الگوریتم ژنتیک

 

الگوریتم ژنتیک تکنیک جستجویی برای یافتن راه حل تقریبی برای مسائل بهینه ­سازی و جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم ­های تکاملی است که از تکنیک ­های مانند بازترکیب (Crossover) و جهش (Mutation) استفاده می­کند. این الگوریتم اولین بار توسط جان هلند معرفی شد. در واقع این الگوریتم از اصول انتخاب طبیعی داروین برای یافتن راه­ حل بهینه استفاده می­کند. مختصراً گفته می‌شود که الگوریتم ژنتیکیک تکنیک برنامه ‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. الگوریتم ژنتیک تکامل ژنی را مدل می­کند و برای حل گستره­ وسیعی از مسائل از جمله تولید مورد آزمون بکار می­رود. بصورت کلی الگوریتم ژنتیک از یک جمعیت اولیه کار خود را آغاز می­کند. در جمعیت اولیه مقدار برازش هر کروموزوم توسط تابع برازش (Fitness Function) محاسبه می­شود و آنهایی که به پاسخ بهینه نزدیک ­تر هستند با احتمال بیشتری به عنوان والد برای تولید کروموزوم های فرزند در نسل بعد انتخاب می­شوند. برای تولید نسل جدید روی تعدادی از کروموزوم های نسل قبل عملیات بازترکیب و جهش انجام می­شود و کروموزوم های جدید تولید می­شوند. بقیه­ جمعیت نسل با کروموزوم های نسل قبل پر می­شوند. این فرایند آنقدر ادامه می­یابد تا پاسخ مورد نظر پیدا شود یا اینکه تعداد دفعات اجرای برنامه به یک حد نصاب برسد. قالب اصلی الگوریتم ژنتیک بدین صورت است:

  1. initialize (population)
  2. fitness(population)
  3. repeat
    • selection(population)
    • crossover(population)
    • mutation(population)
    • fitness(population)
  4. until best individual is good enough

قالب کلی الگوریتم ژنتیک

جمعیت اولیه

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

 

تابع برازش

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

 

انتخاب

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

  • چرخ دوار
  • انتخاب مسابقه ­ای
  • انتخاب Boltzmann
  • انتخاب رتبه­ای
  • انتخاب حالت پایدار

 

عملگر باز ترکیب

از عملگر بازترکیب (Crossover) برای تولید کروموزوم­ های نسل جدید از روی والدهای نسل جاری استفاده می­شود. عملگر بازترکیب انواع زیادی دارد. در اینجا به دو نوع بازترکیب که نسبت به بقیه پرکاربردترند اشاره می­شود:

  • تک نقطه­ای- توسط یک نقطه­ تصادفی در هر دو کروموزوم والد، کروموزوم­ ها به دو قسمت تقسیم می­شوند. سپس بخش اول یکی از والدها با بخش دوم والد دیگر جابجا می­شود.
  • دو نقطه­ای- دو نقطه روی کروموزوم­ های والد مشخص می­شود و بخشی آن قسمت از کروموزوم­ ها که بین دو نقطه هستند باهم جابجا می­شوند.

 

عملگر جهش

عملگر جهش (Mutation) برای کاربردهای خاص توسعه یافته اند. هدف از بکارگیری عملگر جهش پرهیز از افتادن در پاسخ ­های بهینه­ محلی است. در عمل جهش یک یا چند ژن بصورت تصادفی یا غیر­تصادفی انتخاب شده و مقدار آن بخش انتخاب شده تغییر می­کند. مقداردهی جدید می­تواند تصادفی باشد و یا طبق روش خاصی تعیین گردد.