الخوارزميات الجينية (الحلقة 4 والأخيرة)

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

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

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

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

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

وسأدعكم الآن لتستمتعوا بمحتويات هذه الحلقة الأخيرة من الخوارزميات الجينية بشكل مفصل…

مبدأ الخوارزميات الجينية: [1]

مما سبق نرى بأن مبدأ الخوارزميات الجينية بسيط جداً ويمكن تلخيصه كما يلي :

1: ترميز المسألة بالشكل المناسب والأمثل

2:التوليد العشوائي للتجمعpopulation  البدائي المؤلف من مجموعة من الكروموزومات التي تتألف بدورها من مجموعة من الجينات , حيث ان كل كروموزوم (الذي هو عبارة عن تجمع جيني) عبارة عن حل.

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

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

5:تلي عملية الاختيار , عمليتي التصالب والطفرة .

6: ومن ثم نعود مجدداً للبدء من الخطوة رقم 3.

 

أهمية عمليتي التصالب والطفرة في الخوارزميات الجينية:

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

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

لنتخيل المسألة التالية :

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

(ملاحظة :

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

 

وضوحاً فإن الحل الأمثل هو السلسلة الثنائية الكاملة الوحدان , اي المؤلفة من تتالي 7 واحد دون ورود أي صفر

1111111

Chromosome

 

وبفرض أنه بعد عملية التهيئة العشوائية للحلول كان لدينا مجموعة الحلول التالية :

 

Chromosome A	1100011
Chromosome B	0001100
Chromosome C	0110000

 

نجد أن الحل الأمثلي الذي نبحث عنه موجود ضمن التجمع , ولكنه غير فعال لكونه مبعثر ضمن عدد من الحلول , فنجد أنفسنا هنا بحاجة لآلية التصالب crossover  بهدف دمج هذه الحلول معاُ والوصول للحل المطلوب

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

Chromosome X

1111110

 

 

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

 

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

 

الرسم :

 

 

 

متى تكون الخوارزميات الجينية مفيدة وفعالة : [3]

تكون بشكل عام الخورازميات الجينية مفيدة وفعالة في أحد الحالات التالية :

  1: عندما يكون فضاء البحث كبير جداً و معقد إلى حدٍ ما وغير مفهوم بشكل واضح

 2: المعلومات ,أو بالاحرى المعرفة في المجال المدروس نادرة , أو أنه من الصعب ترميز خبرة الخبير في المجال المدروس بهدف تضيّق فضاء البحث

3:لا يوجد طرائق تحليل رياضي معروفة لحل المسألة .

4: فشلت طرائق البحث التقليدية لحل المسألة .

 

مجالات تطبيق الخوارزميات الجينية : [1]

تم تطبيق الخوارزميات الجينية في عدد كبير من المجالات , منها العلمية , المسائل الهندسية , وفي مجال الأعمال والألعاب و الروبوتات …

بعض التصنيفات الرئيسية التي استخدمت فيها الخوارزميات الجينية :

1:مسائل الأمثلة بشكل عام :

بما فيها الأمثلة العددية , والحسابية مثل مسألة البائع المتجول TSP  ,التصميم الصناعي مثل مسألة آلة تقطيع الخشب ,جدولة أعمال التسوق , أمثلة جودة الصوت والفيديو.

2: البرمجة الاوتوماتيكية :

حيث تم استخدام الخوارزميات الجينية لتطوير برامج حاسوبية بهدف تنفيذ مهام محددة ,ولتصميم بنى حاسوبية أخرى ,مثل شبكات الفرز sorting network  .

3:تعليم الروبوتات والآلات :

تم استخدام الخوارزميات الجينية في كثير من تطبيقات التعلم التلقائي machine –learning  ,ومن ضمنها التصنيف classification  و النتبأ prediction  .

وقد تم استخدام الخوارزميات الجينية في تصميم الشبكات العصبونية neural networks design  .

 

4:النماذج الاقتصادية Economic models

تم استخدام الخوارزميات الجينية لنمذجة آليات ابتكار وتطوير استراتيجيات المزايدة .وفي مجال نشوء الأسواق الاقتصادية emergence of economic markets .

5: التفاعل بين التطور والتعلم :

حيث تم استخدامها لدراسية التأثير المتبادل بين تعلم الأفراد وتطور الأنواع .

6:كنماذج للأنظمة الاجتماعية :

تم استخدامها لدراسة جوانب تطور النظم الاجتماعية , مثل تطور التعاون evolution of cooperation  و تتطور الاتصال evolution of communication  ,سلوك القافلة لدى النمل trail-following behavior in ants .

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

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

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

مراجع للاستزادة
Introduction to Genetic Algorithm www.rennard.org/alife/english/gavintrgb.html	[1]
Introduction to Genetic Algorithm ://cs.felk.cvut.cz/~xobitko/ga	[2]
Genetic Algorithms www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/tcw2/report.html	[3]
//lancet.mit.edu/~mbwall/presentations/IntroToGAs	[4]
Genetic Algorithms and Evolutionary Computation www.talkorigins.org/faqs/genalg/genalg.html	[5]

 

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

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

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

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

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

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

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

سنتابع اليوم من حيث توقفنا في الحلقة الثانية من الخوارزميات الجينية , حيث كنا بصدد مناقشة المكون الثالث للخوارزميات الجينية والذي يتجلى بالعمليات الجينية 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% من عجلة الروليت , عندها سيكون لبقية الكروموزومات فرص ضئيلة جداً لأن يتم اختيارها .

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

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

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

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

المحررون : م.نور 

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

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

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

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

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

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

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

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

 

 

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

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

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

غالباً عند محاولة حل مسألة ما , يكون لدينا في كل مرة حل , لكنه للأسف ,فإن هذا الحل غالباً لا يكون الحل الأمثلي , وإنما نستطيع وضوحاً أن نر بأنه لو كان بإمكاننا مكاملة  هذا الحل مع حل سابق للمسألة بشكل أو بآخر, لاستطعنا الوصول للحل الأمثل. أي: لو أن عدد من الحلول تواجدت معاً في لحظة معينة ,نلاحظ ان الحل الأمثلي يكون مبعثراً بينها , وبالتالي فإن وجود الية لدمج هذه الحلول , قد تولد لنا في لحظة ما الحل الأمثل ,فإذا تخيلنا كل حل بمثابة تتالي من الجينات ضمن كروموزوم –حل – المتواجد بدوره ضمن مجموعة من الكروموزومات المختلفة –عدة حلول للمسألة –ضمن تجمع ما 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)

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

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

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

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

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

 

 

 

