Project topics and materials
Get Complete Project Material File(s) Now! »
Drift Maximizer Achieves the Precise Unary Unbiased Black-Box Complexity (Apart From an o(n) Additive Term)
The inherent difficulty of proving runtime guarantees for evolutionary algorithms and other RSHs for a long time prohibited runtime results that are more precise than giving the asymptotic order of magnitude. It is known that the unary unbiased black-box complexity of OneMax is of order n log n [LW12]. We note here that black-box complexity is the minimum expected runtime that a black-box optimization algorithm needs to solve a problem; the unary unbiased back-box model in addition requires that all search points are sampled from unary distributions which are symmetric with respect to bit values and bit positions, cf. Section 2.1 for a detailed description. The simple randomized local search heuristic (RLS), which in each iteration applies a ran-dom single bit flip on a best-so-far search point, is easily seen to have a runtime of (1 + o(1))n ln (n) by a reduction to the coupon collector problem. Its precise opti-mization time is n ln(n) + (γ − ln(2)) + o(1) ≈ n ln n − 0.1159n, where γ = 0.5772 is the Euler-Mascheroni constant [DD16]. The previously best known unary unbiased algorithm has an expected runtime that is smaller than that of RLS by an additive Q(√n log n) term [LDD15].
In Chapter 3, we bring precise runtime analysis and black-box complexity to-gether. By determining the black-box complexity more precisely than up to the asymptotic order, we shall understand more precisely the problem difficulty, but also learn improved ways to solve the problem. Taking the unary unbiased black-box com-plexity as first object of investigation, we derive a simple (1+1)-type algorithm that, by using a fitness-dependent mutation strength, has a time complexity larger than the theoretical optimum by only an additive εn term (ε a small constant). We show a precise bound for the unary unbiased black-box complexity of OneMax. More precisely, we show that it is n ln(n) − cn ± o(n) for a constant c for which we show 0.2539 < c < 0.2665. We also show how to numerically compute this constant with arbitrary precision. Equally important, our analysis reveals (and needs) a number of interesting structural results. In particular, in the language of fixed-budget com-putation as introduced by Jansen and Zarges [JZ14], the drift-maximizing algorithm with a budget of at least 0.2675n iterations computes a solution with expected fitness distance to the optimum roughly 13% smaller than the output of the previously best known algorithm. The result have been published at GECCO’16 [DDY16b].
Self-adjusting RLS also Achieves the Same Complexity
Based on the analysis of the near-optimal mutation strength, we have proposed at PPSN’16 [DDY16a] a variant of RLS with self-adjusting mutation strengths which can both avoid the performance loss of standard bit mutation and avoid the risk of getting stuck in local optima. The idea is to let the algorithm learn the optimal mutation rate autonomously by analyzing the past performance of the different mutation strengths. Such an on-the-fly learning are subject to an exploration-exploitation trade-off in that they want to exploit those parameter values that are assumed to be optimal at different stages of the optimization process, but also need to allocate some positive probability to select sub-optimal parameter values, in order to be able to detect if some of these have become superior in the meantime. Our algorithm therefore chooses in each iteration with some small probability δ a random parameter and greedily selects the parameter value from which it expects the best progress in fitness otherwise, i.e., with probability 1 − δ. We experimentally analyze our new algorithm on the LeadingOnes and the min-imal spinning tree (MST) problem. We observe that, for suitable parameter settings, it clearly outperforms the (1+1) EA. Interestingly, it even beats the randomized local search (RLS) heuristic (flipping always one bit) for the LeadingOnes problem and the variant of RLS flipping one or two bits for the MST problem. This shows that for these problems a better performance can be obtained from a mutation strength
that changes over time, and that our algorithm is able to find such superior fitness-dependent mutation strengths on the fly. We also make this effect mathematically precise for OneMax. We show that our algorithm essentially is able to find the close-to-optimal mutation schedule identified in our above-described work [DDY16b]. More precisely, with high probability our algorithm always (apart from a lower-order fraction of the iterations) uses a mutation strength which gives an expected progress equal to the best possible progress (again, apart from lower order terms). Conse-quently, it has the same optimization time (apart from an o(n) additive lower order term) and the same asymptotic 13% superiority in the fixed-budget perspective as the drift maximizer proposed in [DDY16b].
Self-adjusting (1+λ) EA Achieves the λ-parallel MutationBased Unbiased Black-box Complexity
Inspired by the self-adjusting algorithm proposed in [DDY16a], we notice that some of the difficulties of the learning mechanism, e.g., the whole book-keeping being part of it and also the setting of the parameters regulating how to discount information over time, can be overcome by using a (1+λ) EA, which samples λ independent offspring per iteration. In a sense, the use of larger populations enables us to adjust the mutation rate solely on information learned in the current iteration. However, we do also use the idea of [DDY16a] to intentionally use parameter settings which appear to be slightly off the current optimum to gain additional insight and to be able to detect and to react to a change in the optimal parameter values. In Chapter 4, we propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. It aims at overcoming some of the difficulties of the learning mechanism just described. It consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated according to which subpopulation contains the best offspring. Instead of always modifying the mutation rate to the rate of the best offspring, we shall take this winner’s rate only with probability a half and else modify the mutation rate to a random one of the two possible values (twice and half the current rate). Our motivation for this modification is that we feel that the additional random noise will not prevent the algorithm from adjusting the mutation rate into a direction that is more profitable. However, the increased amount of randomness may allow the algorithm to leave a possible basin of attraction of a locally optimal mutation rate. We analyze how the (1 + λ) evolutionary algorithm with this self-adjusting mu-tation rate optimizes the OneMax test function. We prove that this dynamic version of the (1 + λ) EA finds the optimum in an expected optimization time (number of fitness evaluations) of O(nλ/ log λ + n log n). This time is asymptotically smaller than the optimization time of the classic (1 + λ) EA. Previous work in [BLS14] shows that this performance is best-possible among all λ-parallel mutation-based unbiased black-box algorithms. As an interesting side remark, our proofs reveal that a quite non-standard but fixed mutation rate of r = ln(λ)/2 also achieves the Q(log log λ) improvement as it implies the bound of Q(n/ log λ) generations if λ is not too small. Hence, the constant choice r = O(1) as studied in [GW17] does not yield the asymptotically optimal number of generations unless λ is so small that the n log n-term dominates. These results have been presented at GECCO’17 [Doe+17]. 1 1. This is a joint work with Christian Gießen and Carsten Witt from Technical University of Denmark. Every author contributes equally to the collaboration.
Extend the Self-adjusting Strategy to Non-elitist Algorithm Self-adaptive (1,λ) EA
In Chapter 5, we propose and analyze a self-adaptive version of the (1, λ) evolu-tionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax bench-mark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations of O( nλ / log λ + n log n). This time is asymptotically smaller than the optimization time of the classic (1, λ) EA and as mentioned above (1 + λ) EA for all static mutation rates and best possible among all λ-parallel mutation-based unbiased black-box algorithms. Our result shows that self-adaptation in evolutionary computation can find com-plex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate proposed in Chapter 4 can be replaced by our simple endogenous scheme. These results will be presented at GECCO’18 [DWY18]. 2.
Related Work
Since the parameter setting has a decisive influence on the performance of RSHs, it is not surprising that it is one of the most intensively studied research questions in the domain of heuristic optimization. Most works, however, study the influence of the parameters on performance by empirical means, whereas here in this work we are rather concerned with rigorous mathematical runtime results. We summarize in this section some of the few known results that are precise enough to determine optimal parameter settings. Not surprisingly, the OneMax benchmark problem also considered in this thesis plays a central role in the works.
Static Parameter Choices
A very early work on precise runtime analysis, apparently overlooked by many subsequent works, is the very detailed analysis on how the (1+1) EA with general mu-tation rate c/ n, c a constant, optimizes the Needle and OneMax functions [GKS99]. Disregarding here the results on the runtime distributions, this work shows that the (1+1) EA with mutation rate c/n finds the optimum of the Needle function in (1 + o(1))1−1e−c 2n time. For OneMax, the runtime estimate in [GKS99] is (1 + o(1))ecc n ln(n) , more pre-cisely, ecc n ln(n) ± O(n). The proof of the latter result uses several deep tools from probability theory, among them Laplace transforms and renewal theory. For a simple proof of the upper bound (1 + o(1)) en ln(n) for mutation rate 1/n, see, e.g., [DJW02]. The first proofs of a lower bound of order (1 − o(1))en ln(n) using more elemen-tary methods where given, independently, in [DFW10; Sud13]. An improvement to en ln (n) − O (n) was presented in [DFW11]. Very recently, again for the case c = 1, a very precise analysis of the expected runtime, specifying all lower order terms larger than Q(log(n)/n) with precise leading constant, was given in [Hwa+18]. That the runtime bound of (1 + o(1))ecc n ln( n) holds not only for OneMax, but any linear pseudo-Boolean function, was shown in [Wit13]. Since the mutation rate determines the leading constant of the runtime, a rate of 1/ n gives the asymptotically best runtime. Using single bit flips is also a suitable choice for the classic randomized 2. This is a joint work with Carsten Witt from Technical University of Denmark. Every author contributes equally to the collaboration. local search with static mutation strengths. By a reduction to the coupon collector problem, we obtain a runtime of (1 + o( 1))n ln(n) which matches the current known unary unbiased black-box complexity of order n log n.
An extension of the OneMax result to (1 + λ) EAs was obtained in [GW15]. The bound of ( 1 + o( 1))(ecc n ln(n) + nλ ln ln( λ) /2 ln(λ)) fitness evaluations contains the surprising result that the mutation rate is important for small offspring population sizes, but has only a lower-order influence once λ is sufficiently large (at least when restricted to mutation rates in the range Q(1/n); note that Lemma 4.2 indicates that mutation rates of a larger order of magnitude can give asymptotically smaller runtimes for larger values of λ).
Table of contents :
Résumé
Abstract
1 Introduction
1.1 Bit-counting Problems
1.2 Summary of Contributions
1.3 Related Work
2 Preliminaries
2.1 Black-box Complexity
2.2 Evolutionary Algorithms
2.3 Randomized Local Search
2.4 Drift Theorems
2.5 Chernoff Bounds
2.6 Occupation Probabilities
2.7 Useful Equations and Inequalities
3 Precise Unary Unbiased Black-box Complexity
3.1 Problem Setting and Useful Tools
3.2 Maximizing Drift is Near-Optimal
3.3 Fitness-Dependent Mutation Strength
3.4 Runtime Analysis for the Approximate Drift-Maximizer ˜A »
3.5 Fixed-Budget Analysis
3.6 Self-adjusting Mutation Rate
3.7 Mathematical Runtime Analysis on OneMax
3.8 Experimental Results
4 Self-adjusting (1+) EA
4.1 Algorithm
4.2 Proof Overview
4.3 The Far Region
4.4 The Middle Region
4.5 The Near Region
4.6 Putting Everything Together
4.7 Experimental Results
5 Self-adapting (1,) EA
5.1 Algorithm
5.2 The Far Region
5.3 The Near Region
5.4 Putting Everything Together
5.5 Experimental Results
6 Conclusions
Bibliography
