شرط انتخاب والدهای متفاوت (تفاوت در حداقل یک دهم طول کروموزوم) برای تولید فرزندان کمک میکند تا بتوانیم قلههای محلی را رد کرده و فضاهای دیگر را نیز جستجو نمائیم و نوع تولید فرزندان (HUX) کمک میکند تا الگوریتم مکانهای مناسبتر را جستجو کند.
جستجوی محلی
عملیات جستجوی محلی، طبق روالی است که در قسمت مربوط به الگوریتم جستجوی محلی نسخه دوم توضیح دادیم. برای اینکه بتوانیم از مزیت جستجوی فراگیر الگوریتم ژنتیک نیز بهره ببریم، عملیات مربوط به جستجوی محلی را فقط روی نیمی از فرزندان اعمال میکنیم. با استفاده از این روش سعی داریم به صورت همزمان هم جستجوی فراگیر و هم میل به سمت بهترین جواب را داشته باشیم. اگر فقط بخواهیم از روش جستجوی فراگیر استفاده نمائیم باید به الگوریتم اجازه دهیم مکانهای مختلف فضای جستجو را بررسی نماید و این مسئله میتواند بسیار زمانبر باشد و در عین حال الگوریتم به سمت بهترین جواب میل نکند، و با سرعت کمی این کار را صورت دهد. اگر فقط از جستجوی محلی استفاده کنیم امکان این وجود دارد که با اجرای الگوریتم یک جمعیت یکدست تولید کنیم و نتوانیم از قلههای محلی عبور کنیم. بنابراین سعی میکنیم از مزیت میل به سمت بهترین جواب الگوریتم جستجوی محلی روی نیمی از فرزندان و از مزیت جستجو فراگیر، فرزندان و والدهایی که جستجوی محلی روی آن ها اعمال نشده استفاده کنیم.
انتخاب نسل بعد
برای نسل بعد از بین 75 والد نسل موجود و 150 فرزند تولید شده که روی 75 تا از آنها الگوریتم جستجوی محلی را اعمال کردهایم، بهترین موارد (کمترین زمان اتمام آخرین کار) را انتخاب و به نسل بعد منتقل میکنیم. دلیل انتخاب بهترینها این میباشد که سعی کنیم در حین اجرای الگوریتم هر نسل نسبت به نسل قبل از خود، بهتر بوده یا حداقل شرایط نسل قبلی را حفظ نماید. برای انجام این کار، برای 75 راهحل مربوط به نسل فعلی و 150 فرزند تولید شده مقدار آخرین زمان اتمام را محاسبه کرده و با استفاده از الگوریتم هیپ سورت این موارد را به صورت صعودی مرتب میکنیم. از ابتدای این آرایه مرتب شده به تعداد 75 راهحل (تعداد مربوط به جمعیت که در طول اجرای الگوریتم ثابت است) انتخاب شده و نسل بعد را تشکیل میدهند. برای جلوگیری از کند شدن الگوریتم مقادیر مربوط به آخرین زمان اتمام و محل مربوط به هر راهحل در آرایه مربوط به والدین و فرزندان را به صورت یک آرایه 2 بعدی که یک بعد آن به تعداد 225 (75+150) و بعد دیگر آن به تعداد 2 (یک خانه مقدار زمان اتمام آخرین کار و یک خانه محل مربوط به این راهحل در آرایههای والدین و فرزندان) میباشد را مرتب میکنیم. خروجی آرایهای یک بعدی خواهد بود که محل راهحلهای انتخاب شده را مشخص مینماید.
تعداد تکرار و شرط پایان
برای اینکه بتوانیم نتایج مناسبی را تولید نماییم و الگوریتم ژنتیک بتواند تاثیر خود را برای جستجوی فضای جستجو داشته باشد؛ الگوریتم مربوطه را 2000 بار تکرار مینمائیم و شرط اتمام تعداد تکرار 2000 بار میباشد و توجهی به ساختار جمعیتها در حین اجرا نداریم. این امکان وجود دارد که جمعیت بوجود آمده در تکرارهای بالاتر جمعیت بهتری باشد یا حتی در تکرارهای قبل از 2000 به همگرایی برسد و بهبود چندانی با اجرای الگوریتم پیدا نکنیم.
در هر تکرار بهترین راهحل تولیدی با بهترین راهحل کلی مقایسه میشود و در صورتیکه از راهحل کلی بهتر باشد به جای آن جایگزین میشود. در انتهای اجرای الگوریتم بهترین راهحل به عنوان خروجی برگردانده میشود.
4-8 جمعبندی
در این فصل به بررسی الگوریتمهای پیشنهادی برای حل مسئله زمانبندی پرداختیم و روشهای حریصانه ذکر شده به سرعت راهحلی را برای مسئله زمانبندی پیدا میکنند ولی کیفیت لازم را ندارند و کاهش چندانی را در زمان اتمام آخرین کار نداریم. روشهای توازن بار پیشنهادی اگرچه باعت بالا رفتن توازن بار روی ماشینها میشوند ولی کاهش زیادی را برای زمان اتمام آخرین کار ندارند. استفاده از روش ترکیبی پیشنهادی باعث کاهش زمان اتمام آخرین کار و بالا رفتن بهرهوری از منابع با هم میشود ولی باید زمان بیشتری را برای رسیدن به این مزایا نسبت به روشهای حریصانه صرف کنیم.در فصل به بررسی نتایج مقایسه روشهای پیشنهادی میپردازیم.
نتایج حاصل از ارزیابی
5-1 مقدمه
در این قسمت ابتدا محک ارزیابی که با آن به مقایسه الگوریتمها میپردازیم را توضیح داده میشود سپس نتایج هر یک از الگوریتمهای پیشنهادی در مقایسه با الگوریتمهای دیگر بررسی میشوند. در مقایسه روشهای مختلف دو پارامتر را مورد توجه قرار میدهیم. پارامتر اول مقدار زمان اتمام آخرین کار میباشد که از این پس با نام makespan از این پارامتر یاد میکنیم. در نگاشتهای تولیدی سعی میکنیم نگاشتی از کارها به منابع را پیدا کنیم که makespan کمتری را داشته باشد. پارامتر دیگر میزان بهرهوری از منابع میباشد که این پارامتر را نیز با نام resource utilization در نتایج میآوریم. به دلیل اینکه در زمانبندیهای دستهای، تمامی منابع با هم آزاد میشوند مطلوبتر این خواهد بود که تمامی منابع تا زمان آزادی کلی، کاری برای انجام شدن داشته باشند و دارای resource utilization بالایی باشند.
5-2 محک ارزیابی براون
در سال 2001 آقای براون و همکارانش[27] به بررسی 11 الگوریتم زمانبندی پرداختند و برای مقایسه این الگوریتمها محکی را تولید نمودند که از آن سال به بعد معیار ارزیابی الگوریتمهای زمانبندی در روشهای دستهای قرار گرفت. برای تولید این محک سعی شده که تا حد امکان شرایط موجود در محیط گرید برای کارها و منابع شبیهسازی شود. از جمله این موارد، میتوان به ناهمگن بودن کارها و منابع نام برد. علاوه بر این موضوع سازگار بودن یا نبودن منابع را نیز مورد بررسی قرار میدهند.
محک براون بر اساس سه معیار ناهمگنی کارها، ناهمگنی منابع و سازگاری منابع، 12 نوع مختلف از ماتریس های ETC را ایجاد میکند.
هر نمونه به صورت u_x_yyzz برچسب گذاری میشود که :
u به معنای توزیع یکپارچه میباشد.
x نشان دهنده نوع سازگاری میباشد (c سازگار، i ناسازگار و s نیمه سازگار)
سازگار: اگر ماشین i کار t را سریعتر نسبت به ماشین j انجام دهد و برای کلیه کارها این شرط برقرار باشد.
نیمه سازگار: اگر شرط سازگاری برای بعضی از کارها برقرار باشد.
ناسازگار: اگر ماشین i برای بعضی کارها سریعترین و برای بقیه کارها کندترین باشد.
yy نشان دهنده ناهمگنی کارها میباشد.(hi بالا و lo پایین)
zz نشان دهنده ناهمگنی منابع میباشد.(hi بالا و lo پایین)
ناهمگنی برای کارها مربوط به زمان اجراییهایی میباشد که کارهای مختلف روی یک منبع خاص احتیاج دارند. در صورتیکه کارها شبیه به هم بوده و به عنوان مثال نیازهای داده، ارتباطات و محاسبات نزدیک به هم داشته باشند، زمانهای اجرایی که روی یک ماشین مشخص برای کارهای متفاوت وجود دارد تقریبا نزدیک به هم خواهد بود و میزان ناهمگنی برای کارها پایین (lo) خواهد بود و در غیر این صورت میزان ناهمگنی بالا (hi) میباشد.