الگوریتم زنتیک، یک روش جستجوی هوشمند و احتمالی است که فرایند تکامل تدریجی (evolution process) داروین را با در نظر گرفتن جمعیتی(Population) از جوابها و به کارگیری عملگرهای ژنتیک، تقاطع(crossover) و جهش(mutation)، در هر توالد (reproduction) شبیه سازی می کند.

     بنابراین الگوریتم های GA نیز مانند الگوریتمهای بهینه سازی مورچگان
(Ant Colony Optimization) برخلاف سایر متاهیوریستیکها همچون روش جستجوی ممنوع(Tabu Search) و شبیه سازی حرارتی(Simulated Annealing) که تنها روی یک جواب عمل می کنند، با جمعیتی از جوابها سرکار دارد. از جمله تفاوتهایی که این روش با ACO دارد این است که در ACO از الگوریتم های سازنده(Constructive)استفاده می شود در حالی که در GA  از الگوریتم های جستجوی محلی(Local search) استفاده می گردد.

   در GA هر جواب در جمعیت طبق معیاری از برازندگی(fitness measure) ارزیابی شده و به جوابهای با درجه برازندگی بهتر فرصت هایی برای توالد داده می شود و در این مرحله جوابهای فرزند(Offsprings یا Childs) تولید شده و با جوابهای فاقد برازندگی(unfit) در جمعیت جیگزین می شوند. بعبارت دیگر ترکیب جوابهای موجود بواسطه فرایند توالد جوابهای جدیدی تولید می کند و این چرخه ارزیابی(evaluation)، انتخاب(selection)، و توالد(reproduction)، تا زمانی که به یک جواب رضایت بخش برسیم تکرار می گردد.

الگوریتم ژنتیک نخستین بار در اوایل دهه 1970 توسط جان هلند(John Holland) و دانشجویانش در دانشگاه میشیگان توسعه داده شده است[1]، که الگوریتم ساده ژنتیک(SGA) نامیده شد و به صورت زیر بود :

Simple Genetic Algorithm()

{

    Initialize population;

    Evaluate population;

    while termination criterion not reached

     {

         Select solutions for next population;

         Perform crossover and mutation;

         Evaluate population;

      } 

   }

سپس اقای گلدبرگ(از شاگردان هلند) توانست در پایان نامه خود مساله پیچیده خطوط لوله گاز را حل کند.

 در واقع الگوریتم های ژنتیک با یک جمعیتی از جوابها سرکار داشته و مایل به دستکاری جوابها به روشی ساده هستند. در یک GA، یک جواب بالقوه برای یک مساله به صورت مجموعه ای از پارامترها که ژن(gene) نامیده می شوند، نمایش داده می شود. این پارامترها با یکدیگر متحد شده و رشته ای از مقادیر را که کروموزوم(Chromosome) نامیده می شود، تشکیل می دهند.

  در یک GA کدگذاری(یک نوع طرز نمایش بر اساس رشته ها) اهمیت بسزایی دارد. همچنین عملگرهای عملی و سودمند برای تقاطع(جابجایی) و جهش و سایر عملگرهای خاص مساله تعریف شوند بطوریکه کاملا صریح و شامل کمترین محاسبات باشند.

لازم به ذکر است که GA و بقیه متاهیوریستیک ها به معنای واقعی کلمه الگوریتم نیستند. بلکه یک چارچوب الگوریتمی کلی برای دسته بزرگی از مسائل بهینه سازی هستند که می توان با استفاده از آنها برای مسائل مختلف الگوریتمی را نوشت.

منبع رضا علائی