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

فهرست
عنوان صفحه
فصـل اول 11
مقدمه 11
راهکارهای ارائه‌شده 13
فصـل دوم 17
مطالعات 17
گرید محاسباتی 19
اجزای تشکیل‌دهنده گرید 19
ساختمان گرید 19
مشخصات گرید محاسباتی 21
طبقه‌بندی سیستم گرید 21
گرید محاسباتی 22
مزایای کلیدی مدل محاسباتی گرید 23
تحکیم 23
گریدهای موجود در زندگی روزمره 24
گریدهای ملی 24
گریدهای خصوصی 25
دسته‌بندی توپولوژی‌های سیستم گرید 25
گرید نوع اول IntraGrid 26
گرید نوع دوم (ExtraGrid) 26
گرید نوع سوم InterGrid 26
استفاده سیستم گرید از دیدگاه یک مدیر شبکه 27
الگوریتم‌های زمان‌بندی تعادل بار 28
زمان‌بندی ایستا 28
زمان‌بندی دینامیکی 28
زمان‌بندی توزیع‌شده 28
مقایسه بین محاسبات گرید و محاسبات خوشه‌ای 29
2-2 مسئله زمان‌بندی کارها در سیستم محاسباتی گرید 30
تعاریف کلی در سیستم زمان‌بندی کارها در گرید 31
آشنایی با الگوریتم‌های تکاملی جهت زمان‌بندی کارها در سیستم گرید 32
بررسی الگوریتم ژنتیک (GA) جهت زمان‌بندی کارها در سیستم گرید 32
بررسی الگوریتم بهینه‌سازی انبوه ذرات (PSO) جهت زمان‌بندی کارها در سیستم گرید 35
بررسی الگوریتم رقابت استعماری (ICA) جهت زمان‌بندی کارها در سیستم گرید. 39
بررسی الگوریتم شبیه‌سازی‌شده تبرید (SA) برای حل مسئله زمان‌بندی کارها در سیستم گرید 44
بررسی الگوریتم بهینهسازی کلونی مورچهها (ACO) جهت زمان‌بندی کارها در سیستم گرید 46
بررسی الگوریتمهای تکاملی پیشین برای مسئله زمان‌بندی گرید 51
نتیجه‌گیری 55
فصـل سوم 57
الگوریتمهای پیشنهادی 57
فرضیات لازم برای زمان‌بندی کارها در سیستم گرید 58
تشریح اصول روش پیشنهادی 59
روش پیشنهادی اول (روش ترکیبی) 62
روش پیشنهادی نوع دوم (روش هیبریدی) 73
فصـل چهارم 79
پیاده‌سازی و ارزیابی نتایج 79
آشنایی با ابزارهای پیاده‌سازی 79
آشنایی با نرم‌افزار متلب 79
آشنایی با CPUID 79
کدهای اساسی در الگوریتم‌های پیشنهادی 82
کدهای دیتابیس ایجادشده برای کارها و پردازشگرها 82
کدهای تخصیص تصادفی کارها به پردازشگرها (ایجاد کروموزوم‌های اولیه) 83
کدهای محاسبه زمان اتمام اجرای کارها در تابع هزینه هدف 83
کدهای جستجوی بهینه‌سازی پیشنهادی 83
کد پیاده‌سازی نحوه ارزیابی روند تابع هدف (NFE) 84
کدهای عملگر تقاطع در الگوریتم‌های پیشنهادی مبتنی بر ژنتیک 84
کدهای عملگر جهش در الگوریتم‌های پیشنهادی مبتنی بر ژنتیک 85
کدهای اساسی در الگوریتم پیشنهادی بهینه‌سازی انبوه ذرات 85
کدهای اساسی در الگوریتم پیشنهادی رقابت استعماری 86
کدهای اساسی در الگوریتم پیشنهادی شبیه‌سازی تبرید 87
کدهای اساسی در الگوریتم پیشنهادی بهینه‌سازی کلونی مورچگان 88
کدهای اساسی عمل هیبریدی برای الگوریتم‌های پیشنهادی نوع دوم 89
ارزیابی 89
ارزیابی روش پیشنهادی اول 89
ارزیابی روش پیشنهادی دوم 91
ارزیابی روش پیشنهادی دوم 103
فصـل پنجم 115
نتیجه‌گیری و کارهای آینده 115
نتیجه‌گیری 115
کارهای آینده 116
کارهای در دست اقدام 116
منـابع و مآخـذ 117

