- author = "Andrei Lissovoi and Pietro S. Oliveto",
- title = "Computational Complexity Analysis of Genetic Programming",
- booktitle = "Theory of Evolutionary Computation",
- publisher = "Springer Nature",
- year = "2020",
- editor = "Benjamin Doerr and Frank Neumann",
- series = "Natural Computing Series",
- chapter = "11",
- pages = "475--518",
- keywords = "genetic algorithms, genetic programming",
- isbn13 = "978-3-030-29413-7",
-
URL = "
https://arxiv.org/abs/1811.04465",
-
URL = "https://doi.org/10.1007/978-3-030-29414-4_11",
-
DOI = "
doi:10.1007/978-3-030-29414-4_11",
- size = "41 pages",
- 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 optimization, the aim of GP is to evolve computer programs with a given functionality. 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 with traditional evolutionary algorithms for function optimization, 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 have focused on restricted settings such as the evolution of trees with given structures or the estimation of solution quality using only a small polynomial number of input/output examples. However, the first computational complexity analyses of GP for evolving proper functions with defined input/output behavior have recently appeared. we present an overview of the state of the art.",
-
notes = "lissovoi2019computational, HVL-Prime
(1+1)-GP RLS-GP, order, majority, bloat control. Sorting, inv, las, ham, exc, run, max. PAC Learning, poly, parity, xor. CGP. Geometric Semantic Genetic Programming (GSGP). 2/3-SuperMajority, Identification
Department of Computer Science, University of Sheffield, UK",
