عمید خطیبی بردسیری

در طول چند دهه گذشته تلاش های زیادی برای حل مسائل بهینه سازی ترکیبی غیرقطعی انجام شده است. مسئله n-وزیر یکی از همین مسائل است که تاکنون راه حل های زیادی برای حل این مسئله ارائه شده است. روش های سنتی حل این مسئله از نظر زمان اجرا، به صورت نمایی هستند و ازنظر پیچیدگی نمایی و فضایی قابل قبول نیستند. در مطالعه حاضر الگوریتم های ژنتیک موازی برای حل مسئله n-وزیر پیشنهاد شده است تا راه حل های این مسئله را پیدا کند. موازی سازی الگوریتم ژنتیک جزیره ای و الگوریتم ژنتیک سلولی با استفاده از جعبه ابزار محاسبات موازی متلب پیاده سازی و روی یک سیستم با پردازنده دو هسته ای اجرا شده است. نتایج نشان می دهد که این الگوریتم ها توانایی پیدا کردن راه حل های مربوط به این مسئله را دارند. این الگوریتم ها حتی بدون استفاده از سخت افزار موازی و با اجرا روی یک هستهٔ پردازنده، نه فقط به الگوریتم های سریع تر بلکه به عملکرد بهتر نیز منجر می شوند. مقایسه های خوبی بین روش پیشنهادی و نسخه های سریال الگوریتم ژنتیک برای سنجش عملکرد روش پیشنهادی انجام شده است. نتایج تجربی نشان می دهد این الگوریتم ها در مقایسه با الگوریتم ژنتیک سریال برای اندازه های بزرگ مسئله کارایی بالایی دارند و در برخی موارد می توانند به تسریع فوق خطی دست یابند. روش پیشنهادی این مقاله می تواند به آسانی برای حل دیگر مسائل بهینه سازی توسعه داده شود.