اساس محاسبات گرید توسط فاستر و همکارانش در دهه‌های ۱۹۸۰ و ۱۹۹۰ به وجود آمد [1] اصطلاح گرید به‌منظور ارائه یک زیرساخت محاسباتی توزیع‌شده برای پاسخگویی به نیازهای روزافزون در حوزه‌ی علوم و مهندسی مطرح شد. از آن زمان تابه‌حال پیشرفت‌های قابل‌ملاحظه‌ای در ساختار این سیستم صورت گرفته است، همچنین خود عبارت گرید در طول این سالیان حداقل در ادراک عمومی با سایر علوم ترکیب‌شده است و از شبکه‌های پیشرفته تا هوش مصنوعی را در برمی‌گیرد [2]
با توجه به گسترش روزافزون کاربران شبکه گرید و به دنبال آن افزایش حجم درخواست‌های کاربران به‌منظور دسترسی به منابع مختلف در شبکه لذا پیاده‌سازی سیستمی در گرید برای تسهیل فرآیند زمان‌بندی کارها در گرید از اهمیت خاصی برخوردار است. از این حیث زمان‌بندی کارها که جزء مسائل دشوار است، یک مسئله چالش‌برانگیز در محیط محاسبات گرید شناخته‌شده است.
به‌طورکلی پیدا کردن زمان‌بندی بهینه برای چنین محیطی با اســتفاده از روش‌های ســنتی معمولی کاری
چندان ساده نیست. درحالی‌که با استفاده از روش‌های فرا اکتشافی، به‌راحتی راه‌حل‌های نزدیک به بهینه برای این مسئله پیچیده ایجاد خواهد شد [3].
سیستم گرید مجموعه‌ای متشکل از سخت‌افزارها و نرم‌افزارهای توسعه‌یافته‌ای است که قابلیت دسترسی مطمئن، مســتحکم، فراگیر، معقول و صــرفه جویانه به‌منظور افزایش توان محاســباتی را به وجود می‌آورد.
پیاده‌سازی این محیط به اشتراک‌گذاری شده، سهولت دسترسی به مجموعه عظیمی از منابع محاسباتی ازجمله کامپیوترها، سرورها، فضای ذخیره‌سازی، نرم‌افزارهای کاربردی، داده‌ها، سرویس‌ها و ابزارهای جانبی را فراهم می‌آورد که برحســب تقاضــای کاربران می‌تواند ارتباط از طریق اینترنت را با ایجاد سرویس‌های امنیتی، مانیتورینگ و مدیریت منابع برای آنان ممکن سازد و به‌عبارتی‌دیگر این سیستم پیشنهادی می‌تواند برای مرکزیت سیستم‌های اینترنتی در محاسبات ابری نیز استفاده شود.
محیط گرید دربرگیرنده مفاهیم متفاوتی اسـت که یکی از اصلی‌ترین مفاهیم مطرح‌شده که از اهمیت خاصی برخوردار است زمان‌بندی کارها در سیستم محاسباتی گرید است. هر منبع پردازشی که به شبکه گرید وصـل شـود یک گره نامیده می‌شود. گره‌های محاسـباتی در سـاختار و مدیریت ناهمگون بوده و با لینک‌های با کارایی و قابلیت اطمینان متفاوت به یکدیگر متصــل می‌باشند. هدف زمان‌بندی کارها فرایند تخصیص کارها به هر گره محاسباتی در حداقل زمان ممکن هست [4] این تخصیص که توسط نرم‌افزار انجام می‌شود زمان‌بند نامیده می‌شود. درواقع زمان‌بند در گرید الگوریتمی است که توانایی پیدا کردن منابع مطلوب برای پردازش یک کار را داراست که هدف تابع اصلی پیدا کردن منابع بهینه و تخصیص آن‌ها به هر کاری است [5].
زمان‌بندی کاربران ازجمله اساسی‌ترین نیازهایی است که باید توسط هر سیستم توزیع‌شده پاسخ داده شود. لذا مکانیزی که با سرعت‌بالا و هزینه اندک بتواند منبع بهینه را برای کاربران مهیا سازد و زمان اتمام اجرای کارها را کاهش دهد، بسیار ضروری است [6].

