تکثیر، گردان، ، جریمه، دودویی، حقیقی

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

1-2-2-قسمت های مهم الگوریتم ژنتیک
الگوریتم ژنتیک ساده توسط گولبرگ شرح داده شده و در این قسمت برای توضیح قسمت های اصلی ارائه می شود. کد برنامه مجازی در شکل نشان داده شده است که نکات مهم الگوریتم ژنتیک ساده را در بردارد. جمعیت در زمان t با متغیر وابسته به زمان P(t) نشان داده شده است. به کمک این برنامه اجزای مهم الگوریتم ژنتیک شرح داده می شود. این برنامه در زیر نشان داده شده است:
{
Generate initial population Pt
Evaluate population Pt
while stopping criteria not satisfied
repeat
{
Select elements from Pt to put
into Pt+l
Crossover elements of Pt and put
into Pt+l
Mutate elements of Pt and put
into Pt+l
Evaluate new population Pt+l
Pt = Pt+l
}
}
الگوریتم ژنتیک بر روی مجموعه ای از جواب ها که جمعیت نامیده می شوند اعمال می گردد. افراد یک جمعیت رشته هایی از اعداد هستند که کروموزوم نامیده می شوند و حاوی اطلاعات کد شده پارامترهای تصمیم گیری اند. به صورت معمول جمعیت شامل 30 تا 100 فرد است. اگرچه تاحدود 10 فرد هم به کار می رود.
معمولی ترین شیوه نمایش کروموزوم ها در الگوریتم ژنتیک به شکل رشته های دودویی است. هر متغیر تصمیم گیری به صورت دودویی در آمده و سپس با کنار هم قرار دادن این متغیرها کروموزوم ایجاد می شود. اگرچه این روش گسترده ترین شیوه کدگذاری است اما شیوه های دیگری مثل نمایش اعداد حقیقی در حال گسترش است. در فضای بعضی از مسائل این بحث پیش آمده که نمایش دودویی طبیعت جستجو را پیچیده می کند و علاوه بر آن مشکلات دیگری هم دارد. به عنوان مثال دو عدد کدشده 10000000 و 01111111 را در نظر بگیرید.مقادیر حقیقی این دو عدد فقط یک واحد با هم اختلاف دارند. ولی مقادیر کد شده از لحاظ ظاهری اختلاف زیادی با هم دارند. این اختلاف در هنگام اعمال عملگرهای معمول ژنتیک، مشکل زا می شود. به بیان دیگر یک تغییر کوچک در فضای کدشده مشابه آن تغییر در فضای کدنشده را ایجاد نمی کند.
نمایش ژن ها با اعداد حقیقی برای به دست آوردن امتیازاتی در بهینه سازی توابع عددی مطرح شد. این شیوه نمایش به علت اینکه نیازی به خارج شدن از حالت کدشده ندارد و به حافظه کمتری نیاز دارد مورد استفاده قرار می گیرد. در این شیوه چون تبدیل به حالت دودویی نداریم از دقت مقادیر به علت این تبدیل کاسته نمی شود. کدگذاری با اعداد حقیقی برای بهینه سازی توابع بهترین نتایج را می دهد.
نکته مهمی که در هنگام کدگذاری باید به آن دقت شود طبیعت مسأله و قیود آن است. بعد از این اعمال عملگرهای ژنتیک به کروموزوم ها، جواب های جدیدی به دست می آید که ممکن است در قیدهای مسأله صادق نباشند. این حالت در بسیاری از مسائل دارای قید به وقوع می پیوندد. ساده ترین راه حل استفاده از تابع جریمه در تابع هدف است. با این شیوه برازش جواب های خارج از قیود به شدت کم می شود. در نتیجه فرآیند انتخاب به سمت کروموزوم هایی که در قیدها صادقندگرایش پیدا می کند. هرچه میزان جریمه بیشتر باشد الگوریتم با سرعت بیشتری همگرا می شود و در ضمن احتمال رسیدن به بهینه موضعی افزایش می یابد. به همین دلیل میزان جریمه را در مسائل مختلف به وسیله سعی و خطا مشخص می کنند و این مورد اشکالی است که از تابع جریمه گرفته می شود. با توجه به مطالب بین شده نکات مهم در الگوریتم های ژنتیک به شرح زیر است:
1- شرایط جمعیت اولیه می‌تواند در سرعت رسیدن به جواب بسیار تأثیرگذار باشد. یعنی اگر جمعیت اولیه مناسب‌تر باشد، بسیار سریع‌تر به جواب می‌رسیم. بنابراین گاهی در بعضی از مسئله‌ها به جای آن که جمعیت اولیه به صورت تصادفی ایجاد شود، از اعمال شرایط خاص مسئله به جمعیت اولیه نیز استفاده می‌شود.
2- با توجه به وجود پارامترهای تصادفی در الگوریتم مسئله حتی در صورت استفاده از جمعیت اولیه یکسان ممکن است در اجراهای مختلف الزاماً جواب‌های یکسان به دست نیاید و البته در صورت استفاده از جمعیت اولیه متناوت این پدیده ملموس‌تر خواهد بود.
3- تابع ارزش در این‌گونه از الگوریتم‌ها از اهمیت بسزایی برخوردار است؛ چرا که معمولاً در اکثر مسائل در اثر ترکیب، حالت‌هایی رخ می‌دهد که منطبق بر شرایط مسئله نیست و حتی فاقد معنی و مفهوم است. بنابراین تابع ارزش باید به گونه‌ای طراحی شود که به ازای این حالات مقادیر بسیار کمی برگرداند و از طرفی باید برای نزدیک شدن به هدف بسیار خوب تخمین بزند.
4- یکی از پدیده‌های جالب این است که ممکن است در نسل‌های میانی نمونه‌هایی بروز کنند که از نظر تابع ارزش و خوب بودن بسیار مناسب باشند. یک روش این است که اینگونه موارد را شناسایی کنیم و در نسل بعدی نیز از آن‌ها استفاده کنیم. به این تکنیک نخبه‌گرایی می‌گویند که عملاً تأثیر بسزایی در رسیدن به جواب مسئله دارد.

