Computational Complexity Analysis of Genetic Programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.7954
- @Misc{Lissovoi:2018:arxiv,
-
author = "Andrei Lissovoi and Pietro Simone Oliveto",
-
title = "Computational Complexity Analysis of Genetic
Programming",
-
howpublished = "arXiv",
-
year = "2018",
-
month = "11 " # nov,
-
keywords = "genetic algorithms, genetic programming",
-
bibsource = "DBLP,
http://dblp.uni-trier.de/db/journals/corr/corr1811.html#abs-1811-04465",
-
URL = "http://arxiv.org/abs/1811.04465",
-
abstract = "Genetic Programming (GP) is an evolutionary
computation technique to solve problems in an
automated, domain-independent way. Rather than
identifying the optimum of a function as in more
traditional evolutionary optimisation, the aim of GP is
to evolve computer programs with a given functionality.
A population of programs is evolved using variation
operators inspired by Darwinian evolution (crossover
and mutation) and natural selection principles to guide
the search process towards better programs. While many
GP applications have produced human competitive
results, the theoretical understanding of what problem
characteristics and algorithm properties allow GP to be
effective is comparatively limited. Compared to
traditional evolutionary algorithms for function
optimisation, GP applications are further complicated
by two additional factors: the variable length
representation of candidate programs, and the
difficulty of evaluating their quality efficiently.
Such difficulties considerably impact the runtime
analysis of GP where space complexity also comes into
play. As a result initial complexity analyses of GP
focused on restricted settings such as evolving trees
with given structures or estimating the quality of
solutions using only a small polynomial number of
input/output examples. However, the first runtime
analyses concerning GP applications for evolving proper
functions with defined input/output behaviour have
recently appeared. In this chapter, we present an
overview of the state-of-the-art.",
-
notes = "journals/corr/abs-1811-04465",
- }
Genetic Programming entries for
Andrei Lissovoi
Pietro S Oliveto
Citations