الخوارزميات الجينية (حلقة 2) Genetic Algorithm

facebook-group

السلام عليكم ورحمة الله وبركاته

أتمنى ألا أكون قد أطلت عليكم , ريثما قمت بإعداد الحلقة الثانية من الخوارزميات الجينية

في هذه الحلقة سنقوم بشرح الآلية التي نقوم وفقها بإسقاط المفهوم البيولوجي السابق – التي وقفنا عنده في الحلقة الأولى – ضمن إطار البرمجة والمعلوماتية .

لن أطيل عليكم الحديث عبر المقدمة ,وسأدعكم للتفاصيل التقنية الممتعة مع خالص تمنياتي لكم بالفائدة .

ما ستتعلمه في هذه الحلقة :

كيفية اسقاط المفهوم البيولوجي في مجال الحوسبة وحل المسائل.

المكونات الأساسية الثلاث للخوارزميات الجينية .

كيفية اسقاط المفهوم البيولوجي في مجال الحوسبة وحل المسائل:

يتضح لدينا من الحلقة السابقة المنطلق البيولوجي الذي تم استيحاء فكرة الخوارزميات الجينية منه.

أما في مجال الحوسبة فإن الفكرة الأساسية التي أظهرت الحاجة لنوع من الخوارزميات مماثل نوعاً ما ,لألية عمل الكروموزومات في الكائنات الحية هي التالية:

غالباً عند محاولة حل مسألة ما , يكون لدينا في كل مرة حل , لكنه للأسف ,فإن هذا الحل غالباً لا يكون الحل الأمثلي , وإنما نستطيع وضوحاً أن نر بأنه لو كان بإمكاننا مكاملة  هذا الحل مع حل سابق للمسألة بشكل أو بآخر, لاستطعنا الوصول للحل الأمثل. أي: لو أن عدد من الحلول تواجدت معاً في لحظة معينة ,نلاحظ ان الحل الأمثلي يكون مبعثراً بينها , وبالتالي فإن وجود الية لدمج هذه الحلول , قد تولد لنا في لحظة ما الحل الأمثل ,فإذا تخيلنا كل حل بمثابة تتالي من الجينات ضمن كروموزوم –حل – المتواجد بدوره ضمن مجموعة من الكروموزومات المختلفة –عدة حلول للمسألة –ضمن تجمع ما population  ,عندها بإمكاننا عبر العمليات المتاحة على الكروموزمات –التصالب والطفرة – انتاج حلول جديدة –كروموزومات جديدة أبناء–  قد يمثل أحدها الحل الأمثل , ونستطيع تقييم هذا الحل , عبر تابع الصلاحية fitness function  , الذي سيقيس جودة هذا الحل , وبالتالي فرصته بالنجاة , والانتقال للجيل التالي.

 

مما سبق نستطيع ان نر بأن هنالك 3 مكونات اساسية للخوارزميات الجينية :

المكونات الاساسية الثلاث للخوارزميات الجينية:  [2] [4]

1: طريقة ترميز الحل-الكروموزوم-بما يناسب المسألة المطروحة.

2: تابع الصلاحية fitness function   ,ويستخدم لتقيم الحلول.

3: المؤثرات –العمليات- الجينية (التصالب والطفرة).

 

1 : نعلم بأن الخوارزميات الجينية تنطلق من مجموعة عشوائية من الحلول –حلول المسألة المطروحة- وبالتالي

فإن أهم شئ يجدر بنا التفكير به , هو التمثيل البرمجي الأنسب والسليم لهذه الحلول بحيث نسرع الخوارزمية بهدف الوصول للحل الأمثل , وطبعاً عملية اختيار التمثيل الأنسب عملية تابعة للمسألة التي نسعى لحلها ,ولكن هنالك عدد من أساليب التمثيل الشهيرة التي تم تطبيقها على مسائل مناسبة لها ولاقت نجاحاً ملحوظأ ,

  سنعدد هنا – على سبيل الذكر لا الحصر- بعض هذه  الطرائق الشهيرة والناجحة المستخدمة في ترميز الحلول

  1:الترميز الثنائي Binary Encoding

