The importance of the individual encoding in memetic algorithms with diversity control applied to large Sudoku puzzles

Segura, Carlos; Segredo, Eduardo; Miranda, Gara

Abstract

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.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 2017 IEEE Congress on Evolutionary Computation (CEC)
• Start Date: Jun 5, 2017
• End Date: Jun 8, 2017
• Acceptance Date: Mar 8, 2017
• Online Publication Date: Jul 7, 2017
• Publication Date: Jul 7, 2017
• Deposit Date: Mar 9, 2017
• Publicly Available Date: Mar 9, 2017
• Publisher: Institute of Electrical and Electronics Engineers
• Book Title: 2017 IEEE Congress on Evolutionary Computation (CEC)
• ISBN: 9781509046010
• DOI: https://doi.org/10.1109/CEC.2017.7969565
• Keywords: Sudoku, memetic algorithms, convergence,
• Public URL: http://researchrepository.napier.ac.uk/Output/809701
• Contract Date: Mar 9, 2017