الجينات

بدايات التفكير في الخوارزميات الجينية: [1][2] 

ركزت التجارب في الذكاء الصنعي بشكل تقليدي على محاولة تكرار تصرفات الإنسان –أذكى الكائنات الحية -وتطبيقها في مجال البرمجيات ,وقد استطاعت هذه المقاربة نوعاً ما أن تحقق نجاح ملحوظ ,وأكبر مثال على ذلك آلة ديب بلو للعب الشطرنج  Deep Blue chess machine  التي تغلبت على الذكاء البشري المتمثل باللاعب كاسبروف Kasparov  وذلك في شهر أيار من عام 1997  ,لكن عملية المحاكاة السابقة للسلوك البشري , كانت محدودة نوعاً ما, حيث وقفت عاجزة عن حل بعض المسائل , التي يعرف معظم الناس حلها مسبقاً .ومن هنا بدأت تظهر فكرة الطرائق الذكية الحسابية computational intelligence methods  مثل الحوسبة التطورية evolutionary computing  , التي زودت الحاسب بإمكانية حل المسائل المعقدة دون الاعتماد على خبرة الإنسان,وانما حاولت الاستفادة من ألية التطور(المطروحة في نظرية داروين  )وتحويلها لنموذج حاسوبي كإجرائية للأمثلة , فكما في الطبيعة, فإن عملية التطور في الكائنات الحية تهدف للتكيف مع البيئة المحيطة بهدف النجاة فعملية التطور تتجه دوماً نحو ما هو أمثل وأفضل للكائن الحي – و مثال عليها تطور الزرافات بحيث استطالت اعناقها لتستطيع الوصول لغذائها المتمثل في أوراق الأشجار العالية – إذ أن البقاء للأصلح.

 وفعلاً , فلم تلبث الافكار السابقة طويلاً حبيسة المختبرات ,حيث  تم فعلياً طرح   فكرة الخوارزميات الجينية –التي هي جزء من الحوسبة التطورية – بشكل رسمي في الولايات المتحدة عام 1970 من قبل بروفيسور في علوم الحاسب من جامعة ميشيغان Michigan University of يدعى جون هولاند Johon Holland  ويبلغ من العمر 76 عام ,وقد كان قد بدأ بالعمل عليها منذ بدايات الستينيات, وكان هدفه تطور فهم إجرائية التطور الطبيعية وتصميم نظم صناعية لها مميزات مشابهه للنظم الطبيعية.

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

 الأمثلية المحلية بدلاً من الوصول للحل الأمثلي العام ,تلك المطبات التي غالباً ما تقع فيها طرائق البحث التدريجية Gradient search methods , لكن بشكل عام فإن الخوارزميات الجينية تميل لأن تكون مكلفة حسابياً .

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

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

مقدمة بيولوجية  Biological Background: [2]

الكروموزوم:

كل الكائنات الحية تتألف من خلايا, يوجد في كل خلية نفس مجموعة الكروموزومات chromosomes .

حيث ان الكروموزومات هي عبارة عن سلاسل من الدي ان اي DNA  ,وبإمكاننا القول بأن الكروموزومات هي بمثابة نموذج يمثل الكائن كله.

إذ يتألف كل كروموزوم من عدد من الجينات , التي بدورها عبارة عن كتل من الدي ان اي DNA  ,و كل جين gene يرمّز بروتين محدد , اي بشكل اساسي بإمكاننا القول بأن كل جين يرمّز صفة معينة في الكائن الحي , على سبيل المثال لون العينين .

لكل جين ضمن الكروموزوم موقعه الخاص , يدعى هذا الموقع ب locus .

تدعى المجموعة الكاملة من المادة الجينية –اي كل الكروموزومات – بالجينوم genome .

وتدعى مجموعة محددة من الجينات ضمن الجينوم بالجينوتايب genotype  .

يتحول الجينوتايب في الكائن الحي – بعد التطورات التي تلي مرحلة الولادة – إلى الفينوتايب phenotype  , الذي يمثل بدوره خواص فيزيائية مدركة في الكائن الحي , مثل لون العينين , الذكاء , …الخ

 

التكاثرreproduction :

اول مرحلة في عملية التكاثر , هي مرحلة الاتحاد recombination  أو التصالب crossover  بين الكروموزومات, حيث تقوم الجينات من الوالدين في هذه المرحلة-بطريقةٍ ما – بتشكيل الكروموزوم الجديد , وهنالك احتمال  بعدها لهذه الاجيال الجديدة الناتجة new offspring  بأن تخضع للطفرة mutation .

الطفرة Mutation:

 وتعني حدوث تغيير بسيط في بعض عناصر الدي ان اي DNA   , هذه التغيرات تنتج بشكل اساسي من اخطاء اثناء نسخ الجينات من الابوين .

تقاس صلاحيةfitness  الكائن الحي بقدرة الكائن الحي على النجاح في حياته.

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

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

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