کارهای مرتبط در محیط محاسبات ابری

آقای ژواو سیلوا و همکارانش [۳۵] الگوریتمی را ارائه دادند که در این الگوریتم ابتدا زمان میانگین لازم برای یک کار تا انتهای آن را محاسبه می کند این مقدار در آینده برای یافتن تعداد میزبان ها ,مورد استفاده قرار می گیرد سپس پیش بینی میکند که میزبان ها توانایی انجام چه تعداد کار را دارند.سپس تعداد کارهایی که موجود است از تعداد کارهایی که میزبان ها می توانند انجام دهند کسر شده و با ضرب شدن در فاکتور ساخت تصحیح می شود.اگر کارها بصورت منظم وارد شوند این الگوریتم پاسخ خوبی نمی دهد میانگین زمان پاسخگویی بالا می رود و مقدار متوسط پاسخگویی نزدیک به کارهای پایانی است و در اواخر کارها میزبان های جدید باید اختصاص داده شود. برای حل این مشکل از انتخاب تصادفی کارها استفاده می کنند ولی باز هم مشکل وجود دارد آن اینکه اگر کارهای ابتدایی بزرگ باشد تعداد زیادی از میزبان ها در ابتدا مورد استفاده قرار می گیرد برای همین از فاکتور ساخت استفاده می کنند.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

آقای لی فنگ آی و همکارانش [۳۶] الگوریتمی اکتشافی ارائه دادند که برای ترکیب وب سرویس ها در شبکه محاسبات ابری استفاده می شود. ورودی مجموعه ای از ترکیب وب سرویس ها است. محدودیت هایی را که در ورودی ها اعمال کردند عبارتند از : ۱-تقدم و تاخر مورد نیاز در اجرای وب سرویس ها رعایت شود ۲- محدودیت های منابع در نظر گرفته شود ۳- محدودیت در موعدها برای وب سرویس ها رعایت شود
رابطه۲-۱ به عنوان تابع شایستگی در این مقاله بیان شده است
اگر V(X)≤۱ باشد یعنی محدودیت ها نقض نشده است ولی اگر V(X)>1 باشد یعنی تعدادی از محدودیت ها نقض شده است. بدترین حالت می باشد که حداکثر هزینه کل در تمام افراد موجود در نسل فعلی است مقدار شایستگی در بازه ۱ تا بی نهایت قرار دارد. زمان به پایان رسیدن وب سرویس است و مهلت تعیین شده برای آن وب سرویس می باشد.معادلات ۱ تا ۳ تضمین می کند که تمامی راه حل های امکان پذیر در یک نسل بهتر از تمامی راه حل های غیر ممکن در نسل است.راه حل های غیر ممکن محدودیت های بیشتری را نقض میکنند. در این الگوریتم عملگر تقاطع۰٫۱۵ و عملگر جهش ۰٫۸۵ در نظر گرفته شده است یکی از مشکلات آن این است که بحثی درباره اینکه کارها بصورت همزمان وارد شوند ارائه نداده است
۳-آقای جین تیسانگ تیسای و همکارانش[۳۷] الگوریتمی ارائه دادند که هر فرد در آن به صورت =[(۲,R1),(1,R3),(3,R2),(2,R4),(1,R3),(1,R2),(3,R4),(2,R1),(3,R2)] نشان داده می شود که ۱و۲و۳ نشان دهنده کار و R هم نشان دهنده منبع می باشد و هر یک از کارها دارای چند زیر کار می باشند مثلا کار ۱ دارای ۳ زیر کار می باشد.برای عملگر جهش ابتدا بهترین فرد از نسل را انتخاب نموده سپس با بهره گرفتن از فاکتور تتا , عمل جهش به مقادیر مربوط به فرد برگزیده توسط سایر افراد نسل انجام می گیرد فاکتور تتا بدین گونه است که مجموعه ای از p عضو ساخته می شود که p شماره کارها می باشد سپس این مجموعه با بهره گرفتن از متد تاگوچی به ۲ گروه مجزا تقسیم می شوند اگر کارهای هر فرد در گروه اول قرار می گرفتند آنگاه همان زوج مرتب در فرزندان تولید می شوند وگرنه کار فرد برتر در نسل بعدی قرار می گیرد.عملگر تقاطع آنها بدین شکل است که برای هر زوج مرتب فرزند یک عدد تصادفی بین ۰ و ۱ ایجاد می شود اگر مقدار تولید شده کوچکتر از مقدار مورد نظر بود که در اینجا ۰٫۸ است از والد جهش یافته استفاده می شود وگرنه از والد دیگر انتخاب می شود.
آقای جیانهواگوو وهمکارانش [۳۸] الگوریتم ژنتیکی را برای زمانبندی منابع مطرح کردند.مرحله اول که مقدار دهی اولیه می باشد آنها از متد درخت پوشا استفاده می کنند که این درخت پوشا توسط مجموعه ای از ماشین های فیزیکی و ماشین های مجازی ساخته می شود که ماشین های مجازی نود های برگ هستند .از قوانین درخت می توان به این نکته اشاره کرد که نود ها با توجه به شرایط تعادل بار ملاقات می شوند.تابع شایستگی در این مقاله بصورت رابطه ۲-۴ محاسبه می شود
A و B ضرایب وزنی هستند و در رابطه ۲-۵ محدودیت های مجاز برای تغییر دما در سیستم تعادل بار است که می تواند از پیش تعریف شده باشد. تابع جریمه است که وقتی که فرد محدودیت ها را رعایت کند برابر ۱ وقتی رعایت نکند برابر ۰ قرار می گیرد. هدف انتخاب افرادی با میزان شایستگی بالا است.احتمال انتخاب هر کدام از افراد با رابطه ۲-۶ بدست می آید
شایستگی عنصر i در جمعیت می باشد و D اندازه جمعیت می باشد.این رابطه نشان می دهد که افرادی با شایستگی بالاتر به احتمال بیشتری انتخاب می شود.استراتژی انتخاب آن روش چرخشی می باشد بدین صورت که فردی که شایستگی بالاتر قطعه بزرگتری را در اختیار می گیرد عملگر تقاطع به صورت زیر عمل می کند ۱- دو تا از افراد بر اساس انتخاب چرخشی انتخاب می شود ۲- این دو درخت والد با هم ترکیب می شود و تمام نود های برگ دو والد در آن قرار می گیرند ۳-برای نود های برگ متفاوت ابتدا احتمال انتخاب آن ها محاسبه می شود که مطابق است بر باری که برای هر ماشین مجازی وجود دارد بعد Pگره دارای کمترین بار به عنوان برگ توزیع می شوند تا زمانی که توزیع کامل شود۴-این مراحل تا زمانی که تعداد افراد مورد نیاز ساخته شود تکرار می شود.عملگر جهش به شکل رابطه ۲-۷ بیان شده است
tتعداد تولید نسل و D اندازه جمعیت و Mتعداد ماشین های مجازی می باشد.
آقای ژوونگ نیژنگ و همکارانش [۳۹] الگوریتم ژنتیک موازی را ارائه نمودند.نمایش کروموزوم به صورت (۸ و ۵ و۲) نمایش داده می شود که IR اول به نود شماره ۲ نسبت داده می شود و IR دوم به نود شماره ۵ و IR سوم به نود شماره ۸ اختصاص داده می شود.IR ها دارای برچسب شماره و ویژگی های سیستم مورد نیاز(cpu و حافظه و هارد دیسک) می باشند . مرحله بعد برای هر نود محاسباتی اندازه منابع بیکار آن محاسبه می شود . پارامترهایی که برای مهاجرت افراد از یک بخش به بخش دیگر چک می شوند عبارتند از: ۱- توپولوژی ۲- نرخ مهاجرت ۳- طرح مهاجرت که نشان می دهد کدام افراد باید مهاجرت کنند ۴-فاصله بین مهاجرت که نشان دهنده فرکانس مهاجرت است.محدودیت هایی که در نظر گرفته شده یک کار در هر لحظه زمانبندی می شود و همه نود ها در زمان بندی ظاهر می شود بجز نود هایی که منابع بیکار نداشته باشد.تابع شایستگی بصورت رابطه ۲-۸ در نظر گرفته شده است
Kبرچسبی است که اگر برابر با ۱ باشد نشان دهنده CPU است اگر ۲ باشد نشان دهنده ظرفیت حافظه و اگر ۳ باشد نشان دهنده میزان ظرفیت هارد می باشد.مقدار بر اساس در رابطه ۲-۸ بدست می آید که اگر برابر ۱ باشد قرار دادن مناسب است که بیشترین استفاده از منابع را می توان انتظار داشت اگر کمتر از ۱ باشد این راه حل تنها بخشی از یک راه حل بهینه می باشد که نمی تواند بیشترین بهره وری از منابع را داشته باشد در هر حالت ذکر شده عددی مثبت به تعلق می گیرد و اگر این مقدار بزرگتر از ۱ بود راه حل مطلقا غیر متناسب است. بر اساس رابطه ۲-۸ با ۱۰۰۰ جمع می شود تا مقدار شایستگی آن مثبت است.
خانم شامیندر کااوور و همکارانش [۴۰] الگوریتم ژنتیکی ارائه دادند. نمایش کرموزوم به صورت شکل ۱۰ است که برای هر پردازنده سلسله ای از کارها به آن اختصاص داده می شود.

شکل ۱۰- نمایش کروموزوم ]۴۰[
از تقاطع ۲ نقطه ای در آن استفاده شده است و عملگر جهش این الگوریتم از روش جایگزینی ساده استفاده کرده است تابع شایستگی آن بدین صورت است که افرادی برای نسل بعد انتخاب می شود که طول بازه کمتر از استاندارد اعمال شده برای الگوریتم ژنتیک باشد و شرایط انتهایی برای آن تعداد مشخصی از تولید می باشد که در اینجا ۳۰ نسل تعیین شده است.
آقای چنگ هونگژاو و همکارانش [۴۱] با ارائه الگوریتم ژنتیکی برای زمانبندی کارهای مستقل در محیط محاسبات ابری به دنبال راهکاری بهینه می باشند در این الگوریستم تابعی برای جریمه نیز در نظر گرفته شده است.کروموزوم آن به شکل ۱۱ نمایش داده شده است
شکل ۱۱- نمایش کروموزوم[۴۱]
TA نشان دهنده کار و P نشان دهنده واحد پردازش است تابع شایستگی آن بصورت رابطه ۲-۹ نشان داده شده است .
نشان دهنده زمان پایان کار برای k واحد پردازش می باشد و تابع f برای جریمه در نظر گرفته شده که به شکل رابطه ۲-۱۰ است:
نشان دهنده موعد مقرر و نشان دهنده زمان واقعی پایان کار می باشد و هزینه تاخیر و هزینه ذخیره سازی برای کارها می باشد.عملگر تقاطع بصورت رابطه ۲-۱۱ انجام میگیرد:
فرض شده است که نرخ تقاطع برای افراد بد C1 و برای افراد خوب C2 می باشد.عملگر جهش نیز بر اساس رابطه ۲-۱۲ بدست می آید.
که در این حالت عددی تصادفی انتخاب می شود که ژن مورد نظر برای جهش را تعیین می کند برای انتخاب محل ژن عددی تصادفی تعیین می شود و سپس تابع شایستگی برای آن کروموزوم بدست می آید که در صورت داشتن شایستگی بالاتر نسبت به کروموزوم قبلی کروموزوم جدید ذخیره سازی می شود.شرط پایان آن نیز تولید ۲۰ نسل متوالی بدون تغییر می باشد.معمولا کارهایی که دارای توابع جریمه می باشند باعث سربار اضافی در اجرای الگوریتم می باشد که این برای ما مطلوب نیست.
آقای گان گواوو نینگ همکارانش [۴۲] الگوریتم گرمادهی ژنتیکی ارائه دادند . کروموزم در این الگوریتم به شکل ۱۲ در نظر گرفته شده است:
شکل ۱۲- نمایش کروموزوم [۴۲]
که تعداد منابعی است که برای اجرای کار مورد استفاده قرار گرفته است. تابع شایستگی در آن بصورت رابطه ۲-۱۳ تعیین شده است
نشان دهنده وزن پارامتر های کنترل کیفیت می باشد و نشان دهنده مقدار مورد انتظار پارامترهای کنترل کیفیت می باشد تابع جامع ارزیابی است که وظیفه آن ارزیابی در زمان اجرای کار j بااستفاده منابع موجود است m تعداد پارامترها را مشخص می کند و n انواع منابع را نشان می دهد. از روش انتخاب متناسب در این الگوریتم استفاده شده است بدین صورت که با توجه به اندازه شایستگی افراد در یک نسل به آنها اولویتی داده می شود .عملگر تقاطع آن بصورت تک نقطه ای تعیین شده است. عملگر جهش به این شکل است که مجموعه ای تصادفی از یک یا چند مقدار کوچک در ژن انتخاب شده و با احتمال جهش در آن صورت میگیرد.مرحله گرمادهی در این الگوریتم پس از انتخاب و تقاطع و جهش انجام میگیرد که توانایی جستجوی محلی را بهبود می بخشد که در ۳ مرحله انجام میگیرد ۱- مقدار اولیه ای برای x0 بعد از انتخاب و تقاطع و جهش تعیین می شود ۲- یک راه حل امکان پذیر X1 تحت دمای TK ساخته می شود x1 راه حل همسایه x0 می باشد و اختلاف بین آنها از طریق رابطه ۲-۱۴ محاسبه می شود.
و توابع شایستگی آنها می باشند.با احتمال راه حل جدید وارد می شود.اگر راه حل به وضعیت متعادل در دما برسد می تواند به حالت ۲ یا ۳ برگردد ۳-دما می تواند با این روش کاهش پیدا کند رابطه ۲-۱۵ تابع کاهش دما در این الگوریتم می باشد:
شرط پایانی نیز بدین شکل تعریف می شود که شایستگی یک نسل به مقدار بیشینه خود برسد.استفاده از تلفیق تک نقطه ای نسبت به تلفیق دو نقطه ای ضعیف تر عمل می کند و روند همگرایی به جواب بهینه را کاهش می دهد.
آقای مزماز و همکارانش ]۴۳[ الگوریتم موازی ارائه دادند و از الگوریتم ژنتیک هیبریدی برای یافتن مجموعه بهینه استفاده نمودند آنها ازمدل موازی جزیره ای به منظور مهاجرت کارها استفاده می کنند.طول کروموزوم در این روش ۲۰ در نظر گرفته شده است و نرخ جهش آن ۳۵/۰ تعیین شده است
تابع شایستگی این روش در رابطه ۲-۱۶ نشان داده شده است:
A تعداد سوییچ کردن در یک سیکل زمان است C ظرفیت مجموع بار است و V ولتاژ تغدیه می باشد f تعداد تکرار می باشد و میزان هزینه محاسباتی برای کار i می باشد.
آقای موکانو و همکارانش ]۴۴[ الگوریتمی ژنتیکی ارائه دادند که در آن تابع شایسگی بصورت رابطه۲-۱۷ در نظر گرفته شده است:

هدف در این الگوریتم نزدیک شدن AQU به سمت عدد ۱ می باشد.برای انتخاب کروموزم ها از روش جرخه رولت استفاده شده است و همچنین از نخبه سالاری در انتخاب کروموزوم ها بهره برده شده است.عملگر تقاطع ۰٫۶ تعیین شده است و عملگر جهش ۰٫۰۵ در نظر گرفته شده است بیشینه تعداد تولید کروموزوم ۲۰ و طول کروموزوم نیز ۲۰ درنظر گرفته شده است.

کارهای مرتبط در سایر محیط های توزیع شده

آقای نیجونگ لی همکارانش[۴۵] الگوریتمی را ارائه داده اند که باعث بهبود عملکرد جستجو در مشکل اختصاص منابع می باشد. ۲ فرض در آن در نظر گرفته شده است ۱- R منبع وجود دارد که همه منابع باید به فعالیت ها اختصاص داده شود ۲- احتمال اختصاص منبع j به فعالیت i بصورت نشان داده شود.تابع هدف که باید مینیمم شود بصورت رابطه ۲-۱۸ نمایش داده می شود:
مقداری بولین است که وقتی برابر با ۱ است یعنی فعالیت j ام به منبع i ام اختصاص داده شده است و تابع جریمه می باشد.الگوریتم ارائه شده ادغامی از الگوریتم ژنتیک و الگوریتم مورچگان است برای جلوگیری از همگرایی زودرس و بدست آوردن راه حل های مناسب از الگوریتم ژنتیک و برای انجام تنظیمات در فضای جستجو برای نتیجه بهتر از الگوریتم مورچگان استفاده می کند.کروموزوم ها بصورت آرایه ای از فعالیت ها نشان داده شده است که مقدار i ام از ژن j نشان می دهد که منبع j به فعالیت i اختصاص داده شده است.۲ رویکرد برای بالا بردن توانایی جستجو ارائه شده است ۱- استفاده از عملگر تقاطع برای حفظ نخبگان به این صورت که فرزندان با ژن های احتمالا خوب والدین آنها ساخته شوند ژن خوب یعنی منبع j به فعالیت i با بهترین مقدار در تمام فعالیت ها اختصاص داده شود ۲ - قرار دادن اکتشاف بعد از حلقه اصلی الگوریتم ژنتیک است به این صورت که کروموزوم ها بر اساس بصورت نزولی مرتب شده و منبع j به بهترین مقدار اختصاص داده می شود.منابعی که هنوز در کروموزوم ها قرار نگرفته اند بصورت حریصانه با بهترین مقدار انتخاب شده و در مقداری بولین است که وقتی برابر با ۱ است یعنی فعالیت j ام به منبع i ام اختصاص داده شده است و تابع جریمه می باشد..بعد از الگوریتم ژنتیک نوبت استفاده از الگوریتم مورچگان است. ۳ مرحله اصلی در آن وجود دارد ۱- تولید عامل ها ۲- فعایت عامل ها ۳-واپاشی فرمون. بهترین راه حل از دنباله فرمون بروز رسانی شده استفاده می کند
آقای آندرو جی پیج و همکارانش [۴۶] الگوریتم ژنیتک در محیط توزیع شده ارائه دادند. هرکرموزوم در این مدل بصورت شکل ۱۳ نمایش داده می شود:
شکل ۱۳- نمایش کروموزوم [۴۴]
هر عدد نشان دهنده یک شناسه واحد برای یک کار است و با عدد ۱- صف هر پردازنده محدود می شود تابع شایستگی بصورت رابطه۲-۱۹ تعیین می شود
: تعداد کار های موجود , A :زمان پردازش هر کار , B: سربار ارتباطی کارها , x: یک زمانبندی برای جمعیت است و مقدار شایستگی برای کرموزوم x را با نشان می دهند که مقدار آن بین ۰ و ۱ است هر چه مقدار بزرگتر باشد زمانبندی مناسب تر می باشد.عملگر جهش بدین صورت پیاده سازی شده است که اگر طول بازه بعد از ۱۰ نسل بهبود نیافت نرخ جهش افزایش می یابد و در زمانی که طول بازه رو به بهبود است نرخ جهش کاهش می یابد.تابع انتخاب بر مبنای چرخه رولت می باشد شرایط توقف آن نیز به این شرح است ۱- تعداد تولید نسل بیش از تعداد تعیین شده باشد ۲- مقدار بهترین جواب پس از تعداد مشخصی از نسل ها تغییر نکند.
آقای یوان شودای و همکارش [۴۷] الگوریتم ژنتیکی برای سرویس ها در شبکه گرید ارائه دادند.کروموزوم به صورت مجموعه ای از مقادیر دودویی تشکیل شده است که بدین معنا است که منبع به نود اختصاص داده شده است.تابع شایستگی در آن بصورت رابطه ۲-۲۰ تعریف می شود:
Aمقدار ثابت مثبتی می باشد قابلیت اطمینان سرویس در شبکه گرید می باشد که بین ۰ تا ۱ قرار دارد و از تابع انتخاب چرخ رولت برای انتخاب کروموزوم ها استفاده شده است.عملگر جهش بین ۰٫۵% تا ۵% در نظر گرفته شده است .جمعیت در نظر گرفته شده بین ۲۰تا۳۰ کروموزوم است و تعداد تولید نسل نیز در آن بین ۱۰۰تا ۲۰۰ در نظر گرفته شده است.
آقای یانگ گاوو وهمکارانش [۴۸] برای زمان بندی در محیط گرید الگوریتمی را ارائه دادند.کروموزوم بصورت مقابل نمایش داده می شود = (,, . . ,) که n تعداد کارهای موجود در شبکه و m تعداد نود ها می باشد که m < n می باشد. تابع شایستگی آن نیز بصورت رابطه ۲-۲۱ در نظر گرفته شده است.
j : از ۱ تا p که p برابر اندازه جمعیت می باشد دررابطه ۲-۲۲ نتایج عملی بدست آمده از اجرای تعداد مختلفی از کارها در هر نود را بیان می کند بیشترین تعداد کاری است که نود i می تواند انجام دهد تعداد کارهای در حال اجرای نود i را نشان می دهد.برای انتخاب کرموزوم ها از روش چرخ رولت استفاده کرده است و برای بخش تقاطع آن از رابطه ۲-۲۳ استفاده می کند که P1 و P2 کروموزوم های والد انتخاب شده هستند.