تبلیغات
طراحی الگوریتم - ساختمان داده - هوش مصنوعی - نظریه - شرح الگوریتم ژنتیک

پنجشنبه 26 مهر 1386 - 07:10 ق.ظ


در پست قبلی دوست عزیزمان مسئله n وزیر را با استفاده از الگوریتم  ژنتیک که یک الگوریتم هوشمند است در اختیارتان قرار داد.در این پست من سعی می کنم شرح کامل این الگوریتم را در اختیارتان قرار دهم.

 امید است این مطلب در کنار مطلب دوست عزیزمان مجموعه کاملی را در اختیار تان قرار دهد.

الگوریتم ژنتیک ( Genetic Algorithm )

الگوریتم های ژنتیک یکی از الگوریتم های جستجوی تصادفی است که ایده آن برگرفته از طبیعت می باشد . الگوریتم های ژنتیک در حل مسائل بهینه سازی کاربرد فراوانی دارند . به عنوان مثال می توان به مسئله فروشنده دوره گرد اشاره کرد . در طبیعت از ترکیب کروموزوم های بهتر ، نسل های بهتری پدید می آیند . در این بین گاهی اوقات جهش هایی نیز در کروموزوم ها روی می دهد که ممکن است باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل می کند .

در الگوریتم های ژنتیک ابتدا به طور تصادفی یا الگوریتمیک ، چندین جواب برای مسئله تولید می کنیم . این مجموعه جواب را جمعیت اولیه می نامیم . هر جواب را یک کروموزوم می نامیم . سپس با استفاده از عملگرهای الگوریتم ژنتیک پس از انتخاب کروموزوم های بهتر ، کروموزوم ها را باهم ترکیب کرده و جهشی در آنها ایجاد می کنیم . در نهایت نیز جمعیت فعلی را با جمعیت جدیدی که از ترکیب و جهش در کروموزوم ها حاصل می شود ، ترکیب می کنیم . موارد فوق را با جزئیات بیشتری مورد بررسی قرار می دهیم :

نحوه نمایش

برای استفاده از الگوریتم ژنتیک در حل مسائل باید روشی برای نشان دادن جواب مساله داشته باشیم . در بیشتر مواقع از رشته های بیتی یا آرایه ها استفاده می کنیم . به عنوان مثال برای نشان دادن یک تور در مساله فروشنده دوره گرد می توان از یک آرایه یک بعدی استفاده کرد . بدین صورت که آرایه به تعداد شهرها دارای عنصر خواهد بود . مقادیر موجود در آرایه بیانگر ترتیب شهر ها خواهد بود .

برای انتخاب ، ترکیب و ایجاد جهش در کروموزوم ها عملگرهای مختلفی وجود دارد اما غالبا الگوریتم های ژنتیک از چهار عملگر زیر برای حل مسائل استفاده می کنند :

  1. Fitness  (برازش )
  2. Selection (  انتخاب)
  3. Crossover (ادغام)
  4. (جهش)    Mutation

 برازش 

با استفاده از این عملگر ، میزان بهینگی هر کروموزوم را تعیین می کنیم . به عنوان مثال در مسئله فروشنده دوره گرد ، تورهای با مسافت کمتر بهینه تر هستند . و یا در مسئله n-وزیر تعداد برخوردهای کمتر باعث بهینگی بیشتر کروموزوم می شود . بنابراین می توان نتیجه گرفت که عملگر Fitness برای هر کروموزوم احتمالی را نسبت می دهد که این احتمال ، همان احتمال ترکیب شدن کروموزم برای تولید نسل های آینده را نشان می دهد . بدیهی است که کروموزوم های بهینه تر شانس بیشتری برای ترکیب با دیگر کروموزوم ها خواهند داشت . بنابراین احتمالی که به آنها نیز نسبت می دهیم باید بیشتر باشد 

 انتخاب

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

