شکل 2-9 ساختار زمانبند سلسله مراتبی …………………………………………………………………………….. 20
شکل 2-10 ساختار زمانبند غیر متمرکز ……………………………………………………………………………… 20
شکل 4-1 الگوریتم توازن نسخه دوم ……………………………………………………………………………………. 41
مقدمه
1-1 مقدمه
کامپیوترهای امروزی مانند مغز انسان معمولا از بخش کوچکی از توانایی‌های خود استفاده می‌کنند و اغلب به‌ صورت غیرفعالند و منتظر اطلاعات ورودی می‌مانند. تصور کنید که اگر از منابع سخت‌افزاری این همه کامپیوتر غیرفعال استفاده شود و همه در یک کامپیوتر جمع شوند، چه دستگاه پرقدرتی خواهیم داشت. شبکههای محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع (کامپیوتری) سیستم‌های دیگر نیز استفاده نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به میزان زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل استفاده از گرید میباشد[1].
هدف شبکههای محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریتهای مختلف بین کاربران است. کاربران درخواستهای خود را پیوسته برای محیط گرید ارسال میکنند و بخش مدیریت منابع این کارها را به گره های محاسباتی موجود در شبکه اختصاص میدهد. به چگونگی تخصیص این درخواستها روی گرههای محاسباتی مختلف زمانبندی میگویند.
اعمال سیاستهای مختلف برای عملیات زمانبندی نتایج متفاوتی را خواهد داشت که این سیاست با توجه به اهداف مشخص شده برای گرید اتخاذ میشوند. عملیات زمانبندی در سیاستهای مختلف از فاکتورهای متفاوتی برای تخصیص کارها روی منابع مختلف استفاده میکند. امکان دارد یک فاکتور نقش تعیین کنندهای در یکی از سیاستها داشته باشد ولی در سیاست دیگر اصلا به آن توجه نشود، از اینرو هدف هر الگوریتم بهینه کردن سیاست مورد نظر خود است.
1-2 هدف از اجرای پایان نامه
با توجه به تاثیر بالای عملیات زمانبندی در عملکرد بهینه گرید و مزایایی که برای گرید در قسمت قبل ذکر شد، ارائه یک روش کارا در زمانبندی می تواند تاثیر زیادی در حل مسائل بزرگ در شاخه های مختلف داشته باشد.
در گریدهای محاسباتی هدف بالا بردن درصد استفاده از منابع در کنار کاهش زمان اتمام آخرین کار میباشد. در این طرح تحقیق همین اهداف را دنبال میکنیم و سعی داریم نگاشتی از کارها را ارائه دهیم که هم باعث بالا رفتن بهرهوری از منابع شود و هم کمترین زمان را برای اتمام آخرین کار داشته باشد.
1-3 مراحل انجام پایان نامه
برای انجام پایاننامه ابتدا مفاهیم گرید و روشهای موجود مطالعه و بررسی شدند و بعد از مقایسه صورت گرفته روی روشهای مختلف، الگوریتم ژنتیک برای تولید نگاشت انتخاب شد. در کنار الگوریتم ژنتیک الگوریتمی را ارائه کردیم که به توازن بار روی منابع کمک میکند و با استفاده از مزایای دو الگوریتم نام برده شده نگاشت بهینهای را برای کارها بدست آوردیم. برای پیادهسازی الگوریتمها از زبان برنامه نویسی java شده است.
1-4 ساختار پایان نامه
در فصل دوم الگوریتم ژنتیک، پارامترهای موثر در این الگوریتم و مفاهیم اولیهی زمانبندی مورد بررسی قرار میگیرد. در فصل سوم گذری بر تحقیقات پیشین خواهیم داشت. الگوریتمهای پیشنهادی در فصل چهارم ارائه شده است و در فصل پنجم نتایج حاصل از ارزیابی و مقایسه الگوریتمهای پیشنهادی آورده شده است.
ادبیات موضوعی
2-1 مقدمه
در این فصل ابتدا الگوریتم ژنتیک را مورد بررسی قرار میدهیم. در این بررسی ساختار کلی الگوریتم ژنتیک و پارامترهای تاثیرگذار در عملکرد این الگوریتم را مشخص میکنیم. در ادامه محیط شبکههای محاسباتی گرید را شرح داده و به بررسی اصطلاحات و تعاریف موجود میپردازیم. روشهای مختلف زمانبندی را بیان کرده و انواع صفبندی کارها را مورد بررسی قرار میدهیم.
الگوریتم ژنتیک، الهامی از علم ژنتیک و نظریه تکامل داروین است و بر اساس بقای برترین‏ها یا انتخاب طبیعی استوار است. یک کاربرد متداول الگوریتم ژنتیک، استفاده از آن بعنوان تابع بهینه‏کننده است. الگوریتم ژنتیک ابزار سودمندی دربازشناسی الگو، انتخاب ویژگی، درک تصویر و یادگیری ماشینی است[3-8]. در الگوریتم‏ ژنتیک، نحوه تکامل ژنتیکی موجودات زنده شبیه‏سازی می‏شود.
اگرچه کارهایی توسط یک زیستشناس به نام Fraser در زمینه مدلسازی تکامل در سیستم‌های بیولوژیک در دهه 60 میلادی صورت گرفت ولی الگوریتم ژنتیک برای کاربردهای مهندسی و به صورت امروزی آن، نخستین بار توسط جان هلند[9] متخصص علوم کامپیوتر دانشگاه میشیگان در سال 1975 پیشنهاد گردید. کار وی آغاز تمامی کوششها برای کاربرد الگوریتم ژنتیک در مهندسی است. پس از آن کارهای Dejong [10]در سال 1975 در زمینه بررسی و مقایسه چندین روش الگوریتم ژنتیک پایه‌های نظری بحث را فراهم آورد. این الگوریتم با الهام از طبیعت بر پایه اصل تکاملی «پایداری بهترین‌ها» استوار است. الگوریتم ژنتیک اگرچه پس از الگوریتم استراتژی تکاملی پیشنهاد گردید ولی مشهورترین روش از بین الگوریتم‌های تکاملی است. در یک الگوریتم ژنتیک یک جمعیت از افراد طبق مطلوبیت آنها در محیط بقا مییابند. افرادی با قابلیتهای برتر، شانس ازدواج وتولید مثل بیشتری را خواهند یافت. بنابراین بعد از چند نسل فرزندانی با کارایی بهتر بوجود می‌آیند. در الگوریتم ژنتیک هر فرد از جمعیت بصورت یک کروموزوم معرفی می‌شود. کروموزومها در طول چندین نسل کاملتر می‌شوند. در هر نسل کروموزومها ارزیابی می‌شوند و متناسب با ارزش خود امکان بقا و تکثیر می‌یابند. تولید نسل در بحث الگوریتم ژنتیک با عملگرهای آمیزش3 و جهش4 صورت می‏گیرد. والدین برتر بر اساس یک تابع برازندگی انتخاب می‌شوند.
در هر مرحله از اجرای الگوریتم ژنتیک، یک دسته از نقاط فضای جستجو مورد پردازش‏های تصادفی قرار می‏گیرند. به این صورت که به هر نقطه دنباله‏ای از کاراکترها نسبت داده می‏شود و بر روی این دنباله‏ها، عملگرهای ژنتیکی اعمال می‏شوند. سپس دنباله‏های بدست آمده رمزگشایی می‏گردد تا نقاط جدیدی در فضای جستجو بدست آید. در آخر براساس این که تابع هدف در هر یک از نقاط چه مقدار باشد، احتمال شرکت نمودن آنها در مرحله بعد تعیین می‏گردد[11-14].
الگوریتم‏ ژنتیک را می‏توان یک روش بهینه‏سازی تصادفی جهت‏دار دانست که به تدریج به سمت نقطه بهینه حرکت می‏کند. در مورد ویژگی‌های الگوریتم ژنتیک در مقایسه با دیگر روش‌های بهینه سازی می‌توان گفت که الگوریتمی است که بدون داشتن هیچ گونه اطلاعی از مسئله و هیچ گونه محدودیتی بر نوع متغیرهای آن برای هر گونه مسئله ای قابل اعمال است و دارای کارآیی اثبات شده‌ای در یافتن بهینه کلی می‌باشد. توانایی این روش در حل مسائل پیچیده بهینه‌سازی است که روش‌های کلاسیک یا قابل اعمال نیستند و یا دریافتن بهینه کلی قابل اطمینان نیستند[15].
2-2 ساختار الگوریتم‏ ژنتیک
به طور کلی، الگوریتم‏ ژنتیک از اجزاء زیر تشکیل می‏شود:
کروموزوم