اصول و تعاریف اولیه الگوریتم های ژنتیک

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

واژگان پایه :

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

• جمعیت :(Population): یک زیر مجموعه از همه راه حل‌های ( رمز شده) ممکن برای مسائله مورد مطالعه.جمعیت برای یک الگوریتم ژنتیک مشابه با جمعیت برای انسان است بجز اینکه بجای وجود  انسان ها ما راه حل‌های کاندید را داریم که وجود بشر را نشان می دهند.

• کروموزوم ها (Chromosomes) یک کروموزوم یک راه حل برای مسائله مورد مطالعه است.

• ژن :(Gene) ژن موقعیت عنصری از یک کروموزم است

• آلل (Allele) : مقداری که یک ژن برای یک کروموزم خاص دریافت می‌کند.

• ژنوتیپ(Genotype) : ژنوتیپ یک جمعیت در فضای محاسبات است.در فضای محاسبات ، راه حل‌ها به شیوه ای که به راحتی قابل فهم و مدیریت بوسیله یک سیستم محاسباتی باشند نمایش داده می‌شوند.

• فنوتیپ (Phenotype) :فنوتیپ  جمعیتی در فضای راه حل یک  دنیای واقعی موجود می‌باشد که در آن راه حل‌ها به شیوه ای نمایش داده می‌شوند که آن‌ها در موقعیت های دنیای واقعی نمایش داده شده‌اند.

• رمز گشایی و رمز گذاری (Decoding and Encoding) : در مسائل ساده فضای  فنوتیپ و ژنتیپ مشابه هستند.اگرچه در اغلب موارد  فضای  فنوتیپ و ژنتیپ با یکدیگر متفاوت هستند.رمز گشایی فرآیند انتقال یک راه حل از فضای ژنوتیپ به فضای فنوتیپ، در حالی که رمزگذاری فرآیند  انتقال از فضای فنوتیپ به ژنوتیپ می‌باشد.رمزگذاری باید به قدر کافی سریع باشد این فرآیند مکرراً در خلال محاسبه مقدار fitness (سازگاری) انجاممی‌شود.

برای مثال در مسائله کوله پشتی 0/1 (0/1 Knapsack Problem).فضای فنوتیپ شامل راه حل‌هایی است که فقط شامل تعداد آیتم هایی است که از آیتم های موجد برداشته شده اند برداشته شده‌اند.به هر حال ، در فضای ژنوتیپ مثال ذکر شده در بالا می‌تواند به عنوان یک رشته دودویی با طول n نمایش داده شود ( که در اینجا n تعداد آیتم هاست). صفر (۰) در موقعیت x نمایش می‌دهد که x امین (x th) آیتم برداشته شده است در حالیکه وجود 1 برعکس آن را نشان می دهد( x امین آیتم برداشته نشده است).این نمونه‌ای است که در آن فضای ژنوتیپ و فنوتیپ با یکدیگری متفاوت هستند.

• تابع سازگاری (Fitness Function ) : یک تعریف ساده از  تابع سازگاری تابعی است که راه حل را به عنوان ورودی دریافت می نماید و راه حل مناسب را به عنوان خروجی تولید می‌کند.در بعضی از موارد ، تابع سازگاری و تابع هدف یکسان هستند و در بعضی دیگر بر اساس مسائله ممکن است که متفاوت باشند.

• عملگر ژنتیکی(Genetic Operators ) : عملگرهای ژنتیکی ترکیب ژنتیکی فرزندان را تغییر می‌دهند .برای مثال می‌توان به عملگر های انتخاب(selection) ، جهش(mutation)  ،متقاطع (crossover)و غیره نام برد.

ساختار پایه الگوریتم های ژنتیک
ساختار پایه یک الگوریتم ژنتیک به شرح ذیل است :
از یک جمعیت اولیه شروع می‌کنیم ( که می‌تواند به صورت تصادفی یا شیوه‌های ابتکاری دیگر تولید شده باشد) .والدینی را از این جمعیت برای زاد و ولد انتخاب می‌کنیم.عملگرهای crossover و mutation (جهش) را روی والدین برای تولید نمودن فرزندان جدید اعمال می‌کنیم و سرانجام این فرزندان اشخاص موجود را در جمعیت جایگزین نموده و فرآیند تکرار می‌شود. در این روش الگوریتم های ژنتیک سعی می‌کنند تا شیوه تکامل بشری را تا حدی تقلید کند.

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

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best