Evolving Boolean functions with conjunctions and disjunctions via genetic programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.7970
- @InProceedings{Doerr:2019:GECCOb,
-
author = "Benjamin Doerr and Andrei Lissovoi and
Pietro S. Oliveto",
-
title = "Evolving {Boolean} functions with conjunctions and
disjunctions via genetic programming",
-
booktitle = "GECCO '19: Proceedings of the Genetic and Evolutionary
Computation Conference",
-
year = "2019",
-
editor = "Manuel Lopez-Ibanez and Thomas Stuetzle and
Anne Auger and Petr Posik and Leslie {Peprez Caceres} and
Andrew M. Sutton and Nadarajen Veerapen and
Christine Solnon and Andries Engelbrecht and Stephane Doncieux and
Sebastian Risi and Penousal Machado and
Vanessa Volz and Christian Blum and Francisco Chicano and
Bing Xue and Jean-Baptiste Mouret and Arnaud Liefooghe and
Jonathan Fieldsend and Jose Antonio Lozano and
Dirk Arnold and Gabriela Ochoa and Tian-Li Yu and
Holger Hoos and Yaochu Jin and Ting Hu and Miguel Nicolau and
Robin Purshouse and Thomas Baeck and Justyna Petke and
Giuliano Antoniol and Johannes Lengler and
Per Kristian Lehre",
-
isbn13 = "978-1-4503-6111-8",
-
pages = "1003--1011",
-
address = "Prague, Czech Republic",
-
DOI = "doi:10.1145/3321707.3321851",
-
publisher = "ACM",
-
publisher_address = "New York, NY, USA",
-
month = "13-17 " # jul,
-
organisation = "SIGEVO",
-
keywords = "genetic algorithms, genetic programming, Theory, Run
time analysis",
-
size = "9 pages",
-
abstract = "Recently it has been proved that simple GP systems can
efficiently evolve the conjunction of n variables if
they are equipped with the minimal required components.
In this paper, we make a considerable step forward by
analysing the behaviour and performance of a GP system
for evolving a Boolean function with unknown
components, i.e. the target function may consist of
both conjunctions and disjunctions. We rigorously prove
that if the target function is the conjunction of n
variables, then a GP system using the complete truth
table to evaluate program quality evolves the exact
target function in O(l n log squared n) iterations in
expectation, where l ge n is a limit on the size of any
accepted tree. Additionally, we show that when a
polynomial sample of possible inputs is used to
evaluate solution quality, conjunctions with any
polynomially small generalisation error can be evolved
with probability 1 − O(log squared (n)/n). To produce
our results we introduce a super-multiplicative drift
theorem that gives significantly stronger runtime
bounds when the expected progress is only slightly
super-linear in the distance from the optimum.",
-
notes = "Also known as \cite{3321851} GECCO-2019 A
Recombination of the 28th International Conference on
Genetic Algorithms (ICGA) and the 24th Annual Genetic
Programming Conference (GP)",
- }
Genetic Programming entries for
Benjamin Doerr
Andrei Lissovoi
Pietro S Oliveto
Citations