انتخاب: اولین قدم شامل انتخاب افرادی از جمعیت برای تولید مثل است. این انتخاب به صورت تصادفی، با بهره گرفتن از یک احتمال متناسب با تابع برازندگی افراد انجام می­گردد. در این مرحله، باید در ارتباط با نحوه انتخاب والدین برای عمل تقاطع (باز ترکیب)^[۲۵]، نحوه تولید فرزندان و تعداد فرزندان تصمیم ­گیری گردد. هدف این است که والدین شایسته­تر انتخاب­شده که منجر به تولید فرزندانی با برازندگی بالا گردد. کروموزوم­هایی که از جمعیت اولیه برای تولید مثل انتخاب می­شوند، والدین نام دارند. همگرایی الگوریتم ژنتیک وابستگی بالایی به دامنه و شدت فشار رویه انتخاب برای گزینش افراد شایسته­تر دارد.

روش­های مختلفی برای انتخاب وجود دارد که از آن جمله ‌می‌توان به موارد زیر اشاره کرد:

• انتخاب مرتبه­ای

در این روش، کروموزوم­ها بر اساس مقدار برازندگی آن ها رتبه ­بندی شده و به ترتیب بدترین به بهترین رتبه مرتب می­گردند. احتمال انتخاب هر کروموزوم بر اساس درصد نسبی رتبه خود ‌می‌باشد.

• انتخاب تصادفی

در این روش والدین بر اساس یک روش کاملاً تصادفی از جمعیت انتخاب می­شوند. این روش با توجه به عدم اهمیت به شانس بیش­تر بهترین­ها برای تولید مثل، از کیفیت پایینی نیز برخوردار است.

• انتخاب رقابتی

در این روش یک زیر مجموعه کوچکی از کروموزوم­ها به صورت تصادفی انتخاب شده و به رقابت می­پردازند. سرانجام در این رقابت، بر اساس میزان برازندگی، یکی از آن­ها به پیروزی رسیده و انتخاب می­ شود. ایراد این روش این است که در آن هیچ­گاه کروموزوم دارای کم­ترین شانس برنده نخواهد شد.

• انتخاب بولتزمن

این روش بیش­تر در الگوریتم انجماد تدریجی مورد استفاده قرار ‌می‌گیرد. در این حالت دما از یک مقدار بالا در ابتدای الگوریتم شروع می­ کند و معنای آن این است که فشار انتخاب پایین است. دما به مرور کاهش می­یابد و به دنبال آن، فشار انتخاب به مرور افزایش می­یابد. ‌بنابرین‏ در این حالت، در ابتدای الگوریتم گوناگونی افزایش یافته و در انتها جستجوی محلی قوت می­یابد.

• انتخاب چرخ رولت

روشی که غالباً در انتخاب والدین مورد استفاده ‌می‌گیرد، همان‌ طور که در شکل ۲-۱ می بینید، سطح چرخ رولت به بخش هایی تقسیم می­ شود که تعداد آن­ها برابر تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم ‌می‌باشد. سپس چرخ رولت به گردش در می ­آید تا در نقطه­ای به تصادف متوقف شود. این نقطه، کروموزوم انتخاب شده را مشخص می­سازد. کروموزوم­هایی انتخاب می­شوند که سطح بیش تر(شایستگی بالاتری) را دارا می­باشند. این شیوه انتخاب سبب می­ شود که با گذشت زمان، تعداد کروموزوم­های مطلوب در جمعیت افزایش یابد به طوری که میانگین مقدار برازندگی جمعیت در مقایسه با جمعیت مرحله قبل بیش­تر شود.

شکل ۲-۱- نمایش انتخاب چرخ رولت در الگوریتم ژنتیک (فتاحی، ۱۳۹۱)

تولید مثل: در قدم دوم، عملگرهای ترکیب مجدد و جهش روی افراد انتخاب شده به کار گرفته شده و کروموزوم­های جدید تولید می­گردد. در این مرحله، فرزندان جدید تولید می­شوند. در این مرحله عملگر ترکیب مجدد (تقاطع)، فرآیندی است که در ۳ مرحله صورت ‌می‌گیرد:

الف) اپراتور تولید مثل یک زوج والد را از حوضچه تولید مثل انتخاب می­ نماید.

ب) یک نقطه تقاطع به طور تصادفی در طول رشته انتخاب می­ شود.

ج) مقادیر رشته­ ها با توجه به نقطه تقاطع تعویض می­گردند.

عملگر تقاطعی با یک احتمال از قبل تعیین شده، بر روی کروموزوم­های والد عمل می­ کند. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقأ مشابه والدین خواهند بود.

روش­های مختلفی برای عملگر تقاطع وجود دارد و بخشی از این روش­ها به شرح زیر هستند:

• تقاطع دو نقطه­ای

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

• تقاطع چند­نقطه­ای

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

• تقاطع یکنواخت

بر اساس این عملگر، یک ژن از هر دو والد به طور مستقل از سایر ژن­ها، شانس برابر برای حضور در کروموزوم یک فرزند را دارد. در این حالت، بر اساس یک توزیع تصادفی باینری مشخص می­ شود که یک ژن از کدام والدین انتخاب شده است. مثلاً اگر توزیع باینری ۱ را نشان داد، آن ژن از والد اول و اگر ۰ بود از والد دوم انتخاب می­گردد.

• تقاطع از سه والد

در این روش، ۳ والد به صورت تصادفی انتخاب می­ شود. هر ژن از والد اول با همان ژن از والد دوم مقایسه می­ شود. در صورتی که مشابه باشند، همان ژن به فرزند منتقل می­ شود و در غیر این صورت با والد سوم مقایسه می­ شود. این روش بر این پایه استوار است که شباهت­های والدین کشف شده و بر اساس آن­ها فرزندانی تولید می­گردد.

• تقاطع مرتب

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

• تقاطع تک نقطه­ای

عملگر تقاطعی تک نقطه­ای معمول­ترین نوع عملگرهای تقاطع محسوب می­ شود که در مدل ارائه شده در این تحقیق هم از آن بهره گرفته شده است. در این عملگر دو کروموزوم به صورت تصادفی از یک نقطه شکسته می­شوند و بخش­های شکسته شده دو کروموزوم با هم جابه­جا می­گردند. بدین ترتیب، دو کروموزوم جدید به دست می ­آید. به کروموزوم­های اولیه، کروموزوم­های والد و به کروموزوم­های حاصل شده از عمل جا به ­جایی، فرزند می­گویند (فتاحی، ۱۳۹۰). یک مثال از عملگر تقاطع تک­نقطه­ای در شکل ۲-۲ نشان داده شده است.

شکل۲-۲- نمایش عملگر تقاطع تک­نقطه­ای در الگوریتم ژنتیک (فتاحی، ۱۳۹۰)

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

شکل­های مختلفی برای جهش به شرح زیر موجود است:

• • معکوس کردن