TY - GEN
T1 - Product geometric crossover for the Sudoku puzzle
AU - Moraglio, Alberto
AU - Togelius, Julian
AU - Lucas, Simon
PY - 2006
Y1 - 2006
N2 - Geometric crossover is a representation-independent definition of crossover based on the distance of the search space interpreted as a metric space. It generalizes the traditional crossover for binary strings and other important recombination operators for the most used representations. Using a distance tailored to the problem at hand, the abstract definition of crossover can be used to design new problem specific crossovers that embed problem knowledge in the search. In recent work, we have introduced the important notion of product geometric crossover that enables the construction of new geometric crossovers combining preexisting geometric crossovers in a simple way. In this paper, we use it to design an evolutionary algorithm to solve the Sudoku puzzle. The different types of constraints make Sudoku an interesting study case for crossover design. We conducted extensive experimental testing and found that, on medium and hard problems, the new geometric crossovers perform significantly better than hill-climbers and mutations alone.
AB - Geometric crossover is a representation-independent definition of crossover based on the distance of the search space interpreted as a metric space. It generalizes the traditional crossover for binary strings and other important recombination operators for the most used representations. Using a distance tailored to the problem at hand, the abstract definition of crossover can be used to design new problem specific crossovers that embed problem knowledge in the search. In recent work, we have introduced the important notion of product geometric crossover that enables the construction of new geometric crossovers combining preexisting geometric crossovers in a simple way. In this paper, we use it to design an evolutionary algorithm to solve the Sudoku puzzle. The different types of constraints make Sudoku an interesting study case for crossover design. We conducted extensive experimental testing and found that, on medium and hard problems, the new geometric crossovers perform significantly better than hill-climbers and mutations alone.
UR - http://www.scopus.com/inward/record.url?scp=34547282598&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34547282598&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:34547282598
SN - 0780394879
SN - 9780780394872
T3 - 2006 IEEE Congress on Evolutionary Computation, CEC 2006
SP - 470
EP - 476
BT - 2006 IEEE Congress on Evolutionary Computation, CEC 2006
T2 - 2006 IEEE Congress on Evolutionary Computation, CEC 2006
Y2 - 16 July 2006 through 21 July 2006
ER -