Defining locality as a problem difficulty measure in genetic programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.7964
- @Article{Galvan-Lopez:2011:GPEM,
-
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
performance.",
-
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
Citations