مثالی از مسئله زمان‌بندی با، شمای کلی رقابت استعماری، الگوریتم رقابت استعماری

 

شکل ۳-۹ مثالی از مسئله زمان‌بندی با ۹ وظیفه و ۳ منبع ۴۴
شکل ۳-۱۰ : وضعیت نهایی الگوریتم ICA و ترکیبی ۴۶
شکل ۳-۱۱ – تغییراتی که در حرکت مستعمره ها به سمت استعمارگرها ایجاد می شوند. ۴۷
شکل ۳-۱۲ فرایند تعویض امپریالیستها و کشورهای مستقل ۴۸
شکل ۳-۱۳: شمای کلی رقابت استعماری: امپراطوری‌های بزرگ‌تر، با احتمال بیشتری، مستعمرات امپراطوری‌های دیگر را تصاحب می‌کنند. ۴۹
شکل ۳-۱۴: سقوط امپراطوری‌ ضعیف؛ امپراطوری شماره ۴، به علت از دست دادن کلیه مستعمراتش، دیگر قدرتی برای رقابت ندارد و باید از میان بقیه امپراطوری‌ها حذف شود. ۵۱
شکل ۴-۱ زمان برگشت برای الگوریتمهای مختلف ۵۸
شکل ۴-۲ زمان برگشت برای حالت (۱۰ و ۲۰۰ و ۵۰ ) و تکرارهای ۱۰۰ و ۲۰۰ و ۳۰۰ ۵۹
شکل ۴-۳ زمان اجرا برای حالت (۱۰ و ۲۰۰ و ۵۰ ) و تکرارهای ۱۰۰ و ۲۰۰ و ۳۰۰ ۶۰
شکل ۴-۴ زمان های اجرا برای ۵۰ وظیفه با ۳۰۰ تکرار ۶۰
شکل ۴-۵ زمان برگشت برای وظایف متنوع جمعیت ۵۰ تا تکرار ۱۰۰ بار و تعداد منابع ۱۰ تا ۶۱
فهرست جداول
عنوان شماره صفحه
جدول ۳-۱ تنظیم نرخ تحول ۴۷
جدول ۴-۱ تنظیمات ده منبع پردازشی نمونه ۵۴
جدول ۴-۲ مقادیر تعیین شده برای الگوریتمها ۵۴
جدول ۴-۳ ارزیابی مقادیر زمان برگشت ۵۶
جدول ۴-۴ ارزیابی زمان های اجرای الگوریتمها ۵۷
چکیده
گرید محاسباتی به معنای همکاری منابع توزیع‌شده جغرافیایی در حل مسائل بزرگ می‌باشد. زمان‌بندی در گرید محاسباتی برای انواع سیستم‌هایی که به عنوان سیستم‌های دفاعی و امنیتی هستند و موبایل و سیستم‌های آزمایشگاهی پزشکی که متمرکز نیستند، از اهمیت بالایی برخوردار است. از الگوریتم‌های قطعی برای بالا بردن کیفیت زمان‌بندی نمی‌توان استفاده کرد زیرا زمان‌بندی در گرید محاسباتی یک مسئله غیرقطعی است. الگوریتم ژنتیک، رقابت استعماری، ازدحام ذرات، تپه نوردی از روش‌های غیرقطعی در بهبود زمان‌بندی در گرید می‌باشند. در این تحقیق با مقایسه کردن و بررسی الگوریتم‌های ذکرشده مزایا و معایب آن‌ ها اقدام به ادغام و ترکیب نقاط قوت این الگوریتم‌ها بر پایه الگوریتم رقابت استعماری استفاده نموده‌ایم. زمان‌بندی وظایف مسئله‌ای مستقل است که شامل n وظیفه و m ماشین می‌باشد و هر وظیفه باید با هر یک از ماشین‌ها مورد پردازش قرار بگیرد طوری که زمان انجام کار کمینه شود. الگوریتم رقابت استعماری پایه برای مقادیر حقیقی و فضاهای پیوسته تعریف‌شده است درصورتی‌که زمان‌بندی وظایف گسسته باشد، بدین منظور الگوریتم رقابت استعماری را با الگوریتم‌های ژنتیک و ازدحام ذرات، ترکیب نموده‌ایم و به حالت فضای گسسته مبدل کردیم.الگوریتم ترکیبی را با افزودن گروهی به نام کشورهای مستقل بررسی کردیم. علی‌رغم ایده اصلی الگوریتم رقابت استعماری که مبتنی بر استعمارگر و کلونی (مستعمره) است، یک گروه از کشورهای بی‌طرف و صلح‌آمیز در اینجا در نظر گرفته‌شده‌اند. این کشورها متحده هستند و با بهره گرفتن از هوش ازدحامی با همدیگر ارتباط برقرار می‌کنند.
کلمات کلیدی:
گریدهای محاسباتی، زمان‌بندی وظایف مستقل، الگوریتم‌های تکاملی، رقابت استعماری، الگوریتم ترکیبی