دانلود رایگان ترجمه مقاله الگوریتم Memetic مبتنی بر جستجو محلی متغیر برای مشکل متعادل بار – اسپرینگر 2016

جست و جوی متغیر محلی بر اساس الگوریتم ممتیک برای مسئله توازن بار در رایانش ابری

A Variable Local Search Based Memetic Algorithm for the Load Balancing Problem in Cloud Computing

چکیده :
متعادل کننده بار (LB) یک مسئله مهم و چالش برانگیز بهینه سازی در محاسبات ابری است . متعادل کننده بار شامل اختصاص مجموعه ای از خدمات به مجموعه ای از ماشین آلات برای بهینه سازی کاربردهای دستگاه است . این مطالعه یک الگوریتم ممتیک (MA) برای مسئله متعادل کننده بار ارائه می دهد . الگوریتم ممتیک یک روش ترکیبی است که ترکیبی از قدرت الگوریتم های تکاملی بر اساس تعداد با جستجوی محلی می باشد. با این حال اثر الگوریتم ممتیک به طور عمده به روش جستجوی محلی انتخاب شده برای الگوریتم ممتیک بستگی دارد. به این دلیل که روش انجام جستجوی محلی متفاوت برای موارد مختلف و تحت مراحل مختلف جستجو وجود دارد . علاوه بر این، با استناد به جستجوی محلی در هر تولید می توان ظرفیت را جستجو کرد . برای رسیدگی به این مسائل، این مطالعه پیشنهاد یک الگوریتم محلی ممتیک با جستجو بر اساس متغیر در زمینه مسئله متعادل کننده بار ارائه می دهد . متحرک پیشنهادی با استفاده از چند مکانیزم جستجوی محلی عمل می کند. هریک هدایت یک منطقه مختلف در فضای جستجو را با استفاده از مکانیزم های مختلف جستجو انجام می دهند که می تواند با یک مسیر جستجوی متفاوت با الگوریتم ممتیک محلی متمایز شود. این نه تنها به جستجو برای جلوگیری از گرفتار شدن در دام یک نقطه بهینه محلی کمک می کند، همچنین می تواند به طور موثر با ویژگی های مختلف جستجو چشم انداز و تغییرات پویا مسئله برخورد کند. علاوه بر این، یک شاخص تنوع برای کنترل فرآیندهای جستجوی محلی برای تشویق تنوع راه حل به تصویب رسیده است. روش الگوریتم ممتیک این است که در موارد مسئله دستگاه تغییر پیشنهادی گوگل برای ROADEF/ EURO 2012 مورد بررسی قرار گرفته است. در مقایسه با حالت روش پیشرفته ، روش ما به بهترین عملکرد در بسیاری از موارد دست می یابد، اثربخشی متغیر محلی الگوریتم ممتیک بر اساس جستجو برای مسئله متعادل کردن بار نشان داده شده است .

