Computer Science
Computer Science-2021.gz:143292
Computer Science
4fe05a4903a3b86cc5cfec57224865859b53198b
Automatic adaptation of hypermutation rates for multimodal optimisation

Previous work has shown that in Artificial Immune Systems (AIS) the best static mutation rates to escape local optima with the ageing operator are far from the optimal ones to do so via large hyper-mutations and vice-versa. In this paper we propose an AIS that automatically adapts the mutation rate during the run to make good use of both operators. We perform rigorous time complexity analyses for standard multimodal benchmark functions with significant characteristics and prove that our proposed algorithm can learn to adapt the mutation rate appropriately such that both ageing and hypermutation are effective when they are most useful for escaping local optima. In particular, the algorithm provably adapts the mutation rate such that it is efficient for the problems where either operator has been proven to be effective in the literature.


INTRODUCTION
It is well understood that the performance of virtually all general purpose optimisation algorithms depends crucially on the parameter settings of their variation operators, used to create new candidate solutions, and of their selection operators used to decide whether to accept new solutions or keep previously identified ones. For instance the performance of local search algorithms [31] on a given problem class depends on the neighbourhood size choice, Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. while for simulated annealing [27] also the cooling schedule used in the selection phase comes into play. Nature inspired optimisation algorithms often come with parameter ranges that are suggested by the underlying paradigm that they imitate. For example, traditional generational evolutionary algorithms (EAs) and genetic algorithms (GAs), inspired by Darwinian evolution, naturally require low mutation rates or their runtime will be exponential even for any function with unique optimum [4].
In recent years increasing evidence has been provided that steadystate EAs and GAs become more efficient either at hillclimbing or at escaping from local optima of multimodal optimisation problems (or both) by using considerably higher mutation rates than those that have traditionally been recommended [2,6,7,14,34,36]. In contrast to generational evolutionary systems where all generated solutions form the new population, the use of artificially introduced elitism in steady-state EAs and GAs allows them to considerably increase the mutation rate without quickly deteriorating their performance i.e., it does not matter if solutions of low quality are created by the higher mutation rates as these will not be accepted [5]. This advantage has been exploited recently by so called Fast EAs that use power-law mutation operators which allow for large mutations more often than the binomial distributions of the traditional standard bit mutations (SBMs) of EAs [19,22,23]. However, the elitism introduced into steady-state algorithms does not allow them to be competitive on problems where non-elitist algorithms (e.g., simulated annealing) are particularly efficient [13,24,29,32].
Artificial immune systems (AISs), inspired by Burnet's clonal selection working principle of the natural immune system of vertebrates [3], naturally apply high mutation rates (i.e., hypermutation) which have also been proven to escape from local optima more efficiently than SBMs. Furthermore, by using an ageing operator, they have been shown to also be capable of escaping from local optima by accepting solutions of lower quality (i.e., essentially through non-elitism). The effectiveness of both hypermutations and ageing at escaping local optima has been proven on standard multimodal benchmark functions with significant structures from the literature [10], as well as for identifying arbitrarily good approximations for NP-Hard problems such as NumberPartitioning (EAs using SBMs may get stuck on poor 4/3 approximations) [9,37]. Traditional AISs, such as Opt-IA [12] and B-Cell [25], exhibit this greater exploration capabilities at the expense of being slower during the exploitation phases of the optimisation (i.e., hillclimbing). Recently, though, so called Fast AISs have been presented that are asymptotically as fast as traditional randomized local search (RLS) and EAs at hillclimbing, while still outperforming them during the exploration phases [8]. Such improved performance during the hillclimbing phases even allows for linear speed-ups of the AISs to approximate Number Partitioning [11].
A major problem with the generality of the Fast AISs is that the hypermutation parameter should be set such that the mutation rate should be high for optimal performance at escaping local optima by performing large mutations, and low for doing so by accepting lower quality solutions by using the non-elitist capabilities of the ageing operator. In particular, if the mutation rate is too high in the latter case, once a local optimum is escaped from, then there is a high probability that the algorithm returns to it via a large mutation if its basin of attraction is large. Hence, on one hand, setting the parameter to appropriate values requires considerable problem knowledge. On the other hand, a fixed parameter value inevitably leads to suboptimal performance for problems where both the elitist and non-elitist strategies are required at different moments.
In this paper we propose an Adaptive Fast AIS that changes the hypermutation rate automatically to identify whether it is more effective to escape from local optima via large mutations or by accepting solutions of lower quality. The adaptive mechanism we propose to use is inspired by the standard 1/5 rule traditionally used in evolutionary computation [1] but differs considerably from it by increasing the mutation rate with the decrease of the success rate, rather than the other way round. The insight for this considerable change is that during the hillclimbing phases where improvements are easier to identify, low mutation rates suffice, while on local optima where improving solutions are harder to identify, then higher mutation rates should be helpful. We rigorously prove that the Adaptive Fast AIS either outperforms or performs just as well as the recently introduced Fast EAs and Fast AISs on the same multimodal benchmark functions where the latter were shown to be beneficial. Furthermore we introduce a more general and harder multimodal benchmark function where it is necessary to adapt the hypermutation rate because we show that the state-of-the-art fast algorithms with static rates are at least super-polynomially slower.

