الخوارزميات التطورية:توزيعات إعادة السكان الأمثل

Question

كل هذا موجود بالفعل في العنوان، ولكن إليك تفصيلًا لأي شخص مهتم بالخوارزميات التطورية:

في EA، الفرضية الأساسية هي أنك تقوم بشكل عشوائي بإنشاء عدد معين من الكائنات الحية (والتي هي في الواقع مجرد مجموعات من المعلمات)، وتشغيلها ضد مشكلة ما، ثم السماح لأصحاب الأداء الأفضل بالبقاء على قيد الحياة.

ثم يتم إعادة إسكانك بمزيج من تهجين الناجين، وطفرات الناجين، وكذلك عدد معين من الكائنات العشوائية الجديدة.

افعل ذلك عدة آلاف من المرات، وستظهر كائنات فعالة.

يقوم بعض الأشخاص أيضًا بأشياء مثل إدخال "جزر" متعددة من الكائنات الحية، وهي مجموعات منفصلة يُسمح لها بالتهجين من حين لآخر.

إذن سؤالي هو:ما هي النسب المئوية المثلى لإعادة السكان؟

لقد كنت أحتفظ بأفضل 10% من أصحاب الأداء، وأعيد توطينهم بنسبة 30% من التهجين و30% من الطفرات.أما الـ 30% المتبقية فهي للكائنات الحية الجديدة.

لقد قمت أيضًا بتجربة نظرية الجزر المتعددة، وأنا مهتم بنتائجك في هذا الشأن أيضًا.

لا يغيب عن بالي أن هذا هو بالضبط نوع المشكلة التي يمكن أن يحلها EA.هل أنت على علم بأي شخص يحاول ذلك؟

شكرا لك مقدما!

Answer 1

حاولت في البداية أن أضع نموذجًا لما اعتقدت أن الأنظمة العضوية ستكون عليه.قررت في النهاية أن ذلك ليس جيدًا، وأصبحت أكثر عدوانية، حيث تم الاحتفاظ بـ 10%، و20% متحورة، و60% هجينة، و10% عشوائية.

ثم لاحظت أن أفضل 10% من نتائجي كانت جميعها متطابقة تقريبًا.لذلك قمت بزيادة العشوائية إلى 30٪.وقد ساعد ذلك البعض، ولكن ليس كثيرًا.

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

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

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

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

Answer 2

أفضل الموارد التي وجدتها لـ GA وEA كانت كتب John Koza البرمجة الجينية.وهو يغطي الموضوع بعمق - تقنيات تشفير الجينوم، والطفرة العشوائية، والتربية، وضبط وظيفة اللياقة البدنية.

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

لا شيء من هذا يعطيك إجابات محددة، ولكن لا أعتقد أن هناك إجابات محددة، GA لا يمكن التنبؤ به بطبيعته وضبط هذه الأنواع من المعلمات قد لا يزال يمثل نوعًا من الفن.بالطبع يمكنك دائمًا تجربة Meta-GA، باستخدام تلك المعلمات ككروموسوم، والبحث عن الإعدادات التي تنتج لياقة أكثر سرعة في GA الأساسي الذي تقوم بتشغيله.

يعتمد على كيفية "التعريف" الذي تريد الحصول عليه.

Answer 3

هذا محل نقاش ساخن (في الأدب و كتب ميلاني وآخرون) موضوع يبدو أنه خاص جدًا بالمجال.ما يصلح لمشكلة واحدة من نوع واحد مع معلمات n لن ينجح أبدًا مع مشكلة أخرى، أو مجال آخر، أو مجموعة معلمات أخرى.

لذا، كما اقترحت TraumaPony، قم بتعديلها بنفسك لكل مشكلة تقوم بحلها أو اكتب شيئًا لتحسينها لك.أفضل شيء يمكنك القيام به هو متابعة جميع تجارب "تدوير المقابض" والضبط الدقيق حتى تتمكن من رسم خريطة للحل والتعرف على كيفية التحسين داخل تلك المساحة بسرعة.جرب أيضًا تقنيات بديلة مثل تسلق التلال حتى يكون لديك خط أساسي للتغلب عليه.

@ كايل بيرتون:كروس مقابل.معدلات الطفرة هي أيضا تتم مناقشتها باستمرار في كل فئة من المشاكل التي تم تسليمها إلى GAs وGPs.

Answer 4

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

Answer 5

لقد حققت بعض النجاح في زيادة تنوع السكان عن طريق تحديد الطفرة والتقاطع من اثنين من الجينات من الكروموسومات الأم.

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

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

لقد وجدت أن هذا من شأنه أن يوقف الهضبة الكلاسيكية والتقارب السكاني.

جانبًا، أميل إلى إجراء عمليات التقاطع والطفرة لكل طفل.

بالنسبة إلى أجيال الـ GA، أحاول تجنب النخبوية تمامًا، ولكن عندما أسكن من جزر متعددة، أحتفظ بالنخبة العليا من كل جزيرة.عندما تجتمع الجزر معًا، يمكن للنخب جميعًا أن تتكاثر معًا.

Answer 6

يبدو أن هناك بعض الإجابات التي تقترح استخدام GA الثاني لتحديد المعلمات المثلى لـ GA الأول، دون ذكر كيفية تحديد المعلمات المثلى للثاني.ولا يسعني إلا أن أتساءل عن المعتقدات الدينية لأولئك الذين يقترحون هذا النهج ...

Answer 7

كما ذكر آخرون، يعتمد المزيج الأمثل على مشكلتك المحددة والعوامل الأخرى الخاصة بالمشكلة مثل حجم مساحة الحل.

قبل أن نناقش انهيار التطور من جيل إلى جيل، من المهم أن نأخذ في الاعتبار حجم كل جيل.بشكل عام، نهجي هو البدء بعدد كبير إلى حد ما (حوالي 100 ألف إلى 500 ألف فرد) من الأفراد المتنوعين إلى حد ما، وهو أمر يقترحه كوزا في بعض أعماله.للحصول على هذا التنوع منذ البداية، يمكنك تقسيم مساحة الحل إلى مجموعات، ثم التأكد من وجود عدد معين من الأفراد على الأقل في كل مجموعة.(على سبيل المثال.إذا كان لديك تمثيل شجرة لكل فرد، فتأكد من إنشاء كميات متساوية من العمق 2، 3، ...، max_عمق)

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

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

ومع ذلك، فإن نهجي الحالي هو الحفاظ على أعلى 1%، وتهجين أعلى 20% إلى 20% جديدة، وتهجين أعلى 40% في الـ 20% التالية، وتهجين أعلى 90% لتوليد الـ 20% التالية، وبشكل عشوائي توليد الباقي (39٪).إذا كانت هناك نسخ مكررة، أقوم بإزالتها واستبدالها بأفراد عشوائيين جدد.

لا أستخدم الطفرات لأن العدد الكبير من الأفراد العشوائيين يجب أن يهتموا بإضافة "الطفرات" أثناء التهجين التالي.

Answer 8

أنت تعرف ماذا يمكنك أن تفعل ...يمكنك كتابة خوارزمية جينية لتحديد التوزيع الأمثل.

لكن، عادةً ما أحتفظ بأعلى 12% و28% من السلالات المهجنة؛مع 30% لكل منهما للآخرين.