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

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.

• Vahid Mohammadi Saffarzadeh
• Pourya Jafarzadeh
• Masoud Mazloom

• PSO
• SA
• N-queen
• CSP

[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.