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

الگوریتم بهینه سازی کرم شب‌تاب Firefly Algorithm Optimization، و یا به اختصار الگوریتم کرم شب‌تاب Firefly Algorithm، از رفتار کرم های شب‌تاب طبیعی که در مجموعه ها بزرگ در کنار هم زندگی می کنند الهام گرفته شده است و یکی از الگوریتم های بسیار کارآمد در حل مسائل بهینه سازی ترکیبی است.

الگوریتم های دیگری نیز بر اساس الگوریتم کرم شب تاب ساخته شده اند که همگی سیستم های چند عاملی Multi Agent هستند و عامل ها کرم های شب‌تاب  مصنوعی هستند که مشابه با کرم های شب‌تاب واقعی رفتار می کنند. الگوریتم کرم شب‌تاب، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندان بالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند. از این دسته الگوریتم ها می توان به الگوریتم های کلونی مورچگان، زنبور عسل، پرندگان و … اشاره کرد.

مقدمه

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

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

این الگوریتم برای حل و بررسی محدوده وسیعی از مسائل بهینه سازی به کار برده شده است. از این میان می توان به حل مسأله کلاسیک فروشنده دوره گرد و همچنین مسأله راهیابی در شبکه های مخابرات راه دور اشاره نمود. مساله فروشنده دوره گرد (Traveling Salesman Problem) و یا به اختصار TSP، یکی از مسائل مشهور بهینه سازی ترکیبی است. در این مسأله، یک فروشنده دوره گرد می خواهد به چند شهر سفر کند و کالای خود را به فروش برساند. اما می بایست از تمام شهرها عبور کند، از هر شهر فقط یک بار عبور کند و با طی کوتاه ترین مسیر، سفر خود را به پایان برساند.

حل این مساله کاربردهای وسیعی در حوزه های مختلف مهندسی دارد. از جمله مسائلی که از نظر ریاضی با مسأله TSP معادل هستند، می توان به حل انواع مسایل زمانبندی، مسیریابی، جایابی کالا در انبار، جایابی ماشینها در کارگاه ها، و طراحی مدارات چاپی اشاره نمود.

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

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

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

روشنایی باید با تابع هدف در ارتباط باشد.

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

Begin
   1) Objective function: F(x), X=(x1,x2,...,xd);
   2) Generate an initial population of fireflies Xi (i=1,2,...,n);
   3) Formulate light intensity I so that it is associated with F(X);
   (for example, for maximization problems, I=F(x);)
   4) 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;

end

تشریح الگوریتم

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

فاز اول به روز کردن رنگدانه

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

که در آن (li(t)، li(t-1) ، J(xi(t) به ترتیب مقدار جدید لوسی فرین، مقدار قبلی لوسی فرین و برازندگی مکان کرم i در تکرار t از الگوریتم بوده و ρ وγ اعداد ثابتی برای مدل کردن افت تدریجی و تاثیر برازندگی بر لوسی فرین می باشند.

فاز دوم حرکت

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

در قسمت b از این شکل کرم ها بر اساس میزان لوسی فرین رتبه بندی شده اند، به این صورت که کرم با شماره 1 بیشترین درخشش را دارد. شعاع تصمیم rd در واقع مشخص کننده ی محدوده ای است که کرم های در آن محدوده همسایه محسوب می شوند برای سطح لوسی فرین با کرم مورد نظر مقایسه می شوند. شعاع حسگری rs مشخص کننده ی حد بالایی برای شعاع تصمیم می باشد. در واقع در طی تکرار های الگوریتم FA شعاع تصمیم کرم ها بسته به شرایطی که در آن قرار دارند تغییر می کند ولی به هر صورت شعاع تصمیم هر کرم از شعاع حسگری آن بیشتر نمی شود. شعاع حسگری مدل کننده حداکثر توانایی کرم ها برای مشاهده ی کرم های دیگر می باشد.

در شکل چهار کرم شبتاب a, b, c, d میزان لوسی فرین بیشتری نسبت به کرم شبتاب e دارند ولی کرم شبتاب e تنها در محدوده مشاهده کرم شب تاب های c و d قرار دارد و بنابراین دو جهت ممکن برای انتخاب به منظور حرکت به سمت کرم درخشنده تر پیش روی آن است. برای هر کرم شب تاب i احتمال حرکت به سمت همسایه درخشنده تر j به صورت زیر تعریف می گردد:

که در این رابطه (Ni(t مجموعه کرم های شب تاب همسایه کرم شب تاب i در زمان (t ،dij(t فاصله اقلیدسی بین کرم شبتاب i و j در زمان t و (rdi(t بیانگر برد همسایگی متغیر مربوط به کرم شب تاب i در زمان t است. با فرض انتخاب شدن کرم شب تاب j توسط کرم شب تاب i (با احتمال p که از رابطه بالا بدست می آید) معادله حرکت زمان-گسسته ی کرم شب تاب را می توان به شکل زیر نوشت:

که درآن (xi(t بردار m بعدی مکان کرم شب تاب i در زمان t است، ||.|| عملگر نرم اقلیدسی را نشان می دهد و s اندازه گام حرکت است.

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

سورس کد الگوریتم کرم شب تاب Firefly Algorithm یا به اختصار FA در محیط پایتون نوشته شده است. این سورس کد با استفاده از توابع محک نوشته شده و هم اکنون می‌توانید آن را دانلود بفرمایید. برای اطلاعات بیشتر و دانلود سورس کد بر روی لینک زیر کلیک نمایید.

همین الان کلیک کنید

به روز کردن برد همسایگی

به هر کرم شب تاب i یک همسایگی تخصیص می یابد که برد شعاعی rid آن به طور طبیعی دینامیک است. (0 < rid ≤ rs). دلیل عدم استفاده از یک همسایگی ثابت نیاز به توجیه دارد، از آنجایی که کرم شب تاب ها تنها به اطلاعات محلی در همسایگی شان برای حرکت نیاز دارند، انتظار می رود تعداد قله هایی قابل شناسایی تابع برد حسگری شعاعی است. در واقع اگر برد حسگری هر کرم شبتاب کل فضای جستجو را پوشش دهد همه ی کرم ها به سمت بهینه ی سراسری حرکت می کنند و بهینه های محلی نادیده گرفته می شوند.

از آنجا که اطلاعات از پیش دانسته درباره ی تابع هدف (به عنوان مثال تعداد قله ها و یا فاصله بین قله ها) برای مسئله فرض نمی شود به سادگی نمی توان برد همسایگی ثابتی مناسب برای تمامی تابع های هدف در نظر گرفت. به عنوان نمونه انتخاب برد همسایگی rd برای تابع هدف هایی با کمترین فاصله میان قله های بیشتر از rd نسبت به تابع هایی که این فاصله برای آنها کمتر از rd است مناسب تر است. با فرض r0 به عنوان برد همسایگی اولیه برای هر کرم شبتاب (rid(0) = r0 )، در هر تکرار الگوریتم FA برد همسایگی هر کرم شبتاب با توجه به رابطه زیر به روز می شود:

که در آن β پارامتری ثابت و nt پارامتری برای کنترل تعداد همسایگی ها می باشد.

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

منابع

[1] Yang, Xin-She. “Firefly algorithms for multimodal optimization.” Stochastic algorithms: foundations and applications. Springer Berlin Heidelberg, 2009. 169-178.

[2] Hassanzadeh, Tahereh, Karim Faez, and Golnaz Seyfi. “A speech recognition system based on structure equivalent fuzzy neural network trained by firefly algorithm.” Biomedical Engineering (ICoBE), 2012 International Conference on. IEEE, 2012.

[3] Kumar, Shakti, Parvinder Kaur, and Amarpartap Singh. “Fuzzy model identification: A firefly optimization approach.” International Journal of Computer Applications 58.6 (2012).