Fitness levels with tail bounds for the analysis of randomized search heuristics
Introduction
The running time analysis of randomized search heuristics, including evolutionary algorithms, ant colony optimization and particle swarm optimization, is a vivid research area where many results have been obtained in the last 15 years. Different methods for the analysis were developed as the research area grew. For an overview of the state of the art in the area see the books by Auger and Doerr [1], Neumann and Witt [8] and Jansen [4].
The fitness-level method, also called the method of f-based partitions, is a classical and intuitive method for running time analysis, first formalized by Wegener [11]. It applies to the case that the total running time of a search heuristic can be represented as (or bounded by) a sum of geometrically distributed waiting times, where the waiting times account for the number of steps spent on certain levels of the search space. Wegener [11] presented both upper and lower bounds on the running time of randomized search heuristics using the fitness-level method. The lower bounds relied on the assumption that no level was allowed to be skipped. Sudholt [10] significantly relaxed this assumption and presented a very general lower-bound version of the fitness-level method that allows levels to be skipped with some probability.
Only recently, the focus in running time analysis turned to tail bounds, also called concentration inequalities. Zhou, Luo, Lu, Han [12] were the first to add tail bounds to the fitness-level method. Roughly speaking, they prove w.r.t. the running time T that holds, where h is the worst-case expected waiting time over all fitness levels and is arbitrary. An obvious open question was whether the factor 2 in front of the expected value could be “removed” from the tail bound, i.e., replaced with 1; Zhou et al. [12] only remark that the factor 2 can be replaced with 1.883.
In this article, we give a positive answer to this question and supplement the fitness-level method also with lower tail bounds. Roughly speaking, we prove in Section 2 that and , where s is the sum of the squares of the waiting times over all fitness levels. We apply the technique to a classical benchmark problem, more precisely to the running time analysis of randomized local search (RLS) on OneMax in Section 3, and prove a very sharp concentration of the running time around . We finish with some conclusions and a pointer to related work.
Section snippets
New tail bounds for fitness levels
Miscellaneous authors [6] on the Internet discussed tail bounds for a special case of our problem, namely the coupon collector problem (Motwani and Raghavan [7, Chapter 3.6]). Inspired by this discussion, we present our main result in Theorem 1 below. It applies to the scenario that a random variable (e.g., a running time) is given as a sum of geometrically distributed independent random variables (e.g., waiting times on fitness levels). A concrete application will be presented in Section 3.
Theorem 1 Let
Application to RLS on OneMax
As a proof of concept, we apply Theorem 2 to a classical benchmark problem in the analysis of randomized search heuristics, more precisely the running time of RLS on OneMax. RLS is a well-studied randomized search heuristic, defined in Algorithm 1. The function is defined by , and the running time is understood as the first hitting time of the all-ones string (plus 1 to count the initialization step). We obtain a very sharp concentration, as stated in
Conclusions
We have supplemented upper and lower tail bounds to the fitness-level method. The lower tails are novel contributions and the upper tails improve an existing result from the literature significantly. As a proof of concept, we have applied the fitness levels with tail bounds to the analysis of RLS on OneMax and obtained a very sharp concentration result.
If the stochastic process under consideration is allowed to skip fitness levels, which is often the case with globally searching algorithms such
Acknowledgement
The author thanks Per Kristian Lehre for useful discussions.
References (12)
- et al.
The use of tail inequalities on the probable computational time of randomized search heuristics
Theor. Comput. Sci.
(2012) Analyzing randomized search heuristics: Tools from probability theory
- et al.
Collecting coupons with random initial stake
Analyzing Evolutionary Algorithms – The Computer Science Perspective
(2013)- et al.
General drift analysis with tail bounds
Cited by (52)
Exponential slowdown for larger populations: The (μ + 1)-EA on monotone functions
2021, Theoretical Computer ScienceError analysis of elitist randomized search heuristics
2021, Swarm and Evolutionary ComputationLower Bounds from Fitness Levels Made Easy
2024, Algorithmica