در طراحي و اجراي الگوريتم هاي تكاملي، جنبه هاي زير بايد مورد توجه قرار گيرند. اين ملاحظات كه كليه گويشها را دربرمي گيرد، به طور كلي و بدون توجه به الگوريتم خاص توضيح داده مي شوند.

يك جنبه آن است كه در زمان اجراي EA، تا حد ممكن برای حفظ تنوع ژنتيكي جمعيت تلاش كنيم. برخلاف ساير روشهاي بهينه سازي، EA ها كل جمعيت افراد را به كار مي برند (كه يكي از دلايل قدرت آنهاست) ولي اگر اين جمعيت شروع برای تمركز بر روي منطقه كوچكي از فضاي جستجو كند، همه مزاياي به كارگيري تعداد زيادي از افراد متفاوت، ناپديد مي گردند. در حاليكه حجم محاسباتي شايستگي آنها باقي مي ماند. اين فرضيه، همگرايي زودهنگام[1] (پيش از موعد) ناميده مي شود. دو راهكار برای ممانعت از اين اتفاق وجود دارد: اطمينان از توليد افراد جديد مثلا با استفاده از جهش سطح بالا و يا تغيير شايستگي افراد برای مقابله با تمايل يافتن اين مقادير به شايستگي هاي افراد موجود. يك تكنيك معروف در اين زمينه، مكانيزم niching است.

كاوش و استخراج لغاتي هستند كه اغلب در EC به كار مي روند. يكي از معضلات بهينه سازي اين است كه آيا جستجو بايد در اطراف بهترين راه حلي كه تا به حال يافته شده صورت گيرد (كه اميدواريم همسايه هاي آن شامل نقاط بهتري باشند) يا نواحي كاملا متفاوتي از فضاي جستجو را كاوش كنيم (زيرا ممكن است بهترين راه حل فعلي، يك بهينه محلي باشد). EA بايد بدون داشتن اطلاعات قبلي از چشم انداز فضاي جستجو ، اين معضل را رفع كند. فاز استخراج معمولا مي تواند به چند رويه بهينه سازي محلي محول شود كه يا عملگر جهش خوانده مي شود و يا به طور سيستمي به كليه افراد تازه متولد شده اعمال مي شود و آنها را به نزديك ترين بهينه محلي جابه جا مي كند. در حالت دوم الگوريتم تلفيقي حاصل، الگوريتم memetic ناميده مي شود.

به طور كلي دو نيروي پيش برنده در هر EA وجود دارد: انتخاب و تغيير. اولي نمايشگر حركت به سوي كيفيت است و تنوع ژنتيكي جمعيت را كاهش مي دهد. دومي، توسط عملگرهاي تركيب مجدد و جهش پياده سازي مي شود و تنوع ژنتيكي را افزايش مي دهد. برای اينكه EA به درستي كار كند، اين دو نيرو بايد داراي تعادل (توازن) باشند.

مولفه هاي الگوريتم هاي تكاملي

حل يك مساله توسط EA، با تخصيص نمايش به راه حلهاي داوطلب آغاز مي شود. اين راه حلها به عنوان فنوتيپ هايي درنظرگرفته مي شوند كه مي توانند ساختارهاي بسيار پيچيده داشته باشند. اعمال مستقيم عملگرهاي تغييردهنده بر اين ساختارها ممكن است ساده و يا عملي نباشد. بنابراين اين فنوتيپها با فنوتيپهاي متناظر نمايش داده مي شوند. ماشين EC استاندارد شامل عملگرهاي تبديل آمادهء زيادي است كه روي فضاي ژنوتيپ خاصي عمل مي كنند مانند رشته بيتي، بردارهاي حقيقي، جايگشتهاي اعداد صحيح يا درختها. طراحي يك ***************

 

  1. 3. 3. جهش

عملگرهای جهش، تبدیلات احتمالی افراد هستند. سازش معمول بین کاوش و استخراج باید حفظ گردد. جهش های بزرگ به دلایل تئوری لازمند، البته جهش های خیلی بزرگ، الگوریتم را به گام برداری تصادفی تبدیل می کنند. پس بیشتر جهشها ممکن اس فرزند نزدیک به دالدین ایجاد کنند. به طور کلی جهش کلی استانداردی وجود ندارد ولی برای اصلاح مقدار یک مولفه از ژنوتیپ با احتمالی کوچک تلاش می شود.

مناظره تاریخی

مدتهای طولانی در مورد میزان مفیدبودن عملگر ادغام مناظره وجود داشته است. که آیا این عملگر یک تبدی اساسی است و یا می تواند مضر باشد. توافق کلی که امروزه حاصل شده این است که جواب بستگی به مساله دارد. اگر ادغام از نظر مفهومی برای مساله خاص بامعنی است، احتمالا استفاده از آن ایده خوبی است. در غیر این صورت جهش به تنهایی برای یافتن راه حلهای خوب کافی است.

 

 

واضح است كه هر يك از روشهاي EC داراي تنوعهاي زيادي است . در اينجا به توضيح مختصر هر روش مي پردازيم:

  1. 1. GA : GA استاندارد به صورت تركيبي از نمايش رشته بيتي، ادغام تبادل بيت[2] ( با احتمال pc)، جهش چرخش بيتي[3] ( كه با احتمال pm به هر بيت اعمال مي شود)، انتخاب roulette-wheel به اضافه جايگزيني نسلي ( گرچه جانشيني حالت پايدار هم مي تواند به كار رود)، درنظر گرفته مي شود.

