×

Landscape analysis and efficient metaheuristics for solving the \(n\)-queens problem. (English) Zbl 1287.90057

Summary: 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\times n\) chessboard. In this paper, two single-solution-based (local search (LS) and tuned simulated annealing (SA)) and two population-based metaheuristics (two versions of scatter search (SS)) are presented for solving the problem. Since parameters of heuristic and metaheuristic algorithms have great influence on their performance, a TOPSIS-Taguchi based parameter tuning method is proposed, which not only considers the number of fitness function evaluations, but also aims to minimize the runtime of the presented metaheuristics. The performance of the suggested approaches was investigated through computational analyses, which showed that the local search method outperformed the other two algorithms in terms of average runtimes and average number of fitness function evaluations. The LS was also compared to the cooperative PSO (CPSO) and SA algorithms, which are currently the best algorithms in the literature for finding the first solution to the \(n\)-queens problem, and the results showed that the average fitness function evaluation of the LS is approximately 21 and 8 times less than that of SA and CPSO, respectively. Also, a fitness analysis of landscape for the \(n\)-queens problem is conducted which indicates that the distribution of local optima is uniformly random and scattered over the search space. The landscape is rugged and there is no significant correlation between fitness and distance of solutions, and so a local search heuristic can search a rugged plain landscape effectively and find a solution quickly. As a result, it is statistically and analytically proved that single-solution-based metaheuristics outperform population-based metaheuristics in finding the first solution of the \(n\)-queens problem.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

OEIS; Scatter Search
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Number of ways of placing n nonattacking queens on an n X n board.

References:

