الخوارزميات الجينية (GA) تعتمد على نهج تطوري في الذكاء الاصطناعي، حيث يتم استخدام طرق تطور السكان للحصول على الحل الأمثل لمشكلة معينة. تم اقتراحها لأول مرة في عام 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 ملكات
تُستخدم الخوارزميات الجينية لحل العديد من المشكلات، بما في ذلك مشاكل اللوجستيات والبحث. هذا المجال مستوحى من أبحاث دمجت بين علم النفس وعلوم الحاسوب.
"الخوارزميات الجينية سهلة التنفيذ، لكن سلوكها يصعب فهمه." المصدر قم ببعض البحث للعثور على تنفيذ لخوارزمية جينية مثل حل لغز سودوكو، واشرح كيف تعمل باستخدام رسم تخطيطي أو مخطط تدفق.
شاهد هذا الفيديو الرائع الذي يتحدث عن كيفية تعلم الكمبيوتر لعب سوبر ماريو باستخدام الشبكات العصبية المدربة بواسطة الخوارزميات الجينية. سنتعلم المزيد عن تعلم الكمبيوتر لعب الألعاب مثل هذه في القسم التالي.
هدفك هو حل ما يسمى بـ معادلة ديوفانتين - وهي معادلة ذات جذور صحيحة. على سبيل المثال، ضع في اعتبارك المعادلة a+2b+3c+4d=30. تحتاج إلى العثور على الجذور الصحيحة التي تحقق هذه المعادلة.
هذا الواجب مستوحى من هذا المنشور.
تلميحات:
- يمكنك اعتبار الجذور في النطاق [0;30]
- كجين، يمكنك استخدام قائمة قيم الجذور
استخدم Diophantine.ipynb كنقطة انطلاق.