۱۵

۲۹۶۸

۵-۳ بررسی پارامترهای مختلف الگوریتم پیشنهادی
الگوریتم پیشنهادی ترکیبی از الگوریتم های رقابت استعماری و روش تپه نوردی تکراری می باشد. در این الگوریتم، مسئله زمانبندی و تخصیص منابع با بهره گرفتن از الگوریتم رقابت استعماری و با ایجاد یک مجموعه با تعداد کشور اولیه حل می شود. زمانی که الگوریتم رقابت استعماری دچار همگرایی زودرس گردید و در بهینه های محلی گرفتار شد، مکانیسم تشخیص همگرایی مبتنی بر شباهت میانگین مجموعه کشورها، این همگرایی را تشخیص میدهد. در صورتی که مقدار شباهت میانگین مجموعه کشورهای موجود از یک حد آستانه () بزرگتر باشد، با اجرای الگوریتم تپه نوردی تکراری، سعی در افزودن تعدادی کشور جدید به مجموعه کشورهای موجود می کند. با توجه به این توضیحات، مهمترین پارامترهایی که الگوریتم ترکیبی پیشنهادی را تحت تأثیر قرار می دهد، مقدار پارامتر حد آستانه می باشد. در این بخش به بررسی تأثیر مقادیر مختلف این پارامتر بر کارایی الگوریتم پیشنهادی از نظر زمان اجرای الگوریتم، کیفیت (هزینه) زمانبندی و زمان همگرایی الگوریتم، می پردازیم. زمان اجرای الگوریتم برابر است با زمان پردازنده برای ۲۰۰ نسل اجرای الگوریتم. کیفیت زمانبندی نیز بر اساس مقدار شایستگی کشور جواب محاسبه می شود که به صورت زیر محاسبه می شود.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

(۵-۱)

که در آن نشان دهنده زمان پایان آخرین کار و نیز نشان دهنده میانگین زمان اجرای تمامی کارها می باشد. زمان همگرایی الگوریتم، زمانی است که مقدار شایستگی امپراتوری بیش از ۰٫۰۰۱ تغییر نکند.
تعداد کشورهای اولیه، برای مسئله FT10برابر با ۱۰۰ کشور، برای مسئله FT20برابر با ۱۵۰، برای مسئله LA40، ۲۰۰ و برای مسئله SWV14 ، ۳۰۰ در نظر گرفته شده است.
شکل های ۵-۱ تا ۵-۴ نتیجه اجرای الگوریتم پیشنهادی برای مقادیر مختلف را به تصور کشیده است.

شکل۵-۱: تغییرات هزینه، زمان و همگرایی نسبت به مقدار حد آستانه برای مسئله FT10(شکل ها از سمت راست به چپ مرتب هستند)

شکل ۵-۲: تغییرات هزینه، زمان و همگرایینسبتبهمقدارحدآستانهبرایمسئلهFT20

شکل ۵-۳: تغییراتتغییرات هزینه، زمان و همگرایی نسبت بهمقدارحدآستانهبرایمسئلهLA40

شکل ۵-۴: تغییراتتغییرات هزینه، زمان و همگرایینسبتبهمقدارحدآستانهبرایمسئلهSWV14
نتایجی که از شکل های ۵-۱ تا ۵-۴ می توان گرفت عبارتند از:
الگوریتم پیشنهادی بهترین کم هزینه ترین جواب ها را برای مقادیر به دست می آورد. هر چه مقدار این حد آستانه به صفر نزدیکتر باشد، فرکانس فراخوانی های جستجوی محلی بیشتر بوده و در نتیجه، گامهای تصادفی در الگوریتم افزایش خواهد یافت. افزایش گامهای تصادفی باعث کاهش احتمال همرایی الگوریتم می شود و در نتیجه الگوریتم پیشنهادی برای مقادیر کوچک حد آستانه، جواب مناسبی را پیدا نمی کند. از طرفی دیگر، هر چه مقدار حد آستانه به یک نزدیکتر باشد، فرکانس فراخوانی های جستجوی محلی کاهش پیدا کرده و در نتیجه الگوریتم پیشنهادی شبیه به یک الگوریتم رقابت استعماری ساده عمل می کند.