الگوریتم جهش قوباغه یا الگوریتم SFLA : الگوریتمی برای حل مسائل بهینه سازی، که از رفتار اجتماعی قورباغه ها در طبیعت الهام گرفته شده است.
الگوریتم جهش قورباغه مخلوط شده یا SFLA که مخفف عبارت ، Shuffled Frog Leaping Algorithm ، می باشد ؛ یک الگوریتم بهینه سازی و فراابتکاری است که با الگو برداری از رفتار قورباغه ها ابداع شده است.
پیشینه الگوریتم قوباغه
الگوریتم قورباغه ، نسخه ای توسعه یافته از الگوریتم Shuffled Complex Evolution می باشد که به اختصار به آن SCE گفته میشود و بنام الگوریتم تکاملی مجتمع های مخلوط شده شناخته میشود، می باشد.
خود الگوریتم SCE نیز ترکیبی از قابلیت های الگورتیم ژنتیک، با قابلیت جستجوی تصادفی الگورتیم CRS به معنی جستجوی تصادفی کنترل شده می باشد. به همین جهت میتوان آن را در دسته الگوریتم های ممتیک قرار داد.
الگوریتم قوباغه ، در واقع همان الگوریتم SCE است با این تفاوت که نخبه گرایی یا Elitism و هوش جمعی یا Swarm Intelligence به آن اضافه شده است.
الگوریتم جهش قورباغه یک الگوریتم ممتیک است :
الگوریتم SFLA نیز یک الگوریتم ممتیک به حساب می آید، الگوریتم ممتیک در مقابل الگوریتم ژنتیک مطرح شد.
تفاوت الگوریتم ژنتیک و ممتیک:
- در الگوریتم ژنیتک ، طبق نظریه تکامل داروین ، صفات و ویژگی ها از والدین به فرزندان به ارث میرسد.
- در الگوریتم ممتیک، طبق نظریه تکامل لامارک ، صفات و ویژگی ها ی فرد با جستجو در اطراف خود (جستجوی محلی) به دست می آید.
- در الگوریتم ممتیک، تکامل علاوه در جمعیت، بصورت فردی نیز پیش میرود.
- به الگوریتم های ممتیک ، الگوریتم های ترکیبی یا الگورتیم های ژنتیک محلی نیز گفته میشود.
1) ابتدا پارامترهاي اولیه الگوریتم مقداردهی میشوند
2) جمعیت اولیه (قورباغه ها) به صورت تصادفی تولید میشود.
3) شایستگی هر عضو محاسبه میشود
4) تمام قورباغه ها بر اساس میزان شایستگی شان به صورت نزولی، مرتب می شوند
5) قورباغه ها به چند گروه (MemePlex) تقسیم می شوند به این صورت که قورباغه با بهترین شایستگی در گروه اول ، قورباغه دوم در گروه دوم ،و قورباغه m ام در گروه m ام قرار میگیرد به همین ترتیب قورباغه m+1 ام در گروه اول و .. قرار میگیرند همانند شکل زیر
6) جستجوي محلی براي جهش قورباغه هايی با بدترین شایستگی به سمت قورباغه هايی با بهترین شایستگی صورت می پذیرد. این جهش مطابق روابط ( 1) و ( 2) می باشد.
که در رابطه فو قxb و xw به ترتیب، قورباغه هاي با بدترین و بهترین شایستگی در گروه خود می باشند.
Dمقدار جهش ضعیف ترین قورباغه به سمت بهترین عضو گروه ،
و Dmaxبیشترین حد مجاز براي جهش قورباغه
و rand ،عددي تصادفی در بازه [ 1 و 0] می باشد.
پس از اعمال تغییرات فوق در صورتی که قورباغه جدید داراي پاسخ بهتري نسبت به بدترین قورباغه گروه داشته باشد، جایگزین آن می گردد . در غیر این صورت همین اعمال باجایگزینی Xg با Xbتکرار می گردد. اگر با اعمال تغییر فوق پاسخ مناسب تري یافت نگردید، یک جواب به صورت تصادفی تولید کرده و آن را جایگزین بدترین عضو گروه می نماییم . این روند براي تعداد تکرار مشخص شده ادامه می یابد تا در نهایت شرایط اتمام الگوریتم حاصل گردد.
فلوچارت الگوریتم جهش قورباغه، یا قورباغه جهنده:
ویژگی های الگوریتم جهش قورباغه
- الگوریتم SFLA از نحوه جستجوی غذای گروههای قورباغه سرچشمه می گیرد.
- الگوريتم جهش ترکیبی قورباغه از استراتژی ترکیب استفاده می کند
- و امکان مبادله پیام در جستجوی محلی را فراهم می سازد.
- در الگوریتم جهش ترکیبی قورباغه نه تنها در جستجوی محلی بلکه در جستجوی سراسری نیز پیامها مبادله می شوند.
- جستجوی محلی امکان انتقام مم را میان افراد ممکن می سازد.
- و استراتژی ترکیب امکان انتقال مم را میان كل جمعیت ممکن می سازد.
- در این الگوریتم جمعیت شامل یک دسته از قورباغه ها (جواب ها) می شود،
- هر قورباغه ساختاری شبیه به کروموزوم در الگوریتم ژنتیک را خواهد داشت.
- کل جمعیت قورباغه ها در دسته های کوچکتری تقسیم بندی می شوند.
- هر دسته نماینده انواع مختلفی از قورباغه ها هستند که در محل های مختلفی از فضای جوابها گسترده شده اند.
- سپس هر دسته از این قورباغه ها شروع به یک جستجوی محلی دقیق در اطراف محل استقرار خود می کنند.
- هر قورباغه در هر دسته هم تحت تأثیر دیگر اعضای گروه خود قرار می گیرد و هم از گروه های دیگر متاثر می شود.
بعد از چند مرحله بعد آمیزش انجام می گیرد و اطلاعات بین تمامی گروه ها پخش میشود تا شرط همگرایی برقرار شود.
نحوه یافتن بهترین جواب در این الگوریتم از دو مرحله جستجو سراسری و محلی تشکیل شده است.
نحوه بهینه سازی توسط الگوریتم جهش قورباغه
ابتدا تعداد دسته های موردنظر و تعداد قورباغه هایی که می بایست در هر دسته قرار گیرند مشخص می شوند.
- تعداد دسته ها را m عدد در نظر میگیریم.
- تعداد قورباغه های موجود در هر دسته را n عدد فرض میکنیم.
- تعداد کل نمونه ها (قورباغه ها) برابر F = m*n خواهد بود.
گام اول: تعداد F راه حل (قورباغه) تولید میشود.
گام دوم : تابع هزینه برای تمام نمونه های تولیدشده محاسبه می گردد.
گام سوم :مرتب سازی و توزیع قورباغه ها:
کل قورباغه های انتخابی بر اساس تابع هزینه محاسبه شده، مرتب می شوند به گونه ای که:
- نمونه با کمترین تابع هزینه و بهترین موقعیت در اولین مکان قرار گیرد (مرتب سازی نزولی).
موقعیت بهترین قورباغه در کل جمعیت (بعنوان بهترین جواب فعلی) ذخیره می گردد.
سپس کل قورباغه ها در بین m دسته انتخابی تقسیم می شوند به قسمتی که در هر دسته n قورباغه قرار گیرد،
نحوه تقسیم قورباغه ها در دسته ها بدین صورت می باشد که :
- در جمعیت مرتب شده اولین عضو در اولین دسته قرار می گیرد،
- دومین عضو در دومین دسته
- و به همین ترتیب ادامه می یابد تا امین عضو انتخاب شده و در m امین دسته قرار گیرد.
حال همین روال مجددا تکرار میشود یعنی عضو 1+m ام در اولین دسته قرار خواهد گرفت و به همین ترتیب روند تقسیم قورباغه ها ادامه می یابد.
اعمال فرایند تکامل در دسته ها
بعد از تقسیم قورباغه ها در بین دسته های مختلف ، هر دسته به تعداد از قبل تعیین شده مراحل تکامل را تکرار می کند.
پس از این مرحله، تمام قورباغه ها ترکیب شده و مرحله جستجوی سراسری دوباره تکرار می شود.
