The use of tail inequalities on the probable computational time of randomized search heuristics

DOI10.1016/j.tcs.2012.01.010zbMath1242.68299OpenAlexW2032655195MaRDI QIDQ428911

Dong Zhou, Dan Luo, Zhangang Han, Ru-qian Lu

Publication date: 25 June 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.010

zbMATH Keywords

computational complexitytail inequalitiesevolutionary algorithms (EAs)expected running timeprobable computational time (PCT)randomized search heuristics (RSHs)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Analyzing randomized search heuristics via stochastic domination ⋮ Fitness levels with tail bounds for the analysis of randomized search heuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A large population size can be unhelpful in evolutionary algorithms
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Engineering stochastic local search algorithms. Designing, implementing and analyzing effective heuristics. Second international workshop, SLS 2009, Brussels, Belgium, September 3--4, 2009. Proceedings
• Towards an analytic framework for analysing the computation time of evolutionary algorithms
• Ant colony optimization and the minimum spanning tree problem
• Runtime analysis of a binary particle swarm optimizer
• Runtime analysis of a simple ant colony optimization algorithm
• Runtime analysis of ant colony optimization with best-so-far reinforcement
• On the analysis of the \((1+1)\) evolutionary algorithm
• A study of drift analysis for estimating computation time of evolutionary algorithms
• On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• How to analyse evolutionary algorithms.
• Real royal road functions -- where crossover provably is essential
• A new approach to estimating the expected first hitting time of evolutionary algorithms
• First steps to the runtime complexity analysis of ant colony optimization
• Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization
• A theory of the learnable
• On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics
• On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
• Computing single source shortest paths using single-objective fitness
• Probability and Computing
• STACS 2005
• Automata, Languages and Programming
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: The use of tail inequalities on the probable computational time of randomized search heuristics