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