آموزش الگوریتم فرا ابتکاری
1- تعریف بهینه‌سازی:
بهینه‌سازی جزء لاینفک زندگی انسان بوده و در تمامی موقعیت‌ها آدمی به دنبال انتخاب بهترین گزینه بوده است. به عبارت دیگر، بهینه سازی به معنای جستجوی مناسب‌ترین جواب برای یافتن کارآمدترین روش با بیشترین راندمان می باشد. این فرآیند از دید نظریه پردازان شامل سه مرحله است: (1) مدلسازی مساله براساس روابط موجود (2)یافتن تابع هدف و یا معیار سنجش عملکرد مناسب (3) و روش بهینه‌سازی.
براساس شواهد تاریخی میتوان اذعان نمود با پیدایش محاسبات ریاضی بر پایه مشتق و تلاش ریاضی دانانی همچون نیوتن، برنولی، لاگرانژ، کوشی و گیبس، روش‌های بهینه سازی شروع به رشد نمود. این گروه از مسائل عمدتا با برنامه‌نویسی ریاضی قابل حل بود و طی دهه‌های آتی اشکال غیرخطی به آن اضافه شده است.
گروه جدیدی با نام الگوریتم‌های فرابتکاری[1] از اواسط 1940 با هدف گسترش فضای جستجو و الهام گرفته از پدیده های طبیعی توانست نمای جدید از قدرت و کیفیت این روش‌ها را نمایان سازد. کلمه metaheuristics ترکیبی از دو لغت یونانی قدیمی است؛ فعل heuriskein به معنای “جستجو کردن” و پیشوند metha به معنای “فراتر، گسترده”. با این تفاسیر تعریف مشخصی از فرابتکاری در ادبیات یافت نمیشود ولی Osman & Laport [1] آنرا اینگونه تعریف می کنند: ” روش فرابتکاری یک فرآیند تکرارشونده هوشمندانه جهت کاوش و بهره برداری فضای جستجو است که از استراتژی‌های یادگیری جهت ساختن اطلاعات و یافتن نزدیک ترین جواب به نقطه بهینه مساله استفاده میکند.”
2- تاریخچه پیدایش و تکامل روش‌های فرابتکاری:
Sorensen [2] سیر پیدایش و تحول روش‌های فرابتکاری را به پنج بازه زمانی تقسیم کرده است:
1- دوره پیش از تولد ( قبل از 1940) که اصول بنیادی و روابط ریاضی مورد نیاز در حال شکل گیری بود اما نام یا اثری از الگوریتم وجود نداشت.
2- دوره آغازین ( بین سال‌های 1940 تا 1980) که روابط اولیه کشف شد.
3- دوره روش محور (بین 1980 – 2000 میلادی) که جهش حقیقی و پیدایش بسیاری از روش ها در این برهه تاریخی به وقوع پیوست.
4- دوره کاربردی( از 2000 تا کنون) و گسترش استفاده از روش ها در علوم مختلف.
و در آخر دوره (5) که از دیدگاه سورنزن ” دوره علمی” نام گذاری شده، جامه ای علمی بر قامت این هنر میپوشاند.
پیش از سال 2000 میلادی، مشهورترین الگوریتم‌های تکامل محور[2] مانند(استراتژی تکامل (evolutionary strategies) – الگوریتم ژنتیک (Genetic algorithm) و تفاضل تکاملی (differential evolution) ) و الگوریتم‌های مسیر محور[3] مانند ( تپه‌نوردی (hill climbing) – بازپخت شبیه‌سازی شده (simulated annealing)- جستجوی تابو (Tabu search)- جستجوی محلی تکرارشونده (iterative local search)- جستجوی همسایگی متغیر(Variable neighborhood search)) ابداع شدند. تولد الگوریتم‌های شناخته شده برپایه ازدحام (ازدحام ذرات Particle Swarm Optimization و کلونی مورچگان Ant Colony Optimization) تقریبا در دهه 2000 رخ داد و از آن زمان به بعد دوران طلایی رشد و نمو روابط بهینه‌سازی چندهدفه (Multi-Objective optimization)، فراابتکاری هیبریدی (Hybrid metaheuristics)، فرابتکاری موازی (Parallel metaheuristics ) و محاسبات ابری (Cloud computing) شناخته شده است. همزمان با جهش روش‌های الگوریتم فرابتکاری، روابطی بر پایه پدیده‌های طبیعی به وجود آمد که در جدول زیر اسامی انگلیسی آنها نوشته شده است.
| Collective Decision Optimization Algorithm (CDOA) | Harmony search (HS) |
| Charged System search (CSS) | Artificial Bee Colony (ABC) algorithm |
| Ray Optimization (RO) | Big Bang Big Crunch (BB-BC) |
| Dolphin Echolocation (DE) optimization | Teaching learning-based optimization (TLBO) |
| Tug-of-War Optimization (TWO) algorithm | Imperialist competitive algorithm (ICA) |
| Colliding Bodies Optimization (CBO) | Cuckoo search (CS) |
| Water Evaporation Optimization (WEO) | Krill Herd (KH) |
| Vibrating Particles System (VPS) | Gray Wolf Optimization (GWO) |
| Cyclical Parthenogenesis Algorithm (CPA) | Nephron Algorithm Optimization (NAO) |
| Thermal Exchange Optimization (TEO) | Salp Swarm algorithm (SSA) |
| Lightning Attachment Procedure Optimization (LAPO) | Grasshopper Optimization Algorithm (GOA) |
3- کاربرد الگوریتم‌های فرابتکاری:
به لطف کامپیوتر و ابزارهای هوشمند، پیشرفت‌های چشمگیری در زمینه مدلسازی، تحلیل و طراحی دقیق مسائل دنیای حقیقی به وقوع پیوسته است. تقریبا همه پدیده‌های دنیای واقعی را می توان به عنوان مسائل بهینه سازی پیچیده در نظر گرفت. این پیچیدگی نشات گرفته از ذات مسائل است. به عبارتی اگر فضای حل مساله گسسته یا پیوسته، خطی با غیرخطی و یا دارای محدودیت‌های طراحی غیرمحدب[4] باشد، ماهیت پیچیدگی روش براساس آنها شکل میگیرد. از سویی دیگر، تمامی ویژگی های مثبت در ابزارهای فرابتکاری متمرکز شده و آنها را به اولین و بهترین گزینه برای بهینه سازی تبدیل کرده است. به همین دلیل در تمامی گرایش‌های علمی از مهندسی گرفته تا اقتصاد و پزشکی از آن استفاده میکنند. به عنوان مثال در شاخه مهندسی هوا فضا جهت طراحی بهینه هواپیما و فضاپیماها، در مهندسی نرم‌افزار برای کمینه سازی زمان و هزینه محاسباتی، در مهندسی عمران جهت طراحی سازه‌هایی با کمترین وزن و بیشترین پایداری و در مهندسی الکترونیک جهت ایجاد مقرون به صرفه ترین شبکه از این الگوریتم‌ها استفاده میشود.
4- معرفی MATLAB و شناخت ابزار محاسباتی الگوریتم‌های فرابتکاری:
نرم افزار متلب (MATLAB = Matrix Laboratory) محصول شرکت MathWorks و قویترین ابزار محاسباتی، برنامه‌نویسی و تجسمی برای نوشتن مدلسازی ریاضی در یک محیط دوستانه برای کاربر (User friendly) است. اساس این نرم‌افزار ثبت داده‌ها در قالب ماتریس و یا بردار است. از آنجایی که روند کلی الگوریتم‌های فراابتکاری تکرار حلقه‌های پیچیده و اصلاح مقادیر ماتریس است، نرم افزار متلب به ابزار محبوب بهینه‌سازان تبدیل شده است. نمونه‌های استاندارد مدلسازی روش‌های فرابتکاری در متلب شامل سه بخش می‌شوند. در فاز اول، متغیرهای الگوریتم و یا همان متغیرهای طراحی مساله تعریف شده و حدود جواب مشخص میشود. در فاز دوم که بدنه اصلی برنامه نام دارد، طی چرخه تکرارشونده گزینه های جدید جواب ایجاد شده تا به معیار توقف برسد. لازم به ذکر است که معیار توقف نیز انواع مختلفی داشته که متداول‌ترین آنها تعداد تکرار الگوریتم و یا تخمین تابع هدف میتواند باشد. در فاز سوم، نتایج و جواب بهینه مساله نشان داده میشود. کدنویسی در ساده ترین شکل خود میتواند خط به خط نوشته و پردازش شود و یا از ابزارهایی مانند تابع (function)، جدول (table)، ساختار(structure)، اجزا منطقی (logical states)، رشته (string) و … استفاده شود که حالت پیشرفته برنامه‌نویسی بوده و میتواند به پیچیدگی‌های مساله بیافزاید.
[1] Metaheuristics methods
[2] Evolutionary-based metaheuristics
[3] Trajectory-based metaheuristics
[4] Nonconvex design constraints