1 INTRODUCTION

Noise is a common phenomenon in many real-world optimization problems. It can stem from sources as different as errors of measurement in experiments, from the use of stochastic sampling or simulation procedures, or from interactions with users, to name but a few. Reduced convergence velocity or even inability to approach the optimum are commonly observed consequences of the presence of noise on optimization strategies.

It can frequently be observed in experiments that evolutionary algorithms (EAs) are comparatively robust with regard to the effects of noise. In fact, noisy environments are considered to be a prime area for the application of EAs. For genetic algorithms (GA), optimization in noisy environments has been investigated, among others, by Fitzpatrick and Grefenstette [10], Miller and Goldberg [12], and Rattray and Shapiro [15]. Their work has led to recommendations regarding population sizing and the use of resampling, and it has been shown that in the limit of an infinitely large population the effects of noise on the performance of a GA employing Boltzmann selection are entirely removed.

In the realm of evolution strategies (ESs), theoretical studies of the effects of noise date back to early work of Rechenberg [16] who analyzed the performance of a (1 + 1)-ES in a noisy corridor. An analysis of the performance of the (1 + A)-ES on a noisy sphere by Beyer [3] sparked empirical research by Hammel and Bäck [11] who concluded that the findings made for GAs do not always easily translate to ES. Arnold and Beyer [2] address the effects of overvaluation of the parental fitness using a (1 + 1)-ES on a noisy sphere. Both Rechenberg [17] and Beyer [7, 8] give results regarding rescaled mutations in (1, λ)- ES. For an overview of the status quo of ES research concerned with noisy environments and for additional references see [1, 8].

Empirical evidence presented by Rechenberg [17] and by Nissen and Propach [13] as well as by a number of others suggests that population-based optimization methods are generally superior to point-based methods in noisy environments. However, analytically obtained results in the field of ES have been published only for single-parent strategies. The present paper attempts to close part of this gap between theory and empirical observations by presenting a formal analysis of the local performance of a (μ/μ_I, λ)-ES on a noisy sphere in the limit of infinite parameter space dimensionality. The results of the analysis can serve as an approximation for large but finite parameter space dimensionality provided that population sizes are chosen not too large.

Much of the theoretically-oriented research on ES relies on the examination of the local behavior of the strategies in very simple fitness environments. While such environments bear only little resemblance to real-world problems, they have the advantage of mathematical tractability. Frequently, consideration of simple fitness environments, such as the sphere or the ridge, leads to an understanding of working mechanisms of ES that can explain phenomena observable or be of practical use in more complex fitness environments. The discovery of the genetic repair principle [5] and the recommendation regarding the sizing of the learning parameter in self-adaptive strategies in [19] are but two examples. The present paper continues this line of research by analyzing the behavior of the (μ/μ_I, λ)-ES on a sphere with fitness measurements disturbed by Gaussian noise. The results derived are accurate in the limit of an infinite-dimensional parameter space and can serve as approximations for large but finite-dimensional parameter spaces.

This paper is organized as follows. Section 2 outlines the (μ/μ_I, λ)-ES algorithm and the fitness environment for which its performance will be analyzed. The notion of fitness noise is introduced. In Section 3, a local performance measure – the expected fitness gain from one generation to the next – is computed. It is argued that for the spherically symmetric environment that is investigated, in the limit of an infinite-dimensional parameter space the expected fitness gain formally agrees with the progress rate. Section 4 discusses the results. It is demonstrated that the performance gain as compared with one-parent strategies is present for small population sizes already. It is shown that in contrast to the noise-free situation, the efficiency of the (1 + 1)-ES can be exceeded by that of a (μ/μ_I, λ)-ES if noise is present. Section 5 concludes with a brief summary and suggestions for future research.

2 ALGORITHM AND FITNESS ENVIRONMENT

Section 2.1 describes the (μ/μ_I, λ)-ES with isotropic normal mutations applied to optimization problems with a fitness function of the form f: ^N → . Without loss of generality, it can be assumed that the task at hand is minimization, i.e. that high values of f correspond to low fitness and vice versa. Section 2.2 outlines the fitness environment for which the performance of the algorithm is analyzed in the succeeding sections.

3 PERFORMANCE

