A New Approach to Solve N-Queen Problem with Parallel Genetic Algorithm

Subject Areas : Parallel and Distributed Architectures, Algorithms and Systems

Monire Taheri Sarvetamin ¹ , Amid Khatibi ² , Mohammad Hadi Zahedi ³

1 - Department of Computer engineering, Islamic Azad University of Kerman, Kerman, Iran
2 - Computer engineering department, Bardsir branch, Islamic Azad University, Bardsir, IRAN
3 - Faculty of Electrical and Computer Engineering, Khaje Nasir Toosi University of Technology, Tehran, Iran

Received: 2018-04-08 Accepted : 2018-06-05 Published : 2018-05-01

Keywords: Cellular Genetic Algorithm, Parallel Genetic Algorithms, N-Queen Problem, Island Genetic Algorithm,

Abstract :

Over the past few decades great efforts were made to solve uncertain hybrid optimization problems. The n-Queen problem is one of such 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 the n-Queen problem. Parallelizing island genetic algorithm and Cellular genetic algorithm was implemented and run. The results show that these algorithms have 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 super linear speedup. The proposed method in the present study can be easily developed to solve other optimization problems.

References:

[1]    Bashir, L.Z. and N. Mahdi, Use Genetic Algorithm in Optimization Function For Solving Queens Problem. World Scientific News, 2015. 11: p. 138-150.
[2]    Ohta, M., Chaotic neural networks with reinforced self-feedbacks and its application to N-Queen problem. Mathematics and computers in simulation, 2002. 59(4): p. 305-317.
[3]    Hu, X., R.C. Eberhart, and Y. Shi. Swarm intelligence for permutation optimization: a case study of n-queens problem. in Swarm intelligence symposium, 2003. SIS'03. Proceedings of the 2003 IEEE. 2003. IEEE.
[4]    Agarwal, K., A. Sinha, and M.H. Bindu, A novel hybrid approach to N-queen problem, in Advances in Computer Science, Engineering & Applications. 2012, Springer. p. 519-527.
[5]    El-Qawasmeh, E. and K. Al-Noubani. A Polynomial Time Algorithm for the N-Queens Problem. in IASTED International Conference on Neural Networks and Computational Intelligence. 2004.
[6]    Hu, N., An Integer Coding Based Optimization Model for Queen Problems. American Journal of Computational Mathematics, 2016. 6(01): p. 32.
[7]    Mandziuk, J., Solving the n-queens problem with a binary Hopfield-type network. Synchronous and asynchronous model. Biological Cybernetics, 1995. 72(5): p. 439-446.
[8]    Mohabbati-Kalejahi, N., H. Akbaripour, and E. Masehian, Basic and Hybrid Imperialist Competitive Algorithms for Solving the Non-attacking and Non-dominating n-Queens Problems, in Computational Intelligence. 2015, Springer. p. 79-96.
[9]    Ahrabian, H., A. Mirzaei, and A. Nowzari-Dalini, A DNA Sticker Algorithm for Solving N-Queen Problem. IJCSA, 2008. 5(2): p. 12-22.
[10]    Khan, S., et al. Solution of n-queen problem using aco. in Multitopic Conference, 2009. INMIC 2009. IEEE 13th International. 2009. IEEE.
[11]    Farhan, A.S., W.Z. Tareq, and F.H. Awad, Solving N Queen Problem using Genetic Algorithm. International Journal of Computer Applications, 2015. 122(12).
[12]    Božikovic, M., M. Golub, and L. Budin. Solving n-Queen problem using global parallel genetic algorithm. in International Conference on Computer as a tool EUROCON 2003. 2003.
[13]    Dash, S.R., S. Dehuri, and S. Rayaguru. Discovering interesting rules from biological data using parallel genetic algorithm. in Advance Computing Conference (IACC), 2013 IEEE 3rd International. 2013. IEEE.
[14]    Mihaylova, P. and K. Brandisky. Parallel genetic algorithm optimization of die press. in Proc. of 3rd International PhD Seminar “Computational Electromagnetics And Technical Applications. 2006.
[15]    Yu, B., et al., Parallel genetic algorithm in bus route headway optimization. Applied Soft Computing, 2011. 11(8): p. 5081-5091.
[16]    Soufan, O., et al., DWFS: a wrapper feature selection tool based on a parallel genetic algorithm. PloS one, 2015. 10(2): p. e0117988.
[17]    Alba, E. and J.M. Troya, A survey of parallel distributed genetic algorithms. Complexity, 1999. 4(4): p. 31-52.
[18]    Kacprzyk, J. and W. Pedrycz, Springer handbook of computational intelligence. 2015: Springer.
[19]    Alba, E., Parallel evolutionary algorithms can achieve super-linear performance. Information Processing Letters, 2002. 82(1): p. 7-13.
[20]    Sharma, G. and J. Martin, MATLAB®: a language for parallel computing. International Journal of Parallel Programming, 2009. 37(1): p. 3-36.
[21]    Shonkwiler, Ron. "Parallel Genetic Algorithms." In ICGA, pp. 199-205. 1993.
[22]     Martinjak, Ivica, and Marin Golub. "Comparison of heuristic algorithms for the n-queen problem." In Information Technology Interfaces, 2007. ITI 2007. 29th International Conference on, pp. 759-764. IEEE, 2007.
[23]     Heris, Jalal Eddin Aghazadeh, and Mohammadreza Asgari Oskoei. "Modified genetic algorithm for solving n-queens problem." In Intelligent Systems (ICIS), 2014 Iranian Conference on, pp. 1-5. IEEE, 2014.
[24]     Liu, Jing, Weicai Zhong, and Licheng Jiao. "A multiagent evolutionary algorithm for constraint satisfaction problems." IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 36, no. 1 (2006): 54-73.