متاهیوریستیک‌ها؛ جست‌وجو بین اکتشاف و بهره‌برداری

ایده فضای جواب، تابع هدف، جمعیت و Differential Evolution را با ریاضیات ساده و پیوند با یک پروژه واقعی دنبال می‌کنیم.

بهینه‌سازی و متاهیوریستیک‌هامتوسط

هدف یادگیری

مفهوم فضای جست‌وجو و موازنه exploration/exploitation را بفهمید و رابطه پایه Differential Evolution را تفسیر کنید.

پیش‌نیازها

مبانی بهینه‌سازی
احتمال مقدماتی

فضای جواب

هر مقدار ممکن از متغیرهای تصمیم یک جواب کاندید است. الگوریتم باید در فضای مجاز دنبال جواب‌هایی با مقدار بهتر تابع هدف بگردد.

جواب بهینه

x^*\in\arg\min_{x\in\Omega}f(x)

ایده Genetic Algorithm

در GA چند جواب هم‌زمان نگهداری می‌شوند. انتخاب، crossover و mutation جمعیت را تغییر می‌دهند و evaluation کیفیت هر جواب را می‌سنجد.

selection: انتخاب والدها
crossover: ترکیب اطلاعات
mutation: ایجاد تنوع
evaluation: سنجش تابع هدف

ایده Differential Evolution

DE از اختلاف اعضای جمعیت برای ساخت یک بردار جدید استفاده می‌کند؛ این اختلاف نوعی جهت حرکت در فضای جواب فراهم می‌کند.

بردار جهش در DE

v = x_{r_{1}} + F (x_{r_{2}} - x_{r_{3}})

سپس بردار آزمایشی با بردار هدف ترکیب و بر اساس مقدار تابع هدف انتخاب می‌شود.

ارتباط با پروژه بهینه‌سازی پویا

در Event-Driven Metaheuristic Optimization خود مسئله نیز در طول زمان تغییر می‌کند. بنابراین سؤال فقط پیدا کردن جواب خوب نیست؛ باید بررسی کنیم آیا می‌توان از state قبلی برای سازگاری با مسئله جدید استفاده کرد.

تمرین

برای یک مسئله دوبعدی تابع هدف تعریف کنید.
سه بردار ساده انتخاب کنید و mutant vector را محاسبه کنید.
توضیح دهید چرا warm-start باید با benchmark سنجیده شود و یک حکم عمومی نیست.

پروژه مرتبط

Event-Driven Metaheuristic Optimization

پروژه واقعی برای GA، DE، بهینه‌سازی پویا و مقایسه restart با warm-start.

باز کردن منبع

راهکارهای مرتبط

مدل‌سازی، الگوریتم و بهینه‌سازی

یک مسئله بهینه‌سازی دشوار دارید؟

می‌توان مدل را مشخص کرد و سپس مناسب‌ترین روش جست‌وجو را بررسی کرد.

گفت‌وگو درباره مسئله