الخوارزميات الوراثية

Question

أحاول تنفيذ خوارزمية وراثية ستحسب الحد الأدنى من RASTRIGIN FUNCTON وأنا أواجه بعض المشكلات.
أحتاج إلى تمثيل الكروموسوم كسلسلة ثنائية ، حيث تأخذ وظيفة Rastrigin قائمة بالأرقام كمعلمة ، كيف يمكن فك تشفير الكروموسوم إلى قائمة بالأرقام؟
كما يريد Rastrigin أن تكون العناصر الموجودة في القائمة -5.12 <= x (i) <= 5.12 ماذا يحدث إذا قمت بإنشاء الكروموسوم ، فلن ينتج عن رقم في هذا الفاصل؟

Answer 1

أنت تتطلع إلى تنفيذ خوارزمية وراثية. يجب أن يكون تنفيذك بحيث يعمل مع أي مشكلة تقليل (أو تعظيم) عام ، وليس فقط rastrigin وظيفة. قد تقرر تنفيذ GA مشفرة ثنائية أو GA مشفرة حقيقية. كلاهما له استخداماته الخاصة والتطبيقات المتخصصة. لكن بالنسبة لك ، أود أن أقترح تنفيذ GA مشفرة حقيقية. وفقًا لسؤالك فيما يتعلق بما يجب القيام به ، إذا كانت القيم المتغيرة التي تم إنشاؤها خارج [-5.12: 5.12] ، فإن GA مشفرة حقيقية و GA الثنائية سوف تتعامل معها بشكل مختلف.

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

pyevolve هي مكتبة Python للخوارزميات الجينية والبرمجة الوراثية.

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

Answer 2

لماذا تحتاج إلى تمثيل الكروموسوم كسلسلة ثنائية؟ يمكنك كتابة الخوارزميات التطورية التي تستخدم أنواعًا أخرى. يمكنك استخدام قائمة الأرقام.

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

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

Answer 3

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

استخدام أرقام النقاط العائمة من شأنها أن تتيح لك الاقتراب أكثر من ذلك بكثير ، على سبيل المثال 1E-10 ، أثناء استخدام أرقام 64 بت النموذجية. علاوة على ذلك ، تستخدم الخوارزمية التطورية الحديثة المخطط التكيفي لضبط خطوة الطفرة أثناء التحسين. هذه الآلية تسمح بزيادة سرعة التقارب ، مقارنة بخطوة طفرة ثابتة. الخروج من هذا لمعرفة ما يحققه الأمثل التطوري النموذجي على وظيفة Rastrigin: http://coco.gforge.inria.fr/doku.php؟id=bbob-2010

Answer 4

أفترض أنك برمجة في C. integers (int للغة C) يمكن تعبئتها كمجموعة من 4 بايت/char (32 بت). لذلك إذا كانت صفيفك

char* chrom_as_bytes=(...)

يمكنك الحصول على القيمة i-th عن طريق الإلقاء على int*

int ith=3;
value=((int*)chrom_as_bytes)[ith];

إذا لم تكن القيمة في النطاق -5.12

انظر أيضا المقالة في ويكيبيديا.

Answer 5

إذا كنت مهتمًا ، فقد قمت بتنفيذ باستخدام Pyevolve:http://pyevolve.sourceforge.net/examples.html#example-7-the-rastringin-functionآسف على الخطأ المطبعي في الاسم.