در این پست میخوایم در خصوص الگوریتم های فراابتکاری هیبریدی و نیز نحوه هیبرید کردن الگوریتم‌های فراابتکاری رو بهتون یاد بدیم چیزی که خیلی لازمتون میشه واسه نوشتن مقاله و کد کردن مدل‌هاتون

  • اول بگم هیبرید کردن چه معنایی داره؟

هیبرید کردن یعنی مخلوط کردن دو یا چند الگوریتم و استفاده از خصوصیات دو یا چند الگوریتم فراابتکاری برای رسیدن به جواب بهتر، همون طور که میدونین  که فراابتکاری ها فقط میتونن جوابهای نزدیک به بهینه رو پیدا کنن نه خود بهینه رو .پس ما جواب هاشون رو بهبود بدیم چون جای بهبود  دارن!!!

توی این پست و پست های بعدی میخوایم یاد بگیریم الگوریتم SA  رو بهبود بدیم. پس اونو با الگوریتم ژنتیکGA هیبرید میزنیم

بهتره اول یه مروری روی الگوریتم شبیه سازی تبرید یا همون SA خودمون انجام بدیم :

در روش شبیه‌سازی تبرید، هر نقطه S در فضای جست و جو مشابه یک حالت از سیستم فیزیکی است و تابع (E(S

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

اگر جواب همسایه  بهتر از جواب فعلی باشد، الگوریتم آن را به عنوان جواب فعلی قرار می‌دهد( به آن حرکت می‌کند)، در غیر اینصورت، الگوریتم جواب را با احتمال (exp(-ΔE/Tبه عنوان جواب فعلی می‌پذیرد. در این رابطه ΔE تفاوت بین تابع هدف جواب فعلی و جواب همسایه است و  یک پارامتر به نام دما است. در هر دما چندین تکرار اجرا می‌شود و سپس دما به آرامی کاهش داده می‌شود. در گام‌های اولیه دما خیلی بالا قرار داده می‌شود تا احتمال بیشتری برای پذیرش جواب‌های بدتر وجود داشته باشد.با کاهش تدریجی دما، در گام‌های پایانی احتمال کمتری برای پذیرش جواب‌های بدتر وجود داشته باشد و بنابراین الگوریتم به سمت یک جواب خوب همگرا می‌شود. در هر مرحله الگوریتم تبرید شبیه‌سازی، چند حالت را درهمسایگی حالت کنونی S در نظر می‌گیرد و به طور احتمالی تصمیم می‌گیرد که سیستم را از حالت S منتقل ‌کند یا در همین حالت باقی بماند.

حال میخوایم یادبگیریم چه جوری الگوریتم SA را با الگوریتم GA  یا همون ژنتیک هیبرید کنیم :

تفاوت اصلی الگوریتم SAGA ارائه­ شده در این پست با الگوریتم SA کلاسیک، اضافه شدن عملگر تولیدمثل[۱] به انتهای هر دما است. در الگوریتم SA کلاسیک، در انتهای تکرارهای هر دما، یک جواب انتخاب می­شود و سپس دما با نرخ مشخصی کاهش می­یابد و جواب منتخب به گام/دمای بعدی الگوریتم منتقل می­شود. اما، در الگوریتم SAGA، تکرارهای هر دما را دو مرتبه انجام می­دهیم و در پایان هر دما دو جواب منتخب می­شوند.

سپس بین این دو جواب علمگر تولیدمثل رخ می­دهد و دو جواب جدید (فرزند) از آن‌ها حاصل می‌شود، نهایتأ بین چهار جواب موجود در انتهای هر دما (دو جواب نهایی منتخب­شده و دو فرزند آن‌ها) رقابت صورت می­گیرد و دو جواب بهتر به دمای بعد الگوریتم منتقل می­شوند و الگوریتم برای این دو جواب ادامه می­یابد و مجددأ این روند تا دمای نهایی ادامه می­یابد. گرچه واضح است الگوریتم SAGA زمان حل[۲] بیشتری را نسبت به الگوریتم SA کلاسیک صرف می­کند، اما در این روش جستجوی محلی[۳] در هر دما صورت می­گیرد که سبب می­گردد بخش بیشتری از فضای حل مسئله بررسی گردد و احتمال گیر کردن در جواب بهینه محلی[۴] کاهش یابد. بعلاوه، عملگر تولیدمثل که بین دو جواب/والد منتخب در انتهای هر دما صورت می­گیرد، سبب می­گردد ویژگی­های برتر این دو جواب با هم ادغام شوند و احتمال تولید یک جواب/فرزند بهتر در انتهای هر دما، برای شروع دمای جدید، افزایش می­یابد.

توی پست های بعدی این آموزش همراه ما باشین تا بتونین از این الگوریتم های هیبرید بیشتر و بهتر استفاده کنین.

[۱] Crossover

[۲] Solution Time

[۳] Local Search

[۴] Local Optimum