الگوریتم بهینه سازی جهش قورباغه SFLA

از نام‌های دیگر الگوریتم بهینه سازی جهش قورباغه، می‌توان به الگوریتم قورباغه و الگوریتم جهش قورباغه و الگوریتم SFLA اشاره نمود. این الگوریتم در ابتدا توسط Eusuff و Lansey در سال ۲۰۰۳ مطرح شد هر چند مقالات زیادی پس از برای بهبود این الگوریتم ارائه شده است

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

الگوریتم SFLA یک الگوریتم مبتنی بر ممتیک متأهیوریستیک است. الگوریتم ممتیک، یک الگوریتم مبتنی بر جمعیت است که برای مسائل بهینه سازی پیچیده و بزرگ مورداستفاده قرار می‌گیرد. ایده اصلی این الگوریتم، به کار گیری یک روش جستجوی محلی در درون ساختار الگوریتم ژنتیک برای بهبود کار آبی فرآیند تشدید هنگام جستجو است. الگوریتم ممتیک در ابتدا مجموع جواب‌های اولیه را رمزگذاری می‌کند، آنگاه این الگوریتم میزان مطلوبیت هر یک از جواب‌ها را بر اساس یک تابع برازندگی را محاسبه کرده و جواب‌های جدیدی را تولید می‌کند.

الگوریتم SFLA از نحوه جستجوی غذای گروه قورباغه‌ها الهام می‌گیرد. این الگوریتم برای جستجوی محلی میان زیر گروه قورباغه‌ها از روش نموممتیک استفاده می‌کند. الگوریتم جهش ترکیبی قورباغه از استراتژی ترکیب استفاده می‌کند و امکان مبادله پیام در جستجوی محلی را فراهم می‌سازد.

این الگوریتم مزایای الگوریتم نموممتیک و بهینه سازی گروه ذرات را ترکیب می‌کند. در الگوریتم جهش ترکیبی قورباغه نه تنها در جستجوی محلی بلکه در جستجوی سراسری نیز پیام‌ها مبادله می‌شوند. بدین ترتیب جستجوی محلی و سراسری به خوبی در این الگوریتم ترکیب می‌شوند. الگوریتم جهش ترکیبی قورباغه قابلیت بالایی برای جستجوی سراسری دارد و پیاده سازی آن آسان است. الگوریتم جهش ترکیبی قورباغه می‌‎تواند بسیاری از مسائل غیر خطی، غیرقابل تشخیص و چند حالته را حل کند.

الگوریتم بهینه سازی جهش قورباغه SFLA

کلیک کنید

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

این الگوریتم مزایای دو دسته از الگوریتم های مبتنی بر ژنتیک ( مانند ممتیک ) و الگوریتم‌های مبتنی بر رفتار اجتماعی ( مانند الگوریتم دسته پرندگان PSO ) را باهم ترکیب کرده است و سعی می‌کند یک تعادل بین بررسی گسترده در فضای جواب‌های احتمالی ایجاد کند. در این الگوریتم جمعیت شامل یک دسته از قورباغه‌ها (جواب‌ها) می‌شود، هر قورباغه ساختاری شبیه به کروموزوم در الگوریتم ژنتیک را خواهد داشت.

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

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

پاورپوینت الگوریتم‌های ژنتیک

کلیک کنید

تشکیل جمعیت اولیه

در تشکیل جمعیت اولیه ابتدا تعداد دسته‌های موردنظر و تعداد قورباغه‌هایی که می‌بایست در هر دسته قرار گیرند مشخص می‌شوند. اگر تعداد دسته‌ها و تعداد قورباغه‌های موجود در هر دسته ۱ در نظر گرفته شود، در این صورت تعداد کل نمونه‌ها برابر F = m*n خواهد بود.

سپس تابع هزینه برای تمام نمونه‌های تولیدشده محاسبه می‌گردد. مرتب سازی و توزیع تعداد کل قورباغه‌های انتخابی بر اساس تابع هزینه محاسبه شده، مرتب می‌شوند به گونه‌ای که نمونه با کم‌ترین تابع هزینه و بهترین موقعیت در اولین مکان قرار گیرد. موقعیت بهترین قورباغه در کل جمعیت ذخیره می‌گردد. سپس کل قورباغه‌ها در بین m دسته انتخابی تقسیم می‌شوند به قسمتی که در هر دسته ۱ قورباغه قرار گیرد.

نحوه تقسیم بدین صورت می‌باشد که در جمعیت مرتب شده اولین عضو در اولین دسته قرار می‌گیرد، دومین عضو در دومین دسته و به همین ترتیب ادامه می‌یابد تا امین عضو انتخاب شده و در mامین دسته قرار گیرد، سپس عضو ۱+m ام در اولین دسته قرار خواهد گرفت و به همین ترتیب روند تقسیم قورباغه‌ها ادامه می‌یابد.

تکامل دسته‌ها از تقسیم قورباغه‌ها در بین دسته‌های مختلف هر دسته به تعداد از قبل تعیین شده مراحل تکامل را تکرار می‌کند. پس از این مرحله، تمام قورباغه‌ها ترکیب شده و مرحله جستجوی سراسری دوباره تکرار می‌شود.

فلوچارت الگوریتم

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

استراتژی فرا اکتشافی الگوریتم SFLA در دو مرحله اصلی اکتشاف سراسری Global exploration و اکتشاف محلی یا Local exploration طبق مراحل زیر خلاصه می‌شود.

مراحل اکتشاف سراسری Global exploration

مرحله اول:  مقداردهی اولیه

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…,     ,Ym Y) که هر کدام  شامل n  قورباغه هستند. تقسیم کن.

مرحله پنجم: تکامل ممتیک در هر memeplex

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

مرحله ششم: ترکیب memeplex ها

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

مرحله هفتم : بررسی همگرایی

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

مراحل اکتشاف محلی یا Local exploration

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

مرحله اول : مقدار دهی اولیه

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

مرحله دوم : ۱+im=im

مرحله دوم : ۱+iN=iN

مرحله چهارم : ایجاد یک submemeplex

هدف قورباغه‌ها این است که با بهبود مم‌هایشان به سمت موقعیت‌های بهینه حرکت کنند. روش انتخاب submemeplex تخصیص وزن‌های بیشتر به قورباغه‌هایی که کارایی بالاتر دارند و وزن‌های کمتر به قورباغه‌هایی با مقادیر کارایی کمتر است. وزن‌ها با توزیع احتمال مثلثی تخصیص داده می‌شوند، یعنی n , … , ۱= 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 قبلی کن و به مرحله‌ی ۸ از جستجوی محلی برو. در غیر این صورت به مرحله‌ی ۶ جستجوی محلی برو.

حل فروشنده دوره گرد با الگوریتم جهش قورباغه SFLA در متلب

کلیک کنید

ادامه …

مرحله ششم : محاسبه‌ی انداز‌ه‌ی گام بوسیله‌ی 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 ها به جستجوی سراسری باز گرد.