الگوریتم جهش قورباغه ای

الگوریتم جهش قورباغه ای

چکیده– الگوریتم جهش ترکیبیِ قورباغه (SFLA) یک الگوریتم تکاملی و مبتنی بر جمعیتِ متاهیوریستیک جدید است. این الگوریتم سریع است و قابلیت جستجوی سراسری بسیار خوبی دارد. در این مقاله در ابتدا قاعده ­ی کلی الگوریتم SFLA مطرح می­شود و سپس پارامترهای آن مورد تحلیل قرار می­گیرند.  بوسیله­ ی آزمایش، پارامترها به گونه­ ای انتخاب می­شوندکه تاثیر مثبتی بر SFLA داشته باشند. الگوریتم SFLA با استفاده از تابع آزمایش، با الگوریتم ژنتیک (GA) و بهینه ­سازیِ گروه ذرات (PSO) مقایسه می­شود. آزمایشات نشان می­دهند که دقت و قابلیت جستجوی سراسریِ SFLA از GA و PSO بهتر است.

مقدمه

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

الگوریتم ترکیبی جهش قورباغه

قاعده­ی کلیِ SFLA

الگوریتم SFLA ترکیب روش قطعی و روش تصادفی است. روش قطعی به الگوریتم امکان می­دهد تا پیام­ها را به صورت کارایی مبادله کند. روش تصادفی انعطاف­ پذیری و مقاومت الگوریتم را تضمین می­­کند. الگوریتم با انتخاب تصادفی گروه­های قورباغه شروع می­شود. گروه­ های قورباغه به چندین زیرگروه تقسیم می­شوند. هر یک از این زیرگروه­ها می­توانند جستجوی محلی را به صورت مستقل و با روش­ متفاوتی انجام دهند. قورباغه­ های موجود در یک زیرگروه می­توانند بر روی سایر قورباغه ­های موجود در همان زیرگروه اثر بگذارند. بدین تریب قورباغه­ های موجود در یک زیرگروه تکامل می­یابند. تکامل ممتیک کیفیت ممتیکِ قورباغه­ های منفرد را بهبود و قابلیت دستیابی به هدف را افزایش می­دهد. برای رسیدن به یک هدف خوب می­توان وزنِ قورباغه ­ها­ی خوب را افزایش و وزن قورباغه ­های بد را کاهش داد. بعد از تکامل برخی از ممتیک­ها، زیرگروه­ها با هم ترکیب می­شوند. بواسطه­ ی ترکیب ممتیک­ها در حوزه­ ی سراسری بهینه می­شوند و بوسیله ­ی مکانیزم ترکیب زیرگروه­های قورباغه­ ی جدیدی ایجاد می­شود. ترکیب، کیفیتِ ممتیک­ هایی که تحت تاثیرِ زیرگروه­های مختلف قرار می­گیرند را افزایش می­دهد. جستجوی محلی و جستجوی سراسری تا برآورده شدن شرط همگرایی ترکیب می­شوند. توازن بین مبادله پیام سراسری و جستجوی محلی به الگوریتم امکان می­دهد تا به راحتی از مینیمم محلی پرش کند  و تا دستیابی به بهینه­ سازی توسعه یابد. یکی از خصیصه­ های  الگوریتم SFLA همگرایی سریع آن است.

شرح الگوریتم SFLA

جسجوی سراسری

۱٫مقداردهی اولیه :

M , Nرا انتخاب کن.M  تعداد Memeplex ها و  n تعداد قورباغه های موجود در هر  memeplexرا نشان میدهد بنابراین اندازه کل جمعیت موجود در آبگیر از طریق رابطه f=m.nبدست می آید.

۲٫تولید جمعیت مجازی

از فضای شدنی، F  قورباغه مجازی (U(1),U(2),…,U(F)) را نمونه برداری کن.مقدار شایستگی  ƒ(i)هر قورباغه U(i) را به ازاء هر(U_i^d،…،U_i²،U_i¹  U(i) = (،محاسبه کن. d تعداد متغیر های تصمیم است.

۳) درجه بندی قورباعه ها

قورباغه هارا بر اساس شایستگی شان به صورت نزولی مرتب و در آرایه یX={U(i),f(i),i=1…,F} ذخیره کن. موقعیت بهترین قورباغه P_x در کل جمعیت را ثبت کن.(که(۱)U  = P_x).

۴) تقسیم قورباغه ها در memeplex  ها

آرایه ی X را در m،, Y^m) memeplex…,           ,Y²¹Y) که هر کدام  شامل n  قورباغه هستند. تقسیم کن.

۵)تکامل ممتیک در هر memeplex

