ارائه راهکاری جدید برای حل مسئله n-وزیر به کمک الگوریتمهای ژنتیک موازی
نویسندگان
1 Department of Computer Engineering, Islamic Azad University, Kerman, Iran
2 Department of Computer Engineering, Islamic Azad University, Kerman, Iran
doi
چکیده
در طول چند دهه گذشته تلاشهای زیادی برای حل مسائل بهینهسازی ترکیبی غیرقطعی انجام شده است. مسئله n-وزیر یکی از همین مسائل است که تاکنون راهحلهای زیادی برای حل این مسئله ارائه شده است. روشهای سنتی حل این مسئله از نظر زمان اجرا، به صورت نمایی هستند و ازنظر پیچیدگی نمایی و فضایی قابل قبول نیستند. در مطالعه حاضر الگوریتمهای ژنتیک موازی برای حل مسئله n-وزیر پیشنهاد شده است تا راهحلهای این مسئله را پیدا کند. موازیسازی الگوریتم ژنتیک جزیرهای و الگوریتم ژنتیک سلولی با استفاده از جعبهابزار محاسبات موازی متلب پیادهسازی و روی یک سیستم با پردازنده دو هستهای اجرا شده است. نتایج نشان میدهد که این الگوریتمها توانایی پیدا کردن راهحلهای مربوط به این مسئله را دارند. این الگوریتمها حتی بدون استفاده از سختافزار موازی و با اجرا روی یک هستهٔ پردازنده، نه فقط به الگوریتمهای سریعتر بلکه به عملکرد بهتر نیز منجر میشوند. مقایسههای خوبی بین روش پیشنهادی و نسخههای سریال الگوریتم ژنتیک برای سنجش عملکرد روش پیشنهادی انجام شده است. نتایج تجربی نشان میدهد این الگوریتمها در مقایسه با الگوریتم ژنتیک سریال برای اندازههای بزرگ مسئله کارایی بالایی دارند و در برخی موارد میتوانند به تسریع فوقخطی دست یابند. روش پیشنهادی این مقاله میتواند به آسانی برای حل دیگر مسائل بهینهسازی توسعه داده شود.
