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

E.G. ORTIZ-GARCÍA, S. SALCEDO-SANZ, Á.M. PÉREZ-BELLIDO, L. CARRO-CALVO, A. PORTILLA-FIGUERAS, X. YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

5 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)169-181
Number of pages13
JournalEvolutionary Intelligence
Volume2
Issue number4
Early online date31 Oct 2009
DOIs
Publication statusPublished - Dec 2009
Externally publishedYes

Bibliographical note

This 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.

Keywords

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

Fingerprint

Dive into the research topics of 'Improving the performance of evolutionary algorithms in grid-based puzzles resolution'. Together they form a unique fingerprint.

Cite this