الگوریتم های فرا ابتکاری یا فرا تکاملی یا فرا اکتشافی نوعی از الگوریتم های تصادفی هستند که برای یافتن پاسخ بهینه به کار می‌روند.
روش‌ها و الگوریتمهای بهینه‌سازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتمهای تقریبی (approximate algorithms) تقسیم‌بندی می‌شوند. الگوریتمهای دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی سخت کارایی کافی ندارند و زمان اجرای آنها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتمهای تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند.
الگوریتمهای تقریبی نیز به سه دسته الگوریتمهای ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش‌بندی می‌شوند. دو مشکل اصلی الگوریتمهای ابتکاری، گیر افتادن آنها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است. الگوریتم های فراابتکاری برای حل این مشکلات الگوریتمهای ابتکاری ارائه شده‌اند. در واقع الگوریتم های فراابتکاری، یکی از انواع الگوریتمهای بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند. رده‌های گوناگونی از این نوع الگوریتم در دهه‌های اخیر توسعه یافته‌است که همه این ها زیر مجموعه الگوریتم فراابتکاری می باشند.
دسته‌بندی الگوریتم های فرا ابتکاری
معیارهای مختلفی می‌توانند برای طبقه‌بندی الگوریتم های فراابتکاری استفاده شوند:
- مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتمهای مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتمهای مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند.
- الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم های فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم های فراابتکاری نیز از طبیعت الهام گرفته نشده‌اند.
- با حافظه و بدون حافظه: برخی از الگوریتم های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به طور مثالتبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
- قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم های فراابتکاری احتمالی نظیر تبرید شبیه‌سازیشده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.
الگوریتم های فراابتکاری بر پایه جمعیت
از الگوریتمهای شناخته شده فراابتکاری بر پایه جمعیت میتوان الگوریتمهای تکاملی (الگوریتم ژنتیک، برنامه‌ریزی ژنتیک، …)، بهینه‌سازی کلونی مورچگان، کلونی زنبورها، روش بهینه‌سازی ازدحام ذرات، الگوریتم قهرمانی در لیگهای ورزشی، بهینه‌سازی ملهم از فیزیک نور، الگوریتم ریشه-پاجوش و الگوریتم چکه آبهای هوشمند را نام برد.
در سالهای اخیر الگوریتم های فراابتکاری جدیدی با توجه به موجودات زنده موجود در طبیعت توسعه داده شده اند که از معروف ترین آنها میتوان به الگوریتم بهینه سازی گرگ خاکستری ، الگوریتم بهینه سازی سنجاقک ، الگوریتم بهینه سازی گرده افشانی گل ها، الگوریتم بهینه سازی نهنگ یا وال ، الگوریتم بهینه سازی ملخ نام برد.
الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب
از الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب میتوان الگوریتم جستجوی ممنوعه و الگوریتم تبرید شبیه‌سازی شده را نام برد.
پیاده‌سازی الگوریتم های فراابتکاری
فرایند طراحی و پیاده‌سازی الگوریتم های فراابتکاری دارای سه مرحلهٔ متوالی است که هر کدام از آنها دارای گام‌های مختلفی هستند. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحلهٔ ۱ آماده‌سازی است که در آن باید شناخت دقیقی از مسئله‌ای که می‌خواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فراابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسئله به طور واضح و شفاف مشخص شود. مرحلهٔ بعدی، ساخت نام دارد.
مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه‌گیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن پیاده‌سازی الگوریتم طراحی شده در مرحلهٔ قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.
منبع
خلاصه ای در مورد الگوریتم های متاهیوریستیک
اکنون تعداد زیادی از مسائل بهینه سازی در پیرامون ما وجود دارد که به روش دقیق یا اصلاً قابل حل نیستند و یااین که در زمان معقول انجام این امر امکان پذیر نیست. بعضی از این چنین مسائلی را که عمدتاً جزء مسائل بهینه سازی هستند، مسائل NP-Hard می نامند. این خانواده بزرگ از مسائل، خواص بسیار جالبی دارند که سبب شده است تا کنون روش های تقریبی متعددی برای حل هر کدام از آنها در طول زمان ارائه شود. الگوریتم های فراابتکاری (متاهیوریستیک) جزء این دسته از روش ها هستند.
البته در مواقعی که در یک مسئله بهینه سازی، پارامتر یا محدودیت تصادفی، چند تابع هدف متضاد و امثالهم هم وجود داشته باشد، استفاده از الگوریتم های فراابتکاری بسیار موفقیت آمیزتر از سایر روش ها گزارش شده است. از طرف دیگر تنها تعداد معدودی از این الگوریتم ها اثبات شده اند که در حل بعضی از مسائل خاص حتماً به ازای هر مقدار از پارامترهای ورودی به جواب بهینه همگرا می شوند. عیب عمده این روش ها هم در همین مورد است. اما قابلیت مانور فراوان، طراحی ساده و بسیار سریع بودن آنها در کفه دیگر ترازو قرار دارد.
تعداد الگوریتم های فراابتکاری بسیار زیاد است اما ساختار منطق حاکم بر آنها معمولا جزء چند دسته از ساختارهای شناخته شده قرار می گیرد. از این رو با شناخت این منطق ها می توان الگوریتم های هیبریدی جدیدی را برای حل مسائلی را که با آنها سر و کار داریم، به وجود آورد. این روند همچنان ادامه دارد و هر روز الگوریتم های جالبی متولد می شوند و عده ای از الگوریتم ها نیز به تدریج منسوخ می شوند و تنها ارزش گزارش شدن در تاریخچه الگوریتم ها را به خود می گیرند. به عبارت دیگر، یکی از اهداف این دوره، آشنایی با دنیای زنده و پر تکاپوی موجودات الگوریتمی برای مهندسین صنایع است تا در مطالعات علمی خود از آنها استفاده کنند.
منبع
در چند دهه اخیر، دسته‌ای از الگوریتمهای تقریبی توسعه داده شده‌اند که سعی دارند با ترکیب اصول اولیه روش‌های ابتکاری (هیوریستیک) روشی را برای جستجوی مؤثر و کارای فضای جواب پیدا کنند. امروزه این روش‌ها به روش‌های فرا ابتکاری (متاهیوریستیک) مشهورند. اصطلاح متاهیوریستیک اولین بار توسط Glover در سال 1993 و به هنگام معرفی روش جستجوی ممنوع به عنوان یک روش ابتکاری جدید به کار برده شد.
پیش از این، روش‌های فرا ابتکاری، روش‌های ابتکاری نوین نامیده می‌شدند. الگوریتمهای تکاملی نظیر الگوریتم ژنتیک، الگوریتم بهینه‌سازی مورچگان، روش شبیه‌سازی تبرید، جستجوی ممنوع و شبکه‌های عصبی مصنوعی نمونه‌هایی از این روش‌ها می‌باشند.
تا به امروز تعریف مشخص و جامعی از اصطلاح متاهیوریستیک یا فرا ابتکاری صورت نگرفته است و تعاریف مختلفی برای این اصطلاح ارائه شده است. اما به طور خلاصه میتوان مشخصات اصلی روش‌های فرا ابتکاری را به صورت زیر بیان نمود.
- برخلاف روش‌های ابتکاری، هدف اصلی این روش‌ها، جستجوی مؤثر و کارای فضای جواب به جای یافتن صرف جواب‌های بهینه یا نزدیک بهینه می‌باشد؛
- روش‌های فرا ابتکاری سیاست‌ها و راهکارهایی هستند که فرآیند جستجو را هدایت می‌کنند؛
- روش‌های فرا ابتکاری تقریبی بوده و اغلب غیر قطعی(تصادفی) می‌باشند؛
- این روش‌ها ممکن است با استفاده از مکانیزم‌هایی از به دام افتادن فرآیند جستجو در بهینه‌های موضعی جلوگیری کنند؛
- الگوریتم های فراابتکاری، برخلاف روش‌های ابتکاری وابسته به نوع مساله نیستند، به عبارت دیگر میتوان آنها را برای حل طیف گسترده‌ای از مسائل بهینه‌سازی مورد استفاده قرار داد؛
- روش‌های فرا ابتکاری پیشرفته‌تر، از تجربیات و اطلاعات به دست آمده در طول فرآیند جستجو به شکل حافظه برای هدایت جستجو به نواحی پرامیدتر فضای جواب استفاده می‌کنند؛
به طور خلاصه میتوان گفت که الگوریتم های فراابتکاری، راهکارهای پیشرفته و کلی جستجو می‌باشند و گام‌ها و معیارهایی را پیشنهاد می‌کنند که در فرار از دام بهینه‌های موضعی بسیار مؤثر هستند. عامل مهم در این روش‌ها، تعادل پویا بین استراتژی‌های تنوع بخشی و پرقدرت سازی است. تنوع بخشی به جستجوی گسترده در فضای جواب اشاره دارد و پرقدرت سازی به معنی بهره‌برداری از تجربیات به دست آمده در فرآیند جستجو و تمرکز بر نواحی پرامیدتر فضای جواب می‌باشد.
بنابراین با ایجاد تعادل پویا بین این دو استراتژی از یک طرف، جستجو به سمت محدوده‌هایی از فضای جواب سوق داده می‌شود که جواب‌های بهتری در آنها یافت شده است و از طرف دیگر موجب عدم اتلاف زمان بیشتر در بخشی از فضای جواب می‌شود که پیش از این بررسی شده و یا شامل جواب‌های نامرغوب‌تری است.
یکی از شاخص‌های تقسیم‌بندی الگوریتم های فراابتکاری، تعداد جواب‌هایی است که آنها در هر تکرار، تولید و مورد بررسی قرار می‌دهند. بر این اساس روش‌های فر ا ابتکاری به دو گروه روش‌های تک نقطه‌ای و روش‌های جمعیتی تقسیم‌بندی می‌شوند که در اینجا شرح مختصری از هر کدام از این روش‌ها آورده می‌شود.
منبع
الگوریتم های فراابتکاری
ردپای بهینه سازی تقریبا در همه بخش های زندگی ما وجود دارد. از طراحی مهندسی گرفته تا بازارهای مالی، از فعالیت های روزمره تا برنامه ریزی تعطیلات و از علوم کامپیوتری تا کاربردهای صنعتی. در حقیقت ما به طور پیوسته به دنبال راه حل های بهینه برای مسائلی که با آن ها روبرو می شویم، هستیم.
توسعه تکنیک های بهینه سازی از سال ها پیش همچنان ادامه دارد و در نیم قرن اخیر پیشرفت های فراوانی در زمینه روش های بهینه سازی صورت گرفته است. روش ها و الگوریتم های بهینه سازی به دو دسته کلی الگوریتم های قطعی و الگوریتم های احتمالی یا تقریبی تقسیم بندی می شوند. الگوریتم های قطعی قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی آن ها به شدت کاهش می یابد.
الگوریتم های تقریبی قادر به یافتن جواب های نزدیک به بهینه در زمان حل کوتاه برای مسائل بهینه سازی سخت هستند. الگوریتم های تقریبی به دو دسته الگوریتم های ابتکاری و فرا ابتکاری بخش بندی می شوند. دو مشکل اصلی الگوریتم های ابتکاری قرار گرفتن در بهینه محلی و نا توانی برای کاربرد در مسائل گوناگون است.
الگوریتم های فراابتکاری برای رفع مشکلات الگوریتم های ابتکاری ارائه شدند. درواقع این الگوریتم ها یکی از انواع الگوریتم های بهینه سازی احتمالی هستند که دارای راهکارهای برون رفت از بهینه محلی می باشند و برای طیف گسترده ای از مسائل کاربرد دارند. در این بخش مهمترین مباحث مربوط به ر الگوریتم های فراابتکاری در چندین سرفصل مهم و جامع برای پژوهشگران جمع آوری و طبقه بندی شده است.
دسته‌بندی الگوریتم های فراابتکاری
معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتم های فراابتکاری استفاده شود.
-1مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتمهای مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتمهای مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند .
-2الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم های فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم های فراابتکاری نیز از طبیعت الهام گرفته نشده اند .
3-با حافظه و بدون حافظه: برخی از الگوریتم های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
-4قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم های فراابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.
الگوریتم های مبتنی بر یک جواب
-الگوریتم تبرید شبیه سازی شده simulated annealing
-جست وجوی ممنوعه tabu search
-جست و جوی حریصانهGRASP search
-جست و جوی همسایگی متغیرvariable neighborhood search
-جست و جوی محلی هدایت شدهguided local search
-جست و جوی محلی تکرار شوندهinterated local search
الگوریتم های مبتنی بر جمعیت
–الگوریتم ژنتیک 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
منابع