- author = "Stephen Margetts",
- title = "Adaptive Genotype to Phenotype Mappings for Evolutionary Algorithms",
- school = "Department of Computer Science, Cardiff University",
- year = "2001",
- address = "UK",
- month = may,
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://www.cs.cf.ac.uk/user/Antonia.J.Jones/Theses/SMargettsThesis.pdf",
- size = "251 pages",
-
abstract = "This thesis investigates the notion of an adaptive
genotype to phenotype mapping in an evolutionary
algorithm.
We start by defining an abstract framework for evolutionary search which highlights the similarities and differences between evolutionary algorithms. Studying this framework leads us to the idea that an evolutionary algorithm can be specified without defining the structures which make up its genotype and phenotype. Such algorithms are useful as they can be applied to many different problem domains with very little modification.
To compare and test this type of algorithm, we construct an abstract problem generator which can be used to create test problems for a wide variety of phenotypes. To help us compare different evolutionary algorithms, we also develop a number of statistics which enable us to efficiently extract useful information from a running evolutionary algorithm.
We then use the abstract framework to identify an interesting possibility for an adaptive evolutionary algorithm: an algorithm which has an adaptive mapping function from genotype to phenotype. We develop a general framework for this concept which involves the co-evolution of a population of mappings with a population of structures to which the mappings are applied.
To test this idea, we implement an adaptive genetic algorithm and an adaptive genetic programming system. We evaluate these adaptive algorithms by running comparative experiments against several standard evolutionary algorithms, using both artificially generated and real world problems. Although the improvements are perhaps are not as impressive as we might have hoped, we are able to show that our adaptive algorithms are at least as effective as their non-adaptive counterparts.",
-
notes = "1.7 Contributions of this Work This thesis makes five
main contributions:
1. Showing that we can construct generic evolutionary algorithms (chapters 3 and 6). Such algorithms are specified without identifying the structures to be used as genotypes and phenotypes, and so can be used in a wide range of problem domains.
2. Demonstrating that the mapping between the genotype and phenotype affects performance of an evolutionary algorithm (chapter 6). We develop the notion of a phlegmatic genotype to phenotype mapping, which constrains the mapping such that changes to a genotype generate similar changes to its corresponding phenotype. This minimises the impact of the mapping on the performance of the algorithm.
3. Motivating and investigating evolutionary algorithms with adaptive genotype to phenotype mappings (chapters 6 and 7). We develop a generic model for constructing evolutionary algorithms with adaptive genotype to phenotype mappings. We demonstrate this model using genetic algorithms for real-valued function optimisation, and with developmental genetic programming.
4. Developing a framework for the generation of optimisation problems (chapter 4). This framework is easily adapted to wide variety of common representations such as lists, strings, trees and graphs. The user of the problem generator specifies the position and fitness of the optima in the search landscape, and so can control the difficulty of the problem. In addition, as the optima are known explicitly, a solution can be assessed for quality directly.
5. Developing population statistics based on near neighbour distances (chapter 5). By calculating a small number of near neighbours of an evolving population, we can measure how the population is distributed in the search space. This allows us to determine the diversity of a population directly, instead of using indirect measures based on fitness.
p194 chaotic time series: The Henon Map
p202 Huffman encoding
p218 Future Work
p219 Problem Generation for Genetic Programming
p221 Phlegmatic Mappings for Genetic Programming",
