الگوریتم کرم شب تاب یا FireFly Algorithm

الگوریتم کرم شب تاب یک الگوریتم فراابتکاری است که برای اولین بار در سال 2007 توسط Xin-She Yang  برای حل مسائل بهینه سازی معرفی شد. در ادامه بصورت کامل به بررسی الگوریتم FireFly خواهیم پرداخت.

الگوریتم کرم شب تاب یا Firefly Algorithm به اختصار FA) در اواخر سال ۲۰۰۷ و توسط Xin-She Yang معرفی شده است.

ایده اصلی الگوریتم FA ، از ارتباط نوری میان کرم های شب تاب الهام گرفته شده است.

این الگوریتم را می توان از مظاهر هوش ازدحامی یا Swarm Intelligence دانست، که در آن از همکاری (و احتمالا رقابت) اعضای ساده و کم هوش، مرتبه بالاتری از هوشمندی ایجاد می شود که قطعا توسط هیچ یک از اجزا قابل حصول نیست.

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

آشنایی با کرم شب تاب:

کرمِ شب‌تاب بر خلاف نامش از خانواده حشرات و زیرمجموعه سوسک‌ها می‌باشد.

کرم‌های شب تاب نور سرد تولید می‌کنند که فاقد طیف‌های فروسرخ و فرابنفش می‌باشد.

این نور که طول موج آن از ۵۱۰ تا ۶۷۰۰ نانومتر متغیر است می‌تواند به رنگ‌های زرد، سبز یا قرمز کم‌رنگ دیده شود.

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

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

حشرات دیگر با دیدن نور کرم شب تاب به آنها نزدیک نمیشوند و قورباغه نیز علاقه چندانی به شکار آن ندارد.

تحقیقات نشان داده است که حتی اگر کرم شب تاب بر فراز آب پرواز کند، ماهیها و حتی کوسه از آن میترسند و فرار میکنند.

تاکنون در حدود ۲۰۰۰ گونه از این نوع حشرات در نواحی معتدل و گرمسیری شناسایی شده است.

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

در بین بیشتر گونه‌ها هر دو جنس نر و ماده توانایی پرواز دارند. اما در بین بعضی گونه‌ها، جنس ماده قادر به پرواز نمی‌باشد.

نور چشمک زن از کرم های شب تاب در آسمان تابستان مناطق گرمسیری و متعدل دید شگفت انگیزی را ایجاد میکند.

در طبیعت حدود 2000 گونه کرم شب تاب وجود دارد و بسیاری از کرم های شب تاب نور چشمک زن کوتاه و ریتمیک ایجاد میکنند.

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

نور چشمک زد توسط یک فرایند شب تابی یا بیولومینسن ایجاد میشود . دو عمل اساسی ای که این نورهای چشمک زن انجام میدهند عبارتند از جذب شریک جنسی (ارتباط یا جفت گیری) و جذب طعمه می باشد. علاوه بر این، نور چشمک زن گاهی اوقات بعنوان یک مکانیسم هشدار دهنده برای حفاظت از شکارچیان کرم شب تاب عمل کند.
نور چشمک زن معادل است با فلش. در ادامه این دو کلمه معادل یک دیگر می باشند
ریتم فلش ، سرعت و میزان فلش و مدت زمان فلش، بخشی از سیستم سیگنال هر دو جنس کرم شب تاب را به ارمغان می آورد. کرم های ماده به الگوی فلش منحصر به فرد جنس نر در همان گونه پاسخ میدهد، در حالی که در برخی از گونه ها از قبیل Photuris ، کرم ماده میتواند سیگنال معاشقه درخشنده را استراق سمع کند یا حتی الگوی فلش جفت گیری گونه های دیگر را تقلید کند به طوری که کرم های شب تاب نری را که ممکن است به اشتباه تصور کنند که یک همسر بالقوه در حال چشمک زدن است را فریب داده و بخورد.
ما میدانیم که شدت نور در یک فاصله خاص مانند R از یک منبع نور از قانون مربع معکوس پیروی میکند. قانونی که میگوید ، شدت نور I با افزایش فاصله R کاهش میباشد و از رابطه زیر پیروی میکند:
I ∝ 1/r2
علاوه بر این، هوا نوری که با افزایش فاصله ضعیف و ضعیف تر میشود را جذب میکند. ترکیب این دو عامل دیده شدن کرم شب تاب را محدود میکند به یک فاصله محدود، معمولا چند صد متر در شب که به اندازه کافی برای کرم های شب تاب برای ایجاد ارتباط کافی می باشد.
نور چشمک زن کرم های شب تاب را میتوان به شیوه ای فرموله کنیم که مرتبط با تابع هدفی که میخواهیم بهینه کنیم باشد ، که این امکان فرموله کردن الگوریتم بهینه سازی جدیدی را ایجاد میکند. در ادامه ابتدا فرمولهای اصلی الگوریتم کرم شب تاب را بیان میکنید و سپس به بحث در خصوص جزئیات پیاده سازی می پردازیم.

الگوریتم کرم شب تاب (FIREFLY ALGORITHM)
حال میتوانیم برخی از ویژگی های نور چشمک زن کرم های شب تاب را بصورت ایده آل در آوریم به طوری که برای توسعه الگوریتم کرم شب تاب استفاده شوند. برای سادگی در توصیف الگوریتم کرم شب تاب که برای اولین بار توسط Xin-She Yang در دانشگاه کمبریج در سال 2007 توسعه داده شده است سه قانون زیر را در نظر میگیریم:
1- همه کرم های شب تاب تک جنسیتی هستند(یعنی جنس نر و ماده متمایز نیستند) در نتیجه یک کرم شب تاب میتواند به سمت سایر کرم های شب تاب بدون در نظر گرفتن جنسیت شان جذب شود.
2- میزان جذابیت یک کرم متناسب با روشنایی آن می باشد. در نتیجه برای هر دو کرم شب تاب در حال چشمک زدن، کرمی که روشنایی کمتری دارد به سمت کرم روشن تر حرکت میکند. میزان جذابیت متناسب با روشنایی می باشد و هر دوی آنها با افزایش فاصله کاهش می یابند. در حالتی که هیچ یک از دو کرم شب تاب روشن تر از دیگری نباشد یکی از آنها به صورت تصادفی به سمت دیگری حرکت میکند.
3- روشنایی یک کرم شب تاب تحت تاثیر چشم انداز تابع هدف تعیین میشود. یعنی با توجه به تابع هدف مورد نظر میزان روشنایی هر کرم شب تاب مشخص میشود.
برای یک مسئله ماکزیمم سازی (maximization) ، میزان روشنایی را میتوان به سادگی متناسب با مقدار تابع هدف در نظر گرفت. شکل های دیگری از روشنایی را میتوان به روش مشابه بعنوان تابع شایستگی در الگوریتم ژنتیک تعریف کرد. بر اساس سه قانون فوق ، مراحل اصلی الگوریتم کرم شب تاب را میتوان در شبه کد نشان داده شده در شکل زیر خلاصه کرد:

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

در الگوریتم کرم شب تاب، دو موضوع مهم وجود دارد : 1- تغییر شدت نور و 2- فرموله سازی جذابیت. برای سادگی ، ما همیشه میتوانیم فرض کنیم که میزان جذابیت یک کرم شب تاب بر اساس روشنایی آن که به نوبه خود با تابع هدف در ارتباط است تعیین میشود.
در ساده ترین حالت برای مسئله بهینه سازی حداکثری (ماکزیمم سازی)، میزان روشنایی I برای یک کرم خاص که در موقعیت x قرار دارد میتواند بعنوان I(x) ∝ f(x) تعیین شود.
با این حال ، میزان جذابیت β ، نسبی است ، یعنی باید در چشم بیننده دیده شود یا بعبارت دیگر توسط کرم های دیگر که این کرم را می بینند قضاوت شود. بنابراین ، میزان جذابیت با فاصله rij بین کرم i ام و کرم j ام تغییر میکند. علاوه بر این ، شدت نور با فاصله گرفتنش از منبع کاهش می یابد، و همچنین نور در رسانه ها (محیط اطراف) جذب می شود، بنابراین ما باید اجازه دهیم که جذابیت با درجه ای از جذب شدن تغییر کند.
در ساده ترین شکل، شدت نور I(r) با توجه به قانون مربع معکوس تغییر میکند:
رابطه 1
که در آن Is شدت نور در منبع می باشد .برای یک رسانه داده شده (منظور محیط می باشد) با یک ضریب جذب ثابت γ ، شدت نور I با فاصله r تغییر میکند. به این معنا که :
رابطه 2
که در آن I0 میزان شدت روشنایی اصلی یا اولیه می باشد. به منظور اجتناب از تکینگی در r=0 در عبارت اثر ترکیبی از قانون مربع معکوس و قانون جذب میتواند به صورت یک فرم گوسی همانند زیر تقریب زده شود:
ربطه 3

از انجا که میزان جاذبه یک کرم شب تاب متناسب با شدت نور دیده شده توسط کرم شب تاب مجاور است ، میتوانیم جذابیت β یک کرم شب تاب را بصورت زیر تعریف کنیم:
رابطه 4
که در ان β0 میزان جذابیت در r = 0 می باشد. از آنجا که معمولا محاسبه سریعتر از محاسبه یک تابع نمایی می باشد در نتیجه تابع فوق را در صورت لزوم میتوان به راحتی به شکل زیر تقریب زد:
رابطه 5
هر دو رابطه فوق (رابطه 4 و5) یک مشخصه فاصله را تعریف میکنند که جذابیت به طور قابل توجهی از β0 به β0e−1 برای رابطه 4 یا β0/2 در رابطه 5 تغییر میکند.
در پیاده سازی واقعی ، تابع جذابیت β(r) میتواند هر نوع تابع یکنواخت کاهشی مانند شکل کلی زیر باشد:
رابطه 6
برای γ ثایت ، طول مشخصه میشود:
رابطه 7
در مقابل، برای یک مقیاس Γ داده شده در مسئله بهینه سازی، پارامتر γ را میتوان به عنوان یک مقدار اولیه معمولی استفاده کرد. به این معنا که
رابطه 8
فاصله بین هر دو کرم شب تاب I و J که به ترتیب در مکان های Xi و Xj قرار دارند یک فاصله کارتزین می باشد:
رابطه 9
که در ان Xi,k نشان دهنده مولفه k ام از فضای Xi کرم i ام می باشد . در حالت 2 بعدی این فرمول بصورت زیر می باشد:
رابطه 10
حرکت و جابجایی یک کرم i به سمت کرم j حذابتر (روشن تر) با رابطه زیر تعیین میشود:
رابطه 11
که در رابطه فوق، بخش دوم آن بدلیل جذب می باشد، بخش سوم آن نیز تصادفی سازی با پارامتر آلفا می باشد و یک بردار از اعداد تصادفی با توزیع یکنواخت یا توزیع گوسی می باشد. بعنوان مثال ،در ساده ترین حالت را میتوان با جایگزین کرد. که دستور rand یک مولد اعداد تصادفی با توزیع یکنواخت در بازه [0,1] می باشد. در اغلب پیاده سازی ها، مقدار β0 = 1 و α ∈ [0, 1] در نظر گرفته میشود.
لازم به ذکر است که رابطه 11 یک حرکت تصادفی با گرایش به سمت کرم روشن تر می باشد. در حالتی که β0 = 0 باشد این رابطه یک گام تصادفی ساده می باشد. علاوه براین ، بخش تصادفی فرمول را میتوان به راحتی به توزیع های دیگر از جمله توزیع Levy flight تغییر داد.
پارامتر γ در حال حاضر تنوع جذابیت را تعیین میکند، و مقدار آن در تعیین سرعت همگرایی الگوریتم و چگونگی رفتار الگورتیم کرم شب تاب خیلی مهم و حیاتی است. در تئوری می باشد اما در عمل γ = O(1) می باشد و در اکثر کاربردهای این الگوریتم مقدار آن به طور معمول از 0.1 تا 10 تغییر میکند.

لازم به ذکر است که فاصله r که در بالا تعریف شد تنها به فاصله اقلیدسی محدود نمیشود ، ما میتوانیم از فاصله های دیگری برای r در فضای n بعدی بسته به نوع مسئله ای که حل میکنیم استفاده کنیم. بعنوان مثال ، برای مئسله برنامه ریزی شغلی (job scheduling) ، میتوان r را بعنوان تاخیر زمانی یا فاصله زمانی در نظر گرفت. برای شبکه های پیچیده مانند اینترنت و شبکه های اجتماعی، فاصله r را میتوان به عنوان ترکیبی از درجه خوشه های محلی و میانگین مجاورت رئوس در نظر گرفت. در حقیقت، هر معیاری که بتواند بصورت موثر مقدار علاقه و تمایل در مسئله بهینه سازی را توصیف کند میتوان بعنوان فاصله r استفاده کرد.
مقیاس Γ باید با مقیاس مورد نظر در مسئله بهینه سازی ارتباط داشته باشد. اگر Γ یک مقیاس معمولی برای یک مسئله بهینه سازی داده شده می باشد، برای تعداد زیادی از کرم های شب تاب (n کرم) که n خیلی خیلی بزرگتر از k می باشد و k تعداد نقاط بهینه محلی می باشد، بنابراین موقعیت اولیه این n کرم شب تاب باید نسبتا بصورت یکنواخت در کل فضای جستجو توزیع شده باشد. بعنوان یک پروسه تکراری، کرم های شب تاب باید به همه بهینه های محلی (از جمله بهینه های عمومی) همگرا شوند. بامقایسه بهترین راه حل در میان همه این نقاط بهینه، نقطه بهینه عمومی به راحتی قابل دستیابی می باشد. تحقیقات اخیر ما نشان میدهد که ممکن است اثبات کنیم که الگوریم کرم شب تاب به نقطه بهینه سراسری نزدیک خواهد شد زمانی که n → ∞ و t>>1 باشد. در واقع ، الگوریتم خیلی سریع همگرا میشود که در ادامه خواهیم دید.
دو مورد مهم محدود کننده یا مجانبی وجود دارد زمانی که و می باشد. در مقدار جذابیت ثابت است β = β0 و می باشد ، این معادل است با اینکه بگوییم شدت نور در آسمان ایده آل و آرمانی کاهش نمی یابد. بنابراین، یک کرم شب تاب چشمک زن در هر نقطه از دامنه میتواند دیده شود. بنابراین یک نقطه بهینه تک (معمولا بهینه سراسری) به راحتی قابل دسترسی می باشد. اگر ما حلقه داخلی را برای j در شکل 1 را حذف کنیم و بجای xj بهترین بهینه فعلی یعنی g* را جایگزین کنیم در این حالت الگوریتم کرم شب تاب به حالت خاصی از الگوریتم ازدحام ذرات (PSO) تبدیل میشود. در نتیحه بهره وری و کارایی این حالت خاص برابر با الگوریتم PSO میشود.
از طرف دیگر، حالت محدود کننده منجر به و می شود که تابع دلتای دیراک (Dirac delta function) می باشد، به این معنی که جذابیت در نظر سایر کرم های شب تاب تقریبا برابر با صفر می باشد. این معادل است با این حالت که کرم شب تاب در یک منطقه بسیار مه آلود بصورت تصادفی پرسه میزند.. هیچ کرم دیگری دیده نمیشود، و هر کرم شب تاب در یک مسیر کاملا تصادفی پرسه میزند. بنابراین یک جستجوی کاملا تصادفی رخ میدهد.
از آنجا که الگوریتم کرم شب تاب معمولا در حالتی بین این دو حالت افراطی می باشد، میتوان پارامتر γ و α را به نحوی تنظیم کرد که الگوریتم کارایی بهتر از هر دو حالت جستجوی تصادفی و جستجوی pso داشته باشد. در حقیقت، الگوریتم کرم شب تاب میتواند نقاط بهینه سراسری و نقاط بهینه محلی را به طور همزمان و موثر پیدا کند . این مزیت در ادامه در زمان شبیه سازی الگوریتم نشان داده خواهد شد.
مزیت دیگر الگوریتم کرم شب تاب این است که کرم های شب تاب مختلف تقریبا به صورت مستقل کار میکنند. در نتیجه برای پیاده سازی موازی بسیار مناسب است.این الگوریتم حتی از الگوریتم ژنتیک و PSO نیز بهتر است چونکه کرم شب تاب یسیار نزدیک تر در اطراف هر نقطه بهینه جمع میشوند. میتوان این انتظار را داشت که در پیاده سازی موازی الگوریتم، تعاملات بین نواحی مختلف حداقل باشد.

پیاده سازی:
برای اینکه نشان دهیم الگوریتم کرم شب تاب به چه صورت کار میکند ، این الگوریتم را در متلب شبیه سازی کرده ایم.
به منظور نمایش دادن اینکه هم نقاط بهینه سراسری و هم نقاط بهینه محلی را میتوان با الگوریتم کرم شب تاب بصورت همزمان پیدا کرد ما از تابع زیر که 4 نقطه بهینه دارد استفاده میکنیم:

که در ان دامنه هر دو متغیر x و y بین منفی 5 و 5 می باشد. این تابع 4 پیک (نقطه بهینه) دارد . دو پیک محلی با مقدار f=1 در نقطه (-4,4) و (4,4) و دو بهینه سراسری با fmax=2 در نقطه (0,0) و همچنین نقطه (0,-4) . همانطور که در شکل زیر نمایش داده شده است.

میتوانیم ببینیم که هر 4 نقطه بهینه با استفاده از 25 کرم شب تاب و در 20 تکرار الوریتم پیدا شده اند. شکل زیر را ببینید

بنابراین تعداد کل دفعاتی که تابع ارزیابی میشود 500 مرتبه می باشد . که این خیلی موثر تر از بسیاری از الگوریتم های فرااکتشافی موجود می باشد.