Improving the performance of evolutionary algorithms in grid-based puzzles resolution

被引：4

作者：

Ortiz-García E.G. ^{[1
]}

Salcedo-Sanz S. ^{[1
]}

Pérez-Bellido Á.M. ^{[1
]}

Carro-Calvo L. ^{[1
]}

Portilla-Figueras A. ^{[1
]}

Yao X. ^{[2
,3
]}

机构：

[1] Department of Signal Theory and Communications, Universidad de Alcalá, Escuela Politécnica Superior, 28871 Madrid, Alcalá de Henares

[2] The Centre for Research in Computational Intelligence and Applications (CERCIA), School of Computer Science, The University of Birmingham, Birmingham

[3] Nature Inspired Computation and Applications Laboratory (NICAL), University of Science and Technology of China, Hefei

来源：

Evolutionary Intelligence | 2009年 / 2卷 / 4期

关键词：

A-priori probabilities of bits; Evolutionary algorithms; Grid-based puzzles; Japanese puzzles; Light-up puzzles;

D O I：

10.1007/s12065-009-0030-3

中图分类号：

学科分类号：

摘要：

This paper proposes several modifications to existing hybrid evolutionary algorithms in grid-based puzzles, using a-priori probabilities of 0/1 occurrence in binary encodings. This calculation of a-priori probabilities of bits is possible in grid-based problems (puzzles in this case) due to their special structure, with the solution confined into a grid. The work is focused in two different grid-based puzzles, the Japanese puzzles and the Light-up puzzle, each one having special characteristics in terms of constraints, which must be taken into account for the probabilities of bit calculation. For these puzzles, we show the process of a-priori probabilities calculation, and we modify the initialization of the EAs to improve their performance. We also include novel mutation operators based on a-priori probabilities, which makes more effective the evolutionary search of the algorithms in the tackled puzzles. The performance of the algorithms with these new initialization and novel mutation operators is compared with the performance without them. We show that the new initialization and operators based on a-priori probabilities of bits make the evolutionary search more effective and also improve the scalability of the algorithms. © 2009 Springer-Verlag.

引用

页码：169 / 181

页数：12

共 23 条

[1] Khoo A., Zubek R., Applying inexpensive AI techniques to computer games, IEEE Intell Syst, 17, 4, pp. 48-53, (2002)
[2] Lucas S.S., Kendall G., Evolutionary computation and games, IEEE Comput Intell Mag, 1, 1, pp. 10-18, (2006)
[3] Kendall G., Parkes A., Spoerer K., A Survey of NP-Complete Puzzles, Int Comput Games Assoc J, 31, 1, pp. 13-34, (2008)
[4] Ortiz-Garcia E., Salcedo-Sanz S., Perez-Bellido A.M., Portilla-Figueras A., Yao X., Solving very difficult Japanese puzzles with a hybrid evolutionary-logic algorithm, Lect Notes Comput Sci, 5361, pp. 360-369, (2008)
[5] Batenburg B., Kosters W., A discrete tomography approach to Japanese puzzles, Proceedings of the Belgian-Dutch Conference on Artificial Intelligence, pp. 243-250, (2004)
[6] Wiggers W., A comparison of a genetic algorithm and a depth first search algorithm applied to Japanese nonograms, Proceedings of the 1st Twente Student Conference on IT, pp. 1-6, (2004)
[7] Salcedo-Sanz S., Portilla-Figueras J., Perez Bellido A., Ortiz-Garcia E., Yao X., Teaching advanced features of evolutionary algorithms using Japanese puzzles, IEEE Trans Edu, 50, 2, pp. 151-155, (2007)
[8] Conceptis Puzzles Inc, (2009)
[9] Ueda N., Nagao T., NP-completeness Results for Nonograms via Parsimonious Reductions, (1996)
[10] Benton J., Snow R., Wallach N., A combinatorial problem associated with nonograms, Linear Algebra Appl, 412, 1, pp. 30-38, (2006)

← 1 2 3 →