2010/07/27 by Greg Durrett, Frank Neumann, Durrett, Greg +3 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Reinforcement Learning in Robotics #Viral Infectious Diseases and Gene Expression in Insects
paper · pdf · doi:10.48550/arxiv.1007.4636
openalex publication_date 2010/07/27 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
Analyzing the computational complexity of evolutionary algorithms for binary\nsearch spaces has significantly increased their theoretical understanding. With\nthis paper, we start the computational complexity analysis of genetic\nprogramming. We set up several simplified genetic programming algorithms and\nanalyze them on two separable model problems, ORDER and MAJORITY, each of which\ncaptures an important facet of typical genetic programming problems. Both\nanalyses give first rigorous insights on aspects of genetic programming design,\nhighlighting in particular the impact of accepting or rejecting neutral moves\nand the importance of a local mutation operator.\n