1-2-2-1-تابع هدف و تابع برازش
تابع هدف شاخصی از نحوه عملکرد افراد در فضای مسأله به ما می دهد. به عنوان مثال در مسأله ای که هدف مینیمم سازی باشد مناسب ترین فرد آن است که تابع هدفش کمترین مقدار را داشته باشد. این اطلاعات خام معمولاً به عنوان یک مرحله میانی در تعیین کارایی نسبی افراد در الگوریتم ژنتیک بکار می روند. تابع بعدی در این مرحله تابع برازش است. این تابع برای تبدیل مقادیر تابع هدف به مقیاسی برای سازگاری و کارایی نسبی افراد بکار می رود. مقادیر برازش را مثبت در نظر می گیرند. بنابراین در مواردی که مقدار تابع هدف منفی می شود یکی از کارهای تابع برازش مثبت کردن این مقادیر است.
در بعضی از موارد مقدار تابع برازش متناسب با تعداد فرزندانی است که انتظار می رود از آن کروموزوم تولید شود. یک روش معمول این است که برازش هر فرد برابر حاصل قسمت تابع هدف بر مجموع توابع هدف در نظر گرفته شود. این روش در مواقعی که توابع هدف منفی هستند با مشکل مواجه می گردد. از یک تبدیل خطی و مثبت سازی برای غلبه بر این مشکل استفاده می شود.
استفاده از تبدیل خطی ممکن است باعث ایجاد همگرایی زودرس شود. الگوریتم انتخاب کروموزوم ها را بر پایه برازش آن ها انتخاب می کند. استفاده از تبدیل خطی باعث می شود که تعداد فرزندانی که از هر کروموزوم انتظار می رود متناسب با کارایی آن باشد. اگر هیچ قیدی در نظر گرفته نشود آنگاه کروموزوم هایی که کارایی بالا دارند بر دیگر کروموزوم ها چیره شده و نسل جدید را فرزندان آن ها تشکیل می دهند. با این عمل احتمال این که به نقاط بهینه نسبی و نه بهینه کلی برسیم زیاد می شود. به صورت مشابه اگر پراکندگی جمعیت کم باشد با تبدیل خطی زمان لازم برای رسیدن به بهینه کلی زیاد خواهد شد.
با محدود کردن میزان تکثیر کروموزوم ها هیچ کروموزومی نمی تواند بیش از حد فرزند ایجاد کند. این کار مانع همگرایی زودرس می شود. می توان برازش افراد را متناسب با جایگاه آن ها در جمعیت و نه مقادیر تابع هدف آن ها انتخاب کرد. متغیری به نام sp (0 sp 1) برای تعیین تمایل انتخاب بهترین فرد معین شده و برازش دیگر افراد بوسیله رابطه (1-1) مشخص می شود.
(1-1)

