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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

آرایه‌ای نیز برای تمامی پروانه‌ها برای ذخیره مقادیر تناسب (OM) وجود دارد. یکی دیگر از مؤلفه‌های اصلی در الگوریتم یک ماتریس شبیه به ماتریس پروانه‌ها است که ماتریس شعله یا آتش (F) است و یک آرایه نیز با نام OF برای ذخیره کردن مقدار تابع تناسب آن استفاده می‌شود.

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

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

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

• سورس کد الگوریتم شعله پروانه MFO در متلب — کلیک کنید.

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

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

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

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

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

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

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

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

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

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

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

حرکت مارپیچی

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

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

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

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

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

به وضوح نشان می‌دهند که یک پروانه می‌تواند فضای جستجوی اطراف اطراف را کاوش و بهره برداری کند. شعله در یک بعد. اکتشاف هنگامی اتفاق می‌افتد که موقعیت بعدی در خارج از فضای بین پروانه و شعله باشد ، همانطور که در فلش‌های دارای برچسب ۱ ، ۳ و ۴ مشاهده می‌شود. بهره برداری زمانی اتفاق می‌افتد که موقعیت بعدی در فضای بین پروانه و شعله قرار داشته باشد. در فلش با برچسب ۲. مشاهدات جالبی برای این مدل وجود دارد:

نتیجه گیری

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

منابع

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

لیست الگوریتم های فرا ابتکاری (متاهیوریستیک) برای بهینه سازی

لیست الگوریتم های فرا ابتکاری (متاهیوریستیک) برای بهینه سازی

کلیک کنید