الگوریتم MVO بهینه سازی چند نظمی Multi-Verse Optimizer

الگوریتم MVO

الگوریتم MVO یا بهینه سازی چند نظمی Multi-Verse Optimizer الگوریتم فراابتکاری و مبتنی بر جمعیت است که توسط سید علی میرجلیلی Seyedali Mirjalili در سال 2015 در ژورنال The Natural Computing Applications از انتشارات Springer به چاپ رسیده است. تئوری چند نظمی بر اساس نظریه چند نظمی است که بر این باور استوار است که جهان بر اساس چندین انفجار بزرگ ساخته شده است. این تئوری از وجود چندین جهان موازی خبر می دهد که در موازات هم ادامه می یابند. الگوریتم چند جهانی بر اساس سه محتوا اصلی به نام سفید چاله، سیاه چاله و کرم چاله بنیان شده است. مقاله اصلی این الگوریتم را می توانید از طریق لینک زیر دانلود فرمایید.

دانلود مقاله اصلی

بهینه ساز چند نظمی

نظریه بیگ بنگ بحث می کند که جهان ما با یک انفجار بزرگ آغاز شده است. طبق این نظریه، انفجار بزرگ منشأ همه چیز در این جهان است و قبل از آن چیزی نبوده است. نظریه چند نظمی یا Multi Verse یکی دیگر از نظریه های اخیر و شناخته شده بین فیزیکدانان است. در این تئوری اعتقاد بر این است که بیش از یک بیگ بنگ وجود دارد و هر بنگ باعث تولد یک جهان می شود. اصطلاح چند نظمی بر خلاف نظریه پیدایش یک جهان است، که به وجود جهان های دیگر علاوه بر جهانی که همه ما در آن زندگی می کنیم اشاره دارد. جهان های مختلف با هم تعامل دارند و حتی ممکن است در نظریه چند نظمی با یکدیگر برخورد کنند همچنین ممکن است قوانین فیزیک مختلفی در هر یک از کیهان ها وجود داشته باشد. سه مفهوم اصلی نظریه چند نظمی به عنوان الهام بخش الگوریتم MVO انتخاب شده است: سفیدچاله ها، سیاه چاله ها و کرم چاله ها.

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

الگوریتم MVO سفید چاله سیاه چاله کرم چاله

الگوریتم MVO نمایش سفید چاله سیاه چاله کرم چاله در الگوریتم بهینه سازی چند نظمی و جهان های موازی

هر جهان نرخ تورم inflation rate را دارد که باعث گسترش آن از طریق فضا می شود. سرعت تورم یا انبساط یک جهان از نظر شکل گیری ستارگان ، سیارات ، سیارک ها ، سفید چاله ها، سیاه چاله ها، کرم های چاله ها ، قوانین جرمی و مناسب بودن برای زندگی بسیار مهم است. در یکی از مدل های چند نظمی چرخه ای بحث شده است که جهان های مختلفی برای رسیدن به وضعیت پایدار از طریق سفید چاله ها، سیاه چاله ها و کرم چاله ها در تعامل هستند. این نظریه الهام بخش اصلی الگوریتم بهینه سازی چند نظمی Multi-Verse Optimizer یا الگوریتم MVO است که به صورت مفهومی و ریاضی در ادامه مدل می شود.

الگوریتم MVO

همانطور که در بخش قبل گفته شد الگوریتم MVO یک الگوریتم متاهیورستیک و مبتنی بر جمعیت است. یک الگوریتم مبتنی بر جمعیت روند جستجو را به دو مرحله مهم تقسیم می کند: مرحله اکتشاف exploration و مرحله بهره برداری exploitation. در این الگوریتم از مفاهیم سفید چاله و سیاه چاله برای کشف فضاهای جستجو و از مفهوم کرم چاله در بهره برداری از فضاهای جستجو استفاده می شود. فرض می کنیم که هر راه حل با یک جهان نشان داده شود و هر متغیر در هر جهان یک شیء در آن است. علاوه بر این، به هر راه حل یا جواب یک نرخ تورم اختصاص می یابد، که متناسب با مقدار عملکرد تابع تناسب مربوط به راه حل است. همچنین در این الگوریتم از اصطلاح زمان به جای تکرار استفاده می کنیم زیرا این یک اصطلاح رایج در نظریه و کیهان شناسی چند نظمی است. در هنگام بهینه سازی ، قوانین زیر برای جهان ها در الگوریتم MVO اعمال می شود:

  1. هرچه نرخ تورم یک راه حل (جهان) بالاتر باشد، احتمال داشتن سفیدچاله بیشتر است.
  2. هرچه نرخ تورم یک راه حل (جهان) بالاتر باشد، احتمال داشتن سیاه چاله کمتر است.
  3. جهان هایی که نرخ تورم بالاتری دارند ، تمایل به ارسال اشیاء از طریق سفید چاله ها دارند.
  4. جهان هایی که نرخ تورم کمتری دارند تمایل به دریافت اشیاء بیشتری از طریق سیاه چاله ها دارند.
  5. صرف نظر از نرخ تورم، اشیاء موجود در همه جهان ها ممکن است با حرکت تصادفی به سمت بهترین جهان از طریق کرمچاله ها انتقال یابند.

مدل مفهومی الگوریتم در شکل زیر نشان داده شده است.

نمایش راه حل و جابجایی اشیا در الگوریتم MVO

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

مرحله استخراج

