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

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

No abstract