امروز قصد دارم برای شما دانشجویان عزیز الگوریتم ژنتیک را معرفی کنم و چند مثال کاربردی از آن نیز برای شما ارائه می دهم :
الگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است.
ما یک مربع 3×3 داریم که می خواهیم اعدادی بین 1تا15 را در این مربع قرار دهیم به طوری که جمع
اعداد در هر سطرو ستون برابر 24 شود.
این مسئله تا حدودی پیچیده است. ممکن است یک انسان بتواند آن را در مدت زمانی مشخص حل کند ولی هیچ گاه یک کامپیوتر نخواهد توانست آن را در مدت زمان کوتاهی با استفاده از اعداد تصادفی حل کند. ولی الگوریتم ژنتیک می تواند این مشکل را حل کند.
نسل اول
اولین گام ایجاد کردن یک نسل ابتدایی برای شروع کار است که شامل تعدادی ژنوم تصادفی است. این ژنوم ها به صورت باینری(0و1) نشان داده می شوند. حالا مثال مان:
اول یکسری عدد به صورت تصادفی تولید می شوند. هر ژنوم یا کروموزوم شامل اطلاعاتی برای هر 9 جای خالی است. چون این اعداد مقادیر بین 0 تا 15 دارند می توان آنها را با 4 بیت یا ژن داده نمایش داد. پس هر ژنوم شامل 36 بیت است.
یک نمونه ژنوم می تواند به شکل زیر باشد:
Bits (Genes) 0110 1100 1111 1011 0100 1010 0111 0101 1110
Values(Traits) 6 12 15 11 4 10 7 5 14
حالا باید به هر ژنوم در مجموعه یک عدد تناسب(Fitness) بنابر تاثیر آن در حل مسئله نسبت داد. فرآیند و روش محاسبه این عدد برای هر مسئله فرق می کند. انتخاب الگوی مناسب برای مسئله مشکلترین و حساسترین بخش در حل مسئله ژنتیک است. دراین مثال ما اعداد را در مکان هایشان جایگذاری می کنیم و بررسی می کنیم که چقدر با جواب اصلی فاصله دارند.
|
12 |
6 |
||
|
10 |
4 |
11 |
||
|
14 |
5 |
7 |
|
= = = 24 21 39 |
مقادیر معادل عبارتند از 33و25و26و24و21و39. واضح است که این مقادیر مسئله را حل نمی کنند. پس باید مقادیر تناسب را برای این ژنوم محاسبه کرد. برای این کار ابتدا فاصله هرمجموع را از24 محاسبه کرده، سپس معکوس مجموع تفاصل آنها را محاسبه می کنیم .
بنابراین درجه تناسب برای این ژنوم تقریباً برابر 0.033 است. هرچقدر که اعداد ما به جواب نزدیکتر باشند عدد تناسب بزرگتر خواهد شد. اما اگر مخرج ما برابر 0 شود چه اتفاقی می افتد؟ دراین صورت همه اعداد ما برابر 24 شده اند و ما به جواب رسیده ایم.
نسل بعدی
دو ژنوم به طور تصادفی برای تولید نسل بعدی انتخاب می شوند. این اصلی ترین بخش الگوریتم ژنتیک است که از 3 مرحله تشکیل شده:
انتخاب
دو ژنوم به طور تصادفی از نسل قبل انتخاب می شوند. این ژنوم ها دارای اعداد تناسب بزرگتری هستند و بعضی صفات آنها به نسل بعدی منتقل می شوند. این بدین معنی است که عدد تناسب در حال افزایش خواهد بود.
بهترین روش برای تابع انتخاب(Fitness) در این مسئله روشی به نام رولت(Roulette) است. اول یک عدد تصادفی بین 0 و عدد تناسب نسل قبلی انتخاب می شود. تابع انتخاب به صورت زیر خواهد بود:
RouletteSelection()
{
float ball = rand_float_between(0.0, total_fitness);
float slice = 0.0;
for each genome in population
{
slice += genome. fitness;
if ball < slice
return genome;
}
}
تغییر از یک نسل به نسل بعدی(Cross over)
حالا دو ژنوم بخشی از ژنهایشان را برای ایجاد نسل بعدی اهدا می کنند. اگر آنها تغییر پیدا نکنند همانطور بی تغییر به نسل بعدی منتقل خواهند شد. درجه Crossover نشان دهنده این است که هر چند وقت یکبار ژنوم ها تغییر پیدا خواهند کرد و این عدد باید در حدود 65-85% باشد.
عملگر تغییر در ژنوم های باینری مثال ما با انتخاب یک مکان تصادفی در ژنوم برای تغییر آغاز می شود. بخش اول ژنهای پدر و بخش دوم ژنهای مادر با هم ترکیب می شوند(و بالعکس) تا2 فرزند تولید شوند. در زیریک عمل تغییر را می بینیم.
Before Crossing
Father 011110010011 001011011000111011010000
Mother 010100111110 010101111101000100010010
After Crossing
Child1 011110010011 010101111101000100010010
Child2 010100111110 001011011000111011010000
جهش(Mutation)
قبل از این که ژنوم ها در نسل بعدی قرار بگیرند، احتمال دارد دچار جهش یا تغییر ناگهانی شوند شوند. جهش یک تغییر ناگهانی در ژن است. در ژنهای باینری این تغییر به معنای تغییر یک بیت از 0به 1 یا از 1 به 0 است. درجه جهش نشان دهنده احتمال بروز جهش در یک ژن است و تغریباً بین 1-5% برای ژنهای باینری و 5-20%برای ژنهای عددی است.
