Runtime analysis of the (1+1) EA on computing unique input output sequences
DOI10.1016/J.INS.2010.01.031zbMATH Open1328.68200OpenAlexW2116902835MaRDI QIDQ903582FDOQ903582
Authors: Per Kristian Lehre, Xin Yao 
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
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 \((\mu + 1)\)-EA on the dynamic BinVal function
evolutionary algorithmsfinite state machinesconformance testingruntime analysisrandom searchunique input output sequences
Formal languages and automata (68Q45) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Cites Work
- Introduction to algorithms
- Real royal road functions for constant population size
- Title not available (Why is that?)
- A study of drift analysis for estimating computation time of evolutionary algorithms
- The analysis of evolutionary algorithms on sorting and shortest paths problems
- Real royal road functions -- where crossover provably is essential
- On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
- Title not available (Why is that?)
- On the analysis of the \((1+1)\) evolutionary algorithm
- Formal Approaches to Software Testing
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
- Testing finite-state machines: state identification and verification
- Population size versus runtime of a simple evolutionary algorithm
- A rigorous analysis of the compact genetic algorithm for linear functions
- Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.
- Title not available (Why is that?)
- Theoretical Analysis of Local Search in Software Testing
- On the Brittleness of Evolutionary Algorithms
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
- Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools
- A study on the extended unique input/output sequence
- Design and analysis of different alternating variable searches for search-based software testing
- 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)
