الگوریتم بهینه‌سازی کرم شب‌تاب (FA) — راهنمای جامع و تخصصی

الگوریتم بهینه‌سازی کرم شب‌تاب (Firefly Algorithm – FA) یک روش قدرتمند برای بهینه‌سازی است که بر اساس رفتار جلب نور کرم‌های شب‌تاب طراحی شده است. این الگوریتم در سال ۲۰۰۸ توسط دکتر Xin-She Yang ارائه شد و به سرعت در بین پژوهشگران محبوبیت یافت. در این مقاله به صورت کامل و تخصصی، ساختار الگوریتم FA، مراحل اجرا، فرمول‌ها، مزایا، معایب و کاربردهای آن را بررسی می‌کنیم.

مقدمه

کرم شب تاب از خانواده حشرات و زیرمجموعه سوسک‌ها است. کرم‌های شب تاب نوری از خود تولید می‌کنند که فاقد طیف‌های فرابنفش می‌باشد. نور کرم شب‌تاب کاملاً شبیه سایر نورهاست. به استثنای آن که این نور حرارتی ندارد. این قبیل نور را به نام (لومی نسانس) می‌شناسند. در کرم شب‌تاب این نور توسط ماده‌ای به نام (لوسی فرین) تولید می‌شود که این ماده با اکسیژن ترکیب شده و تولید نور می‌نماید این نور دارای طول موج ۵۱۰ تا ۶۷۰ نانومتر متغییر است و می‌تواند به رنگ‌های زرد، سبز یا قرمز کم‌رنگ دیده شود. دانشمندان قبلاً بر این عقیده بودند که این حشرات با نورشان موجب جلب توجه جنس مخالف برای جفت گیری و یا صید برای شکار می‌شوند.

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

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

معرفی الگوریتم کرم شب‌تاب (FA)

الگوریتم کرم شب تاب یا Firefly Algorithm (به اختصار FA) در اواخر سال ۲۰۰۷ و توسط Xin-She Yang معرفی شده است، که ایده اصلی آن از ارتباط نوری میان کرم های شب تاب الهام گرفته شده است. این الگوریتم را می توان از مظاهر هوش ازدحامی یا Swarm Intelligence دانست، که در آن از همکاری اعضای ساده و کم هوش، مرتبه بالاتری از هوشمندی ایجاد می شود که قطعا توسط هیچ یک از اجزا قابل حصول نیست. الگوریتم FA یک الگوریتم فراکتشافی، با الهام از رفتار های کرم شب تاب مصنوعی است. این الگوریتم با فرضیه زیر فرمول بندی شده است:

1. همه کرم شب تاب ها تمایل جنسی دارند، به طوری که یک کرم شب تاب به تمام کرم شب تاب های دیگر را جذب می کند.
2. جذابیت متناسب است به روشنایی خود، و برای هر دو کرم شب تاب یکی کمتر روشن خواهد شد جذب (و در نتیجه به حرکت می افتد ) یکی روشن تر، با این حال، روشنایی می تواند به عنوان فاصله آنها افزایش و یا کاهش یابد.
3. اگر کرم شب تابی روشن تر از کرم شب تاب داده شده وجود داشته باشد آن را به طور تصادفی حرکت خواهد داد. روشنایی باید با تابع هدف در ارتباط باشد.

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

پاورپوینت الگوریتم کرم شب تاب FA — ویژه ارائه کلاسی

کلیک کنید

مفاهیم کلیدی الگوریتم FA

1. شدت نور (Brightness): شدت نور یک کرم شب‌تاب متناسب با کیفیت راه‌حل است. در مسائل کمینه‌سازی، هر چه مقدار تابع هدف (Cost) کمتر باشد، شدت نور بیشتر است.
2. جاذبه بین کرم‌های شب‌تاب (Attractiveness): کرم شب‌تاب ضعیف‌تر به سمت کرم شب‌تاب قوی‌تر حرکت می‌کند. میزان جاذبه با فاصله و شدت نور تعیین می‌شود؛ هرچه فاصله بیشتر شود، جاذبه کاهش می‌یابد.

مراحل اجرای الگوریتم FA

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

