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

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

الگوریتم جهش قورباغه (SFLA – Shuffled Frog Leaping Algorithm) یکی از الگوریتم های بهینه سازی مبتنی بر جمعیت است که از رفتار طبیعی قورباغه ها در جستجوی غذا الهام گرفته شده است. این الگوریتم نخستین بار توسط “ابراهیم” در سال 2006 معرفی شد و به دلیل کارایی بالا در حل مسائل بهینه سازی پیچیده مورد توجه محققان قرار گرفته است. SFLA ترکیبی از مفاهیم جستجوی محلی و تبادل اطلاعات جمعیتی است که از روش های فراابتکاری مانند الگوریتم ژنتیک (GA) و الگوریتم کلونی مورچگان (ACO) الهام گرفته شده است. این الگوریتم تلاش می‌کند تا با تقسیم جمعیت به گروه های کوچک تر و تبادل اطلاعات میان آن‌ها، همگرایی به سوی بهترین جواب ممکن را تسریع بخشد.

در SFLA، قورباغه ها به عنوان عامل های جستجو در فضای مسئله توزیع شده و به گروه های جداگانه ای به نام “ممپلکس” (Memeplex) تقسیم می شوند. هر ممپلکس به طور مستقل جستجوی محلی انجام می‌دهد و سپس نتایج حاصل را با سایر ممپلکس ها مبادله می‌کند. این فرآیند مشابه ترکیب جستجوی محلی و جستجوی جهانی است و موجب افزایش کارایی در یافتن جواب های بهینه می شود. ویژگی‌های متمایز SFLA شامل سادگی در پیاده سازی، توانایی در مدیریت مسائل غیرخطی و توانایی فرار از بهینه های محلی است که آن را به ابزاری مناسب برای مسائل مختلف مهندسی و علمی تبدیل کرده است.

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

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

• برنامه نویسی

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

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

• مشاوره برنامه نویسی

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

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

بیشتر الگوریتم های فراابتکاری طبیعی از رفتارها یا پدیده های فیزیکی گروه های موجودات در طبیعت الهام گرفته اند. برای مثال، الگوریتم بهینه سازی وال (WOA) از روش های خاص جستجو و مکانیسم شکار دسته جمعی وال های گوژپشت الهام گرفته و شامل سه مرحله اصلی جمع آوری طعمه، شکار با حباب و جستجوی طعمه می باشد. الگوریتم شکارچیان دریایی (MPA) از نظریه “بقا برای شایسته ترین” الهام گرفته است، که نشان می دهد شکارچیان دریایی با انتخاب بین حرکت های لوی و براونی بهترین استراتژی های شکار را اتخاذ می کنند. همچنین الگوریتم های دیگری مانند الگوریتم سنجاقک (DA)، الگوریتم بهینه سازی شعله پروانه (MFO)، الگوریتم جستجوی مداری اتمی (AOS) و الگوریتم بهینه سازی غزال (GOA) نیز از رفتارها یا اصول طبیعی الهام گرفته شده اند.

مطلب پیشنهادی: الگوریتم خفاش (Bat Algorithm) چیست؟

در حالی که این الگوریتم ها عملکردی ساده، کارآمد و توانایی فرار از بهینه های محلی را ارائه می دهند، نظریه “ناهار رایگان” تصریح می کند که هیچ الگوریتمی نمی تواند همه مسائل بهینه سازی را به خوبی حل کند یا در همه مسائل عملکرد عالی داشته باشد. بنابراین، بهبود مستمر الگوریتم ها برای حل مسائل بهینه سازی عملی ضروری است.

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

مطلب پیشنهادی: الگوریتم کرم شب تاب چیست؟

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

مطلب پیشنهادی: مسئله کوله پشتی چیست؟

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

• الگوریتم گرگ خاکستری

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

1. ایجاد جمعیت اولیه:
   • یک جمعیت اولیه از قورباغه ها تولید می شود.
   • مقدار برازش هر قورباغه بر اساس تابع هدف مسئله محاسبه می شود.
2. جستجوی محلی:
   • راه حل های موجود در هر همسایگی محلی بهبود داده می شوند.
   • این مرحله کیفیت راه حل ها را افزایش داده و جستجو در مناطق نزدیک فضای جستجو را تقویت می کند.
3. تکامل میمتی:
   • الگوریتم از ترکیبی از یادگیری فردی و یادگیری اجتماعی استفاده می کند.
   • یادگیری فردی به قورباغه ها اجازه می دهد تا راه حل های خود را به صورت مستقل بهینه کنند.
   • یادگیری اجتماعی به قورباغه ها امکان تبادل اطلاعات با قورباغه های مجاور را می دهد که باعث اشتراک گذاری دانش می شود.
4. بازآرایی:
   • قورباغه های با بهترین برازش انتخاب شده و برای ایجاد یک جمعیت جدید بازآرایی می شوند.
   • این فرآیند رفتار سلسله مراتبی قورباغه ها را تقلید می کند، جایی که قورباغه های غالب جستجوی سایر قورباغه ها را هدایت می کنند.

• الگوریتم زنبور عسل

الگوریتم اصلی جهش قورباغه (SFLA)

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

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

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

• الگوریتم تکاملی تفاضلی

مرحله 1: یک جمعیت مجازی از F قورباغه های مختلف به طور تصادفی در فضای امکان پذیر D بعدی تولید می شود. هر قورباغه نشان دهنده یک راه حل نامزد مسئله بهینه سازی است و D تعداد متغیرهای تصمیم گیری است. بنابراین ith قورباغه با یک بردار بیان می شود Ui=(Ui1, Ui2, … UiD). هر قورباغه دارای یک ارزش تناسب اندام مرتبط است fi که عملکرد قورباغه را اندازه گیری می کند.

مرحله 2: همه قورباغه ها بر اساس مقادیر تناسب اندامشان به ترتیب نزولی مرتب می شوند و کل جمعیت به m memeplex (جامعه) Y1,Y2,⋯Ym تقسیم می شوند، هر کدام حاوی n قورباغه (یعنی F = m × n)، به طوری که

قورباغه را با بهترین ارزش تناسب اندام به عنوان Ug در کل جمعیت ثبت کنید.

مرحله 3: تکامل ممتیک SFLA شروع می شود. در مرحله اول، q قورباغه های متمایز به طور تصادفی از n قورباغه در Ym memeplex انتخاب می شوند برای ساخت یک ساب مپلکس استراتژی انتخاب این است که به قورباغه هایی که ارزش عملکرد بالاتری دارند، احتمال بیشتری برای انتخاب داده شود. قورباغه های درون ساب مپلکس به ترتیب کاهش عملکرد متوسل می شوند. برای هر ساب مپلکس، قورباغه هایی با بدترین و بهترین عملکرد به ترتیب Uw و Ub مشخص می‌شوند، بدترین قورباغه Uw در هر submemeplex به صورت زیر به روز می شود:

که در آن S اندازه گام به روز شده است و یک بردار D بعدی است. r یک عدد تصادفی بین 0 و 1 است. Smax حداکثر اندازه گامی است که قورباغه پس از آلوده شدن می پذیرد. قورباغه جدید سپس توسط رابطه زیر محاسبه می شود

قانون تکامل ارائه شده در بالا به صورت شکل زیر نشان داده شده است.

اگر عملکرد جدید Uw’ بهتر از قدیمی است Uw، پس Uw جایگزین بدترین ها می شود. در غیر این صورت، محاسبات در معادلات. (2) و (3) با توجه به بهترین قورباغه جهانی تکرار می شوند، یعنی: Ub جایگزین Ug می شود. اگر هیچ بهبودی در این مورد ممکن نشد، قورباغه (راه حل) جدیدی به طور تصادفی برای جایگزینی قورباغه Uw تولید می شود. این عمل با تعداد تکرار لازم Lmax تکرار می شود. فرآیند جستجوی بالا، کاوش محلی SFLA نامیده می شود.

مرحله 4: هنگامی که کاوش محلی برای m memeplexها کامل شد، الگوریتم برای درهم ریختن به اکتشاف جهانی باز می گردد. برای تبادل اطلاعات جهانی، جمعیت قورباغه مطابق با ارزش‌های تناسب اندام جدید مرتب می‌شود. بهترین قورباغه جهانی Ug را به روز کنید. سپس، کل قورباغه ها به m memeplex تقسیم می شوند و جستجوی محلی جدید دوباره شروع می شود. اکتشاف محلی و فرآیند جابجایی جهانی به طور متناوب تا اعداد تکرار Gmax انجام می شود یا معیارهای همگرایی برآورده می شوند. Ug به روز شده است راه حل بهینه مسئله بهینه سازی است.

پارامترهای اصلی SFLA عبارتند از: تعداد قورباغه‌ها F، تعداد ممپلکس‌های m، تعداد قورباغه‌ها در هر memeplex n، تعداد قورباغه‌ها در هر ساب مپلکس q و Lmax حداکثر تعداد جستجوی محلی تکرارهای تکاملی. قبل از هم زدن آخرین پارامتر معیار توقف الگوریتم است. این می تواند حداکثر تعداد تکرار در هم زدن سراسری Gmax یا دقت راه حل ɛ باشد.

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

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

1. طراحی مهندسی:
   • بهینه سازی پارامترهای طراحی سیستم های پیچیده مانند ساختار بال هواپیما یا شبکه های توزیع نیرو.
2. مدیریت زنجیره تامین:
   • بهینه سازی سطوح موجودی، مسیرهای توزیع و برنامه های تولید برای کاهش هزینه ها و افزایش کارایی.
3. خوشه بندی و طبقه بندی داده ها:
   • شناسایی الگوها و گروه بندی نقاط داده بر اساس شباهت ها که در تحلیل داده و تصمیم گیری کمک می کند.
4. پردازش تصویر و سیگنال:
   • بهبود کیفیت تصاویر، کاهش نویز و استخراج ویژگی های مفید از سیگنال ها.
5. تخصیص منابع:
   • بهینه سازی تخصیص منابع مانند نیروی انسانی، تجهیزات یا بودجه برای دستیابی به حداکثر بهره وری و کارایی هزینه.

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