وبلاگ

در تحقیقات پیشین، الگوریتم­های مانند EVU، SIP، کلونی مورچگان و ژنتیک به منظور بهینه­سازی هزینه­ تأمین به­کار گرفته شده ­اند[۱۹] [۲۰] [۲۴] [۲۵]. ما در روش پیشنهادی در این رساله از الگوریتم رقابت استعماری به منظور تخصیص بهینه­ ماشین­های مجازی به فراهم­کنندگان و در نتیجه کاهش هزینه­ کل تأمین برای کاربر استفاده کرده­ایم. در فصل قبل روش کلی این الگوریتم به طور مفصل شرح داده شد. در این­جا الگوریتم تطبیق یافته با صورت مسئله آمده است.

الگوریتم بهینه­سازی هزینه­ تأمین با تخصیص ماشین­های مجازی به فراهم­کنندگان با رقابت استعماری

 

1. 1. از الگوریتم قبل میزان تقاضای پیش ­بینی شده برای هر کلاس ماشین مجازی (بردار d) را دریافت کن.

 

1. 1. I کشور اولیه را به صورت آرایه­های m*n عنصری تشکیل بده که هر عنصر نشان­دهنده تعداد ماشین مجازی کلاس i است که به فراهم­کننده­ j تخصیص داده می­ شود(q_ij).

 

1. 1. برای مقدار دهی اولیه به I کشور مراحل زیر را انجام بده.

      1. 1. برای هر m عنصر یک کشور، مقادیر تصادفی بین صفر و d_i تولید کن به طوری که شروط زیر برقرار باشد.

       

      1. 1. اگر هنوز I کشور تولید نشده به مرحله­ ۳ برگرد.

       

       

 

1. 1. اگر در فاز رزرو است از قسمت a، اگر در فاز مصرف است از قسمت b و اگر در فاز برحسب تقاضا است از قسمت c استفاده کن و هزینه­ I کشور را محاسبه کن.

 

1. 1. h کشور را که هزینه­ کمتری دارند به عنوان امپریالیست انتخاب کن.

 

1. 1. برای هر امپراطوری نسبت کسب مستعمره را با بهره گرفتن از رابطه­ زیر محاسبه کن.

 

1. 1. از بین کشورهای مستعمره به نسبت pn[empire] به هر امپراطوری تخصیص بده.

 

1. 1. سیاست جذب : تعدادی از خانه­های هر مستعمره را به تصادف انتخاب کن و مقادیر آن­ها را با مقادیر نظیر از امپراطوری جایگزین کن. شروط موجود در مرحله­ ۳ را برای مستعمره بررسی کن. اگر برقرار نبود سیاست جذب را در مورد مستعمره تکرار کن.

 

1. 1. مرحله­ ۴ را تکرار کن.

 

1. 1. جابجایی موقعیت مستعمره و امپریالیست: برای تمام امپراطوری­ها مراحل زیر را انجام بده:

      1. 1. قدرت کل امپراطوری را با رابطه­ زیر محاسبه کن:

       

      1. 1. اگر مستعمره­ای در آن امپراطوری وجود دارد به طوری­که cost[colony]<TCn[empire] است، جای امپراطوری و مستعمره را عوض کن.

       

       

 

1. 1. رقابت استعماری : از بین امپراطوری­ها، آن را که قدرت کل بیشتری دارد، یعنی پرهزینه­تر است، انتخاب کن و مراحل زیر را انجام بده:

      1. 1. ضعیف­ترین مستعمره­ی آن امپراطوری را پیدا کن(مستعمره با هزینه­ بیشتر)

       

      1. 1. بردار R=[R₁,…,R_h] را که R_empireها اعدادی تصادفی بین ۰ و ۱ هستند تشکیل بده.

       

      1. 1. بردار D را از رابطه­ زیر محاسبه کن:

       

      1. 1. مستعمره­ی ضعیف را به امپراطوری بده که مقدار نظیر آن در بردار D از همه بیشتر است.

       

       

 

1. 1. اگر امپراطوری وجود دارد که فاقد مستعمره است، آن را حذف کن.

 

1. 1. اگر تنها یک امپراطوری باقی مانده است هزینه­ آن را به عنوان هزینه­ بهینه­ این فاز تأمین در نظر بگیر. در غیر این­صورت به مرحله­ ۸ بازگرد.

 

1. 1. مقدار حقیقی درخواست­ها را برا ی فاز مصرف و اختلاف بین مقدار پیش ­بینی شده با مقدار حقیقی را برای فاز برحسب تقاضا در بردار d قرار بده و مراحل ۲ تا ۱۳ را برای فاز­های مصرف و برحسب تقاضا تکرار کن.

 

1. 1. مجموع هزینه­ هر سه فاز را به عنوان هزینه­ تأمین بهینه اعلام کن.

 

1. 1. پایان

 

ویژگی این الگوریتم نسبت به روش­های قبل، همگرایی آن و نیز کمتر نمودن هزینه­ تأمین است.
۴-۴) ارزیابی روش­ پیشنهادی و مقایسه با سایر روش­ها با بهره گرفتن از نتایج حاصل از شبیه­سازی
برای ارزیابی روش ارائه شده در این رساله، دو الگوریتم تخمین و بهینه­سازی به صورت یک شبیه­ساز در محیط NetBeans طراحی گردید. با توجه به این­که مدل ارائه شده در این رساله با مدل موجود در [۲۴] بیشترین شباهت را دارد، پارامترهای سیستم را مشابه آن تنظیم می­کنیم و سپس نتایج را مقایسه خواهیم کرد. این تنظیمات به صورت زیر است:

 

• • فرض می­کنیم سیستم سه کلاس ماشین مجازی، چهار فراهم­کننده و یک کاربر دارد.

 

• • تعداد درخواست­ها برای هر ماشین مجازی را عددی بین صفر تا ۵۰ در نظر گرفته شده و به منظور سهولت فرض بر این است که میزان درخواست برای همه کلاس­های ماشین مجازی مشابه است.

 

• • ۱۰۰ داده به عنوان تاریخچه­ درخواست­ها با دو توزیع نرمال و یکنواخت تولید شده که در توزیع نرمال میانگین ۵/۲۵ و واریانس ۱۲ و در توزیع یکنواخت میانگین ۵/۲۵ در نظر گرفته شده است.

 

• • در الگوریتم تخمین از شبکه­ پرسپترون سه لایه با یک لایه­ی مخفی استفاده شده است. سه گره در لایه­ی ورودی و چهار گره در لایه­ی مخفی در نظر گرفته شده است.

 

• • نرخ یادگیری در الگوریتم تخمین با مقدار ۵/۰ آغاز شده است. از ۶۰% داده ­ها برای آموزش، ۲۰% برای اعتبارسنجی و ۲۰% برای تست روش استفاده شده است.

 

• • جمعیت اولیه­ کشورها در الگوریتم بهینه­سازی ۱۰۰ و تعداد امپراطوری­های اولیه ۱۰ می­باشد.

 

• • قیمت هر نوع منبع در هر فراهم کننده در جدول ۴-۱، مقدار منابع مورد نیاز هر کلاس ماشین مجازی در جدول ۴-۲ و حداکثر ظرفیت هر فراهم­کننده از هر نوع منبع در جدول ۴-۳ مشخص شده است.

 

• برنامه ۱۰ بار اجرا شده و میانگین نتایج حاصل به عنوان هزینه در نظر گرفته شده است.