ويعد من أشهر الطرائق المسخدمة في تمثيل الحلول في الخوارزميات الجينية , وتنبع شهرته لكونه أول اسلوب تم استخدامه في ترميز الحلول في الخوارزميات الجينية , حيث يتم هنا ترميز كل حل –كروموزوم – على شكل سلسلة من البتات 0 أو 1.

 الشكل التالي يوضح شكل كروموزوم يستخدم التمثيل الثنائي:

Chromosome A

101100101100101011100101

Chromosome B

111111100000110000011111

 

مثال على مسائل تستخدم هذا التمثيل:

مسألة حقيبة الظهر Knapsack problem

وهذه المسألة تهدف إلى حمل كل ما غلا ثمنه ,وخف وزنه ,في حقيبة تحمل على الظهر , و يكون لدينا في هذه المسألة مجموعة محددة من الأغراض , لكل منها وزن وثمن محدد, حيث باستخدام الترميز الثنائي فإن كل بت يشير إلى غرض ما ,ويمثل فيم اذا تم أخذ ذاك الغرض ووضعه في الحقيبة أم لا .

  

   2: تمثيل التباديل permutation Encoding

في هذا النوع من التراميز كل كروموزوم يمثل سلسلة من الأعداد  –أو الرموز- غير المتكررة , والمتوضعة وفق تتالي ما.

 

الشكل التالي يوضح شكل كروموزوم يستخدم ترميز التباديل مرةً باستخدام الأعداد , ومرةً باستخدام الأحرف

Chromosome A

1  5  3  2  6  4  7  9  8

Chromosome B

8  5  6  7  2  3  1  4  9

 

Chromosome A

L I G H T

Chromosome B

I G T H L

 

يستخدم ترميز التباديل عادةً في مسائل الترتيب Ordering Problems , مثل مسألة البائع المتجول TSP[*]

 , ومسألة جدولة المهام Task Ordering Problem .

 

  3: ترميز القيمة Value Encoding

في هذا النوع من التمثيل يكون لدينا كل كروموزوم عبارة عن سلسلة من بعض القيم –المرتبطة بشكل وثيق بمسألة ما –ويمكن لهذه القيم أن تأخذ عدة صيغ ممكنة وذلك حسب المسألة التي يتم معالجتها , مثل سلاسل من الأرقام , الأعداد الحقيقية , محارف , أو حتى مجموعات من أغراض معقدة Complicated Objects.

 

الشكل التالي يمثل بعض الكروموزومات التي تستخدم ترميز القيمة

Chromosome A

1.2324  5.3243  0.4556  2.3293  2.4545

Chromosome B

ABDJEIFJDHDIERJFDLDFLFEGT

Chromosome C

(back), (back), (right), (forward), (left)

 

ويستخدم عادةً في المسائل التي تستخدم بعض القيم المعقدة كالأعداد الحقيقية .

ملاحظة :

من أجل هذا النوع من التمثيل قد نضطر إلى تطوير مؤثرات تصالب وطفرة خاصة , لتناسب علية التمثيل المستخدمة في هذه المسائل.

مثال على مسائل تستخدم هذا النوع من الترميز:

إيجاد مجموعة الأوزان لشبكة عصبونية Finding weights for neural network

 

   4:ترميز الشجرة Tree Encoding

يستخدم هذا النوع من الترميز بشكل أساسي للتعابير والبرامج التطورية evolving programs or expressions  ,كما يستخدم للبرمجة الجينية  genetic programming .

حيث يكون كل كروموزوم في ترميز الشجرة بمثابة شجرة من بعض الأغراض objects  , مثل التوابع أو الأوامر في لغات البرمجة .

 