1 . مقدمه
رایانش ابری یک تکنولوژی در حال رشد سریع فراهم می کند که خدمات تقاضای محاسبات بر روی اینترنت را فراهم می کند [3،6]. این دسترسی به شبکه منابع محاسباتی قابل تنظیم از جمله ذخیره سازی، پردازش، پهنای باند و حافظه است که به اشتراک گذاشته شده . ارائه دهنده گان ابر مانند گوگل و آمازون، مدیریت یک مرکز داده است که منابع محاسباتی هستند و با کاربران نهایی به اشتراک گذاشته می شود. با رشد سریع تقاضا در خدمات ابر، تخصیص منابع بهینه یکی از اهداف مهم در محاسبات ابری می باشد [6] .
توازن بار (LB) یکی از منابع ابر است و وظیفه تخصیص بهترین آرایش خدمات به مجموعه ای از ماشین آلات را دارد ، به طوری که استفاده از این دستگاه می تواند موجب بهبود عملکرد گردد . در این مقاله، ما مسئله متعادل کننده بار توسط گوگل برای ROADEF/ EURO 2012 را در نظر گرفته ایم [1]. این کار به عنوان ماشین تغییر مسئله (MRP) معرفی شده است . هدف از MRP به منظور بهبود استفاده از منابع توسط تخصیص مجدد مجموعه ای از فرآیندها به مجموعه ای از ماشین آلات است، در حالی که تمام محدودیت های مسئله باید راضی کننده باشد . طیف وسیعی از روش ها برای حل MRP ارائه شده است . این خدمات عبارتند از جستجو متغیر محله [8]، برنامه نویسی مبتنی بر محدودیت جستجوی محلی بزرگ [15]، جستجو های بزرگ محله [4]، چند شروع تکرار جستجوی محلی [14]، شبیه سازی سفت و سخت [20] و محدوده تکرار جستجوی محلی [13] .
در این مطالعه، ما یک روش الگوریتم ممتیک (MA) مبتنی بر این مسئله تعادل بار ارائه داده ایم . الگوریتم ممتیک روش جستجو بهینه سازی تصادفی که ترکیبی از الگوریتم بر اساس تعداد با جستجوی محلی است . منطق الگوریتم ممتیک قدرت شناسایی الگوریتم های مبتنی بر تعداد با قابلیت بهره برداری از جستجوی محلی است [16]. الگوریتم ممتیک در حل مسائل سخت بهینه سازی مختلفی بسیار موفق نشان داده است [17] . با این حال موفقیت الگوریتم ممتیک خودکار نمی باشد [21،22،25]. دو جنبه مهم که باید در هنگام طراحی الگوریتم ممتیک برای یک مسئله خاص در نظر گرفته شود وجود دارد [18]. در مرحله اول، انتخاب جستجوی محلی مهم است . عملکرد الگوریتم ممتیک به شدت به انتخاب الگوریتم جستجوی محلی بستگی دارد. برای یک جستجوی محلی با ویژگی های متنوع ، موارد مختلف و مسئلهات مختلف بسیار دشوار است. حتی برای همان نمونه، مشخصه از فضای جستجو تحت مراحل مختلف ممکن است به طور چشمگیری متفاوت باشد[24]. که باعث می شود انتخاب روش جستجوی محلی دشوار و بحرانی گردد. در مرحله دوم، الگوریتم ممتیک اغلب با چالش چگونگی حفظ تنوع از یک فرایند جستجو مواجه است [23] . استفاده بیش از حد از جستجوی محلی ممکن است بیشتر محاسبات و اطلاعات را به خطر بیندازد . برای پرداختن به این دو موضوع، ما یک جستجوی محلی مبتنی بر الگوریتم ممتیک متغیر ارائه داده ایم . این ترکیب الگوریتم ژنتیک (الگوریتم پیشرفته) با الگوریتم های جستجوی محلی متعدد است که در آن هر کس می تواند یک منطقه مختلف در فضای حرکت جستجو کند . مکانیزم های مختلف جستجو می تواند با یک مسیر در جستجو های مختلف با الگوریتم ممتیک محلی متمایز شود . علاوه بر این یک شاخص تنوع به تصویب رسیده برای کنترل جستجوی محلی برای جلوگیری از تنوع در تعداد راه حل های ایجاد شده است. با روش ارائه شده، بدون نیاز به بررسی ماهیت یک مسئله تعادل بار و انتخاب یک جستجوی محلی مناسب برای این مسئله وجود دارد. نیاز به تنظیم جستجوی محلی نیز در روش الگوریتم ممتیک ضروری بیان شده است.
الگوریتم پیشنهادی در موارد مسئله در مقیاس کوچک و بزرگ دستگاه و تغییر ROADEF/ EURO 2012 مورد بررسی قرار گرفته است. برای مقایسه، حالت الگوریتم پیشرفته برای این چالش نیز در بخش 2 گنجانده شده است . متغیر محلی بر اساس جستجو الگوریتم ممتیک در بخش ارائه 3 شده است . بخش 4 تنظیمات آزمایش را نشان می دهد در حالی که نتایج به دست آمده در بخش 5 ذکر شده است . بخش 6 نتیجه این مطالعه است.

Abstract.

Load balancing (LB) is an important and challenging optimisation problem in cloud computing. LB involves assigning a set of services into a set of machines for which the goal is to optimise machine usages. This study presents a memetic algorithm (MA) for the LB problem. MA is a hybrid method that combines the strength of population based evolutionary algorithms with local search. However the effectiveness of MA mainly depends on the local search method chosen for MA. This is because local search methods perform differently for different instances and under different stages of search. In addition, invoking local search at every generation can be computationally expensive and compromise the exploration capacity of search. To address these issues, this study proposes a variable local search based MA in the context of LB problem. The proposed MA uses multiple local search mechanisms. Each one navigates a different area in search space using a different search mechanism which can leads to a different search path with distinct local optima. This will not only help the search to avoid being trap in a local optima point, but can also effectively deal with various landscape search characteristics and dynamic changes of the problem. In addition, a diversity indicator is adopted to control the local search processes to encourage solution diversity. Our MA method is evaluated on instances of the Google machine reassignment problem proposed for the ROADEF/EURO 2012 challenge. Compared with the state of the art methods, our method achieved the best performance on most of instances, showing the effectiveness of variable local search based MA for the Load Balancing problem.

1 Introduction

Cloud computing is a fast growing technology that provides on-demand computing services over the Internet [3,6]. It offers network access to a various shared pool of configurable computing resources including storage, processing, bandwidth and memory. A cloud provider, such as Google and Amazon, manages a data centre of which the computing resources are to be shared by end users. With the rapid growth of the demand in cloud services, optimal resources allocation becomes one the most important targets in cloud computing [6]. Load balancing (LB) is one of the cloud resource allocation tasks seeking for the best arrangement of services into a set of machines so the usage of these machines can be improved. In this paper, we consider the LB problem introduced by Google for the ROADEF/EURO 2012 challenge [1]. The task is named as Machine Reassignment Problem (MRP). The goal of MRP is to improve the usage of resources by reassigning a set of processes into a set of machine, while all problem constraints must be satisfied. A range of methods have been proposed to solve MRP. These include variable neighbourhood search [8], constraint programming-based large neighbourhood search [15], large neighbourhood search [4], multi-start iterated local search [14], simulated annealing [20] and restricted iterated local search [13]. In this study, we propose a memetic algorithm (MA) based method for this load balancing problem. MA is a stochastic optimisation search method which combines population based algorithm with local search. The rationale of MA is to synergise the exploration power of population based algorithms with the exploitation capability of local search [16]. MA has been proven very successful in solving various difficult optimisation problems [17]. However the success of MA is not automatic [21,22,25]. There are two important aspects that have to be considered when designing MA for a particular problem [18]. Firstly, the choice of local search is important. The performance of MA heavily depends on the selected local search algorithm. It is difficult for one local search to fit with diverse features of different instances of different problems. Even for the same instance, the characteristic of search space under different stages may vary significantly [24]. That makes the choice of local search method difficult and critical. Secondly, MA often faces the challenge of how to preserve the diversity of a search process [23]. Excessive use of local search may consume more computation on exploitation compromising the effort on exploration. To address these two issues, we propose a variable local search based memetic algorithm. It combines genetic algorithm (GA) with multiple local search algorithms in which each one can navigate a different area in the search space. Different search mechanisms can lead to a different search path with distinct local optima. Furthermore a diversity indicator is adopted to control the invocation of local search to prevent lost of diversity in the population of solutions. With the proposed method, there is no need to examine the nature of a load balancing problem and to choose an appropriate local search for the problem. The need of tuning the local search is also unnecessary in the proposed MA approach. The proposed algorithm are evaluated on small and large scale instances of the machine reassignment problem from ROADED/EURO 2012 challenge. For comparison purposes, the state of the art algorithms for this challenge are included as well. In Sect. 2, this challenge is described in details. The proposed variable local search based MA is presented in Sect. 3. Section 4 shows the experiment settings while the results are listed in Sect. 5. Section 6 concludes this study.