- author = "William B. Langdon",
- title = "Fitness First and Fatherless Crossover",
- booktitle = "Proceedings of the Genetic and Evolutionary Computation Conference Companion",
- series = "GECCO '21",
- year = "2021",
- editor = "Francisco Chicano and Alberto Tonda and Krzysztof Krawiec and Marde Helbig and Christopher W. Cleghorn and Dennis G. Wilson and Georgios Yannakakis and Luis Paquete and Gabriela Ochoa and Jaume Bacardit and Christian Gagne and Sanaz Mostaghim and Laetitia Jourdan and Oliver Schuetze and Petr Posik and Carlos Segura and Renato Tinos and Carlos Cotta and Malcolm Heywood and Mengjie Zhang and Leonardo Trujillo and Risto Miikkulainen and Bing Xue and Aneta Neumann and Richard Allmendinger and Fuyuki Ishikawa and Inmaculada Medina-Bulo and Frank Neumann and Andrew M. Sutton",
- month = "10-14 " # jul,
- pages = "253--254",
- organisation = "SIGEVO",
- address = "Internet",
- publisher = "Association for Computing Machinery",
- publisher_address = "New York, NY, USA",
- keywords = "genetic algorithms, genetic programming, parallel computing, MIMD and AVX-512 SIMD, fast tree evaluation, Speedup technique, runt free broods, memory efficient GA, generational EA, tournament selection, convergence, extended evolution, Long-Term Evolution Experiment, LTEE, Extended unbounded evolution, unlimited bloat: Poster",
- isbn13 = "978-1-4503-8351-6",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/Langdon_2021_GECCO.pdf",
-
video_url = "
https://youtu.be/9W3EWuc1v2s",
-
DOI = "
doi:10.1145/3449726.3459437",
- size = "2 pages",
-
abstract = "When programs are very large and fitness evaluation is
fast (e.g. due to evaluating only a tiny fraction of
the program) it can be efficient to evaluate fitness
before creating the program, as only individuals with
children need be created. The saving can be > 50percent
and even in highly converged populations, it saves
exp(-2) = 13.5percent.
In GP crossover one child is created from two parents but the root donating parent (mum) contributes far more than the other (dad). The subtree from the father is usually small and can be extracted from each dad and saved before crossover. This gives single parent crossover, which when combined with fitness first, further reduces the number of crossovers. Even in the worst case the reduction is exp(-1) = 37 percent.
With large trees, even in populations of similar fitness, eliminating bachelors and spinsters is feasible and can reduce both runtime and memory consumption. Storage in a (N) multi-threaded implementation for a population M is about 0.63M + N, compared to the usual M+2N, in practice saving > 17percent. We achieve 692 billion GP operations per second, 692 giga GPops, on an Intel i7-9800X 16 thread 3.8GHz desktop (CPU bandwidth 85 GByte/second).",
-
notes = "Poster
http://www.cs.ucl.ac.uk/staff/W.Langdon/gecco2021/langdon_2021_gecco_poster.pdf
Code
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/gp-code/GPinc.tar.gz
GECCO-2021 A Recombination of the 30th International Conference on Genetic Algorithms (ICGA-2021) and the 26th Annual Genetic Programming Conference (GP-2021)",
