Evolving Boolean functions with conjunctions and disjunctions via genetic programming

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@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