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

DOI10.1016/j.ins.2010.01.031zbMath1328.68200OpenAlexW2116902835MaRDI 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

Formal languages and automata (68Q45) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems ⋮ Design and analysis of different alternating variable searches for search-based software testing ⋮ 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 ⋮ On the effectiveness of immune inspired mutation operators in some discrete optimization problems

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

This page was built for publication: Runtime analysis of the \((1+1)\) EA on computing unique input output sequences