PRELIMINARIES
In this section, we first introduce the artificial immune system framework that we will use throughout the paper, the power law mutation operators (i.e., hypermutations) used by the Fast EAs and Fast AISs and our proposed adaptive Fast AIS. Afterwards we describe the standard benchmark functions from the literature that we will use to assess the performance of the algorithms.

Algorithms from the Literature
A bare-bones (1+1) AIS is shown in Algorithm 1 [10,12]. This simple algorithmic framework will suffice to show the benefits of adapting the hypermutation rate for multimodal optimisation. The algorithm uses both characteristic operators of an AIS: ageing and hypermutation. The AIS applies hybrid ageing which is the best known for escaping local optima [9,10,33]. The algorithm is initialised by choosing a bit-string representing a candidate solution (called b-cell or equivalently individual) uniformly at random with an assigned age of zero. At each iteration of the while loop an offspring is created by performing a hypermutation. If the offspring improves the fitness of its parent, its age will be set to zero. Otherwise, it inherits the age . := . ; 11: for ∈ { , } do 12: if . ≥ then 13: with probability 1/2, reinitialise uniformly at random with . = 0; 14: of the parent. In the next step, if any of these b-cells' age exceeds a threshold , that b-cell will be reinitialised with probability 1/2 and its age will be set to zero. Finally, the best b-cell will be chosen to evolve in the next generation. For the hypermutation variation step we will consider the recently proposed power-law operators used by the Fast EA and the Fast AIS that have been shown to escape local optima more efficiently than traditional EAs. The Fast EA uses a heavy-tailed power-law distribution [19]. It flips each bit in the bit-string representing the parent solution with probability / where the mutation rate is chosen in each generation according to the following probability distribution (which for future reference will be used by the Adaptive Fast (1+1) AIS ): Here the parameter was defined to be strictly larger than 1, and a parameter value of = 1.5 was recommended when the operator was originally introduced. Compared to the strongly concentrated binomial distribution of SBM (each bit is flipped in every generation with a static probability / -usually = 1), this power-law distribution allows for a greater balance between large and small mutations. We make two minor modifications to the operator: 1) rather than flipping each bit with probability / , the operator will flip exactly bits; 2) we extend the tail of the distribution to choose within [1, · · · , ] rather than within [1, · · · , 2 ] as originally proposed (i.e., the sum /2 =1 − has been changed to =1 − in the denominator of (1)). The former change simplifies the analysis without affecting the average performance of the operator considerably. The latter modification has recently been considered by [22]. Both changes allow to make fairer comparisons with the hypermutation operator used by the Fast AIS which can flip any exact number of chosen bits. When this operator is used in line 5 of Algorithm 1, we call the algorithm Fast (1+1) AIS . The hypermutation operator of the originally proposed Fast AIS uses a similar distribution [8]. However, the distribution is symmetric i.e., the probability of flipping bits is the same as that of flipping − bits for all ∈ {0, . . . , }. Thus, while the expected number of bit-flips is always /2, the parameter determines the shape of the distribution. Another distinction is that, instead of choosing a mutation rate and flipping each bit with probability / , the Fast AIS uses the power-law distribution to pick mutation potentials -the number of bits to flip (the reason why we made the first modification to the Fast EA operator for a fairer comparison of the distributions). In particular, the operator picks the mutation potential ∈ {0, 1, . . . , } with probability ( ) where ( ) : {0, 1, . . . , } → (0, 1], and then flips exactly bit-positions picked uniformly at random without replacement (this distribution for future reference will be used by the Adaptive Fast (1+1) AIS ): We include 0 in the support of here since it is essential to flip 0bits for the efficiency of population based evolutionary algorithms, in particular as it impacts the take-over times of the population [5][6][7]38]. However, in trajectory-based algorithms such as the ones discussed in this paper, we recommend to exclude not flipping any bits as a possible outcome. Hence, for the rest of the paper we will assume that ∈ {1, . . . , }. The originally introduced Fast AIS had an equivalent distribution of mutation sizes for each fitness evaluation to (2) when = 1 [8]. However, any ≥ 1 may be applied. It should be pointed out that the originally proposed operator flipped bits at every operation one by one and used a probability distribution very similar to (2) to determine whether to evaluate the solution after the -th bit-flip and stopped the hypermutation as soon as an improvement was detected (i.e., stop at first constructive mutation). However, this is not necessary as shown in [11] and for a fairer comparison with the distribution of the Fast (1+1) AIS we remove this feature and only evaluate the solution once all the bits are flipped. If this hypermutation operator is used in the framework of Algorithm 1, we call the resulting algorithm Fast (1+1) AIS . Fig. 1 compares the two power-law distributions with that of SBM.
Both algorithms exhibit their best performance at escaping local optima via large mutations when the parameter is set to a value close to 1. However, with such a parameter value, the operators lose effectiveness in conjunction with the ageing operator for escaping from local optima with large basins of attraction by accepting solutions of inferior quality, because the high mutation rates lead the algorithm back to the basin of attraction of the original local optimum with high probability [11].

