آموزش ویدیویی الگوریتم بهینه سازی ژنتیک
در این پست آموزش الگوریتم ژنتیک به زبان ساده در قالب یک فایل ویدیویی و توضیحات زیر ارائه شده است. امیدوارم که دوستان با مطالعه پست و دیدن ویدیو بتوانند بهره ی کامل را از این آموزش بگیرند.
جهت دریافت فایل پاورپوینت ارائه فوق از لینک میتوانید تهیه کنید.
هدف در بهینه سازی
در بهینه سازی ها هدف یافتن نقاط ماکزیمم و مینیمم کلی است.
انواع روش های بهینه سازی
- روش های بهینه سازی ریاضیاتی مثل روشهای خطی و روش لاگرانژ
- روش جستجوی سراسری (جستجوی تمام فضای سرچ )
- روش های فرا ابتکاری مثل الگوریتم ژنتیک و PSO و …
چرا الگوریتم های فراابتکاری؟
عوامل تاثیرگذار در پیچیدگی محاسباتی مدل های تصمیم گیری:
1- غیرخطی بودن توابع هدف یا محدودیت ها
2- گسسته بودن فضای حل مسئله
3- اندازه مسئله
روش های دقیق:
در شرایط فوق قادر به پیدا کردن جواب بهینه در زمان قابل قبولی نیستند.
هدف روش های فراابتکاری:
پیدا کردن بهترین جواب ممکن نزدیک به بهینه ( در زمان قابل قبول)
الگوریتم های فرا ابتکاری
در سی سال گذشته، نوع جدیدی از الگوریتم های تقریب ظهور یافته اند که اساساً هدف از آنها ترکیب روش های ابتکاری در چارچوبهای کلان تر به منظور کاوش کارا و اثربخش فضای جستجو می باشد. امروزه از این رو شها با عنوان روشهای فرا ابتکاری(متاهیوریستیک) نام برده می شود.این واژه را اولین بار” گلوور” در سال 1986 به کار برد که از ترکیب دو واژه یونانی “متا” و “هیوریستیک” ساخته شده است. پیشوند “متا” به معنای فراتر یا در سطحی بالاتر است و”هیوریستیک” به معنای یافتن است.یک روش فرا ابتکاری، در حقیقت، یک روش ابتکاری برای حل یک طبقه بسیار عمومی از مسائل است و ترکیبی کارآمد از توابع هدف یا روش های ابتکاری مبتنی بر توابع هدف می باشد
معرفی الگوریتم ژنتیک
üالگوریتم ژنتیک، الهامی از علم ژنتیک و نظریة تکامل داروین است و بر اساس بقای برترینها یا انتخاب طبیعی استوار است. یک کاربرد متداول الگوریتم ژنتیک، استفاده از آن بعنوان تابع بهینه کننده است. الگوریتم ژنتیک ابزار سودمندی دربازشناسی الگو، انتخاب ویژگی،درك تصویرو یادگیری ماشینی است .در الگوریتم های ژنتیکی، نحوه تکامل ژنتیکی موجودات زنده شبیه سازی میشود. این الگوریتم ها با الهام از روند تکاملی طبیعت مسائل را حل می نمایند . یعنی مانند طبیعت یک جمعیت از موجودات را تشکیل می دهند و با اعمالی بر روی این مجموعه به یک مجموعه بهینه و یا موجود بهینه دست می یابند.با توجه به خصوصیات خاص خودشان به خوبی از عهده حل مسائلی که نیاز به بهینه سازی دارند بر می آیند.
مثال : تکامل زرافه
زرافه ها گردن بلندی دارند
در گذشته در بین زرافه ها آن هایی که کمی گردنشان بلندتر بوه توانسه اند از شاخه های بلند تر گیاهان تغزیه کنند، در حالی که آن هایی که گردن کوتاه تری داشته اند غذای کمتری خورده اند.آن هایی که گردن بلندتری داشته اند شانس بیشتری برای زنده و سالم ماندن داشته اند چرا که تغذیه بهتری داشته اند ویژگی های مطلوب در طی نسل های مختلف گسترش میابد. امروزه گونه های تکامل یافته زرافه با گردن بلند زندگی میکنند.
اندازه ی مناسب پاها
همین مسئله در طی زمان در خصوص پاهای زرافه نیز وجود داشته و با گذشت زمان بهترین اندازه ی پاهای زرافه ایجاد شده، چرا که پای خیلی بلند باعث شکار شدن و از بین رفتن آن ها میشده است.
فلوچارت تکامل گونه ها در الگوریتم ژنتیک
فلوچارت کلی الگوریتیم بهینه سازی ژنتیک
ایجاد جمعیت اولیه
در ابتدا به صورت رندوم در کل فضای سرچ یک سری جمعیت اولیه ایجاد می شود.
تبدیل اعداد
در این قسمت اعداد که به صورت دهدهی هستند تبدیل به اعداد در مبنای 2 میشوند.
بدست آوردن ارزش هر تابع
نحوه ی انتخاب بهترین ها برای نسل بعدی
1- انتخاب قطعی Deterministic Selection
2- انتخاب رنک Rank Selection
3- انتخاب یکنواخت Uniform Selection
4- انتخاب ترنومنتSelection Tournament
5- انتخابSelection Roulette wheel
انتخاب قطعی Deterministic Selection
در این انتخاب ابتدا مقادیر تابع بر اساس بهترین به بدترین مرتب و بهترین ها برای نسل بعد انتخاب میشوند.
انتخاب ترنومنت Tournament
در این انتخاب ابتدا داده ها به صورت رندوم به گروه های مختلفی تقسیم میشوند، بعد در هر گروه بهترین انتخاب میشود.
انتخاب یکنواخت
در این نوع انتخاب شانس انتخاب تمامی داده ها برای نسل بعدی به یک نسبت است. این نوع انتخاب سرعت همگرایی را بسیار کم میکند ولی شانس جستجوی تمام فضا را بالا می برد. معمولا از این نوع انتخاب در مواردی که تابع دارای تعداد لوکال خیلی زیادی است و ممکن است داده ها در لوکال ها گیر کند استفاده میشود. آن هم در مسائلی که هزینه ی محاسبات بتابع بالا نباشید.
انتخاب رنک Rank Selection
در این روش ابتدا مقادیر از بدترین به بهترین امتیاز 1 تا n را میگیرند. یعنی انکه بهترین است بالاترین امتیاز و بعد آنکه کمترین است امتیاز 1 را میگیرد و در هنگام انتخاب شانس هر داده که امتیاز بالاتری دارد بیشتر است.
انتخاب چرخ رولت
در این روش ابتدا مقادیر از بدترین به بهترین امتیاز 1 تا n را میگیرند. یعنی انکه بهترین است بالاترین امتیاز و بعد آنکه کمترین است امتیاز 1 را میگیرد و در هنگام انتخاب شانس هر داده که امتیاز بالاتری دارد بیشتر است.
عملیات کراس آور
اعداد در مبنای ده بعد از تبدیل به مبنای دو به صورت زیر به صورت تک نقطه ای عملیات کراس آور روی آن ها انجام می شود. سپس خروجی مجددا به منبای ده بر میگردد تا تابع هدف ان محاسبه شود.
انواع کراس آور
در کراس اور یک نقطه ای یک شماره ی رندوم انتخاب و از همانجا کروموزوم بریده شده و با هم تعویض میشود.در کراس اور چند نقطه ای ، چند نقطه ی رندوم ایجاد و از محل شماره های رندوم کروموزوم ها بریده و با هم تعویض میشود.
چرا کراس آور؟
در حقیقت کراس آور حکم لوکال سرچ را دارد چون ماهیت کروموزوم ها را عوض نمیکند بلکه کروموزوم ها را ترکیب میکند بنابراین در اکثر مواقع وقتی کراس اور بین دو والد اتفاق می افتد فرزندانی که ایجاد میشوند شبیه دو والد هستند شاید کمی بهتر باشند. در مسائل بهینه سازی کراس آور به معنی جستجوی اطراف نقاط رندوم قبلی است.
عملیات جهش
در عملیات جهش کروموزوم مورد نظر که رشته ای از صفر و یک هست، یکی از ژن ها به طور رندوم اگر یک است به صفر و اگر صفر است به یک تبدیل میشود.
چرا جهش؟
در جهش به صورت رندوم یکی از سلول های کروموزم اگر یک باشد به صفر و اگر صفر باشد به یک تبدیل می شود. عملیات جهش اگر در سلول های بالایی کروموزوم اتفاق بیفتد ماهیت عدد را عوض کرده و حکم گلوبال سرچ را دارد. در بهینه سازی معمولا بعد از جهش روی کروموزوم ها سرچ از یک ناحیه به یک ناحیه ی دیگر جابجا میشود. در اصل عملیات جهش باعث میشود که فضای سرچ بیشتری جستجو شود و داده ها در فضای کلی بیشتر جستجو کنند.
نحوه ی انتخاب والدین نسل بعدی
والدین نسل بعدی از انتخاب بهترین ها ی والدین و فرزندان در نسل قبلی بدست می آیند. این فرایند در شکل به طور کامل نشان داده شده است.
الیتیزم (نخبه گرایی) در الگوریتم ژنتیک
فرستادن بهترین ها به نسل بعد بدون شرکت در مرحله انتخاب
در برخی از موارد در الگوریتم ژنتیک برای اینکه سرعت همگرایی بالا برود، بهترین های هر نسل بدون اینکه در عملیات انتخاب شرکت کنند مستقیم به نسل بعدی راه پیدا میکنند. این کار باعث میشود که سرعت همگرایی الگوریتم افزایش یابد. اما عیبی که دارد این است که گاهی نخبه ها بهترین نیستند و حکم مقادیر لوکال خوب را دارند نه گلوبال خوب و الگوریتم توی لوکال ها ترپ میشود.
تعیین پارامترهای الگوریتم ژنتیک
در الگوریتم ژنتیک باید پارامترهای مربوط به کراس آور و جهش و نخبه گرایی تعیین شود. مثلا از کل والدین چند درصد جهش ایجاد شود. چند درصد کراس آور ایجاد شود و چند درصد بدون طی مراحل انتخاب (نخبه گرایی) به نسل بعد باید راه پیدا کنند.
