On the Benefits of Populations on the Exploitation Speed of Standard Steady-State Genetic Algorithms
Dogan Corus Pietro S. Oliveto


Benefits of Populations on the Exploitation Speed of Steady-State GAs]On the Benefits of Populations on the Exploitation Speed of Standard Steady-State Genetic Algorithms
















It is generally accepted that populations are useful for the global exploration of multi-modal optimisation problems. Indeed, several theoretical results are available showing such advantages over single-trajectory search heuristics. In this paper we provide evidence that evolving populations via crossover and mutation may also benefit the optimisation time for hillclimbing unimodal functions. In particular, we prove bounds on the expected runtime of the standard (μ+1) GA for OneMax that are lower than its unary black box complexity and decrease in the leading constant with the population size up to μ=O(√(log n)). Our analysis suggests that the optimal mutation strategy is to flip two bits most of the time. To achieve the results we provide two interesting contributions to the theory of randomised search heuristics: 1) A novel application of drift analysis which compares absorption times of different Markov chains without defining an explicit potential function. 2) The inversion of fundamental matrices to calculate the absorption times of the Markov chains. The latter strategy was previously proposed in the literature but to the best of our knowledge this is the first time is has been used to show non-trivial bounds on expected runtimes.






[
    Carlos Feinstein,^1,2, Gustavo Baume^1,2, Jimena Rodríguez^1,2, and Marcela Vergne^1,2
  ^1Facultad de Ciencias Astronómicas y Geofísicas, Observatorio Astrónomico, UNLP, La Plata, Argentina; cfeinstein@fcaglp.unlp.edu.ar
  ^2Instituto de Astrofísica de La Plata - CONICET
    December 30, 2023
====================================================================================================================================================================================================================================================================================



  

§ INTRODUCTION





































Populations in evolutionary and genetic algorithms are considered crucial
for the effective global optimisation of multi-modal problems. For this to be the case,
the population should be sufficiently diverse such that it can explore multiple regions of the search space at the same time <cit.>.
Also, if the population has sufficient diversity,
then it considerably enhances the effectiveness of crossover for escaping from local optima.
Indeed the first proof that crossover can considerably improve the performance of GAs 
relied on either enforcing diversity by not allowing genotypic duplicates or by using unrealistically small crossover rates for the function <cit.>.
It has been shown several times that crossover is useful to GAs using the same, or similar, diversity enhancing mechanisms for a range of optimisation problems
including shortest path problems <cit.>, vertex 
cover <cit.>, colouring problems inspired by the Ising 
model <cit.> and computing input output sequences in finite state 
machines <cit.>. 

These examples provide considerable evidence that,  by enforcing the necessary diversity, crossover makes GAs effective and often superior to applying mutation alone.
However, rarely it has been proven that the diversity mechanisms are actually necessary for GAs, or to what extent they are beneficial to outperform their mutation-only counterparts rather than being applied
to simplify the analysis. 
Recently, some light has been shed on the power of standard genetic algorithms without diversity over the same algorithms using mutation alone. 
Dang et al. showed that the plain is at least a linear factor faster than its (μ+1) EA counterpart at escaping the local optimum of  <cit.>.
Sutton showed that the same algorithm with crossover if run sufficiently many times is a fixed parameter tractable algorithm for the closest string problem while without crossover 
it is not <cit.>.
Lengler provided an example of a class of unimodal functions to highlight the robustness of the crossover based version with respect to the mutation rate compared to the mutation-only version
i.e., the is efficient for any mutation rate c/n while the (μ+1) EA requires exponential time as soon as approx. c>2.13 <cit.>.
In all three examples the population size has to be large enough for the results to hold,
thus providing evidence of the importance of populations in combination with crossover.


Recombination has also been shown to be very helpful at exploitation if the necessary diversity is enforced through some mechanism.
In the (1+(λ,λ)) GA such diversity is achieved through large mutation rates. The algorithm
can optimise the well-known function in sublogarithmic time with static offspring population sizes λ <cit.>, and in linear time with self-adaptive values of λ <cit.>.
Although using a recombination operator, the  algorithm is still basically a single-trajectory one (i.e., there is no 
population). More realistic steady-state GAs that actually create offspring by 
recombining parents 
have also been analysed for . 
Sudholt showed that (μ+λ) GAs are twice as fast as their 
mutation-only version (i.e., no recombination) for if diversity is 
enforced artificially i.e., genotype duplicates are preferred for deletion <cit.>. He proved a runtime of  (e/2) n ln n 
+O(n) versus the  e n ln n +O(n) function evaluations required by any 
standard bit mutation-only evolutionary algorithm for and any other linear 
function <cit.>. 
If offspring are identical to their parents it is not necessary to evaluate the quality of their solution. 
When the unnecessary queries are avoided,  the expected runtime of the GA using 
artificial diversity from <cit.> is bounded above by (1+o(1)) 
0.850953 n lnn <cit.>. 
Hence, it is faster than any unary (i.e., mutation-only)
unbiased  [The probability of a bit being flipped by an unbiased 
operator is the same for each bit-position.] black-box search heuristic <cit.>

On one hand, the enforced artificiality in the last two results considerably 
simplifies the analysis. On the other hand, the power of evolving populations 
for 
effective optimisation cannot be appreciated.  
Since the required diversity to 
make crossover effective is artificially enforced,  the optimal 
population size is 2 and larger populations provide no benefits. 

Corus and Oliveto showed that the standard without diversity is still faster than mutation-only ones by proving 
an upper bound on the runtime of (3/4) e n ln n +O(n) for any 3< μ < o(log n / loglog n) <cit.>. A result of 
enforcing the diversity in <cit.> was that the best GA for the problem only used a 
population of size 2. However, even though this artificiality was removed in 
<cit.>, a population of size 3 was 
sufficient to get the best upper bound on the runtime achievable with their analysis. 
Overall, their analysis does not indicate any tangible benefit towards using a population larger than μ=3. Thus, rigorously showing that populations are beneficial for GAs
in the exploitation phase has proved to be a non-trivial task.






In this paper we provide a more precise analysis of the behaviour of the population of the for .










We prove that the standard is at least  60% faster than the same algorithm using only mutation. 
We also prove that the GA is faster than any unary
unbiased 
 black-box search heuristic 
if offspring with identical genotypes to their parents are not evaluated. 

More importantly, our upper bounds on the expected runtime decrease 
with the population size up to μ =o(√(log n)), 

thus providing for the first time a natural example where 
populations evolved via recombination  and mutation optimise faster than unary unbiased heuristics. 








§ PROBLEM DEFINITION AND OUR RESULTS































 §.§ The Genetic Algorithm



The is 
 a standard steady-state GA which samples a single 
new solution at every generation <cit.>. It keeps a population of the μ best 
solutions sampled so far and at every iteration selects two solutions from the current 
population uniformly at random with replacement as the parents. The 
recombination operator then picks building blocks from the parents to 
create the offspring solution. For the case of pseudo-Boolean functions 
f:{0,1}^n →, the most frequently used recombination 
operator is uniform crossover which picks the value of each bit 
position i∈ [n] from one parent or the other uniformly at random (i.e., from each parent with 
probability 1/2) <cit.>. Then, an unbiased unary 
variation operator, which is called the mutation operator, is applied to 
the offspring solution before it is added to the population. The most common 
mutation operator is the standard bit-mutation which independently flips each 
bit of the offspring solution with some probability c/n 


<cit.>. Finally, before moving to the next 
iteration, one of the solutions with the worst fitness value is removed from 
the population. For the case of maximisation the is defined in 
Algorithm <ref>. The runtime of Algorithm <ref> is the 
number of function evaluations until a solution which maximises the function 
f is sampled for the first time. If every offspring is evaluated, then the 
runtime is equal to the value of the variable t in Alg. <ref> when 
the optimal solution is sampled. However, if the fitness of offspring which are 
identical to their parents are not evaluated, then the runtime is smaller than 
t. We will first analyze the former  scheme 	and then adapt the result to the 
latter. 
 [t] 
      <cit.>
    
   
    P_1 μ individuals, uniformly at random from {0, 
1}^n  
tμ 
    optimum is found
    
            Select x, y ∈ P_t uniformly at random with replacement  
            z uniform crossover(x, y) 
            z  mutate(z)   
	    P_t+1 P_t ∪{z} 
	    Remove the element with lowest fitness from P_t+1, breaking 
ties at random  
    t  t+1;
    
     










 §.§ The Optimisation Problem





Given a secret bitstring z ∈{0,1}^n, _z(x) :={ i ∈ [n] | z_i = x_i } returns the number of 
bits on which a candidate solution x ∈{0,1}^n matches z 
<cit.>. The 
optimisation time (synonymously, runtime)  is defined by the 
number of queries to the function required by an algorithm to minimise the 
Hamming distance between the candidate solution and the hidden bitstring z. 



 §.§ Our Results


In this paper we prove the following results.


 
 The expected runtime for the (
 with unbiased mutations and  population size 
μ=o(√(logn)) to optimise
the function is




  * E[T]≤ (1+o(1))n lnn·γ_1 (μ, p_0, p_1, p_2),  


if offspring identical to their parents are not evaluated for 
their quality is known and p_0, p_1, and p_2 are respectively the 
probabilities that  zero, one or two bits are flipped, 
[Theorem <ref>, Section <ref>] 


  * E[T]≤ (1+o(1))n lnn·γ_2(μ, c),  

 if the quality of all offspring is 
evaluated and using standard bit mutation 


with rate c/n, c ∈Θ(1), [Corollary <ref>, Section <ref>]








where γ_1 and γ_2  are decreasing functions 
of the population size μ.


  

The above two statements are very general as they provide  upper bounds on the 
expected runtime of the for each value of the population size up to 
μ=o(√(logn)) and any unbiased mutation operator. 

The leading constants γ_1 and γ_2 in Statements 1 and 2 are 
plotted respectively in Fig. 
<ref> and <ref> for different population sizes using 
the  p_0, p_1, p_2 and c values which minimise the 
upper bounds. 
The result is significant particularly for the following three reasons (in order of increasing importance).

(1) The first statement shows how the genetic algorithm 
outperforms any unbiased mutation-only heuristic since the best expected 
runtime achievable by any algorithm belonging to such class is at least
n ln n - cn ± o(n)  <cit.>. Given that the best expected 
runtime achievable with any search heuristic using only standard bit mutation is 
(1+o(1)) e n lnn <cit.>, the second statement shows how by adding 
recombination a speed-up of 60% is achieved for the problem for any population size up to μ=o(√(logn)). 














(2) Very few results are available proving constants in the leading  terms of the expected runtime for randomised 
algorithms due to the considerable technical difficulties in deriving them. 
Exceptions exist such as the analyses of
 <cit.> and 
<cit.> without which our comparative results would not have been 
achievable.  
While such precise results are gaining increasing importance in the 
theoretical computer science community, the available ones are related to more 
simple algorithms. 

This is the first time similar results are achieved 
concerning a much more complicated to analyse standard genetic algorithm using 
realistic population sizes and recombination. 



(3) The preciseness of the analysis allows for the first time an 
appreciation of the surprising importance of the population for optimising 
unimodal functions [Populations are traditionally thought to be useful 
for solving multi-modal problems.] as our upper bounds on the expected runtime 
decrease as the population size increases. In particular as the problem size 
increases, so does the optimal size of the population (the best known runtime 
available for the was of  (1+o(1)) 3/4 e n ln n independent of the 
population size as long as it is greater than μ=3 i.e., there were no 
evident advantages in using a larger population <cit.>). This 
result is in contrast to all previous analyses of simplified evolutionary 
algorithms for unimodal functions where the algorithmic simplifications, made 
for the purpose of making the analysis more accessible, caused the use of 
populations to be either ineffective or  detrimental <cit.>. 
Our upper bound of  μ=o(√(logn)) 

is very 
close to the at most logarithmic population sizes typically recommended 
for monotone functions to avoid detrimental 
runtimes <cit.>. We conjecture that the optimal population 
size is Θ(log n^1 - ϵ) for any constant ϵ>0,  which 
cannot be proven with our mathematical methods for technical reasons. 



 §.§ Proof Strategy

Our aim is to provide a precise analysis of the expected runtime of the for optimising with arbitrary problem size n. Deriving the exact 
transition probabilities of the algorithm from all possible configurations to 
all others of its population is prohibitive. We will instead 
devise a set of n Markov chains, one for each improvement the algorithm has to 
pessimistically make to reach the global optimum, which will be easier to 
analyse. Then we will prove that the Markov chains are slower to reach their 
absorbing state than the is in finding the corresponding improvement. 

In essence, our proof strategy consists of: (1) to identify suitable Markov 
chains, (2) to prove that the absorbing times of the Markov chains are larger 
than the expected improving times of the actual algorithm and (3) to bound the 
absorbing times of each Markov chain.

In particular, concerning point (2) we will first define a potential function 
which monotonically increases with the number of copies of the 
genotype with most duplicates in the population and then bound 
the expected change in the potential function at every iteration (i.e., 
the drift ) from below. Using the maximum value of the potential function 
and the minimum drift, we will bound the expected time until the potential 
function value drops to its minimum value for the first time. This part of the 
analyses is a novel application of drift analysis 
techniques <cit.>. In particular, 
rather than using an explicit distance function as traditionally occurs, we 
define the potential function to be equal to the conditional expected absorption 
time of the corresponding states of each Markov chain.

Concerning point (3) of our proof strategy, we will calculate the absorbing 
times of the Markov chains M^j by identifying their fundamental matrices. This 
requires the inversion of tridiagonal matrices. Similar matrix manipulation 
strategies to bound the runtime of evolutionary algorithms have been previously 
suggested in the literature <cit.>. However, all 
previous applications showed that the approach could only be applied to prove 
results that could be trivially achieved via simpler standard methods. To the 
best of our knowledge, this is the first time that the power of this long 
abandoned approach has finally been shown by proving non-trivial bounds on the 
expected runtime.


















































































































 

 
 
 
 

§ MAIN RESULT STATEMENT

 
 Our main result is the following theorem. The transition probabilities  
p_i,k for (i,k)∈ [m]^2 and m:=⌈μ/2⌉ are defined in 
Definition <ref> (Section <ref>) and are depicted in 
Figure <ref>. 
 
 theoremmainone
 
 

 The expected runtime for the with μ=o(√(logn)) using an 
unbiased mutation operator mutate(x) that flips i bits with probability 
p_i with p_0 ∈Ω(1) and p_1 ∈Ω(1) to optimise the function is:


 
 
  * E[T]≤ (1+o(1))n lnn1/p_1 +  p_2  2(1-ξ_2) 
μ/(μ+1) if the quality of each offspring is evaluated, 
 
 
  * E[T]≤ (1+o(1))n lnn(1-p_0) /p_1 +  p_2  
2(1-ξ_2) μ/(μ+1) if the quality of offspring identical to their 
parents is not evaluated for their quality is known; and 


    ξ_i=p_i-1,i-2/p_i-1,m+p_i-1,i-2 + p_i-1,i(1-ξ_i+1) ,
       ξ_m=p_m-1,m-2/p_m-1,m+p_m-1,m-2.







The recombination operator of the GA is effective only if individuals with 
different genotypes are picked as parents (i.e., recombination cannot 
produce any improvements if two identical individuals are recombined). 
However, more often than not, the population of the consists only 
of copies of a single individual. 
 When diversity is created via mutation  (i.e., a new genotype is added to the 
population), it either quickly leads to an improvement or it quickly 
disappears. The bound on the runtime reflects this behaviour as it is simply a 
waiting time until one of two event happens; either the current individual is 
mutated to a better one 

or diversity emerges 

and leads to an improvement before it is lost.



The  ξ_2 term in the runtime is the conditional probability that once 
diversity is created by mutation, it will be lost before reaching the next 
fitness level (an improvement). Naturally, (1-ξ_2) is the 
probability that a successful 
crossover will occur before losing diversity. The (1-ξ_2) 
factor increases with the population size μ, which implies that larger 
populations have a higher capacity to maintain diversity long enough to be 
exploited by the recombination operator. 














Note that setting p_i:=0 for all i>2 minimises the upper bound on the 
expected runtime in the second statement of Theorem <ref> and reduces 
the bound to: E[T]≤ (1+o(1))n lnn (p_1 + p_2)/(p_1  +  p_22μ(1-ξ_2)/μ+1). Now, we can see the critical role that 
ξ^*(μ)=(1-ξ_2)μ/(μ+1) plays in the expected runtime. For any 
population size 
which yields ξ^*(μ)≤ 1/2, flipping only one bit per mutation  becomes 
advantageous. The best upper bound achievable from the above expression is then 
(1+o(1))n lnn by assigning an arbitrarily small constant to  p_0 and  
p_1=1-p_0. As long as p_0=Ω(1), when an improvement occurs, the 
superior 
genotype takes over the population quickly relative to the time between 
improvements. Since there are only one-bit flips, the crossover operator 
becomes virtually useless (i.e., crossover requires a Hamming distance of 2 
between parents to create an improving offspring) and the resulting algorithm is 
a stochastic local search algorithm with a population. However, when ξ^*(μ)>1/2 
setting p_2 as large as possible provides the best upper bound. The  
transition for ξ^*(μ) happens between population sizes of 4 and 5. For 
populations larger than 5, by setting p_1:=ϵ/2 and p_0=:ϵ/2 to 
an arbitrarily small constant 
ϵ and setting p_2=1-ϵ, we get the upper bound E[T]≤ 
(1+o(1))(1+ϵ)n 
lnn(μ+1)/(2μ(1-ξ_2)), which is 
plotted for different population sizes in Figure <ref>. 











 




 













 












































A direct corollary to the main result is the upper bound for 
the classical commonly used in evolutionary computation which 
applies standard bit mutation with mutation rate c/n for which 
p_0=(1-o(1))/e^c, p_1=(1-o(1))c/e^c and p_2=(1-o(1))c^2/(2 e^c).





Let ξ_2 be as defined in Theorem <ref>. The expected runtime for 
the with μ=o(√(logn)) using standard bit-mutation with 
mutation 
rate c/n, c=Θ(1) to optimise the function is:


 
 
  * E[T]≤ (1+o(1))n lnne^c/c+  c^2 μ/(μ+1)    
(1-ξ_2) if the quality of each offspring is evaluated, 
 
 
  * E[T]≤ (1+o(1))n lnn(1-e^-c)e^c/c+  c^2 
μ/(μ+1)    (1-ξ_2) if the quality of offspring identical to their 
parents is not evaluated for their quality is known;





By calculating ξ^*(μ):=(1-ξ_2)μ/(μ+1) for fixed values of μ we can 
determine values of c (i.e., mutation rate) which minimise the leading 
constant of the runtime bound in Corollary <ref>. In 
Figure <ref> we plot the leading constants in the first 
statement, minimised by picking the appropriate c values for μ ranging 
from 5 to 50. All the values presented improve upon the  upper bound on the 
runtime of 1.96 n lnn given in <cit.> for any μ≥ 
3 
and μ = o(logn/loglogn). All the upper bounds are less than 1.7 n 
lnn and clearly decrease with the population size, signifying an at least 
60% increase in speed compared to the e n 
lnn(1-o(1)) lower bound for the same algorithm 
without the recombination operator.









Considering the leading constants in the second statement of 
Corollary <ref>, for all population sizes larger than 5, the upper bound 
for the optimal mutation rate is smaller than the theoretical 
lower bound on the runtime of unary unbiased 
black-box algorithms. For population sizes of 3 and 4,   ξ^*=1/3 and the 
expression to be minimised is (1-e^-c) e^c/(c+ c^2/3). For c>0, this 
expression has no minimum and is always larger than one. Thus, at least with our 
technique, a population of size 5 or larger is necessary to prove that the outperforms stochastic local search  and any other unary unbiased 
optimisation heuristic.













































§ ANALYSIS

 
Our main aim is to provide an upper bound on the expected runtime (E[T]) of 
the defined in Algorithm <ref> to maximise the function.

W.l.o.g. we will assume that the target string z of the  function to 
be identified is the bitstring of all 1-bits since all the operators in the are invariant to the bit-value (have no bias towards 0s or 1s). We will 
provide upper bounds on the expected value E[T^j], where T^j is the time 
until an individual with at least j+1 1-bits is sampled for the first time 
given that the initial population consists of individuals with j 1-bits (i.e., the population is at level j).  
Then, by summing up the values of E[T^j] and the expected times for the whole 
population to reach j+1 1-bits for j∈{1…,,n-1} we achieve a valid 
upper bound on the runtime of the . Similarly to the analysis in 
<cit.>, we will pessimistically assume that the algorithm is 
initialised with all individuals having just 0-bits, and that throughout the 
optimisation process at most one extra 1-bit is discovered at a time. 




We will devise a Markov chain M^j for each j∈{0, …,n -1 } 
for which we can analyse the expected absorbing time E[T_i^j] starting 
from state S_i^j. We will then prove that it is in expectation slower in 
reaching its absorbing state than the is in finding an improvement given 
an initial population at level j. 































In particular, we will define a non-negative potential function 
on the domain of all possible configurations of a population at level j or 
above. For any configuration at level j, we will refer to the genotype with 
the most copies in the population as the majority genotype and define the 
diversity of a population  as the number of non-majority individuals in 
the population. Our potential function will be monotonically decreasing with 
the diversity. Moreover, we will assign the potential function  a value of zero for 
all populations with at least one solution which has more than j 1-bits.




Then, we will bound the expected change in the potential function at every 
iteration (i.e., the drift) from below. Using the maximum value of the 
potential function and the minimum drift, we will derive a bound on 



the expected time until an improvement is found starting from a 
population at level j with no diversity (i.e., all the solutions in the 
population are identical). While this 
upper bound will not provide an explicit runtime as a function of the problem 
size, it will allow us to conclude that the E[T_0^j]≥ E[T^j]. Thus, 
all that remains will be to bound the expected absorbing time of M^j 
initialised at state S_0^j. We will obtain this bound by  identifying 
the fundamental matrix of M^j. After establishing that the inverse of the fundamental 
matrix is a strongly diagonally dominant tridiagonal matrix, we will make 
use of existing tools in the literature for inverting such 
matrices and complete our proof.




















 §.§ Markov Chain Definition


 
In this subsection we will present the Markov chains which we will use to 
model the behaviour of the . Each Markov chain M^j has 
m:=⌈μ/2⌉ transient states (S^j_0, S^j_1,…, S^j_m 
-1) and one absorbing state 
(S^j_m ) with the topology depicted in Figure <ref>. 
The states S_i^j represent the amount of diversity in the 
population. 
Hence, eg., S_1^j refers to a 
population where all the individuals have j 1-bits and all  but one of them 
share the same genotype, while S_m-1^j refers to a population where at most 
m-1 = ⌈μ/2 ⌉ +1 individuals are identical. 
Compared to the analysis presented in <cit.> that used Markov 
chains of only three states (i.e., no diversity, diversity, increase in 
1-bits), M^j allows to control the diversity in the population more 
precisely, thus to show that larger populations are beneficial to the 
optimisation process.

 
Let M_j be a Markov chain with m:=⌈μ/2⌉ transient states 
(S^j_0, 
S^j_1,…, S^j_m -1) and one absorbing state (S^j_m ) with 
transition probabilities p_i,k from state S^j_i to state S^j_k 
as follows:

    p_0,1   := μ/(μ+1)2 j (n-j) p_2   /n^2  ,   
    p_0,m:= (n-j)p_1/n  ,
       p_i, m    :=2 i/μμ-i/μp_0/4   if  i>0,


    p_1,2   := p_0( (1/μ)^2 
    μ-1/μ+1 
    +2 1/μμ-1/μ1/4μ-1/μ+1), 
    
    p_1,0   :=p_0( (μ-1/μ)^2 +2 1/μμ-1/μ1/4) 1/μ+1, 
    
    
    p_i,i+1   := p_0( (i/μ)^2 min(μ-i/μ+1, 1/4) +2 i/μμ-i/μ1/4μ-i/μ+1)   
     if     
    m-1>i>1,
    
    
    p_i,i-1   :=p_0( (μ-i/μ)^2 +2 
    i/μμ-i/μ1/4 + (i/μ)^2 
    1/16) i/μ+1
       if    
    m>i>1, 
    
    p_m,m   :=1,    p_0,0:= 1-p_0,1-p_0,m,
    
    
    
    p_m-1, m-1   := 1-p_m-1,m-2-p_m-1,m, 
    
    p_i, i   := 1-p_i,i-1-p_i,i+1-p_i,m   if  0<i<m-1, 
    
    p_i,j   :=0    otherwise.








Now, we will point out the important characteristics of these transition 
probabilities. The transition probabilities, p_i,k, are set to be equal to 
provable bounds on the probabilities of the with a population consisting 
of solutions with j bits of gaining/losing diversity (p_i,i+1/p_i,i-1) 
and sampling a solution with more than j 1-bits (p_i,m). In particular, 
upper bounds are used for the transition probabilities p_i,k where i<k and 
lower bounds are used for the transition probabilities p_i,k where i>k. 
Note that greater diversity corresponds to a higher probability of two distinct 
individuals with j 1-bits being selected as parents and improved via 
recombination (i.e., p_i,m  monotonically increases with i  and  
recombination is ineffective if i=0 and the improvement probability p_0,m 
is simply the probability of increasing the number of 1-bits by mutation only. 
Thus, p_0,m=Θ(j/n) while p_i,m=Θ(i(μ-i)/μ^2) when i>0.  
The first forward transition probability p_0,1 denotes the probability of 
the mutation operator of creating a different individual with j 1-bits and the 
selection operator removing one of the majority individuals from the population. 
The other transition probabilities, p_i,i+1 and p_i,i-1 bound the 
probability that a copy of the minority solution or the majority solution is 
added to the population and that a member of the other species 
(minority/majority) is removed in the subsequent selection phase. All transition 
probabilities except p_0,1 and p_0,m are independent of j and referred 
to in the theorem statements without specifying j.





 §.§ Validity of the Markov Chain Model


In this subsection we will present how we establish that M^j is a pessimistic 
representation of Algorithm <ref> initialised with a population 
of μ identical individuals at level j. In particular, we will show that 
E[T^j_0], the expected absorbing time starting from state S_0^j is 
larger than E[T^j]. This result is formalised in the following lemma.



Let E[T] be the expected runtime until the with 
μ=o(logn/loglogn) optimises the function and   
E[T_i^j] 
(or E[T_i] wherever j is obvious)  is the expected 
absorbing time of M^j starting from state S^j_i. Then, E[T] ≤ o(n 
logn) + (1+o(1))∑_j=0^n-1 E[T_0^j]. 


We will use drift analysis <cit.>, a frequently used tool in the 
runtime analysis of evolutionary algorithms, to prove the above result.  We 
will 
start by defining a 
potential function over the state space of Alg. <ref> that maps 
states to the expected absorbing times of M^j. The minimum of the potential 
function will correspond to the state of Algorithm <ref> which 
has sampled a solution with more than j 1-bits and we will explicitly prove 
that the maximum of the potential function is E[T^j_0]. Then, we will show 
that the drift, i.e.,
the expected decrease in the potential function value in a single time 
unit (from time t to t+1), is at least one. 
Using the maximum value of the potential function and the minimum drift, 
we will bound the runtime of the algorithm by the absorbing time of the Markov chain.


We will define our potential function over the domain of all possible 
population diversities at level j. We will refer to the genotype 
with the most copies in 
the population as the majority genotype and recall that the diversity, D_t ∈{ 
0, …, μ-1}, of a population P_t is defined as the number of 
non-majority individuals in the population. 







The potential 
function value for level j, g^j (or g wherever j is obvious),  is defined as follows:

    g^j(D_t)=g^j_t=
       
          E[T_D_t]      0≤ D_t < ⌈μ/2⌉-1 
    
          E[T_⌈μ/2⌉-1 ]    ⌈μ/2⌉-1 ≤ D_t < μ-1 
    
          0    ∃ x∈ P_t    s.t.   (x)>j

where E[T_i^j] (denoted as E[T_i] wherever j is obvious) is the 
expected absorbing time of the Markov chain M^j starting from state 
S^j_i.

The absorbing state of the Markov chain corresponds to a population with at 
least one individual with more than j 1-bits, thus having  potential function 
value (and  expected absorbing time) equal to zero. The state S_0^j corresponds to a population with no diversity.  The 
following lemma formalises that the expected absorbing time gets larger as the 
initial states get further away from ⌈μ/2⌉-1. This property 
implies that the expected absorbing time from state S_0^j  constitutes an 
upper bound for the potential function g^j. 
 
 Let E[T^j_i] be the expected absorbing time of Markov chain M^j 
conditional on its initial state being S_i^j. 
Then,  ∀ j ∈{0,…,n-1}, E[T^j_i] ≥ E[T^j_i-1] for all 1 ≤ i ≤⌈μ/2⌉ and g^j_t≤ E[T^j_0] ∀ t>0. 


Now that the potential function is bounded from above, we will bound the drift
E[g_t-g_t+1)|D_t=i]. Due to the law of total expectation, the expected 
absorbing time, E[T_i] satisfies ∑_j p_i,j (E[T_j]-E[T_i])=1 for any 
absorbing Markov chain at state i.





Since E[T_i] and E[T_j] are the respective potentials of the states S_i 
and S_j, the left hand side of the equation closely resembles the 
drift. 
Since the probabilities for M^j are  
pessimistically set to underestimate the drift, the above equation allows us 
to formally prove the following: 
 
For a population at level j,
 E[g_t^j - g_t+1^j| D_t=i] ≥ 1-o(1) for all t>0



We will now show that Δ_t(i) := E[g_t - g_t+1| D_t=i], the 
expectation of the difference between the potential function values of 
population P_t and P_t+1, is larger than one for all i. 
 
When there is no diversity in the population (i.e., D_t=0) the only 
way to increase the diversity is to introduce it during a mutation operation. 
A non-majority individual is obtained when one of the n-j 0-bits and one of the j 
1-bits are flipped while no other bits are touched. Then one of the majority 
individuals must be removed from the population during the selection phase.This 
event has probability at least
p_2 · 2 ·(n-j)/n j/nμ/μ+1
= p_0,1.
Another way to change the potential function value is to create an improved 
individual with the mutation operator. In order to improve a solution it is 
sufficient to pick one of n-j 1-bits and flip no other bits.  This event has 
the probability at least 
p_1·(n-j)/n =

p_0,m.
Thus, we can conclude that when D_t=0, the drift is at least p_0,m (T_0) + 
p_0,1 (T_0 - T_1). We can observe through the law of total expectation for 
the state S^j_0 of Markov chain M^j that this expression for the drift 
when D_t=0 is larger than one. 

For D_t>0, we will condition the drift on whether the picked parents	
		are both majority individuals ℰ_1,
		are both minority individuals with the same genotype  
ℰ_2,
		are a pair that consists of one majority and one minority 
individual ℰ_3, or they
		are both minority individuals with different genotypes 
ℰ_4.

	Let ℰ^* be the event that the population P_t consists of 
two genotypes with Hamming distance two. Then, 
	
    {ℰ_1|ℰ^*} = 
    {ℰ_1|ℰ^*}= 
    (μ-i/μ)^2 
       {ℰ_2|ℰ^*} 
    ={ℰ_2|ℰ^*} + 
    {ℰ_4|ℰ^*}= (i/μ)^2 
    
       {ℰ_3|ℰ^*}={ℰ_3 
    |ℰ^*} = 2i/μμ-i/μ;   {ℰ_4|ℰ^*} = 0

	Note that when there are more than two genotypes in the population, the 
event of picking any two non-majority individuals is divided into two separate 
cases of picking identical minority individuals and picking two different 
minority individuals. Obviously, the sum of the probabilities of these two 
cases is equal to the probability of picking two minority individuals when there 
are only two genotypes (one majority and one minority) in the population. 

Restricting ourselves to Δ_t^i>0, the drift conditional on  
i>0, the law of total expectation states: 
    
    Δ_t^i>0    = {ℰ^*}∑_i=1^4({ℰ_i|ℰ^*}(Δ_t^i>0|ℰ_i,ℰ^*)) + 
    
     +    (1-{ℰ^*} )
    ∑_i=1^4({ℰ_i|ℰ^*}(Δ_t^i>0|ℰ_i,ℰ^*))

We can rearrange the above expression using the probabilities from 
Eq <ref>

    Δ_t^i>0   ≥(μ-i/μ)^2 
    (Δ_t^i>0|ℰ_1) + (i/μ)^2 
    min((Δ_t^i>0|ℰ_2), 
    (Δ_t^i>0|ℰ_4) )
     +   2 
    μ-i/μi/μ(Δ_t^i>0|ℰ_3)





We will now write the law of total expectation for state i for our Markov 
chain M^j:

    1= p_i, i+1 (E[T_i] -E[T_i+1]) + p_i, i-1 (E[T_i] -E[T_i-1]) + 
    p_i, m E[T_i]


	We will then  substitute the probabilities in the law of total 
expectation with the values from Definition <ref>, 	
	
    1   = p_0( (i/μ)^2 min(μ-i/μ+1, 1/4) +2 i/μμ-i/μ1/4μ-i/μ+1) (E[T_i] 
    -E[T_i+1]) 
    
    	   + p_0( (μ-i/μ)^2 +2 
    i/μμ-i/μ1/4 + 
    (i/μ)^2 1/16) i/μ+1 (E[T_i] 
    -E[T_i-1]) 
    
    	   +( 2 i/μμ-i/μ1/4e^c) 
    E[T_i]

	
	Finally, we will rearrange the above expression into the terms with 
the probabilities of events ℰ_i as multiplicative factors
	
    1   = ( μ-i/μ)^2 p_0i/μ+1 
    (E[T_i]-E[T_i-1])   
        +(i/μ)^2  p_0( min(μ-i/μ+1, 1/4) (E[T_i] -E[T_i+1]) 
       +  
    1/16i/μ+1(E[T_i] -E[T_i-1])) 
       +2 i/μμ-i/μ 
    p_0(1/4μ-i/μ+1 (E[T_i] -E[T_i+1]) 
       + 
    1/4i/μ+1 (E[T_i] 
    -E[T_i-1])+E[T_i]/4)

	
We will refer to the first, second and third line of the
Eq <ref> as the ℰ_1, ℰ_2 and 
ℰ_3 term respectively. We will show that for each term, the 
conditional drift is larger than the term without the multiplicative factor.

When two majority individuals are selected as parents (ℰ_1), we 
pessimistically assume that improving to the next level and increasing the 
diversity has zero probability. Losing the diversity requires that no bits 
are flipped  during mutation and that a minority individual will be removed 
from 
the population. The probability that no bits are flipped is p_0. Thus we can show that:
Δ_t^i>0|ℰ_1 ≥ p_0(E[T_i] - E[T_i-1]) 
i/μ+1.

This bound is obviously the same as the ℰ_1 term of 
Eq <ref> without the parent selection probability. 

When two minority individuals are selected as parents(ℰ_2 or 
ℰ_4), if they are identical (ℰ_2) then it is sufficient 
that the mutation does not flip any bits which occurs with probability p_0 

and that a majority 
individual is removed from the population (with probability (μ-i)/μ). 
Thus, the probability of increasing the diversity is p_0 × 
(μ-i)/μ and the probability of creating a majority individual is 
1/n since it is necessary to flip at least one particular bit position: 
Δ_t^i>0|ℰ_2 ≥ 
p_0μ-i/μ(E[T_i] - 
E[T_i+1])

However, if the two minority individuals have a Hamming distance of 
2d≥ 2 (i.e., ℰ_4), then in order to create another 
minority individual at the end of the crossover operation it 
is necessary that the crossover picks exactly d 1-bits and d 0-bits  among 
2d bit positions where they differ. There are 2dd different ways 
that this can happen and the probability that any particular outcome of 
crossover is realised is 2^-2d. One of those outcomes though, might 
be the majority individual and if that is the case the diversity can decrease 
afterwards. However, while the Hamming distance between the minority 
individuals can be 2d=2, obtaining a majority individual by 
recombining two minority individuals requires at least four specific bit 
positions to be picked correctly during crossover and thus does not occur with 
probability greater than 1/16. On the other hand, when two different minority 
individuals are selected as parents,  there is at least  a 1- 
2dd 2^-2d/2≥ 1/4 
probability that the crossover will result in an individuals with more 1-bits 
and then with probability p_0 the mutation will not flip any 
bits. 

    Δ_t^i>0|ℰ_4≥ p_0 [ 
    (2dd-1) 
    2^-2dμ-i/μ+1 (E[T_i] -E[T_i+1]) + 
       +(min(1/16,2^-2d)+1/n) i/μ+1 
    (E[T_i] -E[T_i-1])+ 1/4E[T_i]  ]
       ≥(1-o(1))· p_0  [  
    min(1/16,2^-2d) i/μ+1 
    (E[T_i] -E[T_i-1])+ E[T_i]/4]

Note that the ℰ_2 term of Eq <ref> multiplied with 
a factor of (1-o(1)) is smaller than both conditional drifts multiplied with 
the parent selection probability (i/μ)^2. 





Finally, we will consider the drift conditional on event ℰ_3, 
the case when one minority and one majority individual are selected as 
parents. We will further divide this event into two subcases. In the first case 
 the Hamming distance 2d between the minority and the majority individual is 
exactly two (d=1). Then, the probabilities that crossover creates a copy 
of the minority individual, a copy of the majority individual or a new 
individual with more 1-bits are all equal to 1/4. Thus, the conditional drift 
is (Δ_t^i>0|ℰ_3,d=1)

    ≥   p_0/4( 
    i/μ+1 
    (E[T_i]-E[T_i-1])+ μ-i/μ+1(E[T_i]-E[T_i+1]) + E[T_i] 
    ).

However, when d>1, the drift is more similar to the case of ℰ_3 
where the probabilities of creating copies of either the minority of the 
majority diminish with larger d while larger d increases the probability 
of creating an improved individual. More precisely, the drift is 


    (Δ_t^i>0|ℰ_3,d>1)≥ p_0  
    [ 
    (2dd-1) 2^-2dμ-i/μ+1 (E[T_i] -E[T_i+1]) 
       + (2^-2d+1/n) 
    i/μ+1 (E[T_i] -E[T_i-1])
    	+ (1- 2dd 2^-2d/2)E[T_i]  ]
       ≥ p_0  ( 
    (2^-2d+1/n)i/μ+1 
    (E[T_i] -E[T_i-1])
       + (1- 2dd 2^-2d/2)E[T_i]  )
    
    
    
    		    ≥ p_0  ( 
    (1/16+1/n)i/μ+1 (E[T_i] -E[T_i-1])+ 
    15/32E[T_i]  )
    
    
       ≥(1-o(1))· p_0  ( 
    1/16i/μ+1 (E[T_i] -E[T_i-1])+ 
    15/32E[T_i]  )

Since (E[T_i] - E[T_i-1]) is negative and E[T_i] > E[T_i] - E[T_i+1], 
(Δ_t|ℰ_3,d>1)≥ (Δ_t|ℰ_3,d=1). Now, 
finally we can observe that (Δ_t|ℰ_3,d=1) multiplied with 
2i(μ-i)/μ^2 is larger than the ℰ_3 term in Eq <ref> 
multiplied with a factor of (1-o(1)). 

We have now shown piece by piece that the conditional drifts are larger 
than the corresponding terms in the right hand side of Eq <ref> 
up to small order terms, and thus established that Δ_t ≥ (1-o(1)) for all 
t>0. Since we have previously shown that g^j_t≤ T_0^j, we can now 
apply Theorem <ref> to obtain E[T^j] ≤ (1+o(1)) E[T_0^j].

Once an individual with j+1 1-bits is sampled for the first time it takes 
μlogμ iterations before the whole population consists of 
individuals with at least  j+1 1-bits <cit.>. If 
the population 
size is in the order of o(logn/loglogn), then the total number of 
iterations where there  are individuals with different fitness values in the 
population is in the order of o(n logn). Since j ∈{0,1,…,n-1}, 
we can establish that E[T]≤ o(nlogn)+∑_j=0^n-1E[T^j] ≤ 
o(nlogn)+(1+o(1))∑_j=0^n-1 E[T_0^j].


  With the potential function bounded from above by Lemma <ref> and 
the drift bounded from below by Lemma <ref>, we can use 
the additive drift theorem[The additive drift theorem is 
provided in the appendix as Theorem <ref> for reviewer convenience] 
from <cit.> to bound E[T^j] by E[T_0^j]. By summing over 
all levels, we get the bound stated in Lemma <ref> on the expected 
runtime of Algorithm <ref>.




 §.§ Markov Chain Absorption Time Analysis

In the previous subsection we stated in Lemma <ref> that we can 
bound the absorbing times of the Markov chains M^j 
to derive an upper bound on the runtime of Algorithm <ref>.
In this subsection we use mathematical tools developed for the analysis of 
Markov chains to provide such bounds on the absorbing times.  

The absorbing time of a Markov chain starting from any initial state 
i can be derived by identifying its fundamental matrix. 
Let the matrix Q denote the transition probabilities between the transient 
states of the Markov chain M^j. The fundamental matrix of M^j is 
defined as N:=(I - Q)^-1 where I is the identity matrix. The most 
important characteristic of the fundamental matrix is that when it is 
multiplied by a column vector of ones, the product is a vector holding 
E[T^j_i], the expected absorbing times conditional on the initial state 
i of the Markov chain. Since, Lemma <ref> only involves 
T_0^j, we are only interested in the entries  of the first row of 
N=[n_ik]. 

However, inverting the matrix I-Q is not always a straightforward task. 
Fortunately,  I-Q=[a_ik] has characteristics that allow bounds on the 
entries of its inverse. Its entries are related to the transition probabilities 
of M^j as follows:

    a_11   =1-p_0,0= p_0,1+ p_0,m
    
     a_mm   =1-p_m-1,m-1= p_m-1,m-2+ p_m-1,m
    
     a_ii   =1-p_i-1,i-1= p_i-1,i-2+ p_i-1,i+p_i-1,m
       ∀ i 
    ∈{2,...,m-1}
    
     a_ik   =-p_i-1,k-1  ∀ i,k ∈{1,…,m}∧ i≠ k


Observe that I-Q  is a tridiagonal matrix, in the sense that all 
non-zero elements of I-Q are either on the diagonal or adjacent to it. 
Moreover, the diagonal entries a_ii of I-Q are in the form 
1-p_i-1,i-1, which is equal to the sum of all transition probabilities out 
of state i-1. Since the other entries on row i are transition probabilities 
from state i-1 to adjacent states, we can see that |a_ii| > ∑_i≠ k 
a_ik. The matrices where |a_ii| > ∑_i≠ k a_ik holds are 
called  strongly diagonally dominant (SDD). Since I-Q is SDD, according 
to Lemma 2.1[For reviewer convenience, it is 
Lemma <ref> in 
the Appendix.] in <cit.>, it holds for the fundamental matrix 
N 
for  all i≠ k that, |n_i,k| ≤ |n_k,k| ≤(|a_k,k| 
(1-∑_l≠ j|a_l,k| /|a_k,k|))^-1≤(|a_k,k|- ∑_l≠ j|a_l,k| )^-1.

In our particular case, the above inequality implies that |n_1,k| ≤  
1/p_k-1,m. For any population with diversity, there is a probability in the 
order of 1/μ to select one minority and one majority individual and a 
constant probability that their offspring will have more 1-bits than the 
current level. Considering m=μ, E[T_0^j] = ∑_k=1^mn_1,k < n_1,1 + ∑_k=2^m1/p_k-1,m≤  n_1,1 + μ^2.



We note here that the μ^2 factor in the above expression creates the 
condition μ=o(√(logn)) on the population size  for our main 
results. We will now bound the term n_1,1 from above to establish our upper 
bound using the following theorem:





 

 A is an m× m tridiagonal non-singular SDD matrix such that 
a_i,k≤ 0 for all i≠ k, A^-1=[n_i,k] exists and n_i,k≥ 
0 for all i,k, then 
n_1,1= 1/(a_1,1+ a_1,2ξ_2), ξ_i=a_i,i-1/(a_i,i+ a_i,i+1ξ_i+1), and 
ξ_m=a_m,m-1/a_m,m.







In order to use Theorem <ref>,  we need to satisfy its conditions. 
We can easily see that non-diagonal entries of the original matrix I-Q are 
non-positive and use Theorem 3.1[For reviewer 
convenience, it is Theorem <ref> in the Appendix.]


in <cit.> to show that 
N=(I-Q)^-1 has no negative entries. Thus, Theorem <ref> yields:














 With an initial population of size μ=o(√(logn)) at level j, the 
expected time E[T^j] until an individual with j+1 1-bits is sampled by the for the first time is bounded from above  as follows:

    E[T^j_0] ≤n/n-j1/p_1+ 
    2 μ p_2/(μ+1)j  /n   
    (1-ξ_2) +o(logn)
       ξ_m=p_m-1,m-2/p_m-1,m+p_m-1,m-2
    
    
       ξ_i=p_i-1,i-2/p_i-1,m+p_i-1,i-2 + p_i-1,i(1-ξ_i+1)  ∀ 1<i<m=⌈μ/2⌉ .

where p_i,k are the transition probabilities of the Markov chain M^j.


The above bound on E[T^j_0], together with 
Lemma <ref>, yields Theorem <ref>, our main result.



§ CONCLUSION






In this work, we have shown that the steady-state optimises 
faster than any unary unbiased search heuristic. 


Providing precise asymptotic bounds on the expected runtime of standard GAs without artificial mechanisms that simplify the analysis has been a long 
standing open problem. 
We have derived bounds up to the leading term constants of the expected runtime.
To achieve this result we show 
that a simplified Markov chain  pessimistically represents the behaviour of  
the GA for . This insight about the algorithm/problem pair allows the derivation 
of runtime bounds for a complex multi-dimensional stochastic 
process. The analysis shows that as the number of states in the Markov chain (the population size) increases, so does the 
probability that diversity in the population is kept. Thus, larger populations increase the probability that recombination 
finds improved solutions quickly, hence reduce the expected runtime. 


ACM-Reference-Format


§ APPENDIX




















































 §.§ Proof of Lemma <ref>


We will first show that E[T^j]≤ (1+o(1))E[T_0^j] .

In order to achieve this result, we will first establish that g^j_t≤ 
E[T_0]  ∀ t>0 and then that  Δ_t ≥ 1-o(1)
1   ∀ t>0.  These two results will allow us to use 
Theorem <ref> and conclude that E[T^j]≤ (1+o(1)) E[T_0^j]. 
For the rest of the analysis of E[T^j], we will drop the superscript of 
E[T_i^j] and g^j_t.



 We are interested in max(E[T_0], E[T_1], …, E[T_m]) since 
these are the values that the potential function g can have. According to the 
transition probabilities in Definition <ref>, p_i+1,m≥ p_i,m  for all i. Using this observation and the law of total expectation  we can 
show that not only max(E[T_0], E[T_1], …, E[T_m])= E[T_0] but 
also E[T_i-1] ≥ E[T_i] for all i.  




First, we will prove that E[T_m-2] ≥ E[T_m-1] by contradiction. Then, 
we will prove by induction that E[T_i-1] ≥ E[T_i] for all i. For this 
induction we will use E[T_m-2] ≥ E[T_m-1] as our basic step and we will 
prove by contradiction that if for all j>i E[T_j-1]≥ E[T_j] holds 
then E[T_i-1] ≥ E[T_i] must also hold. 

If we use the law of total expectation for the absorbing time starting from 
state  0<i<m, we obtain:

    E[T_i] = p_i, i+1 (E[T_i+1] +1 ) + p_i, i-1 (E[T_i-1] +1 ) 
    
       + p_i, m+1 + (1- p_i, i+1 - p_i, i-1- p_i, m) (E[T_i] +1 )



This equation can be rearranged as follows:

    1= p_i, i+1 (E[T_i] -E[T_i+1] ) + p_i, i-1 (E[T_i] -E[T_i-1] ) 
    + p_i,m E[T_i]

For the special case of i=m, we have:

    1= p_m-1, m (E[T_m-1] ) + p_m-1, m-2 (E[T_m-1] -E[T_m-2] )

If we introduce the allegedly contradictory assumption E[T_m-2] < 
E[T_m-1], the above equation implies:

    1 > p_m-1, m (E[T_m-1] )  1/p_m-2,m≥1/p_m-1, m
       > E[T_m-1] > E[T_m-2] 
       1/p_m-2,m  > E[T_m-2]



Given that 1/p_i, m  > E[T_i]  and E[T_i+1] > E[T_i]   the 
law of total expectation for i implies:

    1= p_i, i+1 (E[T_i] -E[T_i+1]) + p_i, i-1 (E[T_i] -E[T_i-1]) + 
    p_i, m E[T_i]


    1< p_i, i+1 (E[T_i] -E[T_i+1]) + p_i, i-1 (E[T_i] -E[T_i-1]) + 1


    0< p_i, i-1 (E[T_i] -E[T_i-1])


    E[T_i-1]< E[T_i]  1/p_i-1, m≥1/p_i, m > 
    E[T_i]  
    > E[T_i-1]

Thus the allegedly contradictory claim E[T_m-1] > E[T_m-2] induces over 
i 
such that it implies E[T_1] > E[T_0] and 1/p_0,m > E[T_0]. We can now 
write the 
total law of expectation for i=0.

    1= p_0,1 (E[T_0] - E[T_1]) + p_0,m E[T_0]


    1 < p_0,1 (E[T_0] - E[T_1]) + 1


    0 < p_0,1 (E[T_0] - E[T_1])


    0 > p_0,1

The last statement is a contradiction since a probability cannot be negative. 
This contradiction proves the initial claim E[T_m-2] ≥ E[T_m-1] 

We will now follow a similar route to prove that E[T_i-1] ≥ E[T_i] for 
all 
i.
Given that for all j>i  E[T_j-1] ≥ E[T_j] holds, we will show that 
E[T_i>E[T_i-1]
creates a contradiction. We start with the law of total expectation for E[T_i:

    1= p_i, i+1 (E[T_i] -E[T_i+1]) + p_i, i-1 (E[T_i] -E[T_i-1]) + 
    p_i, m E[T_i]

Our assumption “ ∀ j>i    E[T_j] ≤ E[T_j-1]” 
implies that E[T_i]-E[T_i+1] ≥ 0, thus we obtain: 

    1> p_i, i-1 (E[T_i] -E[T_i-1]) + p_i, m E[T_i]

With our allegedly contradictory assumption E[T_i]-E[T_i-1]>0 we obtain:

    1> p_i, m E[T_i] 1/p_i-1, m≥1/p_i, m > 
    E[T_i]  > E[T_i-1]

We have already shown above that 1/p_i-1, m≥ 1/p_i, m  > E[T_i]  > 
E[T_i-1] can be 
induced over i and implies E[T_1] > E[T_0] and 1/p_0,m > E[T_0]. Then 
we can 
conclude that: 

    E[T_i] ≥ E[T_i+1]  ∀ 0 ≤ i ≤⌈μ/2⌉-1.


The above conclusion implies that E[T_0] is the largest value that our 
potential function can have and E[T_i] - E[T_i+1] is non-negative 
for all i.







 §.§ Proof of Lemma <ref>

Here, we will use the following additive drift 
theorem from <cit.>,


 
Let (X_t)_t∈_0, be a stochastic process, adapted to a filtration 
()_t∈_0, over some state space S⊆{0}∪ 
[x_min,x_max], where 
x_min≥ 0. 
Let g:{0}∪ [x_min,x_max]→^≥ 0 be any function
such that g(0)=0, and 0<g(x)<∞ for all 
x∈[x_min,x_max]∖{0}.
Let 𝒯_a=min{t| X_t≤ a} for a∈{0}∪ 
[x_min,x_max]. 
If E[g(X_t)-g(X_t+1)   X_t≥ x_min]≥α_u 
for some α_u>0 then 
E[𝒯_0| X_0] ≤g(X_0)/α_u.




Since Δ_t ≥ (1-o(1))  from Lemma <ref> and g^j_t≤ 
E[T_0^j] from Lemma <ref>, we can apply 
Theorem <ref> to obtain E[T^j] ≤ (1+o(1)) E[T_0^j].
Once an individual with j+1 1-bits is sampled for the first time it takes 
μlogμ iterations before the whole population consists of 
individuals with at least  j+1 1-bits <cit.>. If 
the population size is in the order of o(logn/loglogn), then the 
total number of 
iterations where there  are individuals with different fitness values in the 
population is in the order of o(n logn). Since j ∈{0,1,…,n-1}, 
we can establish that 

    E[T]≤ o(nlogn)+∑_j=0^n-1E[T^j] ≤ 
    o(nlogn)+(1+o(1))∑_j=0^n-1 E[T_0^j].

 









 §.§ Proof of Lemma <ref>



We made use of the following lemma to obtain .

    E[T_0^j] = ∑_k=1^mn_1,k < n_1,1 + ∑_k=2^m1/p_k-1,m≤  n_1,1 + μ^2.

  

 Let A be a SDD matrix, then A^-1=[n_ik] exists and for any i ≠ k,
 
    |n_ik|≤  n_kk∑_i≠ k |a_ik| /|a_ii|≤ 
     n_kk≤1/|a_kk| - ∑_ l ≠ k |a_k l|

 

In order to show that the entries of the fundamental matrix of M^j 
are all non-negative, we will employ the following result.

 
If A is a tridiagonal non-singular SDD matrix and a_i,i>0 then A^-1= 
[n_i,k] exists and 

 
  * sign(n_i,i)=1
 
  * sign(n_i,k)=(-1)^i+k∏^i_l=k+1a_l,l-1, i>k 
 
  * sign(n_i,k)=(-1)^i+k∏^k_l=ia_l,l+1, i<k



 Since the diagonal entries of I-Q are strictly positive, according to 
Theorem <ref> the diagonal entries of N are also positive. 
The non-diagonal entries of I-Q are all negative thus the series 
multiplication from Theorem <ref> for i>k reduces to 
(-1)^i+k+i-k=(-1)^2i=1. Similarly for the case  i<k the multiplication 
reduces to (-1)^i+k+k-i=(-1)^2k=1.

 

Starting from Inequality <ref> and applying 
Theorem <ref> we obtain:

    E[T_0^j]    ≤  n_1,1 + μ^2≤1/a_1,1+ 
    a_1,2ξ_2 
    + μ^2
       = 1/p_0,m+p_0,1(1-ξ_2) +μ^2
    ≤   1/p_0,m+p_0,1(1-ξ_2)+ μ^2
       ≤1/ (n-j)p_1/n  +μ/(μ+1)2j 
    (n-j)p_2  /n^2 (1-ξ_2)+ μ^2
       =n/n-j1/p_1+ μ/(μ+1)2 j  p_2  /n   
    (1-ξ_2) +o(logn)
 
where we substitute p_0,1 and p_0,m with their values declared 
in Definition <ref>.
The definitions of ξ_i and ξ_m are obtained by simply substituting the 
matrix entries in Theorem <ref> with their respective values from 
Equations <ref> to <ref>.






 §.§ Proofs of main results





 Combining Lemma <ref> and Lemma <ref> we obtain:
 
    E[T]   ≤ o(nlogn)+(1+o(1))∑_j=0^n-1E[T^j] 
       ≤  
    o(nlogn)+ (1+o(1))∑_j=0^n-1( n/n-j1/p_1+ 
    μ/(μ+1)2 j  p_2  /n   
    (1-ξ_2))

We will now divide the sum into two smaller sums:

    ∑_j=1^nn/n-j1/p_1+ μ/(μ+1)2 j  p_2  
    /n   
    (1-ξ_2)
       = ∑_j=1^n- n/√(logn)n/n-j1/p_1+ μ/(μ+1)2 j  p_2  /n   
    (1-ξ_2)
       + ∑_j=n- 
    n/√(logn)+1^nn/n-j1/p_1+ μ/(μ+1)2 j  p_2  /n   
    (1-ξ_2)
       ≤n √(logn) + n/p_1+ 2   p_2  μ/(μ+1)(1-1/√(logn))
    (1-ξ_2)∑_j=n- 
    n/√(logn)+1^n1/n-j
       ≤n √(logn) +n lnn/p_1+ 2   p_2  μ/(μ+1)(1-1/√(logn))
    (1-ξ_2)

We conclude the proof by substituting the sum in Eq <ref> with the above expression.

    E[T]    ≤ o(nlogn)+ (1+o(1))(n √(logn) + n 
    lnn/p_1+ 2   p_2  μ/(μ+1)(1-1/√(logn))
    (1-ξ_2))
       ≤ o(nlogn)+ (1+o(1))(n √(logn) +(1+o(1))n 
    lnn/p_1+ 2   p_2  μ/(μ+1) 
    (1-ξ_2))
       =(1+o(1))n lnn1/p_1+ 2   p_2  μ/(μ+1) 
    (1-ξ_2)
 

The expressions for ξ_i and ξ_m come from Lemma <ref> and 
proves the first statement.

For the second statement, we adapt the result for the variant of which 
does not evaluate copies of either parents. When there is no diversity in the 
population the offspring is identical to the parent with probability p_0. 
Then, given that a fitness evaluation occurs, the probability of improvement via 
mutation is p_0,m/(1-p_0) and the probability that diversity 
is introduced is p_0,1/(1-p_0). The proof is identical to the 
proof of first statement, except for using probabilities 
p^*_0,m=p_0,m/(1-p_0) and 
p^*_0,1=p_0,1/(1-p_0)  instead of p_0,1 and p_0,m 
from Definition <ref>. Even if we pessimistically assume that a 
function evaluation occurs at every iteration when there is diversity in the 
population, we still get a (1-p_0) decrease in the leading constant. 





















































