الگوریتم ژنتیک

الگوریتم ژنتیک

اسلاید 1: الگوریتم ژنتیک

اسلاید 2:  نوعی از الگوریتم‌های تصادفی هستند که برای یافتن پاسخ بهینه به کار می‌روند.راهکارهای پیشرفته و کلی جستجو می‌باشند و گام‌ها و معیارهایی را پیشنهاد می‌کنند که در فرار از دام بهینه‌های موضعی بسیار مؤثر هستند.یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند.الگوریتم های فرا ابتکاری/فرا اکتشافی

اسلاید 3: روش‌ها و الگوریتم‌های بهینه‌سازی 1.دقیق (exact) 2.الگوریتم‌های تقریبی (approximate algorithms) الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی سخت کارایی کافی ندارند و زمان اجرای آن‌ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم های فرا ابتکاری/فرا اکتشافی

اسلاید 4: 1.الگوریتم‌های ابتکاری (heuristic) 2.فراابتکاری (meta-heuristic) ) 3.فوق ابتکاری (hyper heuristic)انواع الگوریتم های تقریبی

اسلاید 5: مراحل فرایند طراحی و پیاده‌سازی الگوریتم‌های فراابتکاری مرحله آماده‌سازی :در آن باید شناخت دقیقی از مسئله‌ای که می‌خواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فراابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسئله به طور واضح و شفاف مشخص شود. مرحله ساخت :مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه‌گیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. مرحله پیاده‌سازی : در آن پیاده‌سازی الگوریتم طراحی شده در مرحله قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.

اسلاید 6: دسته‌بندی الگوریتم‌های فرا ابتکاری 1.مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتم‌های مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند.    2.الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم‌های فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم‌های فراابتکاری نیز از طبیعت الهام گرفته نشده اند   .

اسلاید 7: 3.با حافظه و بدون حافظه: برخی از الگوریتم‌های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم‌های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند. 4.قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فراابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد

اسلاید 8: الگوریتم های مبتنی بر یک جواب -الگوریتم تبرید شبیه سازی شده simulated annealing -جست وجوی ممنوعه tabu search -جست و جوی حریصانهGRASP search  -جست و جوی همسایگی متغیرvariable neighborhood search  -جست و جوی محلی هدایت شدهguided local search  -جست و جوی محلی تکرار شوندهinterated local search

اسلاید 9: الگوریتم های مبتنی بر جمعیت الگوریتم ژنتیک Genetic Algorithm -الگوریتم رقابت استعماری Imperialist Competitive Algorithm -الگوریتم بهینه سازی کلونی مورچگان Ant Colony Optimization Algorithm  -الگوریتم کلونی زنبور عسل Bee Colony Algorithm -الگوریتم کرم شب تاب Firefly Algorithm -الگوریتم سیتم ایمنی مصنوعی Artificial Immune System Algorithm -الگوریتم جستجوی هارمونی Harmony Search Algorithm -الگوریتم بهینه سازی تجمعی ذرات Particle Swarm Optimization Algorithm

اسلاید 10: هيوريستيك ها الگوريتم هايي هستند كه مي توانند يافتن جوابهاي خوب در فاصله مشخصي از جواب بهينه را تضمين كنند كه به آنها الگوريتم هاي تقريبي مي گويند. الگوريتم هاي ديگري هستند كه تضمين مي دهند با احتمال بالا جواب نزديك بهينه توليد كنند كه به آنها الگوريتم هاي احتمالي گفته مي شود. جداي از اين دو دسته، مي توان الگوريتم هايي را پذيرفت كه هيچ تضميني در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتايج آنها، به طور متوسط بهترين تقابل كيفيت و زمان حل براي مسئله مورد بررسي را به همراه داشته اند

اسلاید 11: هيوريستيك معيارها، روشها يا اصولي براي تصميم گيري بين چند گزينه خط مشي و انتخاب اثربخش ترين براي دستيابي به اهداف مورد نظر .نتيجه برقراري اعتدال بين دو نياز هستند: نياز به ساخت معيار هاي ساده و در همان زمان توانايي تمايز درست بين انتخاب هاي خوب و بد. يك هيوريستيك مي تواند حسابي سرانگشتي باشد كه براي هدايت يك دسته از اقدامات به كار ميرود. براي مثال، يك روش مشهور براي انتخاب طالبي رسيده عبارتست از فشار دادن محل اتصال به ريشه از يك طالبي نامزد انتخاب و سپس بو كردن آن محل. اگر بوي آن محل مانند بوي داخل طالبي باشد آن طالبي به احتمال زياد رسيده است. اين قاعده سرانگشتي نه تضمين مي كند كه تنها طالبي هاي رسيده به عنوان نامزد انتخاب شوند و نه تضمين مي كند كه طالبي هاي رسيده آزمايش شده، رسيده تشخيص داده شوند اما به هر حال اين روش ،اثربخش ترين روش شناخته شده است.

اسلاید 12:

اسلاید 13: موجودی که توانایی انطباق بیشتر با تغییرات دارد شانس بقاء بیشتر دارد. مثال نابودی دایناسورهاانگیزه خودتکثیری،میل به جاودانگینتایج تغییرات برنامه ریزی خوب و موفقسگ و گربه در اثر مجاورت و همزیستی با انسان از سایر گربه انان باهوش ترند.

اسلاید 14:

اسلاید 15: اطلاعات یا رشته وراثتی ما ، یک درخت گردو(گیاهان) و برخی انسانهای دیگر مشترک و مشابه است!!!

اسلاید 16:

اسلاید 17:

اسلاید 18:

اسلاید 19: تک تک عناصر سازنده=ژنوتیپخروجی انواع ترکیبهای ژنوتیپ=فنوتیپ یا تابع هدف