اُپتی‌کد، مرجع کدهای الگوریتم فرا ابتکاری مسائل ریاضی

الگوریتم‌های فرا ابتکاری

الگوریتم‌های فرا ابتکاری (Metaheuristic Algorithms) جزو روش‌های بهینه‌سازی تقریبی محسوب می‌شوند.کلمه فرا ابتكاري برای اولین بار در مقاله گلاور در هنگام معرفي الگوريتم جستجوي ممنوعه، عنوان شد. الگوريتم‌هاي فرا ابتكاري استراتژي‌هاي كلي جستجو هستند و مي‌توانند به عنوان راهكار يافتنجواب در مورد طيف وسيعي از مسائل استفاده شوند. الگوریتم‌های فراابتکاری، به طور قابل ملاحظه‌ای توانایی دست‌یابی به جواب‌های بهینه یا نزدیک بهینه را برای مسائل سخت افزایش می‌دهند. ویژگی مشترک این دسته از الگوریتم‌ها، اینست که از یک‌سری سازوکارهایی برای خروج از نقاط بهینه محلی استفاده می‌کنند و در دام این محل‌ها نمی‌افتند.

الگوریتم‌های فرا ابتکاری ویژگی‌های دیگری نیز دارند. احتمالی بودن ماهیت این روش‌ها، از به دام افتادن آن‌ها در نقاط بهینه محلی جلوگیری می‌کند. همچنین، علی‌رغم اینکه این روش‌ها بیشتر در مسائل گسسته کاربرد دارند، در حل مسائل پیوسته نیز می‌توان از آن‌ها بهره جست. اغلب این روش‌ها، از دل مفاهیمی چون فیزیک، زیست‌شناسی و جانورشناسی الهام گرفته شده‌اند. براي استفاده از هر روش فرا ابتكاري در حل يك مسئله خاص، بايستی قوانين موجود در مسئله و پارامترهاي روش به نحوي طراحي شوند كه بهترين استفاده ممكن از الگوریتم مدنظر در حل مسئله به دست آيد. به فرآیند تنظيم و طراحي روند و نحوه مقدارگيري پارامترهاي روش‌هاي فرا ابتكاري، تنظيم سازي مي گويند.

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

1- روش مبتنی بر یک جواب: برخی الگوریتم‌ها مانند ، شبیه‌سازی تبرید، جست‌وجوی ممنوعه، جست‌وجوی محلی تکرار شونده، جست‌وجوی همسایگی متغیر و جست‌وجوی محلی هدایت شده یک پاسخ یکتا را در نظر می‌گیرند و با طی فرآیندهایی سعی در بهبود آن پاسخ دارند.

2- روش مبتنی بر جمعیت: در مقابل، برخی الگوریتم‌ها یک جمعیتی از پاسخ‌های اولیه را در نظر می‌گیرند و در هر تکرار تا رسیدن به شراتط خاتمه، با اعمال برخی عملیات بر روی این پاسخ‌ها، به سمت دست‌یابی به پاسخ‌های بهتر می‌روند. الگوریتم‌هایی همچون الگوریتم‌های تکاملی (ژنتیک)، جست‌وجوی پراکنده، ازدحام ذرات، کلونی زنبورعسل و کلونی مورچگان جزو این دسته از الگوریتم‌ها هستند.

در دهه اخیر روش‌های جدیدی که مبتنی بر جمعیت حیوانات هستند، ابداع شده‌اند که از مطرح‌ترین آن‌ها می‌توان به الگوریتم گرگ خاکستری، الگوریتم وال، کرم شب‌تاب، جهش قورباغه، الگوریتم ملخ، جست‌وجوی فاخته و الگوریتم خفاش اشاره کرد. ایده اصلی این روش‌ها اغلب مبتنی بر فرآیند یافتن غذا و یا ادامه نسل بهتر این جانوران است.

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

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

Metaheuristics- From Design to Implementation- El-Ghazali Talbi