F مقدار برازش، N تعداد افراد و x فرد دارای مرتبه i در جمعیت است. در بهترین فرد i = 1 و در بدترین فرد i = N است. برای مثال اگر جمعیت 40 عضو داشته باشد و sp = 0.9 باشد آنگاه برازش افراد در محدوده [0.9 1.1] قرار می گیرد. ضعیف ترین کروموزوم برازش 9/0 و بهترین کروموزوم برازش 1/1 را دارا خواهد بود فاصله بین مقادیر برازش دو کروموزوم مجاور 005/0 می شود.
روش دیگری نیز برای تعیین برازش افراد بر حسب جایگاه آن ها در جمعیت وجود دارد. در این شیوه برازش از فرمول زیر محاسبه می شود:

(1-2)
در این روش فاصله بین مقادیر برازش ها یکسان نیست ولی مجموع مقادیر برازش یک می شود.

1-2-2-2- انتخاب
انتخاب فرایند تعیین دفعاتی است که یک فرد خاص می تواند در مرحله تکثیر شرکت کند. به بیان دیگر تعداد فرزندانی که از یک فرد بوجود خواهند آمد، در این مرحله مشخص می شوند. انتخاب افراد به طور کلی شامل دو فرایند جداگانه است.
مشخص کردن تعداد دفعاتی که انتظار می رود یک فرد در مرحله تکثیر شرکت کند.
تبدیل اعداد بدست آمده از مرحله قبل به اعداد صحیح.
مرحله اول مربوط به تبدیل برازش افراد به احتمال شرکت افراد در مرحله تکثیر است و بیشتر در مرحله تعیین برازش انجام می شود. مرحله دوم انتخاب احتمالی افراد است که بر اساس برازش نسبی صورت می گیرد و نمونه برداری هم خوانده می شود.
بسیاری از تکنیک های انتخاب از چرخ گردان استفاده می کنند. یک فاصله از صفر تا مجموع برازش ها در نظر گرفته می شود. سپس مقادیر برازش آنها در کنار هم روی این فاصله قرار می گیرند. سایز فاصله مربوط به هر فرد متناسب با برازش آن است. به جای خط راست از یک دایره هم می توان استفاده کرد.
محیط دایره برابر مجموع برازش های کلیه افراد جمعیت است. برای انتخاب یک فرد عددی بین یک و صفر تا مجموع برازش ها انتخاب شده و فردی که این نقطه در محدوده آن قرار می گیرد انتخاب می شود. این فرایند تا انتخاب تعداد افراد لازم تکرار می گردد.
روش انتخاب با چرخ گردان یک نمونه برداری تصادفی با جایگزینی محسوب می شود. اندازه هر قسمت و احتمال انتخاب هر فرد در طی فرایند انتخاب ثابت باقی می ماند. هر فرد که احتمال انتخاب آن صفر نباشد از لحاظ تئوری می تواند والد تمامی نسل بعد باشد.
می توان اندازه هر بخش را بعد از انتخاب شدن تغییر داد. هربار که یک فرد انتخاب شد اندازه بخش مربوط به آن یک واحد کم می شود. اگر اندازه بخش منفی شود آنگاه صفر در نظر گرفته می شود.
از چرخ گردان در یک روش دیگر هم استفاده می شود. در این روش به مقدار جز صحیح برازش هر فرد یک کپی از آن انتخاب می شود. سپس مقادیر اعشاری برازش ها در یک چرخ گردان قرار گرفته و باقی مانده انتخاب ها به یکی از دو روش قبلی با جایگذاری و یا بدون آن مشخص می شوند.
روش دیگر نمونه برداری تصادفی کلی است. در این روش به جای انتخاب یک فرد در هر مرحله تمامی افراد لازم را با هم انتخاب می کنیم. اگر N انتخاب لازم باشد عددی مثل P را در فاصله صفر تا حاصل تقسیم مجموع برازش ها بر N به صورت تصادفی انتخاب کرده سپس افراد را با یک ترتیب تصادفی می چینیم. حال N نشانگر را در موقعیت های P و P + 1 و… P + N -1 قرار می دهیم.
هر فردی که نشانگر بر روی آن قرار گیرد انتخاب می شود. در این شیوه زمان کمتری برای انتخاب صرف می شود.
در بعضی مقالات از انتخاب مسابقه ای استفاده شده است. در این روش هر بار تعداد دو و یا چند کروموزوم بوسیله چرخ گردان انتخاب شده است و از میان آن ها بهترینشان انتخاب می شود و این کار تا انتخاب تمام افراد لازم ادامه می یابد.
روشی برای اعمال قید بدون اعمال تابع جریمه پیشنهاد شده که در مرحله انتخاب انجام می شود. هربار دو فرد بوسیله چرخ گردان انتخاب می شوند و بین آن ها مقایسه صورت می گیرد. اگر هر دو مجاز بودند آنکه برازش بالاتری دارد انتخاب می شود. اگر هر دو غیر مجاز بودند آنکه انحراف از قید کمتری دارد انتخاب می شود. در صورتی که یکی مجاز و دیگری غیر مجاز باشد آنکه مجاز است انتخاب می شود. در این شیوه دیگر نیاز به تابع جریمه نیست و مستقل از نوع مسأله است.
در تمام روش های بالا نظم بین افراد ایجاد شده باید قبل از رفتن به مرحله بعد و اعمال عملگرها بر هم زده شود.