راهکارهای ارائه‌شده
هدف توسعه زمان‌بندی گرید با استفاده از الگوریتم تکاملی و اطلاعات دینامیکی برای بهبود تصمیم‌گیری زمان‌بندی است و ازآنجایی‌که روش‌های کلاسیک استفاده محدودی دارند و در فضای مسئله با ابعاد بالا شکست می‌خورند. در این روش فضای جستجو با اندازه مسئله رشد می‌کند و بنابراین جستجوی جامع یک راه‌حل عملی نیست. از این حیث برای حل این نوع مسائل بهینه‌سازی، روش‌های فرا اکتشافی مانند روش محاسبات تکاملی استفاده می‌شود که فرضیات بسیار کمی برای مسئله‌دارند و می‌تواند راه‌حل‌های مسئله را در فضـای جستجوی بزرگ، جسـتجو نماید. زمان‌بندی بر مبنای اکتشافات تکاملی سریع‌تر از روش‌های معمول می‌تواند زمان اتمام کارها را به حداقل برساند.
این الگوریتم‌ها، قادر به ایجاد زمان‌بندی باکیفیت‌تری در سـیستم گرید می‌باشند و کارایی مؤثری در تخصیص کارها به منابع دارند. تخصیص بهینه کارها به منابع باهدف مینیمم کردن زمان اتمام اجرای کارها و روند زمانی اجرای کارها صورت می‌گیرد که این دو، معیار بسیار مهم در سیستم گرید هستند.
ترکیب الگوریتم‌های تکاملی راهکاری جدید و پیچیده برای بهینه نمودن آن‌ها اســت. ترکیب به معنای به‌کارگیری هم‌زمان دو یا چند روش برای استفاده از مزایا و کمرنگ کردن معایب آن‌ها است. ویژگی برجسته این الگوریتم‌های پیشـنهادی، گریز از نقطه کمینه محلی اسـت که توسـط الگوریتم ژنتیک به وجود می‌آید و موجب افزایش قدرت این الگوریتم برای تولید راه‌حل‌های بهینه می‌شوند و باعث می‌شود نســـبت به روش‌های کلاسیک بهینه‌سازی سرعت هم‌گرایی بیشتری داشته باشند.
در این مطالعه به بررسی مسئله زمان‌بندی کارها در سیستم گرید با استفاده از ترکیب الگوریتم ژنتیک با الگوریتم‌های تکاملی پرداخته می‌شود و بهبود کارایی این الگوریتم‌ها با الگوریتم‌های ساده تشکیل‌دهنده آن‌ها برای ایجاد زمان‌بندی سوپر موردتحقیق واقع می‌شود. سپس بررسی می‌شود این الگوریتم‌های پیشنهادی توانسته‌اند، در کاهش زمان اتمام اجرای کارها و روند زمانی اجرای کارها مؤثر باشند و درواقع عملکرد الگوریتم ژنتیک را بهبود بخشنده و روند جستجوی محلی این الگوریتم را به سمت جستجوی سراسری میل دهد و از همگرایی زودرس و توقف در مینیمم‌های محلی جلوگیری کرده و یافتن بهینه سراسری را تضمین می‌کنند؛ یعنی به‌عبارت‌دیگر به ایجاد الگوریتم‌های تکاملی جدید که حاصل ترکیب الگوریتم ژنتیک با الگوریتم بهینه‌سازی انبوه ذرات، الگوریتم رقابت استعماری، الگوریتم شبیه‌سازی تبرید و الگوریتم کلونی مورچگان برای مسئله بهینه‌سازی زمان‌بندی کارهای توزیع‌شده در سیستم گرید می‌پردازیم و سپس هر الگوریتم پیشنهادی با الگوریتم‌های ساده در هر ترکیب مقایسه شده و با پیاده‌سازی آن‌ها در متلب عملکرد الگوریتم‌های پیشنهادی در زمان‌بندی کارهای کاربران مشاهده می‌شود.
به‌طورکلی می‌توان اهداف این مطالعه را در به‌کارگیری راهکار پیشنهادشده در موارد زیر خلاصه کرد.
– کاهش زمان اتمام اجرای کارها
– افزایش بهره‌وری سیستم
– افزایش سرعت در تخصیص منابع به کاربران
ازجمله پرسش‌هایی که این مطالعه سعی در پاسخ به آن دارد می‌توان به موارد زیر اشاره نمود.
آیا یک محقق علوم کامپیوتری می‌تواند مسئله‌ی زمان‌بندی کارها در سیستم گرید را در مدت‌زمان کمی بهینه کند؟
بله الگوریتم‌های تکاملی با روند خاصی که دارند به‌سرعت می‌توانند بر روی جمعیت توزیع‌شده اعمال کنند.
– آیا در زمان اتمام اجرای کارها صرفه‌جویی لازم به‌عمل‌آمده است؟
ما در این مطالعه با مقایسه زمان اتمام کارها در هر الگوریتم پیشنهادی (ترکیبی و یا هیبریدی) با الگوریتم‌های ساده متشکل در آن می‌توانیم میزان بهبود این روش را موردتحقیق قرار می‌دهیم و با در نظر گرفتن روند زمانی جریان کارها، هر الگوریتمی که بتواند در این معیار دوم نیز موفق‌تر عمل کند به‌عنوان بهترین الگوریتم پیشنهادی برگزیده می‌شود.
آیا این روش توانسته است در محیط اجرای کارها بهینه بهتری از خود نشان دهد؟
چون الگوریتم‌های پیشنهادی با روش‌های فرا اکتشافی عمل می‌کنند که می‌توانند با جهت‌گیری‌های خاص خود جمعیت وسیعی را پوشش داده و هنگامی‌که الگوریتم‌هایی چون FCFS و SJF به علت حجم زیاد کارهای کاربران از اتمام کل کارهای ارائه داده‌شده به سیستم گرید عاجز می‌مانند و تعادل بار کاری در سیستم از بین می‌رود، این روش به‌راحتی می‌تواند پاسخگوی نیاز کاربران باشد. درواقع با این طراحی جدید زمان‌بند با سرعت بیشتری به زمان‌بندی کارهای دریافتی از کاربران می‌پردازد که باعث کارایی هر چه بیشتر سیستم و کاهش ترافیک شبکه گرید می‌گردد