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

امتیاز 5.00 ( 1 رای )

الگوریتم سنجاقک

واقعیت جالب در مورد سنجاقک ها رفتار ازدحامی منحصر به فرد و نادر این حشره می باشد. توده سنجاقک ها تنها برای دو هدف شکل می گیرند: شکار و مهاجرت که شکار را توده استاتیک یا تغذیه می نامند و مهاجرت را توده داینامیک یا مهاجر می نامند. در توده ثابت یا استاتیک سنجاقک ها گروه های کوچکی را تشکیل می دهند و در یک ناحیه کوچک به جلو و عقب حرکت می کنند تا سایر حشرات پرنده مانند پروانه ها و پشه ها را شکار کنند. تحرکات محیطی و تغییرات ناگهانی در مسیر پرواز ازمشخصه های اصلی توده ایستا می باشد.در توده های داینامیک تعداد زیادی از سنجاقک ها یک توده برای مهاجرت در یک جهت و با مسافت طولانی را شکل می دهند.
ایده اصلی الگوریتم سنجاقک از رفتارهای ازدحام ایستا و داینامیک سرچشمه می گیرد. این دو رفتار ازدحامی خیلی شبیه به دو مرحله اصلی از بهینه سازی با الگوریتم های فرا اکتشافی می باشد:

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

شکل2-5

الگوهای اصلاحی اولیه بین افراد در گروه سنجاقک هاعبارتند از:

  1. جدایی یا تفکیک: این عملگر اشاره به اجتناب یک فرد با سایر افراد همسایه در یک فضا دارد.
  2. ترازبندی: عدم تجاوز سرعت ذرات یا اشیا نسبت به سایر همسایه ها در یک فضای واحد یا تنظیم سرعت افرادبا توجه به سایر افراد همسایه می باشد.
  3. انسجام: این عملگر نیز اشاره به تمایل افراد به سمت مرکز ثقل همسایه ها را دارد.

هدف اصلی هر توده و گروه در سناریو فوق حفظ بقا می باشد. بنابراین همه افراد باید به سمت منبع غذایی جذب شوند و از دشمن ها دور بمانند. با توجه به این دو رفتار ذرات، 5 عامل اصلی در بروز رسانی موقعیت ذرات وجود دارد که در شکل فوق نشان داده شده است.

این 5 مفهوم اجازه می دهد که رفتار سنجاقک ها را در توده های ایستا و پویا شبیه سازی کنیم.هر کدام از رفتار های فوق با استفاده از مدلهایی فرموله بندی شده اند که در قسمت زیر مورد بحث قرار گرفته است.

عملگر جدایی در فرمول زیر مدل شده است.

در فرمول بالا X موقعیت فرد جاری ، Xj موقعیت jمین فرد در همسایگی و N تعداد همسایه های موجود در همسایگی فرد را نشان می دهد.

ترازبندی نیز با استفاده از فرمول زیر مدل شده است:

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

در فرمول بالا X موقیت یک فرد ، Xj موقعیت jمین همسایه در محیط و N تعداد همسایه های مربوط به فرد مورد نظر است. فرمول بالا ارتباط بسیار نزدیکی با فرمول جدایی داشته و به منظور یافتن میانگین میزان اختلاف موقعیت ماشین مجازی فعلی با سایر ماشین های مجازی موجود در روش پیشنهادی استفاده می-گردد.

جهش به سمت منبع غذایی توسط افراد با استفاده از رابطه زیر فرموله شده است:

در فرمول بالا X موقعیت فرد و X¬¬+ نیز موقعیت منبع غذایی را نشان می دهد. در فرمول فوق پس از یافتن ماشین مجازی کم بار جهت اجرای کارهای با اولویت بالاتر توسط سنجاقک ها، جهش به سمت ماشین مجازی مربوطه صورت می گیرد که در قالب رابطه به آن پرداخته شده است.


فرار از دشمن نیز با فرمول زیر نشان داده می شود:

