Competitive Co-evolution
Richard K. Belew, CSE Dept. - UC San Diego and CS Dept. - UW
(Visiting)
Tue. 12 pm Nov. 5 4274 Chamberlin Hall
Many of the most important design problems are difficult
not only because there are a vast number of solutions to
consider, but also because the number of TESTS for potential
solutions is vast as well. We analyze the ``competition
dynamic'' between solutions and tests as it arises in evolutionary
computations: Two distinct populations of ``hosts'' and
``parasites'' are maintained, with increasing reproductive
success of individuals in one population being at the expense of
those in the other. The resulting search is related to the theory
of PAC learning, and several heuristics are demonstrated to
significantly improve the evolutionary algorithm's search
behavior. Game-playing applications are shown to be a very
natural domain for these methods, and some prelimary results
applied to the board game of Go are presented.
This work is based on an upcoming dissertation by Chris Rosin,
CSE/UCSD.