الگوریتمهای فراابتکاری یا فراتکاملی یا فرااکتشافی نوعی از الگوریتمهای تصادفی هستند که برای یافتن پاسخ بهینه به کار میروند.
روشها و الگوریتمهای بهینهسازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتمهای تقریبی (approximate algorithms) تقسیمبندی میشوند. الگوریتمهای دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینهسازی سخت کارایی کافی ندارند و زمان اجرای آنها متناسب با ابعاد مسائل به صورت نمایی افزایش مییابد. الگوریتمهای تقریبی قادر به یافتن جوابهای خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینهسازی سخت هستند. الگوریتمهای تقریبی نیز به سه دسته الگوریتمهای ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخشبندی میشوند. دو مشکل اصلی الگوریتمهای ابتکاری، گیر افتادن آنها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است. الگوریتمهای فراابتکاری برای حل این مشکلات الگوریتمهای ابتکاری ارائه شدهاند. در واقع الگوریتمهای فراابتکاری، یکی از انواع الگوریتمهای بهینهسازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گستردهای از مسائل را دارند.[۱][۲] ردههای گوناگونی از این نوع الگوریتم در دهههای اخیر توسعه یافتهاست[۳]که همه اینها زیر مجموعه الگوریتم فراابتکاری میباشند.
دستهبندی الگوریتمهای فراابتکاری
معیارهای مختلفی میتواند برای طبقهبندی الگوریتمهای فراابتکاری استفاده شود:[۴]
- مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتمهای مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر میدهند، در حالی که در الگوریتمهای مبتنی بر جمعیت در حین جستجو، یک جمعیت از جوابها در نظر گرفته میشوند.
- الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتمهای فراابتکاری از طبیعت الهام گرفته شدهاند، در این میان برخی از الگوریتمهای فراابتکاری نیز از طبیعت الهام گرفته نشدهاند.
- با حافظه و بدون حافظه: برخی از الگوریتمهای فراابتکاری فاقد حافظه میباشند، به این معنا که، این نوع الگوریتمها از اطلاعات بدست آمده در حین جستجو استفاده نمیکنند (بهطور مثال تبرید شبیهسازی شده). این در حالی است که در برخی از الگوریتمهای فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده میکنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره میکند.
- قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل میکند. اما در الگوریتمهای فراابتکاری احتمالی نظیر تبرید شبیهسازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار میگیرد.
الگوریتمهای فراابتکاری بر پایه جمعیت
از الگوریتمهای شناخته شده فراابتکاری بر پایه جمعیت میتوان الگوریتمهای تکاملی[۵] (الگوریتم ژنتیک، برنامهریزی ژنتیک، ...)، بهینهسازی کلونی مورچگان،[۶] کلونی زنبورها،[۷] روش بهینهسازی ازدحام ذرات، الگوریتم بهینهسازی جنگل[۸]، الگوریتم بهینه سازی Battle Royal[۹]، الگوریتم قهرمانی در لیگهای ورزشی، بهینهسازی ملهم از فیزیک نور، الگوریتم ریشه-پاجوش و الگوریتم چکه آبهای هوشمند را نام برد.
در سالهای اخیر الگوریتمهای فرابتکاری جدیدی با توجه به موجودات زنده موجود در طبیعت (الهام گرفته از طبیعت) توسعه داده شدهاند که از معروفترین آنها میتوان به الگوریتم بهینه سازی گرگ خاکستری ، الگوریتم بهینه سازی سنجاقک ، الگوریتم بهینه سازی گرده افشانی گل ها، الگوریتم بهینه سازی نهنگ یا وال ، الگوریتم بهینه سازی ملخ، و الگوریتم بهینه سازی کلونی پنگوئن های امپراتور[۱۰] [۱۱] نام برد.
اخیرا، به نظر می رسد روند توسعه جدیدی از الگوریتم ها با الهام گرفتن از علم دیرینه شناسی و علوم باستان آغاز شده است. این الگوریتم ها که در دسته جدید الهام گرفته از دوران باستان، قرار می گیرند با بررسی ویژگی های دوران باستان سعی می کنند نوعی بهینه سازی ایجاد کنند [۱۲].
الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب
از الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب میتوان الگوریتم جستجوی ممنوعه[۱۳] و الگوریتم تبرید شبیهسازی شده[۱۴] را نام برد.
پیادهسازی الگوریتمهای فراابتکاری
فرایند طراحی و پیادهسازی الگوریتمهای فراابتکاری دارای سه مرحلهٔ متوالی است که هر کدام از آنها دارای گامهای مختلفی هستند. در هر گام فعالیتهایی باید انجام شود تا آن گام کامل شود. مرحلهٔ ۱ آمادهسازی است که در آن باید شناخت دقیقی از مسئلهای که میخواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فراابتکاری برای آن باید با توجه به روشهای حل موجود برای این مسئله بهطور واضح و شفاف مشخص شود. مرحلهٔ بعدی، ساخت نام دارد. مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازهگیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی میباشد. آخرین مرحله پیادهسازی است که در آن پیادهسازی الگوریتم طراحی شده در مرحلهٔ قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.[۱۵]
جستارهای وابسته
منابع
پیوند به بیرون
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
