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