ارائه راهکاری جدید برای حل مسئله n-وزیر به کمک الگوریتم‌های ژنتیک موازی

فصلنامه مدیریت راهبردی در سیستم های صنعتی (مدیریت صنعتی سابق)

مقاله 6، دوره 12، شماره 42، اسفند 1396، صفحه 75-86   

نوع مقاله: مقاله پژوهشی

نویسندگان

منیره طاهری سروتمین^* ؛ عمید خطیبی بردسیری

گروه مهندسی کامپیوتر، واحد کرمان، دانشگاه آزاد اسلامی، کرمان، ایران

چکیده

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

کلیدواژه‌ها

الگوریتم‌های ژنتیک موازی؛ الگوریتم ژنتیک جزیره‌ای؛ الگوریتم ژنتیک سلولی؛ مسئله n-وزیر

مراجع

1-      Agarwal, K., Sinha, A., & Bindu, M. H. (2012). A novel hybrid approach to N-queen problem, Advances in Computer Science, Engineering & Applications, pp. 519-527. Springer

2-      Ahrabian, H., Mirzaei, A., & Nowzari-Dalini, A. (2008). A DNA Sticker Algorithm for Solving N-Queen Problem. IJCSA, 5(2): 12-22.

3-      Alba, E. (2002). Parallel evolutionary algorithms can achieve super-linear performance. Information Processing Letters, 82(1): 7-13.

4-      Alba, E., & Troya, J. M. (1999). A survey of parallel distributed genetic algorithms. Complexity, 4(4): 31-52.

5-      Bashir, L. Z., & Mahdi, N. (2015). Use Genetic Algorithm in Optimization Function For Solving Queens Problem. World Scientific News, 11, 138-150.

6-      Božikovic, M., Golub, M., & Budin, L. (2003). Solving n-Queen problem using global parallel genetic algorithm. Paper presented at the International Conference on Computer as a tool EUROCON 2003.

7-      Dash, S. R., Dehuri, S., & Rayaguru, S. (2013). Discovering interesting rules from biological data using parallel genetic algorithm. Paper presented at the Advance Computing Conference (IACC), 2013 IEEE 3rd International.

8-      El-Qawasmeh, E., & Al-Noubani, K. (2004). A Polynomial Time Algorithm for the N-Queens Problem. Paper presented at the IASTED International Conference on Neural Networks and Computational Intelligence.

9-      Farhan, A. S., Tareq, W. Z., & Awad, F. H. (2015). Solving N Queen Problem using Genetic Algorithm. International Journal of Computer Applications, 122(12).

10-  Hu, N. (2016). An Integer Coding Based Optimization Model for Queen Problems. American Journal of Computational Mathematics, 6(1): 32.

11-  Hu, X., Eberhart, R. C., & Shi, Y. (2003). Swarm intelligence for permutation optimization: a case study of n-queens problem. Paper presented at the Swarm intelligence symposium, 2003. SIS'03. Proceedings of the 2003 IEEE.

12-  Kacprzyk, J., & Pedrycz, W. (2015). Springer handbook of computational intelligence: Springer.

13-  Khan, S., Bilal, M., Sharif, M., Sajid, M., & Baig, R. (2009). Solution of n-queen problem using aco. Paper presented at the Multitopic Conference, 2009. INMIC 2009. IEEE 13th International.

14-  Mandziuk, J. (1995). Solving the n-queens problem with a binary Hopfield-type network. Synchronous and asynchronous model. Biological Cybernetics, 72(5): 439-446.

15-  Mihaylova, P., & Brandisky, K. (2006). Parallel genetic algorithm optimization of die press. Paper presented at the Proc. of 3rd International PhD Seminar “Computational Electromagnetics And Technical Applications.

16-  Mohabbati-Kalejahi, N., Akbaripour, H., & Masehian, E. (2015). Basic and Hybrid Imperialist Competitive Algorithms for Solving the Non-attacking and Non-dominating n-Queens Problems Computational Intelligence, pp. 79-96. Springer.

17-  Ohta, M. (2002). Chaotic neural networks with reinforced self-feedbacks and its application to N-Queen problem. Mathematics and computers in simulation, 59(4): 305-317.

18-  Sharma, G., & Martin, J. (2009). MATLAB®: a language for parallel computing. International Journal of Parallel Programming, 37(1): 3-36.

19-  Soufan, O., Kleftogiannis, D., Kalnis, P., & Bajic, V. B. (2015). DWFS: a wrapper feature selection tool based on a parallel genetic algorithm. PloS one, 10(2), e0117988.

20-  Yu, B., Yang, Z., Sun, X., Yao, B., Zeng, Q., & Jeppesen, E. (2011). Parallel genetic algorithm in bus route headway optimization. Applied Soft Computing, 11(8): 5081-5091.