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

استاد راهنما:

دکتر غلامحسین دستغیبی فرد

برای رعایت حریم خصوصی نام نگارنده درج نمی گردد

تکه هایی از متن به عنوان نمونه :

فهرست مطالب:

1- مقدمه …………………………………………………………………………………………………… 1

1-1 مقدمه ……………………………………………………………………………………………………………. 1

1-2 هدف از اجرای پایان­نامه ………………………………………………………………………………. 2

1-3 مراحل انجام پایان­نامه ………………………………………………………………………………….. 2

1-4 ساختار پایان­نامه …………………………………………………………………………………………… 3

2- ادبیات موضوعی ………………………………………………………………………………………. 4

2-1 مقدمه ……………………………………………………………………………………………………………. 4

2-2 ساختار الگوریتم ژنتیک ………………………………………………………………………………… 6

2-3 عملگرهای ژنتیکی …………………………………………………………………………………………. 7

2-4 طریقه کلی الگوریتم ژنتیک ……………………………………………………………………………… 8

2-5 شرط پایان الگوریتم ………………………………………………………………………………………. 10

2-6 بعضی از کاربرد­های الگوریتم ژنتیک ……………………………………………………………… 10

2-7 تعاریف ……………………………………………………………………………………………………………… 11

2-8 مزایای اجرای موازی ……………………………………………………………………………………….. 12

2-9 مراحل زمانبندی در گرید …………………………………………………………………………….. 16

2-10 انواع زمانبند ………………………………………………………………………………………………….. 17

2-11 انواع زمانبندی ……………………………………………………………………………………………… 18

2-12 چگونگی­ی زمانبندی (ایستا و پویا) …………………………………………………………………… 19

2-13 ساختار زمانبند …………………………………………………………………………………………….. 19

2-14 انواع صف­بندی کارها ……………………………………………………………………………………. 21

2-15 پیچیدگی محاسباتی زمانبندی …………………………………………………………………….22

2-16 جمع بندی ………………………………………………………………………………………………… 22

3- پیشینه پژوهشی …………………………………………………………………………………….. 23

3-1 مقدمه ……………………………………………………………………………………………………………. 23

3-2 الگوریتم­های حریصانه ………………………………………………………………………………….. 23

3-3 الگوریتم­های تکاملی …………………………………………………………………………………….. 26

3-3-1 راه­کارهای مبتنی بر جستجوی محلی ………………………………………… 26

3-3-2 راه­کارهای جمعیت محور ……………………………………………………………. 28

3-4 جمع­بندی …………………………………………………………………………………………………… 31

4- الگوریتم­های پیشنهادی ………………………………………………………………………….. 33

4-1 مقدمه ……………………………………………………………………………………………………………. 33

4-2 فرضیات وتعاریف …………………………………………………………………………………………… 34

4-3 الگوریتم­ Asuffrage ……………………………………………………………………………………..

4-4 الگوریتم­ MaxSuffrage ………………………………………………………………………………..

4-5 الگوریتم توازن نسخه یک …………………………………………………………………………….. 38

4-6 الگوریتم توازن نسخه دو ………………………………………………………………………………. 40

4-7 الگوریتم ژنتیک و توازن بار ………………………………………………………………………….. 41

4-8 جمع­بندی ……………………………………………………………………………………………………… 46

5- نتایج حاصل از ارزیابی………………………………………………………………………………. 47

5-1 مقدمه ……………………………………………………………………………………………………………. 47

5-2 محک ارزیابی براون ……………………………………………………………………………………… 47

5-3 ارزیابی الگوریتم Asuffrage …………………………………………………………………………

5-4 ارزیابی الگوریتم MaxSuffrage ……………………………………………………………………

5-5 ارزیابی الگوریتم توازن نسخه یک …………………………………………………………………. 53

5-6 ازریابی الگوریتم توازن نسخه دو …………………………………………………………………… 54 دانلود متن کامل در سایت sabzfile.com

5-7 ارزیابی الگوریتم ژنتیک به همراه توازن بار……………………………………………………. 55

5-8 پیشنهادات برای آینده …………………………………………………………………………………. 57

6- منابع ……………………………………………………………………………………………………… 58

چکیده:

شبکه­های تورین محاسباتی (گرید) زمینه‌ای را فراهم آورده می باشد که بتوان از منابع ناهمگن در نقاط مختلف جغرافیایی برای حل مسائل پیچیده علمی، مهندسی و تجارت بهره گیری نمود. عملیات زمانبندی تأثیر کلیدی در عملکرد گرید اعمال می­کند. در این پایان نامه با بهره گیری از مزایای الگوریتم ژنتیک، پنج الگوریتم زمانبندی برای نگاشت بهینه­ای از کارهای دسته­ای روی ماشین­ ها ارائه شده می باشد که تمامی فضای جستجو مسأله زمانبندی را مطالعه کرده و یک توازن بار روی همه ماشین­ها ایجاد نماید. نتایج پیاده­ سازی الگوریتم­های ارائه شده نشان دهنده متوسط کاهش 13.23 درصد در زمان اتمام آخرین کار نسبت به الگوریتم های پیشین می باشد.

