شکل۳-۱۱ ) سقوط امپراطوری ها در روند چرخه الگوریتم رقابت استعماری [۳۴]
مراحل ذکر شده در بالا را می‌توان به صورت شبه کد ریز خلاصه کرد.

1. 1. چند نقطه تصادفی روی تابع انتخاب کرده و امپراطوری‌های اولیه را تشکیل بده.

1. 1. مستعمرات را به سمت کشور امپریالیست حرکت بده (سیاست همسان‌سازی یا جذب).

1. 1. عملگر انقلاب را اعمال کن.

1. 1. اگر مستعمره‌ای در یک امپراطوری، وجود داشته باشد که هزینه‌ای کمتر از امپریالیست داشته باشد، جای مستعمره و امپریالیست را با هم عوض کن.

1. 1. هزینه­ کل یک امپراطوری را حساب کن (با در نظر گرفتن هزینه­ امپریالیست و مستعمراتشان).

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

1. 1. امپراطوری‌های ضعیف را حذف کن.

1. 1. اگر تنها یک امپراطوری باقی مانده باشد، توقف کن وگرنه به ۲ برو.

۳-۳) خلاصه­ی فصل
شبکه های عصبی نوعی مدل­سازی ساده­انگارانه از سیستم­های عصبی واقعی هستند که کاربرد فراوانی در حل مسائل مختلف در علوم دارند. حوزه کاربرد این شبکه­ ها آن­چنان گسترده است که از کاربردهای طبقه ­بندی گرفته تا کاربردهایی نظیر درون­یابی، تخمین، آشکارسازی وغیره را شامل می­ شود. شاید مهمترین مزیت این شبکه­ ها، توانایی وافر آن­ها در کنار سهولت استفاده از آن­ها باشد. یکی از پر کابردترین شبکه ­های عصبی، شبکه­ پرسپترون چند لایه با روش یادگیری پس­انتشار خطا می­باشد. یکی از مزایای این شبکه، قدرت زیاد در پیش ­بینی سری­های زمانی است. یعنی پیش ­بینی آینده با در دست داشتن تاریخچه­ گذشته.
یکی از الگوریتم­های تکاملی جدید که برای مسائل بهینه­سازی به­کار گرفته می­ شود، الگوریتم رقابت استعماری است. در حالت کلی الگوریتم رقابت استعماری به هر نوع مسئله بهینه سازی بدون هیچ محدودیتی قابل اعمال است و نسبت به دیگر الگوریتم­های تکاملی از سرعت همگرایی بالایی برخوردار است. همین موضوع باعث شده ‌است تا از این الگوریتم در حل مسائل بسیاری در حوزه مهندسی برق، مکانیک، صنایع، مدیریت، عمران، هوش مصنوعی و غیره استفاده شود [۳۵]، [۳۶]، [۳۷]، [۳۸].

