ارائه راهكاري جديد براي حل مسئله n-وزير به كمك الگوريتم هاي ژنتيك موازي

Solving N-Queen Problem Using Global Parallel Genetic Algorithm

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

Great efforts were made to solve uncertain hybrid optimization problems in the past few decades. The n-Queen problem is one of these problems that many solutions have been proposed for. The traditional methods to solve this problem are exponential in terms of runtime and are not acceptable in terms of space and memory complexity. In this study, parallel genetic algorithms are proposed to solve n-Queen problem. Parallelizing island genetic algorithm and the Cellular genetic algorithm was implemented and run. The results show that this algorithm has the ability to find related solutions to this problem. The algorithms are not only faster but also they lead to better performance even without the use of parallel hardware and just running on one core processor. Good comparisons were made between the proposed method and serial genetic algorithms in order to measure the performance of the proposed method. The experimental results show that the algorithm has high efficiency for large-size problems in comparison with genetic algorithms, and, in some cases, it can achieve superlinear speedup. The proposed method, in the present study, can be easily developed to solve other optimization problems.