خوارزمية بايثون الوراثية لإيجاد إكسترا العالمية

خلفية

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



ولذا قررت كتابة حزمتي الصغيرة في Python مع تصور للخوارزمية ، حيث سيكون من المناسب تكوين هذه الخوارزمية والبحث عن التفاصيل الدقيقة للنموذج المحدد.

في هذه المقالة القصيرة ، أود أن أشارك العملية والملاحظات والنتائج.

مبدأ الخوارزمية

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

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

يحمل الفرد الأحادي الصبغية في كل من معلوماته الجينية حول إحداثيات x أو y المقابلة. يتم تحديد السكان من قبل العديد من الأفراد ، ولكن يتم تقسيم السكان إلى 4 أفراد. هذا الحل ، بالطبع ، يرجع إلى محاولة لتجنب التقارب إلى المستوى المحلي الأمثل ، لأن المهمة هي إيجاد أقصى عالمي. مثل هذا التقسيم ، كما أظهرت الممارسة ، لا يسمح في كثير من الحالات بنمط جيني واحد للسيطرة على جميع السكان ، ولكنه ، على العكس من ذلك ، يعطي ديناميات "تطور" أكبر. يتم تطبيق الخوارزمية التالية لكل جزء من السكان:

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

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

الاختبارات والملاحظات الأولية

لذا ، نختبر هذه الخوارزمية على مثالين بسيطين:

الاختبار 1

$$

$$f(x, y) = sin(x) + cos(y)$$

اختبار 2

$$

$$\frac{4 \sqrt{x} - 5y }{ 3x ^ 2 + 2 y ^ 2 - 2 x + 1}$$

بعد اختبار ودراسة تشغيل الخوارزمية بطريقة النظرة والنثر العشوائي ، تم الكشف عن العديد من أنماط الفرضيات:

• يتناسب خطأ الخوارزمية بشكل مباشر مع عدد الأفراد ، ولكن في المتوسط ​​يتم احتساب الخطأ في المئات ، على الرغم من أنه مع معلمات غير ناجحة يمكن أن يصل الخطأ إلى أعشار

• $$

  $$[-1, 1)$$
  - . , , , ( )
• 5-15 , «»

• $$

  $$[-1, 1)*[-1, 1)$$
  
  وقد تكون هناك حالات عندما يغطي هذا المربع الحد الأقصى المحلي ، والذي لا يناسبنا

ضع في اعتبارك سطحًا به العديد من الأشكال القصوى للنموذج:

$$

$$g(x, y) = \sum\limits_{i=1}^nf_n(h, x_0, y_0), f(h, x_0, y_0) = h*exp(-(x - x_0)^2 - (y - y_0)^2)$$

سيكون أقصى دالة g في نقاط

$$

$$(x_0, y_0)$$

.

اختبار 3

$$

$$g(x, y) = f_1(2, 0, 0) + f_2(5, 3, 3)$$

$$

$$g(x, y) = 2exp(-x^2 - y^2) + 5exp(-(x - 3)^2 - (y - 3)^2)$$

يؤكد هذا المثال ويوضح جميع الملاحظات المذكورة أعلاه.

ترقية الخوارزميات الجينية

لذا ، في الوقت الحالي ، تتكون وظيفة الطفرة بشكل بدائي للغاية: فهي تضيف قيمًا عشوائية من نصف الفاصل الزمني

$$

$$[-1, 1)$$

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

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

اختبار 1

$$

$$f(x, y) = sinx$$

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

ولكن ماذا عن مشكلة التطرف المحلي؟ تأمل في مثال مألوف.

اختبار 2

$$

$$g(x, y) = f_1(2, 0, 0) + f_2(5, 3, 3)$$

$$

$$g(x, y) = 2exp(-x^2 - y^2) + 5exp(-(x - 3)^2 - (y - 3)^2)$$

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

ملخص

لقد لخصت النتيجة:

• تسمح لك مجموعة المعلمات الصحيحة بالعثور بدقة على الحد الأقصى العالمي لدالة متغيرين
• تقسيم السكان في كثير من الحالات يتجنب التقارب إلى المستوى المحلي الأمثل
• يسمح إدخال قوة الطفرة أيضًا للمرء بتجنب التقارب إلى المستوى المحلي الأمثل وفي بعض الأحيان يزيد من دقة النتيجة
• ,
• ,

...

• , . , , aka
• , ,
• ()