A study of drift analysis for estimating computation time of evolutionary algorithms
From MaRDI portal
Publication:1768779
DOI10.1023/B:NACO.0000023417.31393.c7zbMath1074.68062MaRDI QIDQ1768779
Publication date: 15 March 2005
Published in: Natural Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (54)
On easiest functions for mutation operators in bio-inspired optimisation ⋮ Robustness of populations in stochastic environments ⋮ Concentration of first hitting times under additive drift ⋮ Drift Analysis and Evolutionary Algorithms Revisited ⋮ Choosing selection pressure for wide-gap problems ⋮ The \$-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems ⋮ A new approach to estimating the expected first hitting time of evolutionary algorithms ⋮ A rigorous analysis of the compact genetic algorithm for linear functions ⋮ Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions ⋮ Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem ⋮ A tight runtime analysis for the \((\mu + \lambda)\) EA ⋮ The complex parameter landscape of the compact genetic algorithm ⋮ Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints ⋮ Adaptive drift analysis ⋮ Crossover can be constructive when computing unique input-output sequences ⋮ Analyzing different variants of immune inspired somatic contiguous hypermutations ⋮ Unnamed Item ⋮ Self-stabilizing Cuts in Synchronous Networks ⋮ Choosing the right algorithm with hints from complexity theory ⋮ Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter ⋮ Runtime analysis of the \((1+1)\) EA on computing unique input output sequences ⋮ Multiplicative drift analysis ⋮ Black-box search by unbiased variation ⋮ Finding Antimagic Labelings of Trees by Evolutionary Search ⋮ A large population size can be unhelpful in evolutionary algorithms ⋮ Non-existence of linear universal drift functions ⋮ The use of tail inequalities on the probable computational time of randomized search heuristics ⋮ Simplified drift analysis for proving lower bounds in evolutionary computation ⋮ Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded ⋮ Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front ⋮ On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms ⋮ Evolutionary algorithms for quantum computers ⋮ Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints ⋮ Island models meet rumor spreading ⋮ Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances ⋮ Drift conditions for estimating the first hitting times of evolutionary algorithms ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ Multiplicative up-drift ⋮ Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint ⋮ Markov chain analysis of evolutionary algorithms on OneMax function -- from coupon collector's problem to (1 + 1) EA ⋮ Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions ⋮ Drift analysis of mutation operations for biogeography-based optimization ⋮ The time complexity analysis of a class of gene expression programming ⋮ The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm ⋮ A self-stabilizing algorithm for cut problems in synchronous networks ⋮ Optimal parameter choices via precise black-box analysis ⋮ Recent advances in evolutionary computation ⋮ 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 ⋮ Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links ⋮ Theoretical Analysis of Local Search in Software Testing ⋮ On the effectiveness of immune inspired mutation operators in some discrete optimization problems ⋮ First-hitting times under drift ⋮ Recursively Generated Evolutionary Turing Machines and Evolutionary Automata
This page was built for publication: A study of drift analysis for estimating computation time of evolutionary algorithms
