در ترکیب چندگانه n نقطه ترکیبی به صورت تصادفی و بدون تکرار تعیین شده و به صورت صعودی مرتب می شوند. سپس متغیرهای بین هر دو نقطه ترکیبی، یک در میان بین دو والد جابجا می شوند تا به این ترتیب دو فرزند جدید تولید شوند.
ترکیب یکنواخت
در ترکیب یکنواخت، هر ژن کروموزوم جدید به صورت جداگانه انتخاب می شود. هر ژن وابسته به موقعیتش به صورت تصادفی از یکی از دو والد انتخاب می شود. در این نوع ترکیب، یک فرزند بوجود می آید. در این روش از یک ساختار مشابه با افراد تحت عنوان ماسک استفاده می شود. مقادیر ماسک به صورت تصادفی تعیین می شوند و از آنها برای تعیین نحوه مشارکت والدین در تولید فرزندان استفاده می گردد. جمعیت جدیدی که با ترکیب یکنواخت به وجود می آید دارای تنوع ژنتیکی بیشتری نسبت به ترکیب های تک نقطه ای و دو نقطه ای می باشد. به همین دلیل این نوع ترکیب در جمعیت هایی که اعضای کمی دارند اثر بهتری دارد تا جمعیت هایی که تعداد اعضای زیادی دارند.
برای روشن شدن نحوه عملکرد این روش به مثال زیر توجه کنید، دو فرد زیر را در نظر بگیرید:
Individual 0 1 1 1 0 0 1 1 0 1 0
Individual 1 0 1 0 1 1 0 0 1 0 1
برای تولید فرزندان، در صورتی که مقدار یک بیت از ماسک برابر با یک باشد مقدار بیت متناظر آن در فرزند، از فرد اول و در صورتی که صفر باشد از فرد دوم گرفته می شود. فرض کنید ماسک به صورت زیر باشد :
Sample 0 1 1 0 0 0 1 1 0 1 0
Sample 1 0 0 1 1 1 0 0 1 0 1
بعد از انجام عملیات تلفیق یکنواخت، فرزندان به صورت زیر خواهند بود :
Offspring 1 1 1 0 1 1 1 1 1 1 1
Offspring 0 0 1 1 0 0 0 0 0 0 0
2-11-9- احتمال ترکیب
برای تعیین رخ دادن یا ندادن ترکیب، از پارامتری به نام احتمال ترکیب استفاده می شود که این پارامتر مقداری بین صفر و یک است. اگر ترکیبی صورت نگیرد، فرزندان دقیقا همانند والدین خواهند بود. اگر ترکیب صورت بگیرد، فرزندان از بخش هایی از کروموزوم های والدین به وجود می آیند. اگر احتمال ترکیب یک باشد، در این صورت همه فرزندان در نتیجه ترکیب به وجود آمده اند. اگر این احتمال صفر باشد، کل نسل جدید، در اثر نسخه برداری عینی کروموزوم های نسل قدیم به وجود آمده است. مقدار برای جمعیت هایی با اندازه 30 تا 200 ، در محدوده 0.5 تا 1 خواهد بود.
2-11-10- جهش
پس از عمل ادغام رشته ها، نوبت به عمل جهش می رسد. این عمل برای جلوگیری از همگرایی سریع و کمک به الگوریتم جستجو برای فرار از به دام افتادن در مینیمم های محلی مفید است. از سوی دیگر این عمل برای حفظ حالت متفاوت و متمایز بودن کروموزوم ها در یک جمعیت به کار می رود. عمل جهش به این ترتیب است که یک عدد تصادفی بین صفر تا یک تولید می شود. اگر عدد تولید شده کوچکتر از (احتمال جهش) باشد، مقدار خروجی را برابر درست[71] و گرنه برابر غلط[72] در نظر می گیریم. اگر برای یک بیت مقدار خروجی درست باشد بیت تغییر می کند در غیر این صورت بیت بدون تغییر باقی خواهد ماند.
وارونه سازی بیت
از این نوع جهش در کدگذاری باینری استفاده می شود. در اینجا بیتی که شرایط جهش را دارد اگر صفر باشد به یک و اگر یک باشد به صفر تغییر مقدار می دهد.
شکل 2-6 عملگر جهش وارونه سازی بیت
تغییر ترتیب قرار گیری
از این نوع جهش مخصوصا در الگوریتم هایی استفاده می شود که کدگذاری بر اساس مقدار باشد. در این جهش ، محـل قرار گیری دو ژنی که می خواهند جهش بیابند در کروموزوم تعویض می شوند.
شکل 2-7 عملگر جهش تغییر ترتیب
2-11-11- استراتژی برخورد با محدودیت ها
بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد چگونگی برخورد با محدودیت های مسئله می باشد زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم های غیرموجه نیز مـی شوند. میکالـویچ [35] چند تکنیک مـعمول جهت مواجهه بـا محدودیت ها، تقسیم بندی نموده است که در ادامه به برخی از آنها اشاره می شود.
استراتژی اصلاح عملگرهای ژنتیک[73]
یک روش برای جلوگیری از تولید کروموزوم غیر موجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزوم ها، کروموزوم تولید شده نیز موجه باشد. در این حالت یک سری مشکلات وجود دارد. مثلا پیدا کردن عملگری که دارای شرایط فوق باشد بسیار دشوار بوده و از مسئله ای به مسئله دیگر متفاوت می باشد.
استراتژی ردی[74]
در ایـن روش پس از تـولید هر کروموزوم آن را از نظر موجه بودن تست کرده و در صورت غیر موجه بودن حذف می گردد. این روش بسیار ساده و کارا می باشد.
استراتژی اصلاحی[75]
در ایـن روش به جای اینکه کروموزوم غیر موجه حذف گردد تبدیل به یک کروموزوم موجه می گردد. این روش نیز مانند روش اول به مسئله وابسته بوده و یافتن فرایند اصلاح گاهی بسیار پیچیده می باشد.
استراتژی جریمه ای[76]
در این روش بر خلاف سه روش قبل که از ورود جواب های غیر موجه جلوگیری می کردند، جواب های غیر موجه با احتمال کم امکان حضور می یابند. سه روش فوق دارای این اشکال بودند که بـه هیچ نقطه ای بیرون از فضای موجـه توجـه نمی کردند ، اما در بعضی مسائل بهینه سازی جواب های غیر موجه درصد زیادی از جمعیت را اشغال می کنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجه انجام گیرد شاید یافتن جواب موجه خیلی وقت گیر و مشکل باشد. استراتژی جریمه ای از متداول ترین تکنیک های مورد استفاده برای پذیرش با جواب های غیر موجه می باشد که در
آن ابتدا محدودیت هـای مسئله در نظر گرفته نمی شوند ، سپس بـرای هر تخلف از محدودیت ها، یک جریمه اختصاص داده می شود که این جریمه در تابع هدف قرار می گیرد. مسئله اصلی، چگونگی انتخاب یک مقدار مناسب برای مقدار جریمه می باشد که بتواند در حل مسئله کمک نماید. نکته ای که در روش جریمه وجود دارد این است که یک جواب غیر موجه به سادگی حذف نمی شود، زیرا ممکن است در ژن های آن اطلاعات مفیدی وجود داشته باشد که با اندکی تغییر به جواب بهینه تبدیل شود[23].
2-11-12- شرایط توقف الگوریتم
برخی از شرط های متداول توقف عبارتند از :
1- رسیدن به جواب : این روش، ساده ترین روش است. به این معنی که اگر مقدار کروموزوم مناسب ترین باشد، الگوریتم متوقف می شود.
2- عدم پیشرفت : یعنی الگوریتم پس از تعدادی تکرار با همان کروموزوم های قبلی ادامه پیدا کند. چه اینکه الگوریتم به جواب بهینه رسیده باشد و یا در یک مینیمم موضعی گیر افتاده باشد.
3- به روش آماری : اگر مقدار تابع Fitness به یک مقدار مشخصی رسید، الگوریتم متوقف می شود.
4- تعداد تکرارها : اگر با هیچ کدام از موارد فوق جواب نداد، شرط توقف را تعداد تکرارهای مشخصی قرار می دهیم.
5- بهینه ساز موضعی : استفاده از یک بهینه ساز موضعی که در صورت عدم پیشرفت، متوقف شود.
فصل سوم
بیان مسئله و ارائه مدل ریاضی آن