Problem structure heuristics and scaling behavior for genetic algorithms

Recent empirical and theoretical studies have shown that simple parameters characterizing the structure of many constraint satisfaction problems also predict the cost to solve them, on average. We apply these observations as a heuristic to improve the performance of genetic algorithms for some constraint satisfaction problems. In particular, we use a simple cost measure to evaluate the likely solution difficulty of the different unsolved subproblems appearing in the population. This is used to determine which individuals contribute to subsequent generations and improves upon the traditional direct use of the underlying cost function. As a specific test case, we used the GENESIS genetic algorithm to search for the optimum of a class of random Walsh polynomials and identified the improvement due to this new heuristic. We describe how this improvement depends on the population size and accuracy of the underlying theory. Finally, we discuss extensions to other types of machine learning and problem solving systems.