Sudoku solution using a genetic algorithm

Question

I took on the task of creating a sudoku solver using a genetic algorithm.

Initialization . Save the setpoints on each chromosome, and then randomly generate such values ​​so that each row is a real permutation of the values ​​from 1 to 9.

Fitness : determined by the number of “out of place” values ​​in each row, column, and square grid added together.

Fitness function : typical roulette wheel selection

Choice : random, but weighted using a roulette wheel.

Crossover : randomly select different lines from two parents who create one child. (I also implemented a crossover that randomly selects 3 rows at a time from two parents - to maintain good mini grids). The following are two examples of children, one from each crossover method:

Parent 1 row 1 Parent 2 row 2 Parent 1 row 3 Parent 2 row 4 Parent 1 row 5 Parent 2 row 6 Parent 2 row 7 Parent 1 row 8 Parent 1 row 9 Parent 1 row 1 Parent 1 row 2 Parent 1 row 3 Parent 2 row 4 Parent 2 row 5 Parent 2 row 6 Parent 1 row 7 Parent 1 row 8 Parent 1 row 9 

Mutation . Initially, I simply swapped values ​​in two random places, but this actually made the algorithm much worse, because it introduced duplicates in strings that were real permutations. So I changed the mutation (which seems to work best when the mutation probability is in the range of 25% - 50%) to randomly select a row and then randomize the ordering of that row (leaving the given values ​​in their correct places).

I also tried a mutation, where I selected a random line, and then selected two random (undefined) positions in the line and changed them, but this also greatly degraded performance. (Unlike sharing two random locations, I don’t understand why this mutation will make the job much worse, but the mutation to randomize the entire line improves performance)

My algorithm has yet to solve the riddle of any complexity. Often it will be close (in the range of 6 to 10 conflicts), but it will never be able to get to a solution (it seems to detect local minima and get stuck).

In order to improve the algorithm, I added the ability to replace most of the population (the worst chromosomes) with completely randomized boards, but this seems to have minimal effect.

What are the weaknesses in my approach? How to increase productivity?

It seems that Sudoku can bring better mutation performance, as opposed to crossover.

Answer 1

I solved some sudoku puzzles using GA using this approach: http://fendrich.se/blog/2010/05/05/solving-sudoku-with-genetic-algorithms/

Sudoku has many false local minima, so it’s important to maintain a diverse population. Do not go too eagerly. This is the key to many difficult problems. Get off very slowly.

I do not like the choice of a roulette wheel. This is a toy that converges too quickly and is too dependent on the fitness function. For example, you can choose a tournament.

I agree that the crossover is difficult to apply. You can consider it as a kind of large mutation, which, as it turned out, is a crossover.

Answer 2

The best strategy I know to solve soduko programmatically is to use the Boolean feasibility problem.