منيرة
11-28-2009, 04:51 PM
خوارزمية الجينات أو الخوارزمية الوراثية
تعريف خوارزمية الجينات
هي تقنية بحث، تستخدم في مجال الذكاء الاصطناعي artificial intelligence وتحديداً في فرع البحث وحل المشاكل Problem solving and search. تقوم بايجاد أفضل الحلول لمشاكل التحسين optimization problems بالاعتماد على العشوائية stochastic في البحث.
اخترعها جون هولند John Holland في الستينات، وطورها هو وطلابة وزملائه. وكان اختراعه مبنياً على فكرة الحوسبة التطورية لإنغو رشنبرغ Ingo Rechenberg.
كما يظهر من اسم هذه الخوارزمية أنها أُستلهمت من الجينات في جسم الانسان، وكذلك استفادت من نظرية التطور لداروين -مع بطلان ومغالطة هذه النظرية للواقع ولكن أمكن الاستفادة منها في هذا المجال-. مما هو معروف أن الجينات في جسم الانسان يحصل بينها تزاوج يؤدي إلى انتاج جيل جديد من الجينات. ونظرية التطور وبالتحديد ما تدعوه الاختيار الطبيعي natural selection هو عملية يتم بها بقاء ونجاة الأفراد ذوو الميزات الأفضل. وإذا كانت هذه الميزات قابلة للتوريث فإنها تورث للأجيال القادمة مما يعني أن الميزات الأفضل والقابلة للتوريث تصبح أكثر شيوعاً في الأجيال اللاحقة.
لذا فإن خوارزمية الجينات تقوم بتزويج الجينات المعرفة فيها ، وتحتفظ بالميزات ذات الأفضلية ، وتنتج أجيالاً جديدة ، وتستمر بإجراء هذه العمليات حتى تحصل على أفضل فرد يمكن الحصول عليه ، والذي يمثل الحل.
حتى الآن قد يبدو هذا الأمر صعباً ومستعصياً على الاستيعاب، سأشرح طريقة عملها بالتفصيل لاحقاً، ولكن يجب أن أتأكد من أنك تدرك أن هذه الخوارزمية تعيد العمليات (تزويج الجينات، الاحتفاظ بالميزات ذات الأفضلية، وانتاج أجيال جديدة) حتى تحصل على أفضل فرد. واحتاج إلى تعريفك بمصطلحات مهمة لفهم هذه الخوارزمية.
مصطلحات مهمة لفهم الخوارزمية
مجال البحث search space: ويسمى أيضاً مجال الحالات state spaceهو المجال المحتوى على جميع الحالات states التي تمثل الحلول الملائمة ، ونحن نبحث عن الحل لمشكلتنا الذي هو واحد من هذه الحلول الملائمة. أكبر مشكلة هي أن مجال البحث من الممكن أن يكون كبيرا للغاية ومعقداً ، فلا نعلم من أين نبدأ وأين نبحث بالضبط حتى نجد الحل، لذلك نستخدم بعض طرق البحث ومنها خوارزمية الجينات ، حتى نبحث عن الحل في أماكن متفرقة وبسرعة، والحل الناتج من هذه الخوارزمية يعتبر حل جيد (نظرا لكبر مجال البحث) ، لأنه غير ممكن في كثير من الأحيان اثبات أن هذا الحل هو الحل الأفضل!
الفرد Individual : (ويسمى أيضاً كروموسوم chromosome و حالة state) تعني فرد أو شخص، وهي تمثل الأفراد الناتجين عن التزاوج ، ويمكن لأي فرد تتوفر به بعض الشروط أن يكون هو الحل للمشكلة التي نحاول حلها. ويمثل في الخوارزمية بسلسلة string من الأرقام أو الأحرف (تخيل هذه الأرقام والحروف على أنها جينات في الكروموسوم). شاهد الشكل 1.
شكل1 : مقارنة بين الكروموسوم في الخوارزمية وفي الطبيعة
(جميع الأشكال مرفقة على الرابط المبين أدناه )
http://www.gulfup.com/do.php?id=1353041
المجموعة الحيوية Population: وهي مجموعة من الأفراد individuals المولدين عشوائياً ويمثلون أفراد أو حالات مختلفة. انظر الشكل2.
شكل2 : مقارنة بين المجموعة الحيوية في الخوارزمية وفي الطبيعة
التكاثر أو التناسل Reproduction: تمثله العمليات التالية:
1.التزاوج Crossover: وهي عملية التزاوج بين الأفراد والتي تنتج أجيال جديدة
2.التحوير Mutation : التغيير وهي عملية تتم على سلسلة الفرد لتغيير أحد الجينات فيه (تغير رقم أو حرف حسب نوع السلسلة) ، وتستخدم لتحافظ على التنوع من مجموعة الحيوية إلى الأخرى. انظر الشكل 3.
دالة الكفاءة Fitness function: (وتسمى أيضا دالة الهدف objective function) وهذه الدالة ليست واحده لكل مشكلة، بل إن أصعب جزء في الخوارزمية هو اختيار دالة الكفاءة المناسبة، وهي التي تحدد كفاءة أوجدارة أومدى جودة الكروموسوم بالنسبة للمشكلة المراد حلها. انظر الشكل 3.
نقطة التزاوج Crossover point: موضع نقطة التزاوج في سلسلة الفرد. انظر الشكل 3.
النسل Offspring: وهم الأفراد الناتجون عن عملية تزاوج الأباء. انظر الشكل 3.
الاختيار Selection : هي عملية اختيار الفرد الأفضل من الجيل الجديد، ويعتمد اختيار الفرد الأفضل على دالة الجدارة.
معايير التوقف Stopping Criteria: هي شروط يحددها المستخدم تحدد متى يريد أن تتوقف الخوارزمية ، وسأذكر الشروط لاحقاً.
شكل3 :توضيح لبعض عمليات الخوارزمية
خطوات عمل الخوارزمية
1.البداية: كون مجموعة حيوية من ن كرموموسوم ، وعبئها بقيم عشوائية.
2.ابدأ العمل من هنا:
a.حساب الكفاءة: احسب دالة الكفاءة لكل كروموسوم في المجموعة الحيوية الحالية، واستخرج نسبة كفاءة الكروموسوم بالنسبة للبقية.
b.انشاء مجموعة حيوية جديدة: أنشئ مجموعة حيوية جديدة بتكرار الخطوات التالية حتى تكتمل المجموعة:
i.الاختيار: اختر كروموسومان ليمثلا الوالدين من المجموعة ، بناء على دالة الكفاءة لهم، كلما كانت دالة الكفاءة للكروموسوم أعلى* كلما زادت نسبة اختياره، ولكن تجدر الاسارة إلى أنه يوجد الكثير من الطرق التي تحدد اختيار الكروموسوم.
ii.التزاوج: زاوج الكروموسومين عند نقطة التزاوج** اذا كان لديهما احتمالية تزاوج crossover probability ، ويتم التزاوج بانقسام كل كروموسوم عند نقطة التزاوج ، ثم يوصل كل جزء من أحد الكروموسومين مع الجزء المقابل من الكروموسوم الآخر ، فينتج لدينا كرومسومان جديدان.
iii.التحوير: يتم تحوير الكروموسوم الجديد اذا كان لدية احتمالية تحوير mutation probability
iv.القبول: أضف الكروموسوم الناتج إلى المجموعة الحيوية الجديدة
c.استبدال المجموعات: استبدل المجموعة الحيوية القديمة بالمجموعة الحيوية الجديدة.
d.اختبر شرط التوقف عن البحث***:
i.شرط الانتهاء متحقق: توقف واجعل أفضل كروموسوم في المجموعة الحيوية الجدية هو الحل.
ii.شرط الانتهاء لم يتحقق: اكمل البحث بالدوران مرة اخرى بدءً من النقطة 2 ، وانتبه أن المجموعة الحيوية الحالية هي المجموعة الجديدة (نقطة3).
* كما ذكرت في البداية هذه الخوارزمية توجد أفضل الحلول لمشاكل التحسين optimization problems، لذا في مشاكل التحسين هذه قد نحتاج إلى إيجاد أكبر دالة هدف maximizing the objective function ، لذا فإننا عند اختبار كفاءة الكروموسوم نختار من له أعلى دالة كفاءة. وقد نحتاج إلى أيجاد أصغر دالة هدف minimizing the objective function وهنا نختار الكروموسوم ذو الكفاءة الأقل. واختيار احدى الحالتين يعتمد على نوع المشكلة.
** نقطة التزاوج تحدد بعدة طرق ، أبسط طريقة هي اختيار نقطة عشوائية في الكروموسوم ، فينقسم الكروموسومان عند هذه النقطة ويتصل الجزء قبل نقطة التزاوج من الكروموسوم الأول مع الجزء بعد نقطة التزاوج من الكروموسوم الثاني والعكس. يوجد طرق أخرى منها اختيار أكثر من نقطة تزاوج ، ومنها ما هو معقد . ويوجد تزاوج مخصص ويعني ذلك أن طريقته صنعت لمشكلة محددة وهذا النوع يطور أداء خوارزمية الجينات ، وبالطبع كل هذه الخيارات تعتمد على نوع المشكلة.
*** معايير التوقف Stopping Criteriaأو شروط التوقف Stopping conditions وهي كالتالي:
الأجيال Generations: تتوقف الخوارزمية عندما تصل للعدد المشروط من الأجيال. مثال: عندما تريد أن تستمر الخوارزمية بالبحث عن حل في 50 جيل، فإنها بعد أن تكرر النقاط أعلاه خمسين مرة ستتوقف وتعطيك الحل.
الحدود الزمنية Time limit: تتوقف الخوارزمية عندما ينتهي الوقت بالثواني الذي تحدده.
حدود الكفاءة Fitness limit: تتوقف الخوارزمية عندما تصبح كفاءة الكروموسوم في المجموعة الحيوية الحالية أقل من أو تساوي حدودو الكفاءة .
مهلة الأجيال Stall generations: تتوقف الخوارزمية عندما لا يحدث تطور لدالة الهدف لسلسلة من الأجيال المتتابعة طولها يساوي المهلة المحددة، مثال: عندما تحدد أن مهلة الأجيال 5 ، فإنه اذا مرت خمسة أجيال متتابعة دالة الهدف لم تتغير تتوقف الخوارزمية.
مهلة الوقت Stall time limit: تتوقف الخوارزمية عندما لا يحدث تطور في دالة الهدف خلال مدة زمنية محددة بمهلة الوقت وتحسب بالثواني، مثال: عندما تحدد مهلة الوقت ب 60 ثانية، فإنه اذا مرت 60 ثانية ودالة الهدف للكروموسومات لم تتغير تتوقف الخوارزمية.
تطبيق الخوارزمية
سوف نطبق الخوارزمية بشكل مبسط على مشكلة تسمى الثمان ملكات 8-queens :
شكل4 :مشكلة الثمان ملكات
في لعبة الشطرنج تستطيع الملكة التحرك عمودياً وأفقياً وقطرياً.
لوح الشطرنج مكون من ثمان أعمدة وثمان صفوف.
في مشكلة الثمان ملكات القياسية 8*8 المطلوب هو وضع ثمان ملكات على لوح الشطرنج بحيث لا تهاجم أي من الملكات الأخرى ، بمعنى أن لا تكون أي ملكة في نفس العمود أو الصف أو القطر الذي تكون فيه ملكة أخرى.
سوف نطبق الخوارزمية الآن على هذه المشكلة. ولكن يجب أولا أن نحدد بعض الأمور وهي:
أولاً: الكروموسوم: يجب أن نختار طريقة لتمثيل الكروموسوم، وهي أهم خطوة والتي تبنى عليها بقية الخطوات ، لذلك يجب أن نحرص على أن يكون التمثيل بسيط وسهل التعامل معه. يمكن أن نختار تمثيل الكروموسوم على شكل جدول 8*8 كل ملكة لها عمود وفي العمود نحدد مكانها ! ولكن عندما نتذكر تعقيد الخوارزمية ، يبدو هذا التمثيل مزعجاً وكبيرا جدا وفيه مساحات غير مستخدمة ، والمساحة أمر مهم عند العمل على الحاسوب ويؤثر في سرعة انجاز المهمات، لذلك دعونا نبحث عن طريقة أخرى. سوف نمثل الكرموسوم بثمان خانات فقط، كل خانة تمثل ملكة، والرقم داخل الخانة يمثل موقع الملكة في العمود المقابل لها، كما في الشكل 5.
شكل5 : تمثيل الكروموسوم في مشكلة الثمان ملكات
ثانياً: دالة الكفاءة: سنعبر عن كفاءة الكروموسوم بعدد الملكات اللاتي لا يهاجمن بعضهن، الحد الأدنى يساوي صفر ويعني أن كل الملكات يهاجمن بعضهن، والحد الأعلى يساوي 28 بمعنى أن جميع الملكات لا يهاجمن بعضهن (كل ملكة من الثمان لا تهاجم السبع البقية = 56، وحتى لا نحسب كل ملكة مرتين فإننا نقسم على 2 ، 8 * 7 / 2 = 28 )
ثالثاً: التزاوج: هناك طرق كثيرة لاختيار الكروموسومات لمزاوجتها، و سوف نستعمل طريقة التنقية culling، وهي أن كل كروموسوم له نسبة كفاءة تحت عتبة معينة يستثنى. بناء على هذه الطريقة سنختار العتبة 20 لذلك سنستثني كل كروموسوم دالته تحت هذه الرقم.
رابعاً: التحوير : وهو أن نحور بعض الجينات في أي موضع في الكروموسوم بتغيير الرقم إلى رقم آخر بين 1 – 8. وسوف نحور كل جين له احتمال أقل من 0,1 .
خامساً: معيار التوقف: سيكون معيار التوقف هو الوصول إلى 5 أجيال ثم يعطينا النتيجة .
والآن سنبدأ بالتطبيق بطريقة بسيطة جداً:
1. البداية: سوف نكون مجموعة حيوية من 4 كروموسومات انظر الشكل6 (أ).
2.ابدأ العمل من هنا:
a.نحسب الكفاءة لكل كروموسوم، وذلك بِعَدّ الملكات اللاتي لا يهاجمن بعضهن. ثم نستخرج نسبة كل كروموسوم بالنسبة لبقية الكروموسومات وذلك بقسمة دالة الكروموسوم على مجموع دوال الكروموسومات. بالنسبة للكروموسوم الأول ذو الكفاءة 24 (24 زوج من الملكات لا يهاجمن بعضهن) ، تحسب له النسبة هكذا : 24 / (24 + 23 +20 + 11 ) = 31%. وكذلك بالنسبة لبقية الكروموسومات: الثاني = 23 / ((24 + 23 +20 + 11 ) = 29%. الثالث = 20 / ((24 + 23 +20 + 11 ) = 26%. الرابع = 11 / ((24 + 23 +20 + 11 ) = 14% ، شاهد الشكل 6(ب).
b.ننشىء مجموعة حيوية جديدة ونملأها كالتالي:
i.الاختيار: بما أن العتبة هي20، إذن سنختار الكروموسوم الأول والثاني والثالث فقط.انظر الشكل6 (جـ).
ii.التزاوج: حسب ترتيب النسبة سنزاوج الكروموسومات ، الكروموسوم الأول مع الثاني لأنهم الأعلى درجة ، ثم الثاني مع الثالث. شاهد الشكل6 (د) ونلاحظ هنا أنه يمكن لكروموسوم أن يدخل في عملية التزاوج أكثر من مرة. سوف ينتج لنا كروموسومان جديدان، وبملاحظة هذان الكروموسومان يمكن أن نلاحظ أن التزاوج يؤدي إلى تنوع المجموعة الحيوية بمعنى أن التزاوج يأخذ خطوات كبيرة في مجال البحث وسوف تتقلص هذه الخطوات عندما نصل لاحقا إلى كروموسومات متشابهه، لماذا؟
iii.التحوير: كل مكان في الكروموسوم من الممكن تحويره عشوائياً باحتمال مستقل صغير. سوف نستخدم طريقة غاوسGaussian بحيث نعطي كل جين في الكروموسوم رقم عشوائي من 0 إلى 1 ، اذا كان الرقم أقل من احتمالية التحوير (التي حددناها في الأعلى بـ 0,1) سوف نغير هذا الرقم إلى رقم آخر عشوائي بين 1 و8، كما نشاهد في الشكل6 (هـ).
iv.القبول: نقبل الكروموسوم الناتج ونضعه في المجموعة الحيوية الجديدة.
شكل6 : تطبيق الخوارزمية (أ) المجموعة الحيوية الجديدة ، ترتب حسب دالة الكفاءة في (ب) ثم يتم الاختيار (جـ) بناء على دالة الكفاءة، وتتم مزاوجة الكروموسومات حسب الترتيب (د) وثم يطبق التحوير (هـ)
c.استبدال المجموعات: سوف نستبدل المجموعة الأولى بالمجموعة الجديدة.
d.اختبر شرط التوقف: عدد الأجيال حتى الآن جيل واحد فقط إذن نكمل ، وهكذا يتم تطبيق الخطوات السابقة مرة أخرى حتى يتحقق شرط التوقف وهو الوصول إلى 5 أجيال ، ثم يصبح الكروموسوم صاحب أعلى دالة كفاءة هو الحل. يظهر هنا أنه من الممكن أن تكون النتيجة غير مرضية ويكون الكروموسوم الناتج لا يحل المشكلة وذلك لأن عدد الكروموسومات في المجموعة الحيوية قليل ولأن شرط التوقف – 5 أجيال - لم يسمح للخوارزمية أن تتعمق في البحث حتى تحصل على أفضل نتيجة .
برمجة الخوارزمية
يوجد الكثير من الأشخاص في الانترنت الذين قاموا ببرمجة هذه الخوارزمية ولكن الذي شاهدته حتى الآن برامج مخصصة لمشكلة معينة، ولكن يوجد في ماتلاب MATLAB دالة تقوم بتطبيق هذه الخوارزمية بسهولة وهي دالة ga ، بينما يلزمك معرفة بعض الأمور حتى تستطيع استخدامها .
المصدر : بحث/ هند الروقي.
تعريف خوارزمية الجينات
هي تقنية بحث، تستخدم في مجال الذكاء الاصطناعي artificial intelligence وتحديداً في فرع البحث وحل المشاكل Problem solving and search. تقوم بايجاد أفضل الحلول لمشاكل التحسين optimization problems بالاعتماد على العشوائية stochastic في البحث.
اخترعها جون هولند John Holland في الستينات، وطورها هو وطلابة وزملائه. وكان اختراعه مبنياً على فكرة الحوسبة التطورية لإنغو رشنبرغ Ingo Rechenberg.
كما يظهر من اسم هذه الخوارزمية أنها أُستلهمت من الجينات في جسم الانسان، وكذلك استفادت من نظرية التطور لداروين -مع بطلان ومغالطة هذه النظرية للواقع ولكن أمكن الاستفادة منها في هذا المجال-. مما هو معروف أن الجينات في جسم الانسان يحصل بينها تزاوج يؤدي إلى انتاج جيل جديد من الجينات. ونظرية التطور وبالتحديد ما تدعوه الاختيار الطبيعي natural selection هو عملية يتم بها بقاء ونجاة الأفراد ذوو الميزات الأفضل. وإذا كانت هذه الميزات قابلة للتوريث فإنها تورث للأجيال القادمة مما يعني أن الميزات الأفضل والقابلة للتوريث تصبح أكثر شيوعاً في الأجيال اللاحقة.
لذا فإن خوارزمية الجينات تقوم بتزويج الجينات المعرفة فيها ، وتحتفظ بالميزات ذات الأفضلية ، وتنتج أجيالاً جديدة ، وتستمر بإجراء هذه العمليات حتى تحصل على أفضل فرد يمكن الحصول عليه ، والذي يمثل الحل.
حتى الآن قد يبدو هذا الأمر صعباً ومستعصياً على الاستيعاب، سأشرح طريقة عملها بالتفصيل لاحقاً، ولكن يجب أن أتأكد من أنك تدرك أن هذه الخوارزمية تعيد العمليات (تزويج الجينات، الاحتفاظ بالميزات ذات الأفضلية، وانتاج أجيال جديدة) حتى تحصل على أفضل فرد. واحتاج إلى تعريفك بمصطلحات مهمة لفهم هذه الخوارزمية.
مصطلحات مهمة لفهم الخوارزمية
مجال البحث search space: ويسمى أيضاً مجال الحالات state spaceهو المجال المحتوى على جميع الحالات states التي تمثل الحلول الملائمة ، ونحن نبحث عن الحل لمشكلتنا الذي هو واحد من هذه الحلول الملائمة. أكبر مشكلة هي أن مجال البحث من الممكن أن يكون كبيرا للغاية ومعقداً ، فلا نعلم من أين نبدأ وأين نبحث بالضبط حتى نجد الحل، لذلك نستخدم بعض طرق البحث ومنها خوارزمية الجينات ، حتى نبحث عن الحل في أماكن متفرقة وبسرعة، والحل الناتج من هذه الخوارزمية يعتبر حل جيد (نظرا لكبر مجال البحث) ، لأنه غير ممكن في كثير من الأحيان اثبات أن هذا الحل هو الحل الأفضل!
الفرد Individual : (ويسمى أيضاً كروموسوم chromosome و حالة state) تعني فرد أو شخص، وهي تمثل الأفراد الناتجين عن التزاوج ، ويمكن لأي فرد تتوفر به بعض الشروط أن يكون هو الحل للمشكلة التي نحاول حلها. ويمثل في الخوارزمية بسلسلة string من الأرقام أو الأحرف (تخيل هذه الأرقام والحروف على أنها جينات في الكروموسوم). شاهد الشكل 1.
شكل1 : مقارنة بين الكروموسوم في الخوارزمية وفي الطبيعة
(جميع الأشكال مرفقة على الرابط المبين أدناه )
http://www.gulfup.com/do.php?id=1353041
المجموعة الحيوية Population: وهي مجموعة من الأفراد individuals المولدين عشوائياً ويمثلون أفراد أو حالات مختلفة. انظر الشكل2.
شكل2 : مقارنة بين المجموعة الحيوية في الخوارزمية وفي الطبيعة
التكاثر أو التناسل Reproduction: تمثله العمليات التالية:
1.التزاوج Crossover: وهي عملية التزاوج بين الأفراد والتي تنتج أجيال جديدة
2.التحوير Mutation : التغيير وهي عملية تتم على سلسلة الفرد لتغيير أحد الجينات فيه (تغير رقم أو حرف حسب نوع السلسلة) ، وتستخدم لتحافظ على التنوع من مجموعة الحيوية إلى الأخرى. انظر الشكل 3.
دالة الكفاءة Fitness function: (وتسمى أيضا دالة الهدف objective function) وهذه الدالة ليست واحده لكل مشكلة، بل إن أصعب جزء في الخوارزمية هو اختيار دالة الكفاءة المناسبة، وهي التي تحدد كفاءة أوجدارة أومدى جودة الكروموسوم بالنسبة للمشكلة المراد حلها. انظر الشكل 3.
نقطة التزاوج Crossover point: موضع نقطة التزاوج في سلسلة الفرد. انظر الشكل 3.
النسل Offspring: وهم الأفراد الناتجون عن عملية تزاوج الأباء. انظر الشكل 3.
الاختيار Selection : هي عملية اختيار الفرد الأفضل من الجيل الجديد، ويعتمد اختيار الفرد الأفضل على دالة الجدارة.
معايير التوقف Stopping Criteria: هي شروط يحددها المستخدم تحدد متى يريد أن تتوقف الخوارزمية ، وسأذكر الشروط لاحقاً.
شكل3 :توضيح لبعض عمليات الخوارزمية
خطوات عمل الخوارزمية
1.البداية: كون مجموعة حيوية من ن كرموموسوم ، وعبئها بقيم عشوائية.
2.ابدأ العمل من هنا:
a.حساب الكفاءة: احسب دالة الكفاءة لكل كروموسوم في المجموعة الحيوية الحالية، واستخرج نسبة كفاءة الكروموسوم بالنسبة للبقية.
b.انشاء مجموعة حيوية جديدة: أنشئ مجموعة حيوية جديدة بتكرار الخطوات التالية حتى تكتمل المجموعة:
i.الاختيار: اختر كروموسومان ليمثلا الوالدين من المجموعة ، بناء على دالة الكفاءة لهم، كلما كانت دالة الكفاءة للكروموسوم أعلى* كلما زادت نسبة اختياره، ولكن تجدر الاسارة إلى أنه يوجد الكثير من الطرق التي تحدد اختيار الكروموسوم.
ii.التزاوج: زاوج الكروموسومين عند نقطة التزاوج** اذا كان لديهما احتمالية تزاوج crossover probability ، ويتم التزاوج بانقسام كل كروموسوم عند نقطة التزاوج ، ثم يوصل كل جزء من أحد الكروموسومين مع الجزء المقابل من الكروموسوم الآخر ، فينتج لدينا كرومسومان جديدان.
iii.التحوير: يتم تحوير الكروموسوم الجديد اذا كان لدية احتمالية تحوير mutation probability
iv.القبول: أضف الكروموسوم الناتج إلى المجموعة الحيوية الجديدة
c.استبدال المجموعات: استبدل المجموعة الحيوية القديمة بالمجموعة الحيوية الجديدة.
d.اختبر شرط التوقف عن البحث***:
i.شرط الانتهاء متحقق: توقف واجعل أفضل كروموسوم في المجموعة الحيوية الجدية هو الحل.
ii.شرط الانتهاء لم يتحقق: اكمل البحث بالدوران مرة اخرى بدءً من النقطة 2 ، وانتبه أن المجموعة الحيوية الحالية هي المجموعة الجديدة (نقطة3).
* كما ذكرت في البداية هذه الخوارزمية توجد أفضل الحلول لمشاكل التحسين optimization problems، لذا في مشاكل التحسين هذه قد نحتاج إلى إيجاد أكبر دالة هدف maximizing the objective function ، لذا فإننا عند اختبار كفاءة الكروموسوم نختار من له أعلى دالة كفاءة. وقد نحتاج إلى أيجاد أصغر دالة هدف minimizing the objective function وهنا نختار الكروموسوم ذو الكفاءة الأقل. واختيار احدى الحالتين يعتمد على نوع المشكلة.
** نقطة التزاوج تحدد بعدة طرق ، أبسط طريقة هي اختيار نقطة عشوائية في الكروموسوم ، فينقسم الكروموسومان عند هذه النقطة ويتصل الجزء قبل نقطة التزاوج من الكروموسوم الأول مع الجزء بعد نقطة التزاوج من الكروموسوم الثاني والعكس. يوجد طرق أخرى منها اختيار أكثر من نقطة تزاوج ، ومنها ما هو معقد . ويوجد تزاوج مخصص ويعني ذلك أن طريقته صنعت لمشكلة محددة وهذا النوع يطور أداء خوارزمية الجينات ، وبالطبع كل هذه الخيارات تعتمد على نوع المشكلة.
*** معايير التوقف Stopping Criteriaأو شروط التوقف Stopping conditions وهي كالتالي:
الأجيال Generations: تتوقف الخوارزمية عندما تصل للعدد المشروط من الأجيال. مثال: عندما تريد أن تستمر الخوارزمية بالبحث عن حل في 50 جيل، فإنها بعد أن تكرر النقاط أعلاه خمسين مرة ستتوقف وتعطيك الحل.
الحدود الزمنية Time limit: تتوقف الخوارزمية عندما ينتهي الوقت بالثواني الذي تحدده.
حدود الكفاءة Fitness limit: تتوقف الخوارزمية عندما تصبح كفاءة الكروموسوم في المجموعة الحيوية الحالية أقل من أو تساوي حدودو الكفاءة .
مهلة الأجيال Stall generations: تتوقف الخوارزمية عندما لا يحدث تطور لدالة الهدف لسلسلة من الأجيال المتتابعة طولها يساوي المهلة المحددة، مثال: عندما تحدد أن مهلة الأجيال 5 ، فإنه اذا مرت خمسة أجيال متتابعة دالة الهدف لم تتغير تتوقف الخوارزمية.
مهلة الوقت Stall time limit: تتوقف الخوارزمية عندما لا يحدث تطور في دالة الهدف خلال مدة زمنية محددة بمهلة الوقت وتحسب بالثواني، مثال: عندما تحدد مهلة الوقت ب 60 ثانية، فإنه اذا مرت 60 ثانية ودالة الهدف للكروموسومات لم تتغير تتوقف الخوارزمية.
تطبيق الخوارزمية
سوف نطبق الخوارزمية بشكل مبسط على مشكلة تسمى الثمان ملكات 8-queens :
شكل4 :مشكلة الثمان ملكات
في لعبة الشطرنج تستطيع الملكة التحرك عمودياً وأفقياً وقطرياً.
لوح الشطرنج مكون من ثمان أعمدة وثمان صفوف.
في مشكلة الثمان ملكات القياسية 8*8 المطلوب هو وضع ثمان ملكات على لوح الشطرنج بحيث لا تهاجم أي من الملكات الأخرى ، بمعنى أن لا تكون أي ملكة في نفس العمود أو الصف أو القطر الذي تكون فيه ملكة أخرى.
سوف نطبق الخوارزمية الآن على هذه المشكلة. ولكن يجب أولا أن نحدد بعض الأمور وهي:
أولاً: الكروموسوم: يجب أن نختار طريقة لتمثيل الكروموسوم، وهي أهم خطوة والتي تبنى عليها بقية الخطوات ، لذلك يجب أن نحرص على أن يكون التمثيل بسيط وسهل التعامل معه. يمكن أن نختار تمثيل الكروموسوم على شكل جدول 8*8 كل ملكة لها عمود وفي العمود نحدد مكانها ! ولكن عندما نتذكر تعقيد الخوارزمية ، يبدو هذا التمثيل مزعجاً وكبيرا جدا وفيه مساحات غير مستخدمة ، والمساحة أمر مهم عند العمل على الحاسوب ويؤثر في سرعة انجاز المهمات، لذلك دعونا نبحث عن طريقة أخرى. سوف نمثل الكرموسوم بثمان خانات فقط، كل خانة تمثل ملكة، والرقم داخل الخانة يمثل موقع الملكة في العمود المقابل لها، كما في الشكل 5.
شكل5 : تمثيل الكروموسوم في مشكلة الثمان ملكات
ثانياً: دالة الكفاءة: سنعبر عن كفاءة الكروموسوم بعدد الملكات اللاتي لا يهاجمن بعضهن، الحد الأدنى يساوي صفر ويعني أن كل الملكات يهاجمن بعضهن، والحد الأعلى يساوي 28 بمعنى أن جميع الملكات لا يهاجمن بعضهن (كل ملكة من الثمان لا تهاجم السبع البقية = 56، وحتى لا نحسب كل ملكة مرتين فإننا نقسم على 2 ، 8 * 7 / 2 = 28 )
ثالثاً: التزاوج: هناك طرق كثيرة لاختيار الكروموسومات لمزاوجتها، و سوف نستعمل طريقة التنقية culling، وهي أن كل كروموسوم له نسبة كفاءة تحت عتبة معينة يستثنى. بناء على هذه الطريقة سنختار العتبة 20 لذلك سنستثني كل كروموسوم دالته تحت هذه الرقم.
رابعاً: التحوير : وهو أن نحور بعض الجينات في أي موضع في الكروموسوم بتغيير الرقم إلى رقم آخر بين 1 – 8. وسوف نحور كل جين له احتمال أقل من 0,1 .
خامساً: معيار التوقف: سيكون معيار التوقف هو الوصول إلى 5 أجيال ثم يعطينا النتيجة .
والآن سنبدأ بالتطبيق بطريقة بسيطة جداً:
1. البداية: سوف نكون مجموعة حيوية من 4 كروموسومات انظر الشكل6 (أ).
2.ابدأ العمل من هنا:
a.نحسب الكفاءة لكل كروموسوم، وذلك بِعَدّ الملكات اللاتي لا يهاجمن بعضهن. ثم نستخرج نسبة كل كروموسوم بالنسبة لبقية الكروموسومات وذلك بقسمة دالة الكروموسوم على مجموع دوال الكروموسومات. بالنسبة للكروموسوم الأول ذو الكفاءة 24 (24 زوج من الملكات لا يهاجمن بعضهن) ، تحسب له النسبة هكذا : 24 / (24 + 23 +20 + 11 ) = 31%. وكذلك بالنسبة لبقية الكروموسومات: الثاني = 23 / ((24 + 23 +20 + 11 ) = 29%. الثالث = 20 / ((24 + 23 +20 + 11 ) = 26%. الرابع = 11 / ((24 + 23 +20 + 11 ) = 14% ، شاهد الشكل 6(ب).
b.ننشىء مجموعة حيوية جديدة ونملأها كالتالي:
i.الاختيار: بما أن العتبة هي20، إذن سنختار الكروموسوم الأول والثاني والثالث فقط.انظر الشكل6 (جـ).
ii.التزاوج: حسب ترتيب النسبة سنزاوج الكروموسومات ، الكروموسوم الأول مع الثاني لأنهم الأعلى درجة ، ثم الثاني مع الثالث. شاهد الشكل6 (د) ونلاحظ هنا أنه يمكن لكروموسوم أن يدخل في عملية التزاوج أكثر من مرة. سوف ينتج لنا كروموسومان جديدان، وبملاحظة هذان الكروموسومان يمكن أن نلاحظ أن التزاوج يؤدي إلى تنوع المجموعة الحيوية بمعنى أن التزاوج يأخذ خطوات كبيرة في مجال البحث وسوف تتقلص هذه الخطوات عندما نصل لاحقا إلى كروموسومات متشابهه، لماذا؟
iii.التحوير: كل مكان في الكروموسوم من الممكن تحويره عشوائياً باحتمال مستقل صغير. سوف نستخدم طريقة غاوسGaussian بحيث نعطي كل جين في الكروموسوم رقم عشوائي من 0 إلى 1 ، اذا كان الرقم أقل من احتمالية التحوير (التي حددناها في الأعلى بـ 0,1) سوف نغير هذا الرقم إلى رقم آخر عشوائي بين 1 و8، كما نشاهد في الشكل6 (هـ).
iv.القبول: نقبل الكروموسوم الناتج ونضعه في المجموعة الحيوية الجديدة.
شكل6 : تطبيق الخوارزمية (أ) المجموعة الحيوية الجديدة ، ترتب حسب دالة الكفاءة في (ب) ثم يتم الاختيار (جـ) بناء على دالة الكفاءة، وتتم مزاوجة الكروموسومات حسب الترتيب (د) وثم يطبق التحوير (هـ)
c.استبدال المجموعات: سوف نستبدل المجموعة الأولى بالمجموعة الجديدة.
d.اختبر شرط التوقف: عدد الأجيال حتى الآن جيل واحد فقط إذن نكمل ، وهكذا يتم تطبيق الخطوات السابقة مرة أخرى حتى يتحقق شرط التوقف وهو الوصول إلى 5 أجيال ، ثم يصبح الكروموسوم صاحب أعلى دالة كفاءة هو الحل. يظهر هنا أنه من الممكن أن تكون النتيجة غير مرضية ويكون الكروموسوم الناتج لا يحل المشكلة وذلك لأن عدد الكروموسومات في المجموعة الحيوية قليل ولأن شرط التوقف – 5 أجيال - لم يسمح للخوارزمية أن تتعمق في البحث حتى تحصل على أفضل نتيجة .
برمجة الخوارزمية
يوجد الكثير من الأشخاص في الانترنت الذين قاموا ببرمجة هذه الخوارزمية ولكن الذي شاهدته حتى الآن برامج مخصصة لمشكلة معينة، ولكن يوجد في ماتلاب MATLAB دالة تقوم بتطبيق هذه الخوارزمية بسهولة وهي دالة ga ، بينما يلزمك معرفة بعض الأمور حتى تستطيع استخدامها .
المصدر : بحث/ هند الروقي.