تكرارات متعددة من اختيار البطولة في الخوارزمية الوراثية

Question

يا شباب، أنا مرتبك بعض الشيء حول كيفية عمل تكرارات متعددة من اختيار البطولة.

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

ومع ذلك، لست متأكدا مما يحدث بعد ذلك.

هل نبدأ فقط في التزاش عشوائيا تلك الموجودة في بركة التزاوج؟ ثم أعد تشغيل عملية الاختيار عن طريق اختيار أزواج عشوائية من الجيل الجديد؟

شكرا.

Answer 1

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

Answer 2

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

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

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

ولكن ليكون أكثر كفاءة، وإذا كنت تعرف كيفية دمج الأفراد حتى ينتجوا حلا أفضل (وهذا قد يكون صعبا للغاية)، يمكنك استخدام وظيفة تقارب، والتي تأخذ 2 أفراد وإرجاع تقارب بينهما. الجزء الصعب هو تحديد التقارب. اعتمادا على المشكلة، قد يكون مختلفا تماما. على سبيل المثال، إذا أخذت مشكلة مبيعات السفر، فقد حصلت على أفضل الحلول عند التزاوج الفرد مع التشابه الأقل. لذلك عادت وظيفة التقارب الخاصة بي 1 - التشابه.

بهذه الطريقة، يمكنني تقليل عدد التكرارات بنسبة 80٪ واحصل على حلول جيدة للغاية.

لكن ضع في اعتبارك أن الأكبر هو حمام السباحة الخاص بك، وسوف تأخذ وظيفة التقارب لتنفيذ - وظائف التقارب يمكن أن تكون O (N²)، أو حتى O (N³)، في أي حالات يمكن أن تكون عنق الزجاجة من خوارزميةك. في هذه الحالة، قد يكون من الأفضل استخدام التزاوج العشوائي.

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

Answer 3

هذه ليست نصيحة جيدة ولكن ...

ومع ذلك، لست متأكدا مما يحدث بعد ذلك.

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

كما أشار شخص آخر في هذا المنتدى: السر الصغير القذر حول الغاز هو أنه فني أكثر من العلم.

أيضا، للحصول على نصيحة جيدة حقا، ستحتاج إلى وصف أفضل للمشكلة التي تريد حلها.