- author = "Franz Rothlauf",
- title = "Representations for Evolutionary Algorithms",
- booktitle = "GECCO 2015 Introductory Tutorials",
- year = "2015",
- editor = "Anabela Simoes",
- isbn13 = "978-1-4503-3488-4",
- keywords = "genetic algorithms, genetic programming, grammatical evolution, cartesian genetic programming",
- pages = "345--366",
- month = "11-15 " # jul,
- organisation = "SIGEVO",
- address = "Madrid, Spain",
-
URL = "
http://doi.acm.org/10.1145/2739482.2756593",
-
DOI = "
doi:10.1145/2739482.2756593",
- publisher = "ACM",
- publisher_address = "New York, NY, USA",
-
abstract = "Successful and efficient use of evolutionary
algorithms (EA) depends on the choice of the genotype,
the problem representation (mapping from genotype to
phenotype) and on the choice of search operators that
are applied to the genotypes. These choices cannot be
made independently of each other. The question whether
a certain representation leads to better performing EAs
than an alternative representation can only be answered
when the operators applied are taken into
consideration. The reverse is also true: deciding
between alternative operators is only meaningful for a
given representation.
In EA practice one can distinguish two complementary approaches. The first approach uses indirect representations where a solution is encoded in a standard data structure, such as strings, vectors, or discrete permutations, and standard off-the-shelf search operators are applied to these genotypes. This is for example the case in standard genetic algorithms, evolution strategies, and some genetic programming approaches like grammatical evolution or Cartesian genetic programming. To evaluate the solution, the genotype needs to be mapped to the phenotype space. The proper choice of this genotype-phenotype mapping is important for the performance of the EA search process. The second approach, the direct representation, encodes solutions to the problem in its most natural space and designs search operators to operate on this representation.
Research in the last few years has identified a number of key concepts to analyse the influence of representation-operator combinations on EA performance. Relevant properties of representations are locality and redundancy.
Locality is a result of the interplay between the search operator and the genotype-phenotype mapping. Representations are redundant if the number of phenotypes exceeds the number of possible genotypes. Redundant representations can lead to biased encodings if some phenotypes are on average represented by a larger number of genotypes or search operators favour some kind of phenotypes.
The tutorial gives a brief overview about existing guidelines for representation design, illustrates the different aspects of representations, gives a brief overview of models describing the different aspects, and illustrates the relevance of the aspects with practical examples.
It is expected that the participants have a basic understanding of EA principles.",
- notes = "Also known as \cite{2756593} Distributed at GECCO-2015.",
