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

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

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

 

الگوریتم بهینه سازی جهش قورباغه یا Shuffled Frog Leaping Algorithm  (به اختصار SFLA)، یکی از الگوریتم های بهینه سازی فرا ابتکاری است که از رفتار اجتماعی قورباغه ها در طبیعت الهام گرفته شده است، و از نظر دسته بندی، در میان الگوریتم های رفتاری یا الگوریتم های ممتیک (Memetic Algorithms) قرار می گیرد. از نام های دیگر الگوریتم بهینه سازی جهش قورباغه، می توان به الگوریتم قورباغه و الگوریتم جهش قورباغه و الگوریتم SFLA اشاره نمود. این الگوریتم در ابتدا توسط Eusuff و Lansey در سال 2003 مطرح شد هر چند مقالات زیادی پس از برای بهبود این الگوریتم ارائه شده است. در پایین لینک دانلود مقاله اصلی الگوریتم بهینه سازی قورباغه قرار داده شده است.

دانلود مقاله اصلی

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

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

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

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

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

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

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

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

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

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

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

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

 

مراحل الگوریتم جهش قورباغه 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 را به ازاء هر (Uid،…،Ui2،Ui1 ) U(i) =  ، محاسبه کن. d تعداد متغیر های تصمیم است.

مرحله سوم: درجه بندی و مرتب سازی قورباعه ها

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

مرحله چهارم: تقسیم قورباغه ها در memeplex ها

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

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

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

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

بعد از این که در  هر memeplex تعداد معینی تکامل ممتیک انجام شد، memeplex ها را  (Ym , …         , (Y1در X قرار بده ، بطوریکه رابطه ی {m , …, 1= k , YK) = X برقرار  باشد. موقعیت بهترین قورباغه ی موجود در جمعیت (Px)را بهنگام کن.

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

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

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

در مرحله ی پنجم جستجوی سراسری، تکامل هر 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=Pi. برای ساخت آرایه ی (submemeplex (Z از هر n قورباغه ی موجود در هر memeplex تعداد q قورباغه به صورت تصادفی انتخاب می شوند. قورباغه های موجود در submemeplex بر حسب میزان شایستگی شان به صورت نزولی مرتب می شوند. موقعیت بهترین قورباغه و بدترین قورباغه ی موجود در submemeplex به ترتیب با PB و PW مشخص می شوند.

مرحله پنجم : تصحیح موقعیت بدترین قورباغه

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

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

ادامه …

مرحله ششم : محاسبه ی اندازه ی گام بوسیله ی PX

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

و موقعیت جدید (U(q  بوسیله ی رابطه ی S   + P= (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 را در موقعیت اصلیشان در Yim قرار بده. Yim را براساس مقدار کارایی به صورت نزولی مرتب کن.

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

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

 


مطالب زیر را حتما بخوانید

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.