Drift analysis and average time complexity of evolutionary algorithms
From MaRDI portal
Publication:5940960
DOI10.1016/S0004-3702(01)00058-3zbMath0971.68129OpenAlexW2084149434MaRDI QIDQ5940960
Publication date: 20 August 2001
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0004-3702(01)00058-3
Related Items (63)
Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms ⋮ Variable solution structure can be helpful in evolutionary optimization ⋮ Runtime analysis of non-elitist populations: from classical optimisation to partial information ⋮ The impact of random initialization on the runtime of randomized search heuristics ⋮ Drift Analysis and Evolutionary Algorithms Revisited ⋮ Does comma selection help to cope with local optima? ⋮ Fast mutation in crossover-based algorithms ⋮ Fixed-target runtime analysis ⋮ Choosing selection pressure for wide-gap problems ⋮ A new approach to estimating the expected first hitting time of evolutionary algorithms ⋮ Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions ⋮ Analysis of noisy evolutionary optimization when sampling fails ⋮ A tight runtime analysis for the \((\mu + \lambda)\) EA ⋮ Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems ⋮ The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Average convergence rate of evolutionary algorithms in continuous optimization ⋮ Practical performance models of algorithms in evolutionary program induction and other domains ⋮ When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not ⋮ Runtime Analysis of a Co-Evolutionary Algorithm ⋮ Adaptive drift analysis ⋮ On the approximation ability of evolutionary optimization with application to minimum set cover ⋮ Lower bounds from fitness levels made easy ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ Runtime analysis of a multi-objective evolutionary algorithm for obtaining finite approximations of Pareto fronts ⋮ Multiplicative drift analysis ⋮ 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 ⋮ Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise ⋮ Approximating fixation probabilities in the generalized Moran process ⋮ Drift analysis of ant colony optimization of stochastic linear pseudo-Boolean functions ⋮ Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances ⋮ Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change ⋮ Drift conditions for estimating the first hitting times of evolutionary algorithms ⋮ Backward-chaining evolutionary algorithms ⋮ An analysis on recombination in multi-objective evolutionary optimization ⋮ Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem ⋮ Multiplicative up-drift ⋮ The runtime of the compact genetic algorithm on jump functions ⋮ Generalized decomposition and cross entropy methods for many-objective optimization ⋮ 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 ⋮ How to escape local optima in black box optimisation: when non-elitism outperforms elitism ⋮ The impact of a sparse migration topology on the runtime of island models in dynamic optimization ⋮ Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm ⋮ Static and self-adjusting mutation strengths for multi-valued decision variables ⋮ Drift analysis of mutation operations for biogeography-based optimization ⋮ Memetic algorithms: The polynomial local search complexity theory perspective ⋮ Running time analysis of the (1+1)-EA for robust linear optimization ⋮ When to use bit-wise neutrality ⋮ Working principles of binary differential evolution ⋮ Recent advances in evolutionary computation ⋮ Analyzing evolutionary optimization and community detection algorithms using regression line dominance ⋮ Comparison of simple diversity mechanisms on plateau functions ⋮ Hitting times of local and global optima in genetic algorithms with very high selection pressure ⋮ Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms ⋮ On the effectiveness of immune inspired mutation operators in some discrete optimization problems ⋮ First-hitting times under drift ⋮ Unnamed Item ⋮ Towards an analytic framework for analysing the computation time of evolutionary algorithms
Uses Software
Cites Work
- Heuristic combinatorial optimization by simulated Darwinian evolution: A polynomial time algorithm for the traveling salesman problem
- Theory of evolutionary algorithms: A bird's eye view
- On the convergence rates of genetic algorithms
- Statistical Dynamics of the Royal Road Genetic Algorithm
- Hitting-time and occupation-time bounds implied by drift analysis with applications
- Criteria for classifying general Markov chains
- The time complexity of maximum matching by simulated annealing
- Optimizing epochal evolutionary search: Population-size dependent theory
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Drift analysis and average time complexity of evolutionary algorithms
