Coevolutionary Learning

We are studying the effectiveness and dynamics of coevolutionary learning. Coevolutionary learning is an adaptive computational technique, related to genetic algorithms, in which a population of learners coevolves with a population of training examples, in order to evolve training examples that are optimally challenging for evolving learners at different stages of evolution. We have shown that some previously reported results on coevolution in the evolutionary computation literature can largely be explained as a result of a technique called ``resource sharing'' rather than coevolution, but that coevolution on a spatial lattice has a highly significant advantage over evolution, resource sharing, and other evolutionary methods (see Figure 1). We are continuing to study the effects of spatial distirbution on coevolution between populations.

Figure 1: Percentage of successful runs (out of 50 or more independent runs) for each of eight different learning methods, as applied to the one-dimensional "density-classification" task for cellular automata. The eight methods are: spatial coevolution, non-spatial coevolution, spatial evolution, non-spatial evolution, spatial resource sharing, non-spatial resource sharing, boosting GAs, and voting GAs.

Figure 2: Left: Diversity in population (measured in terms of proportion of individuals that implement different types of strategies) as a function of generation in a typical run of spatial coevolution. Right: Same as on the left, but for a typical run of non-spatial coevolution.

Publications from this Project:

1. Mitchell, M. (2006). Coevolutionary learning with spatially distributed populations. In G. Y. Yen and D. B. Fogel (editors), Computational Intelligence: Principles and Practice. New York: IEEE Computational Intelligence Society.


2. Mitchell, M., Thomure, M. D., and Williams, N. L. (2006). The role of space in the success of coevolutionary learning. In In L. M. Rocha et al. (editors), Artificial Life X: Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems, pp. 118--124. Cambridge, MA: MIT Press.


3. Williams, N. and Mitchell, M. (2005). Investigating the success of spatial coevolutionary learning. In H. G. Beyer et al. (editors), Proceedings of the 2005 Genetic and Evolutionary Computation Conference, GECCO-2005, New York: ACM Press, 523-530.


4. Williams, N. (2004). Exploring coevolutionary learning. Masters Thesis, OGI School of Science and Engineering, Oregon Health & Science University.


5. Pagie, L. and Mitchell, M. (2002). A comparison of evolutionary and coevolutionary search. International Journal of Computational Intelligence and Applications, 2(1), 53-69.


6. Werfel, J., Mitchell, M., and Crutchfield, J. P. (2000). Resource sharing and coevolution in evolving cellular automata. IEEE Transactions on Evolutionary Computation, 4(4), 388-393.