The Fitness Level Method with Tail Bounds
The fitness-level method, also called the method of f-based partitions, is an intuitive and widely used technique for the running time analysis of randomized search heuristics. It was originally defined to prove upper and lower bounds on the expected running time. Recently, upper tail bounds were added to the technique; however, these tail bounds only apply to running times that are at least twice as large as the expectation. We remove this restriction and supplement the fitness-level method with sharp tail bounds, including lower tails. As an exemplary application, we prove that the running time of randomized local search on OneMax is sharply concentrated around n ln n - 0.1159 n.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms
The fitness level method is a popular tool for analyzing the hitting time of elitist evolutionary algorithms. Its idea is to divide the search space into multiple fitness levels and estimate lower and upper bounds on the…
Evolutionary AlgorithmsOn Proportions of Fit Individuals in Population of Evolutionary Algorithm with Tournament Selection
In this paper, we consider a fitness-level model of a non-elitist mutation-only evolutionary algorithm (EA) with tournament selection. The model provides upper and lower bounds for the expected proportion of the individu…
Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from Fitness Levels
The fitness level method is an easy-to-use tool for estimating the hitting time of elitist evolutionary algorithms. Recently, linear lower and upper bounds by fitness levels have been constructed. But these bounds requir…
Evolutionary AlgorithmsDerivation of Upper Bounds on Optimization Time of Population-Based Evolutionary Algorithm on a Function with Fitness Plateaus Using Elitism Levels Traverse Mechanism
In this article a tool for the analysis of population-based EAs is used to derive asymptotic upper bounds on the optimization time of the algorithm solving Royal Roads problem, a test function with plateaus of fitness. I…
Lower Bounds from Fitness Levels Made Easy
One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels …
Evolutionary Algorithms