فصل چهارم
معرفی و شبیه­سازی روش پیشنهادی
۴-۱) معرفی مدل
در روش پیشنهادی مشابه [۲۴] یک مدل سیستم برای محیط محاسبات ابری در نظر گرفته شده است. همان­طور که در شکل ۴-۱ دیده می­ شود، این مدل شامل کاربر، کارگزار ابر، فراهم­کنندگان و یک پیش ­بینی­کننده­ میزان تقاضا است.
شکل۴-۱ ) مدل کلی محیط ابر در روش پیشنهادی
در این مدل، کاربران، تقاضاهای خود را در قالب میزان درخواست از هر نوع کلاس ماشین­های مجازی به کارگزار ارسال می­ کنند. کلاس­های ماشین مجازی را با مجموعه­ VM={vm₁,vm₂,…,vm_v} نشان می­دهیم. هر کلاس ماشین مجازی به منظور نوع ویژه­ای از خدمات مانند سرویس­دهنده پست الکترونیکی، سرویس­دهنده خدمات خرید و فروش و غیره تعریف گردیده است. تعداد کل ماشین­ها مجازی را با v نشان می­دهیم. تعدادی فراهم­کننده­ خدمات ابر وجود دارد که هر یک منابعی را برای میزبانی ماشین­های مجازی درخواست شده توسط کاربران فراهم می­ کنند. مجموعه­ فراهم­کنندگان را با P={p₁,p₂,…,p_p} نشان می­دهیم که تعداد کل آن­ها p می­باشد. به منظور سهولت در استفاده از مدل، فرض می­کنیم منابع پیشنهاد شده توسط فراهم­کنندگان چهار نوع هستند. توان محاسباتی (با واحد CPU-hours )، حافظه­ ذخیره­سازی(با واحد GBs)، پهنای باند شبکه (با واحد GBs/day) و انرژی برق(با واحد KWh) که آن­ها را به ترتیب با شماره­های ۱، ۲، ۳ و ۴ مشخص می­کنیم. هر فراهم­کننده­ p_j یک مخزن محدود از منابع را در اختیار دارد و حداکثر ظرفیت هر فراهم­کننده از هر منبع با بردار t_j=(t_j1,t_j2,t_j3,t_j4) نشان داده شده است که t_jk بیشترین ظرفیت فراهم­کننده j از منبع k می­باشد. هر کلاس ماشین مجازی vm_i برای اجرا شدن نیاز به میزان معینی از هر منبع دارد که با بردار r_i=(r_i1,r_i2,r_i3,r_i4)^T نشان داده می­ شود و r_ik نشان­دهنده میزان مورد نیاز از منبع k در ماشین مجازی کلاس i است. میزان درخواست­های حقیقی با بردار a=(a₁,a₂,…,a_n) مشخص شده است. a_i مقدار تقاضای واقعی از کلاس ماشین مجازی i است. پیش ­بینی کننده­ تقاضا، سعی در تخمین درخواست­های واقعی دارد. تقاضاهای پیش ­بینی شده را با بردار d=(d₁,d₂,…,d_n) نشان می­دهیم که در آن d_i میزان پیش ­بینی شده درخواست کاربر از ماشین مجازی نوع i است. در فاز رزرو درخواست­های پیش ­بینی شده به فراهم­کنندگان مختلف تخصیص می­یابد. این تخصیص با ماتریس Q نشان داده شده و عنصر q_ij در این ماتریس نشان­دهنده تعداد ماشین­های مجازی کلاس i است که به فراهم­کننده­ j اختصاص داده شده است. اگر میزان تقاضای پیش ­بینی شده کمتر از میزان حقیقی باشد، فاز برحسب تقاضا فعال می­ شود. بردارo=(o₁,o₂,…,o₃) نشان­دهنده تعداد ماشین­های مجازی است که به فراهم­کنندگان در طرح برحسب تقاضا باید تخصیص داده شود.
کارگزار ابر در این مدل مسئول تأمین درخواست­های کاربر است یعنی تخصیص q_ij. در این رساله این کار با الگوریتم رقابت استعماری صورت می­گیرد. این روش تخصیص­های بهینه را به گونه ­ای انجام می­دهد که هزینه­ منابع برای کاربر حداقل شود.
اغلب فراهم­کنندگان ابر (مانند Amazon EC2) دو نوع طرح پرداخت را پیشنهاد می­ دهند. طرح­های رزرو کردن و برحسب تقاضا. یک فراهم­کننده در ابر قیمت­های متفاوتی را در هر طرح ارائه می­دهد. در طرح رزرو کردن، کاربر مبلغی را از ابتدا برای رزرو منابع پرداخت می­ کند و سپس در حین مصرف هزینه­ای را بابت مصرف منابع رزرو شده می ­پردازد. در طرح برحسب تقاضا کاربر فقط به ازای میزان مصرف خود هزینه می­ کند. بنابراین تأمین منابع در سه فاز رزرو، مصرف و برحسب تقاضا صورت می­گیرد. در مدل مورد بحث، پیش ­بینی کننده­ درخواست با بهره گرفتن از تاریخچه­ استفاده­های قبلی کاربر از هر کلاس ماشین مجازی، درخواست­های آتی را پیش ­بینی می­ کند و به همان میزان در فاز رزرو، ماشین مجازی رزرو می­ کند. زمانی­که نیازهای واقعی کاربران مشخص شد، تأمین به فاز مصرف وارد می­ شود. کاربران به میزان استفاده از منابع رزرو شده، در این فاز هزینه پرداخت می­ کنند و اگر منابع رزرو شده برای درخواست­های حقیقی کافی نباشد، تأمین وارد فاز برحسب تقاضا خواهد شد. کل هزینه­ تأمین معادل مجموع هزینه­ های هر سه فاز است، البته در بیشتر موارد مجموع هزینه­­های فازهای رزرو و مصرف از فاز برحسب تقاضا کمتر است.
برای قیمت­ گذاری منابع، بردار قیمت­­ها در فاز رزرو با c_j=(c_1j,c_2j,c_3j,c_4j) تعریف شده که c_kj قیمت هر واحد منبع k در فراهم­کننده­ j برحسب دلار است. به همین ترتیب بردارهای u_j و p_j نشان­دهنده قیمت­های منابع در هر فراهم­کننده در فازهای مصرف و بر حسب تقاضا است.
با توجه به توضیحات فوق، در این مدل، کمترین هزینه زمانی به­دست می ­آید که پیش ­بینی­ها دقیق­تر بوده و بیشترین تأمین در فاز رزرو صورت می­گیرد. در این مدل ابتدا یک روش برای تخمین درخواست­های آینده باید در نظر گرفته شود. سپس این درخواست­ها توسط الگوریتم بهینه­سازی که در کارگزار پیاده­سازی می­گردد، به فراهم­کنندگان اختصاص داده می­ شود.
۴-۲) الگوریتم پیش ­بینی درخواست بعدی کاربر
در کارهای پیشین، روش­های متعددی برای پیش ­بینی نیازهای آتی ارائه شده است. در تحقیقی که مرجع اصلی این رساله بوده است[۲۴]، برای تخمین درخواست بعدی از سه روش روش فیلتر کالمن ساده، هموارسازی نمایی مضاعف، زنجیره مارکوف استفاده شده است. ما در این بخش از شبکه­ عصبی پرسپترون چند لایه با روش یادگیری پس انتشار خطا استفاده کرده­ایم. الگوریتم این روش به صورت زیر است.
الگوریتم پیش ­بینی درخواست بعدی کاربر با روش MLP with EBP

