RT Conference Proceedings
T1 Evolutionary techniques in a constraint satisfaction problem: Puzzle Eternity II
A1 Muñoz, Jorge
A1 Gutiérrez Sánchez, Germán
A1 Sanchis de Miguel, María Araceli
AB This work evaluates three evolutionary algorithms in a constraint satisfaction problem. Specifically, the problem is the Eternity II, a edge-matching puzzle with 256 unique square tiles that have to be placed on a square board of 16 times 16 cells. The aim is not to completely solve the problem but satisfy as many constraints as possible. The three evolutionary algorithms are: genetic algorithm, an own implementation of a technique based on immune system concepts and a multiobjective evolutionary algorithm developed from the genetic algorithm. In addition to comparing the results obtained by applying these evolutionary algorithms, they also will be compared with an exhaustive search algorithm (backtracking) and random search. For the evolutionary algorithms two different fitness functions will be used, the first one as the score of the puzzle and the second one as a combination of the multiobjective algorithm objectives. We also used two ways to create the initial population, one randomly and the other with some domain information.
PB IEEE
SN 978-1-4244-2958-5
YR 2009
FD 2009
LK https://hdl.handle.net/10016/9915
UL https://hdl.handle.net/10016/9915
LA eng
NO Proceeding of: IEEE Congress on Evolutionary Computation (CEC 2009), May 18-21 (Monday - Thursday), 2009, Trondheim, Norway.
NO This work was supported in part by the University Carlos III of Madrid under grant PIF UC3M01-0809 and by the Ministry of Science and Innovation under project TRA2007-67374-C02-02.
DS e-Archivo
RD 20 may. 2024