بخشی از مقاله
مقايسه ي عملکرد الگوريتم هاي رقابت استعماري و تکاملي تفاضلي در زمانبندي منابع محاسبات ابري
چکيده
محاسبات ابري مدلي است که تلاش مي کندمنابع محاسباتي قابل پيکربندي مانندشبکه ها،سرويس دهنده ها، منابع ذخيره سازي و سرويس ها را در اختيار کاربران قرار دهد به طوريکه هر کاربر به راحتي در هر کجاي جهان به محض درخواست بتواند از اين منابع استفاده کند و آنها را آزاد سازد.هدف از مسئله ي زمانبندي در محاسبات ابري، انتساب بهينه ي کارها به منابع موجود در محيط ابري ميباشد، در نتيجه مسئله ي بهينه سازي زمانبندي يکي از چالش هاي اساسي در محاسبات ابري ميباشد. در اکثر کارهاي گذشته مسئله ي بهينه سازي زمانبندي در محاسبات ابري از دو جهت مديريت زمانبندي منابع و زمانبندي کارها در لايه هاي مختلف مورد بررسي قرار گرفته است ، که هدف به حداقل رساندن هزينه هاي مصرفي ميباشد. بهينه سازي زمانبندي منابع ، در اکثر کارهاي گذشته روي کمينه سازي يکي از دو گزينه ي زمان يا هزينه ي اجرا متمرکز شده است . تکنيک هاي زمانبندي زيادي مانند الگوريتم ژنتيک ، الگوريتم بهينه سازي ازدحام ذرات ، الگوريتم هاي Min-Min و Max-Min توسط محققين در اين زمينه توسعه يافته اند.آنچه بيشتر در اين تحقيق مورد توجه قرار گرفته است مسئله ي زمانبندي منابع در محاسبات ابري مبتني بر عامل ارتجاعي با برنامه هاي کاربردي کيسه ي وظايف ، با استفاده از الگوريتم هاي رقابت استعماري و تکاملي تفاضلي ميباشد. در اين تحقيق دو گزينه ي زمان و هزينه ي مصرفي با هم در نظر گرفته ميشوند. با توجه به نتايج به دست آمده ،الگوريتم رقابت استعماري مجموعه اي از رکوردهاي تخصيص منابع ابري را برميگرداند که ميتوانند برنامه هاي کاربردي کيسه ي وظايف را با رعايت بودجه ها و سررسيدها، با ميانگين نرخ موفقيت ٩٥.٦٢% در فضاهاي جستجوي امکان پذير، اجرا کنند، که نسبت به ميزان موفقيت الگوريتم تکاملي تفاضلي با ميانگين نرخ موفقيت ٩٥.٥٥% بهتراست .
کليدواژه ها:محاسبات ابري، زمانبندي منابع ، الگوريتم رقابت استعماري، الگوريتم تکاملي تفاضلي.
مقدمه
ابر نوعي سيستم توزيع شده و موازي ميباشد که شامل مجموعه اي از کامپيوترهاي به هم پيوسته ولي مجازي است که به صـورت پويـا بـه عنوان يک يا چند منبع محاسباتي واحد و يـک جـا ارائـه شـده انـد[١].
مهم ترين چالش هاي محاسبات ابـري عبارتنـد از: مقيـاس و کشـش ، پايش و اندازه گيري، امنيت وزمان بندي[٢].زمانبندي مسئله اي بحراني و اساسي در محاسبات ابري ميباشد، چون يـک فـراهم کننـده ي ابـر ملزم به سرويس دهي به کاربران زيادي در سيسـتم محاسـبات ابـري ميباشد. زمانبندي معمولا براي موازنه ي بارگذاري مؤثر يک سيسـتم يا رسيدن به يک هدف با کيفيت خدمات انجام ميشود.[٣]. 1 در اين مقاله بهينه سازي زمانبندي منابع در محاسبات ابري مبتني بـر عامل و دسترسي به منابع مورد نظر با پرداخـت کمتـرين هزينـه ، بـه صورت هم زمان و با استفاده از سيستم مبتني بر عامـل مـورد بررسـي قرار گرفته است . شکل ١ معماري محاسبات ابري مبتني بـر عـاملبراي اجـــراي برنامـــه هـــاي کـــاربردي کيســـه ي وظـــايف را نشـــان ميدهد. در سيستم بررسي شده در اين مقاله که مبتني بر چند عامـل ميباشد، عامل واسط نقش اساسي در زمانبندي منابع محاسبات ابري با استفاده از برنامه هاي کاربردي کيسه ي وظايف ، ايفا ميکند. اين کار از طريق عامل مصرف کننده ميباشد که درخواسـت مـورد نظـر را بـا توجه به هزينه و زمان مشخص شده از سـوي مصـرف کننـده دريافـت کرده و در اختيار عامل واسط قرار ميدهد، عامل واسط بـا توجـه به محدوديت هاي مشخص شده ، مجموعه ي زيربهينـه ي منـابع ابـري را براي اجراي برنامه کاربردي کيسه ي وظايف ارزيابي ميکنـد و عمـل تخصيص و ترکيب منابع ابري را از طريق چندين عامل فراهم کننده ي سرويس انجام ميدهد. عامل هاي واسـط وظيفـه ي زمانبنـدي منـابع تخصيص يافته را بر عهده دارند و اين کار را با استفاده ازالگوريتم هـاي مختلف و با در نظر گـرفتن دو محـدوديت اصـلي بودجـه و سررسـيد انجام ميدهند.در اين مقاله از الگـوريتم تکـاملي تفاضـلي١ بـه علـت مزاياي آن از جمله ؛ کارآيي آن در تعيين مسـير بهينـه ي عامـل هـاي خودکار، کارآيي آن در طراحي عامل هـاي هوشـمند و شـباهت آن بـا الگوريتم ژنتيک ٢از لحاظ مبتني بر جمعيت بودن و بالا بـودن سـرعت اجرا[٤]، استفاده شده است . همچنـين روشـرقابت اسـتعماري٣پـس از روش ژنتيک يکي از اولين راه کارهابراي فراهم سازي و ارائـه يـک راه حل به صورت خودکاراست که ميتواند مجموعه هـاي منـابع را بـراي اجراي برنامه هاي کاربردي کيسه ي وظـايف بـا محـدوديت بودجـه و سررسيد متشکل از منابع اقتصاديتر (ولي کندتر) در حضور موعدهاي آزاد (سست )و منابع قويتر (ولي گران تر) در حضور بودجه هاي بـزرگ ارزيابي کند.
کارهاي مرتبط
در [٥] يک الگوريتم زمانبندي مؤثر به نام الگوريتم زمانبنـدي خطـي براي زمانبندي کارها و منابع طراحي شده است که کارهـا و منـابع را زمانبندي ميکنـد. ايـن الگـوريتم اساسـا روي از بـين بـردن شـرايط قحطي ٤ و بن بست ٥تمرکز ميکند[٥]. هم چنين لي ينگ ٦ و همکـارش در سال ٢٠١٢ مدلي تصادفي از يک خوشه ي محاسبات ابري در نظـر ميگيرند که کارها را مطابق يک فرآينـد تصـادفي و درخواسـت هـاي ماشين هاي مجازي، که از لحاظ منابع مانند پردازنده ، حافظه و فضـاي ذخيره سازي مشخص شده است در نظر ميگيرد[٦]. در [٧] نشان داده شده است که استفاده از الگوريتم کلوني مورچه ٧ در مـدل پايـه بـراي برآورد توزيع گره و تعادل بار٨ کارآيي خوبي دارد[٧]. زمانبندي کـار بـا استفاده از مدل برگر٩ يکـي از الگـوريتم هـا بـراي زمانبنـدي کـارهـا ميباشد که ناتمامي وظيفه هنگام حاصل نشدن تطابق کارهـا-منـابع براي آن عيب محسوب ميشـود[٨]. ترکيـب مـدل برگـر و شـبکه ي عصبي ١٠ بـر نقـص مـدل برگـر غلبـه خواهـد کـرد. نويسـندگان [٩] الگوريتم زمانبندي جديدي پيشنهاد کرده اند که نسخه اي بهبود يافتـه از الگــوريتم ژنتيــک مــيباشــد. در الگــوريتم زمانبنــدي پيشــنهادي، روش هـاي زمانبنــدي Min-Min و Max-Minدر الگــوريتم ژنتيــک استاندارد ادغام شده اند. الگوريتم طراحيشده قادر به زمانبندي چندين کار روي چندين ماشين در رفتاري کارا ميباشد به طوريکه کارها در کم ترين زمان ممکن کامل مـيشـوند[٩]. در [١٠] نيـز روشـي بـراي بهبود الگوريتم بهينه سازي ازدحام ذرات در استراتژي زمانبندي منـابع محاسبات ابري را پيشنهاد کرده انـد کـه سـرعت همگرايـي الگـوريتم بهينه سازي ازدحام ذرات را افـزايش مـيدهـد. نتـايج تجربـي نشـان ميدهد که الگوريتم بهينه سـازي ازدحـام ذرات بهبـود يافتـه متوسـط زمان عمليات کارها را کاهش داده ، منـابع شايسـته را بـراي کارهـاي کاربران به صورت کارآمد در محيط فراهم کـرده و نسـبت اسـتفاده ي منابع را افزايش ميدهد[١٠].
بــا توجــه بــه ايــن کــه صــالحي و بويــا[١١] و گــروه تحقيقــاتي سوگاوانام ١١[١٢] الگوريتم هاي بهينه سازي را براي اجراي برنامـه هـاي کاربردي کيسه ي وظايف محدودشده توسط بودجه و سررسيدها فراهم ساخته اند، الگوريتم هاي ارائه داده شده يشان به صورت انحصار متقابل ميباشد، يعني مصرف کننده ها تصميم ميگيرند که مصرف بودجه و يا زمان اجرا (سررسيد) را بهبود بخشند.
در اين مقاله بر خلاف اکثر کارهاي صـورت گرفتـه ، بيشـينه ي تعـداد منابع ابري در نظر گرفته شده است . از ديگر ويژگـيهـاي ايـن کـار، ساده سازي انتخاب و ترکيب منابع براي اجراي برنامه هـاي کـاربردي کيسه وظايف بر حسب عملکرد، در نظر گرفتن کارآيي محاسباتي ثابتي از منبع ابري پشتيبانيشده ، سرعت بالا و موازي بودن ميباشد.
بررسي الگوريتم هاي مورد اسـتفاده در زمانبنـدي منـابع ابري سيستم موجود
در اين مقاله نيز با استفاده از الگوريتم هاي رقابت استعماري و تکاملي تفاضلي به عنوان روش هاي نوين بهينه سازي و با در نظـر گـرفتن دو محدوديت هزينه و زمان به بهينه سازي زمانبندي منابع در محاسـبات ابري مبتني بر عامل پرداخته شده است .
مراحل الگوريتم رقابت استعماري به صورت زير ميباشد:
• شکل دهي امپراطوري اوليـه :در ابتـدا يـک آرايـه از متغيرهـاي مسئله را که بايد بهينه شوند، ايجاد ميکنيم . اين آرايه را کشـور مـينـاميم . متغيـرهـاي مجهـول تـابع هزينـه در طـي فرآينـد بهينه سازي از نگاه اين الگوريتم داراي ويژگيهايي هسـتند کـه يک کشور را به نقطه ي مينيمم تابع هزينه رهنمون ميسازند. در حقيقت در حل مسئله ي بهينه سازي زمانبندي منابع در محاسبات ابري به دنبال کشوري با بهتـرين ويژگـي از لحـاظ پارامترهـاي 3 زمان و هزينه هستيم که داراي کمترين تابع هزينه باشـد. بـراي شروع تعدادي از اين کشورها بايد ايجاد شوند، بنابراين مـاتريس کل کشورها به صورت تصادفي اوليه تشکيل ميشوند.
• مدل سازي انقلاب :از آنجايي که سياسـت انقـلاب در الگـوريتم رقابت استعماري به جمعيـت اوليـه وابسـته مـيباشـد،يعني اگـر جمعيت اوليه توليد شده بهينه باشد سريع به جـواب مـيرسـد و برعکس اگر بهينه نباشد ممکن است به جواب نرسـد، از طرفـي در حالت گسسته ، وابسته بودن به جمعيت اوليه بيش تر ميشـود.
براي اين که فضاي جواب هاي بدست آمده کمتر به جمعيت اوليه وابسته باشد، الگوريتم رقابت استعماري مدل انقلاب را پيشـنهاد ميدهد. در اين حالت تعداد جواب هاي توليد شده افزايش مييابد و در نتيجه از شدت وابستگي جواب هاي فضاي مسـئله کاسـته ميشود. در اين مقاله اين کار با يک جهش ٠.١ در تـابع انقـلاب انجام ميشود.
• مدل سازي سياست جذب :از آن جايي که داده هاي مـا در حرکـت مستعمره به سمت امپرياليسم در فضاي گسسته ميباشند، عمـل جذب نيز بايد در فضاي گسسته اتفـاق بيافتـد. در واقـع در نظـر داريم که حرکت مـا نظيـر حرکـت پيوسـته در فضـاي جسـتجو گسسته باشد، براي اين کار ما يک نقطـه از فضـاي جسـتجو را انتخاب ميکنيم از آن جايي که اين نقطـه ي انتخـابي در فضـاي گسسته قرار ندارد، يـک نقطـه ي ديگـر (نزديکتـرين نقطـه بـه با برنامه هاي کاربردي کيسه ي وظايف نقطه ي انتخاب شده را) پيدا مـيکنـيم . بـراي انجـام ايـن کـار نقطه ي انتخابي اول را روند مـيکنـيم تـا بتـوانيم بـا توجـه بـه مختصات آن نزديک ترين نقطه به نقطه ي انتخابي را پيدا کنـيم .
از سوي ديگر ساير نقاط اطراف نقطـه ي جديـد را نيـز جسـتجو ميکنيم تا بهترين موقعيت را بين نقاط اطراف پيدا کنيم .
• جابجــايي موقعيــت مســتعمره و امپرياليســت :در حــين حرکــت مستعمرات به سمت کشور اسـتعمارگر، ممکـن اسـت بعضـي از مستعمرات به موقعيتي بهتر از امپرياليست برسند (بـه نقـاطي در تابع هزينه برسند که هزينه ي کمتري را نسـبت بـه مقـدار تـابع هزينه در موقعيت امپرياليست ، توليد مـيکننـد.) در ايـن حالـت ، کشور استعمارگر و کشور مسـتعمره ، جـاي خـود را بـا همـديگر عوض کرده و الگوريتم با کشـور اسـتعمارگر در موقعيـت جديـد ادامه يافته و اين بار اين کشور امپرياليست جديد است که شروع به اعمال سياست همگون سازي بر مستعمرات خود ميکند.
• قدرت و هزينه ي کل يـک امپراطوري:قـدرت يـک امپراطـوري برابر است با قدرت کشور اسـتعمارگر، بـه اضـافه ي درصـدي از قدرت کل مستعمرات آن ، مقدار اين هزينه ي کل معمـولا بـين صفر و يکميباشد و نزديک به صفر در نظر گرفته ميشود.
• حذف امپراطوري ضعيف :هر امپراطوري که نتواند بر قدرت خـود بيافزايــد و قــدرت رقابــت خــود را از دســت بدهــد، در جريــان رقابت هاي امپرياليسـتي،حـذف خواهـد شـد. بـه مـرور زمـان و بهتدريج امپراطوريهاي ضـعيف ، مسـتعمرات خـود را از دسـت ميدهند و امپراطوريهاي قـويتر، ايـن مسـتعمرات را تصـاحب کرده و بر قدرت خويش ميافزايند. الگوريتم مورد نظر تا برآورده شدن يک شرط همگرايي، يعني رسيدن بـه حـداقل يـک منبـع بهينه و موفقيت آميز که با دو قيد بودجه و سررسيد محدود شـده است ، و يا اتمام تعداد کل تکرارها، ادامه مييابد. پـس از مـدتي، همه ي امپراطوريها سقوط کرده و تنها يـک امپراطـوري بـاقي ميماند که ساير کشورها تحت کنترل اين امپراطوري واحد، قرار ميگيرند. در اين تحقيق نيز امپراطوري باقيمانده منبعـي اسـت که داراي کمترين ميـزان هزينـه ي دسترسـي و کمتـرين زمـان دسترسي، و در کل داراي بيش ترين ميزان موفقيت ميباشد.
مراحل الگوريتم تکاملي تفاضلينيز به صورت زير ميباشد:
• توليد جمعيت اوليه : در ابتدا برداري از متغيرهـاي مسـئله را کـه بايد بهينه شوند، ايجاد ميکنيم . اين بردار را کروموزوم ميناميم .
در حقيقت در حـل مسـئله ي بهينـه سـازي زمانبنـدي منـابع در محاسبات ابري به دنبال کروموزومي با بهترين ويژگي از لحـاظ پارامترهاي زمان و هزينه هستيم که داراي کمترين تـابع هزينـه باشد. براي شروع تعدادي از اين کروموزوم ها بايد ايجاد شـوند، بنابراين کروموزوم ها به صورت تصادفي اوليه تشکيل ميشوند و سپس به صورت صعودي يا نزولي مرتب ميشوند.
• عمل جهش : الگوريتم تکاملي ديفرانسيلي نام خـود را از عملگـر جهش تفاضلي خويش گرفته است . عملگر جهـش نقـش ايجـاد تنوع در جمعيت را بر عهده دارد، اين عملگر در الگوريتم تکاملي ديفرانسيلي بر خلاف ديگر الگوريتم هاي تکـاملي، نقـش نسـبتا مهمتري نسبت به ساير عملگرها ايفـا مـيکنـد. بـه طـوريکـه الگوريتم تکاملي تفاضلي نسل قبل را جهش داده و جمعيتي بـه تعداد NP عضو توليد ميکند. در اين مرحله ، سه بردار به صورت تصادفي و دو به دو متفاوت از هم ، انتخـاب مـيشـوند. عملگـر جهش تفاضلي نسبتي از تفاضـل دو بـردار جـواب (بـردار اول و دوم ) را به يک بردار پايه (بردار سـوم ) اضـافه مـيکنـد. فـاکتور جهش در الگوريتم عـددي بزرگتـر از صـفر و نزديـک بـه يـک ميباشد که نسبت سهم بردار تفاضـلي در توليـد نسـل جديـد را کنترل ميکند.
• عمل تقاطع يا جابجايي: عمل جابجايي به منظور ايجاد جمعيـت فرزند از جمعيت آزمايشي به کار مـيرود. عمليـات جابجـايي در واقع تنوع جمعيت را که پس از عمليات جهـش بـه وجـود آمـده است کنترل ميکند. در اين مرحله ، هر يک از مؤلفه هـاي بـردار جهش يافته با احتمال CR به بردار کانديدا منتقل ميشـوند و در غير اين صورت مؤلفه ي معادل در بردار اصلي جايگزين ميشود.
• عمل انتخاب : فرآيند انتخاب در الگوريتم تکاملي تفاضلي با ديگر الگوريتم هاي ابتکـاري متفـاوت اسـت . در سـاير الگـوريتم هـاي تکاملي افراد بازمانده براي نسل بعد به صورت احتمالي انتخـاب ميشوند، در صورتي که در الگـوريتم تکـاملي ديفرانسـيلي ايـن انتخاب به صورت انتخاب قطعي بين بردار والد و بردار فرزند بـا در نظر گرفتن برازش آن دو صورت ميگيرد. مزيت اصـلي ايـن استراتژي اين است که با ممانعت از انتقال بردار والد و فرزند بـه صورت هم زمان به نسل بعد از کم شدن تنوع جمعيت جلوگيري مينمايد. در اين مرحله ، به منظـور انتخـاب بازمانـدگان از روش حريصانه استفاده ميشود و هر بردار با بردار کانديـداي مربوطـه مقايسه ميشود، هر کدام که شايستگي بيشتري داشته باشد بـه نسل بعدي منتقل ميشود. به عبارتي ديگر، در اين مرحله ، بردار توليد شده ي مرحله ي قبل از نظر مقدار تابع هدف با بردار اصلي مقايسه شده و اگر مقدار تابع هدف بهتري نسبت به بردار اصـلي فراهم کند، بردار انتخاب ميشود.
• توقف : فرآيند جهش و انتخاب براي تمامي بردارها انجام شـده و يک جمعيت جديد ساخته ميشود تا زماني که يک راه حل بهينه به دست آيد.اگر حداکثر تعداد نسل هاي kاجرا شده و يا بهبودي در تابع هدف در يک نسل ، که از قبل تعيين شده ، حاصـل شـود اين فرآيند قطع ميشود. فرآيند جستجو تا زماني که معيار توقف الگوريتم برآورده شود، ادامه مييابد.
در شـکل ٢ مراحـل الگـوريتم رقابـت اسـتعماريو در شـکل ٣مراحـل الگـوريتم تکـاملي تفاضـلي جهـت بهينـه سـازي زمانبنـدي منـابع در محاسبات ابري مبتني بر عامل را به صورت شبه کد نشـان داده شـده است .
شبيه سازي و ارزيابي
بســتر آزمــايش در محـيط نـرم افــزار MATLAB پيـاده سـازي شــد،
آزمايش ها درکامپيوتري با مشخصات زير انجام گرفتند:
GB RAM ٤, GHz١٧٣, inside Intel core i٧ با سيستم ٦٤ بيتي Windows 7پارامترهــاي کنترلــي الگــوريتم رقابــت اســتعماري در جــدول ١ و پارامترهاي کنترلي الگوريتم تکاملي تفاضلي در جدول ٢ آمده اسـت .
داده هاي ورودي محيط ابر جدول ٣ نيـز متشـکل از مـاکزيمم تعـداد نمونه هاي مجاز و انواع غيراجرايي منـابع ابـري توصـيف شـده توسـط ظرفيت هاي محاسباتي، نرخ هاي هزينه ي ساعتي و نرخ هاي کارآيي هر کدام ميباشد.همان طور که در جـدول ٤ نشـان داده شـده اسـت ، زوج هاي محـدوديت (قيـد) (ناشـي از ضـرب ضـربدري بودجـه هـا و سررسيدها) برايفراهم سازي شرايط تکاملي تفاضليانتخاب شدند.
