Improve Sudoku evolution to allow for lower population sizes

[jsboige]

As part of a recently merged pull-request, a new sample was added to solve Sudokus. The sample includes several strategies, and the better ones seem successful at solving most Sudokus. However, the only way I figured to ensure the population does not get stuck on a partial solution local maximum is to increase the population size, and that considerably for hard Sudokus. This results approximately in the corresponding metrics:

• Very Easy Sudoku: 250 chromosomes, <1 sec
• Easy Sudoku: 5000 chromosomes, 10 sec
• Medium Sudoku: 100000 chromosomes, 5-10 min
• Hard Sudoku: 300000 chromosomes, 1-2h

This is raises the following questions:

• Can we think of any set of parameters that make the current implementation more efficient?
• How could we explain that other GAs libraries used to tackle the same problem seem able to work with lower populations and yield progresses over higher generation numbers? See for instance this article, that one, or many other implementations on Github.

Some additional thoughts to get started:

• In order to trade population size for generation number, I introduced 2 partially successful alternatives on top of the initial 1 gene = 1 cell and 1 gene = 1 row-permutation strategies:
  1. Multiple Chromosome: I made that one general purpose as part of the Extension project: it evolves an arbitrary number of chromosomes rather than just one by inlining the genes.
  2. Random permutations: Instead of having just one gene per row permutation, I had several genes picked randomly.
• Because of the way Sudokus work, I expect that a 2-points crossover at the 4th and 7th row with permutations (or 27th and 54th gene with 81-cells chromosomes) might somehow help in order to properly isolate "boxes", that is, 3x3 cell groups where digits must differ, additionally to rows and columns.
• However, local maxima are such that it seems nearly impossible to escape one with random mutations once the entire population has commited to a single one. Thus it seems key to avoid such a global collapse and preseve genetic diversity instead. The various texts I ended up adding to the top of the gtk drawing box were meant to assess precisely when the entire population collapses to a single local maximum. They're not too pretty nor helpful otherwise, so feel free to change that part. The collapse to a local maximum usually won't take more than 50 generations.
• Again the only efficient way I found to escape collapsing into a local maximum was to increase the population size according to the search space (a row with 5 cells in an easy Sudoku will allow for 24 legal permutations, whereas a row with no cell in a hard Sudoku will allow for the complete 9!=362880 permutations), but that is akin to simultaneously visiting and collapsing to all local maxima in the same small number of generations, which I don't consider very satisfying.
• Now it might simply be that most generally, crossover won't work with Sudokus, that it any mixture of 2 partially resolved Sudokus will result in a much worse one. Then I would suppose that other libraries are better at escaping local maxima by implementing some kind of tabu search not found in genetic sharp, where they will allow some parts of the population to get away from the initial collapsing genome without repeatedly falling in its attractor.

[giacomelli]

Hi @jsboige, can you point me any of your unit tests that can be used to verify the items below?

Very Easy Sudoku: 250 chromosomes, <1 sec Easy Sudoku: 5000 chromosomes, 10 sec Medium Sudoku: 100000 chromosomes, 5-10 min Hard Sudoku: 300000 chromosomes, 1-2h

[jsboige]

Hi, those tests were not performed in the unit tests but rather manually in the GTK interface: You'll find the corresponding sudokus in the corresponding controller, and they correspond to Sudokus 1-4 loaded by default. I then had to set the population numbers manually. The corresponding unit-test only tests solving the easy sudoku, which it loads from the Test helper.

[giacomelli]

In your tests what option did you use on "Genetics" dropdown?

[giacomelli]

@jsboige another question:

What is the expected fitness value return from SudokuFitness's Evaluate method when a board is resolved?

[jsboige]

In your tests what option did you use on "Genetics" dropdown?

The cells genetics has pretty poor performances as compared to the permutations one, since the search space is much larger with no benefits AFAIK in terms of getting away from local maxima.

@jsboige another question:

What is the expected fitness value return from SudokuFitness's Evaluate method when a board is resolved?

The expected fitness is 0 for a solved Sudoku, (it counts the number of misplaced cells, I believe I placed a dual termination criterion accordingly in the unit tests).

For now, the evolution looks like a single collapse to all the local maxima closest to the initial population without any room for lateral exploration, meaning the only way I found to get to the solution is making sure the initial population is large enough so that the global maxima is reachable during that collapse. IMHO, this makes it an interesting problem to push this Framework's limits in terms of lateral exploration. Now the default parameter are quite aggressive as far as I understand, so with your knowledge of ways to soften that a bit, you might be able to find the right tuning.

Otherwise, what I believe might be missing in order to achieve some better performances and avoid the whole population collapsing to a local maximum is some kind of tabu search for parts of the population to force divergence and diversity.

Have you had a look at https://dev.heuristiclab.com/trac.fcgi/, which seems to be one of the main competing stacks in the .Net ecosystem? They do have those kind of advanced features that might be interesting to add to your Framework.

[giacomelli]

The performance of GeneticSharp has been improved a lot in the latest versions, but probably won't solve the points mentioned by you about sudoku's sample.

I'll close the issue right now, but feel free to re-open it with a PR associated. This PR should add benchmark methods to our BenchmarkDotNet project, This benchmarks should demonstrate the performance of the points you mentioned. Please, in the same PR add the changes (no breaking changes) suggestions to improve the performance on those points.