1-2-2-3- تقاطع
عملگر اساسی در الگوریتم ژنتیک برای تولید کروموزوم عملگر جابجایی می باشد. همانند آنچه در طبیعت وجود دارد، عملگر جابجایی افراد جدیدی تولید می کند که از قسمت های مختلف ژن والدین خود تشکیل شده اند. این عملگر بر روی یک جفت از کروموزوم های انتخاب شده اعمال می شود. این عملگر، مهم ترین عملگر ژنتیکی بوده و به عنوان موتور جستجوی الگوریتم ژنتیک در فضای کاوش می باشد که عملکرد الگوریتم ژنتیک به مقدار وسیعی به نوع عملگر جابجائی به کار رفته در آن بستگی دارد. انجام عمل جابجائی به روش کدگذاری جوابها بستگی دارد. عملگر اصلی ایجاد نسل جدید در مرحله تکثیر تقاطع است. همانند کروموزوم ها در طبیعت فرزندان حاصل از این عمل هریک بخشی از اطلاعات روی کروموزوم های والدین را دارند. ساده ترین نوع تقاطع، تقاطع یک نقطه ای است. در زیر چند نمونه روش جابجائی برای دو حالت کدگذاری دودوئی و حقیقی ارائه شده است.
روش های معمول جابجائی دودویی شامل جابجایی تک نقطه، دو نقطه، چند نقطه و جابجایی یکنواخت می باشد. ساده ترین حالت جابجا کردن،