الگوریتم جهش قورباغه یا SFLA
الگوریتم جهش قورباغه یا SFLA یک الگوریتم فراابتکاری در دنیای الگوریتم‌های بهینه‌سازی به شمار می‌آید. این الگوریتم بر مبنای رفتار اجتماعی قورباغه‌ها در طبیعت ایجاد شده و دارای مزایای زیادی در حوزه طبقه‌بندی است. یکی از نکات مهم درباره این الگوریتم این است که در میان الگوریتم‌هایی که استانداردهای رفتاری دارند، معمولا بهترین گزینه برای استفاده است. الگوریتم قورباغه برای اولین بار توسط Eusuff و Lansey در سال 2003 میلادی مورداستفاده قرار گرفت. با این حال آنها تنها نسخه اولیه این الگوریتم را ارائه دادند.
در طول زمان، الگوریتم قورباغه به میزان زیادی بهینه‌سازی شده و موارد زیادی به آن اضافه یا از آن کم شده‌اند. در ادامه قصد داریم کمی بیشتر درباره الگوریتم جهش قورباغه صحبت کرده و تمام نکاتی که باید درباره آن بدانید را در اختیار شما قرار دهیم.
آشنایی با الگوریتم جهش قورباغه
الگوریتم جهش قورباغه یا SFLA جزئی از الگوریتم‌های مبتنی بر جمعیت به شمار می‌آید که شما می‌توانید از آن برای حل بسیاری از مسائل بهینه‌سازی پیشرفته استفاده کنید. ایده اصلی که در این الگوریتم وجود دارد، جستجوی محلی در ساختار الگوریتم ژنتیک است. ساختار کلی این الگوریتم به شکلی است که ابتدا مجموع پاسخ‌های اولیه را رمزگذاری کرده و سپس این الگوریتم میزان سودآوری هریک از این پاسخ‌های اولیه را بررسی می‌کند. این کار با استفاده از یک تابع مخصوص صورت می‌گیرد که در نهایت منجر به ایجاد راهکارهای جدید می‌شود.
الگوریتم SFLA از نحوه جستجوی قورباغه‌ها برای غذا الهام گرفته شده است. این الگوریتم از یک روش Nomometric برای جستجوی محلی در میان زیرگروه‌های قورباغه استفاده می‌کند. به عبارت دیگر این الگوریتم از یک استراتژی ترکیبی استفاده کرده و امکان تبادل پیام را در جستجوی محلی فراهم می‌کند. این الگوریتم مزایای Nomometric و بهینه‌سازی گروه‌ها را با یکدیگر ادغام کرده و یک الگوریتم کاملا بهینه را به شما ارائه می‌دهد.
نکته مهمی که باید درباره الگوریتم جهش قورباغه یا SFLA دانست، این است که این الگوریتم نه‌تنها برای جستجوی محلی می‌تواند پاسخگو باشد، بلکه در جستجوی جهانی و کلی نیز عملکرد مطلوبی دارد و می‌تواند دقت بالایی را ارائه دهد. پس به طور کلی می‌توان گفت که جستجوی محلی و جهانی به‌خوبی در این الگوریتم ترکیب شده است. این الگوریتم بسیار قابل جستجو بوده و پیاده‌سازی آن نیز کاملا ساده و آسان است. الگوریتم SFLA می‌تواند بسیاری از مسائل غیرخطی، غیرقابل کشف و چند حالته را حل کند.
توصیف کاملی از الگوریتم SFLA
به طور کلی باید بدانید که الگوریتم جهش قورباغه مزایای دو دسته از الگوریتم‌های مبتنی بر ژنتیک و الگوریتم‌های مبتنی بر رفتار اجتماعی را ترکیب می‌کند. در واقع هدف اصلی که این الگوریتم آن را دنبال می‌کند، این است که بتواند بین بررسی گسترده در فضای پاسخ‌های ممکن یک حالت تعادل را ایجاد کند. این الگوریتم مبتنی بر جمعیت، جمعیتی از قورباغه‌ها (که در واقع همان پاسخ‌های جستجو هستند) را شامل می‌شود که در آن هر قورباغه در الگوریتم ژنتیک ساختاری کوروموزم مخصوص به خود را خواهد داشت.
در کل باید بدانید که کل جمعیت قورباغه‌ها به گروه‌های کوچک‌تری تقسیم می‌شوند که هر گروه، نشان‌دهنده انواع مختلفی از قورباغه‌ها خواهد بود که در مکان‌های مختلف فضای پاسخ ما پراکنده شده‌اند. در ادامه هر گروه از قورباغه‌ها جستجوی دقیق محلی را در اطراف زیستگاه خود آغاز می‌کنند. در الگوریتم جهش قورباغه یا SFLA هر قورباغه‌ای که در هر دسته قرار دارد تحت تاثیر سایر اعضای گروه خود و همچنین گروه‌های دیگر قرار می‌گیرد. پس از این‌که چندین مرحله این قورباغه‌ها با یکدیگر ارتباط برقرار می‌کنند و اطلاعات در بین همه گروه‌ها پخش می‌شود شرایط همگرایی بررسی خواهد شد و در صورت همگرایی ما به جواب نزدیک شده‌ایم.
نکته بعدی که باید درباره این الگوریتم به آن دقت داشته باشید این است که نحوه یافتن بهترین راه حل در الگوریتم جهش قورباغه شامل دو مرحله جستجوی جهانی و محلی است.
مطلب پیشنهادی: الگوریتم میگو در متلب
تشکیل جمعیت اولیه در الگوریتم SFLA
الگوریتم جهش قورباغه یا SFLA نیز مانند هر الگوریتم فراابتکاری دیگری که وجود دارد کار خود را با یک جمعیت اولیه آغاز می‌کند. در حین تشکیل این جمعیت اولیه ابتدا تعداد گروه‌ها و تعداد قورباغه‌هایی که باید در هر دسته حضور داشته باشند مشخص خواهد شد. اگر تعداد گروه‌ها و قورباغه‌ها در هر جمعیت عدد یک در نظر گرفته شود تعداد کل نمونه‌های ما برابر F = n*m خواهد بود. در ادامه تابع هزینه برای تمامی این نمونه‌های تولید شده محاسبه خواهد شد. حال در مرحله بعدی نمونه‌هایی که ایجاد شده‌اند مرتب خواهند شد.
دقت داشته باشید که این مرتب‌سازی بر اساس فاکتوری انجام می‌شود که تابع هزینه نامیده می‌شود. این تابع مقادیری را برای نمونه تولید کرده و بررسی می‌کند که آن نمونه تا چه اندازه به مقداری که به دنبال جستجوی آن هستیم نزدیک است. سپس بر اساس نزدیک‌ترین گزینه، نمونه‌های ایجاد شده مرتب خواهند شد. حال از میان نمونه‌هایی که تولید شده‌اند موقعیت بهترین قورباغه حفظ خواهد شد تا در مراحل بعدی بتوانیم از آن استفاده کنیم.
در مرحله بعدی از الگوریتم جهش قورباغه یا SFLA کل قورباغه‌ها به m دسته از این دسته‌های انتخاب شده تقسیم می‌شوند. به این ترتیب مشاهده خواهید کرد که در هر دسته یا کلاسی که ایجاد شده یک قورباغه وجود خواهد داشت. در خصوص روشی که برای این تقسیم‌بندی انجام می‌شود باید به نکات زیر دقت داشته باشید:
- در جمعیت مرتب شده، نفر اول در هر دسته مشخص خواهد شد و نفر دوم و نفرات بعدی نیز به همین ترتیب مشخص می‌شوند که بیان کردیم این کار با استفاده از یک تابع هزینه صورت می‌گیرد.
- این کار ادامه پیدا می‌کند تا زمانی که متولی مربوطه انتخاب شده و در رده m قرار گیرد. در ادامه عضو m+1 در دسته اول قرار گرفته و روند تقسیم قورباغه‌ها نیز به همین شکل ادامه پیدا می‌کند.
- نکته بعدی که باید درباره این تقسیم‌بندی به آن دقت داشته باشید این است که مراحلی که برای این تکامل طی می‌شوند به تعدادی هستند که پیش از شروع الگوریتم مشخص شده است.
- بعد از این‌که این مرحله با موفقیت انجام شد تمامی قورباغه‌ها با یکدیگر ترکیب خواهند شد و مرحله جستجوی سراسری به همین شکل تکرار خواهد شد.
مراحل مختلف الگوریتم جهش قورباغه
پس از تشکیل جمعیت اولیه باید دقت داشته باشید که الگوریتم جهش قورباغه یا SFLA مراحل دیگری را نیز طی می‌کند. در ادامه قصد داریم در جدول زیر توضیحات کاملی را درباره این مراحل به شما ارائه دهیم.
|
مرحله |
توضیحات |
|
مرحله مقداردهی اولیه |
در این مرحله دو متغیر T و P انتخاب خواهند شد. حاصل ضرب این دو متغیر در واقع نشان‌دهنده کلیه memeplexes خواهد بود. توجه داشته باشید که در این مقداردهی P نشان‌دهنده تعداد کلی قورباغه‌ها در هر memeplex است. حال طبق همین الگو اگر شما قصد داشته باشید اندازه کل جمعیت خود را در هر دسته به دست بیاورید تنها کافی است که T و P را در یکدیگر ضرب کنید که ما این مقدار را داخل یک متغیر به نام F ذخیره می‌کنیم. |
|
تولید جمعیت مجازی |
در مرحله بعدی از هریک از فضاهای موجودی که دارید F قورباغه مجازی را نمونه‌برداری می‌کنید. نمونه‌های ایجاد شده را داخل یک متغیر دیگر به‌نام W ذخیره خواهیم کرد. دقت داشته باشید که W یک آرایه است که از مقدار 0 شروع شده و تا F-1 پیش می‌رود و اندازه آن نیز F است. حال باید تابع هزینه را برای هریک از این نمونه‌ها محاسبه کنید. دقت داشته باشید که این تابع را با f(i) نشان خواهیم داد و برای مثال محاسبه تابع هزینه ما به شکل زیر خواهد بود: W(i) = (Wi1, Wi2, …, Wid) در اینجا باید دقت داشت که d همان تعداد متغیرهای تصمیم‌گیری است که ما در الگوریتم خود آن را مشخص خواهیم کرد. |
|
طبقه‌بندی و مرتب‌سازی قورباغه‌ها |
در مرحله سوم از الگوریتم جهش قورباغه یا SFLA نیازمند این خواهیم بود که قورباغه‌ها را به ترتیب نزولی و با توجه به شایستگی و هزینه‌ای که در آرایه زیر دارند ذخیره کنیم: X = {W(i), f(i) & i=1,…F} حال شما نیازمند این خواهید بود که موقعیت بهترین قورباغه Px را در جمعیت ثبت کنید که برای مثال به شکل زیر می‌توانید این کار را انجام دهید: U = Px(1) |
|
قورباغه‌ها را میان ممپلکس‌ها تقسیم کنید |
حال تنها کاری که باید در این مرحله انجام دهید این است که آرایه X که ایجاد کرده‌اید را به Y قسمت تقسیم‌بندی کنید به طوری که هرکدام شامل T قورباغه باشند. |
|
تکامل memetics در هر memeplex |
در این مرحله توجه کنید که هر Yk memeplex(k = 1, 2, 3, ……, m) توسط الگوریتم جستجوی محلی پرش قورباغه که در ادامه توضیح داده شده است تکامل پیدا خواهد کرد. |
|
Memeplexها را با هم ترکیب کنید |
بعد از این‌که تعداد معینی از تکامل ممتیک در هر ممپلکس انجام شد تنها کاری که باید انجام دهید این است که ممپلکس‌های (Y1,…, Ym) را در X قرار دهید، به طوری که رابطه X = {Y(k), k = 1, 2, …., m} ایجاد شده باشد. سپس باید بهترین موقعیت جمعیت Px را به روزرسانی کنید. |
|
مطالعه همگرایی |
دقت داشته باشید که در صورت تحقق شرایط همگرایی این الگوریتم متوقف خواهد شد. در غیر این صورت باید به مرحله چهارم جستجوی جهانی بازگردید. |
مراحل جستجوی محلی
در بخش قبلی از الگوریتم جهش قورباغه یا SFLA درباره مراحل جستجوی سراسری صحبت کردیم. حال باید بدانید که بخش دیگری از این الگوریتم مربوط به جستجوی محلی است. در ادامه مراحل جستجوی سراسری این الگوریتم را نیز برای شما توضیح خواهیم داد:
مرحله اول: مقداردهی اولیه
در این مرحله شما باید دو متغیر iM و iN را تعریف کرده و مقدار اولیه آنها را روی صفر قرار دهید. دقت داشته باشید که iM نشان‌دهنده تعداد memeplexes و iN نشان‌دهنده مراحل تکامل خواهد بود. در ادامه باید یک واحد به هرکدام از این دو متغیر اضافه کنید. در ادامه باید یک submemeplex ایجاد کنید.
توجه کنید که در این بخش از الگوریتم جهش قورباغه یا SFLA هدف قورباغه‌ها این خواهد بود که با بهبود میم‌های خود به سمت موقعیت‌های بهینه‌تر حرکت کنند. روشی که برای انتخاب memeplexes انتخاب می‌شود به این صورت است که وزن‌های بیشتری به قورباغه‌هایی با عملکرد بهتر و وزن‌های کمتر به قورباغه‌هایی با مقدار عملکرد پایین‌تر اختصاص پیدا خواهد کرد. در اینجا وزن‌ها با توزیع احتمال مثلثی و به‌صورت زیر اختصاص داده خواهند شد:
Pi = {2(j-1 + n) / n(n+1), j = 1, …, n}
در همین مرحله شما برای ساختن آرایه submemeplex Z، تعداد q قورباغه به طور تصادفی در هریک از n قورباغه در هر memeplex انتخاب می‌شوند. موارد موجود در submemeplex نیز به ترتیب با PB و PW نشان داده می‌شوند.
مرحله دوم: اصلاح وضعیت بدترین قورباغه
در این مرحله از الگوریتم شما باید وضعیت بدترین قورباغه‌ای که در هر دسته وجود دارد را اصلاح کنید تا بتوانید عملکرد کل الگوریتم را بهینه‌سازی کنید. برای این‌که بتوانید چنین کاری را انجام دهید باید ابتدا بدترین قورباغه در زیر ممپلکس که در واقع همان قورباغه‌ای است که بدترین عملکرد را دارد را پیدا کرده و سپس موقعیت آن را اصلاح کنید. برای این‌که بتواند این موقعیت را اصلاح کنید نیازمند استفاده از رابطه زیر خواهید بود:
U(q) = S + PW
در خصوص این رابطه باید بدانید که S اندازه گام قورباغه خواهد بود که به شکل زیر به دست می‌آید:
اگر موقعیت جدید بهتر از موقعیت قبلی بود U(q) جدید را با U(q) قبلی جایگزین کرده وئ به مرحله 8 از جستجوی محلی بروید. در صورتی که چنین چیزی در الگوریتم جهش قورباغه یا SFLA امکان‌پذیر نبود باید به مرحله 6 جستجوی محلی رفته و همین فرایند را ادامه دهید.
مطلب پیشنهادی: الگوریتم ژنتیک چیست؟
مرحله سوم: اندازه گام را با Px محاسبه کنید.
گاهی اوقات ممکن است وقتی که تا انتها مرحله دو پیش می‌روید نتیجه بهتری را به دست نیاورید. در این مرحله باید اندازه گام قورباغه را تغییر و اصلاح کنید. برای این‌که بتوانید چنین کاری را انجام دهید ابتدا باید موقعیت جدید U(q) را طبق الگویی که بیان کردیم محاسبه کنید. در صورتی که U(q) جدیدی که به دست آورده‌اید در فضای ممکن برای جستجو قرار داشته باشد مقدار بازده جدید که همان f(q) است را محاسبه می‌کنید.
حال اگر این مقدار به دست آمده نسبت به موقعیت قبلی بهتر بود تنها کاری که باید انجام دهید این است که U(q) جدید را با U(q) قبلی جایگزین کرده و به مرحله هشتم جستجوی محلی بروید. در غیر این صورت باید وارد مرحله بعدی شوید که در ادامه توضیح خواهیم داد.
مرحله چهارم: سانسورکردن نتایج
در صورتی که موقعیت جدید در منطقه قابل دستیابی نباشد یا این‌که بهتر از موقعیت قبلی نباشد یک قورباغه جدید r به‌صورت تصادفی در یک مکان موجود ایجاد شده و جایگزین قورباغه‌ای می‌شود که موقعیت جدید آن برای پیشرفت مناسب نیست. حال در ادامه شما باید f(r) را محاسبه کرده و U(q) را برابر r و f(q) را برابر f(r) قرار دهید.
مرحله پنجم: memeplex را به‌روزرسانی کنید.
پس از این‌که تغییرات مرحله قبل را انجام دادید باید قورباغه‌ها را در Z در موقعیت اصلی خود روی Yim قرار دهید. دقت داشته باشید که در این مرحله شما باید Yim را به ترتیب عملکردی نزولی مرتب کنید. در صورتی که N>iN بود به مرحله سوم جستجوی محلی بروید. در صورتی که m>im بود نیز باید به مرحله اول جستجوی محلی در الگوریتم جهش قورباغه یا SFLA بروید. در صورتی که چنین اتفاقی رخ ندهد برای ترکیب memeplexes باید به مرحله جستجوی سراسری بازگردید.
مطلب پیشنهادی: الگوریتم گرگ خاکستری چیست؟
سخن پایانی
الگوریتم جهش قورباغه یا SFLA یکی از الگوریتم‌های فراابتکاری بسیار محبوب در دنیای بهینه‌سازی است که می‌تواند ترکیب دو استراتژی بهینه‌سازی محلی و سراسری را به شما ارائه دهد. این الگوریتم قابلیت‌های متنوعی را به شما ارائه می‌دهد و مهم‌ترین ویژگی آن نیز این است که می‌تواند روی سرعت نتیجه دادن تاثیرگذار باشد. الگوریتم SFLA از چندین مرحله مختلف تشکیل شده است که حتما باید آنها را به ترتیب طی کنید. این الگوریتم در تشکیل جمعیت اولیه خود نیز از تکنیک هوشمندی استفاده می‌کند که در نهایت منجر به دقت بالاتر پاسخ‌های دریافت شده خواهد شد. در صورتی که شما هم علاقه‌مند به داشتن اطلاعات بیشتر درباره الگوریتم‌ها هستید حتما از سایر بخش‌های سایت ما نیز دیدن کنید.
.svg)
دیدگاه شما