[1] Aarts, E.H.L., Lenstra, J.K.: Local Search in Combinatorial Optimization. Wiley, New York (1997) · Zbl 0869.00019
[2] Abramson, B., Yung, M.: Divide and conquer under global constraints: a solution to the N-queens problem. J. Parallel Distrib. Comput. 6(3), 649-662 (1989) · doi:10.1016/0743-7315(89)90011-7
[3] Amooshahi, A.; Joudaki, M.; Imani, M.; Mazhari, N., Presenting a new method based on cooperative PSO to solve permutation problems: a case study of n-queen problem (2011)
[4] Bell, J., Stevens, B.: A survey of known results and research areas for n-queens. Discrete Math. 309, 1-31 (2009) · Zbl 1228.05002 · doi:10.1016/j.disc.2007.12.043
[5] Bezzel, M.: Proposal of 8-queens problem, Berliner Schachzeitung 3, 363 (1848)
[6] Campos, V., Laguna, M., Mart, R.: Context-independent scatter search and tabu search for permutation problems. INFORMS J. Comput. 17, 111-122 (2005) · Zbl 1239.90109 · doi:10.1287/ijoc.1030.0057
[7] Dirakkhunakon, S.; Suansook, Y., Simulated annealing with iterative improvement (2009) · doi:10.1109/ICSPS.2009.61
[8] Draa, A.; Talbi, H.; Batouche, M., A quantum inspired genetic algorithm for solving the N-queens problem, Algiers
[9] Draa, A., Meshoul, S., Talbi, H., Batouche, M.: A quantum-inspired differential evolution algorithm for solving the N-queens problem. Int. Arab J. Inf. Technol. 7, 21-27 (2010)
[10] Erbas, C.; Sarkeshik, S.; Tanik, M. M., Different perspectives of the n-queens problem, 99-108 (1992), New York · doi:10.1145/131214.131227
[11] Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721-741 (1984) · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[12] Glover, F.; Hao, J. K. (ed.); Lutton, E. (ed.); Ronald, E. (ed.); Schoenauer, D. (ed.); Snyers, D. (ed.), A template for scatter search and path relinking, No. 1363, 13-54 (1997)
[13] Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8, 156-166 (1977) · doi:10.1111/j.1540-5915.1977.tb01074.x
[14] Homaifar, A.; Turner, J.; Ali, S., The n-queens problem and genetic algorithms, No. 1, 262-267 (1992) · doi:10.1109/SECON.1992.202348
[15] Hwang, C.L., Yoon, K.: Multiple Attribute Decision Making-Method and Applications, a State-of-the-Art Survey. Springer, New York (1981) · Zbl 0453.90002 · doi:10.1007/978-3-642-48318-9
[16] Jagota, A., Optimization by reduction to maximum clique (1993)
[17] Jones, T.; Forrest, S., Fitness distance correlation as a measure of problem difficulty for genetic algorithms, 184-192 (1995), San Francisco
[18] Jones, T.: Evolutionary algorithms, fitness landscapes and search. PhD thesis, University of New Mexico, Albuquerque, NM (1995)
[19] Kale, L.V.: An almost perfect heuristic for the n non-attacking queens problem. Inf. Process. Lett. 34, 173-178 (1990) · Zbl 0696.68097 · doi:10.1016/0020-0190(90)90156-R
[20] Khan, S.; Bilal, M.; Sharif, M.; Sajid, M.; Baig, R., Solution of n-queen problem using ACO (2009)
[21] Kirkpatrick, S., Gelet, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 621-630 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[22] Kosters, W.: n-queens bibliography. Retrieved May 4 (2012). http://www.liacs.nl/ kosters/nqueens/
[23] Laguna, M., Marti, R.: Scatter Search: Methodology and Implementations in C. Kluwer Academic, Boston (2003) · Zbl 1055.68103 · doi:10.1007/978-1-4615-0337-8
[24] Lionnet, F.J.E.: Question 963. Nouv. Ann. Math., Ser. 2 8, 560 (1869)
[25] Martí, R.; Laguna, M.; Campos, V.; Rego, C. (ed.); Alidaee, B. (ed.), Scatter search vs. genetic algorithms: an experimental evaluation with permutation problems (2004), Dordrecht
[26] Martinjak, I.; Golub, M., Comparison of heuristic algorithms for the N-queen problem, Cavtat, Croatia
[27] Nouraniy, Y., Andresenz, B.: A comparison of simulated annealing cooling strategies. J. Phys. A, Math. Gen. 31, 8373-8385 (1998) · Zbl 0962.82068 · doi:10.1088/0305-4470/31/41/011
[28] Pauls, E.: Das Maximalproblem der Damen auf dem Schachbrete, II, Deutsche Schachzeitung. Organ fur das Gesammte Schachleben 29(9), 257-267 (1874)
[29] Rego, C., Leão, P.: A scatter search tutorial for graph-based permutation problems. Research Paper HCES-10-00, Hearin Center for Enterprise Science, University of Mississippi, MS 38677, USA (2009) · Zbl 1072.90571
[30] Rivin, I., Zabih, R.: A dynamic programming solution to the n-queens problem. Inf. Process. Lett. 41, 253-256 (1992) · Zbl 0768.90082 · doi:10.1016/0020-0190(92)90168-U
[31] Russell, S.J., Norvig, P.: Artificial Intelligence a Modern Approach Prentice-Hall, Englewood Cliffs (1995) · Zbl 0835.68093
[32] Segundo, P.S.: New decision rules for exact search in N-queens. J. Glob. Optim. 51, 497-514 (2011). doi:10.1007/s10898-011-9653-x · Zbl 1229.90171 · doi:10.1007/s10898-011-9653-x
[33] Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences (2012). http://oeis.org/A000170 · Zbl 1274.11001
[34] Sosic, R., Gu, J.: Efficient local search with conflict minimization. IEEE Trans. Knowl. Data Eng. 6E, 661-668 (1994) · doi:10.1109/69.317698
[35] Taguchi, G., Yokoyama, Y.: Taguchi Methods: Design of Experiments. Am. Supplier Inst. Press, Millersburg (1993)
[36] Talbi, E.-G.: Metaheuristics from Design to Implementation. Wiley, Hoboken (2009) · Zbl 1190.90293
[37] Tambouratzis, T.: A simulated annealing artificial neural network implementation of the n-queens problem. Int. J. Intell. Syst. 12, 739-752 (1997) · doi:10.1002/(SICI)1098-111X(199710)12:10<739::AID-INT3>3.0.CO;2-Z
[38] Tong, L.I., Wang, Ch.H., Chen, H.C.: Optimization of multiple responses using principal component analysis and technique for order preference by similarity to ideal solution. Int. J. Adv. Manuf. Technol. 27, 407-414 (2005) · doi:10.1007/s00170-004-2157-9
[39] Wolpert, D.W., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67-82 (1997) · doi:10.1109/4235.585893
[40] Xinchao, Z.: Simulated annealing algorithm with adaptive neighborhood. Appl. Soft Comput. 11, 1827-1836 (2011) · doi:10.1016/j.asoc.2010.05.029
[41] Yang, X.-S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.