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

facebook-group

بسم الله الرحمن الرحيم

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

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

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

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

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

          التصالب crossover or recombination

          الطفرة mutation

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

وكبداية , سنبدأ بشرح عملية التصالب أولاً crossover:وهي عملية منتجة , أي تنطلق من كروموزومين (صبغيين )–حلين – من الجيل الحالي – جيل الآباء – لتعطي بشكل عام حلين أبناء two offspring .

بينما الطفرة , هي عملية يتم فيها إجراء تبديل – تغيّر – على بعض جينات كروموزوم(صبغي ) ما .

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

مثلاً في حال :

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

لدينا طيف واسع من أساليب التصالب crossover  الممكنة,نذكر منها :

   – التصالب بنقطة وحيدة Single point crossover

وفي هذا النوع من التصالب يتم في البداية تحديد نقطة تصالب وحيدة , ومن ثم يتم نسخ الجينات للابن الأول من بداية الكروموزوم الممثل لأحد الوالدين ,لنقطة التصالب , والبقية يتم نسخها من الوالد الثاني ,وينتج الابن الثاني وفق عملية موافقة للعملية السابقة ولكن الأب الذي كان يأخذ منه الجزء الأول من الجينات يصبح مصدر لبقية الجينات , بينما الأب الثاني تأخذ منه السلسلة الجينية من بدايته لنقطة التصالب,وتنسخ للابن الثاني

الرسم التوضيحي التالي يبين آلية العملية السابقة:

 

 

11001011+11011111 = 11001111

Chromosome parent A

11001011

Chromosome parent B

11011111

Offspring  C

11001111

Offspring  D

11011011

 

– التصالب وفق نقطتين Two point crossover

في البداية يتم اختيار نقطتي تصالب , حيث يتم هنا نسخ من بداية الكروموزوم (الصبغي ) لأول نقطة تصالب من أحد الوالدين للابن , ومن ثم الجزء من السلسلة الثنائية انطلاقاً من أول نقطة تصالب لثاني نقطة تصالب , يتم نسخها نسخها من الوالد الثاني , بينما بقية السلسلة الثنائية للابن الناتج يتم اخذها من الأب الأول وذلك من ثاني نقطة تصالب لنهاية الأب.

 إليكم الرسم التوضيحي التالي :

 
 

 

11001011 + 11011111 = 11011111

Chromosome parent A

11001011

Chromosome parent B

11011111

Offspring  C

11011111

Offspring  D

11001011

 

Uniform crossover

ويتم في هذا النوع من التصالب اختيار بتات بشكل عشوائي ونسخها من الوالد الأول أو الوالد الثاني للأبن.

وربّ رسمة خيرُ من ألف جملة توضيحية :

11001011 + 11011101 = 11011111

Chromosome parent A

11001011

Chromosome parent B

11011101

Offspring  C

11011111

Offspring  D

11001001

 

التصالب الحسابي Arithmetic crossover

وفي هذا النوع من التصالب يتم تنجيز بعض العمليات الحسابية وذلك لإنشاء أبناء جدد

11001011 + 11011111 = 11001001 (AND)

الطفرة Mutation

في حالة الترميز الثنائي , تكون الطفرة , ببساطة , ما هي إلا عملية عكس لأحد البتات في الكروموزم (الصبغي ), حيث يتم اختيار البت ثم قلبه

مثال توضيحي:

11001001 => 10001001

  2: ترميز التباديل Permutation Encoding

   – التصالب بنقطة وحيدة Single point crossover

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

والهدف من الإجراء السابق هو الحفاظ على مفهوم التباديل ,وعدم تكرار الرموز في السلسلة الجينية.

ملاحظة :

يوجد طرق متعددة لانتاج بقية الجينات للابن الناتج بعد عملية نسخ الجينات حتى نقطة التصالب الأولى , لكننا لسنا بصدد ذكرها كلها هنا .

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

الطفرة Mutation

ويتم تنجيزها هنا ببساطة عبر تغير الترتيب في السلسلة الممثلة للكروموزوم , حيث يتم اختيار رمزين من الكروموزوم ويتم إجراء التبديل بينهما .

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

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

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

 

الطفرة Mutation

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

 

(1.29  5.68  2.86  4.11  5.55) => (1.29  5.68  2.73  4.22  5.55)

 

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

التصالب :

يتم اختيار نقطة تصالب من كلا الوالدين ,ويتم تقسيم كل من الوالدين عند نقطة التصالب المختارة , ومن ثم يتم تبادل الاجزاء تحت نقطة التصالب تلك بين الوالدين , لإنتاج ابنين جدد new offspring

الإجراء السابق موضح في الرسم التالي إدناه:

الطفرة Mutation

ويمكن تخيلها على انها تديل العمليات أو الأعداد أو … وذلك حسب المسألة المطروحة , أي باختصار العقد التي يتم اختيارها من الشجرة , يتم اجراء التبديل عليها .

 الانتقاء Selection

