Improve Sudoku evolution to allow for lower population sizes about geneticsharp HOT 6 CLOSED

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

from geneticsharp.

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.

from geneticsharp.

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

from geneticsharp.

@jsboige another question:

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

from geneticsharp.

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.

from geneticsharp.

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.

from geneticsharp.