Research Output

The Importance of the Individual Encoding in Memetic Algorithms with Diversity Control Applied to Large Sudoku Puzzles

  In recent years, several memetic algorithms with explicit mechanisms to delay convergence have shown great promise when solving 9x9 Sudoku puzzles. This paper analyzes and extends state-of-the-art schemes for dealing with Sudoku puzzles of larger dimensionality. Two interesting aspects are analyzed: the importance of the encoding and its relation with the way of managing the diversity. Specifically, three different ways of encoding the individuals and six different methods, including four that control the diversity in a special way, are studied. Computational results are shown with twenty 16x16 Sudoku puzzles. Contrary to the low-dimensional case, important differences appear among the several ways of controlling diversity. Specifically, a method that incorporates multi-objective concepts in the replacement phase to deal with the diversity, resulted in the most promising method. Results show that both the encoding and the way of managing diversity are crucial to attain high success probabilities in large Sudoku puzzles. They also show that, while the analyzed encodings induce different search space sizes, this feature is not enough to justify the differences in the performance attained by them.

  • Date:

    07 July 2017

  • Publication Status:

    Published

  • Publisher

    Institute of Electrical and Electronics Engineers

  • DOI:

    10.1109/CEC.2017.7969565

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    004 Data processing & computer science

  • Funders:

    Edinburgh Napier Funded

Citation

Segura, C., Segredo, E., & Miranda, G. (2017). The Importance of the Individual Encoding in Memetic Algorithms with Diversity Control Applied to Large Sudoku Puzzles. In 2017 IEEE Congress on Evolutionary Computation (CEC)doi:10.1109/CEC.2017.7969565

Authors

Copyright

© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works

Keywords

Sudoku, memetic algorithms, convergence,

Monthly Views:

Available Documents