مقاله بررسی آشنایی با الگوریتم ژنتیک

مقاله بررسی آشنایی با الگوریتم ژنتیک در 16 صفحه قابل ویرایش


بخشی از متن:
الگوریتم ژنتیک از روشهای جستجوی مستقیم اتفاقی است که بر پایه اصول انتخاب طبیعی و بقای اصلح قرار دارد. اصطلاحات بکار رفته در الگوریتم ژنتیک کاملاً شبیه واژگان ژنتیک طبیعی است و حتی تشابه نزدیکی بین عناصر این دو وجود دارد. این روش، اولین بار توسط جان هلند از دانشگاه میشیگان در سال 1975 پیشنهاد شد.
ساختار اصلی که توسط الگوریتم پردازش می‌شود، رشته ( کرموزم ) است. یک رشته زنجیره ای از تعدادی کد ( اغلب کدهایی دودیی ) با طول معلوم است. بیتهای رشته (صفر یا 1 در یک رشته دودویی) معادل ژنهای طبیعی‌اند. هر کدام بیانگر یک متغیر ( مشابه یک ویژگی در ژنتیک طبیعی همانند رنگ چشم ) و هر مصداق خاصی از کد به طور مستقیم یا غیر مستقیم بیانگر مقدار مشخصی از آن متغیر است ( معادل مثلاً چشم آبی ).

شکل 1- رشته در الگوریتم ژنتیک شامل پارامترها بصورت کد دودویی است.
کدهای یک رشته به اندازه تعداد متغیرهاست، پس یک رشته اساسا بیانگر یک جواب ممکن است. با الگوریتم ژنتیک ایجاد یک جمعیت اولیه از رشته‌ها از طریق انتخاب تصادفی مقادیر بیتهای رشته آغاز می‌شود. تعداد رشته‌ها (کروموزمها) در جمعیت، اندازه جمعیت نامیده می‌شود. اندازه جمعیت در ابتدا توسط کاربر تعیین می‌شود یا اینکه بر طبق قاعده‌ای که بعدا خواهد آمد، توسط کامپیوتر تعیین می‌شود و در طی جستجو، ثابت نگه داشته می‌شود.
برازندگی یک رشته (جواب ممکن ) توسط تابع محاسبه می‌شود. چون الگوریتم ژنتیک دنبال ماکزیمم کردن برازندگی جوابهای ممکن است، در یک مسأله ماکزیمم سازی، برازندگی برابر مقدار تابع هدف محاسبه شده برای مقادیر خاص پارامتر که هر رشته بیان می‌کند، می‌باشد. یعنی تابع برازندگی همان تابع هدف است اما در مسأله مینیمم سازی برازندگی با افزایش تابع هدف کاهش می‌یابد. یک راه برای جبران آن تعریف تابع برازندگی به صورت :
1- تابع هدف- مقدار ثابت = تابع برازندگی
که مقدار ثابت به اندازه کافی بزرگ انتخاب می‌شود تا از منفی شدن برازندگی جلوگیری شود. یک مقدار متداول برای این مقدار ثابت، مجموع و ماکزیمم تابع هدف درهر نسل است.
روش دیگرمعکوس کردن تابع هدف می‌باشد.