Adaptive Genotype to Phenotype Mappings for Evolutionary Algorithms

Created by W.Langdon from gp-bibliography.bib Revision:1.3973

@PhdThesis{margetts:thesis,
  author =       "Stephen Margetts",
  title =        "Adaptive Genotype to Phenotype Mappings for
                 Evolutionary Algorithms",
  school =       "Department of Computer Science, Cardiff University",
  year =         "2001",
  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",
}

Genetic Programming entries for Steve Margetts

Citations