الگوریتم های فراابتکاری
الگوریتمهای فوق ابتکاری (مِهتاجُستَنیک)
روشها و الگوریتمهای بهینهسازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتمهای تقریبی (approximate algortithms) تقسیمبندی میشوند. الگوریتمهای دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش مییابد. الگوریتمهای تقریبی قادر به یافتن جوابهای خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینهسازی سخت هستند. الگوریتمهای تقریبی نیز به سه دسته الگوریتمهای ابتکاری یا جُستَنیک (heuristic) و فوق ابتکاری یا مِهتاجستنیک (meta-heuristic) و فرا ابتکاری یا اَبَرجُستنیک (hyper heuristic) بخش بندی می شوند. دو مشکل اصلی الگوریتمهای ابتکاری، قرار گرفتن آنها در بهینههای محلی، و ناتوانی آنها برای کاربرد در مسائل گوناگون است. الگوریتمهای فوق ابتکاری یا مِهتاجستنیک ها برای حل این مشکلات الگوریتمهای ابتکاری ارائه شدهاند. در واقع الگوریتمهای فوق ابتکاری، یکی از انواع الگوریتمهای بهینهسازی تقریبی هستند که دارای راهکارهای برونرفت از بهینه محلی میباشند و قابل کاربرد در طیف گسترده ای از مسائل هستند. [۱] ا رده های گوناگونی از این نوع الگوریتمهای در ده های اخیر توسعه یافته است [۲]
محتویات |
دستهبندی الگوریتمهای فوق ابتکاری (مِهتاجستنیک) [ویرایش]
معیارهای مختلفی میتواند برای طبقهبندی الگوریتمهای فوق ابتکاری استفاده شود: [۳]
- مبتنی بر یک جواب و مبتنی بر جمعیت : الگوریتمهای مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر میدهند، در حالی که در الگوریتمهای مبتنی بر جمعیت در حین جستجو، یک جمعیت از جوابها در نظر گرفته میشوند.
- الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتمهای فوق ابتکاری از طبیعت الهام گرفته شدهاند، در این میان برخی از الگوریتمهای فوق ابتکاری نیز از طبیعت الهام گرفته نشده اند.
- با حافظه و بدون حافظه: برخی از الگوریتمهای فوق ابتکاری فاقد حافظه میباشند، به این معنا که، این نوع الگوریتمها از اطلاعات بدست آمده در حین جستجو استفاده نمی کنند (به طور مثال تبرید شبیهسازی شده). این در حالی است که در برخی از الگوریتمهای فوق ابتکاری نظیر جستجوی ممنوعه از حافظه استفاده میکنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره میکند.
- قطعی و احتمالی: یک الگوریتم فوق ابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل میکند. اما در الگوریتمهای فوق ابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار میگیرد.
الگوریتمهای شناخته شده فوق ابتکاری (مِهتاجُستنیک) بر پایه جمعیت [ویرایش]
از الگوریتمهای شناخته شده فوق ابتکاری بر پایه جمعیت میتوان الگوریتمهای تکاملی [۴] (الگوریتم ژنتیک، برنامهریزی ژنتیک، ...)، بهینهسازی کلونی مورچگان [۵]، کلونی زنبورها [۶]، روش بهینهسازی ازدحام ذرات، الگوریتم رقابت استعماری ، و الگوریتم چکه آبهای هوشمند را نام برد.
الگوریتمهای متداول فوق ابتکاری (مِهتاجستنیک) مبتنی بر یک جواب [ویرایش]
از الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب میتوان الگوریتم جستجوی ممنوعه [۷] و الگوریتم تبرید شبیهسازی شده [۸] را نام برد.
پیادهسازی الگوریتمهای فوق ابتکاری (مِهتاجستنیک) [ویرایش]
فرایند طراحی و پیادهسازی الگوریتمهای فوق ابتکاری (مِهتاجستنیک) دارای سه مرحلهی متوالی است که هر کدام از آنها دارای گامهای مختلفی هستند. در هر گام فعالیتهایی باید انجام شود تا آن گام کامل شود. مرحلهی ۱ آمادهسازی است که در آن باید شناخت دقیقی از مسئلهای که میخواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فوق ابتکاری برای آن باید با توجه به روشهای حل موجود برای این مسئله به طور واضح و شفاف مشخص شود. مرحلهی بعدی، ساخت نام دارد. مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه گیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی میباشد. آخرین مرحله پیادهسازی است که در آن پیادهسازی الگوریتم طراحی شده در مرحلهی قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدون و تهیه گزارش نتایج باید انجام شود. [۹]
جستارهای وابسته [ویرایش]
منابع [ویرایش]
- ↑ الگوریتمهای بهینهسازی فوق ابتکاری/تالیف مسعود یقینی، محمد رحیم اخوان کاظم زاده. جهاد دانشگاهی واحد صنعتی امیر کبیر ISBN ۹۷۸-۹۶۴-۲۱۰-۰۷۸-۱
- ↑ بهینهسازی ترکیبی و الگوریتم های فرا ابتکاری /تالیف کورش عشقی ؛ مهدی کریمی نسب انتشارات آذرین مهر ؛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
- ↑ 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.
