A Hybrid Approach Using Particle Swarm Optimization and Simulated Annealing for N-queen Problem

Authors: Vahid Mohammadi Saffarzadeh, Pourya Jafarzadeh, Masoud Mazloom

Abstract:

This paper presents a hybrid approach for solving nqueen problem by combination of PSO and SA. PSO is a population based heuristic method that sometimes traps in local maximum. To solve this problem we can use SA. Although SA suffer from many iterations and long time convergence for solving some problems, By good adjusting initial parameters such as temperature and the length of temperature stages SA guarantees convergence. In this article we use discrete PSO (due to nature of n-queen problem) to achieve a good local maximum. Then we use SA to escape from local maximum. The experimental results show that our hybrid method in comparison of SA method converges to result faster, especially for high dimensions n-queen problems.

Keywords: PSO, SA, N-queen, CSP

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1063012

References:

[1] Stuart Russell, Peter Norvig, "Artificial Inteligence: A Modern Approach," Constraint Satisfaction Problems, 2nd ed., Pearson Education, Inc, Upper Saddle River, New Jersey, 2003,1995, page: 137.
[2] Xiaohui Hu, Russell C. Eberhart, Yuhui Shi, "Swarm Inteligence for Permutation Optimization: A case Study of n-Queen Problem".
[3] Marko Božikovic, Marin Golub, Leo Budin, "Solving n-Queen problem using global parallel genetic algorithm".
[4] J. Dr'eo, A. P'etrowski, P.Siarry, E.Taillard, "Metaheuristics for Hard Optimization," Some Other Metaheuristics, Springer-Verlag Berlin Heidelberg 2006, pp. 162-166.
[5] Kwang Y.Lee, Mohamed Al-Sharkawi, "Modern Heuristic Optimization Techniques: Theory And Application To Power Systems," Fundamentals of Particle Swarm Optimization Techniques, Willey- Interscience, Hoboken, 2008, pp. 72-79.
[6] Maurice Clerc, "Particle Swarm Optimization," First Formulations, ISTE, United States, 2006, page: 39.
[7] M. Young, The Technical Writer's Handbook. Mill Valley, CA: University Science, 1989.
[8] Kwang Y.Lee, Mohamed Al-Sharkawi, "Modern Heuristic Optimization Techniques: Theory And Application To Power Systems," Preface, Willey-Interscience, Hoboken, 2008, page: xxiv.
[9] J. Dr'eo, A. P'etrowski, P.Siarry, E.Taillard, "Metaheuristics for Hard Optimization," Simulated Annealing, Springer-Verlag Berlin Heidelberg 2006, pp. 25-31.
[10] J. Dr'eo, A. P'etrowski, P.Siarry, E.Taillard, "Metaheuristics for Hard Optimization," Introduction, Springer-Verlag Berlin Heidelberg 2006, page: 8.
[11] Kwang Y.Lee, Mohamed Al-Sharkawi, "Modern Heuristic Optimization Techniques: Theory And Application To Power Systems," Fundamentals of Simulated Annealing, Willey-Interscience, Hoboken, 2008, page(s): 128 and 129.