الشكل التالي يمثل كروموزومات تستخدم ترميز الشجرة

Chromosome A

Chromosome B

 

( +  x  ( /  5  y ) )

( do_until  step  wall )

 

ونعود ونذكر بأن هذا النوع من الترميز مفيد في البرامج التطورية evolving programs  .

لغة البرمجة LISP  تستخدم هذا النوع من التمثيل ,وذلك لأن البرامج ضمنها تمثل بهذا النموذج ,ويمكن بسهولة تحليلها –تحليل بنية البرنامج- Parsing  , باستخدام هذا النموذج في التمثيل ,وبالتالي يمكن عندها تطبيق المؤثرات الجينية –كالتصالب والطفرة – بسهولة باستخدام هذا النموذج في التمثيل.

مثال :

مسألة إيجاد تابع انطلاقاً من عدة نقاط.

إذ تكون المسألة معطاة بالشكل التالي : لدينا مجموعة معطاة من قيم الدخل وقيم الخرج الموافقة لها , والمطلوب إيجاد أفضل تابع يعطي قيم خرج لقيم الدخل المعطاة , وبحيث تقارب هذه القيم –قيم الخرج – قدر الإمكان قيم الخرج المعطاة في المسألة.

حيث يكون الكروموزوم هنا بمثابة توابع ممثلة في بنية الشجرة .

 

ونعود ونأكد بأن طبيعة المسألة هي التي تحكم عملية التمثيل ,إذ أن هنالك علاقة وثيقة بين التمثيل المستخدم وشروط المسألة المطلوب حلها ,مثال على ذلك مسألة البائع المتجولTSP[*]

 حيث من شروط المسألة :

يجب زيارة مدينة ما مرة واحدة وفقط واحدة ,وبالتالي فإن أحد التمثيلات المناسبة هو عبارة عن تبديلpermutation  بين سلسلة من المحارف أو الأعداد الصحيحة , حيث كل سلسلة –التي تمثل حل في النهاية – لا يتكرر فيها رمز ما أكثر من مرة واحدة .

 

++++++++++++++++++++++++++++++++

ملاحظة:

[*]

عندما نذكر الخوارزميات الجينية , فإن أول مسألة تخطر في بالنا هي مسألة البائع المتجول TSP  والتي تمثل التي تمثل النموذج الأكاديمي المتعارف عليه غالبأ لتوضيح  فكرة الخوارزميات الجينية,فمسألة البائع المتجول تستخدم على سبيل الذكر لا الحصر لأنها تغطي طيف واسع جداً من المسائل والتطبيقات العملية التي تتطلب أمثلة في الحلول المطلوبة منها , مثل مسألة حركة القلم المثلى على سطح راسم pen movement of a plotter  , حفر وتثقيب ألواح الدارات المطبوعة drilling of printed circuit boards (PCB) .

مسألة توجيه باصات المدارس , الخطوط الجوية …ألخ .

 

 

++++++++++++++++++++++++++++++++

 

2: أما المكون الثاني فهو : تابع الصلاحية fitness function

في لحظةٍ ما , عندما يكون لدينا عدد من الحلول , نحن بحاجة لألية فعالة ومدروسة توجهنا نحو الحل الأفضل من بين مجموعة من الحلول المطروحة , أي نحن بحاجة لتابع الصلاحية الذي يرشدنا نحو الحل الأمثل , ويعطينا تقييم أولي , اي من هذه الحلول هو أقدر على النجاة وأصلح لأن ينتقل للجيل التالي .

وطبعاً هنا أيضاً فإن عملية اختيار هذا التابع ذو علاقة وثيقة بالمسألة المطروحة , ولا يوجد تابع عام بشكل مطلق لحساب الصلاحية .

ملاحظة :

عملية الانتقال للجيل التالي , تتم عبر عملية الانتقاء Selection Operator التي سنشرحها بعد قليل.

 

