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

DOI10.1016/J.INS.2010.01.031MaRDI QIDQ903582zbMATH OpenOpenAlexFDO

Authors Per Kristian Lehre, Xin Yao

Publication date 14 January 2016

Published in Information Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

evolutionary algorithmsfinite state machinesconformance testingruntime analysisrandom searchunique 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)

Recommendations

• Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise
• scientific article; zbMATH DE number 2013543
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Runtime analysis of the \((1+1)\) evolutionary algorithm on strings over finite alphabets
• A study on the extended unique input/output sequence
• scientific article; zbMATH DE number 4085399
• On \(O(1)\) time algorithms for combinatorial generation
• Runtime analysis of the ( + 1)-EA on the dynamic BinVal function

Cites work

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

Cited in

(11)

• Level-based analysis of the univariate marginal distribution algorithm
• Solving problems with unknown solution length at almost no extra cost
• Crossover can be constructive when computing unique input-output sequences
• A study on the extended unique input/output sequence
• Design and analysis of different alternating variable searches for search-based software testing
• Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools
• Evolutionary generation of unique input/output sequences for class behavioral testing
• On the effectiveness of immune inspired mutation operators in some discrete optimization problems
• Formal Approaches to Software Testing
• The linear hidden subset problem for the \((1 + 1)\) EA with scheduled and adaptive mutation rates
• A comparative performance analysis of evolutionary algorithms on k-median and facility location problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q903582)