الگوریتم های بهینه سازی
به طور کلی انتخاب و طراحی بهینه در بسیاری از مسائل علمی باعث تولید بهترین محصول با جواب ممکن در یک شرایط خاص می شود. نتیجه بهینه سازی به نوع تعریف مسئله و انتخاب روش مناسب برای حل آن، بستگی دارد. محققان در بیشتر مسائل برای پیاده سازی الگوریتم های بهینه سازی به دنبال پیدا کردن یک تابع هدف به صورت حداقل با حداکثر هستند.
روش ها و الگوریتم های بهینه سازی به دو دسته الگوریتم های دقیق و الگوریتم های تقریبی تقسیم بندی می شوند. الگوریتم های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند، اما در مورد مسائل بهینه سازی سخت و پیچیده کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می یابد، ولی الگوریتم های تقریبی قادر به یافتن جواب های خوب (نزدیک به بهینه) در زمان حل کوتاه برای این گونه مسائل هستند. الگوریتم های تقریبی نیز به دو دسته الگوریتم های ابتکاری و الگوریتم های فرا ابتکاری تقسیم بندی می شوند. دو مشکل اصلی الگوریتم های ابتکاری، قرار گرفتن آنها در بهینه محلی و عدم قابلیت آنها برای کاربرد در مسائل مختلف است. الگوریتم های فرا ابتکاری با فرا ابتکاری برای حل دو مشکل فوق ارائه شده اند. در واقع الگوریتم های فرا ابتکاری، یکی از انواع الگوریتم های بهینه سازی تقریبی هستند که دارای مکانیزم های خروج از بهینه محلی می باشند و همچنین قابل کاربرد در طیف وسیعی از مسائل اند. فرایند طراحی و پیاده سازی الگوریتم های فرا ابتکاری دارای سه مرحله متوالی است که هرکدام از آنها دارای گام های مختلفی اند. برای تکمیل هر گام یک سری فعالیت باید انجام شود تا آن گام کامل شود. مرحله اول آماده سازی است که در آن باید شناخت دقیقی از مسئله ای که می خواهیم حل کنیم به دست آوریم. مرحله بعدی، ساخت نام دارد. مهم ترین اهداف این مرحله انتخاب استراتژی برای حل مسئله، تعریف معیارهای اندازه گیری و طراحی الگوریتم برای استراتژی انتخاب شده است. آخرین مرحله پیاده سازی است که در آن پیاده سازی الگوریتم طراحی شده در مرحله قبل، شامل تنظیم پارامترها، تحلیل عملکرد و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.
دسته بندی الگوریتم های فرا ابتکاری
معیارهای مختلفی می تواند برای طبقه بندی الگوریتم های فرا ابتکاری استفاده شود. مبتنی بر یک جواب و مبتنی بر جمعیت الگوریتم های مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر می دهند، در حالی که در الگوریتم های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب ها در نظر گرفته می شود.
الهام گرفته از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم های فرا ابتکاری از طبیعت الهام گرفته شده اند. در این میان برخی دیگر نیز الهام گرفته از طبیعت نیستند.
با حافظه و بدون حافظه: برخی از الگوریتم های فرا ابتکاری فاقد حافظه اند: به این معنا که این نوع الگوریتمها از اطلاعات به دست آمده در حین جستجو استفاده نمی کنند (به طور مثال، تبرید فلزات شبیه سازی شده، این در حالی است که در برخی از الگوریتم های فرا ابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می کنند) این حافظه اطلاعات به دست آمده در حین جستجو را در خود ذخیره می کند.
قطعی و احتمالی: یک الگوریتم فرا ابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می کند، اما در الگوریتم های فرا ابتکاری احتمالی نظیر آنیل شبیه سازی شده، یا سری قوانین احتمالی در حین جستجو مورداستفاده قرار می گیرد.
از جمله الگوریتم های متداول فرا ابتکاری مبتنی بر یک جواب می توان الگوریتم جستجوی ممنوعه و الگوریتم تبرید فلزات شبیه سازی شده را نام برد. الگوریتم های مبتنی بر جمعیت، جواب های نزدیک به بهینه اصلی را از بین جواب های موجود در مسائل بهینه سازی سخت با الگوبرداری از طبیعت پیدا می کنند. الگوریتم های مبتنی بر جمعیت خود به دو دسته الگوریتم های تکاملی شامل الگوریتم ژنتیک، برنامه ریزی ژنتیک، جهش قورباغه و الگوریتم هوش تجمعی شامل الگوریتم مورچگان، زنبور، ازدحام ذرات و تقسیم می شوند.
از جمله روش های فرا ابتکاری که از هوش تجمعی استفاده می کنند، می توان به موارد زیر اشاره کرد:
- روش بهینه سازی کلونی مورچه ها یا ACO
- الگوریتم پرندگان با روش بهینه سازی ازدحام ذرات PSO
- الگوریتم ژنتیک یا GA
- الگوریتم های جهش قورباغه با SELA
الگوریتم جهش قورباغه
الگوریتم جهش قورباغه از الگوریتم های مهم و پرکاربرد در مجموعه الگوریتم های فراابتکاری است که در بیشتر مقالات و پایان نامه ها استفاده می شود. الگوریتم جهش قورباغه مخلوط شده یا Shuffled Frog Leaping Algorithm (به اختصار SFLA)، یکی از الگوریتم های بهینه سازی فرا ابتکاری است که از رفتار اجتماعی قورباغه ها الهام گرفته شده است، و از نظر طبقه بندی، در میان الگوریتم های رفتاری یا الگوریتم های ممتیک (Memetic Algorithms) قرار می گیرد. الگوریتم جهش ترکیبی قورباغه یک الگوریتم مبتنی بر همتیک متأهيوريستیک است. الگوریتم ممتیک، یک الگوریتم مبتنی بر جمعیت است که برای مسائل بهینه سازی پیچیده و بزرگ مورداستفاده قرار می گیرد. ایده اصلی این الگوریتم، به کار گیری یک روش جستجوی محلی در درون ساختار الگوریتم ژنتیک برای بهبود کار آبی فرآیند تشدید هنگام جستجو است. الگوریتم ممتیک در ابتدا مجموع جوابهای اولیه را رمزگذاری می کند، آنگاه ابن الگوریتم میزان مطلوبیت هر یک از جوابها را بر اساس یک تابع برازندگی را محاسبه کرده و جواب های جدیدی را تولید می کند.
الگوریتم SFLA از نحوه جستجوی غذای گروههای قورباغه سرچشمه می گیرد. این الگوریتم برای جستجوی محلی میان زیر گروههای قورباغه از روش نموممتیک استفاده می کند. الگوريتم جهش ترکیبی قورباغه از استراتژی ترکیب استفاده می کند و امکان مبادله پیام در جستجوی محلی را فراهم می سازد. این الگوریتم مزایای الگوریتم نموممتیک و بهینه سازی گروه ذرات را ترکیب می کند. در الگوریتم جهش ترکیبی قورباغه نه تنها در جستجوی محلی بلکه در جستجوی سراسری نیز پیامها مبادله می شوند. بدین ترتیب جستجوی محلی و سراسری به خوبی در این الگوریتم ترکیب می شوند. جستجوی محلی امکان انتقام مم را میان افراد ممکن می سازد و استراتژی ترکیب امکان انتقال مم را میان كل جمعیت ممکن می سازد. مانند الگوریتم ژنتیک و بهینه سازی گروه ذرات الگوریتم جهش ترکیبی قورباغه یک الگوریتم بهینه سازی مبتنی بر گلونی است. الگوریتم جهش ترکیبی قورباغه قابلیت بالایی برای جستجوی سراسری دارد و پیاده سازی آن آسان است. الگوريتم جهش ترکیبی قورباغه می تواند بسیاری از مسائل غیر خطی، غیرقابل تشخیص و چند حالته را حل کند.
این الگوریتم مزایای دو الگوریتم های بر پایه ژنتیک مانند همتیک و الگوریتم های بر اساس رفتار اجتماعی مانند الگوریتم دسته پرندگان را باهم ترکیب کرده است. لذا تلاش می کند که یک تعادل بین بررسی گسترده در فضای جواب های محتمل ایجاد کند. در این الگوریتم جمعیت شامل یک دسته از قورباغه ها (جواب ها) می شود، هر قورباغه ساختاری شبیه به کروموزوم در الگوریتم ژنتیک را خواهد داشت. کل جمعیت قورباغه ها در دسته های کوچکتری تقسیم بندی می شوند، هر دسته نماینده انواع مختلفی از قورباغه ها هستند که در محل های مختلفی از فضای جوابها گسترده شده اند. سپس هر دسته از این قورباغه ها شروع به یک جستجوی محلی دقیق در اطراف محل استقرار خود می کنند. هر قورباغه در هر دسته هم تحت تأثیر دیگر اعضای گروه خود قرار می گیرد و هم از گروه های دیگر متاثر می شود. بعد از چند مرحله بعد آمیزش انجام می گیرد و اطلاعات بین تمامی گروه ها پخش میشود تا شرط همگرایی برقرار شود. نحوه یافتن بهترین جواب در این الگوریتم از دو مرحله جستجو سراسری و محلی تشکیل شده است. تشکیل جمعیت اولیه ابتدا تعداد دسته های موردنظر و تعداد قورباغه هایی که می بایست در هر دسته قرار گیرند مشخص می شوند. اگر تعداد دسته ها و تعداد قورباغه های موجود در هر دسته 1 در نظر گرفته شود، در این صورت تعداد کل نمونه ها برابر F = mn خواهد بود. سپس تابع هزینه برای تمام نمونه های تولیدشده محاسبه می گردد. مرتب سازی و توزیع تعداد کل قورباغه های انتخابی بر اساس تابع هزینه محاسبه شده، مرتب می شوند به گونه ای که نمونه با کمترین تابع هزینه و بهترین موقعیت در اولین مکان قرار گیرد. موقعیت بهترین قورباغه در کل جمعیت ذخیره می گردد. سپس کل قورباغه ها در بین m دسته انتخابی تقسیم می شوند به قسمتی که در هر دسته 1 قورباغه قرار گیرد، نحوه تقسیم بدین صورت می باشد که در جمعیت مرتب شده اولین عضو در اولین دسته قرار می گیرد، دومین عضو در دومین دسته و به همین ترتیب ادامه می یابد تا امین عضو انتخاب شده و در mامین دسته قرار گیرد، سپس عضو 1+m ام در اولین دسته قرار خواهد گرفت و به همین ترتیب روند تقسیم قورباغه ها ادامه می یابد.
تکامل دسته ها از تقسیم قورباغه ها در بین دسته های مختلف هر دسته به تعداد از قبل تعیین شده مراحل تکامل را تکرار می کند. پس از این مرحله، تمام قورباغه ها ترکیب شده و مرحله جستجوی سراسری دوباره تکرار می شود.
جدول خلاصه الگوریتم فراابتکاری جهش قورباغه
جهش قورباغه Shuffled Frog Leaping(SFLA) |
نام الگوریتم |
مبتنی بر جمعیت |
مبتنی بر جمعیت یا نقطه محور |
تبادل اطلاعات بین گروه ها می باشد، که بر اساس آن، بعد از هر جستجوی محلی در گروه ها، اطلاعات بدست آمده بین گروه ها با هم مقایسه می شود |
تمرکز |
تکنیک جستجوی محلی است و بر اساس آن قورباغه ها در هر گروه با تبادل اطلاعات، موقعیت خود را نسبت به غذا (بهترین جواب) بهبود می دهند |
تنوع |
توازن بین مبادله پیام سراسری و جستجوی محلی به الگوریتم امکان می دهد تا به راحتی از مینیمم محلی پرش کند و تا دستیابی به بهینه سازی توسعه یابد |
فرار از بهینه محلی |
موقعیت جدید بدترین جواب در امتداد بهترین و بدترین جواب قرار می گیرند که باعث کاهش سرعت همگرایی می شود |
نحوه ی حرکت |
انعطاف پذیری و قدرت جستجوی الگوریتم را تضمین می کند |
نحوه ی تصادف سازی |
بحث روی پارامتر ها |
|
معيار توقف الگوريتم ميتواند بر مبناي ثابت ماندن تغييرات برازندگي بهترين جواب يا تكرار الگوريتم تا يك تعداد مشخص انتخاب شود |
شرایط توقف |
توليد جمعيت اوليه دسته بندي جستجوي محلي |
خلاصه ای از گام های الگوریتم قورباغه |
مطالب مشابه و پیشنهادی: