الگوریتمهای فراابتکاری: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
| (۴۸ نسخهٔ میانی ویرایش شده توسط ۳۶ کاربر نشان داده نشد) | |||
| خط ۱: | خط ۱: | ||
[[پرونده:Aco TSP.svg|بندانگشتی|الگوریتم ها به روش الگویی. به نظر شما میتوان چند شکل در این الگو درست کرد؟]] |
|||
'''الگوریتمهای فوق ابتکاری''': |
|||
'''الگوریتمهای فراابتکاری یا فراتکاملی یا فرااکتشافی '''نوعی از [[الگوریتمهای تصادفی]] هستند که برای یافتن پاسخ بهینه به کار می‌روند. |
|||
روش‌ها و [[الگوریتمهای بهینه‌سازی]] به دو دسته [[ |
روش‌ها و [[الگوریتمهای بهینه‌سازی]] به دو دسته [[الگوریتمهای دقیق]] (exact) و [[الگوریتمهای تقریبی]] (approximate algorithms) تقسیم‌بندی می‌شوند. الگوریتمهای دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد [[مسائل بهینه‌سازی سخت]] کارایی کافی ندارند و زمان اجرای آنها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتمهای تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتمهای تقریبی نیز به سه دسته الگوریتمهای ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش‌بندی می‌شوند. دو مشکل اصلی الگوریتمهای ابتکاری، گیر افتادن آنها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است. الگوریتمهای فراابتکاری برای حل این مشکلات الگوریتمهای ابتکاری ارائه شده‌اند. در واقع الگوریتمهای فراابتکاری، یکی از انواع الگوریتمهای بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند.<ref>الگوریتمهای بهینه‌سازی فراابتکاری (همراه با کاربردهایی در مهندسی برق)/تالیف دکتر فرشاد مریخ بیات؛ انتشارات جهاد دانشگاهی؛ 1393</ref><ref name="[1]">الگوریتمهای بهینه‌سازی فراابتکاری/تالیف مسعود یقینی، محمد رحیم اخوان کاظم‌زاده. جهاد دانشگاهی واحد صنعتی امیر کبیر {{شابک|978-964-210-078}}-1</ref> رده‌های گوناگونی از این نوع الگوریتم در دهه‌های اخیر توسعه یافته‌است<ref name="[9]">بهینه‌سازی ترکیبی و الگوریتمهای فرا ابتکاری /تالیف کورش عشقی؛ مهدی کریمی نسب انتشارات آذرین مهر ؛1391</ref>که همه این‌ها زیر مجموعه الگوریتم فراابتکاری می‌باشند. |
||
== دسته‌بندی الگوریتمهای |
== دسته‌بندی الگوریتمهای فراابتکاری == |
||
معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتمهای |
معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتمهای فراابتکاری استفاده شود:<ref name="[2]">Talbi, El-Ghazali. Metaheuristics: From Design to Impelementation, John Wiley and sons 2009</ref> |
||
* '''مبتنی بر یک جواب و مبتنی بر جمعیت''' |
* '''مبتنی بر یک جواب و مبتنی بر جمعیت''': الگوریتمهای مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتمهای مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند. |
||
* '''الهام گرفته شده از طبیعت و بدون الهام از طبیعت''': بسیاری از الگوریتمهای |
* '''الهام گرفته شده از طبیعت و بدون الهام از طبیعت''': بسیاری از الگوریتمهای فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتمهای فراابتکاری نیز از طبیعت الهام گرفته نشده‌اند. |
||
* '''با حافظه و بدون حافظه''': برخی از الگوریتمهای |
* '''با حافظه و بدون حافظه''': برخی از الگوریتمهای فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به‌طور مثال [[الگوریتم تبرید شبیه‌سازی شده|تبرید شبیه‌سازی شده]]). این در حالی است که در برخی از الگوریتمهای فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند. |
||
* '''قطعی و احتمالی''': یک الگوریتم |
* '''قطعی و احتمالی''': یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتمهای فراابتکاری احتمالی نظیر تبرید [[شبیه‌سازی]] شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد. |
||
| ⚫ | |||
| ⚫ | از الگوریتمهای شناخته شده فراابتکاری بر پایه جمعیت میتوان الگوریتمهای تکاملی<ref name="[3]">Eiben, A.E. , Smith, J.E. , Introduction to Evolutionary Computiong, Springer 2003</ref> ([[الگوریتم ژنتیک]]، برنامه‌ریزی ژنتیک، ...)، [[روش بهینه‌سازی گروه مورچه‌ها|بهینه‌سازی کلونی مورچگان]]،<ref name="[4]">Dorigo, M. , and Stützle, T. , Ant Colony Optimization, MIT Press, Cambridge, MA, 2004</ref> کلونی زنبورها،<ref name="[5]">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</ref> [[روش بهینه‌سازی ازدحام ذرات]]، [[الگوریتم بهینه‌سازی جنگل]]<ref>{{Cite journal|last=Ghaemi|first=Manizheh|last2=Feizi-Derakhshi|first2=Mohammad-Reza|date=2014-11-01|title=Forest Optimization Algorithm|url=http://www.sciencedirect.com/science/article/pii/S0957417414002899|journal=Expert Systems with Applications|language=en|volume=41|issue=15|pages=6676–6687|doi=10.1016/j.eswa.2014.05.009|issn=0957-4174}}</ref>، الگوریتم [[بهینه‌سازی|بهینه سازی]] Battle Royal<ref>{{Cite journal|last=Rahkar Farshi|first=Taymaz|date=2020-06-02|title=Battle royale optimization algorithm|url=https://doi.org/10.1007/s00521-020-05004-4|journal=Neural Computing and Applications|language=en|doi=10.1007/s00521-020-05004-4|issn=1433-3058}}</ref>، الگوریتم قهرمانی در لیگهای ورزشی، بهینه‌سازی ملهم از فیزیک نور، [http://www.sciencedirect.com/science/article/pii/S1568494615002756 الگوریتم ریشه-پاجوش] و [[الگوریتم چکه آبهای هوشمند]] را نام برد. |
||
| ⚫ | |||
| ⚫ | از الگوریتمهای شناخته شده |
||
در سال‌های اخیر الگوریتمهای فرابتکاری جدیدی با توجه به موجودات زنده موجود در طبیعت (الهام گرفته از طبیعت) توسعه داده شده‌اند که از معروف‌ترین آنها میتوان به الگوریتم بهینه سازی گرگ خاکستری ، الگوریتم بهینه سازی سنجاقک ، الگوریتم بهینه سازی گرده افشانی گل ها، الگوریتم بهینه سازی نهنگ یا وال ، [[الگوریتم بهینه سازی ملخ]]، و الگوریتم بهینه سازی کلونی پنگوئن های امپراتور<ref>{{Cite journal|last=Harifi|first=Sasan|last2=Khalilian|first2=Madjid|last3=Mohammadzadeh|first3=Javad|last4=Ebrahimnejad|first4=Sadoullah|date=2019-02-25|title=Emperor Penguins Colony: a new metaheuristic algorithm for optimization|url=https://doi.org/10.1007/s12065-019-00212-x|journal=Evolutionary Intelligence|language=en|doi=10.1007/s12065-019-00212-x|issn=1864-5917}}</ref> <ref>{{Cite journal|last=Yoosefdoost|first=Icen|last2=Basirifard|first2=Milad|last3=Álvarez-García|first3=José|year=2022-07-29|title=Reservoir Operation Management with New Multi-Objective (MOEPO) and Metaheuristic (EPO) Algorithms|url=https://www.mdpi.com/2073-4441/14/15/2329|journal=Water|language=en|volume=14|issue=15|pages=2329|doi=10.3390/w14152329|issn=2073-4441}}</ref> نام برد. |
|||
| ⚫ | |||
| ⚫ | از الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب میتوان [[الگوریتم جستجوی ممنوعه]] |
||
اخیرا، به نظر می رسد روند توسعه جدیدی از الگوریتم ها با الهام گرفتن از علم دیرینه شناسی و علوم باستان آغاز شده است. این الگوریتم ها که در دسته جدید الهام گرفته از دوران باستان، قرار می گیرند با بررسی ویژگی های دوران باستان سعی می کنند نوعی بهینه سازی ایجاد کنند <ref>https://doi.org/10.1007/s12065-020-00451-3</ref>. |
|||
| ⚫ | |||
| ⚫ | فرایند طراحی و پیاده‌سازی الگوریتمهای |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | از الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب میتوان [[الگوریتم جستجوی ممنوعه]]<ref name="[6]">Glover F. and Laguna, M. , Tabu Search, Kluwer Academic Publishers, 1997simulated annealing, Science, Vol. 220, No. 4598, pp. 671–680, 1983</ref> و [[الگوریتم تبرید شبیه‌سازی شده]]<ref name="[7]">Kirkpatrick, S. , Gelatt, C. D. , and Vecchi, M. P. , Optimization by simulated annealing, Science, Vol. 220, No. 4598, pp. 671–680, 1983</ref> را نام برد. |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | فرایند طراحی و پیاده‌سازی الگوریتمهای فراابتکاری دارای سه مرحلهٔ متوالی است که هر کدام از آنها دارای گام‌های مختلفی هستند. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحلهٔ ۱ آماده‌سازی است که در آن باید شناخت دقیقی از مسئله‌ای که می‌خواهیم حل کنیم بدست آوریم، و اهداف [[طراحی الگوریتم]] فراابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسئله به‌طور واضح و شفاف مشخص شود. مرحلهٔ بعدی، ساخت نام دارد. مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای [[اندازه‌گیری]] عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن پیاده‌سازی الگوریتم طراحی شده در مرحلهٔ قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.<ref name="[8]">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.</ref> |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
== منابع == |
== منابع == |
||
| ⚫ | |||
<!--- [[ویکی‌پدیا:پانویس‌ها]] را بخوانید. در وسط مقاله از <ref>منبع</ref> به عنوان منبع استفاده کنید --> |
|||
| ⚫ | |||
== پیوند به بیرون == |
|||
* [https://programstore.ir/%D9%84%DB%8C%D8%B3%D8%AA-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%87%D8%A7%DB%8C-%D9%81%D8%B1%D8%A7-%D8%A7%D8%A8%D8%AA%DA%A9%D8%A7%D8%B1%DB%8C-%D9%85%D8%AA%D8%A7%D9%87%DB%8C%D9%88%D8%B1/ فهرست الگوریتم های فرا ابتکاری (متاهیورستیک) از سال 1983 تا 2020] |
|||
{{زیرمجموعه‌های اصلی بهینه‌سازی}} |
|||
<!--- رده‌بندی ---> |
|||
[[رده:الگوریتمهای بهینه‌سازی]] |
[[رده:الگوریتمهای بهینه‌سازی]] |
||
[[رده:الگوریتمهای تقریبی]] |
[[رده:الگوریتمهای تقریبی]] |
||
[[رده:الگوریتمهای فراابتکاری| ]] |
|||
[[رده:بهینه‌سازی ریاضی]] |
[[رده:بهینه‌سازی ریاضی]] |
||
[[رده:تحقیق در عملیات]] |
[[رده:تحقیق در عملیات]] |
||
نسخهٔ کنونی تا ۲۴ سپتامبر ۲۰۲۴، ساعت ۱۸:۴۵
الگوریتمهای فراابتکاری یا فراتکاملی یا فرااکتشافی نوعی از الگوریتمهای تصادفی هستند که برای یافتن پاسخ بهینه به کار می‌روند.
روش‌ها و الگوریتمهای بهینه‌سازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتمهای تقریبی (approximate algorithms) تقسیم‌بندی می‌شوند. الگوریتمهای دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی سخت کارایی کافی ندارند و زمان اجرای آنها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتمهای تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتمهای تقریبی نیز به سه دسته الگوریتمهای ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش‌بندی می‌شوند. دو مشکل اصلی الگوریتمهای ابتکاری، گیر افتادن آنها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است. الگوریتمهای فراابتکاری برای حل این مشکلات الگوریتمهای ابتکاری ارائه شده‌اند. در واقع الگوریتمهای فراابتکاری، یکی از انواع الگوریتمهای بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند.[۱][۲] رده‌های گوناگونی از این نوع الگوریتم در دهه‌های اخیر توسعه یافته‌است[۳]که همه این‌ها زیر مجموعه الگوریتم فراابتکاری می‌باشند.
دسته‌بندی الگوریتمهای فراابتکاری
[ویرایش]معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتمهای فراابتکاری استفاده شود:[۴]
- مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتمهای مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتمهای مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند.
- الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتمهای فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتمهای فراابتکاری نیز از طبیعت الهام گرفته نشده‌اند.
- با حافظه و بدون حافظه: برخی از الگوریتمهای فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به‌طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتمهای فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
- قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتمهای فراابتکاری احتمالی نظیر تبرید شبیه‌سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.
الگوریتمهای فراابتکاری بر پایه جمعیت
[ویرایش]از الگوریتمهای شناخته شده فراابتکاری بر پایه جمعیت میتوان الگوریتمهای تکاملی[۵] (الگوریتم ژنتیک، برنامه‌ریزی ژنتیک، ...)، بهینه‌سازی کلونی مورچگان،[۶] کلونی زنبورها،[۷] روش بهینه‌سازی ازدحام ذرات، الگوریتم بهینه‌سازی جنگل[۸]، الگوریتم بهینه سازی Battle Royal[۹]، الگوریتم قهرمانی در لیگهای ورزشی، بهینه‌سازی ملهم از فیزیک نور، الگوریتم ریشه-پاجوش و الگوریتم چکه آبهای هوشمند را نام برد.
در سال‌های اخیر الگوریتمهای فرابتکاری جدیدی با توجه به موجودات زنده موجود در طبیعت (الهام گرفته از طبیعت) توسعه داده شده‌اند که از معروف‌ترین آنها میتوان به الگوریتم بهینه سازی گرگ خاکستری ، الگوریتم بهینه سازی سنجاقک ، الگوریتم بهینه سازی گرده افشانی گل ها، الگوریتم بهینه سازی نهنگ یا وال ، الگوریتم بهینه سازی ملخ، و الگوریتم بهینه سازی کلونی پنگوئن های امپراتور[۱۰] [۱۱] نام برد.
اخیرا، به نظر می رسد روند توسعه جدیدی از الگوریتم ها با الهام گرفتن از علم دیرینه شناسی و علوم باستان آغاز شده است. این الگوریتم ها که در دسته جدید الهام گرفته از دوران باستان، قرار می گیرند با بررسی ویژگی های دوران باستان سعی می کنند نوعی بهینه سازی ایجاد کنند [۱۲].
الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب
[ویرایش]از الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب میتوان الگوریتم جستجوی ممنوعه[۱۳] و الگوریتم تبرید شبیه‌سازی شده[۱۴] را نام برد.
پیاده‌سازی الگوریتمهای فراابتکاری
[ویرایش]فرایند طراحی و پیاده‌سازی الگوریتمهای فراابتکاری دارای سه مرحلهٔ متوالی است که هر کدام از آنها دارای گام‌های مختلفی هستند. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحلهٔ ۱ آماده‌سازی است که در آن باید شناخت دقیقی از مسئله‌ای که می‌خواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فراابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسئله به‌طور واضح و شفاف مشخص شود. مرحلهٔ بعدی، ساخت نام دارد. مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه‌گیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن پیاده‌سازی الگوریتم طراحی شده در مرحلهٔ قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.[۱۵]
جستارهای وابسته
[ویرایش]منابع
[ویرایش]- ↑ الگوریتمهای بهینه‌سازی فراابتکاری (همراه با کاربردهایی در مهندسی برق)/تالیف دکتر فرشاد مریخ بیات؛ انتشارات جهاد دانشگاهی؛ 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
- ↑ Ghaemi, Manizheh; Feizi-Derakhshi, Mohammad-Reza (2014-11-01). "Forest Optimization Algorithm". Expert Systems with Applications (به انگلیسی). 41 (15): 6676–6687. doi:10.1016/j.eswa.2014.05.009. ISSN 0957-4174.
- ↑ Rahkar Farshi, Taymaz (2020-06-02). "Battle royale optimization algorithm". Neural Computing and Applications (به انگلیسی). doi:10.1007/s00521-020-05004-4. ISSN 1433-3058.
- ↑ Harifi, Sasan; Khalilian, Madjid; Mohammadzadeh, Javad; Ebrahimnejad, Sadoullah (2019-02-25). "Emperor Penguins Colony: a new metaheuristic algorithm for optimization". Evolutionary Intelligence (به انگلیسی). doi:10.1007/s12065-019-00212-x. ISSN 1864-5917.
- ↑ Yoosefdoost, Icen; Basirifard, Milad; Álvarez-García, José (2022-07-29). "Reservoir Operation Management with New Multi-Objective (MOEPO) and Metaheuristic (EPO) Algorithms". Water (به انگلیسی). 14 (15): 2329. doi:10.3390/w14152329. ISSN 2073-4441.
- ↑ 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.