مجله علوم رایانشی

چکیده مقاله الگوریتم موازی ممتیکی جستجوی ممنوعه برای حل مسئله تخصیص درجه دوم

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