هر memeplex (… , m  ,۱=k , (y^kبوسیله ی جستجو ی محلی (الگوریتم جهش قورباغه) که در ادامه توضیح داده شده است، تکامل میابد.

۶) ترکیب memeplex ها

بعد از این که در  هر memeplex تعداد معینی تکامل ممتیک انجام شد، memeplex ها را  (Y^m , …         , (Y¹در X قرار بده ، بطوریکه رابطه ی {m , …, 1= k , Y^K) = X برقرار  باشد.موقعیت بهترین قورباغه ی موجود در جمعیت (P_x)را بهنگام کن.

۷)بررسی همگرایی

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

جستجوی محلی (الگوریتم جهش قورباغه):

در مرحله ی پنجم جستجوی سراسری، تکامل هر memeplex به صورت مستقل Nبار انجام می شود. بعد از این که memeplex ها تکامل یافتند، الگوریتم جهت انجام ترکیب به جستجوی سراسری باز می گردد. در ادامه جزئیات جستجوی محلی در هر memeplex تشریح می شود:

۱)مقدار دهی اولیه

im و ln را برابر صفر قرار بده ،im تعداد memeplex ها و ln تعداد مراحل تکامل را می شمارد.

۲)۱+im=im

۳)۱+iN=iN

۴)ایجاد یک submemeplex

هدف قورباغه ها این است که با بهبود مم هایشان به سمت موقعیت های بهینه حرکت کنند.روش انتخاب submemeplex تخصیص وزن های بیشتر به قورباغه هایی که کارایی بالاتر دارند و وزن های کمتر به قورباغه هایی با مقادیر کارایی کمتر است. وزن ها با توزیع احتمال مثلثی تخصیص داده می شوند، یعنی n , … , 1= j , (1+n) n / (j-1+n) 2=P_i. برای ساخت آرایه ی submemeplex (Z) از هر n قورباغه ی موجود در هر memeplex تعداد q قورباغه به صورت تصادفی انتخاب میشوند. قورباغه های موجود در submemeplex بر حسب میزان شایستگی شان به صورت نزولی مرتب می شوند. موقعیت بهترین قورباغه و بدترین قورباغه ی موجود در submemeplex به ترتیب با P_B و P_W مشخص میشوند.

۵) تصحیح موقعیت بدترین قورباغه

موقعیت جدید بدترین قورباغه ی موجود در submemplex (قورباغه ای که بدترین مقدار کارایی را دارد) از طریق رابطه ی S+P_W= U(q) محاسبه می شود. ُُS اندازه ی گام (میزان جهش) قورباغه است و از طریق رابطه ی زیر به دست می آید:

اگر موقعیت جدید بهتر از موقعیت قبلی است، آنگاه U(q) جدید را جایگزین U(Q) قبلی کن و به مرحله ی ۸ از جستجوی محلی برو.در غیر این صورت به مرحله ی ۶ جستجوی محلی برو.

۶)محاسبه ی اندازه ی گام بوسیله ی P_X

اگر در مرحله ی۵ نتیجه ی بهتری تولید نشد، آنگاه اندازه ی گام قورباغه از طریق رابطه ی زیر محاسبه میشود:

و موقعیت جدید U(q) بوسیله ی رابطه ی S   + P_W = (q)U محاسبه میشود. اگر U(q) در بین فضای شدنی باشد، مقدار کارایی جدید f(q) محاسبه می شود. چنانچه f(q) جدید بهتر از قبلی است ، آنگاه  U(q) جدید را جایگزین U(q) قبلی کن و به مرحله هشتم جستجوی محلی برو. در غیر این صورت به مرحله ی هفتم جستجوی محلی برو.

۷)سانسور

اگر موقعیت جدید در ناحیه ی شدنی نیست یا بهتر از موقعیت قبلی نیست ، به صورت تصادفی یک قورباغه ی جدید (r) در یک مکان شدنی تولید و جایگزین قورباغه ای می شود که موقعیت جدیدش برای پیشروی مناسب نیست می شود.f(r) را محاسبه کن و U(q) را برابر r و f(q) را برابر f(r) قرار بده.

۸)بهنگام کردن memeplex

بعد از تغییر ممتیک بدترین قورباغه ی موجود در submemeplex ،قورباغه های موجود در Z را در موقعیت اصلیشان در Y^im قرار بده. Y^im را براساس مقدار کارایی به صورت نزولی مرتب کن.

۹)اگر N>iN است، به مرحله سوم جستجوی محلی برو.

۱۰)اگر m> im است،به مرحله اول جستجوی محلی برو. در غیر این صورت جهت ترکیب memeplex ها به جستجوی سراسری باز گرد.