1. مقداردهی اولیه: تولید تصادفی جمعیتی از کرم‌های شب‌تاب (راه‌حل‌ها) و تعیین شدت نور هر کرم با استفاده از تابع هدف.
2. حرکت کرم‌های شب‌تاب: هر کرم شب‌تاب به سمت کرم‌هایی که نور بیشتری دارند حرکت می‌کند.
3. به‌روزرسانی شدت نور: پس از حرکت، شدت نور کرم‌ها مجدداً محاسبه می‌شود.
4. جستجوی محلی تصادفی: مقداری حرکت تصادفی برای جلوگیری از افتادن در مینیمم‌های محلی اعمال می‌شود.
5. معیار توقف: الگوریتم تا زمانی که شرایط توقف (تعداد تکرار یا دقت مطلوب) برآورده نشود، تکرار می‌شود.

فلوچارت الگوریتم کرم شب تاب

شبه کد الگوریتم FA

Begin
   ۱) Objective function: F(x), X=(x1,x2,...,xd);
   ۲) Generate an initial population of fireflies Xi (i=1,2,...,n);
   ۳) Formulate light intensity I so that it is associated with F(X);
   (for example, for maximization problems, I=F(x);)
   ۴) Define absorption coefficient γ
 
   While (t < MaxGeneration)
      for i = 1 : n (all n fireflies)
         for j = 1 : i (n fireflies)
            if (Ij>Ii),
               Vary attractiveness with distance r via exp(-γr);
               move firefly i towards j;                
               Evaluate new solutions and update light intensity;
            end if 
         end for j
      end for i
      Rank fireflies and find the current best;
   end while
   Post-processing the results and visualization;

الگوریتم کرم شب تاب FA در پایتون Python

کلیک کنید

معادلات اصلی الگوریتم FA

فرمول های اصلی الگوریتم کرم شب تاب بر اساس شدت نور و حرکت کرم شب تاب طراحی شده که به صورت زیر می باشد:

شدت نور (Brightness)

$$I(r) = {I_{0}}{e^{ – \gamma {r^2}}}$$

که در آن:

• \({I_{0}}\): شدت نور اولیه است.
• \(\gamma\): نرخ جذب نور است.
• \({I_{0}}\): فاصله بین دو کرم شب‌تاب است.

حرکت کرم شب‌تاب \({i}\) به سمت کرم شب‌تاب \({j}\)
$${x_i} = {x_i} + {\beta _0}{e^{ – \gamma r_{ij}^2}}({x_j} – {x_i}) + \alpha \times (rand – ۰.۵)$$
که:

• ​\({\beta _0}\): جاذبه در فاصله صفر است.
• \(\alpha \): ضریب تصادفی برای جستجوی محلی.
• \({rand}\): یک عدد تصادفی بین ۰ و ۱ است.

مزایا و معایب الگوریتم FA

مزایا

• قدرت جستجوی جهانی بالا و توانایی عبور از مینیمم‌های محلی
• سادگی در پیاده‌سازی
• نیاز به تعداد پارامترهای قابل تنظیم کم
• قابلیت بالای اکتشاف (exploration)

معایب

• ممکن است در مسائل با ابعاد بسیار بالا عملکرد افت کند.
• وابستگی نسبی به انتخاب پارامترهای مناسب (مانند γ و α).
• در برخی موارد سرعت همگرایی کمتر از سایر الگوریتم‌ها مانند PSO است.

کاربردهای الگوریتم کرم شب‌تاب

• بهینه‌سازی توابع ریاضی
• بهینه‌سازی پارامترهای شبکه‌های عصبی
• مسائل مهندسی طراحی (مانند بهینه‌سازی مدارها)
• خوشه‌بندی داده‌ها
• زمان‌بندی پروژه‌ها
• بهینه‌سازی مسیر و مسیریابی

تعیین درخت پوشای مینیمم با الگوریتم کرم شب تاب در متلب

کلیک کنید

نسخه‌های بهبود یافته الگوریتم FA

• Modified Firefly Algorithm (MFA): بهبود عملکرد جستجوی محلی
• Hybrid Firefly Algorithm: ترکیب با الگوریتم‌های دیگر مانند GA یا PSO
• Multiobjective Firefly Algorithm (MOFA): برای مسائل چندهدفه
• Quantum-behaved Firefly Algorithm (QFA): اعمال مکانیک کوانتومی برای افزایش اکتشاف

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

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

کلیک کنید

جمع‌بندی

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