Adaptive Mechanism
The mechanism we propose to use to adapt the mutation rate in the (1+1) AIS is inspired by the 1/5 rule traditionally used in evolutionary computation for continuous optimisation [26]. The method has also been applied successfully in discrete optimisation to automatically adapt the offspring population size of crossover-based algorithms [16,17] and the duration of the learning period in online algorithm selection (i.e., hyper-heuristics) [20,30]. While commonly used in continuous optimisation, the 1/5 rule adaptation has rarely been rigorously studied to automatically adapt the mutation rate in combinatorial optimisation, with probably the only exception for comparison. and denote the denominators of (1) and (2) respectively. The input size is set to = 14 for visualisation.
of [18] that applied it to adapt the mutation rate of the (1+1) EA for the unimodal Leading Ones benchmark function. In the context of mutation rate adaptation, the traditional 1/5 rule increases the mutation rate by a multiplicative factor if an improving mutation is performed, while it decreases it by a smaller factor (usually 1/4 ) every time a mutation fails to identify an improvement. The mechanism we propose is additionally novel because it considerably differs from the traditional 1/5 rule in two ways. Firstly, with the aim of having high mutation rates when stuck for a long time on a local optimum, the mutation rate is decreased with a success and increased with a failure (the opposite of how the traditional mechanism works). Secondly, since when a local optimum is escaped, our aim is to hillclimb the newly identified gradient, we set the mutation rate to its minimum straight away after an improvement. Formally, assuming maximisation, let , , min and max be respectively the parent, the offspring, and the bounds on the minimum and maximum values that the parameter may take, and the value at time step , then the parameter value at time step + 1 will be (update mechanism): Here the parameter is the number of failures it takes to decrease from its maximum value max to its minimum value min . For the analysis we pick min ∈ {1, 1 + } for some constant > 0 in order to have the highest probability of making large jumps, while maintaining a probability of Ω(1/log ) and Ω(1) respectively for local moves. We set max = (log ) 2 and = Ω( log ) so that for the first /2 iterations after an improvement, the algorithms have: Thus, with high probability the hypermutation can discover its entire Hamming neighbourhood in ( log ) iterations before sampling any solution outside of it, which has a polynomially small probability while the current = Ω(log ).
If we use the mechanism to adapt the hypermutation operator of (1) we call the resulting algorithm Adaptive Fast (1+1) AIS , while if it is adapting the rate for the symmetric distribution of (2), we call the algorithm Adaptive Fast (1+1) AIS .
Recently a stagnation detection mechanism was introduced in the literature for steady-state EAs to identify whether they are on a local optima, and consequently increase the mutation rate [35]. Apart from the different motivations behind our work and theirs, one crucial difference between the update mechanisms, is that stagnation detection only increases the standard bit mutation rate above the standard 1/n rate, when with high probability no neighbouring improvements exist, while our proposed mechanism increases the rate after each unsuccessful hypermutation (at a rate than depends on parameter ). Another difference is that the former flips 1 bit in expectation until stagnation is detected, while the aim behind our proposed mechanism is to always flip a linear number of bits in expectation as inspired by the somatic hypermutations occurring in the immune system (i.e., the expected number of bits that flip does not change, just the distribution defined by the parameter which we adapt). Proof. For the probability of flipping 1-bit we refer to (1) and (2) and note that in both equations we have the numerator equal to 1. We will now bound the normalization factors in the denominators separately. We pessimistically assume = 1. Thus, for Eq.(1) we have: and for Eq. ( 2), we have (recall that we normalize over ∈ {1, . . . , } since we avoid flipping 0 bits due to not having a population): When > log , the denominator for Eq. (1) is 1 + (1) since for any ≥ 2, − = ( −1 ) and if we exclude = 2, for > 2, we have − = ( −1 ). Thus, we can bound the denominator from above by On the other hand, we have three terms ( ∈ {1, − 1, }) in the denominator of Eq. (2) which are equal to 1 − = 1, while we can bound the remaining terms as we did for Eq. (1). The result is 3 + (1). □

Benchmark Functions
We will evaluate the performance of the adaptive algorithms against the static ones on a range of widely used pseudo-Boolean benchmark function classes : {0, 1} → R. These have been designed to reflect significant aspects of optimisation problems that are expected to appear in real-world optimisation applications. Without loss of generality, we will consider the instances of each function class that have the global optimum in the 1 bit-string since the behaviour of the algorithms is the same for all function class instances.

Unimodal Functions.
We will start our analysis by establishing the hillclimbing performance of the adaptive algorithms. For this purpose standard unimodal functions from the literature will be used.
The aim of the well-studied OneMax function is to identify a hidden bit-string by minimizing the Hamming distance to it of the candidate solutions. To this end, the function returns the number of correctly identified bit-positions (i.e., the number of ones when the 1 bit-string is used as target). The function reflects the typical characteristic of optimisation problems, that the closer the algorithm gets to the optimum, the harder it is to identify improving solutions. When the target is the 1 bit-string, it is defined formally as OneMax( ) := =1 (see Fig. 2). The unary unbiased black box complexity of OneMax is Θ( log ) [28] meaning that no algorithm using an unbiased mutation operator may be faster. Both the Fast (1+1) AIS and the Fast (1+1) AIS optimise the function in this best possible expected asymptotic runtime [8,19].
LeadingOnes is a slightly harder unimodal function. The aim of the problem is that of identifying a hidden permutation of the bit-string. If the 1 bit-string is used as global optimum, then the function returns the number of consecutive 1-bits before the first 0-bit: LeadingOnes( ) := =1 =1 . Its unbiased black box complexity is Θ( 2 ) which is also met by the two power-law mutation operators [8,19]. The Ridge function class is slightly harder than both OneMax and LeadingOnes. First a OneMax slope needs to be followed to the 0 bit-string. Afterwards, the 0-bits have to be flipped in consecutive order without touching the tail of the bit-string (i.e., only bit-strings of consecutive 1-bits followed by consecutive 0-bits are on the ridge of higher fitness). While the OneMax slope allows to assess algorithmic performance as improvements become harder with progress, the Ridge slope is used to assess performance when improvement probabilities do not change with the position on the slope: Unary unbiased search heuristics typically require Θ( 2 ) expected function evaluations, a runtime that is met by the power-law hypermutation operators. We will use Ridge as a basis for the design of a multimodal benchmark function where it is necessary to adapt the mutation rate for the AISs to run in polynomial expected runtimes. Using Ridge rather than OneMax for the hillclimbing phases will allow us to make the function more challenging to optimise.

