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

الگوریتم های فراابتکاری یا فراتکاملی یا فرااکتشافی نوعی از الگوریتم های تصادفی هستند که برای یافتن پاسخ بهینه به کار می روند.
روش ها و الگوریتم های بهینه سازی به دو دسته الگوریتمهای دقیق ( exact ) و الگوریتم های تقریبی ( approximate algorithms ) تقسیم بندی می شوند. الگوریتم های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی کافی ندارند و زمان اجرای آن ها متناسب با ابعاد مسائل به صورت نمایی افزایش می یابد. الگوریتم های تقریبی قادر به یافتن جواب های خوب ( نزدیک به بهینه ) در زمان حل کوتاه برای مسائل بهینه سازی سخت هستند. الگوریتم های تقریبی نیز به سه دسته الگوریتم های ابتکاری ( heuristic ) و فراابتکاری ( meta - heuristic ) و فوق ابتکاری ( hyper heuristic ) بخش بندی می شوند. دو مشکل اصلی الگوریتم های ابتکاری، گیر افتادن آن ها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است. الگوریتم های فراابتکاری برای حل این مشکلات الگوریتم های ابتکاری ارائه شده اند. در واقع الگوریتم های فراابتکاری، یکی از انواع الگوریتم های بهینه سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده ای از مسائل را دارند. [ ۱] [ ۲] رده های گوناگونی از این نوع الگوریتم در دهه های اخیر توسعه یافته است[ ۳] که همه این ها زیر مجموعه الگوریتم فراابتکاری می باشند.
معیارهای مختلفی می تواند برای طبقه بندی الگوریتم های فراابتکاری استفاده شود:[ ۴]
• مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتم های مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می دهند، در حالی که در الگوریتم های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب ها در نظر گرفته می شوند.
• الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم های فراابتکاری از طبیعت الهام گرفته شده اند، در این میان برخی از الگوریتم های فراابتکاری نیز از طبیعت الهام گرفته نشده اند.
• با حافظه و بدون حافظه: برخی از الگوریتم های فراابتکاری فاقد حافظه می باشند، به این معنا که، این نوع الگوریتم ها از اطلاعات بدست آمده در حین جستجو استفاده نمی کنند ( به طور مثال تبرید شبیه سازی شده ) . این در حالی است که در برخی از الگوریتم های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می کند.
• قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می کند. اما در الگوریتم های فراابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می گیرد.