Product geometric crossover for the Sudoku puzzle

Alberto Moraglio, Julian Togelius, Simon Lucas

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publication2006 IEEE Congress on Evolutionary Computation, CEC 2006
    Pages470-476
    Number of pages7
    StatePublished - 2006
    Event2006 IEEE Congress on Evolutionary Computation, CEC 2006 - Vancouver, BC, Canada
    Duration: Jul 16 2006Jul 21 2006

    Publication series

    Name2006 IEEE Congress on Evolutionary Computation, CEC 2006

    Other

    Other2006 IEEE Congress on Evolutionary Computation, CEC 2006
    CountryCanada
    CityVancouver, BC
    Period7/16/067/21/06

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Theoretical Computer Science

    Fingerprint Dive into the research topics of 'Product geometric crossover for the Sudoku puzzle'. Together they form a unique fingerprint.

  • Cite this

    Moraglio, A., Togelius, J., & Lucas, S. (2006). Product geometric crossover for the Sudoku puzzle. In 2006 IEEE Congress on Evolutionary Computation, CEC 2006 (pp. 470-476). [1688347] (2006 IEEE Congress on Evolutionary Computation, CEC 2006).