search

giacomelli / GeneticSharp

GeneticSharp is a fast, extensible, multi-platform and multithreading C# Genetic Algorithm library that simplifies the development of applications using Genetic Algorithms (GAs).
MIT License
1.26k stars 330 forks source link

Sudoku Optimizations #80

Closed jsboige closed 3 years ago

jsboige commented 3 years ago

Those are optimizations to the Sudoku chromosomes accounting for the initial constraints from the sudoku to solve. All Sudoku chromosome reach faster convergence with lower population numbers

giacomelli commented 3 years ago

Thanks for the improvement!

Is this pull request related to issue #47 ?

jsboige commented 3 years ago

Actually, it is more of a cleanup and an optimization providing a workaround for yet not directly addressing issue #47 and the corresponding discussion. By applying a simple round of constraint propagation from the sudoku mask, the search space is significantly reduced, allowing for a gain of an order of magnitude without any significant init time impact, but the problem seems to remain that I wasn't able to trigger lateral exploration past 50 generations. I believe this might be an issue to investigate with the library itself, with Elite selection and Elite reinsertion consistently yielding better results.