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

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

مقدمه

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

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

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

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

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

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

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

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

پیشنهاد می‌کنیم دانشجویانی که به دنبال ارائه خوب در کلاس هستند پاورپوینت موجود در لینک زیر را دانلود کرده و آن ارائه دهند.

• پاورپوینت الگوریتم کرم شب تاب 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 با مدلسازی رفتار مجموعه‌ای از کرم‌های شب تاب و تخصیص مقداری مرتبط با برازندگی مکان هر کرم شب تاب به عنوان مدلی برای میزان رنگدانه‌های شب تاب و به روز کردن مکان کرم‌ها در تکرارهای متوالی الگوریتم به جستجوی جواب بهینه مسئله می‌پردازد. در واقع دو مرحله اصلی الگوریتم در هر تکرار فاز به روز کردن رنگدانه و فاز حرکت هستند. کرم‌های شب تاب به سمت کرم‌های شب تاب دیگر با رنگدانه بیشتر که در همسایگی آنها باشند حرکت می‌کنند. به این ترتیب طی تکرارهای متوالی مجموعه به سمت جواب بهتر متمایل می‌گردد.

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

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

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

فاز دوم حرکت

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

در قسمت b از این شکل کرم‌ها بر اساس میزان لوسی فرین رتبه بندی شده‌اند، به این صورت که کرم با شماره ۱ بیشترین درخشش را دارد. شعاع تصمیم 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 اندازه گام حرکت است.

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

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

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

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

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

منابع

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

[۲] 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.

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

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

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

کلیک کنید