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.
Bibliographical noteThis work has been partially supported by Universidad de Alcalá, Comunidad de Madrid and Ministerio de Educación of Spain under grants number CCG08-UAH/AMB-3993 and TEC2006-07010. E. G. Ortiz-García is supported by Universidad de Alcalá, under the University F.P.I. grants program. Á. M. Pérez-Bellido is supported with a doctoral fellowship by the European Social Fund and Junta de Comunidades de Castilla la Mancha, in the frame of the Operating Programme ESF 2007-2013.
- A-priori probabilities of bits
- Evolutionary algorithms
- Grid-based puzzles
- Japanese puzzles
- Light-up puzzles