روش های مختلفی برای انتخاب کروموزوم ها وجود دارد . یکی از معمولترین روش ها روش رقابتی می باشد . در روش رقابتی دو یا چند کروموزوم را به طور تصادفی انتخاب کرده و از میان آنها کروموزومی که Fitness آن بهتر از دیگر کروموزوم های انتخاب شده باشد ، انتخاب می شود . این عمل به تعداد کروموزوم های جمعیت اولیه انجام می شود .

محصول نهایی عملگر انتخاب جمعیت میانی می باشد که از این جمعیت در مراحل بعدی استفاده خواهیم کرد .

 ادغام

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

ادغام کروموزوم ها نیز روش های مختلفی دارد که از این میان سه روش از محبوبیت بیشتری برخوردارند :

  1. ادغام تک نقطه ای

  2. ادغام دو نقطه ای

  3. ادغام توسط ماسک

ادغام تک نقطه ای

در این روش از میان کروموزوم های جمعیت میانی دو کروموزوم را انتخاب می کنیم . سپس به طور تصادفی نقطه ای از کروموزوم را انتخاب کرده و تمام ژن های بعد از این نقطه را در دو کروموزوم تعویض می کنیم .

ادغام دو نقطه ای

در این روش نیز از میان کروموزوم های جمعیت میانی دو کروموزوم را انتخاب می کنیم . سپس به طور تصادفی دو نقطه از کروموزوم را انتخاب کرده و تمام ژن های بین این دو نقطه را در دو کروموزوم تعویض می کنیم .

ادغام توسط ماسک

در این روش از یک ماسک برای ادغام استفاده می کنیم . بدین صورت که آرایه را که به تعداد ژن ها دارای عنصر است ایجاد می کنیم . عناصر این آرایه فقط می تواند مقادیر صفر یا یک1 بپذیرد . عناصر آرایه ماسک را به طور تصادفی مقدار دهی می کنیم . حال با استفاده از این ماسک دو کروموزوم را ادغام می کنیم . مقدار صفر در آرایه ماسک نشان می دهد که ژن باید از کروموزوم اول انتخاب شود . مقدار یک نیز در آرایه ماسک مشخص می کند که ژن باید از کروموزوم دوم انتخاب شود .

روش های یاد شده ، روشهایی کلی می باشند و گاهی اوقات باید تغییراتی در آنها ایجاد کنیم .

 

جهش

عملگر جهش هنگامی که بر روی کروموزمومی اعمال می شود باعث بروز جهش در آن کروموزوم می شود . روش معمول برای جهش تغییر دادن یک یا چند ژن از کروموزوم بطور تصادفی می باشد .

حل مساله با استفاده از الگوریتم های ژنتیک

برای حل مساله با استفاده از الگوریتم های ژنتیک ، ابتدا جمعیت اولیه ای شامل K کروموزوم تولید می کنیم . هر کروموزوم نشان دهنده جواب مساله خواهد بود . سپس با استفاده از عملگر برازش میزان مطلوب بودن هر کرموزوم را محاسبه کرده و در مرحله بعد با استفاده از مقادیر محاسبه شده در مرحله برازش کروموزوم هایی را انتخاب کرده و جمعیت میانی را تولید می کنیم . تعداد کروموزوم های جمعیت میانی نیز K کروموزوم خواهد بود . در نهایت نیز عملگر جهش بر روی کروموزوم های جمعیت میانی اعمال می شود . پس از اعمال عملگر جهش ، جمعیت میانی جایگزین جمعیت اولیه می شود . دوباره مراحل برازش ، ادغام و جهش و جایگزینی بر روی آن انجام می شود . شبه کد زیر نحوه انجام مراحل فوق را نشان می دهد :

Population = GeneratePopulation(K) 

For I = 1 to MaxIterations

 Fitness(Population)

 If any of chromosomes is optimal Then

  Break

 Offspring =  Crossover(Population)

 Mutate(Offspring)

EndFor

توابع Fitness ، Crossover و Mutate نیز با توجه به روش های شرح داده شده پیاده سازی می شوند .

 

 

 


ارسال شده در

[ | دیدگاه ها : دیدگاه ]

[حسام ح | لینک ]
نوشته های پیشین ...