3: المكون الثالث يتجلى بالعمليات الجينية Genetic Operators

تنبع أهمية العمليات الجينية من إيجاد حلول لم تكن موجودة سابقاً في فضاء الحلول

ومن أهم العمليات الجينية :

          التصالب crossover or recombination

          الطفرة mutation

ويعتمد بشكل كبير أداء الخورزميات الجينية على هذين المؤثرين , وطبعاً بالتأكيد فإن أسلوب التمثيل المستخدم له دوره ايضاً .

 

عند هذه النقطة سنتوقف هذا اليوم لنكمل الحلقة القادمة الشرح المتعلق بكيفة القيام بعملية التصالب والطفرة برمجياً.

وإلى ذلك الحين , استودعكم الله , والسلام عليكم ورحمة الله وبركاته.

مع تحيات : م. نور الصباحي

فهرس سلسلة الخوارزميات الجينية :

  1. الخوارزميات الجينية ( الحلقة الأولى)
  2. الخوارزميات الجينية ( الحلقة الثانية)
  3. الخوارزميات الجينية ( الحلقة الثالثة)
  4. الخوارزميات الجينية ( الحلقة الرابعة والأخيرة)
Advertisements

, , , , , , , ,

  1. #1 by محمد ديوب on أغسطس 14, 2008 - 4:37 ص

    ماشاء لله عليك أخ نور ..
    موضوع مهم يستحق الترجمة
    بارك الله بك

  2. #2 by سرى on أبريل 14, 2009 - 6:10 م

    السلام عليكم
    تسلم على هذا الشرح
    انا طالبة دكتوراةوارغب في استخدام الخوارزميات الجينية في اطروحتي ولكن الطلاب اللي معي قالوا انها موضوع قديم وظهرت عدة برامج يمكن استخدامها
    بكونك مهتم بهذا الموضوع بأي شي تنصحني استخدمها ام استخدم البدائل ؟ وما هي هذه البدائل عن الخوارزمية الجينية
    جزاك الله الف خير

  3. #3 by محمد سلمان on أغسطس 3, 2009 - 7:35 ص

    السلام عليكم موضوع جميل وبطريقة شرح مميزةهل يمكن ارشادنا الى كتب عربي تساعد على معرفة تفاصيل اكثر عن الموضوع وجزاكم الله كل خير

    • #4 by schwarztiger on أغسطس 6, 2009 - 6:26 ص

      وعليكم السلام ورحمة الله وبركاته
      بالنسبة للكتب العربية , فبالنسبة لي لا أعرف أي مرجع عربي , وكانت كل مراجعي للموضوع باللغة الانكليزية وقمت بالترجمة واعادة الصياغة لإيصال الفكرة بشكل واضح ومبسط
      أما بالنسبة لذكر مثال , فإذا كنت قد قرأت الحلقات الأربع كاملة , فأعتقد بأنك ستجد ما تبحث عنه , وفي حال وجود نقطة غير واضحة في أحد الأمثلة المطروحة , أرجو الإشارة الى المثال , وفي أي حلقة ورد , وسأقوم بشرح مفصل لتلك النقطة

  4. #5 by احمد on يناير 17, 2010 - 11:11 م

    شكرا لك , شرح جميل جدا …
    انت تشجعني على طرح ما لدي في مدونات
    شكرا مرة اخرى و جزاك الله خيرا …

اترك رد

Please log in using one of these methods to post your comment:

WordPress.com Logo

أنت تعلق بإستخدام حساب WordPress.com. تسجيل خروج   / تغيير )

صورة تويتر

أنت تعلق بإستخدام حساب Twitter. تسجيل خروج   / تغيير )

Facebook photo

أنت تعلق بإستخدام حساب Facebook. تسجيل خروج   / تغيير )

Google+ photo

أنت تعلق بإستخدام حساب Google+. تسجيل خروج   / تغيير )

Connecting to %s

%d مدونون معجبون بهذه: