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

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

  • Genetic Algorithm
  • Genetic Programming
  • Evolutionary Strategies
  • Evolutionary Programming
  • Differential Evolution
  • Cultural Evolution
  • Co-evolution

الگوریتم های تکاملی نیز همانند الگوریتم های متاهیوریستیکی ، به شکل تصادفی اما هدایت شده در فضای حالت مسئله حرکت می کنند. با توجه به نظریه داروین پیاده سازی یک الگوریتم تکاملی طی مراحل زیر انجام می پذیرد :

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

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

Procedure Genetic
  Generate Population
    LOOP
      Calculate Fitness Value of Each Chromosome
      Select some Chromosomes
      Crossover the Selected Chromosomes
      Mutate the Chromosomes
    Replace Current Population with Offspring
  UNTIL stop criterion is not satisfied
END