Dissertation
 
The Design and Analysis of a Computational
Model of Cooperative Coevolution
Mitchell A. Potter
George Mason University, 1997
Thesis Director: Dr. Kenneth A. De Jong
 
Abstract
As evolutionary algorithms are applied to the solution of increasingly complex systems, explicit notions of modularity must be introduced to provide reasonable opportunities for solutions to evolve in the form of interacting coadapted subcomponents. The difficulty comes in finding computational extensions to our current evolutionary paradigms in which such subcomponents ``emerge'' rather than being hand designed. At issue is how to identify and represent such subcomponents, provide an environment in which they can interact and coadapt, and apportion credit to them for their contributions to the problem-solving activity such that their evolution proceeds without human involvement.
We begin by describing a computational model of cooperative coevolution that includes the explicit notion of modularity needed to provide reasonable opportunities for solutions to evolve in the form of interacting coadapted subcomponents. In this novel approach, subcomponents are represented as genetically isolated species and evolved in parallel. Individuals from each species temporarily enter into collaborations with members of the other species and are rewarded based on the success of the collaborations in solving objective functions.
Next, we perform a sensitivity analysis on a number of characteristics of decomposable problems likely to have an impact on the effectiveness of the coevolutionary model. Through focused experimentation using tunable test problems chosen specifically to measure the effect of these characteristics, we provide insight into their influence and how any exposed difficulties may be overcome.
This is followed by a study of the basic problem-decomposition capability of the model. We show, within the context of a relatively simple environment, that evolutionary pressure can provide the needed stimulus for the emergence of an appropriate number of subcomponents that cover multiple niches, are evolved to an appropriate level of generality, and can adapt to a changing environment. We also perform two case studies in emergent decomposition on complex problems from the domains of artificial neural networks and concept learning. These case studies validate the ability of the model to handle problems only decomposable into subtasks with complex and difficult to understand interdependencies.
Downloading the Dissertation
Two PDF versions of this dissertation are available online. One is formatted for printing on both sides of the page and the other is formatted for single-sided printing.  Each of these files is about 2 MB.
  1. PDF formatted for double-sided printing
  2. PDF formatted for single-sided printing
  3.