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

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] استوار است. الگوریتم ژنتیك اگرچه پس از الگوریتم استراتژی تكاملی پیشنهاد گردید ولی مشهورترین روش از بین الگوریتم‌های تكاملی است. در یك الگوریتم ژنتیك یك جمعیت از افراد طبق مطلوبیت آنها در محیط بقا می­یابند. افرادی با قابلیت­های برتر، شانس ازدواج وتولید مثل بیشتری را خواهند یافت. بنابراین بعد از چند نسل فرزندانی با كارایی بهتر بوجود می‌آیند. در الگوریتم ژنتیك هر فرد از جمعیت بصورت یك كروموزوم معرفی می‌شود. كروموزوم­ها در طول چندین نسل كامل­تر می‌شوند. در هر نسل كروموزوم­ها ارزیابی می‌شوند و متناسب با ارزش خود امكان بقا و تكثیر می‌یابند. تولید نسل در بحث الگوریتم ژنتیك با عملگرهای آمیزش و جهش صورت می‏گیرد. والدین برتر بر اساس یك تابع برازندگی انتخاب می‌شوند.

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

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