Guiding Genetic Algorithm via Viral Trait Spreading for Solving Sudoku Puzzle

摘要

Genetic Algorithms work iteratively from generation to generation to find the optimal solution of optimization problems. However, due to the probabilistic operations of Genetic Algorithms (GAs), the performance of GAs search is unpredictable. Even worst, GAs may not be able to find the optimal solution after very long iteration. We propose a solution that incorporates a human intervention to guide GA achieving a better performance. We adopt the Viral Trait Spreading Framework for human intervention in the GA operations. Firstly, we classify GAs operation and then put each group of operation in the Framework. Most of all genetic algorithm operations fall into the Trait Adoption component. We optimized the design of genetic representation and genetic operators to tackle the fixed element constraint and row permutation constraint of Sudoku puzzle. Then, we implemented our approach in net logo, a multiagent programmable modeling environment. Experiment results showed that GA is capable of finding the optimal solution and the human intervention through Viral Trait Spreading Framework guides the GA in searching processes in the narrower search space.