Scott H. Clearwater and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@INPROCEEDINGS {,
AUTHOR = "Scott H. Clearwater and Tad Hogg",
TITLE = "Exploiting Problem Structure in Genetic Algorithms",
BOOKTITLE = "Proc. of 12th Natl. Conf. on AI (AAAI94)",
PAGES = "331-336",
PUBLISHER = "AAAI Press",
ADDRESS = "Menlo Park, CA",
MONTH = "August",
YEAR = "1994"}
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 to improve the performance of genetic algorithms. 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. We also discuss extensions to other types of machine
learning and problem solving systems.
postcript (283K, 6 pages)