الگوریتم بهینه‌سازی جهش قورباغه (SFLA) — آموزش جامع و کاربردی

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

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

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

در واقع الگوریتم 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 قبلی کن و به مرحله‌ی ۸ از جستجوی محلی برو. در غیر این صورت به مرحله‌ی ۶ جستجوی محلی برو.
• مرحله ششم : محاسبه‌ی انداز‌ه‌ی گام بوسیله‌ی 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 ها به جستجوی سراسری باز گرد.

سورس کد الگوریتم بهینه سازی قورباغه در متلب

کلیک کنید

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

پیاده‌سازی ساده الگوریتم SFLA در پایتون

import numpy as np

def objective(x):
    return sum(x**2)

def sfla(objective, dim=5, bounds=(-5, 5), pop_size=20, memeplex_size=5, iterations=100):
    pop = np.random.uniform(bounds[0], bounds[1], (pop_size, dim))
    scores = np.array([objective(ind) for ind in pop])
    for iter in range(iterations):
        idx_sorted = np.argsort(scores)
        pop = pop[idx_sorted]
        scores = scores[idx_sorted]
        memeplexes = np.array_split(pop, memeplex_size)
        for meme in memeplexes:
            best = meme[0]
            worst = meme[-1]
            new_worst = worst + np.random.rand() * (best - worst)
            new_worst = np.clip(new_worst, bounds[0], bounds[1])
            if objective(new_worst) < objective(worst):
                meme[-1] = new_worst
        pop = np.vstack(memeplexes)
        scores = np.array([objective(ind) for ind in pop])
    best_solution = pop[np.argmin(scores)]
    return best_solution

# مثال اجرا
best = sfla(objective)
print("Best solution:", best)

ویژگی‌های اصلی الگوریتم SFLA

مزایای الگوریتم SFLA

• ترکیب مناسب جستجوی محلی و سراسری
• قدرت بالا در فرار از مینیمم‌های محلی
• مناسب برای مسائل گسسته و پیوسته
• کارایی بالا در مسائل چندمتغیره

معایب الگوریتم SFLA

• نیاز به تنظیم تعداد پارامترهای مختلف مانند تعداد Memeplex، تعداد تکرارها، اندازه جمعیت
• امکان کاهش سرعت همگرایی در مسائل بسیار بزرگ
• عدم وجود نسخه استاندارد بهینه برای همه مسائل

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

الگوریتم SFLA در زمینه‌های مختلفی کاربرد دارد، از جمله:

• بهینه‌سازی توابع ریاضی پیچیده
• مسائل مهندسی برق، عمران و مکانیک
• بهینه‌سازی طراحی شبکه‌های مخابراتی
• برنامه‌ریزی تولید و زمان‌بندی
• بهینه‌سازی در یادگیری ماشین و تنظیم پارامترها

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

کلیک کنید

نکات مهم برای بهبود عملکرد SFLA

• تنظیم دقیق تعداد Memeplexها و اندازه آن‌ها
• استفاده از نسخه‌های بهبودیافته مانند Modified SFLA یا ترکیب با الگوریتم‌های دیگر
• افزایش تنوع جمعیت برای جلوگیری از همگرایی زودهنگام
• استفاده از مکانیزم‌های تطبیقی برای تغییر پارامترها در طول اجرا

مقایسه SFLA با سایر الگوریتم‌ها

مقایسه الگوریتم های بهینه سازی در متلب

کلیک کنید

نتیجه‌گیری

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