Search, Neutral Evolution, and Mapping in Evolutionary Computing: A Case Study of Grammatical Evolution

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

  author =       "Dominic Wilson and Devinder Kaur",
  title =        "Search, Neutral Evolution, and Mapping in Evolutionary
                 Computing: A Case Study of Grammatical Evolution",
  journal =      "IEEE Transactions on Evolutionary Computation",
  year =         "2009",
  month =        jun,
  volume =       "13",
  number =       "3",
  pages =        "566--590",
  keywords =     "genetic algorithms, genetic programming, grammatical
                 evolution, Cartesian genetic programming, biology
                 computing, data visualisation, evolutionary
                 computation, genomics, grammars, OneMax, deceptive
                 trap, evolutionary computing, genotype visualization,
                 gray transcription, hierarchical if-and-only-if,
                 needle-in-haystack, neutral evolution literature,
                 parity and majority coding, phenotype maps, population
                 diversity, random mutations",
  ISSN =         "1089-778X",
  DOI =          "doi:10.1109/TEVC.2008.2009063",
  abstract =     "We present a new perspective of search in evolutionary
                 computing (EC) by using a novel model for the analysis
                 and visualisation of genotype to phenotype maps. The
                 model groups genes into quotient sets and shows their
                 adjacencies. A unique quality of the quotient model is
                 that it details geometric qualities of maps that are
                 not otherwise easy to observe. The model shows how
                 random mutations on genes make non-random phenotype
                 preferences, based on the structure of a map. The
                 interaction between such mutation-based preferences
                 with fitness preferences is important for explaining
                 population movements on neutral landscapes. We show the
                 widespread applicability of our approach by applying it
                 to different representations, encodings, and problems
                 including grammatical evolution (GE), Cartesian genetic
                 programming, parity and majority coding, OneMax,
                 needle-in-haystack, deceptive trap and hierarchical
                 if-and-only-if. We also use the approach to address
                 conflicting results in the neutral evolution literature
                 and to analyze concepts relevant to neutral evolution
                 including robustness, evolvability, tunneling, and the
                 relation between genetic form and function. We use the
                 model to develop theoretical results on how mapping and
                 neutral evolution affect search in GE. We study the two
                 phases of mapping in GE, these being transcription
                 (i.e., unique identification of genes with integers)
                 and translation (i.e., many-to-one mapping of genotypes
                 to phenotypes). It is shown that translation and
                 transcription schemes belong to equivalence classes,
                 and therefore the properties we derive for specific
                 schemes are applicable to classes of schemes. We
                 present a new perspective on population diversity. We
                 specify conditions under which increasing degeneracy
                 (by increasing codon size) or rearranging the rules of
                 a grammar do not affect performance. It is shown that
                 there is a barrier to nontrivial neutral evolution with
                 the use of the natural transcription with modulo
                 translation combination; a- necessary but not
                 sufficient condition for such evolution is that at
                 least three bits should change on mutation within a
                 single codon. This barrier can be avoided by using gray
                 transcription. We empirically validate some findings.",
  notes =        "also known as \cite{5089888}",

Genetic Programming entries for Dominic Wilson Devinder Kaur