Solving the n-queens problem using a tuned hybrid imperialist competitive algorithm
Joint Authors
Masehian, Ellips
Akbaripour, Husayn
Mohabbati-Kalejahi, Nisrin
Source
The International Arab Journal of Information Technology
Issue
Vol. 11, Issue 6 (30 Nov. 2014)10 p.
Publisher
Publication Date
2014-11-30
Country of Publication
Jordan
No. of Pages
10
Main Subjects
Information Technology and Computer Science
Topics
Abstract EN
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, 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 ex¬perimental 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) algo¬rithm, 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.
American Psychological Association (APA)
Masehian, Ellips& Akbaripour, Husayn& Mohabbati-Kalejahi, Nisrin. 2014. Solving the n-queens problem using a tuned hybrid imperialist competitive algorithm. The International Arab Journal of Information Technology،Vol. 11, no. 6.
https://search.emarefa.net/detail/BIM-380132
Modern Language Association (MLA)
Masehian, Ellips…[et al.]. Solving the n-queens problem using a tuned hybrid imperialist competitive algorithm. The International Arab Journal of Information Technology Vol. 11, no. 6 (Nov. 2014).
https://search.emarefa.net/detail/BIM-380132
American Medical Association (AMA)
Masehian, Ellips& Akbaripour, Husayn& Mohabbati-Kalejahi, Nisrin. Solving the n-queens problem using a tuned hybrid imperialist competitive algorithm. The International Arab Journal of Information Technology. 2014. Vol. 11, no. 6.
https://search.emarefa.net/detail/BIM-380132
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references.
Record ID
BIM-380132