The max problem revisited: The importance of mutation in genetic programming

Timo Kötzing, Andrew M. Sutton, Frank Neumann, Una May O'Reilly

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the well-studied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutation-based genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutation-based genetic programming algorithms.

Original languageEnglish (US)
Title of host publicationGECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
Pages1333-1340
Number of pages8
DOIs
StatePublished - 2012
Event14th International Conference on Genetic and Evolutionary Computation, GECCO'12 - Philadelphia, PA, United States
Duration: Jul 7 2012Jul 11 2012

Publication series

NameGECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation

Other

Other14th International Conference on Genetic and Evolutionary Computation, GECCO'12
CountryUnited States
CityPhiladelphia, PA
Period7/7/127/11/12

Keywords

  • genetic programming
  • mutation
  • runtime analysis
  • theory

Fingerprint Dive into the research topics of 'The max problem revisited: The importance of mutation in genetic programming'. Together they form a unique fingerprint.

Cite this