This section computes the expected fitness gain, or, equivalently, the progress rate, for the (μ/μ, λ)-ES in the environment outlined in Section 2.2. It relies on a decomposition of mutation vectors suggested in both [3] and in [17] and is illustrated in Figure 1. A mutation vector z originating at parameter space location x can be written as the sum of two vectors z_A and z_B, where z_A is parallel to $\widehat{\mathrm{x}}-\mathrm{x}$ and z_B is in the hyper-plane perpendicular to that. Due to the isotropy of mutations, it can without loss of generality be assumed that z_A = σ(z₁,0,…, 0)^T and z_B = σ(0, z₂,…, z_N)^T, where the z_t, I,…, N, are independent, standard normally distributed random variates and σ is the mutation strength. Using elementary geometry and denoting the respective distances of x and of y = x + z to the location of the optimum by R and r, respectively, it can be seen from Figure 1 that

$\begin{array}{l}{r}^2={\left(R-\sigma z_1\right)}^2+\left|\right|z_B\left|\right|{}^2\\ \begin{array}{cc}\hfill \hfill & \hfill =R^2\hfill \end{array}-2R\sigma z_1+{\sigma }^2{z}_1^2+{\sigma }^2{\displaystyle \sum _{i=2}^N{z}_1^2}\end{array}$

Introducing normalized quantities

$\sigma *=\sigma \frac{N}{R}\begin{array}{ccc}\hfill \hfill & \hfill ,\hfill & \hfill {\sigma }_{\epsilon }^{*}\hfill \end{array}={\sigma }_{\epsilon }\frac{N}{2R^2}\begin{array}{ccc}\hfill \hfill & \hfill \mathrm{and}\hfill & \hfill q_{\mathrm{x}}^{*}\hfill \end{array}\left(z\right)=q_x\left(z\right)\frac{N}{2R^2}\text{,}$

the normalized fitness advantage associated with mutation vector z from Equation (1) is thus

$\begin{array}{l}{q}^{*}\left(z\right)=\frac{N}{2R^2}\left(R^2-r^2\right)\\ \begin{array}{cc}\hfill \hfill & \hfill ={\sigma }^{*}\hfill \end{array}{z}_1-\frac{{{\sigma }^{*}}^2}{2N}{z}_1^2-\frac{{{\sigma }^{*}}^2}{2N}{\displaystyle \sum _{1=2}^N{z}_1^2}\end{array}$

Note that the index x of the normalized fitness advantage has been dropped as the normalized fitness advantage is independent of the location in parameter space due to the choice of normalizations.

The second summand on the right hand side of Equation (3) can for large N with overwhelming probability be neglected compared to the third summand. The term ${\displaystyle {\sum }_{t=2}^N{z}_t^2/N}$ contained in the third summand on the right hand side of Equation (3) is according to the Central Limit Theorem of Statistics asymptotically normal with mean (N – 1)/N ≈ 1 and variance 2(N – 1)/N² ≈ 2/N. In the limit N → ∞, the third summand and therefore the contribution of the z_B component to the fitness advantage is thus simply $-{\sigma }^{*2}/2$. Note that the components z_t, i = 2, …, N of the mutation vector do not influence the fitness advantage associated with a mutation as for large enough N they statistically average out. Thus, the Z_i, i = 2, …, N, are selectively neutral and for large N the fitness advantage associated with mutation vector z can be approximated as

$q^{*}\left(z\right)\approx {\sigma }^{*}{z}_1-\frac{{{\sigma }^{*}}^2}{2}\text{.}$

As shown in Appendix A this relation is exact in the limit N → ∞.

Selection is performed on the basis of perceived fitness rather than ideal fitness. With the definition of fitness noise from Section 2.2, the perceived normalized fitness advantage associated with mutation vector z in the limit N → ∞ is

$q^{*}\left(z\right)+{\sigma }_{\epsilon }^{*}\delta ={\sigma }^{*}\left(z_1+\vartheta \delta \right)-\frac{{{\sigma }^{*}}^2}{2}\text{,}$

where δ is a standard normal random variate and $\vartheta ={\sigma }_{\epsilon }^{*}/{\sigma }^{*}$ is the noise-to-signal ratio. Those μ offspring individuals with the highest perceived fitness are selected to form the parental population of the succeeding time step. Let (k; λ), k = 1,…, λ, be the index of the offspring individual with the kth highest perceived fitness. The difference between the parameter space location of the centroid of the selected offspring and the centroid of the parental population of the present time step is the progress vector

