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

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

روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتم‌های تقریبی (approximate algorithms) تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی سخت کارایی کافی ندارند و زمان اجرای آن‌ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش‌بندی می‌شوند. دو مشکل اصلی الگوریتم‌های ابتکاری، گیر افتادن آن‌ها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است. الگوریتم‌های فراابتکاری برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند.الگوریتم‌های بهینه‌سازی فراابتکاری (همراه با کاربردهایی در مهندسی برق)/تالیف دکتر فرشاد مریخ بیات؛ انتشارات جهاد دانشگاهی؛ 1393الگوریتم‌های بهینه‌سازی فراابتکاری/تالیف مسعود یقینی، محمد رحیم اخوان کاظم‌زاده. جهاد دانشگاهی واحد صنعتی امیر کبیر -1 رده‌های گوناگونی از این نوع الگوریتم در دهه‌های اخیر توسعه یافته‌استبهینه‌سازی ترکیبی و الگوریتم‌های فرا ابتکاری /تالیف کورش عشقی؛ مهدی کریمی نسب انتشارات آذرین مهر ؛1391که همه این‌ها زیر مجموعه الگوریتم فراابتکاری می‌باشند. 

 دسته‌بندی الگوریتم‌های فراابتکاری 
معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتم‌های فراابتکاری استفاده شود:Talbi, El-Ghazali. Metaheuristics: From Design to Impelementation, John Wiley and sons 2009
 مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتم‌های مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند.
 الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم‌های فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم‌های فراابتکاری نیز از طبیعت الهام گرفته نشده‌اند.
 با حافظه و بدون حافظه: برخی از الگوریتم‌های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به‌طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم‌های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
 قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فراابتکاری احتمالی نظیر تبرید شبیه‌سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.

 الگوریتم‌های فراابتکاری بر پایه جمعیت 
از الگوریتم‌های شناخته شده فراابتکاری بر پایه جمعیت می‌توان الگوریتم‌های تکاملیEiben, A.E. , Smith, J.E. , Introduction to Evolutionary Computiong, Springer 2003 (الگوریتم ژنتیک، برنامه‌ریزی ژنتیک، ...)، بهینه‌سازی کلونی مورچگان،Dorigo, M. , and Stützle, T. , Ant Colony Optimization, MIT Press, Cambridge, MA, 2004 کلونی زنبورها،Yonezawa, Y. , and Kikuchi, T. , Ecological algorithm for optimal ordering used by collective honey bee behavior, In 7th International Symposium on Micro Machine and Human Science, pp. 249–256 1996 روش بهینه‌سازی ازدحام ذرات، الگوریتم بهینه‌سازی جنگل، الگوریتم بهینه سازی Battle Royal، الگوریتم قهرمانی در لیگهای ورزشی، بهینه‌سازی ملهم از فیزیک نور، الگوریتم ریشه-پاجوش و الگوریتم چکه آبهای هوشمند را نام برد.

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

اخیرا، به نظر می رسد روند توسعه جدیدی از الگوریتم ها با الهام گرفتن از علم دیرینه شناسی و علوم باستان آغاز شده است. این الگوریتم ها که در دسته جدید الهام گرفته از دوران باستان، قرار می گیرند با بررسی ویژگی های دوران باستان سعی می کنند نوعی بهینه سازی ایجاد کنند https://doi.org/10.1007/s12065-020-00451-3.  

 الگوریتم‌های متداول فراابتکاری مبتنی بر یک جواب 
از الگوریتم‌های متداول فراابتکاری مبتنی بر یک جواب می‌توان الگوریتم جستجوی ممنوعهGlover F. and Laguna, M. , Tabu Search, Kluwer Academic Publishers, 1997simulated annealing, Science, Vol. 220, No. 4598, pp. 671–680, 1983 و الگوریتم تبرید شبیه‌سازی شدهKirkpatrick, S. , Gelatt, C. D. , and Vecchi, M. P. , Optimization by simulated annealing, Science, Vol. 220, No. 4598, pp. 671–680, 1983 را نام برد.

 پیاده‌سازی الگوریتم‌های فراابتکاری 
فرایند طراحی و پیاده‌سازی الگوریتم‌های فراابتکاری دارای سه مرحلهٔ متوالی است که هر کدام از آن‌ها دارای گام‌های مختلفی هستند. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحلهٔ ۱ آماده‌سازی است که در آن باید شناخت دقیقی از مسئله‌ای که می‌خواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فراابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسئله به‌طور واضح و شفاف مشخص شود. مرحلهٔ بعدی، ساخت نام دارد. مهم‌ترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه‌گیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن پیاده‌سازی الگوریتم طراحی شده در مرحلهٔ قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.Yaghini, Masoud; Akhavan, Rahim, DIMMA: A Design and Implementation Methodology for Metaheuristic Algorithms - A Perspective from Software Development, International Journal of Applied Metaheuristic Computing, Vol.1, No.4, pp. 57-74, 2010.

 جستارهای وابسته 
 هوش گروهی
 الگوریتم چکه آب‌های هوشمند

 منابع 

 پیوند به بیرون 
 فهرست الگوریتم های فرا ابتکاری (متاهیورستیک) از سال 1983 تا 2020

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

رده:بهینه‌سازی ریاضی
رده:تحقیق در عملیات
رده:ریاضیات کاربردی