Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics

DOI10.1145/1967654.1967661zbMath1369.68305arXiv1007.4636OpenAlexW2053987102MaRDI QIDQ5276086

Greg Durrett, Frank Neumann, Una-May O'Reilly

Publication date: 14 July 2017

Published in: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.4636

zbMATH Keywords

genetic programming evolutionary algorithms hill climbing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Variable solution structure can be helpful in evolutionary optimization ⋮ Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences ⋮ (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error ⋮ Population size matters: rigorous runtime results for maximizing the hypervolume indicator ⋮ The Max problem revisited: the importance of mutation in genetic programming ⋮ Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming ⋮ The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time

This page was built for publication: Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics