Scott H. Clearwater and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@ARTICLE {,
AUTHOR = "Scott H. Clearwater and Tad Hogg",
TITLE = "Problem Structure Heuristics and Scaling Behavior for Genetic Algorithms",
JOURNAL = "Artificial Intelligence",
VOLUME = "81",
PAGES = "327-347",
YEAR = "1996"}
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.
postcript (808K, available on-line only within Xerox)