Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics
Files
(Restricted Access)
Date
2011
Authors
Durrett, G.
Neumann, F.
O'Reilly, U.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceeding: FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, 2011: pp.69-80
Statement of Responsibility
Greg Durrett, Frank Neumann, Una-May O’Reilly
Conference Name
ACM SIGEVO Workshop on Foundations of Genetic Algorithms (11th : 2011 : Schwarzenberg, Austria)
Abstract
Analyzing the computational complexity of evolutionary algorithms (EAs) for binary search spaces has significantly informed our understanding of EAs in general. With this paper, we start the computational complexity analysis of genetic programming (GP). We set up several simplified GP algorithms and analyze them on two separable model problems, ORDER and MAJORITY, each of which captures a relevant facet of typical GP problems. Both analyses give first rigorous insights into aspects of GP design, highlighting in particular the impact of accepting or rejecting neutral moves and the importance of a local mutation operator.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2011 ACM