به منظور مدل سازی ریاضی تونل های سیاه چاله / سیاه و تبادل اشیاء جهان ، از مکانیزم چرخ رولت استفاده شده است. در هر تکرار ، جهان ها را بر اساس نرخ تورم آنها مرتب می کنیم و یکی از آنها را با چرخ رولت انتخاب می کنیم تا یک چاله سفید داشته باشد. برای انجام این کار مراحل زیر انجام می شود. فرض بر این است:

جمعیت اولیه در الگوریتم MVO

ماتریس U کل جمعیت اولیه یا جهان ها را نشان می دهد که د ر آن d تعداد پارامترها (متغیرها) و n تعداد کائنات ها (راه حل های نامزد) است:

فرمول جابجایی در الگوریتم MVO

شرط بالا برای ارسال و دریافت اشیا از سفید چاله به سیاه چاله گذاشته شده است که در آن xij پارامتر jام جهان iام را نشان می دهد ، Ui جهان iام را نشان می دهد ،( NI (Ui نرخ تورم عادی جهان iام است، r1 یک عدد تصادفی در [0,1] است و xkj پارامتر j ام از جهان را نشان می دهد که توسط مکانیسم چرخ رولت انتخاب شده است. شبه کد برای این قسمت به شرح زیر است:

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

مرحله بهره برداری

همانطور که در این شبه کد بالا و معادلات (3.1) دیده می شود انتخاب و تعیین حفره های سفید توسط چرخ رولت انجام می شود، که بر اساس نرخ تورم عادی انجام می شود. هرچه نرخ تورم بالاتر باشد احتمال ارسال اشیاء از چند چاله های های سفید به سیاه بیشتر است. لطفا توجه داشته باشید که NI- برای مسائل بیشینه سازی باید به NI تغییر یابد. اکتشاف را می توان با استفاده از این مکانیسم تضمین کرد زیرا جهان ها برای کاوش در فضای جستجو برای تغییر اشیاء و مواجهه با تغییرات ناگهانی را لازم دارند. با مکانیزم فوق، جهان تبادل اشیاء را بدون اغتشاش ادامه می دهد. به منظور حفظ تنوع جهان و انجام استثمار، در نظر گرفته شده كه هر جهان چاله هایی برای انتقال اشیاء خود از طریق فضا به طور تصادفی را دارد. ممکن است مشاهده شود که کرمچاله ها بدون در نظر گرفتن نرخ تورم ، اشیاء جهان را به طور تصادفی تغییر می دهند. به منظور ایجاد تغییرات محلی برای هر جهان و احتمال زیاد بهبود نرخ تورم با استفاده از کرم ها، فرض می کنیم که همیشه بین یک جهان و بهترین عالم شکل گرفته تاکنون تونل های کرم چاله برقرار شده اند. فرمول این مکانیسم به شرح زیر است:

فرمول حرکت کرم چاله در الگوریتم MVO

که در آن Xj پارامتر jام از بهترین جهان تشکیل شده تاکنون را نشان می دهد ، TDR یک ضریب است ، WEP ضریب دیگری است ، lbj حد پایین متغیر jام را نشان می دهد ، ubj حد بالایی متغیر jام است ، xij پارامتر jام جهان iام را نشان می دهد ، و r2 ، r3 ، r4 اعداد تصادفی در بازه [0,1] هستند. شبه کد به شرح زیر است (با فرض اینکه Ub و lb نشانگر حد بالایی و پایین بودن متغیرها هستند):

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

ممکن است از شبه کد و فرمول ریاضی استنباط شود که دو ضرایب اصلی در اینجا وجود دارد: احتمال وجود کرم چاله (WEP) و میزان مسافت طی شده (TDR). ضرایب سابق برای تعیین احتمال وجود کرم چاله در جهان است. به منظور تأکید بر بهره برداری به عنوان پیشرفت روند بهینه سازی، لازم است بطور خطی بیش از تکرارها افزایش یابد. میزان مسافت طی شده نیز عاملی برای تعیین میزان فاصله (تغییر) است که می توان با استفاده از یک کرم چاله در اطراف بهترین عالم به دست آمده تا کنون، از طریق یک کرم چاله جابجا شد. بر خلاف WEP ، TDR بر روی تکرارها افزایش یافته است تا از بهره‌برداری دقیق / جستجوی محلی در اطراف بهترین جهان به دست آمده استفاده شود. وجود Wormhole و فاصله مسافت طی شده در شکل زیر نشان داده شده است. فرمول تطبیقی هر دو ضرایب به شرح زیر است:

مقایسه WEP و TDR در الگوریتم MVO

احتمال وجود کرم چاله (WEP) و میزان مسافت طی شده (TDR).

فرمول WEP در الگوریتم MVO

در فرمول WEP مقدار 0.2=min و max=1 در نظر گرفته شده است همچنین l تکرار فعلی و L حداکثر تکرار را نشان می دهد.

فرمول TDR در الگوریتم MVO

در فرمول TDR نیز p=6 در نظر گرفته شده است. که دقت بهره برداری را در مورد تکرار نشان می دهد. سطح بالاتر ، بهره برداری زودتر و دقیق تر / جستجوی محلی همچنین l تکرار فعلی و L حداکثر تکرار را نشان می دهد. توجه داشته باشید که WEP و TDR نیز می توانند به عنوان ثابت در نظر گرفته شوند.

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

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

مراجع

[1] Seyedali Mirjalili, Seyed Mohammad Mirjalili, Abdolreza Hatamlou. “Multi-Verse Optimizer: a nature-inspired algorithm for global optimization“, The Natural Computing Applications Forum 2015.

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

دیدگاهتان را بنویسید

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

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