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

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

کلیدواژه ها:

الگوریتم ژنتیک ، الگوریتم جستجوی ممنوعه ، الگوریتم موازی ممتیکی ، واحد پردازش گرافیکی ، کودا ، مسئله تخصیص درجه دوم ، پردازش موازی