Basic and Hybrid Imperialist Competitive Algorithms for Solving the n-Queens Problem

Ellips Masehian, Nasrin Mohabbati-Kalejahi, Hossein Akbaripour

2012

Abstract

The n-queens problem is a classical combinatorial optimization problem which has been proved to be NP-hard. The goal is to place n non-attacking queens on an n×n chessboard. In this paper, the Imperialist Com-petitive Algorithm (ICA), which is a recent evolutionary metaheuristic method, has been applied for solving the n-queens problem. As another variation, the ICA was combined with a local search method, resulting the Hybrid ICA (HICA). Extensive experimental results showed that the proposed HICA outperformed the basic ICA in terms of average runtimes and average number of fitness function evaluations. The developed algorithms were also compared to the Cooperative PSO (CPSO) algorithm, which is currently the best algo-rithm in the literature for finding the first valid solution to the n-queens problem, and the results showed that the HICA dominates the CPSO by evaluating the fitness function fewer times.

Paper Citation

in Harvard Style

Masehian E., Mohabbati-Kalejahi N. and Akbaripour H. (2012). Basic and Hybrid Imperialist Competitive Algorithms for Solving the n-Queens Problem . In Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012) ISBN 978-989-8565-33-4, pages 87-95. DOI: 10.5220/0004160900870095

in Bibtex Style

@conference{ecta12,
author={Ellips Masehian and Nasrin Mohabbati-Kalejahi and Hossein Akbaripour},
title={Basic and Hybrid Imperialist Competitive Algorithms for Solving the n-Queens Problem},
booktitle={Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012)},
year={2012},
pages={87-95},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004160900870095},
isbn={978-989-8565-33-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012)
TI - Basic and Hybrid Imperialist Competitive Algorithms for Solving the n-Queens Problem
SN - 978-989-8565-33-4
AU - Masehian E.
AU - Mohabbati-Kalejahi N.
AU - Akbaripour H.
PY - 2012
SP - 87
EP - 95
DO - 10.5220/0004160900870095