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

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

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

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

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

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

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

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

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

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

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

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

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

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

مثال مدل مفهومی جهت گیری عرضی

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

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

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

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

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

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

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

سورس کد الگوریتم Moth-flame optimization algorithm یا به اختصار MFO به زبان پایتون نوشته و اجرا شده است. این سورس کد بر اساس 12 توابع تست الگوریتم MFO یا شمع و پروانه را اجرا می کند. برای دانلود این سورس کد می توانید بر روی لینک زیر کلیک کنید.

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

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

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

که 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

پاورپوینت آماده الگوریتم شمع و پروانه MFO در Microsoft Powerpoint با پسوند pptx. در 16 اسلاید بصورت فارسی به توضیح کامل الگوریتم شمع و پروانه MFO و اصول کلی در آن می پردازد. برای نهیه این پاورپوینت بر روی لینک زیر کلیک کنید.

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

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

نتیجه گیری

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

منابع

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