بطور کلی با استفاده از فرمول فوق ماشینهای مجازی که مناسب جهت انتخاب و اجرای کار مورد نظر نیستند از لیست انتخاب ها حذف می شوند.
رفتار سنجاقک ترکیبی از این 5 الگوی مطرح شده است. به منظور بروزرسانی موقعیت سنجاقک های مصنوعی درفضای جستجو و شبیه سازی حرکت آنهادر یک محدده، الگوریتم سنجاقک دو بردار را در نظر می گیرد:1- بردار طول گام (دلتای X ) و 2- بردارموقعیت X.
بردار طول گام همانند بردار سرعت در الگوریتم بهینه سازی PSO است و الگوریتم سنجاقک نیز بر اساس چارچوب PSO توسعه یافته است. بردار طول گام جهت حرکت سنجاقک ها را مشخص می¬کند که در رابطه زیر مورد بررسی قرار گرفته است:


که در آن s ضریب تفکیک را نشان می دهد، Si میزان تفکیک مربوط به فرد iام می باشد و a وزن ترازبندی را نشان می دهد. A ترازبندی iمین فرد است، c نیز ضریب انسجام و Ci نیزمقدار انسجام i مین فردرا نشان می دهد.F معیار غذا و Fi نیز منبع غذایی مربوط به iمین فرد را نشان می دهد.E فاکتور دشمن و Ei نیز موقعیت i مین دشمن را نشان می دهد.w وزن اینرسی می باشد و در نهایت t نیز تعداد تکرار الگوریتم را نشان می دهد.
بعد از اینکه بردار گام محاسبه شد، بردارهای موقعیت با استفاده از فرمول زیر محاسبه می گردد:

xt موقعیت فعلی را نشان می دهد. بطور کلی از بردار های نام برده جهت مدیریت همسایگان و ارائه گزارشی از موقعیت و نحوه تبادل ارتباط ماشین های مجازی با یکدیگر توسط سنجاقک ها مورد استفاده قرار می گیرد.
با استفاده از فاکتورهای تفکیک، ترازبندی، انسجام، غذا و دشمن رفتار های اکتشافی و بهره برداری مختلف در طول اجرای الگوریتم اتفاق می افتد.همسایه سنجاقک ها خیلی مهم می باشند بنابر این یک همسایگی به شکل دایره در فضای دو بعدی کره در فضای سه بعدی و ابر کره در فضای n بعدی با یک شعاع خاص در اطراف هر سنجاقک مصنوعی در نظر گرفته شده است. یک مثال از رفتار ازدحامی سنجاقک ها با شعاع همسایگی افزایشی با مدل ریاضی پیشنهاد شده در شکل2-5 نمایش داده شده است.
همانطور که در بخش قبل صحبت شد سنجاقک ها دو نوع ازدحام را شکل میدهند: ایستا و پویا همانطور که در شکل ‏زیر نشان داده شده است:

شکل2-6

با توجه به شکل بالا میتوان دیدسنجاقک ها تمایل دارند پرواز خود را جهت دهی کنند. درحالیکه تفکیک و انسجام مناسب در ازدحام پویا را حفظ می کنند. در ازدحام ایستا جهت دهی خیلی کم است در حالیکه ازدحام برای حمله به طعمه زیاد می باشد. بنابراین ما سنجاقک ها را با جهت دهی کم و انسجام بالا در زمان بهره برداری از فضای جستجو در نظر می گیریم. به منظور جابجایی بین اکتشاف و بهره برداری شعاع همسایگی با افزایش تعدادتکرارهای الگوریتم افزایش می یابد. راه دیگر برای ایجاد تعادل بین اکتشاف و بهره برداری تنظیم انطباقی فاکتورهای ازدحام یعنی (s,a,c,f,e,and w) در حین بهینه سازی می باشد.
سوالی که ممکن است مطرح شود این است که همگرایی سنجاقک ها در حین بهینه سازی به چه شکل تضمین می شود.سنجاقک ها نیاز دارند تا وزنهای خود را برای انتقال از اکتشاف به بهره برداری در فضای جستجو تطبیق دهند.همچنین فرض می شود که سنجاقک ها تمایل به دیدن سنجاقک های بیشتری برای تنظیم جهت پرواز خود در فرآیند بهینه سازی دارند.به عبارت دیگر ناحیه همسایگی افزایش می یابد و به موجب آن ازدحام به یک گروه در مرحله نهایی از بهینه سازی تبدیل می شود تا به بهینه سراسری همگرا شود. ناحیه منبع غذا و دشمن از بهترین و بدترین جواب هایی که در کل ازدحام تا کنون پیدا شده است به دست می آید. این باعث همگرایی به سمت مناطق امیدوارکننده از فضای جستجو و واگرایی از مناطق نامطلوب در فضای جستجو می شود.
به منظور بهبود رفتارهای تصادفی و اتفاقی و اکتشاف سنجاقک های مصنوعی آنها نیاز دارند تا در زمانی که هیچ راه حلی در همسایگی آنها وجود ندارد در اطراف فضای جستجو با استفاده از یک طول گام تصادفی پرواز کنند. در این حالت موقعیت سنجاقک هابا استفاده از رابطه زیر به روزرسانی می شود:

Xt+1­­=X­­­­­­­­t+Le’vy(d)× X­­­­­­­­t

که t شمارنده تکرار فعلی می باشد و بعد های بردار موقعیت می باشد و مقدار با استفاده از رابطه زیر محاسبه می شود.

که r1, r2  دو عدد تصادفی در بازه صفر و یک و یک ثابت می باشد (که در این کار مساوی 1.5 در نظرگرفته شده است ). الگوریتم بهینه سازی DA در قسمت زیر مورد بررسی قرار می گیرد؟

الگوریتم  DA فرآیند بهینه سازی را با ایجاد یک مجموعه از راه حل های تصادفی برای مسئله بهینه سازی داده شده شروع می­كند. در حقیقت بردارهای موقعیت و گام مربوط به سنجاقک ها بصورت تصادفی و با توجه به حد پایین و بالای متغیر ها مقداردهی اولیه می­شوند.در هر تکرار بهترین موقعیت و مکان هر سنجاقک با استفاده از روابط بالا بروز رسانی می­شود.ب رای بروز کردن بردارهای X و DX همسایگی هر سنجاقک با محاسبه کردن فاصله اقلیدسی بین همه سنجاقک ها و انتخاب N تای آنها صورت می­گیرد. فرآیند بروزرسانی موقعیت به صورت تکرار شونده ادامه می یابد تا زمانیکه شرط توقف برآورده شود.

در اینجا به تفاوت اصلی بین الگوریتم DA و PSO  اشاره می­کنیم.در نظر گرفتن مفاهیم تفکیک یا جدایی separation تخصیص یا جهت دهی alighnment و انسجام یا cohesion ، جاذبه یا attraction ، دافعه یا disattraction در این کار و حرکت تصادفی random walk از مهمترین تفاوت ها می باشند.

مراحل اجرای الگوریتم DA به صورت زیر می باشد:

1- مقداردهی به پارامترهای الگوریتم

2- ساخت جمعیت اولیه سنجاقک ها به صورت تصادفی

3- ارزیابی موقعیت هر سنجاقک و محاسبه شایستگی آن

4- شناسایی بهترین سنجاقک به عنوان منبع غذا یا FoodSourceو بدترین سنجاقک به عنوان دشمن یا Enemy

5- تا زمانیکه شرط توقف برقرار نشده است مراحل 6 تا 13 را برقرار­کن.

6- مقدار پارامترهای e,w,s,a,c,f و شعاع همسایگی را به روز رسانی­کن.

7- برای هر سنجاقک مراحل 8 تا 12 را تکرار کن.

8- شعاع همسایگی را به روزرسانی­کن.

9- مقادیر E,F,C,A,S را به روزرسانی­کن.

10- بردار سرعت و بردار موقعیت سنجاقک را بروز رسانی­کن.

11- شایستگی سنجاقک به روز شده را محاسبه­ کن.

12- اگر میزان شایستگی سنجاقک جدید بهتر از منبع غذا بودسنجاقک جدید را به عنوان منبع غذا قرار بده و اگر میزان شایستگی سنجاقک جدید بدتر از دشمن است آنرا جایگزین دشمن کن.

 13- اگرشرط توقف برقرار نشده است به مرحله 5 برو وگرنه پایان لذا با توجه به بررسی الگوریتم سنجاقک مشاهده گردید که با استفاده از این الگوریتم در هر لحظه می­توان مناسبترین ماشین های مجازی را جهت انجام پردازش های لازم به منظور کاهش مصرف انرژی در مراکز داده، حفظ تعادل بار و ارائه یک مکانیزم زمانبندی کارها استفاده نمود

2474 بازدید