اختيار عجلة الروليت في الخوارزمية الوراثية. يحتاج السكان إلى فرزهم أولا؟

Question

في خوارزمية وراثية، عند اختيار أعضاء Crossover باستخدام طريقة اختيار عجلة الروليت، يحتاج السكان أولا إلى أن يتم فرزهم حسب رتبة اللياقة البدنية؟

يبدو أن الاحتمالات:

1. فرز السكان أولا عن طريق تصاعدي اللياقة البدنية
2. فرز السكان عن طريق تنازلي اللياقة
3. لا فرز السكان والسماح للكرة الروليت حيث قد.

أفكر في أن الفرز في كلتا الحالتين قد لا يكون له أي تأثير - هبوط حصاة عشوائيا على عجلة تحتوي على شرائح مختلفة الحجم (حسب اللياقة) سيكون لها نفس فرصة النتيجة ما إذا كانت الشرائح الأكبر مجمعة معا أم لا. لكنني لست مقتنعا بنسبة 100٪.

ما رأيك؟

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

Answer 1

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

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

Answer 2

حتى لو قمت بتطبيق النخبالية، فلا حاجة لفرز السكان.

العثور على أفضل الأفراد N يتطلب فقط تكرار واحد من خلال السكان.

Answer 3

لا تحتاج إلى فرز السكان إذا كنت تستخدم مثل هذا الاختيار.

وأنت أيضا صحيحة حول التعقيد، والفرز هو N * Log (N)، مما يجعل الخوارزمية الوراثية أبطأ بشكل كبير (ولكن لا يزال، لا يزال التعقيد متعدد الحدود، وهي ميزة حاسمة لخوارزميات وراثية).

إليكم كيف سأفعل ذلك (واحصل على نقاط إضافية في المدرسة لهذا):

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

2. قياس عدد التكرارات وسرعة الخوارزمية / كل تكرار

3. هل الفرز الخاص بك في خطاف. قياس. الآن دع الخطاف فارغ وقياس وهلم جرا.

سوف تحصل على بعض البيانات الجميلة والتحقق تجريبيا ما يخبرك بحسابك.