الگوریتم موازی ممتیکی جستجوی ممنوعه برای حل مسئله تخصیص درجه دوم
نویسندگان
1 دانشگاه شمال
2 دانشگاه تبریز
doi
چکیده
مسئله تخصیص درجه دو یکی از مسائل بهینهسازی ترکیباتی متعلق به ردۀ مسائل سخت بوده که دارای کاربردی وسیع در جایابی تجهیزات، طراحی صفحه کلید، طراحی تخته مدارهای کنترلی و سایر علوم مهندسی است. در این مقاله به بهبود سرعت و کارائی الگوریتم ژنتیک برای حل این مسئله پرداختهمیشود. بدین منظور الگوریتم ممتیکی جستجوی ممنوعه، مطرحشدهاست. جستجوی ممنوعه با ایفای نقش بهعنوان جستجوی محلی باعث افزایش استخراج در فضای جستجو میشود. به همین دلیل از همگرائی زودرس الگوریتم ژنتیک جلوگیری میکند. از طرفی بهمنظور جبران محاسبات ناشی از استفاده جستجوی ممنوعه، از واحد پردازش گرافیکی در بستر کودا برای موازیسازی پردازشها استفادهشدهاست. بهمنظور مقایسه نتایج از مسئله تخصیص درجه دوم با اندازههای مختلف استفادهمیشود. نتایج حاکی از افزایش سرعت اجرای پردازشها تا 13 برابر نسبت به الگوریتم سریال ممتیکی جستجوی ممنوعه است. همچنین به دلیل ترکیب الگوریتم ژنتیک با جستجوی ممنوعه کارائی برای یافتن برازش مسئله، بهبود داشته است.
