الخوارزميات الجينية
تعتمد الخوارزميات الجينية (Genetic Algorithms, GA) على نهج تطوري في الذكاء الاصطناعي. يعني نستخدم فكرة تطوّر مجموعة من الحلول عشان نوصل للحل الأمثل لمشكلة معيّنة. اقترحها John Henry Holland سنة 1975.
تقوم الخوارزميات الجينية على هالأفكار:
- نقدر نمثّل الحلول الصالحة للمشكلة على شكل جينات.
- التهجين يخلينا ندمج حلّين ونطلع منهم بحل جديد صالح.
- نستخدم الاختيار عشان ننتقي الحلول الأفضل بحسب دالة الملاءمة.
- ندخل الطفرات عشان نغيّر مسار التحسين ونطلعه من الحد الأدنى المحلي.
إذا بغينا نطبّق خوارزمية جينية، نحتاج نسوي الآتي:
- نلقى طريقة نرمّز فيها حلول المشكلة باستخدام جينات g∈Γ.
- نعرّف على مجموعة الجينات Γ دالة ملاءمة fit: Γ→R، بحيث تدل القيم الأصغر على حلول أفضل.
- نعرّف آلية تهجين تدمج جينين وتنتج جينًا جديدًا صالحًا crossover: Γ2→Γ.
- نعرّف آلية طفرة mutate: Γ→Γ.
في حالات كثيرة، يكون التهجين والطفرة خوارزميات بسيطة تتعامل مع الجينات كسلاسل رقمية أو متجهات بتّية.
التطبيق التفصيلي للخوارزمية الجينية يختلف من حالة للثانية، لكن بنيتها العامة تمشي كذا:
- نختار مجموعة حلول أولية G⊂Γ.
- نختار عشوائيًا العملية اللي بننفّذها في هالخطوة: تهجين أو طفرة.
- التهجين:
- نختار عشوائيًا جينين g1, g2 ∈ G.
- نحسب ناتج التهجين g=crossover(g1,g2).
- إذا كان fit(g)<fit(g1) أو fit(g)<fit(g2)، نستبدل الجين المقابل في المجموعة بـ g.
- الطفرة: نختار جينًا عشوائيًا g∈G ونستبدله بـ mutate(g).
- نكرر من الخطوة 2 لين تصير قيمة fit صغيرة بما يكفي، أو نوصل للحد الأعلى من عدد الخطوات.
مهام شائعة
عادةً نستخدم الخوارزميات الجينية في مهام مثل:
- تحسين الجداول الزمنية.
- الوصول لأفضل طريقة للتعبئة.
- الوصول لأفضل طريقة للقص.
- تسريع البحث الشامل.
✍️ تمارين: الخوارزميات الجينية
كمّلوا تعلّمكم في الدفاتر التالية:
روحوا إلى هالدفتر عشان تشوفون مثالين على استخدام الخوارزميات الجينية:
- تقسيم الكنز بإنصاف.
- مسألة 8 ملكات.
الخلاصة
نستخدم الخوارزميات الجينية لحل مشاكل كثيرة، ومنها مسائل اللوجستيات والبحث. واستُلهم هالمجال من أبحاث جمعت بين علم النفس وعلوم الحاسب.
🚀 التحدي
«الخوارزميات الجينية سهلة التطبيق، لكن فهم سلوكها صعب.» المصدر ابحثوا عن تطبيق لخوارزمية جينية، مثل حل أحجية Sudoku، واشرحوا طريقة عمله برسم توضيحي أو مخطط انسيابي.
المراجعة والتعلّم الذاتي
شوفوا هالفيديو الممتاز اللي يشرح كيف يتعلم الحاسب يلعب Super Mario باستخدام شبكات عصبية تدربت بخوارزميات جينية. بنتعلم أكثر عن تعلّم الحاسب للألعاب بهالطريقة في القسم الجاي.
هدفكم تحلّون ما يُسمّى معادلة ديوفانتية، وهي معادلة جذورها أعداد صحيحة. خذوا مثلًا المعادلة a+2b+3c+4d=30. المطلوب تلقون الجذور الصحيحة اللي تحققها.
هالواجب مستوحى من هالمنشور.
تلميحات:
- تقدرون تفترضون إن الجذور تقع في النطاق [0;30].
- استخدموا قائمة قيم الجذور بوصفها جينًا.
ابدؤوا من Diophantine.ipynb.
