الگوریتم فراابتکاری چیست؟ الگوریتم بهینه سازی چیست ؟ الگوریتم تکاملی چیست؟

الگوریتم فراابتکاری چیست ؟ و شامل چه الگوریتم هایی میشود؟ در این مقاله از سایت تکاملی ، به بررسی جامع و کامل مفهوم الگوریتم فراابتکاری و شاخه های مختلف آن خواهیم پرداخت.

الگوریتم‌های فراابتکاری یا فراتکاملی یا فرااکتشافی نوعی از الگوریتم‌های تصادفی هستند که برای یافتن پاسخ بهینه به کار می‌روند.

روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتم‌های تقریبی (approximate algorithms) تقسیم‌بندی می‌شوند.

الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی سخت کارایی کافی ندارند و زمان اجرای آن‌ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد.

الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند.

الگوریتم‌های تقریبی نیز به سه دسته :

• الگوریتم‌های ابتکاری (heuristic)
• فراابتکاری (meta-heuristic)
• فوق ابتکاری (hyper heuristic)

بخش‌بندی می‌شوند.

دو مشکل اصلی الگوریتم‌های ابتکاری، گیر افتادن آن‌ها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است.

الگوریتم‌های فراابتکاری برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند.

در واقع الگوریتم‌های فراابتکاری یا Metaheuristic Algorithms ، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند.

الگوریتم های بهینه سازی فراابتکاری را میتوان در سه دسته اصلی دسته بندی کرد:

• الگوریتم های تکاملی ،
• الگوریتم های مبتنی بر فیزیک ،
• الگوریتم های SI (یا مبتنی بر هوش ازدحامی)

الگوریتم تکاملی چیست ؟

دسته اول از الگوریتم های فراابتکاری ، یعنی الگوریتم های تکاملی ، از ایده تکامل در طبیعت الهام گرفته شده است.

این الگوریتم ها براساس نظریه های داروین ساخته شده اند.

این نظریه یک فرایند بهینه سازی با هدف بهبود توانایی موجودات زنده برای زنده ماندن در یک محیط پویا است. محیط زندگی یکی از عواملی است که در تعیین بهترین موجودات نقشی حیاتی دارد. به عبارت دیگر ، چندین گونه از موجودات زنده که در یک محیط خاص زندگی می کنند ، طی چندین نسل تکامل می یابند.

قبلا به بررسی نظریه تکامل داروین ، و همچنین داروین کیست پرداخته ایم ، نظریه انتخاب طبیعی را نیز بحث کرده ایم.

الگوریتم های تکاملی (EA) تقلید ابتکاری از اصول تکامل داروین است. داروین در کتابی با عنوان “مبدا گونه ها” دو سوال اساسی را مطرح کرد:
• آیا امروزه حیوانات و گیاهان از فرزندان موجودات ماقبل تاریخ هستند؟
• آیا یک گونه به گونه دیگری تبدیل می شود؟
این نظریه بسیار گسترده است که در این مقاله توضیح داده نمی شود. با این حال ، همانطور که مستند است ، داروین از پاسخ های مثبت به این سوالات آگاه بود. EA همان اصول داروین را دنبال می کند که در آن جمعیتی از راه حل ها به صورت تکراری تکامل می یابند (بهبود می یابند).
(Swarm Intelligence (SI نوع جالب دیگری از هوش در طبیعت است که به رفتار جمعی موجودات اشاره دارد.
روشهای SI یکی از محبوب ترین مباحث تحقیقاتی طی سالهای اخیر بوده است. آنها بیشتر بر روی طراحی یک سیستم هوشمند با سه ویژگی (انطباق ، پراکندگی و انعطاف پذیری) تمرکز می کنند ، که فرصت های زیادی را برای حل مسائل پیچیده در زمینه های مختلف فراهم می کند.
تعداد زیادی از الگوریتم های SI ، بر اساس SI هستند و از رفتار اجتماعی حیوانات الهام گرفته شده اند. بین ارگانیسم ها و SI ارتباط شدیدی وجود دارد که به آن تعامل گفته می شود. رفتارهای جمعی موجودات منجر به SI می شود و SI شرایط را تغییر می دهد. چند نمونه از این رفتارهای تعاملی در طبیعت به شرح زیر است: • موریانه ها لانه های بزرگ و پیچیده ای می سازند ، و این فراتر از درک و توانایی یک موریانه است.
• کارهای مختلف در کلونی مورچه ها به طور خودکار و بدون مدیریت مرکزی شناسایی می شوند.
• حرکت رقص زنبورهای عسل باعث می شود غذای بیشتری پیدا کنند.
• پرندگان و ماهی ها در الگوی فضایی مطلوب سازمان یافته اند.
• باکتریها با استفاده از مولکولها تغییرات محیطی را دنبال می کنند.

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