الگوریتم ممتیک متاهیوریستیکِ جهش ترکیبی قورباغه
پژوهشی مبتنی بر الگوریتم ممتیک متاهیوریستیکِ جهش ترکیبی قورباغه
چکیده- الگوریتم جهش ترکیبیِ قورباغه (SFLA) یک الگوریتم تکاملی و مبتنی بر جمعیتِ متاهیوریستیک جدید است. این الگوریتم سریع است و قابلیت جستجوی سراسری بسیار خوبی دارد. در این مقاله در ابتدا قاعدهی کلی الگوریتم SFLA مطرح میشود و سپس پارامترهای آن مورد تحلیل قرار میگیرند. بوسیلهی آزمایش، پارامترها به گونهای انتخاب میشوندکه تاثیر مثبتی بر SFLA داشته باشند. الگوریتم SFLA با استفاده از تابع آزمایش، با الگوریتم ژنتیک (GA) و بهینهسازیِ گروه ذرات (PSO) مقایسه میشود. آزمایشات نشان میدهند که دقت و قابلیت جستجوی سراسریِ SFLA از GA و PSO بهتر است.
1.مقدمه
الگوریتم جهش ترکیبیِ قورباغه (SFLA) یک الگوریتم مبتنی بر ممتیک متاهیوریستیک است. این الگوریتم در سالهای اخیر توسط Eusuff و Lansey ایجاد شد. الگوریتم SFLA از نحوهی جستجوی غذای گروههای قورباغه سرچشمه میگیرد. این الگوریتم برای جستجوی محلی میان زیرگروههای قورباغه از روش نمو ممتیک استفاده میکند. SFLA از استراتژیِ ترکیب استفاده میکند و امکان مبادله پیام در جستجوی محلی را فراهم میسازد. این الگوریتم مزایای الگوریتم نمو ممتیک و بهینهسازیِ گروه ذرات (PSO)[1] را ترکیب میکند. در SFLA نه تنها در جستجوی محلی بلکه در جستجوی سراسری نیز پیامها مبادله میشوند. بدین ترتیب جستجوی محلی و سراسری به خوبی در این الگوریتم ترکیب میشوند. جستجوی محلی امکان انتقال مم را میان افراد ممکن میسازد و استراتژیِ ترکیب امکان انتقال مم را میان کل جمعیت ممکن میسازد. مانند الگوریتم ژنتیک (GA) و بهینهسازی گروه ذرات (PSO) الگوریتم جهش ترکیبیِ قورباغه یک الگوریتم بهینهسازیِ مبتنی بر کولونی است. SFLA قابلیت بالایی برای جستجوی سراسری دارد و پیادهسازیِ آن آسان است. الگوریتم SFLA میتواند بسیاری از مسائل غیرخطی، غیرقابلتشخیص[2] و چندحالته[3] را حل کند. این الگوریتم به مراتب برای حل مسالهی توزیع منابع آبی بکارگرفته میشود.
2.الگوریتم ترکیبی جهش قورباغه
A. قاعدهی کلیِ SFLA
الگوریتم SFLA ترکیب روش قطعی و روش تصادفی است. روش قطعی به الگوریتم امکان میدهد تا پیامها را به صورت کارایی مبادله کند. روش تصادفی انعطافپذیری و مقاومت الگوریتم را تضمین میکند. الگوریتم با انتخاب تصادفی گروههای قورباغه شروع میشود. گروههای قورباغه به چندین زیرگروه تقسیم میشوند. هر یک از این زیرگروهها میتوانند جستجوی محلی را به صورت مستقل و با روش متفاوتی انجام دهند. قورباغههای موجود در یک زیرگروه میتوانند بر روی سایر قورباغههای موجود در همان زیرگروه اثر بگذارند. بدین تریب قورباغههای موجود در یک زیرگروه تکامل مییابند. تکامل ممتیک کیفیت ممتیکِ قورباغههای منفرد را بهبود و قابلیت دستیابی به هدف را افزایش میدهد. برای رسیدن به یک هدف خوب میتوان وزنِ قورباغههای خوب را افزایش و وزن قورباغههای بد را کاهش داد. بعد از تکامل برخی از ممتیکها، زیرگروهها با هم ترکیب میشوند. بواسطهی ترکیب ممتیکها در حوزهی سراسری بهینه میشوند و بوسیلهی مکانیزم ترکیب زیرگروههای قورباغهی جدیدی ایجاد میشود. ترکیب، کیفیتِ ممتیکهایی که تحت تاثیرِ زیرگروههای مختلف قرار میگیرند را افزایش میدهد. جستجوی محلی و جستجوی سراسری تا برآورده شدن شرط همگرایی ترکیب میشوند. توازن بین مبادله پیام سراسری و جستجوی محلی به الگوریتم امکان میدهد تا به راحتی از مینیمم محلی پرش کند و تا دستیابی به بهینهسازی توسعه یابد. یکی از خصیصههای الگوریتم SFLA همگرایی سریع آن است.