الگوریتم ژنتیک روشی است برای بهینه سازی مسائل محدود و نامحدود و بر اساس فلسفه انتخاب اصلح در طبیعت بنا شده است. الگوریتم ژنتیک به صورت تکراری جمعیتی از راه حل ها را اصلاح می کند. در هر مرحله ، الگوریتم ژنتیک تعدادی از افراد را به صورت تصادفی از جمعیت کنونی انتخاب می کند تا والدینی برای فرزندان مرحله بعد باشند. در نسل های متوالی ، جمعیت به سوی راه حل بهینه پیش می رود.
الگوریتم ژنتیک برای تولید نسل بعدی از روی نسل کنونی ، از سه قانون اصلی تبعیت می کند:
- قوانین انتخاب ، افرادی(والدینی ) را که در جمعیت نسل بعدی شرکت می کنند ، انتخاب می کند.
- قوانین تقاطع ، برای تشکیل فرزندان نسل بعد، دو والد را با هم ترکیب می کند.
- قوانین جهش ، برای تشکیل فرزندان، تغییراتی تصادفی در والدین به وجود می آورد.
3-9-1- بعضی از اصطلاحات الگوریتم ژنتیک
تابع برازندگی[1]: تابع برازندگی تابعی است که می خواهیم بهینه کنیم. برای الگوریتم های بهینه سازی استاندارد ، این تابع با نام تابع هدف خوانده می شود. در اینجا ما کمینه تابع برازندگی را محاسبه می کنیم.
افراد[2]: هر فرد، نقطه ای است که می توان تابع برازندگی را بر آن اعمال نمود. مقدار تابع برازندگی برای هرفرد ، نمره آن فرد محسوب می شود. برای مثال اگر تابع برازندگی به صورت ذیل باشد:
(3-1)
بردار (1، 3-، 2) که طول آن برابر با تعداد متغیرهای این مسئله است ، یک فرد است و نمره این فرد، (1، 3-، 2)f و برابر با 51 است.
یک فرد گاهی اوقات بانام ژنوم نیز نامیده می شود و ورودی های بردار هر فرد، با نام ژن خوانده می شوند.
جمعیت و نسل ها[3]: هر جمعیت،گروهی از افراد است. برای مثال ، اگر تعداد جمعیت برابر 100 باشد، و تعداد متغیرهای تابع برازندگی برابر 3 باشد، جمعیت با یک ماتریس 3×100 نشان داده می شوند. ممکن است در یک جمعیت ، یک فرد ثابت بیشتر از یکبار وجود داشته باشد. برای مثال، فرد (1، 3-، 2) ممکن است در چند سطر از ماتریس وجود داشته باشد.
در هر مرحله، الگوریتم ژنتیک تعدادی محاسبات بر روی جمعیت کنونی انجام می دهد تا جمعیت جدیدی را به وجود آورد. هر جمعیت متوالی ، یک نسل جدید نامیده می شود.
تنوع[4]: تنوع یا پخشی به میانگین فاصله بین افراد هر جمعیت گفته می شود. اگر میانگین فاصله بزرگ باشد ، جمعیت دارای پخشی زیادی است.
تنوع در الگوریتم ژنتیک بسیار حائز اهمیت است زیرا به الگوریتم اجازه می دهد که محدوده بزرگتری از فضا را جستجو کند.
مقادیر برازندگی و مقادیر بهترین برازندگی[5] : مقدار برازندگی یک فرد، مقدار تابع برازندگی برای آن فرد است. از آنجایی که الگوریتم ، کمترین مقدار تابع برازندگی را پیدا می کند، بهترین مقدار تابع برای یک جمعیت ، کوچکترین مقدار تابع برای هر فرد درآن جمعیت است.
والدین و فرزندان [6]: برای تولید نسل بعدی ، الگوریتم ژنتیک افراد مشخصی را از نسل کنونی انتخاب می کند که به این افراد والدین گفته می شود و از آنها برای تولید نسل آینده استفاده می شود. نسل بعدی فرزندان خوانده می شوند. معمولا الگوریتم ژنتیک والدینی را انتخاب می کند که مقادیر برازندگی کمتری داشته باشند.
3-9-2- نحوه عملكرد الگوریتم ژنتیک:
در اینجا به طور خلاصه توضیح داده شده است که الگوریتم ژنتیک چگونه کار می کند:
- الگوریتم با تولید یک جمعیت اولیه تصادفی شروع می شود.
- سپس الگوریتم، رشته ای از جمعیت های جدید را به وجود می آورد. درهر مرحله ، الگوریتم از افراد نسل کنونی استفاده می کند تا جمعیت بعدی را بسازد. برای تولید جمعیت جدید، الگوریتم مرحل زیر را انجام می دهد:
الف- با محاسبه مقدار برازندگی، به هر عضو جمعیت کنونی نمره می دهد.
ب- نمرات خام تابع را تغییر مقیاس می دهد (نرمالیزه می کند( تا در محدوده ای قابل استفاده تر قرار بگیرند.
پ- والدین را بر اساس مقدار برازندگی آنها انتخاب می کند.
ت-تعدادی از افراد جامعه کنونی که برازندگی کمتر دارند، به عنوان نخبه انتخاب می شوند و مستقیما به نسل بعد منتقل می شوند.
ث-از روی والدین فرزندان را تولید می کند. فرزندان یا به صورت جهش ( انجام تغییرات تصادفی روی تنها یک والد) ، یا به صورت تقاطع ( ترکیب دو بردار ورودی به صورت یک جفت والد) تولید می شوند.
ج-جمعیت کنونی را با فرزندان جایگزین می کند تا نسل بعد را تولید کند.
- هنگامی که یکی از معیارهای توقف به وقوع بپیوندد، الگوریتم متوقف می شود.
[1] – Fitness functions
[2] – Individuals
[3] – populations and generation
[4] – Diversity
[5] – fitness values and best values
[6] – parents and children