Runtime analysis of the \((1+1)\) EA on computing unique input output sequences

DOI10.1016/j.ins.2010.01.031zbMath1328.68200MaRDI QIDQ903582

Xin Yao, Per Kristian Lehre

Publication date: 14 January 2016

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2010.01.031

zbMATH Keywords

evolutionary algorithmsrandom searchfinite state machinesconformance testingruntime analysisunique input output sequences

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

On the effectiveness of immune inspired mutation operators in some discrete optimization problems, Design and analysis of different alternating variable searches for search-based software testing, A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems, Level-based analysis of the univariate marginal distribution algorithm, Solving problems with unknown solution length at almost no extra cost, The linear hidden subset problem for the \((1 + 1)\) EA with scheduled and adaptive mutation rates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Real royal road functions for constant population size
• A rigorous analysis of the compact genetic algorithm for linear functions
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• On the analysis of the \((1+1)\) evolutionary algorithm
• A study of drift analysis for estimating computation time of evolutionary algorithms
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.
• Real royal road functions -- where crossover provably is essential
• Population size versus runtime of a simple evolutionary algorithm
• Theoretical Analysis of Local Search in Software Testing
• On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
• Testing finite-state machines: state identification and verification
• On the Brittleness of Evolutionary Algorithms
• Formal Approaches to Software Testing