شکل۳-۳:عملگر ترکیب در الگوریتم ژنتیک
۳-۳-۱-۴-۳ عملگر جهش[۵۸]
پس از اتمام عمل ترکیب، عملگر جهش بر روی کروموزومها اثر داده می شود. این عملگر به تعداد nmut که در آغاز برنامه از پیش تعیین می شود، در اینجا ۱% از جمعیت میباشد، از جمعیت جدا کرده و به صورت تصادفی یکی از ژنهای هر کروموزوم را تغییر میدهد. روند تغییر مقدار عددی هر ژن که هرکدام بیانگر یک متغیر طراحی هستند، به این صورت است که یک عدد تصادفی بین (۱و۱-) انتخاب می شود و سپس با یک ضریب (مقدار دلخواه ۰.۱) در بازه مجاز تعریف شده برای آن متغیر ضرب می شود و مقدار d را تشکیل میدهد. این مقدار با مقدار عددی ژن مورد نظر جمع شده و مقدار جدیدی برای ژن بدست میدهد. در شکل ۳-۴ چگونگی جهش یافتن کروموزومهای انتخاب شده نشان داده می شود.
شکل۳-۴:عملگر جهش در الگوریتم ژنتیک
۳-۳-۱-۵ روند کلی اجرای الگوریتم ژنتیک
در شکل ۳-۵ روند کلی یک الگوریتم ژنتیک استاندارد نشان داده شده است. در حالت کلی، وقتی یک الگوریتم ژنتیک اعمال می شود، چرخه زیر را طی می کند]۳۲و۳۳[:
ابتدا یک جمعیت اولیه از افراد به طور اتفاقی و بدون در نطر گرفتن معیار خاص انتخاب می شود. برای تمامی کروموزومهای (افراد) نسل صفر، مقدار تابع هدف با توجه به تابع هدف مسئله ای که ممکن است بسیار ساده یا پیچیده باشد، تعیین می شود. سپس با مکانیزم های مختلف تعریف شده برای عمگر انتخاب، زیر مجموعه ای از جمعیت اولیه انتخاب خواهد شد. سپس روی این کروموزومهای انتخاب شده عملیات ترکیب و جهش در صورت لزوم با توجه به مسئله انجام خواهد شد. اکنون باید این کروموزومهایی که تا بحال یک بار عملگرهای ژنتیکی بر روی آنها اعمال شده است، با کروموزومهای جمعیت اولیه (نسل صفر) از لحاظ مقدار تابع هدف مقایسه شوند. بعد از مقایسه، کروموزومهای باقی مانده که بیشترین مقدار ارزش را از نظر تابع برازندگی دارا میباشند، به عنوان جمعیت اولیه برای نسل بعدی مورد استفاده قرار میگیرند. هر مرحله تکرار الگوریتم، یک نسل جدید را ایجاد می کند که با توجه به اصلاحاتی که بر روی آنها صورت پذیرفته، به سوی تکامل پیش خواهند رفت. این روند تکرار می شود تا شرط خاتمه مسئله برآورده شود. شرط خاتمه می تواند تعداد تکرار مشخص، زمان تکرار مشخص، تغییر نکردن محدوده جواب ها و … باشد.
شکل۳-۵ روند کلی یک الگوریتم ژنتیک استاندارد
۳-۳-۲ الگوریتم تکامل تفاضلی[۵۹]
۳-۳-۲-۱ مقدمه
استراتژى تکامل تفاضلى یک روش بهینهسازى احتمالاتى که مبتنى بر جمعیت بنا شده مىباشد. در اصول پایه تولید جمعیت اولیه و ادامه تکامل نسلهاى آینده با الگوریتم ژنتیک مطابقت دارد. تفاوت اصلى این الگوریتم با دیگر الگوریتمهاى تکاملى در انتخاب جهت و فاصله جمعیت فعلى از دیگر عضوهاى جمعیت به منظور هدایت فرایند جستجو به سوى یک جهت مطلوب مىباشد.
۳-۳-۲-۲ تاریخچه
در سالهای اخیریک الگوریتم تفاضلی به نام الگوریتم تکاملی تفاضلی (DE) به عنوان روشی قدرتمند و سریع برای مسائل بهینهسازی در فضاهای پیوسته معرفی شده است. الگوریتم جستجوی DE یکی از جدیدترین روش های جستجو است.
الگوریتم تکاملی تفاضلی (DE) نخستین بار در سال ۱۹۹۵ توسط استورن[۶۰] و پرایس[۶۱] معرفی شد. این دو نشان دادند که این الگوریتم توانایی خوبی در بهینه سازی توابع غیرخطی مشتق ناپذیر دارد.
الگوریتم DE جهت غلبه بر عیب اصلی الگوریتم ژنتیک، یعنی فقدان جستجوی محلی دراین الگوریتم ارائه شده است. تفاوت اصلی بین الگوریتمهای ژنتیکی و الگوریتم DE در عملگر انتخاب selection operators میباشد]۳۴[.
۳-۳-۲-۳ ساختار الگوریتم تکامل تفاضلی
در الگوریتمهاى تکاملى مانند الگوریتم ژنتیک عملگرهاى جهش و ادغام وجود دارد که روند تکامل بر اساس عملگر اصلى یعنى ادغام و در صورت نیاز از عملگر جهش استفاده مىشود. در صورتى که در تکامل تفاضلی روند جهش و ادغام متفاوت مى باشد که این روند عملگرهاى تکامل تفاضلی در موارد زیر تفاوت دارد:
ابتدا عملگر جهش تولید یک بردار مطلوب استفاده مىشود، عمل جهش در واقع از تأثیر افراد جمعیت فعلى صورت مىپذیرد.
عملگر اصلى ادغام که به صورت برش گسسته یا دوجملهاى مىباشد براى تولید فرزند جدید با بهره گرفتن از بردار مطلوب و یک راه حل (والد) بر اساس احتمال صورت مىگیرد.
در عمل اصلى ادغام همیشه یک فرزند تولید مىشود که حجم محاسبات را تقریباً کاهش مىدهد و باعث جهت دادن به فرزندها بر اساس بردار مطلوب صورت مىپذیرد.
به طور کلى تکامل تفاضلى (DE) یک روش جستجوى مستقیم موازى است ]۳۵[ که تعداد NP بردار پارامترى D بعدى را به کارگیرى مى کند.
(۳-۹)
