الگوریتم ژنتیک یکی از الگوریتم های جست جوی تصادفیه که ایده اش رو از طبیعت گرفتن . از این الگوریتم برای حل مسائل بهینه سازی استفاده می کنن . حالا چرا می گن ایده اش از طبیعته ؟ چون مثل عملی که کروموزم ها عمل می کنن سازمان دهی می شن ، از ترکیب کروموزم ها بهتر نسل بهتری درست می شه حتی گاهی اوقات جهشایی هم اتفاق می افته که باز هم ممکنه نسل بهتری بدن . توی الگوریتم ژنتیک هم اول چند تا جواب به طور تصادفی
واسه مسئله پیدا می شه که هر کدوم از این جواب ها همون نقش کروموزوم ها رو این جا دارن . 
واسه انتخاب و ترکیب تو کروموزوم ها الگوریتم ژنتیک از چهار عملگر استفاده می کنه با اسم های زیر :
Fitness (شایستگی یا بهینگی ) : با این عملگر می گیم که یه جواب(کروموزوم ) میزان بهینه بودنش چه قدر هست مثلا تو مثال n وزیر تعداد برخوردای کمتری که بین وزیر ها انجام می شه رو می تونیم به عنوان مقدار بهینگی به حساب بیاریم . معلومه که هر چی بهینگی بیشتر باشه احتمال انتخاب اون کروموزوم هم بیشتره .
Selection (انتخاب ) : حالا موقع انتخاب واسه ترکیب رسیده و باید کروموزوم ها ی بهتر رو انتخاب کنیم ، این کار به عهده ی این عملگره . این عملگر از مقدارهایی که عملگر بدست آورده استفاده می کنه و اسه انتخاب . تعداد انتخاب شده ها باید با تعداد کروموزم های اولیه برابر باشه در واقع چند تا از اون کروموزوم ها ی اولیه ممکنه تکرار بشن . روش های مختلفی وجود داره واسه انتخاب مثلا روش رقابتی که تو اون دو تا از کروموزوم ها به طور تصادفی انتخاب می شن و مقدار بهینگی اونها با هم مقایسه می شه و بهتره انتخاب می شه ، این عمل به تعداد کروموزوم ها ی اولیه انجام می شه .
Crossover (انتقال از یه سیستم به سیستم دیگه یا ادغام) : تو این مرحله کروموزوم ها ی انتخاب شده رو با هم ترکیب می کنیم به امید بهتر بودن فرزندشون . چند روش واسه ترکیب وجود داره :
1.ادغام تک نقطه ای : تو این روش دو تا از کروموزوم ها انتخاب می شن و یه نقطه ای بین اونها به طور تصادفی انتخاب می شه و تمام ژن (مثلا یال های انتخاب شده تو مسئله ی کوتاهترین مسیر )های بعد از این نقطه ها رو تو دو تا کروموزوم جابه جا می کنیم .
2.ادغام دو نقطه ای : این روش خیلی شبیه روش قبله با این تفاوت که تو این روش دو تا نقطه انتخاب می شه و ژن های بین این دو نقطه تو دو تا کروموزوم جابه جا می شن .
3.ادغام با ماسک : تو این روش اومدن یه کار باحال کردن ، یه آرایه درست کردن باعناصری به تعداد ژن ها که هر عنصر می تونه 0 یا 1 باشه و به این آرایه ماسک می گن ، موقع ترکیب دو تا کروموزوم از این آرایه استفاده می کنن ، وقتی عنصر kام این آرایه صفره یعنی این که برای ژن kام فرزند از ژن kام کروموزوم اول استفاده کن واگه یک بود یعنی از کروموزوم دوم انتخاب کن .
Mutation (جهش) : این عملگر از یه روش معمول استفاده می کنه اون هم تغییر دادن یک یا چند تا از ژن ها به طور تصادفیه .
این روش های ادغام کلی بودن و باید روی اونها یه تغییراتی انجام داد .
این عملگرها تا وقتی که به یه جواب خوب برسیم به طور چرخشی ادامه دارن. از این الگوریتم ژنتیک تو هوش مصنوعی خیلی استفاده می شه و قسمت مهم اون ژنتیکه .
فکرکنم تا همین جا بس باشه چون ممکنه فهم این مطلب واسه غیر کامپیوتری ها و اونایی که کتاب طراحی الگوریتم ها رو پاس نکردن سنگین باشه .فقط این که مثال n-وزیر این الگوریتم رو بصورت لینک می ذارم ضمن اینکه این مطلب هم منبع اصلیش همین لینکه.
لیست کل یادداشت های وبلاگ
جستجو در وبلاگ
عضویت در خبرنامه وبلاگ
آمار بازدیدکنندگان