1. 1. از میان داده ­های آموزش یک دسته را به تصادف انتخاب کن.

1. 1. مقادیر تصادفی بین صفر و یک را به عنوان وزن­های اولیه تولید کن.

1. 1. مقادیر تصادفی بین ۱ و ۱- را به عنوان مقادیر اولیه­ بایاس­ها تولید کن.

1. 1. نرخ یادگیری اولیه را تولید کن.

1. 1. وزن­ها، بایاس­ها و داده ­های ورودی را نرمال کن.

1. 1. سطح فعالیت گره­های لایه­ی مخفی را محاسبه کن.

1. 1. سطح فعالیت گره خروجی را محاسبه کن.

1. 1. برای گره­های لایه­ی مخفی و گره­ خروجی عبارت خطا را محاسبه کن.

1. 1. تغییرات وزن­ها را با در نظر گرفتن جمله­ گشتاور محاسبه کن.

1. 1. تغییرات بایاس را محاسبه کن.

1. 1. خطای خروجی را محاسبه کن.

1. 1. اگر تعداد گام­های آموزش مضربی از S رسید، وزن­های به­دست آمده را به داده ­های اعتبارسنجی اعمال کن. اگر خطا از e کمتر است آموزش را متوقف کن و به مرحله­ ۱۴ برو. در غیر این­صورت به مرحله­ ۱۳ برو.

1. 1. یک دسته­ی دیگر از داده ­های آموزش را انتخاب کن و به مرحله­ ۵ بازگرد.

1. 1. وزن­های به­دست آمده را با داده ­های تست محک بزن. اگر خطا کمتر از e است، وزن­ها را ذخیره کن و برای تعیین میزان درخواست بعدی از ماشین مجازی دیگر به مرحله­ ۱ برگرد. در غیر این­صورت برای همین ماشین­مجازی به مرحله­ ۱۳ برگرد.

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

1. 1. پایان

مزیت استفاده از این روش انعطاف­پذیر بودن آن در مقابل انواع ورودی و توانایی یادگیری بالای آن می­باشد که باعث می­ شود تخمین­ها با دقت بالایی انجام شود. نتایج حاصل از ارزیابی روش فوق و مقایسه با سایر روش­ها که در بخش ارزیابی آمده است، گویای مزیت این روش نسبت به روش­های قبلی می­باشد.
۴-۳) الگوریتم بهینه­سازی هزینه­ تأمین منابع