Defining locality as a problem difficulty measure in genetic programming

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

  author =       "Edgar Galvan-Lopez and James McDermott and 
                 Michael O'Neill and Anthony Brabazon",
  title =        "Defining locality as a problem difficulty measure in
                 genetic programming",
  journal =      "Genetic Programming and Evolvable Machines",
  year =         "2012",
  volume =       "12",
  number =       "4",
  pages =        "365--401",
  month =        dec,
  keywords =     "genetic algorithms, genetic programming",
  ISSN =         "1389-2576",
  DOI =          "doi:10.1007/s10710-011-9136-3",
  size =         "37 pages",
  abstract =     "A mapping is local if it preserves neighbourhood. In
                 Evolutionary Computation, locality is generally
                 described as the property that neighbouring genotypes
                 correspond to neighbouring phenotypes. A representation
                 has high locality if most genotypic neighbours are
                 mapped to phenotypic neighbours. Locality is seen as a
                 key element in performing effective evolutionary
                 search. It is believed that a representation that has
                 high locality will perform better in evolutionary
                 search and the contrary is true for a representation
                 that has low locality. When locality was introduced, it
                 was the genotype-phenotype mapping in bit string based
                 Genetic Algorithms which was of interest; more
                 recently, it has also been used to study the same
                 mapping in Grammatical Evolution. To our knowledge,
                 there are few explicit studies of locality in Genetic
                 Programming (GP). The goal of this paper is to shed
                 some light on locality in GP and use it as an indicator
                 of problem difficulty. Strictly speaking, in GP the
                 genotype and the phenotype are not distinct. We attempt
                 to extend the standard quantitative definition of
                 genotype-phenotype locality to the genotype-fitness
                 mapping by considering three possible definitions. We
                 consider the effects of these definitions in both
                 continuous- and discrete-valued fitness functions. We
                 compare three different GP representations (two of them
                 induced by using different function sets and the other
                 using a slightly different GP encoding) and six
                 different mutation operators. Results indicate that one
                 definition of locality is better in predicting
  notes =        "Rothlauf. Mutation only (no crossover). Sum of surplus
                 distances. Even-3-parity, even-4-parity (two function
                 sets) Artificial ant \cite{langdon:1998:antspace} (two
                 function sets) two symbolic regression. Uniform GP. Ant
                 negative correlation (r=-.74). Normalised compression
                 distance (Kolmogorov complexity). Size fair, size fair
                 range crossovers \cite{langdon:2000:fairxo} Hoist, one
                 point, subtree, _permutation_ mutations. p388
                 'mutations involving the discontinuous protected
                 division operator' p390 'always a counter example'.",

Genetic Programming entries for Edgar Galvan Lopez James McDermott Michael O'Neill Anthony Brabazon