| 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. |
