عملگر انتخاب و بهینه‌سازی


Widget not in any sidebars

نحوه عملیات تغییر
با مشخص شدن موارد فوق یک عملگر خاص ایجاد می‌شود که به آن عملگر جهشی گفته می‌شود. در این نوع عملگرها از اطلاعات یک جواب استفاده کرده و جواب دیگری ایجاد می‌شود. این تغییر ممکن است کم یا زیاد بوده که به همان میزان از اطلاعات زیاد یا کم استفاده می‌شود. به عبارت دیگر هر چه تغییرات زیادتر باشد جواب حاصله تصادفی‌تر خواهد بود و این تصادفی ‌بودن برای ورود مواد ژنتیکی جدید به داخل جمعیت مفید می‌باشد.
وقتی که جمعیت به سمت جواب خاصی همگرا می‌شود احتمال جهش باید زیاد شده تا از این عمل جلوگیری نماید و بالعکس وقتی جمعیت دارای جواب‌های غیر یکسان است باید احتمال جهش کم شود. بنابراین احتمال جهش تابع معکوسی از تعداد جواب‌های غیر یکسان جمعیت است. می‌توان بر اساس این موضوع احتمال جهش را بین دو مقدار در حال تغییر قرار داد. نکته دیگر درباره عملگرهای فوق یافتن تعداد نقاط جهش است که این مورد از مسأله‌ای به مسأله دیگر فرق می‌کند و برای یافتن مقدار بهینه آن باید از روش سعی و خطا استفاده کرد [37].
3-4-8-2. عملگرهای تقاطعی
عملگرهایی که یک یا چند نقطه از دو یا چند جواب را انتخاب و مقادیر آنها را تعویض می‌کنند. این عملگرها یک جواب را در نظر گرفته و محل‌هایی از جواب را با جواب‌های دیگر معاوضه کرده و جواب‌های جدید را بوجود می‌آورند. به این نوع عملگرها، عملگرهای تقاطعی گفته می‌شود. در مورد این عملگرها مورد ذیل حائز اهمیت است:
نقاط تعویض
کروموزوم‌هایی که معاوضه در آنها صورت می‌گیرد نقاط تعویض هستند. هر چه تعداد جواب‌هایی که در این عملیات شرکت می‌کنند کمتر باشد جواب‌های حاصله به جمعیت قبلی نزدیک‌تر خواهند بود.
همانطور که قبلا نیز بیان شد نقش عملگرهای ژنتیکی در کارایی الگوریتم بسیار مهم می‌باشد. در سال‌های اخیر تحقیقات زیادی در راستای بهینه‌سازی عملگرهای ژنتیکی صورت گرفته، ولی مطلب حائز اهمیت این است که هیچ رویه یا دستورالعمل خاصی که طبق آن بتوان عملگرهای مناسب طراحی نمود وجود ندارد و طراحی عملگرها کاملا تجربی و بستگی به توانایی تحلیل‌گر دارد.
3-4-8-3. عمل تحول
عملگری که در این بخش معرفی می‌شود عملگر انتخاب بوده که وظیفه اصلی آن هدایت الگوریتم به نواحی امید بخش فضای جواب می‌باشد و دارای سه بخش اساسی فضای نمونه‌گیری، مکانیسم نمونه‌گیری و احتمال انتخاب است که ذیلا به تشریح هر کدام از آنها پرداخته می‌شود.
3-4-8-3-1. فضای نمونه‌گیری
عملگر انتخاب برای ایجاد نسل بعد یا از همه نوزادان و والدین استفاده می‌کند و یا از بخشی از آنها، به طور کلی دو نوع فضای نمونه‌گیری وجود دارد:
الف) فضای نمونه‌گیری عادی
این روش به این صورت بوده که هر نوزاد بلافاصله پس از تولید جایگزین والد خود می‌شود. در این روش اگرpop-size اندازه جمعیت و off-size اندازه نوزادان تولید شده در هر نسل باشد اندازه فضای نمونه‌گیری pop-size خواهد بود که شامل همه نوزادان تولید شده می‌باشد. اشکال اساسی این است که هیچ تضمینی برای اینکه نوزادان تولید شده بهتر از والدین باشند وجود ندارد. محققین برای غلبه بر این ایراد چند روش پیشنهاد نموده‌اند. مثلا هالند پیشنهاد کرد که به جای اینکه نوزادان جایگزین والدین خود شوند جایگزین یک کروموزوم که به صورت تصادفی انتخاب می‌گردد شوند.
ب) فضای نمونه‌گیری توسعه‌یافته
در این روش کلیه والدین و نوزادان دارای شانس برابر برای انتخاب‌شدن هستند. اگر pop-size اندازه جمعیت و off-size اندازه نوزادان تولید شده در هر نسل باشد آنگاه اندازه فضای نمونه‌گیری مجموع دو اندازه فوق خواهد بود. مزیت عمده این روش در این است که کارایی الگوریتم را می‌توان با افزایش نرخ‌های جهشی و تقاطعی بالا برد.
3-4-8-3-2. مکانیسم نمونه‌گیری
مکانیسم نمونه‌گیری به چگونگی انتخاب کروموزوم‌ها از فضای نمونه‌گیری مربوط می‌شود که رویکرد اصلی آن رویکرد نمونه‌گیری تصادفی است. دو نمونه‌گیری تصادفی که اکثرا از آن استفاده می‌شود عبارتند از: انتخاب چرخ رولت و انتخاب کلی تصادفی.
انتخاب چرخ رولت
انتخاب چرخ رولت که اولین‌بار توسط هالند[34] پیشنهاد شد یکی از مناسب‌ترین انتخاب‌های تصادفی بوده که ایده آن احتمال انتخاب می‌باشد. احتمال انتخاب متناظر با هر کروموزوم، بر اساس برازندگی آن محاسبه می‌شود بطوریکه اگر fk مقدار برازندگی کروموزوم k ام باشد احتمال بقای متناظر با آن کروموزوم عبارت است از:
(n=pop-size)
حال کروموزومها را بر اساس pkمرتب کرده و qk که همان مقادیر تجمعی pk می‌باشد به صورت زیر به دست می‌آید: