صفحه قبلی – صفحه بعدی

مفاهیم

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

اصطلاحات پایه

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

  • جمعیت (Population) – یک زیرمجموعه از همه راه حل های ممکن (کدبندی شده) برای مسئله داده شده است.
  • کروموزوم – یک کروموزوم یکی از راه حل های مساله است.
  • ژن – ژن یک عنصر یا همان کوچکترین واحد از یک کروموزوم است.
  • Allele – ارزش یا مقدار یک ژن برای یک کروموزوم خاص است.

Terminology

  • Genotype – جمعیت در فضای محاسبات است. در فضای محاسبات، راه حل ها به شیوه ای ارائه می شود که می تواند با استفاده از یک سیستم محاسباتی به راحتی قابل فهم و دستکاری باشد.
  • Phenotype – جمعيت در فضاي دنیای واقعي است که در آن راه حل ها به گونه اي ارائه مي شوند که در شرايط دنيای واقعي نمايش داده مي شوند.
  • رمز گشایی (Decoding) و رمزگذاری (Encoding) – برای مسائل ساده، فضاهای فنوتیپ و ژنوتیپ یکسان هستند. با این حال در اکثر موارد فضاهای فنوتیپ و ژنوتیپ متفاوت هستند. رمزگشایی یک فرایند تبدیل یک راه حل از ژنوتیپ به فنوتیپ است، در حالی که رمزگذاری فرآیند تبدیل از فنوتیپ به فضای ژنوتیپ است. سرعت رمزگشایی باید بالا باشد زیرا در GA محاسبات تابع تناسب بارها و بارها انجام می شود.
    به عنوان مثال، در مساله کوله پشتی 0/1. فضای فنوتیپ شامل راه حل هایی می شود که فقط شماره آیتم هایی را که باید برداشته شوند در خود نگه می دارد. با این حال، در فضای ژنوتیپ می توان آن را به صورت یک رشته باینری به طول n (که n تعداد آیتم هاست) نشان داد.  مقدار 0 در موقعیت یا ژن x نشان می دهد که آیتم x برداشته شده  و مقدار 1 نشان دهنده برداشته نشدن آن است. این تفاوتی است که فضاهای ژنوتیپ و فنوتیپ دارند.

Phenotype and Genotype Space

  • تابع تناسب (Fitness Function) – تابع تناسب یک تابع است که راه حل را به عنوان ورودی می گیرد و ارزش یا میزان مناسب بودن راه حل را به عنوان خروجی تولید می کند. در برخی موارد، تابع تناسب و تابع هدف ممکن است یکسان باشد، در حالی که در سایر موارد ممکن است بر اساس نوع مساله متفاوت باشد.
  • عملگرهای ژنتیکی – این عملگرها ترکیب ژنتیکی فرزندان را تغییر می دهد و شامل  عملیات برش یا تقاطع (CrossOver)، جهش (Mutation)، انتخاب (Selection) و .. می باشد.

ساختارپایه

ساختار پایه یک GA به شرح زیر است:
ما با یک جمعیت اولیه (که ممکن است به صورت تصادفی یا توسط سایر روشهای اکتشافی تولید شود) شروع می کنیم، والدین را از این جمعیت برای جفت گیری انتخاب می کنیم. عملگرهای برش و جهش را برای تولید فرزندان جدید (Off-Spring) بر روی والدین اعمال می کنیم و در نهایت این فرزندان جایگزین افراد موجود در جمعیت می شوند و همین روند تکرار می شود. به این ترتیب، الگوریتم های ژنتیک در واقع تلاش می کنند تا حدی روند تکاملی انسان را تقلید کنند. هر یک از این مراحل به عنوان یک بخش جداگانه در ادامه این دوره آموزشی بیان خواهد شد.
Basic Structure


صفحه قبلی
– صفحه بعدی

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *