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
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