The secondary substrate problem in co-evolution and developmental-evolution
Jordan B. Pollack, Shivakumar Viswanathan · 2007
The performance of an Evolutionary Algorithm on a search problem is critically effected by the substrate used to encode the candidate solutions of the problem. In addition to the challenge of designing evolvable genetic substrates, two-population competitive coevolutionary algorithms (coEAs) and developmental Evolutionary Algorithms (devo-EAs) present another substrate-related design problem. Both involve an additional substrate with its own mechanism of change. In coEAs, test-cases are encoded with an independent genetic substrate having its own variation operators. In devo-EAs, phenotypes are composed of a distinct substrate with associated generative mechanisms capable of changing an individual's form and size during development. Though this “secondary” substrate is a distinctive feature of both algorithms, the design problem it poses remains poorly understood. This dissertation proposes novel formal models to characterize how the properties of the secondary substrate influences the performance devo-EAs and coEAs respectively. Firstly, we propose a computational model for devo-EAs which shows that the point in time at which the development of a phenotype halts can introduce selection biases that can cause an empirically measurable retardation in the performance of a devo-EA. Furthermore, a Genotype-Phenotype map that is bias-free is formally equivalent to a Nash equilibrium in a non-cooperative multi-player game, where each genotype is a player, the possible halting points are strategies and the payoffs are related to the fitness function. We show that algorithmic solutions to find this Nash map are expensive without a suitable secondary substrate. Secondly, we propose a novel search space model for Pareto coevolution that formally defines the evolvability properties required of the secondary substrate for pathology-free learning with a mutation-only coEA. With this model, we show that on boolean classification problems (a) the variational properties of the secondary substrate are a property of the problem class rather than tied to individual problems, and (b) the absence of coevolutionary pathologies does not imply success in finding high-quality solutions. Rather than being mysterious dynamical properties of coEAs, these findings are transparently explained using Machine Learning first principles.