A Hybrid Heuristic with TOPSIS-based Parameter Tuning for Solving theN-Queens Problem

The n-queens problem is a classical combinatorial optimization problem that is proved to be NP-hard. In this paper, a simulated annealing-basedheuristic for solving the n-queens problem is presented.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 notonly considers the number of iterations, but also aims to minimize the running time of the presented heuristic. Inorder to investigate the performance of the suggestedapproach, a computational analysis on the n-queens problem is performed. Experimental results showed thatthe average running time and the average number of iterations of the heuristic approach were 10 times faster and 12 times less than the basic simulated annealing search, respectively.

Keywords:

N-Queens problem , Heuristic algorithm , Simulated Annealing , Parameter tuning , TOPSIS