ومما اتضح لنا سابقاً من الخطوط العريضة التي تسير وفقها الخورزميات الجينية,فإن الكروموزومات (الصبغيات )  الآباء التي تخضع لعملية التصالب , يتم اختارها –انتقائها – وفق آلية محددة من التجمع الحالي .

تكمن المسألة هنا في كيفية اختيار هذه الكروموزومات (الصبغيات ) ,فحسب نظرية داروين في التطور , فإن الكروموزومات (الصبغيات ) الأفضل يجب أن تنجو , ومنها تنشأ الكروموزومات (الصبغيات ) الأبناء .

إذن تعود مسألتنا هنا إلى مسألة الاختيار الأمثل .عملياً يوجد عدة طرائق لتحديد كيفية انتقاء الكروموزوم (الصبغي )الأمثل , على سبيل المثال :

عجلة الروليت Roulette wheel Selection  ,انتقاء بولتزمان Boltzman selection  , tournament selection  ,انتقاء الحالة المستقرة Steady state selection  …إلخ

سنورد فيمايلي شرح لطريقة عجلة الروليت في الانتقاء:

1-      اختيار عجلة الروليت Roulette Wheel Selection

يتم اختيار الوالدين في هذه الطريقة اعتماداً على قيم صلاحياتهم,فكلما ازدادت قيمة صلاحية الكروموزوم , كلما ازداد احتمال اختياره .

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

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

باختصار ,يمكننا تلخيص الاجرائية السابقة وفق الخوارزمية التالية:

1:(المجموع) حساب مجموع قيم صلاحية كل الكروموزومات الموجودة ضمن التجمع ولنرمز له ب S.

2: (الاختيار) توليد عدد عشوائي   rضمن المجال [0,S]

3: (حلقة)نمر بحلقة على الكروموزومات ضمن التجمع ونقوم بحساب مجموع قيم الصلاحيات أثناء هذا المرور, وعندما نصل لقيمة لهذا المجموع أكبر من r   عندها نتوقف , ونعيد الكروموزوم الذي وصلنا عنده وأدى لكسر الحلقة.

ملاحظة : بالطبع فإن الخطوة رقم 1  نتفذ مرة واحدة فقط من أجل كل تجمع.

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

وبهذا القدر سنكتفي هذا اليوم لنتابع معاً في الحلقة القادمة المزيد المزيد عن الخوارزميات الجينية

ولنتابع – إن شاء الله – في مناقشة مبدأ الخوارزميات الجينية  ,والإشارة إلى أهمية كل من عمليتي التصالب والطفرة بشكل عملي…

ونحن بانتظار تعليقاتكم الكريمة , ونقدكم الكريم البناء لهذا الموضوع.

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

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

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

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

, , , , , , , ,

  1. #1 by محمد ديوب on أغسطس 18, 2008 - 9:01 م

    ما شاء الله أخ نور ….
    وفقك الله
    أكمل أنا من متابع معك باهتمام كبير

  2. #2 by Jehazee on أبريل 15, 2009 - 10:48 ص

    حياك الله اخي, نور
    احببت ان ارد على مقالتك وحتى قبل ان اقراءها … واشكرك على هذه الاطروحات والمقالات المميزه ,ٍسأقراء المقاله ثم اقوم بالرد عليك .. مجدداً ,لدعوه للنقاش

  3. #3 by anass sati on أبريل 22, 2009 - 1:01 م

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

    • #4 by schwarztiger on أبريل 25, 2009 - 5:27 م

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

  4. #5 by anass sati on مايو 17, 2009 - 2:30 م

    السلا م عليكم اخى الكريم اود ان اسال عن تقنية لها علاقة بالخوارزمية تسمى
    Niching techniques

    • #6 by schwarztiger on مايو 19, 2009 - 7:23 م

      السلا م عليكم ورحمة الله وبركاته
      أخي الكريم , إن تقنية
      Niching techniques
      هي عبارة عن تقنية تستخدم في الحوسبة التطورية بشكل عام , من أجل الحفاظ على تنوع واختلاف التجمع , وحتى تمكننا من استكشاف فضاء الحلول بشكل فعال أكثر .
      والسلام عليكم

  5. #7 by ماريا إسلام on يناير 9, 2011 - 2:24 م

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

    • #8 by schwarztiger on يناير 23, 2011 - 7:12 م

      وعليكم السلام ورحمة الله وبركاته
      اعتذر على التأخر في الرد , وان شاء الله في القريب ا لعاجل اكتب عن الطرق الاخرى غير عجلة الروليت , وبإمكانك الان متابعة بقية الردود والتطويرات على موقعي الجديد التالي
      mathaheb.com

اترك رد

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 مدونون معجبون بهذه: