الگوریتم شعله پروانه MFO

الگوریتم MFO

معرفی الگوریتم شعله پروانه

الگوریتم شعله پروانه یا الگوریتم Moth-flame optimization algorithm که به اختصار الگوریتم MFO یا الگوریتم شمع و پروانه نیز نامیده می شود یکی از الگوریتم های بهینه سازی و فراابتکاری است که از رفتار پروانه ها در کنار شعله یا آتش روشی برای حل مسئله پیدا می کند. این الگوریتم در سال 2015 توسط سید علی میر جلیلی در مقاله ای تحت عنوان:

Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm

در ژورنال Knowledge-Based Systems مطرح شد. الگوریتم شعله پروانه با نام های دیگری همچون الگوریتم پروانه آتش، الگوریتم MFO، الگوریتم پروانه شعله و الگوریتم شمع و پروانه نیز شناخته می شود. این الگوریتم یک الگوی اکتشافی نوین الهام گرفته از طبیعت و رفتار پروانه ها و علاقه مندی آن ها به شعله یا آتش است. در این پست می خواهیم به تشریح و توضیح الگوریتم شعله پروانه بپردازیم.

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

در این پست یک الگوریتم بهینه سازی جدید با الهام از طبیعت با نام الگوریتم بهینه سازی شعله (MFO) یا الگوریتم شمع و پروانه ارائه شده است. الهام بخش اصلی این بهینه ساز روش ناوبری پروانه ها در طبیعت به نام جهت گیری عرضی (transverse orientation) است. پروانه ها با حفظ یک زاویه ثابت با توجه به ماه، پرواز در شب را برای مسافت های طولانی انجام می دهند. ولی این حشرات فانتزی در یک مسیر مارپیچی بی فایده و کشنده در اطراف چراغ های مصنوعی به دام می افتند.

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

الگوریتم شعله پروانه

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

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

الگوریتم بهینه سازی پروانه آتش Moth-Flame Optimiser

شب پره ها حشرات فانتزی هستند که بسیار شبیه خانواده پروانه ها هستند. اصولاً بیش از 160،000 گونه مختلف از این حشره در طبیعت وجود دارد. آنها دو مرحله اصلی در طول زندگی خود دارند: لارو و بزرگسال. لاروها در پیله ها به پروانه تبدیل می شوند. جالب ترین واقعیت در مورد پروانه ها روش های ویژه ناوبری آنها در شب است. آنها تکامل یافته اند تا در شب با استفاده از نور ماه پرواز کنند. آنها از مکانیسمی به نام جهت دهی عرضی برای ناوبری استفاده کردند. در این روش ، یک پروانه با حفظ یک زاویه ثابت با توجه به ماه پرواز می کند، مکانیسم بسیار موثری برای سفر در مسافت های طولانی در یک مسیر مستقیم است.


بیشتر بدانید

فیلم آموزشی الگوریتم وال یا نهنگ WOA در متلب

حل مسئله فروشنده دوره گرد TSP با الگوریتم گرگ خاکستری GWO در متلب

فیلم آموزشی حل مسئله فروشنده دوره گرد با الگوریتم GSA در متلب


مثال

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

سیستم ناوبری پروانه

با وجود اثربخشی جهت گیری عرضی (transverse orientation)، معمولاً مشاهده می کنیم که پروانه ها به صورت مارپیچ در اطراف چراغ ها پرواز می کنند. در حقیقت، پروانه ها توسط چراغ های مصنوعی فریب خورده و چنین رفتارهایی را نشان می دهند. این امر به دلیل ناکار آمدی جهت گیری عرضی است که در آن تنها هنگامی که منبع نور بسیار دور است، برای حرکت در خط مستقیم مفید است. هنگامی که پروانه ها نور مصنوعی ساخته شده توسط انسان را مشاهده می کنند، سعی می کنند زاویه ای مشابه با نور را حفظ کنند تا به صورت مستقیم پرواز کنند.

از آنجا که چنین نوری در مقایسه با ماه بسیار نزدیک است، اما حفظ زاویه ای مشابه با منبع نور باعث می شود مسیر پرواز مارپیچی بی فایده یا کشنده برای پروانه ها باشد. یک مدل مفهومی از این رفتار در شکل زیر نشان داده شده است. ممکن است در شکل زیر مشاهده شود که پروانه در نهایت به سمت نور همگرا می شود. این رفتار از لحاظ ریاضی مدل سازی شده است تا یک بهینه ساز بنام الگوریتم بهینه سازی شعله (MFO) یا الگوریتم شمع و پروانه را بوجود آورد.

حرکت مارپیچی پروانه

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

در الگوریتم MFO، فرض بر این است که راه حل های کاندید پروانه ها هستند و متغیرهای مسئله موقعیت پروانه ها در فضا است. بنابراین، پروانه ها با تغییر بردارهای موقعیتی خود می توانند در فضای یک بعدی، دو بعدی یا سه بعدی پرواز کنند. از آنجا که الگوریتم MFO یک الگوریتم مبتنی بر جمعیت است، مجموعه پروانه در یک ماتریس (مثلاً M) نمایش داده می شوند. آرایه ای نیز برای تمامی پروانه ها برای ذخیره مقادیر تناسب (OM) وجود دارد. یکی دیگر از مؤلفه های اصلی در الگوریتم یک ماتریس شبیه به ماتریس پروانه ها است که ماتریس شعله یا آتش (F) است و یک آرایه نیز با نام OF برای ذخیره کردن مقدار تابع تناسب آن استفاده می شود.

ماتریس پروانه و شعله

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

مقدار دهی اولیه

برای تولید راه حل های اولیه و محاسبه مقادیر تناسب هر یک از آنها از هر توزیع تصادفی می توان استفاده کرد. روش زیر به عنوان پیش فرض استفاده می شود:

الگوریتم پروانه آتش

که ub کران بالا و ul کران پایین مقدار متغیر i است. بدین ترتیب برای n در d بعد قادر به تولید جواب اولیه هستیم. پس از مقدار دهی اولیه می توان تناسب هر یک از راه حل را حساب کرد بنابراین OM مقدار تابع تناسب ماتریس M یا پروانه ها خواهد بود.

تکرار الگوریتم

پس از مقدار دهی اولیه،حرکت پروانه ها یا تابع P به طور تکراری اجرا می شود تا عملکرد T یعنی حد همگرایی به شعله یا شمع، مقدار True را برگرداند. عملکرد P عملکرد اصلی است که پروانه ها را در فضای جستجو حرکت می دهد. همانطور که گفته شد الهام بخش این الگوریتم جهت گیری عرضی است.

مارپیچ لگاریتمی

مارپیچ لگاریتمی (logarithmic spiral) به عنوان مکانیزم اصلی بروزرسانی پروانه در این الگوریتم انتخاب شده است. با این وجود، هر نوع مارپیچ با توجه به شرایط زیر قابل استفاده است:

  • نقطه اولیه Spiral باید از پروانه شروع شود.
  • نقطه آخر Spiral باید موقعیت شعله باشد.
  • نوسان دامنه مارپیچ نباید از فضای جستجو تجاوز کند.

با توجه به این نکات ، یک مارپیچ لگاریتمی برای الگوریتم MFO به شرح زیر تعریف می شود:

الگوریتم پروانه آتش

که در این رابطه Di فاصله پروانه i ام برای شعله j ام را نشان می دهد ، b یک ثابت برای تعیین شکل مارپیچ لگاریتمی است و t یک عدد تصادفی در بازه [1 ، 1-] است. D به شرح زیر محاسبه می شود:

الگوریتم پروانه آتش

در معادله مارپیچی لگاریتمی مسیر پرواز مارپیچی پروانه ها در الگوریتم شمع و پروانه شبیه سازی می شود. همانطور که در این معادله دیده می شود، موقعیت بعدی پروانه با توجه به شعله تعریف می شود. پارامتر t در معادله مارپیچی مشخص می کند که موقعیت بعدی پروانه باید نزدیک شعله باشد (t=-1 نزدیکترین موقعیت به شعله است ، در حالی که t =1 دورترین را نشان می دهد). بنابراین می توان یک شکل بیضی وار از اطراف شعله در همه جهات فرض کرد و موقعیت بعدی پروانه در این فضا قرار گرفت.

حرکت مارپیچی

حرکت مارپیچ اصلی ترین روش پیشنهادی است زیرا چگونگی به روزرسانی پروانه ها مواضع خود را در اطراف شعله ها نشان می دهد. معادله مارپیچی به پروانه ای اجازه می دهد تا “اطراف” شعله ها پرواز کند و نه لزوماً در فضای بین آنها. بنابراین ، اکتشاف و بهره برداری از فضای جستجو می تواند تضمین شود. مارپیچ لگاریتمی ، فضای اطراف شعله و موقعیت با در نظر گرفتن t متفاوت در منحنی در شکل زیر نشان داده شده است.

الگوریتم MFO


بیشتر بدانید

فیلم آموزشی الگوریتم گرگ خاکستری GWO در متلب

سمینار آماده الگوریتم جستجوی گرانشی

حل مسئله فروشنده دوره گرد TSP با الگوریتم گرگ خاکستری GWO در متلب


به روزرسانی موقعیت یک پروانه

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

به وضوح نشان می دهند که یک پروانه می تواند فضای جستجوی اطراف اطراف را کاوش و بهره برداری کند. شعله در یک بعد. اکتشاف هنگامی اتفاق می افتد که موقعیت بعدی در خارج از فضای بین پروانه و شعله باشد ، همانطور که در فلش های دارای برچسب 1 ، 3 و 4 مشاهده می شود. بهره برداری زمانی اتفاق می افتد که موقعیت بعدی در فضای بین پروانه و شعله قرار داشته باشد. در فلش با برچسب 2. مشاهدات جالبی برای این مدل وجود دارد:

الگوریتم MFO

نتیجه گیری

در این مقاله سعی شد تا روش کار الگوریتم MFO یا الگوریتم شمع و پروانه تشریح شود. این الگوریتم با توجه به رفتار پروانه ها در چرخش به دور شعله مدلی ارائه می دهد تا راه حل های احتمالی یعنی همان پروانه ها نسبت به شعله یعنی جواب های بهینه همگرا شوند. این الگوریتم کارایی زیادی در زمینه حل مسائل پیوسته و NP-Hard دارد و به استناد مقاله اصلی می توان از این روش برای حل بسیاری از مسائل سخت استفاده کرد.

منابع

Seyedali Mirjalili, Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm, Knowledge-Based Systems 89 (2015) 228–249.

مطالب زیر را حتما بخوانید

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

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