Solving N-Queen Problem Using Global Parallel Genetic Algorithm

Subject Areas : Industrial Management

Monire Taheri Sarvetamin ¹ , Amid Khatibi Bardsiri ²

1 - Department of Computer Engineering, Islamic Azad University, Kerman, Iran
2 - Department of Computer Engineering, Islamic Azad University, Kerman, Iran

Received: 2017-09-13 Accepted : 2018-01-31 Published : 2018-04-09

Keywords:

Abstract :

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.  

References:

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.