تو ضیح الگوریتم ژنتیک با یک مثال عملی

[donya88]

در این تایپیک سعی بر ان داریم تا الگوریتم ژنتیک را با یک مثال عملی خیلی ساده و خلا صه توضیح دهیم.
توضیحات در ارتباط با قسمتهای مختلف الگوریتم از جمله کروموزومها- تابع برازش - ژنهاو.....در کتابها و مقالات و همچنین در این سایت و همین بخش وجود دارد
همانگونه که می دانیم چند صبا حی است که الگوریتم ژنتیک کاربردش را در علوم مختلف از جمله علم اقتصاد یافته است. وظیفه ی ماست که برای کسب این دانش در هر رشته ای که تحصیل می کنیم سعی کرده و از کاربرد ان استفاده نماییم.
متن زیر چکیده ای است از تحقیقی که در ارتباط با همین موضوع می باشد .
با این توضیحات مختصر به سراغ بحث می رویم .
در این مثال می خواهیم مسئله ی 8 وزیر را بوسیله ی این الگوریتم حل کنیم .
هدف مشخص کردن چیدمانی از 8 وزیر در صفحه ی شطرنج است به نحوی که هیچ یک همدیگر را تهدید نکند.
ابتدا باید نسل اولیه را تولید کنیم . صفحه شطرنج 8 در 8 را در نظر بگیرید.
ستونها را با اعداد 0 تا 7 و سطرها را هم از 0 تا 7 مشخص می کنیم .
برای تولید حالات ( کروموزومها ) اولیه بصورت تصادفی وزیرها را در ستونهای مختلف قرار می دهیم . باید در نظر داشت که وجود نسل اولیه با شرایط بهتر سرعت رسیدن به جواب را افزایش می دهد ( اصالت نزاد )
به همین خاطر وزیر i ام را در خانهی تصادفی در ستون i ام قرار می دهیم ( به جای اینکه هر مهره ای بتواند در هر خانه خالی قرار بگیرد ). با اینکار حداقل از برخورد ستونی وزیرها جلوگیری می شود.
توضیح بیشتر اینکه مثلا وزیر اول را بطور تصادفی در خانه های ستون اول که با 0 مشخص شده قرار می دهیم تا به اخر.
i=0.....7
حال باید این حالت را به نحوی کمی مدل کرد . چون در هر ستون یک وزیر قرار دادیم هر حالت را بوسیله ی رشته اعدادی که عدد k ام در این رشته شماره ی سطر وزیر موجود در ستون i ام را نشان می دهد. یعنی یک حالت که انتخاب کردیممی تواند بصورت زیر باشد:
67203422
که 6 شماره ی سطر 6 است که وزیر اول که شمارهی ستونش 0 است می باشد تا اخر.
فرض 4 حالت زیر به تصادف تولید شذه اند . این چهار حالت را بعنوان کروموزومهای اولیه بکار می گیریم.

1) 67203422
2) 70063354
3) 17522063
4)43602471

حال نوبت به تابع برازش fitness function می رسد. تابعی را که در نظر می گیریم تابعی است که برای هر حالت تعداد برخوردها ( تهدیدها )را در نظر می گیرد . هدف صفر کردن یا حداقل کردن این تابع است . پس احتمال انتخاب کروموزومی برای تولید نسل بیشتر است که مقدار محاسبه شده توسط تابع برازش برای ان کمتر باشد.( روشهای دیگری نیز برای انتخاب وجود دارد )
مقدار برازش برای حالات اولیه بصورت زیر می باشد :
( مقدار عدد برازش در جلوی هر کروموزوم( با رنگ قرمز )همان تعداد برخوردهای وزیران می باشد )

1) 67203420 6
2)70063354 8
3)17522063 2
4) 43602471 4



پس احتمالها بصورت زیر است :


p(3)>p(4)>p(1)>p(2

در اینجا کروموزومهایی را انتخاب می کنیم که برازندگی کمتری دارند.پس کروموزوم 3 برای crossover با کروموزومهای 4 و 1 انتخاب می شود .
نقطه ی ترکیب را بین ارقام 5 و 6 در نظر می گیریم.

4و3 :
5) 71 175220
6)63 436024

1و3:
7)20 175220
8)63 672034

حال نوبت به جهش می رسد .در جهش باید یکی از ژنها تغییر کند

. فرض کنید از بین کروموزومهای 5 تا 8 کروموزوم شماره ی 7 واز بین ژن چهارم از 2 به 3 جهش یابد . پس نسل ما شامل کروموزومهای زیر با امتیازات نشان داده شده می باشد :
( امتیازات تعداد برخوردها می باشد )
1)62203420 6
2)70063354 8
3)17522063 2
4)43602471 4
5)17522071 6
6)43602463 4
7)17532030 4
8)67203463 5

کروموزوم 3 کاندیدای خوبی برای ترکیب با 6و7 می باشد . ( فرض در این مرحله جهشی صورت نگیرد و نقطه ی اتصال بین ژنهای 1 و 2 باشد )

1) 67203420 6
2)70063354 8
3)17522063 2
4)43602471 4
5)17522071 6
6)43602463 4
7)17532030 4
8)67203463 5
9)13602463 2
10)47522063 2
11)17532030 4
12)17522063 2

کروموزومهای از 9 تا 12 را نسل جدید می گوییم.
بطور مشخص کروموزومهای تولید شده در نسل جدید به جواب مسئله نزدیکتر شده اند.با ادامه ی همین روند پس از چند مرحله به جواب مورد نظر خواهیم رسید.
پایان