ساير روشهاي EC هم كه موتور تكامل يكساني را با ژنوتيپ متفاوت (و در نتيجه عملگرهاي متفاوت) به كار مي برند، اغلب GA ناميده مي شوند.

  1. 2. استراتژي هاي تكاملي: معمولا به مسايل بهينه سازي با پارامترهاي داراي مقادير حقيقي اعمال مي شوند. ES با استفاده از جهش گاوس[4] و بدون انتخاب و استراتژي هاي جايگزيني به بردارهاي حقيقي اعمال مي شود. ادغام يا با تبادل مولفه ها و يا با تركيب مجدد خطي آنها انجام مي شود. ويژگي خاص ES در خودتطبيقي انحراف استاندارد توزيع گاوس قرار دارد كه در جهش مورد استفاده قرار مي گيرد. ايده اصلي، اضافه كردن اين پارامترها به ژنوتيپها اجازه دادن به آنها برای تكامل يافتن است.
  2. 3. برنامه نويسي تكاملي: EP سنتي درباره تكامل ماشين حالت متناهي برای وظايف يادگيري ماشين بحث مي كند و نحوه نمايش و عملگرهاي خاص خودش را داراست. هر والد به وسيله جهش فقط يك فرزند توليد مي كند و استراتژي جايگزيني جمعي[5] برای حذف نصف افراد به كارمي رود. اما EP فعلي برای به كاربردن هر نمايش و موتورهاي تكامل مختلف ، تكامل پيدا كرده است و امروزه به خاطر استفاده از شكل احتمالي استراتژي جايگزيني جمعي ون عدم استفاده از ادغام، با ES تفاوت دارد.
  3. 4. GP : جوانترين زمينه در اين خانواده، ناحيه كاربردي خاصي در يادگيري ماشين و وظايف مدلسازي دارد. نمايش طبيعي آن ، درخت پارس برای عبارات منطقي صوري[6] است كه يك مدل يا رويه را توصيف مي كنند. عملگرهاي ادغام و جهش به نحوي تطبيق يافته اند كه بر روي درختهاي با اندازه متغير كار كنند. موتور تكامل، از GA به ارث برده شده است. از سوي ديگر، عبارات نحوي (مانند LISP ) مي توانند به صورت برنامه هايي ديده شوند كه GP را به صورت شاخه اي از تكامل خودكار برنامه ها در مي آورد.

 

نواحي كاربردي

اگرچه اغلب تاكيد مي شود كه الگوريتم تكاملي به بيان دقيق يك بهينه ساز نيست، مسايل بهينه سازي، ناحيه كاربردي ممهمي از الگوريتم هاي تكاملي را تشكيل مي دهند. اين كاربردها شامل بهينه سازي تركيبي، بهينه سازي پارامتري پيوسته يا بهينه سازي آميخته گسسته-پيوسته هستند.

امروزه EC به تنهايي در چارچوب بهينه سازي تركيبي، در مقايسه با اكتشافات تحقيقاتي-عملياتي سنتي، رقيب خوبي نيست. ولي تركيب EC با فرااكتشافات OR ويژه، نتايج مهمي به بار مي آورد. امروزه مسايل تركيبي، پرمزيت ترين دامنه كاربردي را برای EC تشكيل مي دهند.

در مورد بهينه سازي پارامتري پيوسته، اشتباهي كه بايد از آن اجتناب كرد، تلاش برای رقابت با روشهاي عددي با كارايي بالاست. در بيشتر موارد، (به دليل فقدان نظم و ترتيب) چنين روشهايي اعمال نمي شوند و يا (به دليل چندپيمانه اي بودن) شكست مي خورند. در اين زمينه ها، EC برای كنترل، الكترومغناطيس ، مكانيك سيالات و تحليل ساختاري با موفقيت به كار مي رود.

انعطاف پذيري EC اجازه مي دهد بتوانيم نمايشهايي را اداره كنيم كه خارج از دسترس ساير روشها هستند. مانند فضاهاي جستجوي آميخته (داراي متغيرهاي گسسته و پيوسته) و نمايشهاي با طول متغير (مانند درخت پارس در GP). اين مساله باعث بهبودهاي مهم در يادگيري ماشين (با تكامل مجموعه قوانين، قوانين اتوماتاي سلولي و …)، مدلسازي و طراحي مي گردد كه در آنها محدود كردن نمايش راه حلها به مجموعه ثابتي الگوريتم از پارامترها، جستجو را به سمت نواحي داراي تنوع ضعيف متمايل مي كند. سرانجام دامنه اي كه در آن به الگوريتم هاي تكاملي توجه زيادي شده است، بهينه سازي چندمنظوره است.

 

 

مرجع

Evolutionary Computing

A.E. Eiben and M. Schoenauer

arXiv:cs.AI/0511004 v1 1 Nov 2005

 

[1] Premature convergence

[2] Bit-excheng

[3] Bit-flip

[4] Gaussian

[5] Plus replacement strategy

[6] Formal