1- مقدمه

1-1- مقدمه

کامپیوترهای امروزی مانند مغز بشر معمولا از بخش کوچکی از توانایی‌های خود بهره گیری می‌کنند و اغلب به‌ صورت غیرفعالند و منتظر اطلاعات ورودی می‌مانند. تصور کنید که اگر از منابع سخت‌افزاری این همه کامپیوتر غیرفعال بهره گیری گردد و همه در یک کامپیوتر جمع شوند، چه دستگاه پرقدرتی خواهیم داشت. شبکه­های محاسباتی (گرید)[1] زمینه‌ای را فراهم آورده می باشد که بتوان از منابع (کامپیوتری) سیستم‌های دیگر نیز بهره گیری نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به اندازه زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل بهره گیری از گرید می­باشد[1].

هدف شبکه­های محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریت­های مختلف بین کاربران می باشد. کاربران درخواست­های خود را پیوسته برای محیط گرید ارسال می­کنند و بخش مدیریت منابع[2] این کارها را به گره های محاسباتی[3] موجود در شبکه اختصاص می­دهد. به چگونگی تخصیص این درخواست­ها روی گره­های محاسباتی مختلف زمانبندی[4] می­گویند.

اعمال سیاست­های مختلف برای عملیات زمانبندی نتایج متفاوتی را خواهد داشت که این سیاست با در نظر داشتن اهداف مشخص شده برای گرید اتخاذ می­شوند. عملیات زمانبندی در سیاست­های مختلف از فاکتورهای متفاوتی برای تخصیص کارها روی منابع مختلف بهره گیری می­کند. امکان دارد یک فاکتور تأثیر تعیین کننده­ای در یکی از سیاست­ها داشته باشد اما در سیاست دیگر اصلا به آن توجه نشود، از اینرو هدف هر الگوریتم بهینه کردن سیاست مورد نظر خود می باشد.

 1-2 هدف از اجرای پایان نامه

با در نظر داشتن تاثیر بالای عملیات زمانبندی در عملکرد بهینه گرید و مزایایی که برای گرید در قسمت قبل ذکر گردید، ارائه یک روش کارا در زمانبندی می تواند تاثیر زیادی در حل مسائل بزرگ در شاخه های مختلف داشته باشد.

در گریدهای محاسباتی هدف بالا بردن درصد بهره گیری از منابع در کنار کاهش زمان اتمام آخرین کار می­باشد. در این طرح پژوهش همین اهداف را دنبال می­کنیم و کوشش داریم نگاشتی از کارها را ارائه دهیم که هم باعث بالا رفتن بهره­وری از منابع گردد و هم کمترین زمان را برای اتمام آخرین کار داشته باشد.

1-3 مراحل انجام پایان نامه

برای انجام پایان­نامه آغاز مفاهیم گرید و روش­های موجود مطالعه و مطالعه شدند و بعد از مقایسه صورت گرفته روی روش­های مختلف، الگوریتم ژنتیک برای تولید نگاشت انتخاب گردید. در کنار الگوریتم ژنتیک الگوریتمی را ارائه کردیم که به توازن بار روی منابع کمک می­کند و با بهره گیری از مزایای دو الگوریتم نام برده شده نگاشت بهینه­ای را برای کارها بدست آوردیم. برای پیاده­سازی الگوریتم­ها از زبان برنامه نویسی java شده می باشد.

 1-4 ساختار پایان نامه

در فصل دوم الگوریتم ژنتیک، پارامترهای موثر در این الگوریتم و مفاهیم اولیه­ی زمانبندی مورد مطالعه قرار می­گیرد. در فصل سوم گذری بر تحقیقات پیشین خواهیم داشت. الگوریتم­های پیشنهادی در فصل چهارم ارائه شده می باشد و در فصل پنجم نتایج حاصل از ارزیابی و مقایسه الگوریتم­های پیشنهادی آورده شده می باشد.

2- ادبیات موضوعی

1-2- مقدمه

در این فصل آغاز الگوریتم ژنتیک را مورد مطالعه قرار می­دهیم. در این مطالعه ساختار کلی الگوریتم ژنتیک و پارامترهای تاثیرگذار در عملکرد این الگوریتم را مشخص می­کنیم. در ادامه محیط شبکه­های محاسباتی گرید را تبیین داده و به مطالعه اصطلاحات و تعاریف موجود می­پردازیم. روش­های مختلف زمانبندی را اظهار کرده و انواع صف­بندی کارها را مورد مطالعه قرار می­دهیم.

الگوریتم ژنتیک، الهامی از علم ژنتیک و نظریه تکامل داروین می باشد و بر اساس بقای برترین‏ها یا انتخاب طبیعی استوار می باشد. یک کاربرد متداول الگوریتم ژنتیک، بهره گیری از آن بعنوان تابع بهینه‏کننده می باشد. الگوریتم ژنتیک ابزار سودمندی دربازشناسی الگو، انتخاب ویژگی، درک تصویر و یادگیری ماشینی می باشد[3-8]. در الگوریتم‏ ژنتیک[1]، چگونگی تکامل ژنتیکی موجودات زنده شبیه‏سازی می‏گردد.

اگرچه کارهایی توسط یک زیست­شناس به نام Fraser در زمینه مدل­سازی تکامل در سیستم‌های بیولوژیک در دهه 60 میلادی صورت گرفت اما الگوریتم ژنتیک برای کاربردهای مهندسی و به صورت امروزی آن، نخستین بار توسط جان هلند[9] متخصص علوم کامپیوتر دانشگاه میشیگان در سال 1975 پیشنهاد گردید. کار وی آغاز تمامی کوشش­ها برای کاربرد الگوریتم ژنتیک در مهندسی می باشد. پس از آن کارهای Dejong [10]در سال 1975 در زمینه مطالعه و مقایسه چندین روش الگوریتم ژنتیک پایه‌های نظری بحث را فراهم آورد. این الگوریتم با الهام از طبیعت بر پایه اصل تکاملی «پایداری بهترین‌ها»[2] استوار می باشد. الگوریتم ژنتیک اگرچه پس از الگوریتم استراتژی تکاملی پیشنهاد گردید اما مشهورترین روش از بین الگوریتم‌های تکاملی می باشد. در یک الگوریتم ژنتیک یک جمعیت از افراد طبق مطلوبیت آنها در محیط بقا می­یابند. افرادی با قابلیت­های برتر، شانس ازدواج وتولید مثل بیشتری را خواهند پیدا نمود. پس بعد از چند نسل فرزندانی با کارایی بهتر به وجودمی‌آیند. در الگوریتم ژنتیک هر فرد از جمعیت بصورت یک کروموزوم معرفی می گردد. کروموزوم­ها در طول چندین نسل کامل­تر می شوند. در هر نسل کروموزوم­ها ارزیابی می شوند و متناسب با ارزش خود امکان بقا و تکثیر می‌یابند. تولید نسل در بحث الگوریتم ژنتیک با عملگرهای آمیزش3 و جهش4 صورت می‏گیرد. والدین برتر بر اساس یک تابع برازندگی انتخاب می شوند.

در هر مرحله از اجرای الگوریتم ژنتیک، یک دسته از نقاط فضای جستجو مورد پردازش‏های تصادفی قرار می‏گیرند. به این شکل که به هر نقطه دنباله‏ای از کاراکترها نسبت داده می‏گردد و بر روی این دنباله‏ها، عملگرهای ژنتیکی اعمال می‏شوند. سپس دنباله‏های بدست آمده رمزگشایی می‏گردد تا نقاط جدیدی در فضای جستجو بدست آید. در انتها براساس این که تابع هدف در هر یک از نقاط چه مقدار باشد، احتمال شرکت کردن آنها در مرحله بعد تعیین می‏گردد[11-14].

الگوریتم‏ ژنتیک را می‏توان یک روش بهینه‏سازی تصادفی جهت‏دار دانست که به تدریج به سمت نقطه بهینه حرکت می‏کند. در مورد ویژگی‌های الگوریتم ژنتیک در مقایسه با دیگر روش‌های بهینه سازی می‌توان گفت که الگوریتمی می باشد که بدون داشتن هیچ گونه اطلاعی از مسئله و هیچ گونه محدودیتی بر نوع متغیرهای آن برای هر گونه مسئله ای قابل اعمال می باشد و دارای کارآیی اثبات شده‌ای در یافتن بهینه کلی[3] می‌باشد. توانایی این روش در حل مسائل پیچیده بهینه‌سازی می باشد که روش‌های کلاسیک یا قابل اعمال نیستند و یا دریافتن بهینه کلی قابل اطمینان نیستند[15].

[1] Genetic Algorithm

[2] Survival of the fittest

3 Cross Over

4 Mutation

[3] Global Optimum

[1]Grid Computing

[2]Resource Management

[3]Nodes Computation

[4]Scheduling

***ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود می باشد***

متن کامل را می توانید دانلود نمائید

این مطلب رو هم توصیه می کنم بخونین:   پایان نامه ارشد نرم افزار: بهینه سازی خوشه ها با استفاده از الگوریتم های تکاملی برای شخصی سازی وب

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

جستجو در سایت :   

اما در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 77

قیمت : 14700 تومان

 

***

—-

پشتیبانی سایت :       

****         serderehi@gmail.com