بخشی از پاورپوینت
اسلاید 1 :
الگوریتمهای فرا ابتکاری
Meta-Heuristic
اسلاید 2 :
الگوریتمهای بهینهسازی
الگوریتمهای بهینهسازی
الگوریتمهای دقیق
الگوریتمهای تقریبی
Deterministic
Non-Deterministic
Optimization Alg.
اسلاید 3 :
الگوریتمهای دقیق
الگوریتمهای تقریبی
یافتن جواب بهینه به صورت دقیق
نداشتن کاربرد در مسائل سخت
مناسب برای مسائل سخت
یافتن جوابهای خوب (نزدیک به بهینه)
افزایش زمان حل به صورت نمایی
زمان حل کوتاه
Deterministic Alg.
Find Exact solution
Could not solve NP-Hard Problems
Execution Time grows Exponentially
Non-Deterministic Alg.
Find Near-optimal solution
Could solve NP-Hard Problems
Small Execution time
اسلاید 4 :
مثال خرید خانه(Buy a House)
الگوریتم عادی (Regular algorithm) :
جستجوی خانه مناسب با بودجه از ابتدا تا انتهای شهر – چندین سال طول بکشد. (Buy best house with you're budget)
تضمین بهترین خانه، مشکل سرعت کم
روش اکتشافی و یا ابتکاری(Heuristic method) :
انتخاب منطقه مناسب با بودجه
مراجعه به مشاورین امکاک منطقه و انتخاب خانه مناسب ( نه لزوماً بهترین ) -> بهینه معقول
الگوریتم های ابتکاری بهترین جواب را تضمین نمی کند.
اسلاید 5 :
الگوریتمهای تقریبی
heuristic
hyper heuristic
Meta
heuristic
Non-Deterministic Alg.
اسلاید 6 :
دو مشکل اصلی الگوریتمهای ابتکاری :
قرار گرفتن آنها در بهینههای محلی (Local Minima)،
و ناتوانی آنها برای کاربرد در مسائل گوناگون است
(Could not solve a large category of problems).
برای حل این مشکلات الگوریتمهای فرا ابتکاری ارائه شدهاند، در واقع الگوریتمهای فراابتکاری، یکی از انواع الگوریتم های بهینهسازی تقریبی هستند که دارای راهکارهای برون رفت از بهینه محلی میباشند و قابل کاربرد در طیف گسترده ای از مسائل هستند.
Main Problems of Heuristic Algorithm
To solve these problems, meta-heuristic algorithm proposed.
Which could solve a lots of problems and escape from local minima.
اسلاید 7 :
الگوریتمهای فرا ابتکاری
پیدا کردن راه حل در یک زمان معقول (find a good solution in resendable time)
به جای اینکه تمامی فضای مسئله را جستجو کنند، به دنبال جستجو در قسمتهایی از مسئله میگردند تا بتوانند به یک بهینهی سراسری یا یک بهینهی محلیِ خوب دست پیدا کنند.
هدفِ الگوریتم فرار کردن از بهینهی محلی و رسیدن به بهینهی سراسری یا چیزی نزدیک به آن
اسلاید 8 :
جستجوی محلی (بهینهسازی)
بهینه سازی محلی با مجاورهایش:
بطور معمول، هر راه حل پیش رو، بیشتر از یک راه حل مجاور دارد، انتخاب هر کدام از راه حلها برای حرکت، تنها با استفاده از اطلاعاتی
در باره ی راه حلهای مجاور با راه حل فعلی صورت میگیرد و به همین جهت جستجوی محلی نامیده میشود .
در نتیجه :
وقتی هیچ تنظیماتی برای بهبود در مجاورت و همسایگی صورت نگیرد، جستجوی محلی، در یک نقطه بهینه محلی گیر کردهاست.
اسلاید 9 :
جستجوی محلی (بهینهسازی)
Local optima
Global optima
اسلاید 10 :
دستهبندی الگوریتمهای فراابتکاری
مبتنی بر یک جواب و مبتنی بر جمعیت
الهام گرفته شده از طبیعت و بدون الهام از طبیعت
با حافظه و بدون حافظه
قطعی و احتمالی
اسلاید 11 :
مبتنی بر یک جواب و مبتنی بر جمعیت Single-solution and population based
الگوریتمهای مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر میدهند، در حالی که در الگوریتمهای مبتنی بر جمعیت در حین جستجو، یک جمعیت از جوابها در نظر گرفته میشوند.
اسلاید 12 :
الهام گرفته شده از طبیعت و بدون الهام از طبیعت Nature inspired algorithm and non-nature inspired
بسیاری از الگوریتمهای فراابتکاری از طبیعت الهام گرفته شدهاند، در این میان برخی از الگوریتمهای فراابتکاری نیز از طبیعت الهام گرفته نشده اند.
اسلاید 13 :
با حافظه و بدون حافظه With memory and memory less
برخی از الگوریتمهای فراابتکاری فاقد حافظه میباشند، به این معنا که، این نوع الگوریتمها از اطلاعات بدست آمده در حین جستجو استفاده نمیکنند این در حالی است که در برخی از الگوریتمهای فراابتکاری از حافظه استفاده میکنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره میکند.
اسلاید 14 :
قطعی و احتمالی (Deterministic and probabilistic)
یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل میکند. اما در الگوریتمهای فراابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار میگیرد.
اسلاید 15 :
الگوریتمهای متداول فراابتکاری مبتنی بر یک جوابSingle solution based metaheuristic
الگوریتم جستجوی ممنوعه (Tabu Search) و
الگوریتم تبرید شبیهسازی شده (Simulated Annulling)
اسلاید 16 :
الگوریتمهای فراابتکاری بر پایه جمعیت
از الگوریتمهای شناخته شده فراابتکاری بر پایه جمعیت میتوان
الگوریتمهای تکاملی (Genetic Algorithm)
(الگوریتم ژنتیک، برنامهریزی ژنتیک، .)،
بهینهسازی کلونی مورچگان (Ant Colony)
کلونی زنبورها (Bees Colony)
روش بهینهسازی ازدحام ذرات (Particle Swarm Optimization)
الگوریتم رقابت استعماری (Imperialist Competitive Algorithm - ICA)
اسلاید 17 :
پیادهسازی الگوریتمهای فراابتکاری Developing meta-heuristic algorithms steps
فرایند طراحی و پیادهسازی الگوریتمهای فراابتکاری دارای سه مرحلهی متوالی است که هر کدام از آنها دارای گامهای مختلفی هستند. در هر گام فعالیتهایی باید انجام شود تا آن گام کامل شود.
اسلاید 18 :
مرحله اول - Step 1
مرحلهی ۱ آمادهسازی (Prepartion) است که در آن باید شناخت دقیقی از مسئلهای که میخواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فراابتکاری برای آن باید با توجه به روشهای حل موجود برای این مسئله به طور واضح و شفاف مشخص شود.
اسلاید 19 :
مرحله دوم - Step 2
مرحلهی بعدی، «ساخت» نام دارد(Counstruction). مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه گیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی میباشد.
اسلاید 20 :
مرحله سوم - Step 3
آخرین مرحله پیادهسازی (Implementation) است و در آن پیادهسازی الگوریتم طراحی شده در مرحلهی قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تهیه گزارش نتایج باید انجام شود.