$〈z〉=\frac{1}{\mu }{\displaystyle \sum _{k=`}^{\mu }{z}^{\left(k;\lambda \right)}}\text{,}$

which consists of components $〈z_i〉={\displaystyle {\sum }_{k=11}^{\mu }{z_t}^{\left(k;\lambda \right)}/\mu \text{.}}$ The expected fitness gain of the strategy is the expected value of the fitness advantage

$q^{*}\left(〈z〉\right)={\sigma }^{*}\left(z_1\right)-\frac{{\sigma }^{*2}}{2N}{〈z_1〉}^2-\frac{{\sigma }^{*2}}{2N}{\displaystyle \sum _{t=2}^N{〈z_t〉}^2}$

associated with this vector.

The vector 〈z〉 can be decomposed into two components 〈z_A〉 and 〈z_B〉 in very much the same manner as shown above and as illustrated in Figure 1 for mutation vectors. As the z_B components of mutation vectors are selectively neutral, the z_B components of the mutation vectors that are averaged are independent. Therefore, each of the 〈z_i〉, I = 2,…, N, is normal with mean 0 and variance 1/μ. Following the line of argument outlined in the derivation leading to Equation (4), the contribution of the z_B components to the expected fitness gain is thus –σ*²/2 μ. Note the occurence of the factor μ in the denominator that reflects the presence of genetic repair, the influence that has in [5] been found to be responsible for the improved performance of the (μ/μ_I, λ)-ESas compared with the (1, λ)-ES.

We now argue that the second summand on the right hand side of Equation (6) can be neglected compared with the third provided that N is large enough. This is the case if $\mu {〈z_1〉}^2\ll N$. Assume that A is fixed and finite. The value of 〈z₁〉² is independent of N. Its mean is not greater than the square of the average of the first μ order statistics of λ independent, standard normally distributed random variables. Therefore, for any  > 0 an N can be given such that the probability that $\mu {〈z_1〉}^2\ll N$ does not hold is less than . As a consequence, the second summand can be neglected.

Computing the expected value of the first summand on the right hand side of Equation (6) is technically involved but straightforward. The calculations are referred to Appendix B. Denoting the cumulative distribution function of the standard normal distribution by Φ and following [5] in defining the (μ/μ, λ)-progress coefficient as

$c_{\mu }/\mu ,\lambda =\frac{\lambda -\mu }{2\mathrm{\pi }}\left(\begin{array}{c}\hfill \mathrm{\lambda }\hfill \\ \hfill \mu \hfill \end{array}\right){\displaystyle {\int }_{-\infty }^{\infty }{e}^{-x^2}}{\left[\Phi \left(x\right)\right]}^{\lambda -\mu -1}{\left[1-\Phi \left(x\right)\right]}^{\mu -1}dx\text{,}$

the result arrived at in Equation (13) reads

$\overline{〈z_1〉}=\frac{c_{\mu }/\mu ,\lambda }{\sqrt{1+{\vartheta }^2}}$

Therefore, the expected fitness gain of the (μ/μ_I, λ)-ES on the noisy, infinite-dimensional quadratic sphere is

${\overline{q}}^{*}=\frac{c_{\mu }/\mu ,\lambda {\sigma }^{*}}{\sqrt{1+{\vartheta }^2}}-\frac{{\sigma }^{*2}}{2\mu }$

The relevance of this result is discussed in Section 4.

We now make plausible that this result formally agrees with the result for the normalized progress rate, i.e. that in the limit N → ∞ the progress rate law

${\phi }^{*}=\frac{c_{\mu /\mu ,\lambda }{\sigma }^{*}}{\sqrt{1+{\vartheta }^2}}-\frac{{{\sigma }^{*}}^2}{2\mu }\text{,}$

where φ* is the expected value of N(R – r)R, holds. For finite normalized mutation strength the normalized fitness gain is finite. Therefore, with increasing N the expected value of the difference between the distance R of the parental centroid from the location of the optimum and the distance r of the centroid of the selected offspring to the location of the optimum tends to zero. As

$N\frac{R^2-r^2}{2R^2}=N\frac{R-r}{R}\cdot \frac{R+r}{2R}\text{,}$

and as (R + r)/2R tends to one, it follows that Equation (9) holds.

4 DISCUSSION

Equation (9) generalizes several previously obtained results and confirms a number of previously made hypotheses and observations. In particular, for ${\sigma }_{\epsilon }^{*}=0\text{,}$ Equation (9) agrees formally with the result of the progress rate analysis of the (μ/μ_I, λ)-ES on the noise-free sphere published in [5]. For μ = 1, results of the analysis of the (1, λ)-ES on the noisy sphere that have been derived in [3] and [17] appear as special cases. Moreover, solving Equation (9) for the distance to the optimum R proves the validity of a hypothesis regarding the residual location error made in [8]. Finally, Equation (9) confirms empirical findings regarding the performance of the (μ/μ_I, λ)-ES made by Herdy that are quoted in [17].

Figure 2 is obtained by numerically solving Equation (9) for the normalized mutation strength ${\widehat{\sigma }}^{*}$ that maximizes the normalized progress rate. Throughout this section, this mutation strength is considered optimal. Both the optimal normalized mutation strength and the resulting normalized progress rate are shown as functions of the normalized noise strength. Note that the axes are scaled by dividing by the optimal normalized mutation strength ${\widehat{\sigma }}^{*}\left({\sigma }_{\epsilon }^{*}=0\right)=\mu c_{\mu /\mu ,\lambda }$ in the absence of noise for normalized noise strength and normalized mutation strength and by the maximal normalized progress rate ${\widehat{\sigma }}^{*}\left({\sigma }_{\epsilon }^{*}=0\right)=\mu c_{\mu /\mu /\lambda }^2/2$ in the absence of noise for the normalized progress rate. Using the scaled quantities the resulting graphs are independent of the population size parameters. For the noisy (1, λ)-ES the figure can already be found in [17].

It can be seen from Figure 2 that a (1, λ)-ES is capable of progress up to a normalized noise strength of ${\sigma }_{\epsilon }^{*}=2c_{1,\lambda \text{,}}$ while a, (μ/μ_I, λ)-ES is capable of progress up to a normalized noise strength of 2μc_μ/μ,λ. That is, a positive progress rate can be achieved for any noise strength by increasing the population size. The reason for this improved performance is – as in the absence of noise – the genetic repair effect. Genetic repair acts in the noisy environment as it does in the noise-free one: the components of the mutation vectors that do not lead towards the optimum but away from it are reduced by the averaging effect of recombination as signified by the presence of the factor μ in the denominator of the loss term in Equation (9). As a consequence, it is possible to explore the search space at higher mutation strengths. In a noisy environment, these increased mutation strengths have the additional benefit of leading to a reduced noise-to-signal ratio ϑ that in limit of very large population sizes tends to zero. Note however that care is in place here as finite population sizes had to be assumed in the limiting process N → ∞. Therefore, no statements regarding the limiting case μ → ∞ can be made. A performance analysis of the (μ/μ_I, λ)-ES in finite-dimensional search spaces will be necessary to arrive at conclusive statements regarding the behavior of strategies employing very large populations or to obtain conclusive results in rather low dimensional search spaces.

The benefit of increased mutation strengths in noisy environments has been recognized before and has led to the formulation of (1, λ)-ES using rescaled mutations in [17, 7, 8]. The present analysis shows that the positive effect of an increased mutation strength can naturally be achieved in (μ/μ_I, λ)-ES, and that no rescaling is required. However, this does not solve the problems related to mutation strength adaptation of (1, λ)-ES using rescaled mutations pointed out in [8] as the self-adaptation of mutation strengths in (μ/μ_I, λ)-ES does not work optimally either.

Defining the efficiency η of an ES as the expected normalized fitness gain, or equivalently the normalized progress rate, per fitness function evaluation for optimally chosen mutation strength, Beyer [6] has shown that on the sphere in the absence of noise, the efficiency of the (l-t-l)-ES cannot be exceeded by any (μ/μ_I, λ)-ES but only asymptotically be reached for very large population sizes. This is not so in noisy environments. Figure 3a) shows the number of offspring per generation λ above which an optimally adjusted (μ/μ_I, λ)-ES outperforms an optimally adjusted (1 + 1)-ES on the infinite-dimensional noisy sphere. It has been obtained by numerically comparing the efficiency of the (μ/μ_I, λ)-ES that follows from dividing the normalized progress rate φ* in Equation (9) by λ with the normalized progress rate of the (1 + 1)-ES computed in [2]. It can be seen that the efficiency of the (1 + 1)-ES can be exceeded even for moderate population sizes if there is noise present. For example, for normalized noise strengths above about 0.59, a (2/2_I, 6)-ES can be more efficient than a (1 + 1)-ES. Only for relatively small normalized noise strengths below 0.2 are large population sizes required to outperform the (1 + 1)-ES. This is a strong point in favor of the use of multi-parent rather than single-parent optimization strategies in noisy environments.

Figure 3b) shows the efficiency of (μ/μ_I, λ)-ES with optimally chosen parameter μ as a function of the number of offspring per generation λ for a number of noise levels. It has been obtained by numerically optimizing the efficiency while considering μ as a real valued parameter in order to smoothen the curves. It can be seen from the asymptotic behavior of each line in the figure that by sufficiently increasing the population size the efficiency can be increased up to its maximal value of 0.202 in the absence of noise. However, it is once more stressed that the relevance of this result for finite-dimensional parameter spaces is rather limited.

5 CONCLUSION

To conclude, the local performance of the (μ/μ_I, λ)-ES on the noisy, infinite-dimensional quadratic sphere has been analyzed. It has been shown that by increasing the population size the effects of noise can be entirely removed. This theoretical result seems to support the validity for ES of empirical observations made by Fitzpatrick and Grefenstette [10] for GAs. For (μ/μ_I, λ)-ES the improved performance is due to genetic repair which makes it possible to use increased mutation strengths and thereby to decrease the noise-to-signal ratio. It has also been demonstrated that, in contrast to the noise-free case, the efficiency of the (1 + 1)-ES can be exceeded by a multi-parent strategy employing recombination, and that even for relatively moderate noise strengths rather small population sizes are sufficient to achieve this.

Future work includes analyzing the performance of the (μ/μ_I, λ)-ES in other fitness environments and extending the analysis to strategies employing dominant rather than intermediate recombination by means of surrogate mutations as exemplified for noise-free environments in [17, 5]. Of particular interest is the extension of the analysis presented here to finite-dimensional parameter spaces. Furthermore, the analysis of the performance of ES employing no recombination or recombination with fewer than μ parents remains as a challenge for the future. The results of such an analysis may prove to be of particular interest as empirical results quoted in [17] indicate that performance improvements not accounted for by the present theory can be observed. Finally, an investigation of the effects of noise on the behavior of mutation strength adaptation schemes such as mutative self-adaptation is of great interest as such schemes are an essential ingredient of ES.

APPENDIX A: SHOWING THE ASYMPTOTIC NORMALITY OF THE FITNESS ADVANTAGE ASSOCIATED WITH A MUTATION VECTOR

The goal of this appendix is to formally show that in the limit N → ∞ the distribution of the normalized fitness advantage is normal with mean – σ*²/2 and variance σ*². Let

$f_1\left(z_1\right)={\sigma }^{*}{z}_1-\frac{{\sigma }^{*2}}{2N}{z}_{\mathrm{I}}^2$

and

$f2\left(z_2,\dots ,z_N\right)=-\frac{{\sigma }^{*2}}{2N}{\displaystyle \sum _{t=2}^N{z}_t^2}\text{.}$

Then q*(z) = f₁(z₁) + f₂(z₂, …, z_N) and the characteristic function of q*(z) is the product of the characteristic functions of f₁(z₁) and f₂(z₂,…,z_N) due to the independence of the summands.

The characteristic function of f₂(z₂,…, z_N) is easily determined. As the sum ${\displaystyle {\sum }_{t=2}^N{z}_i^2}$ is ${\mathrm{\chi }}_{N-1}^2$ -distributed, the charateristic function of f₂(z₂,…, z_N) is

${\varphi }_2\left(t\right)={\left(1+\frac{{\sigma }^{*2}}{N}\mathit{it}\right)}^{-\frac{1}{2}\left(N-1\right)}$

where i denotes the imaginary unit.

The characteristic function of f₁(z₁) is not as easily obtained. It can be verified that for y ≤ N/2

$f_1\left(z_1\right)<y\begin{array}{ccc}\hfill \hfill & \hfill \iff \hfill & \hfill z_1<\frac{N}{{\sigma }^{*}}\hfill \end{array}\left[1-\sqrt{1-\frac{2y}{N}}\right]\begin{array}{ccc}\hfill \hfill & \hfill \mathrm{or}\hfill & \hfill z_1>\frac{N}{{\sigma }^{*}}\hfill \end{array}\left[1+\sqrt{1-\frac{2y}{N}}\right]$

and that f₁(z₁) < y with probability 1.0 if y > N/2. Recall that z₁ is standard normally distributed. Let

$\Phi \left(x\right)=\frac{1}{\sqrt{2\pi }}{\displaystyle {\int }_{-\infty }^x{e}^{-\frac{1}{2}{t}^2}}dt$

denote the cumulative distribution function of the standard normal distribution. The cumulative distribution function of f₁(z₁) is then

$P_1\left(y\right)=\left\{\begin{array}{c}\hfill 1\hfill \\ \hfill \Phi \hfill \end{array}\left(\frac{N}{{\sigma }^{*}}\left(1-\sqrt{1-\frac{2y}{N}}\right)\right)+1-\Phi {\left(\frac{N}{{\sigma }^{*}}\left(1+\sqrt{1-\frac{2y}{N}}\right)\right)}^{\begin{array}{c}\hfill \mathrm{if}y\ge N/2\hfill \\ \hfill \mathrm{if}y<N/2\hfill \end{array}}\right.$

The corresponding probability density function

$p_1\left(y\right)=\left\{\begin{array}{c}\hfill 0\hfill \\ \hfill \hfill \end{array}\frac{1}{\sqrt{2\pi {\sigma }^{*}}\sqrt{1-2y/N}}\right.{\left[exp\left(-\frac{N^{{}^2}}{2{{\sigma }^{*}}^2}{\left(1-\sqrt{1-\frac{2y}{N}}\right)}^2\right)+exp\left(-\frac{N^{{}^2}}{2{{\sigma }^{*}}^2}{\left(1+\sqrt{1-\frac{2y}{N}}\right)}^2\right)\right]}^{\begin{array}{c}\hfill \mathrm{if}y\ge N/2\hfill \\ \hfill \mathrm{if}y<N/2\hfill \end{array}}$

is obtained by differentiation. Using substitution $z=\sqrt{1-2y/N}$ it follows

$\begin{array}{ll}{\varphi }_1\left(t\right)\hfill & ={\displaystyle {\int }_{-\infty }^{\infty }{p}_{\mathit{1}}\left(y\right)e^{ity}\mathit{dy}}\hfill \\ \hfill & =\frac{N}{\sqrt{2\pi {\sigma }^{*}}}{\displaystyle {\int }_0^{\infty }\left[\mathit{exp}\left(-\frac{N^2{\left(1-z\right)}^2}{2{\sigma }^{*2}}\right)+\mathit{exp}\left(-\frac{N^2{\left(1+z\right)}^2}{2{\sigma }^{*2}}\right)\right]\mathit{exp}\left(\mathit{it}\frac{N}{2}\left(1-z^2\right)\right)dz}\hfill \\ \hfill & =\frac{1}{\sqrt{1+{\sigma }^{*2}\mathit{it}/N}}exp\left(-\frac{1}{2}\frac{{\sigma }^{*2}{t}^2}{1+{\sigma }^{*2}\mathit{it}/N}\right)\text{.}\hfill \end{array}$

for the characteristic function of f₁(z₁), where the final step can be verified using an algebraic manipulation system.

Thus, overall the characteristic function of q*(z) is

$\begin{array}{c}\hfill \varphi \left(t\right)={\varphi }_1\left(t\right){\varphi }_2\left(t\right)\hfill \\ \hfill =\frac{1}{{\left(1+{\sigma }^{*2}\mathit{it}/N\right)}^{N/2}}exp\left(-\frac{1}{2}\frac{{\sigma }^{*2}{t}^2}{1+{\sigma }^{*2}\mathit{it}/N}\right)\text{.}\hfill \end{array}$

We now use a property that Stuart and Ord [20] refer to as The Converse of the First Limit Theorem on characteristic functions: If a sequence of characteristic functions converges to some characteristic function everywhere in its parameter space, then the corresponding sequence of distribution functions tends to a distribution function that corresponds to that characteristic function. Due to the relationship

$\underset{N\to \infty }{lim}\frac{1}{{\left(1+x/N\right)}^{N/2}}=exp\left(-\frac{x}{2}\right)\text{,}$

the first factor on the right hand side of Equation (10) tends to exp(–σ*² it/2). The second factor tends to exp(–σ*² t²/2). Therefore, it follows that for any t

$\underset{N\to \infty }{lim}\varphi \left(t\right)=exp\left(1\frac{{\sigma }^{*2}}{2}\left(t^2+\mathit{it}\right)\right)\text{.}$

As this is the characteristic function of a normal distribution with mean –σ*²/2 and variance σ*² the asymptotic normality of the fitness advantage has been shown.

APPENDIX B COMPUTING THE MEAN OF 〈z₁〉

Let z₁^(t) and δ⁽ⁱ⁾, i = 1, …, λ, be independent standard normally distributed random variables. Let (k; λ) denote the index with the kth largest value of z₁⁽ⁱ⁾ + ϑδ^(t) The goal of this appendix is to compute the expected value of the average

$〈z_1〉=\frac{1}{\mu }{\displaystyle \sum _{k=1}^{\mu }{z}_1^{\left(k;\lambda \right)}}\text{,}$

of those μ of the z₁⁽ⁱ⁾ that have the largest values of $z_1^{\left(i\right)}+\vartheta \delta \left(i\right)$.

Denoting the probability density function of z₁^(k; λ) as P_k;λ, the expected value can be written as

$\overline{〈z_1〉}=\frac{1}{\mu }{\displaystyle \sum _{k=1}^{\mu }{\displaystyle {\int }_{-\infty }^{\infty }xpk;\lambda \left(x\right)dx\text{.}}}$

Determining the density p_k;λ requires the use of order statistics. The z₁⁽ⁱ⁾ have standard normal density. The terms $z_1^{\left(t\right)}+\vartheta {\delta }^{\left(t\right)}$ are independently normally distributed with mean 0 and variance 1 + ϑ². The value of $z_1^{\left(t\right)}+\vartheta {\delta }^{\left(t\right)}$ is for given $z_1^{\left(i\right)}=x$ normally distributed with mean x and variance ϑ². For an index to have the kth largest value of $z_1^{\left(t\right)}+\vartheta {\delta }^{\left(t\right)}$, k – 1 of the indices must have larger values of $z_1^{\left(t\right)}+\vartheta {\delta }^{\left(t\right)}$ and λ – k must have smaller values of $z_1^{\left(t\right)}+\vartheta {\delta }^{\left(t\right)}$ As there are λ times k – 1 out of λ – 1 different such cases, it follows

$p_{k;\lambda }\left(x\right)=\frac{1}{2\pi \vartheta }\frac{\lambda !}{\left(\lambda -k\right)!\left(k-1\right)!}{\mathrm{e}}^{-\frac{1}{2}{x}^2}{\displaystyle {\int }_{-\infty }^{\infty }exp}\left(-\frac{1}{2}{\left(\frac{y-x}{\vartheta }\right)}^2\right){\left[\Phi \left(\frac{y}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\lambda -k}{\left[1-\Phi \left(\frac{y}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{k-1}\mathit{dy}$

for the density of z_k;λ

Inserting Equation (12) into Equation (11) and swapping the order of integration and summation it follows

$\overline{〈z_1〉}=\frac{1}{2\pi \mu \vartheta }{\displaystyle {\int }_{-\infty }^{\infty }x{\mathrm{e}}^{-\frac{1}{2}{x}^2}}{\displaystyle {\int }_{-\infty }^{\infty }exp\left(-\frac{1}{2}{\left(\frac{y-x}{\vartheta }\right)}^2\right)}{\displaystyle \sum _{k=1}^{\mu }\frac{\lambda !}{\left(\lambda -k\right)!\left(k-1\right)!}}{\left[\Phi \left(\frac{y}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\lambda -k}{\left[1-\Phi \left(\frac{y}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{k-1}\mathit{dydx}\text{.}$

Using the identity (compare [6], Equation (5.14))

${\displaystyle \sum _{k=1}^{\mu }\frac{\lambda !}{\left(\lambda -k\right)!\left(k-1\right)!}}{P}^{\lambda -k}{\left[1-P\right]}^{k-1}=\frac{\lambda !}{\left(\lambda -\mu -1\right)!\left(\mu -1\right)!}{\displaystyle {\int }_0^P{z}^{\lambda -\mu -1}{\left[1-z\right]}^{\mu -1}dz}$

it follows

$\overline{〈z_1〉}=\frac{\lambda -\mu }{2\pi \vartheta }\left(\begin{array}{c}\hfill \lambda \hfill \\ \hfill \mu \hfill \end{array}\right){\displaystyle {\int }_{-\infty }^{\infty }x{\mathrm{e}}^{-\frac{1}{2}{x}^2}}{\displaystyle {\int }_{-\infty }^{\infty }exp}\left(-\frac{1}{2}{\left(\frac{y-x}{\vartheta }\right)}^2\right){\displaystyle {\int }_0^{\Phi \left(y/\sqrt{1+{\vartheta }^2}\right)}{z}^{\lambda -\mu -1}{\left[1-z\right]}^{\mu -1}\mathit{dzdydx}\text{.}}$

Substituting $z=\Phi \left(u/\sqrt{1+{\vartheta }^2}\right)$ yields

$\begin{array}{l}\overline{〈z_1〉}=\frac{\lambda -\mu }{{\sqrt{2\pi }}^3\vartheta \sqrt{1+{\vartheta }^2}}\left(\begin{array}{c}\hfill \lambda \hfill \\ \hfill \mu \hfill \end{array}\right){\displaystyle {\int }_{-\infty }^{\infty }x{\mathrm{e}}^{-\frac{1}{2}{x}^2}}{\displaystyle {\int }_{-\infty }^{\infty }exp}\left(-\frac{1}{2}{\left(\frac{y-x}{\vartheta }\right)}^2\right)\\ \begin{array}{cc}\hfill \hfill & \hfill {\displaystyle {\int }_{-\infty }^{y}exp\left(-\frac{1}{2}\frac{u^2}{1+{\vartheta }^2}\right)}\hfill \end{array}{\left[\Phi \left(\frac{u}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\lambda -\mu -1}{\left[1-\Phi \left(\frac{u}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\mu -1}\mathit{dudydx}\text{,}\end{array}$

and changing the order of the integrations results in

$\begin{array}{l}\overline{〈z_1〉}=\frac{\lambda -\mu }{{\sqrt{2\pi }}^3\vartheta \sqrt{1+{\vartheta }^2}}\left(\begin{array}{c}\hfill \lambda \hfill \\ \hfill \mu \hfill \end{array}\right){\displaystyle {\int }_{-\infty }^{\infty }exp}\left(-\frac{1}{2}\frac{u^2}{1+{\vartheta }^2}\right){\left[\Phi \left(\frac{u}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\lambda -\mu -1}\\ \begin{array}{cc}\hfill \hfill & \hfill {\left[1-\Phi \left(\frac{u}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\mu -1}{\displaystyle {\int }_{-\infty }^{\infty }x{\mathrm{e}}^{-\frac{1}{2}{x}^2}}{\displaystyle {\int }_u^{\infty }exp}\left(-\frac{1}{2}{\left(\frac{y-x}{\vartheta }\right)}^2\right)\mathit{dydxdu}\text{.}\hfill \end{array}\end{array}$

The inner integrals can easily be solved. It is readily verified that

$\frac{1}{\sqrt{2\pi }\vartheta }{\displaystyle {\int }_{-\infty }^{\infty }x{\mathrm{e}}^{-\frac{1}{2}{x}^2}}{\displaystyle {\int }_u^{\infty }exp}\left(-\frac{1}{2}{\left(\frac{y-x}{\vartheta }\right)}^2\right)\mathit{dydx}=\frac{1}{\sqrt{1+{\vartheta }^2}}exp\left(-\frac{1}{2}{\left(\frac{u}{\sqrt{1+{\vartheta }^2}}\right)}^2\right)$

Therefore,

$\overline{〈z_1〉}=\frac{\lambda -\mu }{2\pi \left(1+{\vartheta }^2\right)}\left(\begin{array}{c}\hfill \lambda \hfill \\ \hfill \mu \hfill \end{array}\right){\displaystyle {\int }_{-\infty }^{\infty }exp}\left(-\frac{u^2}{1+{\vartheta }^2}\right){\left[\Phi \left(\frac{u}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\lambda -\mu -1}{\left[1-\Phi \left(\frac{u}{\sqrt{1+{\vartheta }^2}}\right)\right]}^{\mu -1}du\text{.}$

Using substitution $z=u/\sqrt{1+{\vartheta }^2}$ it follows

$\begin{array}{l}\overline{〈z_1〉}=\frac{\lambda -\mu }{2\pi \left(1+{\vartheta }^2\right)}\left(\begin{array}{c}\hfill \lambda \hfill \\ \hfill \mu \hfill \end{array}\right){\displaystyle {\int }_{-\infty }^{\infty }{\mathrm{e}}^{-x^2}}{\left[\Phi \left(x\right)\right]}^{\lambda -\mu -1}{\left[1-\Phi \left(x\right)\right]}^{\mu -1}dx\\ \begin{array}{cc}\hfill \hfill & \hfill =\frac{c_{\mu /\mu ,\lambda }}{\sqrt{1+{\vartheta }^2}}\hfill \end{array}\text{,}\end{array}$

Where c_μ/μ, denotes the (μ/μ,)-progress coefficient defined in Equation (7).

Acknowledgements

Support by the Deutsche Forschungsgemeinschaft (DFG) under grants Be 1578/4-1 and Be 1578/6-1 is gratefully acknowledged. The second author is a Heisenberg fellow of the DFG.