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

در چند دهه اخیر، دسته‌ای از الگوریتم‌های تقریبی توسعه داده شده‌اند که سعی دارند با ترکیب اصول اولیه روش‌های ابتکاری (هیوریستیک^[1] ) روشی را برای جستجوی مؤثر و کارای فضای جواب پیدا کنند. امروزه این روش‌ها به روش‌های فرا ابتکاری (متاهیوریستیک^[2] ) مشهورند. اصطلاح متاهیوریستیک اولین بار توسط Glover در سال 1993 و به هنگام معرفی روش جستجوی ممنوع ^[3] به عنوان یک روش ابتکاری جدید به کار برده شد.
پیش از این، روش‌های فرا ابتکاری، روش‌های ابتکاری نوین^[4] نامیده می‌شدند. الگوریتم‌های تکاملی^[5]  نظیر الگوریتم ژنتیک^[6]، الگوریتم بهینه‌سازی مورچگان^[7]، روش شبیه‌سازی تبرید^[8]، جستجوی ممنوع و شبکه‌های عصبی مصنوعی^[9] نمونه‌هایی از این روش‌ها می‌باشند.
تا به امروز تعریف مشخص و جامعی از اصطلاح متاهیوریستیک یا فرا ابتکاری صورت نگرفته است و تعاریف مختلفی برای این اصطلاح ارائه شده است. اما به طور خلاصه می‌توان مشخصات اصلی روش‌های فرا ابتکاری را به صورت زیر بیان نمود.

• برخلاف روش‌های ابتکاری، هدف اصلی این روش‌ها، جستجوی مؤثر و کارای فضای جواب به جای یافتن صرف جواب‌های بهینه یا نزدیک بهینه می‌باشد؛
• روش‌های فرا ابتکاری سیاست‌ها و راهکارهایی هستند که فرآیند جستجو را هدایت می‌کنند؛
• روش‌های فرا ابتکاری تقریبی بوده و اغلب غیر قطعی(تصادفی) می‌باشند؛
• این روش‌ها ممکن است با استفاده از مکانیزم‌هایی از به دام افتادن فرآیند جستجو در بهینه‌های موضعی جلوگیری کنند؛
• الگوریتم‌های فرا ابتکاری، برخلاف روش‌های ابتکاری وابسته به نوع مساله نیستند، به عبارت دیگر می‌توان آنها را برای حل طیف گسترده‌ای از مسائل بهینه‌سازی مورد استفاده قرار داد؛
• روش‌های فرا ابتکاری پیشرفته‌تر، از تجربیات و اطلاعات به دست آمده در طول فرآیند جستجو به شکل حافظه برای هدایت جستجو به نواحی پرامیدتر فضای جواب استفاده می‌کنند؛

به طور خلاصه می‌توان گفت که الگوریتم‌های فرا ابتکاری، راهکارهای پیشرفته و کلی جستجو می‌باشند و گام‌ها و معیارهایی را پیشنهاد می‌کنند که در فرار از دام بهینه‌های موضعی بسیار مؤثر هستند. عامل مهم در این روش‌ها، تعادل پویا بین استراتژی‌های تنوع بخشی^[10] و پرقدرت سازی^[11] است. تنوع بخشی به جستجوی گسترده در فضای جواب اشاره دارد و پرقدرت سازی به معنی بهره‌برداری از تجربیات به دست آمده در فرآیند جستجو و تمرکز بر نواحی پرامیدتر فضای جواب می‌باشد.
بنابراین با ایجاد تعادل پویا بین این دو استراتژی از یک طرف، جستجو به سمت محدوده‌هایی از فضای جواب سوق داده می‌شود که جواب‌های بهتری در آنها یافت شده است و از طرف دیگر موجب عدم اتلاف زمان بیشتر در بخشی از فضای جواب می‌شود که پیش از این بررسی شده و یا شامل جواب‌های نامرغوب‌تری است.
یکی از شاخص‌های تقسیم‌بندی الگوریتم‌های فرا ابتکاری، تعداد جواب‌هایی است که آنها در هر تکرار، تولید و مورد بررسی قرار می‌دهند. بر این اساس روش‌های فر ا ابتکاری به دو گروه روش‌های تک نقطه‌ای^[12] و روش‌های جمعیتی^[13]  تقسیم‌بندی می‌شوند که در اینجا شرح مختصری از هر کدام از این روش‌ها آورده می‌شود.

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

معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتم‌های فراابتکاری استفاده شود.
-1مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتم‌های مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند    .
 -2الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم‌های فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم‌های فراابتکاری نیز از طبیعت الهام گرفته نشده اند   .
3-با حافظه و بدون حافظه: برخی از الگوریتم‌های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم‌های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
-4قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فراابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.

الگوریتم های مبتنی بر یک جواب

-الگوریتم تبرید شبیه سازی شده simulated annealing
-جست وجوی ممنوعه tabu search
-جست و جوی حریصانهGRASP search 
-جست و جوی همسایگی متغیرvariable neighborhood search 
-جست و جوی محلی هدایت شدهguided local search 
-جست و جوی محلی تکرار شوندهinterated local search 

الگوریتم های مبتنی بر جمعیت

-الگوریتم ژنتیک Genetic Algorithm
-الگوریتم رقابت استعماری Imperialist Competitive Algorithm
-الگوریتم بهینه سازی کلونی مورچگان Ant Colony Optimization Algorithm 
-الگوریتم کلونی زنبور عسل Bee Colony Algorithm
-الگوریتم کرم شب تاب Firefly Algorithm
-الگوریتم سیتم ایمنی مصنوعی Artificial Immune System Algorithm
-الگوریتم جستجوی هارمونی Harmony Search Algorithm

-الگوریتم بهینه سازی تجمعی ذرات Particle Swarm Optimization Algorithm

در ادامه می توانید فایل های آموزشی مربوط به الگوریتم های فراابتکاری را دانلود کنید

PDF1

PDF2

PDF3

Sources:

Papyrus

Aryamodir

wikipedia