Multimodal Functions.
Multimodal functions are generally used to test the exploration abilities of search heuristics including their effectiveness at escaping local optima. We consider two different classes of multimodal benchmark functions which allow performance assessment in different scenarios that are expected to be typically encountered in real-world optimisation.
The Jump function class is widely used in the performance analysis of randomized search heuristics. It consists of two consecutive OneMax slopes of length − and , respectively. The first slope leads the algorithm towards the local optima and the second One-Max slope leads back to it (see Fig. 2). Since the global optimum is the only search point of better quality than the local optima, elitist algorithms typically have to perform a large mutation by flipping simultaneously exact bits to optimise the function. In particular, for elitist algorithms, the function models the hardest-to-escape local optima with basin of attraction of size , since there exists only one search point at Hamming distance from the local optimum, that has better fitness. Due to the second slope leading back to the local optima, the function is also very hard for non-elitist algorithms that may accept solutions of inferior quality on the second slope. The function is formally defined as: Jump was the function class used to show the effectiveness of the power-law hypermutation operators over the traditional SBM operators [8,19]. In particular, the Fast (1+1) AIS and the Fast (1+1) AIS have respectively expected runtimes of ( ) and ((min{ , − }) ) (if > 1, and ((min{ , − }) log ) if = 1) which are exponentially smaller than the Θ( ) expected runtime required by SBM [21]. From the runtime bounds it can be appreciated why the parameter should be set arbitrarily close to 1 for the operators to have their best possible performance for Jump . A value of = 1 is the best possible if more than bits, for any arbitrarily small constant > 0, have to be flipped to escape from the local optima. We point out that the best possible expected runtime achievable with SBM is (( / ) which is matched by the stagnation detection adaptive (1+1) EA [35].
The Cliff function class is often used to assess the performance of non-elitist algorithms. It was originally designed as an example problem where non-elitist EAs outperform elitist ones [24]. This function includes a OneMax slope with length − which leads the algorithms towards the local optima. The local optima are followed by a second OneMax slope (of length ) of lower fitness which leads to the global optimum (see Fig. 2). While for elitist algorithms the function is just as hard as Jump , non-elitist algorithms, by accepting inferior solutions, can easily find the second slope and then hillclimb up to the global optimum. Cliff is defined as: Some non-elitist algorithms such as Metropolis still require exponential time in the length of the second slope [29]. When the second slope has linear length (i.e., the function is hardest for elitist algorithms) (1+1) EAs and randomized local search algorithms equipped with ageing are known to optimise the function in ( log ) function evaluations i.e., the best runtime achievable by unary unbiased search heuristic on any function with unique optimum [28], which is also met by the non-elitisit Move-Acceptance hyper-heuristic [29]. With a small parameter value close to 1 (optimal for Jump ), the Fast (1+1) AIS and Fast (1+1) AIS will be inefficient because the high mutation rates will cause search points on the second slope to return to the local optima with high probability. The expected runtime decreases with higher values of and will reduce to ( log ) in expectation for parameter values in the order of = Ω(log ) because the mutation operators flip one bit most of the time with such a setting. We will show that by automatically adapting the hypermutation rate, optimal performance can be achieved for both Cliff and Jump .

UNIMODAL FUNCTION ANALYSIS
In this section we will analyse the hill-climbing capabilities of the Adaptive Fast (1+1) AIS and the Adaptive Fast (1+1) AIS on unimodal functions. The essence of the following result is that we can guarantee that an improvement will be achieved before drops to levels that yield super-constant probabilities for single bit flips. A constant probability for single bit flips allows the algorithm to be asymptotically optimal when hill-climbing. where E is the event that the optimum is found before a reinitialisation.
Proof. We will define three events that can happen after the algorithm is initialised with a solution picked uniformly at random.
• E : The optimum is found before reinitialisation.
• E : The algorithm reinitialises before any improvement.
• E : The algorithm reinitialises after at least one improvement. We will denote the probabilities of these events as , , respectively. Since the events are mutually exclusive and exhaustive, + + = 1. Hence, the law of total expectation for the expected runtime [ ] implies: We bound the conditional expectations as follows, • ≤ − 2· ln : If the algorithm picks mutation size 1, which happens with probability at least 1/(2 · ln ), then the conditional probability of improvement is at least 1/ since both operators are unbiased and is unimodal. For the ageing operator to trigger, the algorithm should sample at least offspring which do not improve upon their parent. The probability of this event can be bounded above by: For ≥ (6 + ) ln , for any constant > 0 • ≤ · − 6· + 4· ln · − 2· ln : If the algorithm improves at least once, then in order to reinitialise it is necessary that for at least /2 generations the algorithm must fail to improve while the parameter stays above log . When > log , the probability of the operator flipping one bit position is at least 1/3 − (1) due to Lemma 1. If > /2, then the algorithm must also fail to improve in the following − /2 iterations where the improvement probability is at least 1/(2 · ln ) as in the previous case. Thus, using a union bound over all possible fitness values: • For ≥ 2 ≥ (6 + ) ln for some constant > 0 and for an arbitrarily small > 0: We will now bound · + · · to obtain our claim, • · = ( log ): Due to (4), · < − 2· ln · . The right hand side decreases for all ≥ 2 · ln . • · · = ( log ): Since ≤ · − 6· + 4· ln · − 2· ln , where the (1) is due to eq (6) and ( log ) is obtained as in the previous item. Proof. The number of distinct values for our functions of interest are at most 2 (which is the case for the Ridge function). Thus, our stated and parameters satisfy the scope of Lemma 2. Since all our claimed upper bounds are Ω( log ), we will only find upper bounds on the expected time given that ageing does not trigger.
For any unimodal function , the probability that an offspring has a better fitness than its parent is at least Pr (single bit is flipped) / since in any unimodal function at least one Hamming neighbour has a better fitness value than any current suboptimal solution. Using that all our functions are unimodal the expected time until the first improvement occurs is at most ( log ) since both algorithms flip a single bit with probability at least Ω(1/log ). We will next bound the expected time after the first improvement occurs.
Let [ ] denote how many expected hypermutation operations it takes to improve the fitness-function value from to any value greater than . Moreover, let E denote the event that the value for the algorithm stays above log while the current fitness is . By the law of total expectation we divide [ ] into two additive terms: Since is set to (log ) 2 after an improvement, the event E occurs if and only if the algorithm fails to improve (6 + ) · ln ≤ /2 iterations consecutively as in /2 generations multiplicatively decreases from (log ) 2 to log . As the value stays above log until we fail (6 + ) · ln times after the last improvement, we can bound Pr (¬E ) from above: since Pr (single bit is flipped) = 1 3 − (1) for all > log . Since for all ∈ [1, (log ) 2 ] we have Pr (single bit is flipped) = (1/log ), the conditional expectation [ |¬E ] = ( log ). Thus, we can bound the second term in (7) by (log / ).
When calculating [ |E ] for the functions LeadingOnes and Ridge , we can use the upper bound on the improvement probability Pr (single bit is flipped) / and conclude that [ |E ] = ( ) since E implies Pr (single bit is flipped) = Ω(1). In order to find the total expected time of ( 2 ) we recall that both LeadingOnes and Ridge have ( ) different fitness values.
For the OneMax function, [ |E ] can be smaller than ( ) depending on . In particular, it is sufficient that the hypermutation operator flips a single 0-bit into a 1-bit and does not flip any other bits. This mutation occurs with probability Pr (single bit is flipped)· = · for some constant > 0 and its expected waiting time is at most [ |E ] ≤ /( · ). When summed over different values for ∈ {1, . . . , }, the total waiting time −1 =1 · is in the order of ( log ). Thus, for all considered functions the second term in (7) is a small order term, and the claimed upper bounds follow.
The matching lower bounds are due to the unary unbiased blackbox complexity of the functions [28], which asymptotically match the upper bounds for OneMax and LeadingOnes functions. □

MULTIMODAL FUNCTIONS WHERE ADAPTATION IS ADVANTAGEOUS
We will now focus on the two multi-modal benchmark functions that require different values to be optimised effectively. Our adaptive mechanism allows the value to drop to its minimum when on the local optima of either Jump or Cliff. While high mutation rates (i.e., low values) are necessary to solve the Jump function effectively, for the Cliff counterpart it is critical to flip as few bits as possible to avoid sampling solutions from the first slope. This is easily achieved by the adaptive mechanism which sets = (log ) 2 as soon as an improvement is found on the second slope of the Cliff function. Proof. We first prove the upper bound for the Jump function. The function is identical to OneMax until one of the local optima (i.e., a solution with − 1-bits) is sampled because whether we initialise with fewer than or more than − bits we can regardless use ( − OneMax ( ))/ as a lower bound on the probability of improving any solution except the global or local optima. Thus, we use the upper bound from Theorem 1 to conclude that in expected ( log ) iterations after any uniformly random initialisation, we sample a local optimum. Pessimistically assuming that the hypermutation fails to sample the optimum (which is the only solution that improves a local optimum) for times after the local optimum is sampled, for the remaining − ≥ /2 = Ω( log ) iterations we have = 1. With = 1 the probability that the hypermutation samples the optimal solution is Ω ( log ) −1 −1 since with probability at least Ω(1/( · log )), bits will be flipped and given that bits are flipped, the probability that the optimum is sampled is at least −1 . The expected waiting time until the event occurs is the reciprocal of this probability, log . If the ageing triggers while the current best is at the local optimum, we repeat our argument that in ( log ) iterations we reach the local optimum and attempt Ω( log ) times to sample the global optimum, which implies that in expectation it is necessary to climb the OneMax slope log /Ω( log ) times. Since climbing the OneMax slope takes at most ( log ) times, the expected waiting time is still in the order of log . Following the same arguments we can also find that when ∈ [1 + , (log ) 2 ], the upper bound is 1+ since the probability of flipping bits changes from Ω( 1 ·log ) to Ω( −1− ). For Cliff, the expected time to reach the local optima is the same as above, i.e., ( log ). Now, ageing is triggered after iterations and then, since = min due to the time spent on the local optima, with probability Ω log if min = 1 and with probability Ω ( / ) if min = 1 + , a solution with more 1-bits is sampled in the same iteration. In the following ageing phase, with constant probability, the parent solution is removed from the population while the offspring is spared. In the following iteration, the survived individual improves again with probability Ω log or Ω depending on whether min is equal to 1 or 1 + respectively and sets its age to zero and = (log ) 2 . Since each solution with more than − 1-bits has at least one Hamming neighbour with better fitness value, following the same arguments of the proof of Theorem 1 we conclude that with probability 1 − ( −2 ), > log between two consecutive improvements. Since there are at most improvements, by the union bound the probability that > log until the optimum is found is at least 1 − ( −1 ) Next, we will bound the conditional probability that a solution with at most − 1-bits is sampled before the optimum is found given that the current solution has at least − + 2 1-bits and that > log . First, we will bound the probability that a mutation flips a specific number of bit positions. Since > log , the probability of flipping exactly two positions is (2 − log ) = (1/ ), three positions is (3 − log ) = (1/ ), 4 to 8 positions is (4 · 4 − log ) = (1/ 2 ) and more than 8 positions is at most ( · 8 − log ) = (1/ 2 ). Therefore, given that the improvement probability is at least Ω(1/ ) the probability of obtaining a solution with − + 3 1-bits before flipping two bits is a constant. Then, the probability of obtaining a solution with − + 4 1-bits before flipping three bits is in the order of 1 − (1), the probability of obtaining a solution with − + 8 1-bits given that the current solution has at least − + 4 1-bits is at least 1 − (1/ ). Finally, given that we obtain a solution with − + 8 1-bits, the probability of improving before flipping at least 8 bit positions is at least 1 − (1/ 2 ). Thus, the probability of improving times before we flip at least 8 bits is at least 1 − (1/ ) by the union bound. Combining the failure probabilities, we conclude that with constant probability we sample the optimum before sampling a solution with at most − 1-bits. If any of the failures occur we pessimistically assume that the current solution is reinitialised and then the local optima is sampled before the global optimum. Considering that once a local optimum is found and the ageing mechanism is triggered in ( log ) + = ( ) iterations afterwards, we also find the optimal solution before reinitialisation with probability Ω( 2 /( · log ) 2 ) (Ω( 2 / 2 ) if min = 1 + ) in expected ( log ) iterations. Thus, the total expected runtime can be bounded above by · ( log ) 2 2 and ( · 2 2 ) respectively. □

MULTIMODAL FUNCTIONS WHERE ADAPTATION IS NECESSARY
In this section, we will introduce the CliffWithBasin pseudo-Boolean function where it is necessary to make larger jumps to solutions of lower quality compared to the standard Cliff function. This function will allow us to illustrate how the adaptive hypermutation algorithms are more effective in more challenging multimodal optimisation scenarios where it may be convenient to make large jumps to solutions of lower quality to escape efficiently from local optima. In particular we present a more general multimodal function that they can efficiently optimise while the state-of-the-art hypermutation operators with static parameter have at least super-polynomially worse performance. The function is illustrated in Fig. 3 and is defined as:  CliffWithBasin a : {0, 1} → R is defined as follows: The function has two parallel slopes with the second slope having worse fitness as in the Cliff function while it is necessary to flip exact bit position to move from one slope to the other. Unlike the Cliff function the slopes consist only of Ridge points, which have the form 1 0 − for some ∈ { /2, . . . , }. The rest of the search space has gradients that serve to lead the current solution either to the point 1 /2 0 /2 which is the beginning of the first slope or to the local optima ℓ := 1 1 0 − 1 , i.e., the point with the highest fitness on the first slope. All solutions which have between 1 + 1 and 2 1-bits (i.e., solutions) have smaller fitness values than the local and the global optima but higher than any other solution. 1 The names of the sets , , , , abbreviate: first slope, second slope, basin of attraction, leading ones and n-half, respectively. This basin of attraction forces the algorithms to make a very precise mutation to reach the second slope. Moreover, since the second slope has lower fitness values, even if a solution from the second slope is sampled, it is highly likely that it is mutated into a solution in the basin of attraction, preventing the algorithm from following the second slope to the global optimum. These characteristics make the function particularly challenging for both elitist and non-elitist algorithms. For instance Metropolis would fail to access the second slope of increasing fitness in polynomial expected time due to the large difference in fitness gradient while the Move-Acceptance nonelitist hyper-heuristic would likely require an expected runtime in the order of ( 2 ) to cross the basin [29].
In the following theorem, we show that constant values lead to exponential runtime bounds for the CliffWithBasin function. In particular, constant values cause the hypermutation operator to flip many bits too frequently such that, with overwhelming probability, a solution in the second slope is mutated into a solution before the global optimum is reached. Proof. In order to prove the lower bound on the runtime, we will bound from below the probability of the algorithm reinitialising (i.e., starting a generation with random solution uniformly distributed over the {0, 1} hyperspace) before sampling the optimal solution. We will denote this event as E 0 and use the law of total probability to analyse the conditional probabilities of this event given the age ( ) and the genotype ( ) of the current solution at iteration . Let ℓ := 1 1 0 − 1 . We will start with the conditional probability of the E 0 given that = ℓ, and define E 1 as the event of the algorithm sampling the 1 bit-string in the generations following generation : Pr We will next bound the probability that any solution in is mutated into the 1 string in a single mutation operation. This mutation requires − 1 precise bits to be flipped by the operator and its probability is at most − 1 = −Ω ( ) since even if the mutation operator picks the correct number of bits to be flipped with probability 1, it has to pick each of these − 1 positions correctly among alternatives. We can use the union bound to establish that for any = ( ), When ≥ both the current solution and any offspring solution with equal or less fitness than the parent are each removed from the population with probability 1/2. We first condition on the new offspring having improved the solution which only happens when the global optimum is sampled which has probability −Ω ( ) and allows us to absorb the conditional probability into the (1 − −Ω ( ) ) factor. Then, we condition on which individuals are removed from the population. If the parent survives, then in the next generation the conditional probability is equal to Pr (E 0 | = , = ℓ) since we repeat the same experiment in the next iteration. If both individuals die, then the event E 0 occurs. Finally, if only the offspring individual survives we denote the resulting event as E and obtain: Pr Next, we will condition on which subspace the survived individual belongs to. For any constant * < 1/2, the probability of mutating from any solution with less then 2 1-bits (which includes all the named sets except ) to any point in with at least 2 + * / 2 1-bits (a safe solution) or to the optimal 1 bit-string is at most * / 2 −1 = −Ω ( * / ) . Conditioning on that this event does not happen, if the survived individual has more than (1 + )/2 1-bits and does not belong to , , , , or then the uniformly initialised individuals will have a better fitness than the offspring with overwhelmingly high probability and event E 0 will occur. Moreover, all solutions in {0, 1} \( ∪ {1 }) has a sequence of ( 2 ) local improvements that lead them to ℓ while the probabilities for the mutation to sample a safe solution or the optimum is at most −Ω ( * / ) . Thus, with overwhelming probability ℓ is sampled before the global optimum.
If the current individual is in and has less than 2 + * / 2 1-bits, then the number of 1-bits after the next mutation is | +1 | 1 = | | 1 + − ( − ) = − +2 , where = ( , , | | 1 ) denotes the number of 0-bits that are flipped to 1. Since the number of 1-bits in the solution is at least · 1 2 + , there exists a mutation size ∈ ( / ) such that the nearest integer to the expected number of 1-bits after the operation is exactly 2 − 1. Since the hypergeometric distribution is symmetric around (and increasing towards) its mean, the probability that its outcome is in ± is constant. Since the standard deviation of is ( √ ), some · √ integers around the mean share the constant probability in a way that the integers closer to the mean have a larger share. Consequently the integer closest to the mean has a probability of Ω( −1/2 ). Considering that the probability of picking the correct mutation size is in the order of Ω − * / and ≥ 1, with probability Ω( − 1 2 − * ) a solution from is sampled and accepted due to its higher fitness. In order to improve fitness by increasing the leading ones, at least a particular bit position needs to be flipped which happens with probability (1/ ). Thus, the conditional probability of improving to another solution before reaching is at most in the order of ( −1/2+ * ). In order to reach a solution with 2 · * / leading ones, given that the initial solution has less than * / ones, this conditional event needs to occur at least ( * / ) times which happens with probability −Ω ( * / ) . Pr Next, we will consider the probability Pr (E 0 | = 0, ∈ , E ). For any solution, the only search points with higher fitness are either the global optimum or those belonging to either ℓ or . However, there is a local gradient towards and ℓ while the improvement to the global optimum has a probability ( −Ω ( ) ). Thus, with overwhelming probability the process ends up in either ℓ or . Similarly, individuals in can only improve into the global optimum or to ℓ thus with overwhelming probability reaches before the global optimum. Pr Now we can sequentially replace the conditional probabilities with the bounds obtained up to (8) while combining the factors in the form into (1 − −Ω ( / ) ) via the union bound: We can now conclude our proof by showing that after a reinitialisation the algorithm samples ℓ before the global optimum with overwhelming probability. With probability 1 − −Ω ( ) the newly initialised solutions have 2 ± 2/3 1-bits in their strings due to Chernoff Bounds on binomially distributed variables [15]. Thus, the Hamming distance to the optimal solution and the solutions are in the order of Ω( ) since all those solutions have at least 1 ≥ 1 2 + 1-bits. In the iterations until the algorithm samples ℓ (which takes ( 2 ) in expectation ), the probability of sampling the optimum is in the order of −Ω ( ) . The probability of sampling an initial solution with more than 2 ± 2/3 1-bits has a larger failure probability than reinitialisation after ℓ is sampled, thus determines the lower bound on the expected number of reinitialisation before the optimum is found as Ω ( ) . □ Next, we focus on the mutation from the local optimum 1 1 0 − 1 to any solution on the second slope. Thus, we obtain a lower bound on the runtime by finding how many times the algorithm has to restart to successfully sample the first solution on the second slope. While the theorem holds for all values, it implies that when := 2 − 1 = Ω( ) for any constant > 0, superconstant values lead to expected runtimes that are superpolynomially smaller than the expected times for constant (Theorem 3). The speed of the adaptive variants lies in their ability to use = 1 when the algorithm is stuck at the optima, which increases the probabilty of picking the correct mutation size, while at the same time using a very high > log on the second slope where flipping many bits brings a high risk of sampling a solution from the basin of attraction of the local optima. Proof. We use the same notation and follow the same arguments in the proof of Theorem 3 to establish that with overwhelming probability a newly initialised solution reaches the local optimum before the optimum. Next, we will consider the conditional probability Pr (E 0 | = , = , E ), i.e., given an offspring in survived while the parent is removed. The probability that the survived individual ∈ has at least 1 + leading ones for any ∈ [ ] is at most ( − · − log ) since the parent of is ℓ with exactly 1 leading ones. The probability of decreasing the number of 1-bits in a generation is Ω(1) while the probability of sampling a solution in is ( − + · ( − ) − log ). If a solution from is sampled, then it is still necessary that another improvement occurs so that the solution is not removed from the population, which has probability Ω(1/ ) for all points in . Once an improvement occurs in , the age of the offspring is reset to zero and since individuals in have higher fitness than those in , the only acceptable solution that will increase the Hamming distance to ℓ is the global optimum. Thus, Now, we can follow the same arguments as in Theorem 3 and replace the conditional probabilities sequentially to obtain the Since after a reinitialization it takes Ω( 2 ) to reach ℓ, our claim follows. □ Finally we show that by adapting the parameter during the run, the algorithms can optimise the CliffWithBasin function efficiently. The adaptive algorithms use the minimal values at the local optimum that minimise the lower bound from Theorem 6 while increasing the value on the second slope avoids the exponential runtime proven for fixed = (1) in Theorem 5.
Proof. We will first bound the expected time until the local optimum 1 1 0 − 1 is sampled for the first time. When a solution is randomly initialised, the number of 1-bits in its bit-string is distributed binomially with parameters and 1/2. With overwhelming probability, the initial solution has 2 ± 2/3 1-bits in its string due to Chernoff Bounds on binomially distributed variables [15]. Let := {0, 1} \ ( ∪ ∪ ∪ ∪ ) be the set of solutions where the CliffWithBasin function is evaluated as | 2 − OneMax ( )| −1 . For any solution ∈ the probability of improving the function value is at least 1/2 given that the hypermutation operator flips only a single bit position. Pessimistically assuming that = 1, we can bound the expected time until the algorithm samples a solution with better fitness by (log ) due to the probability of flipping a single bit and the expected time until a solution in is sampled by ( 2/3 log ) expected function evaluations since with overwhelming probability the initial solution has /2 ± ( 2/3 ) 1-bits. Using the law of total expectation as in Theorem 1 we can conclude that the expected time to sample a solution in , given that the initial solution is in is at most ( 2 ) in expectation since all individuals in have a Hamming neighbour with better fitness and only ( ) different fitness values. We can then extend the same argument to the progress in and establish that it takes ( 2 ) iterations after a uniformly random initialisation in expectation to sample the local optimum for the first time.
At the local optimum of CliffWithBasin (i.e., 1 1 0 − 1 ), we will pessimistically assume that we do not find the optimum in steps and have = 1 when the ageing triggers. Similarly to the arguments in Theorem 2 the probability that the parent is removed from the population while the offspring survives is a constant. We differ from the previous theorem's argument here since at the same iteration that the parent individual is removed from the population, the offspring must precisely be 1 0 − for some > 2 which occurs if at least 2 − 1 precise bits are flipped by the hypermutation with probability Ω ( log ) −1 −1 . In the following iteration with probability 1/ log we find a second improvement and reset our age to zero and set = (log ) 2 . Once a solution of the form 1 0 − for > 2 is sampled, the arguments for the constant probability of finding the optimal solution before sampling a solution with less than 2 1-bits, follows the arguments in Theorem 2 for the Cliff function. Since the time to reach the local optimum after reinitialisation is in the order of ( 2 ) and the probability of improving twice after ageing triggers is Ω ( log ) −1 −1 · ( log ) −1 , our claim follows. □ Similarly to Theorem 4 if we use min = 1 + for some constant > 0, the runtime changes by a factor of 2 /(log ) 2 .

CONCLUSION
In recent years, power-law mutation operators have gained increasing interest in the randomized search heuristics community. The reason is that, compared to the traditional binomially distributed mutation operators, they have been shown to provide exponential speed-ups at escaping from local optima that require large mutations while still exhibiting asymptotically optimal hillclimbing performance. Heavy-tailed mutations may become detrimental, though, when used together with some form of non-elitism which may be useful to overcome local optima by accepting solutions of lower quality. In this paper we have shown how such disadvantages may be overcome by automatically adapting the power-law distribution during the run so to learn to decrease the mutation rate once local optima have been escaped from. While we have used standard multimodal benchmark functions with significant structures to explain the scenarios where the adaptive algorithms may considerably improve the performance over static binomial and power-law mutation operators and have provided rigorous evidence of their superiority for all problems where the performance of the heavy-tailed operators is known (and wider classes), our results also easily extend to the NP-Hard Number-Partitioning problem since both ageing and hypermutations are effective for identifying arbitrarily good approximations [9]. Future work should further evaluate experimentally and theoretically the performance of the proposed algorithms on classical combinatorial optimization problems and real-world applications. We note that recently a different self-adjusting mechanism has been proposed in the literature with the aim of increasing the standard bit mutation rate of evolutionary algorithms when detecting local optima [35]. While the mechanism was not designed with the aim of enhancing the non-elitist performance of search heuristics as well as the mutation operator in the presence of local optima, a comparison with our own proposed mechanism should be performed in the near future.