Loading...
توازن بار در محاسبات ابری ترکیبی با MATLAB
در این بخش پروژه شبیه سازی توازن بار در محاسبات ابری ترکیبی با الگوریتم ژنتیک در نرم افزار MATLAB به همراه فیلم آموزشی آماده کرده ایم که در ادامه توضیحاتی از معرفی پروژه ارائه شده و قسمتی از فیلم آموزشی همراه با تصاویر خروجی پروژه در محیط متلب قرار داده شده است.
محاسبات ابری
محاسبات ابری (Cloud computing) یک زیرساخت مهم برای سیستم های توزیع شده است. هدف اصلی در استفاده از محاسبات ابری، کاهش هزینه های استفاده از منابع می باشد. الگوریتم ژنتیک با الهام گرفتن از قانون طبعیت و بقای جمعیت بهتر در رسیدن به پاسخ صحیح مسئله مناسب و کارآمد است. براساس مدلی که در این پروژه مطرح می شود، با توجه به داده های وضعیت های قبلی و وضعیت فعلی ماشین های مجازی و همچنین استفاده از یک ساختار درختی برای نشان دادن نمونه های جمعیت در الگوریتم ژنتیک، سعی شده یک مدل منطقی تر و پویاتر برای حل مسئله زمان بندی در رایانش ابری مطرح شود. در این الگوریتم باتوجه به استراتژی های مناسب در مورد مسئله برای عملگرهای گزینش، تقاطع و ترکیب سعی شده تا یک مدل بهینه با توجه ذات مسئله، برای کمینه سازی زمان اجرا و زمان انتظار وظایف به طور همزمان برای مسئله زمان بندی مطرح شود. به منظور ارزیابی و میزان سنجش دقت روش آزمایشاتی برای کارایی الگوریتم ژنتیک و میزان متوسط بار سیستم ها انجام گرفته است که نتایج آزمایشات و نتایج شبیه سازی با نرم افزار MATLAB نشان می دهد که روش پیشنهادی کارایی و بهره وری مناسبی دارد.
توازن بار در محاسبات ابری
یکی از چالش های اساسی محاسبات ابری یا رایانش ابری توازن بار (Load Balancing) است، به این معنی که حجم کار در سرتاسر گره های متعدد به صورت پویا و مساوی توزیع شود. در گذشته از روش های کلاسیک مانند الگوریتم های Fifo-Lifo-Sjs استفاده شده اما این روش ها بهینه نبوده است، در این پروژه با استفاده از الگوریتم ژنتیک این چالش را برطرف کردیم و به این نتیجه رسیدیم که روش ژنتیک از روش های کلاسیک کارایی بهتری داشته و نتایج بهتری را نشان می دهد. مجموعه داده مورد استفاده در این پیاده سازی، شامل اطلاعاتی در مورد وظایفی است که قرار است بر روی یک محیط ابری اجرا شود. این اطلاعات شامل شماره وظیفه، طول وظیفه (مدت زمانی که وظیفه باید پردازش شود)، حداقل زمانی که وظیفه می تواند در آن انجام شود و همچنین حداکثر زمانی که وظیفه می تواند در آن اجرا شود.
بیان مسئله براساس الگوریتم ژنتیک
شکل نحوه عملکرد الگوریتم GA
ایجاد جمعیت اولیه
الگوریتم ژنتیک (GA) کار خود را با تولید جمعیت اولیه ای از کروموزوم ها آغاز می کند و سپس در یک حلقه به طور مکرر تعدادی از کروموزوم های برتر نسل فعلی را انتخاب کرده و سپس نسل جدیدی را از این کروموزوم ها تولید می کند، روشی که در این پروژه برای ایجاد جمعیت اولیه در نظر گرفتیم Random Search می باشد، در این روش بر خلاف جستجوی تصادفی کورکورانه، یک جستجوی هدفمند می باشد که هربار جمعیت برتر را می یابد و سپس برای جمعیت بدتر عملگر جهش و تقاطع را اعمال می کند تا جمعیت برتر پیدا شود و این کا را تا زمانی انجام می دهد که حلقه به اتمام برسد. همچنین در این پژوهش حلقه در 220 دور انجام می پذیرد. در ایجاد جمعیت اولیه درخت هایی که به جمعیت اضافه می شوند، باید کنترل عمق درخت ها را در نظر گرفت. یعنی در تولید و یا گسترش درخت ها بایستی دقت کنیم که عمق درخت ها بصورت غیر متعارف افزایش پیدا نکند. لذا در تولید جمعیت اولیه دو استراتژی مختلف وجود دارد:
روش اول این است که تمام درخت های اولیه ایجاد شده یک عمق مشخص داشته و به صورت پر باشند، روش تولید این درخت ها به این شکل است که به صورت تصادفی و سطح به سطح از توابع موجود به صورت تصادفی انتخاب و به جای گره های درخت قرار می دهند. این روند آنقدر تکرار می شود تا به بیشترین عمق مورد نظر برسیم، در این حالت برای سطح آخر از مقادیر مجموعه پایانی ها به جای گره های درخت قرار می دهیم تا یک درخت تجزیه کامل تشکیل شود. البته می توانیم درخت های پر با عمق های متفاوت به عنوان جمعیت اولیه تولید کنیم. که معمولاً روش دوم بهتر است، همانطور که اشاره شد در روش دوم به صورت سطح به سطح درخت برای جمعیت اولیه به سمت پایین می آید که این روش بهتر است. در مسئله زمانبدی منابع با الگوریتم ژنتیک ، ابتدا جمعیت اولیه را تولید می کنیم که تولید جمعیت اولیه به شیوه تصادفی با توزیع یکنواخت ایجاد می شود. در زیر نمونه ای از یک جمعیت آورده شده است:
شکل یک نمونه جمعیت
نحوه ایجاد کروموزوم به این صورت می باشد که در شکل بالا هر نمونه ای از جمعیت به شکل یک درخت ترسیم می شود در این مورد جمعیت نمونه شامل 5 ماشین فیزیکی است که بر روی هر کدام از آنها تعدای ماشین مجازی قراد می گیرد. هدف پیدا کردن بهترین جمعیتی می باشد که با استفاده از آن تعادل بار یا توازن بار ماشین های مجازی همیشه برقرار باشد و همچنین هر کدام از ماشین های مجازی در زمان اجرا بیشترین بهره وری از پردازنده را داشته باشند. نحوه کد گذاری شده جمعیت به صورت زیر است:
1 2 3 4 | Individual.PM = [1 2 3 4 5]; Individual.VMs = [1 2 3 4 5 6 7 8 9 10 11 12 13]; Individual.Connections = [3 2 2 3 3]; Individual.Cost = @compute from fitness function |
تولید مثل
در الگوریتم ژنتیک پایه ساختار نمایی تولید مثل بر اساس ژن، گسسته و پیوسته می باشد، در این پژوهش تولید مثل به صورت درختی ایجاد می شود ، هر جمعیت به صورت یک درخت می باشد، برای ایجاد تولید مثل به این صورت عمل می کنیم که ما دو درخت را در نظر می گیریم و نودهای آن را را جا به جا می کنیم که یک تولید مثل ایجاد می شود.در این پژوهش نرخ تولید مثل 8 درصد می باشد و نرخ جهش 2 درصد است.
عملگر تقاطع
در عمگر تقاطع با ترکیب کردن دو نمونه از جمعیت یک نمونه جدید تولید می شود. در این روش چون نمایش جمعیت به صورت درختی است، در این پروژه نرخ ترکیب برابر 8% بوده است. بنابراین این عملگر بر روی دو نمونه درخت T1 و درخت T2 به صورت زیر اجرا خواهد شد:
نمایش گرافیکی عملگر تقاطع
جهش
انجام جهش نیز مانند باز ترکیبی ساده است. روند کار به این صورت است که هر تابع یا پایانی در درخت تجزیه را می توانیم با هر تابع یا پایانی دیگری جایگزین کنیم، حتی ممکن است که به این شکل عمل کنیم که به جای یک زیر درخت یا پایانی، یک زیر درخت دیگر (که به روشی که در تولید جمعیت اولیه گفته شد، ایجاد شده است) را جایگزین می کنیم. در این حالت ممکن است که بخواهیم یک زیر درخت را با یک زیر درخت دیگر جایگزین کنیم، برای انجام کار باید تمام زیر درخت مربوطه را از درخت حذف کنیم و به جای آن زیر درخت یا پایانی جدید را قرار دهیم. اما اگر می خواهیم یک پایانی را با یک زیر درخت جایگزین کنیم، روند کار به این صورت است که به جای گره پایانی زیر درخت مورد نظر را قرار می دهیم. در این پروژه نرخ جمعیتی که در جهش شرکت می کنند 2 درصد در نظر گرفته شده است.
تصاویری از خروجی
هیچ نظری ثبت نشده است