Solving the n-Queens Problem Using a Tuned Hybrid Imperialist Competitive Algorithm

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 Competitive 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). Since, the parameters of heuristic and metaheuristic algorithms have a great influence on the performance of the search, parameter tuning is used for handling the problems in an efficient manner. Hence, a TOPSIS-based parameters tuning is proposed, which not only considers the number of Fitness Function Evaluations (FFE), but also aims to minimize the running time of the presented heuristics. In order to, investigate the performance of the suggested approach, a computational analysis on the n-queens problem was performed. Extensive experimental results showed that the proposed HICA outperformed the basic ICA in terms of average runtimes and average number of FFE. The developed algorithms were also compared to the Cooperative PSO (CPSO) algorithm, which is currently the best algorithm 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