The most fundamental result in probability theory is the law of large numbers for a sequence (X n ) n 1 of independent and identically distributed real valued random variables. Define the empirical mean of (X n ) n 1 by

X n = 1 n n i=1 X i
The law of large numbers asserts that the empirical mean X n converges (almost surely) towards the theoretical mean E(X 1 ) provided that E(|X 1 |) is finite. The next fundamental results are the central limit theorem and Cramér's theorem. Both are refinements of the law of large numbers in two different directions. The central limit theorem describes the random fluctuations of X n around E(X 1 ). Cramér's theorem estimates the probability that X n deviates significantly from E(X 1 ) :

P X n E(X 1 ) + ε for ε > 0.
Such an event is called a "large deviations" event since it has a very small probability: it turns out that this probability decays exponentially fast with n. The first estimate of this kind can be traced back to Cramér's paper [START_REF] Cramér | Sur un nouveau théorème limite de la théorie des probabilités[END_REF] which deals with variables possessing a density. In [START_REF] Chernoff | A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations[END_REF] Chernoff relaxed this assumption. Then coming from statistical mechanics Lanford imported the subadditivity argument in the proof [START_REF] Lanford | Entropy and equilibrium states in classical statistical mechanics[END_REF]. Cramér's theory was extended to infinite dimensional topological vector spaces by Bahadur and Zabell [START_REF] Bahadur | Large deviations of the sample mean in general vector spaces[END_REF]. The classical texts of Azencott [START_REF] Azencott | Grandes déviations et applications[END_REF], Deuschel and Strook [START_REF] Deuschel | Large deviations[END_REF] and Dembo and Zeitouni [START_REF] Dembo | Large deviations techniques and applications[END_REF] take stock of the foregoing improvements. At this point in time classical proofs of Cramér's theorem in R resort either to the law of large numbers (see e.g. [START_REF] Dembo | Large deviations techniques and applications[END_REF]) or to Mosco's theorem (see e.g. [START_REF] Cerf | On Cramér's theory in infinite dimensions[END_REF]). We expose here a direct proof of Cramér's theorem in R based on convex duality. Not only is the proof shorter, but it can easily adapt to a broader setting.

Theorem (Cramér). Let (X n ) n 1 be a sequence of independent and identically distributed real valued random variables and let X n be the empirical mean:

X n = 1 n n i=1 X i
For all x ∈ R the sequence

1 n log P X n x converges in [-∞, 0] and lim n→∞ 1 n log P X n x = inf λ 0 log E e λX1 -λx
Let us define the entropy of the sequence

(X n ) n 1 by ∀x ∈ R s(x) = sup n 1 1 n log P X n x
and the pressure of X 1 (or the log-Laplace transform of the law of X 1 ) by

∀λ ∈ R p(λ) = log E e λX1
The entropy and the pressure may take infinite values. Our strategy is to show a dual version, in the sense of convex functions, of Cramér's theorem.

Proposition (dual equality). For all λ 0,

p(λ) = sup u∈R λu + s(u)
Proof. The classical Chebychev inequality will yield one part of the proof of the above equality. To prove the other part we condition X n to be bounded by K and then let K grow towards +∞. Since X 1 , . . . , X n are independent and identically distributed, we have for all λ 0

∀n ≥ 1 E e nλXn = E e λX1 n
Thus, for u ∈ R and n ≥ 1, it follows from Chebychev inequality that Next, we prove the converse inequality for λ = 0 : for all u ∈ R,

p(λ) = log E e λX1 = 1 n log E e nλXn
0 s(u) sup n 1 1 n log P X 1 u n = log P X 1 u
Hence, letting u go to -∞, we see that

sup u∈R s(u) = 0 = p(0)
Now let λ > 0 and K > 0. For all n 1, using the fact that X 1 , . . . , X n are independent and identically distributed, we have

log E e λX1 1 |X1| K = 1 n log E e λ(X1+•••+Xn) 1 |X1| K • • • 1 |Xn| K 1 n log E e nλXn 1 |Xn| K = 1 n log E e -nλK + Xn -K nλe nλu du 1 |Xn| K 1 n log e -nλK + E 1 -K u Xn 1 |Xn| K nλe nλu du
the last step being a consequence of Fubini's theorem. Since

E 1 -K u Xn 1 |Xn| K P X n u 1 |u| K e ns(u) 1 |u| K we get log E e λX1 1 |X1| K 1 n log e -nλK + K -K
nλe n(λu+s(u)) du

1 n log e -nλK + 2Knλ exp n sup u∈R λu + s(u)
Let K be large enough so that (recall that the supremum of s is 0)

-λK < sup u∈R λu + s(u)
Sending n to ∞ we obtain

log E e λX1 1 |X1| K sup u∈R λu + s(u)
Eventually sending K to +∞ we get

p(λ) sup u∈R λu + s(u)
To deduce Cramér's theorem from the dual equality we have just proved, we need some properties of the function s. First of all it follows from the definition of s that s is non-increasing.

Proposition. For all x ∈ R the sequence

1 n log P X n x converges in [-∞, 0] towards s(x). The function s : R → [-∞, 0] is concave.
Proof. Let x, y ∈ R with x y. Let also α ∈]0, 1[. Suppose that P X 1 y > 0 and let n m 1. Let n = mq + r be the Euclidian division of n by m. On the event

αq -1 k=0 m(k+1) i=mk+1 X i mx ∩ q-1 k= αq m(k+1) i=mk+1 X i my ∩ n i=mq+1 X i y
we have (remember that x y) :

s αx + (1 -α)y αs(x) + (1 -α)s(y)
If y is such that P X 1 y = 0, then

∀n 1 1 n log P X n y = -∞
whence s(y) = -∞ and the concavity inequality still holds.

We now finish the proof of Cramér's theorem. At this point we know that for all x ∈ R inf

λ 0 p(λ) -λx = inf λ 0 sup u∈R λ(u -x) + s(u)
It remains to prove that the latter quantity equals s(x). The result is standard in convex functions theory. Let us give an elementary proof in our setting. The right-hand side of the previous equation is clearly superior or equal to s(x) : take u = x. To prove the converse inequality we set c = inf x ∈ R : P X 1 x = 0 and we distinguish the three cases x < c, x > c and x = c.

• Suppose x < c. Since s is concave and non-increasing let -λ = s g (x) 0 be the left derivative of s at point x. Then s(x) > -∞ and ∀u ∈ R s(u) s(x) -λ(u -x) from which the result follows.

• Suppose x > c. Then s(x) = -∞ and, for all λ 0, p(λ) -λx = log E e λ(X1-x) log e λ(c-x) = λ(c -x) so the infimum over λ 0 is indeed -∞.

• Suppose x = c. Then, for all λ 0 and ε > 0, p(λ) -λc = log E e λ(X1-c) 1 X1<c-ε + 1 c-ε X1 c log e -λε + P X 1 c -ε

Taking the infimum over λ 0 and sending ε to 0 we get inf λ 0 p(λ) -λx log P X 1 c s(c)

A

  short proof of Cramér's theorem in R Raphaël Cerf and Pierre Petit Université Paris Sud February 18, 2010

1 n log e nλu P e nλXn e nλu λu + 1 n

 11 log P X n u Hence, taking the supremum over n 1 and then over u ∈ R, we get ∀λ 0 p(λ) sup u∈R λu + s(u)

  mx + q -αq my + ry n αx + (1 -α)y ThereforeP X n αx + (1 -α)y P X m x αq P X m y q-αq P X 1 y r Since P X 1 y > 0 and 0 r < m,taking logarithms, dividing by n and sending n to ∞, we get for all m 1 lim inf n→∞ 1 n log P X n αx + (1 -α)y α m log P X m x + 1 -α m log P X m y If x = y, taking the supremum over m 1, we conclude that lim n→∞ 1 n log P X n x = s(x) If x < y, sending m to ∞, we get


Keywords: 1991 Mathematics Subject Classification. 60F10, 60J10, 92D15 Wentzell theory, genetic algorithms, stochastic optimization

A NEW GENETIC ALGORITHM

Raphaël CERF

CNRS, Université d'Orsay April 1995

Abstract. Here is a new genetic algorithm. It is built by randomly perturbing a two operators crossover-selection scheme. Three conditions of biological relevance are imposed on the crossover. A new selection mechanism is used, which has the decisive advantage of preserving the diversity of the individuals in the population. The attractors of the unperturbed process are particular equi-fitness subsets of populations endowed with a rich structure. The random vanishing perturbations are twofold: local perturbations of the individuals (mutations) and loosening of the selection pressure. When the population size is greater than a critical value which depends strongly on the optimization problem, their delicate asymptotic interaction ensures the convergence (possibly in finite time) of the population toward the ideal attractor whose populations contain all the maxima of the fitness function. The process explores without respite the neighbourhoods of the best points found so far (instead of focusing on a particular point) and finds simultaneously all the global maxima of the fitness function; it seems to be the first cooperative search procedure of this kind.

Introduction

In the realm of stochastic optimization, attention has focused essentially on two techniques during the last decade: simulated annealing [START_REF] Aarts-P | Simulated annealing: theory and applications[END_REF] and evolutionary algorithms [START_REF] Goldberg | Genetic algorithms in search, optimization and machine learning[END_REF][START_REF] Holland | Adaptation in natural and artificial systems[END_REF].

The fundamental problem may be stated as follows: given a finite but huge space (the size precludes any exhaustive search procedure) endowed with a transition mechanism and a real-valued function defined on this space, determine the set of its global maxima, or find at least sub-optimal points, as fast as possible.

The theory of the simulated annealing is now extensively developed and a great number of results describing the dynamics of this kind of algorithms in various settings are available [START_REF] Aarts-P | Simulated annealing: theory and applications[END_REF][START_REF] Catoni | Large deviations for annealing[END_REF][START_REF] Catoni | Rough large deviations estimates for simulated annealing. Application to exponential schedules[END_REF][START_REF] Catoni | Sharp large deviations estimates for simulated annealing algorithms[END_REF][START_REF] Catoni | Applications of sharp large deviations estimates to optimal cooling schedules[END_REF][START_REF] Deuschel | L 2 convergence of time non-homogeneous Markov processes: I. spectral estimates[END_REF][START_REF] Faigle | Note on the convergence of simulated annealing algorithms[END_REF][START_REF] Geman-D. Geman | Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images[END_REF][START_REF] Hajek | Cooling schedules for optimal annealing[END_REF][START_REF] Hajek-G | Simulated annealing -to cool or not[END_REF][START_REF] Hajek-G | The time complexity of maximum matching by simulated annealing[END_REF][START_REF] Holley-S. Kusuoka-D | Asymptotics of the spectral gap with applications to the theory of simulated annealing[END_REF][START_REF] Holley-D | Simulated annealing via Sobolev inequalities[END_REF][START_REF] Hwang-S | Singular perturbed Markov chains and exact behaviours of simulated annealing process[END_REF][START_REF] Jerrum | Large cliques elude the Metropolis process[END_REF][START_REF] Lundy-A | Convergence of an annealing algorithm[END_REF][START_REF] Sorkin | Efficient simulated annealing on fractal energy landscapes[END_REF][START_REF] Trouvé | Asymptotical behaviour of several interacting annealing processes[END_REF][START_REF] Trouvé | Convergence optimale pour les algorithmes de recuits généralisés[END_REF][START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF][START_REF] Trouvé | Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms[END_REF]. As far as we know, the most accurate work in this area has been achieved by Catoni, in the spirit of the Freidlin-Wentzell theory [START_REF] Catoni | Large deviations for annealing[END_REF][START_REF] Catoni | Rough large deviations estimates for simulated annealing. Application to exponential schedules[END_REF][START_REF] Catoni | Sharp large deviations estimates for simulated annealing algorithms[END_REF][START_REF] Catoni | Applications of sharp large deviations estimates to optimal cooling schedules[END_REF]. Nevertheless, the simulated annealing presents a fundamental drawback: it is sequential in nature.

In an attempt to investigate the theoretical aspects of the parallelization of this algorithm, Trouvé carried out a systematic study (initiated by Hwang and Sheu [START_REF] Hwang-S | Singular perturbed Markov chains and exact behaviours of simulated annealing process[END_REF]) of a broader class of algorithms he baptized generalized simulated annealing [START_REF] Trouvé | Convergence optimale pour les algorithmes de recuits généralisés[END_REF][START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF][START_REF] Trouvé | Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms[END_REF]. As it turns out, this framework is also well adapted for evolutionary algorithms. Let us mention that several recent studies have been devoted to this kind of processes. Holley, Kusuoka and Stroock [START_REF] Holley-S. Kusuoka-D | Asymptotics of the spectral gap with applications to the theory of simulated annealing[END_REF][START_REF] Holley-D | Simulated annealing via Sobolev inequalities[END_REF] have developed an approach leading to an estimation of the second eigenvalue of the infinitesimal generator of the Markov process. This method is particularly well suited in reversible situations, but it has also been recently extended to non-symmetric annealing processes by Deuschel and Mazza [START_REF] Deuschel | L 2 convergence of time non-homogeneous Markov processes: I. spectral estimates[END_REF] and is thus potentially applicable to genetic algorithms. One of our major goals is to show how the large deviations theory of Markov chains with rare transitions can be used to study the convergence of genetic algorithms.

In a first paper [START_REF] Cerf | Asymptotic convergence of genetic algorithms[END_REF], we proposed a Markovian model of Holland's simple genetic algorithm which is built by randomly perturbing a very simple selection scheme: mutations and crossovers are considered as vanishing random perturbations. We proved that the convergence toward the global maxima of the fitness function becomes possible when the population size is greater than a critical value (which depends strongly on the optimization problem). Surprisingly, the crossover is not fundamental to ensure this convergence: the crucial point is the delicate asymptotic interaction between the local perturbations of the individuals (i.e. the mutations) and the selection pressure.

In a second paper [START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF], we used the concepts introduced by Catoni [START_REF] Catoni | Large deviations for annealing[END_REF][START_REF] Catoni | Rough large deviations estimates for simulated annealing. Application to exponential schedules[END_REF][START_REF] Catoni | Sharp large deviations estimates for simulated annealing algorithms[END_REF] and further generalized by Trouvé [START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF][START_REF] Trouvé | Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms[END_REF] to fathom more deeply the dynamics of the two operators mutation-selection algorithm when the population size becomes very large. The key result lies in the structure of the trajectories of populations joining two uniform populations: a small group of individuals sacrifice themselves in order to create an ideal path which is then followed by all other individuals. As a consequence, the various quantities associated with the algorithm (such as the communication cost, the virtual energy, the communication altitude . . . ) are affine functions of the population size. We proved that the hierarchy of cycles on the set of the uniform populations stabilizes. Furthermore, if the mutation kernel is symmetric, the limiting distribution is the uniform distribution over the set of the global maxima of the fitness function.

In this third paper, we introduce two major modifications to the previous schemes. The crossover is now integrated in the unperturbed process and is not considered any more as a random vanishing perturbation: although this operator is not essential to ensure the desired convergence, it certainly increases the efficiency of the algorithm. Three conditions of biological relevance are imposed on the crossover: • When two identical individuals mate, they produce offsprings identical to themselves.

• There is always a non-zero probability that nothing happens during a crossover.

• The two individuals of the mating pair play symmetric roles (the populations are asexual). The first condition is essential for our algorithm to work for every fitness function; the second condition makes the analysis somewhat easier; the third condition is a natural symmetry assumption which could be removed. Furthermore, we propose a new selection mechanism which has the decisive advantage of preserving the diversity of the individuals in the population.

The analysis of the algorithm follows the road opened by Freidlin and Wentzell [START_REF] Freidlin-A | Random perturbations of dynamical systems[END_REF]. Unlike the situations studied in [START_REF] Cerf | Asymptotic convergence of genetic algorithms[END_REF][START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF], the structure of the set of the attractors of the unperturbed process is very rich: these are particular subsets of populations and they stand in one to one correspondence with the equi-fitness subsets of the state space whose cardinality is less than the population size. When the population size is large enough, there is a unique ideal attractor whose populations contain all the maxima of the fitness function. We study the communication cost between attractors: the costs of bad transitions (either those which decrease the maximal fitness of the population or those which lose some peak fitness individuals) increase linearly with the population size, whereas the costs of good transitions (those which create some new peak fitness individuals) remain bounded. As a consequence, when the population size is greater than a critical value, the minimum of the virtual energy corresponds to the ideal attractor previously described. Therefore the sequence of the stationary measures (associated with a fixed level of intensity of the perturbations) concentrates on this attractor as the perturbations vanish. The remaining problem is to adapt carefully the rate of decreasing of the perturbations in order to obtain an inhomogeneous Markov chain with the same limiting law. Besides, it is possible to ensure a stronger convergence: we may force the process to be forever trapped in the attraction basin of the ideal attractor after a finite number of transitions. Furthermore, when the population size is large, the cycles which do not contain the ideal attractor are reduced to one single attractor and the optimal convergence exponent increases faster than an affine function of the population size. We show also how our general model specializes to the case where the state space is {0, 1} N ; we discuss the role of the crossover and compare the genetic algorithm with the parallel (independent) simulated annealing on a small numerical example.

One might wonder whether this asymptotic point of view is relevant for analyzing genetic algorithms. Indeed, the current state of this large deviations theory (even the sharp large deviations estimates of Catoni [START_REF] Catoni | Sharp large deviations estimates for simulated annealing algorithms[END_REF][START_REF] Catoni | Applications of sharp large deviations estimates to optimal cooling schedules[END_REF]) does not yet provide probability bounds which can be effectively computed on a real problem. Therefore one does not know in practice when the process is near the asymptotical regime. Anyway we hope that the paradigm we propose is one of the very first steps toward a complete theory. Asymptotic convergence is the least thing to require for such stochastic algorithms. Moreover our model should shed some light on the true behavior of genetic algorithms. It provides also a tool to make theoretical comparisons: we are able to analyze the optimal convergence exponent for large population sizes (its rate of increase is a quantitative measurement of the intrinsic parallelism of genetic algorithms), to feel the impact of the crossover operator on it, or to compare it with the one associated with parallel (independent) simulated annealing.

Finally, let us summarize the important aspects of this work. Our algorithm finds simultaneously all the global maxima of the objective function in finite time and thus solves completely the optimization problem: it seems to be the first of this kind. The cornerstone of this cooperative search procedure is the delicate asymptotic interaction between the mutations and our enhanced selection mechanism; the process explores simultaneously and without respite the neighbourhoods of the best points found so far (instead of focusing on a particular point). Moreover, we hope to have found the right way of using the crossover operator.

This paper has the following structure. The sections 2 to 7 are devoted to the description of the model: the unperturbed process, its attractors and the random perturbations. The main results are presented in section 8. The role of the crossover is analyzed in section 9. In section 10 we show how our model enters the class of generalized annealing processes. We then give technical results in sections 11 to 14 and prove the main results in the last section 15.

General conventions. The cardinality of a set X will be noted indifferently |X| or card X and its characteristic function 1 X . We adopt usual conventions concerning empty sets:

Q ∅ = 1, P ∅ = 0, min ∅ = +∞, max ∅ = -∞.
If s is a real number, s denotes the unique integer such that s ≤ s < s + 1. The Kronecker symbol δ(i, j) will be used to denote the identity matrix indexed by E:

∀i, j ∈ E δ(i, j) = 0 if i = j, δ(i, j) = 1 if i = j.
For any integer r, the set of the permutations over {1 • • • r} is denoted by S(r).

The fitness landscape

We recall that a Markov kernel k on a finite set X is a a function k(x, y) defined on X ×X with values in [0, 1] verifying

∀x ∈ X y∈X k(x, y) = 1.
Definition 2.1. An abstract fitness landscape consists in four objects (E, f, α, β) where • E, the search space, is a finite space of states, • f , the fitness function, is a positive non-constant function defined on E, • α, the mutation kernel, is an irreducible Markov kernel on E, • β, the crossover kernel, is a Markov kernel on the set E × E.

The points of E will be called individuals and will be mostly denoted by the letters i, j, e. The quantity α(i, j) determines the rate at which the individual i mutates to j. The irreducibility assumption on α, which means that

∀i, j ∈ E ∃e 1 , • • • , e r ∈ E e 1 = i, e r = j, ∀k ∈ {1 • • • r -1} α(e k , e k+1 ) > 0,
is essential to ensure that the whole space E can be explored with the help of the mutation mechanism.

Similarly, the quantity β((i 1 , j 1 ), (i 2 , j 2 )) is interpreted as the probability of producing the pair of individuals (i 2 , j 2 ) by performing a crossover on the couple (i 1 , j 1 ). Throughout this work, we impose the following conditions on the kernel β:

∀i ∈ E β((i, i), (i, i)) = 1, (1) ∀i, j ∈ E β((i, j), (i, j)) > 0, (2) ∀i 1 , j 1 , i 2 , j 2 ∈ E β((i 1 , j 1 ), (i 2 , j 2 )) = β((j 1 , i 1 ), (j 2 , i 2 )). ( 3
)
These three conditions have a natural biological interpretation. Condition [START_REF] Aarts-P | Simulated annealing: theory and applications[END_REF] states that when two identical individuals mate, they produce offsprings identical to themselves. Condition [START_REF] Catoni | Large deviations for annealing[END_REF] states that there is a non-zero probability that nothing happens during the crossover. Condition (3) states that the two individuals of the mating pair play symmetric roles (our population is asexual). The set f * of the global maxima of f is

f * = { i ∈ E : f (i) = max j∈E f (j) }
and f (f * ) is the maximum value of f over E, i.e. max j∈E f (j). Symbols with a star * in superscript will denote sets realizing the minimum or the maximum of a particular functional. The main goal of a genetic algorithm is to locate the points of f * , or at least to find suboptimal points. The minimal and maximal variations of the fitness function are

δ = min { |f (i) -f (j)| : i, j ∈ E, f (i) = f (j) }, ∆ = max { |f (i) -f (j)| : i, j ∈ E }.
Let λ be a positive real number. We put f λ = f -1 ({λ}), which is the set of the points of the search space having fitness λ, and we define similarly

f + λ = f -1 (]λ, ∞[), f - λ = f -1 ([0, λ[). The maximal cardinality of a level set of the fitness function is Λ = max { |f λ | : λ ∈ R * + }. If F is a subset of E, f (F ) (or sometimes simply f F ) denotes the set { f (i) : i ∈ F }.

The population space

A key principle of genetic algorithms is to make a population of individuals evolve simultaneously in the fitness landscape. Let m be the population size of our algorithm. A genetic algorithm is a stochastic process with state space the population space E m ; the m-uples of elements of E, i.e. the points of the set E m , are called populations and will be mostly denoted by the letters x, y, z, u, v. We define a bracket operator [ ] on E m with values in P(E), the set of all the subsets of E, by

x = (x 1 , • • • , x m ) ∈ E m -→ [x] = { x k : 1 ≤ k ≤ m } i.e. [x]
is the set of all individuals present in the population x. With f we associate a function f defined on E m by

f (x) = f (x 1 , • • • , x m ) = max { f (x k ) : 1 ≤ k ≤ m } i.e. f (x)
is the maximal fitness of the individuals of the population x. In this way, the fitness landscape (E, f, α, β) induces a landscape structure (E m , f ) on the population space E m . A key issue is to understand this new landscape and to determine whether it is easier to optimize (E m , f ) than the naive m-fold copy of (E, f ). The peculiarity of genetic algorithms is to introduce a cooperative dynamics on the search space. We now introduce several notations describing the repartition of the fitness values in a population or in a set of populations. For x in E m , x denotes the set of those elements of [x] which realize the value f (x):

x = { x k : 1 ≤ k ≤ m, f (x k ) = f (x) }.
The previous definitions [x], f (x), x are extended to P(E m ), the set of all the subsets of E m , in a natural way: if K is a subset of E m , we have

[K] = { x k : 1 ≤ k ≤ m, x = (x 1 , • • • , x m ) ∈ K }, f (K) = max { f (x k ) : 1 ≤ k ≤ m, x = (x 1 , • • • , x m ) ∈ K }, K = { x k : 1 ≤ k ≤ m, x = (x 1 , • • • , x m ) ∈ K, f (x k ) = f (K) }.
For x in E m , we let x λ = [x] ∩ f λ (the individuals of the population x having fitness λ) and we number the elements of the set x λ

x λ = { x λ 1 , • • • , x λ |x λ | }
in the order they appear in the sequence (x k , 1 ≤ k ≤ m). Equivalently, we have

∀h, k 1 ≤ h < k ≤ |x λ | min { r : x r = x λ h } < min { r : x r = x λ k }.
Such a numbering is clearly unique. Whenever λ does not belong to f [x], the set x λ is empty. For the special case λ = f (x) (i.e. where λ is the maximal value of the fitness in the population x), we use the notation

x = { x 1 , • • • , x |b x| } (i.e.
we replace x λ by x in the preceding notation).

Finally, for x in E m , we denote by

λ x 1 , • • • , λ x |f [x]| the |f [x]| elements of the set f [x] (i.
e. the set of the fitness values observed in the population x), where again the indexation respects the order of appearance of the elements of f

[x] in the sequence (f (x k ), 1 ≤ k ≤ m), or equivalently ∀h, k 1 ≤ h < k ≤ |f [x]| min { r : f (x r ) = λ x h } < min { r : f (x r ) = λ x k }.
When the context is unambiguous, we will drop the superscript in the above notations.

Example: the case

E = {0, 1} N
We specialize our general model to the case where the state space E is {0, 1} N (N ∈ N). A point i of E is a word of length N over the alphabet {0, 1} and is noted i = i 1 • • • i N where i k ∈ {0, 1}. The Hamming distance H(i, j) between two points i, j of E is the number of letters where i and j differ:

H(i, j) = card { k : 1 ≤ k ≤ m, i k = j k }.
The mutation kernel α is defined by

α(i, j) = 0 if H(i, j) > 1, 1/N if H(i, j) = 1.
It is irreducible: the minimal number of transitions necessary to join two arbitrary points of E through the kernel α is N . In order to build the crossover operator, we define now a cutting operator

T k for k in {0 • • • N }; T k maps E × E onto E × E and for i, j in E, we put T k (i, j) = (i , j ) where i = i 1 • • • i k j k+1 • • • j N , j = j 1 • • • j k i k+1 • • • i N .
Notice that T 0 only exchanges the two individuals of the mating pair, i.e. T 0 (i, j) = (j, i), whereas T N is the identity map over E × E.

For any pairs (i, j) and (i , j ) of E × E, we put

C((i, j), (i , j )) = card { k : 1 ≤ k ≤ N, T k (i, j) = (i , j ) }
and we define finally the crossover kernel β by β((i, j), (i , j )) = C((i, j), (i , j )) + C((j, i), (i , j ))

(i ,j )∈E×E C((i, j), (i , j )) + C((j, i), (i , j ))
.

It is a straightforward matter to check that conditions (1), ( 2), (3) are satisfied.

5. The unperturbed Process (X ∞ n ) We first describe the ground process which drives the algorithm. When there is no random perturbation, the process under study is a Markov chain (X ∞ n ) with state space E m . The superscript ∞ reflects the fact that this process corresponds to the limit behavior of our model, when all perturbations vanish. The transition mechanism from X ∞ n to X ∞ n+1 is decomposed in two stages:

X ∞ n crossover ------→ Z ∞ n selection ------→ X ∞ n+1 .
We describe now in detail the crossover and selection operators.

5.1. X ∞ n -→ Z ∞ n : crossover.
The phenomenon of crossover is modeled as a random operation on the couples formed by consecutive individuals of the population X ∞ n . This random operation is the one naturally associated to the crossover kernel β of the abstract fitness landscape (definition 2.1). The transition probabilities from

X ∞ n to Z ∞ n are (4) P (Z ∞ n = z/X ∞ n = x) = δ m (x m , z m ) 1≤k≤m/2 β ((x 2k-1 , x 2k ), (z 2k-1 , z 2k ))
where δ m (i, j) = δ(i, j) if m is odd (the last individual of the population has no mating partner and remains unchanged after crossover) and δ m (i, j) = 1 if m is even. Notice here a fundamental difference with the model studied in [START_REF] Cerf | Asymptotic convergence of genetic algorithms[END_REF]: the crossover is now incorporated into the unperturbed process.

5.2. Z ∞ n -→ X ∞ n+1 : selection.
We propose here an enhanced version of the selection mechanism used in the previous models [START_REF] Cerf | Asymptotic convergence of genetic algorithms[END_REF][START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF] which has the decisive advantage of preserving the diversity of the individuals present in the population. This mechanism may be described roughly as follows. Suppose Z ∞ n = z. To build the population X ∞ n+1 = x, we first select randomly with the uniform distribution a permutation σ of S(| z|). We divide the set of indices {1 • • • m} in | z| + 1 parts of approximately the same size (around m/(| z| + 1) ).

The components of the r-th part (for 1 ≤ r ≤ | z|) are set equal to z σ(r) , that is, roughly, for the indices k such that

1 + (r -1) m | z| + 1 ≤ k ≤ r m | z| + 1
we put x k = z σ(r) (for , see the initial conventions). The components of the (| z| + 1)-th part are chosen independently with the uniform distribution on the set z. We now explicit precisely this transition mechanism. We first define a triangular array of integers τ (k, h),

0 ≤ k ≤ h + 1, 1 ≤ h ≤ m, by ∀h ∈ {1 • • • m} τ (0, h) = 1, τ (h + 1, h) = m, ∀k, h 1 ≤ k ≤ h ≤ m τ (k, h) = 2k m 2(h + 1) + 1.
Let x and z be two elements of E m . If there exists a permutation σ of S(| z|) such that

∀h ∈ {1 • • • | z|} ∀k τ (h -1, | z|) ≤ k < τ (h, | z|) x k = z σ(h) then (5) P X ∞ n+1 = x/Z ∞ n = z = 1 | z|! τ (|b z|,|b z|)≤k≤m 1 b z (x k ) card z .
If no such permutation exists, then

P X ∞ n+1 = x/Z ∞ n = z = 0. Remark 1.
In formula [START_REF] Catoni | Applications of sharp large deviations estimates to optimal cooling schedules[END_REF], the | z|! stands for the choice of a random permutation belonging to S(| z|), and the product corresponds to the choice of the components of x whose indices belong to the (| z| + 1)-th part.

Remark 2. The first | z| parts of x have an even cardinal, so that the crossover can't act on a pair of individuals belonging to distinct parts. Since in addition each such part contains only one type of individual, condition [START_REF] Aarts-P | Simulated annealing: theory and applications[END_REF] shows that the crossover operator will have no effect on the first | z| parts of x. The main interest of the (| z| + 1)-th part is to give the opportunity to distinct individuals of | z| to mate without constraints. Remark 3. If m < 2(| z| + 1), the first | z| parts of x are empty, so that the components of x are chosen independently with the uniform distribution on the set z. However, the dynamics of the algorithm becomes particularly interesting when m is large (as will be shown later), and such situations won't then occur.

The attractors of the chain (X ∞

n ) Due to the selection mechanism, the populations generated by the Markov chain (X ∞ n ) have a very specific structure. In fact, the Markov chain (X ∞ n ) wanders through particular subsets of E m which we call attractors. These subsets play the role of the attractors of the deterministic dynamical system in the Freidlin-Wentzell theory [START_REF] Freidlin-A | Random perturbations of dynamical systems[END_REF]. The aim of this section is to investigate the zoology of the attractors of the chain (X ∞ n ) and to understand the dynamics of (X ∞ n ) on these attractors. Definition 6.1. The attractors of the chain (X ∞ n ) are the sets of populations K such that

i) [K] = K ii) a population x = (x 1 , • • • , x m ) of E m belongs to K if and only if • ∀r ∈ {1 • • • | K|} ∀k, h τ (r -1, | K|) ≤ k, h < τ (r, | K|) =⇒ x k = x h , • { x k : 1 ≤ k < τ (| K|, | K|) } = [K], • { x k : τ (| K|, | K|) ≤ k ≤ m } ⊂ [K].
The set of all the attractors is denoted by K (thus K ∈ P(P(E m ))).

Remark. Notice that the property ii) is an equivalence: that is, each population x satisfying the three conditions in ii) has to belong to K whenever K is an attractor. Conversely, each population in K must fulfill these conditions.

Condition i) implies that the populations of the attractors are equi-fitness populations (i.e. populations whose all individuals have the same fitness). More precisely, we have

∀K ∈ K ∃λ ∈ R * + ∀x ∈ K [x] ⊂ f λ
i.e. all the individuals belonging to the populations of a fixed attractor are in the same level set of f . We denote by K λ (respectively

K + λ , K - λ ) the set of attractors K such that [K] ⊂ f λ (resp. [K] ⊂ f + λ , [K] ⊂ f - λ ).
For an attractor K, we denote by f (K) the unique real number λ such that K belongs to K λ . We denote by K * the attractors included in f * (i.e. K * = K f (f * ) ) and by K * the unique attractor (it exists for m ≥ |f * |) such that [K * ] = f * . We let also K - * = K - f (f * ) . The transition mechanism implies that the process (X ∞ n ) is instantaneously absorbed in the set of the populations which belong to attractors, i.e.

∀x ∈ E m P (∀n ≥ 1 ∃K ∈ K X ∞ n ∈ K/X ∞ 0 = x) = 1.
Moreover, as a consequence of condition (2) on the crossover kernel β, we see that, for each attractor K and each population x in K, the probability

P X ∞ n+1 ∈ K/X ∞ n =
x is positive so that the process has a non-zero probability of staying in an attractor. 10

We distinguish two kinds of attractors. An attractor K is said to be unstable if

∃x ∈ K P X ∞ n+1 ∈ K/X ∞ n = x < 1.
An attractor K is said to be stable if

∀x ∈ K P X ∞ n+1 ∈ K/X ∞ n = x = 1.
Notice that the bracket operator [ ] provides a one to one correspondence between the set K of all the attractors and the subset E of P(E) defined by

E = { F ⊂ E : |F | ≤ m, F = F }.
In fact, if K is an attractor, for each x in K, we have [x] = [K], i.e. the bracket operator is constant over K and thus characterizes K. As a consequence, two distinct attractors do not intersect. When m is small, the set E clearly depends on m, but for m ≥ Λ, it does not depend any more on m, nor does the structure of the set of attractors K: only the size of the populations changes, and the composition of the attractors is stabilized. We use the crossover kernel β to build an operator on the set P(E). If F is a subset of E, we define

β(F ) = { i ∈ E : ∃(i , j , j) ∈ F × F × E β((i , j ), (i, j)) > 0 }.
The operator β is the composition of the operators β and , i.e.

β(F ) = { i ∈ β(F ) : f (i) = f (β(F )) }.
We have the following characterization of the stable attractors.

Lemma 6.2. An attractor

K of K is stable if and only if β([K]) = [K] and m ≥ 2(| K| + 1).
Proof. This is an immediate consequence of the transition mechanism of the process (X ∞ n ): if the above conditions are satisfied, we have

P [X ∞ n+1 ] = [K]/X ∞ n ∈ K = 1. If β([K]) = [K],
there is a non-zero probability that the crossover creates new individuals not belonging to [K] with a fitness greater or equal than f (K), so that X ∞ n+1 has a positive probability of leaving K. If m < 2(| K| + 1), the selection mechanism does not guarantee the survival of all the individuals of [K] so that

P [X ∞ n+1 ] [K]/X ∞ n ∈ K > 0.
We define a partial relation ≺ ∞ on K: for each pair K 1 , K 2 of attractors, we have

K 1 ≺ ∞ K 2 ⇐⇒ ∃x ∈ K 1 ∃y ∈ K 2 ∃r ∈ N P X ∞ n+r = y/X ∞ n = x > 0.
This relation is reflexive and transitive. In addition, the process X ∞ n can leave an attractor only by creating with the crossover new individuals whose fitness is greater or equal to the fitness of the starting attractor. Thus

K 1 ≺ ∞ K 2 =⇒ [K 2 ] ⊂ ∞ n=0 β (• • • β ( β n times b β ([K 1 ])))
and the fitness cannot decrease during such a transition:

K 1 ≺ ∞ K 2 , f (K 1 ) = f (K 2 ) =⇒ f (K 1 ) < f (K 2 ).
Suppose m ≥ 2(Λ + 1). The selection mechanism then never causes a loss of diversity within a level set of f so that

K 1 ≺ ∞ K 2 , f (K 1 ) = f (K 2 ) =⇒ [K 1 ] ⊂ [K 2 ]
and the relation ≺ ∞ is then a partial order on K. If x is a population of E m which belongs to a (necessarily unique) attractor K, we put K(x) = K. It follows from the very definition of the relation

≺ ∞ that ∀n ≥ 1 K(X ∞ n ) ≺ ∞ K(X ∞ n+1 ) i.e. the sequence (K(X ∞ n )) n≥1 is increasing in the ordered set (K, ≺ ∞ ).
Since K is finite, this sequence is stationary; with probability one, the limit

lim n→∞ K(X ∞ n ) = K ∞ is a maximal element of K for the order ≺
∞ . Yet, the maximal elements of K are precisely the stable attractors. Finally, let K be a stable attractor. For any populations x, y belonging to K, the probability transition P X ∞ n+1 = y/X ∞ n = x is independent of x and y (it is completely determined by the set [K]). As a consequence, the process (X ∞ n ) admits a unique invariant probability measure on the attractor K, which is the uniform distribution.

Remark. The main role of the crossover is to make unstable some attractors. Suppose for instance we define the kernel β 0 by

∀i 1 , j 1 , i 2 , j 2 ∈ E β 0 ((i 1 , j 1 ), (i 2 , j 2 )) = 1 2 δ(i 1 , i 2 )δ(j 1 , j 2 ) + 1 2 δ(i 1 , j 2 )δ(j 1 , i 2 )
so that the crossover can only exchange the individuals of the mating pair and never creates new individuals. The corresponding algorithm is then a mutation-selection algorithm. In this case, all the attractors are stable whenever m ≥ 2(| K| + 1).

A numerical example on the space E = {0, 1} 3 . We consider the space E = {0, 1} 3 and we define the fitness function f by

f ({001, 011}) = {1}, f ({010, 101}) = {2}, f ({100}) = {3}, f ({000, 110, 111}) = {4}.
We take m = 10. There are 15 attractors. If F is an equi-fitness subset of E, we denote by K(F ) the associated attractor. The attractors K(010, 101) and K(000, 111) are unstable. All others attractors are stable. Actually, we have

K(000, 111) ≺ ∞ K(000, 110, 111), K(010, 101) ≺ ∞ K(100), K(010, 101) ≺ ∞ K(110).
The ideal attractor K * = K(000, 110, 111) contains 3! 3 4 = 486 populations.

A typical example of such a population is (110, 110, 000, 000, 111, 111, 000, 111, 110, 000).

7. The perturbed Markov chain (X l n ) The three operators of a genetic algorithm play different roles: the mutation tends to disperse the population over the space E, the crossover helps the information to spread quickly over the population and the selection tends to concentrate the population on the current best individual. Our point of view is to consider the mutation and the selection as random perturbations of very crude operators: random perturbations of the identity map for the mutations, random perturbations of the very strong selection mechanism of the chain (X ∞ n ) for the selection. Within this framework we are able to carry out an analysis of the asymptotic dynamics of the algorithm when the perturbations vanish. It is of course questionable whether this paradigm is relevant in practice. A major remaining issue is to obtain operational probability bounds for real optimization problems. There are several such attempts in this direction for sequential simulated annealing. Hajek and Sasaki study a maximum matching problem [START_REF] Hajek-G | The time complexity of maximum matching by simulated annealing[END_REF], Jerrum a maximum clique problem [START_REF] Jerrum | Large cliques elude the Metropolis process[END_REF] and they analyze the rate of growth of the time necessary to reach a solution with a given accuracy when the size of the problem tends to infinity. Jerrum and Sinclair succeed in building polynomial-time algorithms designed to approximate the partition function of the Ising model [START_REF] Jerrum-A | Polynomial-time approximation algorithms for the Ising model[END_REF]. Lundy and Mees describes situations where convergence is exponentially long, and others where termination occurs in polynomial time with a good practical confidence [START_REF] Lundy-A | Convergence of an annealing algorithm[END_REF]. Sinclair develops techniques to handle the multicommodity flow [START_REF] Sinclair | Improved bounds for mixing rates of Markov chains and multicommodity flow[END_REF]. Sorkin investigates the simulated annealing on fractal energy landscapes [START_REF] Sorkin | Efficient simulated annealing on fractal energy landscapes[END_REF]. These interesting results rely on features which depends strongly on the problem under study and cannot be generalized easily. They are aimed at finding efficient implementations on real problems.

Nevertheless our abstract setting for genetic algorithms yields general conditions ensuring the convergence of the genetic algorithm for any fitness landscape. We also put forward the existence of critical population sizes. The paradigm we propose is somewhat different from the practical implementations of genetic algorithms, where the parameters controlling the mutation and the selection are kept constant in time. On one hand our analysis might be interpreted as the analysis of these temporally homogeneous genetic algorithms for small values of the mutation rate and a strong selection pressure. The asymptotic dynamics therefore gives a sharpened and simplified picture of the true dynamics. On the other hand, the scheme of decreasing perturbations is a new procedure which should be tested in practice to see whether it succeeds in accelerating the convergence (in the same way that simulated annealing is an attempt to speed up the Metropolis algorithm).

We now describe precisely the perturbed transition mechanism. The previous Markov chain (X ∞ n ) is randomly perturbed by two distinct mechanisms. The first one acts directly upon the population and mimics the phenomenon of mutation. The second one consists in loosening the selection of the individuals. The intensity of the perturbations is governed by an integer parameter l: as l goes to infinity, the perturbations progressively disappear. The transition mechanism of the perturbed Markov chain (X l n ) is decomposed in three stages:

X l n mutation ------→ Y l n crossover ------→ Z l n selection ------→ X l n+1 . 7.1. X l n -→ Y l n : mutation.
The mutations are modeled by random independent perturbations of the individuals of the population X l n . These random perturbations are built with the help of the mutation kernel α of the abstract fitness landscape (definition 2.1). Let a be a positive real number, which we call the mutation cost. Define

α l (i, j) = α(i, j)l -a if i = j 1 -e =i α(i, e)l -a if i = j
so that α l is an irreducible Markov kernel on E.

The transition probabilities from X l n to Y l n are given by

P Y l n = y/X l n = x = α l (x 1 , y 1 ) • • • α l (x m , y m ).
Note that ( 6)

lim l→∞ P Y l n = y/X l n = x = δ(x 1 , y 1 ) • • • δ(x m , y m )
i.e. the mutations vanish when l goes to infinity.

7.2. Y l n -→ Z l n : crossover. The crossover is not perturbed in any way: this stage is exactly the same as the passage from X ∞ n to Z ∞ n (formula (4)). We define the crossover kernel

β on E m × E m by ∀y, z ∈ E m β(y, z) = P Z l n = z/Y l n = y = P (Z ∞ n = z/X ∞ n = y) .
7.3. Z l n -→ X l n+1 : selection. We first describe informally the selection mechanism. Suppose Z l n = z and we wish to build the vector X l n+1 = x. We first traverse f [z]; with each element λ of this set, we associate a sequence ψ 1 , • • • , ψ n λ obtained by reordering randomly (all orders being equally probable) the set f -1 ({λ})∩f [z]. The population x is then built in the following way: for each component x k , 1 ≤ k ≤ m, we draw a value λ under a distribution probability on the set f [z] which is biased toward the high values. As l goes to infinity, this distribution concentrates on the value f (z). With this value λ, we had previously associated a sequence ψ 1 , • • • , ψ n λ . We divide the set {1 • • • m} in n λ + 1 parts. If the index k under consideration belongs to the r-th part, where 1 ≤ r ≤ n λ , we set x k = ψ r . If k belongs to the (n λ + 1)-th part, we choose x k randomly and uniformly over the set

{ ψ 1 , • • • , ψ n λ }.
We now describe precisely this mechanism. Suppose always Z l n = z. Let us recall some notations. The set

f [z] contains |f [z]| distinct values λ z 1 , • • • , λ z |f [z]|
; throughout this section, when the context is unambiguous, we will drop the superscript z in this notation, so that λ k will stand for λ z k . For each λ in f [z], there are |z λ | distinct individuals in z whose fitness is equal to λ:

z λ = { z λ 1 , • • • , z λ |z λ | }.
The vector X l n+1 = x is built in the following way. For each

h in {1 • • • |f [z]
|}, we select independently and randomly with the uniform distribution a permutation σ h belonging to S(|z

λ h |) = S(|[z] ∩ f λ h |). The law of each component x k (1 ≤ k ≤ m) of x is defined as follows: we select randomly a value λ in the set f [z] with the distribution ∀h ∈ {1 • • • |f [z]|} P (λ = λ h ) = exp(cλ h ln l) |f [z]|
r=1 exp(cλ r ln l) where c is a positive real number, which we call the scaling parameter. The value of x k is then chosen in the set z λ according to the value of the index k: Remark. The selection mechanism at work in the chain (X ∞ n ) is obtained as a particular case: the distribution probability on f [z] is degenerated and attributes mass one to f (z). We give now an explicit expression for the transition probabilities. Let x and z belong to

• if τ (|z λ |, |z λ |) ≤ k ≤ τ (|z λ | + 1, |z λ |) = m,
E m . If [x] ⊂ [z], we put σ(z, x) = ∅. Suppose [x] ⊂ [z]. Let σ(z, x) be the set of the |f [z]|-uples of permutations (σ 1 , • • • , σ |f [z]| ) ∈ S(|z λ 1 |) × • • • × S(|z λ |f [z]| |)
satisfying the following property:

for each k in {1 • • • m}, if h is the unique integer in {1 • • • |f [z]|} such that λ h = f (x k ), and if for some r in {1 • • • |z λ h |} we have τ (r -1, |z λ h |) ≤ k < τ (r, |z λ h |), then x k = z λ h σ h (r)
. The transition probabilities from Z l n to X l n+1 are then given by the intuitive formula:

P X l n+1 = x/Z l n = z = (7) |σ(z, x)| λ∈f [z] |z λ |!   λ∈f [z] m k=τ (|z λ |,|z λ |) 1 z λ (x k ) |z λ | + 1 -1 z λ (x k )   m k=1 exp(cf (x k ) ln l) λ∈f [z] exp(cλ ln l)
.

We define the kernel γ on E m × E m by the identity

P X l n+1 = x/Z l n = z = γ(z, x) m k=1 exp(cf (x k ) ln l) λ∈f [z] exp(cλ ln l)
.

Only the last product in formula [START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF] depends upon l. It may be rewritten as exp(c

m k=1 f (x k ) ln l) λ∈f [z] exp(cλ ln l) m .
As l goes to infinity, this term is equivalent to

exp -c m f (z) - m k=1 f (x k ) ln l which tends to zero whenever [x] is not included in z. Thus lim l→∞ P X l n+1 = x/Z l n = z = |σ(z, x)| λ∈f [z] |z λ |! m k=1 1 b z (x k ) | z| τ (|b z|,|b z|)-1-m . Yet, for x such that [x] ⊂ z, we have either σ(z, x) = ∅ and P X l n+1 = x/Z l n = z = 0, or |σ(z, x)| = λ∈f [z]\{ b f (z)} |z λ |!
in which case (see formula ( 5)) ( 8)

lim l→∞ P X l n+1 = x/Z l n = z = | z| | z|! τ (|b z|,|b z|)-1-m = P X ∞ n+1 = x/Z ∞ n = z
i.e. the limiting selection mechanism is the one used for the Markov chain (X ∞ n ). Formulas ( 6) and (8) yield

∀y, z ∈ E m lim l→∞ P X l n+1 = z/X l n = y = P X ∞ n+1 = z/X ∞ n = y
so that the process (X l n ) is a perturbation of the process (X ∞ n ). A crucial point is that the perturbations really interact as l goes to infinity. More precisely, the rates of convergence in ( 6) and ( 8) should be logarithmically of the same order.

Convergence of the genetic algorithm

We state now our main results. The proofs are delayed in the remaining sections of the paper. Several critical quantities appear in the statements, like the critical population size m * , the critical heights H 1 and H * e . Explicit bounds of these quantities are obtained in the proofs of the results; however these bounds involve some intricated constants associated to the abstract fitness landscape. For the sake of clarity, we state the results without introducing these constants. Let us also point out that the proofs yield also a lot of informations concerning the structure of the most probable trajectories of the process.

The first important result deals with the concentration of the equilibrium law of the algorithm on the ideal attractor K * . Theorem 8.1. (critical population size and limiting distribution) There exists a critical population size m * depending on the fitness landscape (E, f, α, β), the mutation cost a and the scaling parameter c, such that, when the population size m of the algorithm is greater than m * , the limit of the sequence of the stationary measures of the Markov chains (X l n ), l ∈ N, as l goes to infinity, is the uniform distribution over the ideal attractor K * , that is

∀m ≥ m * ∀x, y ∈ E m × K * lim l→∞ lim n→∞ P X l n = y/X l 0 = x = 1 |K * | .
We next state some key facts concerning the cycle decomposition when the population size is large. Theorem 8.2. (structure of the cycles) There exists another critical population size M * such that, when the population size m of the algorithm is greater than M * , each cycle over the set of attractors K not containing the attractor K * is reduced to one single attractor K.

In fact, for m large enough, the set of the attractors does not depend any more on m (the attractors are in one to one correspondence with particular subsets of E, see section 6). The trace of the limiting dynamics on the set of the attractors stabilizes for m large and does not depend any more on m. This could be proved using the same technique as in [7, section 7].

Remark. Once more, this limiting structure is obtained as soon as the population size m is greater than a critical value, the other parameters being fixed. This structure of cycles is the most favorable one: the bad cycles, i.e. those which slow down the convergence, are reduced to one single attractor.

In the next results, we suppose that the population size m is larger than m * . Once we know that the sequence of the stationary measures of the Markov chains (X l n ), l ∈ N, concentrates on the ideal attractor K * , the remaining problem is to build a process with the same limiting law. From now onwards, we consider the inhomogeneous algorithm. That is, the control parameter l is an increasing function of n and we deal with an inhomogeneous Markov chain (X l(n) n ) n∈N : we will suppress the superscript l in most notations. The challenging problem is to adapt the sequence (l(n)) n∈N in order to have

∀x ∈ E m lim n→∞ P (X n ∈ K * /X 0 = x) = 1.
(l(n) should not increase too fast) and simultaneously, we wish to obtain the best rate of convergence (l(n) should not increase too slowly). The answer to this now classical problem is given by Catoni and Trouvé's results [START_REF] Catoni | Large deviations for annealing[END_REF][START_REF] Catoni | Rough large deviations estimates for simulated annealing. Application to exponential schedules[END_REF][START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms[END_REF].

The critical heights H 1 and H * e . For the definition and the properties of the height of exit H e , we refer the reader to Trouvé's work [START_REF] Trouvé | Convergence optimale pour les algorithmes de recuits généralisés[END_REF][START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF][START_REF] Trouvé | Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms[END_REF]. The crucial constant for the convergence of the algorithm is the critical height H 1 defined by

H 1 = sup { H e (π) : π cycle not containing K * } .
The rate of escape from the basin of attraction of K * is

H * e = H e ( x ∈ E m : f * ⊂ [x]
). Proposition 8.3. The critical height H 1 is bounded as a function of m. The height H * e is greater than an affine function of m.

The proof is done in the appendix. We now restate in our context Trouvé's convergence result (Trouvé [27,Theorem 3.23]), which is an extension of a result by Hajek [START_REF] Hajek | Cooling schedules for optimal annealing[END_REF] for the simulated annealing. Theorem 8.4. Suppose m is larger than m * . For all increasing sequences l(n) going to infinity, we have the equivalence sup

x∈E m P (X n ∈ K * /X 0 = x) -→ n→∞ 0 ⇐⇒ ∞ n=0 l(n) -H 1 = ∞.
Furthermore, we may adapt the sequence l(n) in order to be trapped in the basin of attraction of K * after a finite number of transitions. Theorem 8.5. Suppose m is large enough to have m ≥ m * and H 1 < H * e . For all increasing sequences l(n), we have the equivalence

∀x ∈ E m P (∃N ∀n ≥ N f * ⊂ [X n ] /X 0 = x) = 1 ⇐⇒ ∞ n=0 l(n) -H 1 = ∞, ∞ n=0 l(n) -H * e < ∞.
Remark. Proposition 8.3 implies that for m large enough, we have H 1 < H * e so that sequences l(n) with the desired properties do exist.

The optimal rate of convergence. For the meaning and the properties of the optimal convergence exponent, we refer the reader to [START_REF] Catoni | Large deviations for annealing[END_REF][START_REF] Catoni | Rough large deviations estimates for simulated annealing. Application to exponential schedules[END_REF][START_REF] Catoni | Sharp large deviations estimates for simulated annealing algorithms[END_REF][START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF][START_REF] Trouvé | Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms[END_REF]. We restate now Trouvé's result for the optimal convergence rate, which generalizes Catoni's work. Theorem 8.6. There exist two strictly positive constants R 1 and R 2 such that for all m ≥ m * and all n

R 1 n α opt ≤ inf 0≤l(1)≤•••≤l(n) max x∈E m P (X n ∈ K * /X 0 = x) ≤ R 2 n α opt .
Proposition 8.7. The optimal convergence exponent α opt is bounded between two affine strictly increasing functions of m i.e. we have

0 < lim inf m→∞ α opt m ≤ lim sup m→∞ α opt m < ∞.
The proof is done in the appendix. The fact that the optimal convergence exponent α opt increases linearly with m shows that our genetic algorithm is intrinsically parallel: it involves mostly local independent computations. This nice feature will be further discussed in the next section, where we compare the parallel (independent) simulated annealing with the genetic algorithm on a very simple example.

The role of the crossover

The crossover operator is integrated into the ground process which drives the dynamics of the genetic algorithm. It is therefore essential to impose some stability conditions on it to make the convergence toward the global maxima possible for every fitness function. Our condition [START_REF] Aarts-P | Simulated annealing: theory and applications[END_REF],

∀i ∈ E β((i, i), (i, i)) = 1,
is the simplest form of such a requirement.

Proposition 9.1. Suppose there exist i and e such that i = e and β((i, i), (e, e)) > 0 , ∀j ∈ E \ {i} β((j, j), (j, j)) = 1 .

Then there exists a fitness function f such that, whatever the population size m ≥ 2, the mutation cost a and the scaling factor c,

∀x ∈ E m lim l→∞ lim n→∞ P [X l n ] ⊂ f * /X l 0 = x = 0 .
The proof is done in the appendix. Instead of imposing a general condition like (1), one could impose a condition depending on a particular fitness function f . For instance, convergence can be ensured if

∀i ∈ f * β((i, i), (i, i)) = 1
or even if β(f * ) = f * (the notation β(f * ) is explained before lemma 6.2). The condition (2), ∀i, j ∈ E β((i, j), (i, j)) > 0, is not as crucial as the first one. However it makes the analysis of the set of attractors somewhat simpler. Without it, one should impose a further restriction in the of attractors (definition 6.1) so that

∀x ∈ K P (X ∞ n+1 ∈ K/X ∞ n = x) > 0 ,
otherwise the process might escape instantaneously from K with probability one. An example of such a condition is

iii) ∀x ∈ K ∀i, j ∈ [x]
β((i, j), (i, j)) > 0.

The condition (3),

∀i 1 , j 1 , i 2 , j 2 ∈ E β((i 1 , j 1 ), (i 2 , j 2 )) = β((j 1 , i 1 ), (j 2 , i 2 )),
is superfluous and can be removed without affecting the analysis. However, it is a natural condition of symmetry. An important issue is to understand the impact of the crossover on the speed of convergence of the algorithm. A natural direction for future research is to find how one should implement efficiently the crossover operator in order to increase significantly the optimal convergence exponent for a specific class of fitness functions. Let us see what happens on a small numerical example.

We consider the space E = {0, 1} 4 endowed with the mutation and crossover kernels (α, β) defined in section 4. We define the fitness function f by f ({0000}) = {1000}, f ({1000, 0100, 0010, 0001}) = {900}, f ({1100, 1010, 1001, 0110, 0101, 0011}) = {800}, f ({1110, 1101, 1011, 0111}) = {0}, f ({1111}) = {1100} so that f is a function of the number of digits of the individual equal to one. Let β 0 be the identity crossover kernel, that is

∀i 1 , j 1 , i 2 , j 2 ∈ E β 0 ((i 1 , j 1 ), (i 2 , j 2 )) = 1 2 δ(i 1 , i 2 )δ(j 1 , j 2 ) + 1 2 δ(i 1 , j 2 )δ(j 1 , i 2 ). 20
The algorithm with β 0 corresponds to a genetic algorithm without crossover, that is a mutation-selection algorithm. Let us denote by H 1 (β 0 ), α opt (β 0 ) the critical height and the optimal exponent associated to the algorithm running with the crossover β 0 .

To compute H 1 we look at the trajectories of minimal cost which start from the attractor K(0000) and end into the attractor K(1111). With β 0 (i.e. no crossover) and a sufficiently large population size, the best way is to let an individual follow a mutation path like 0000 → 0100 → 0101 → 1101 → 1111 while all other individuals remain in 0000. Whenever this explorer reaches 1111, the whole population jumps on 1111. This trajectory requires four mutations and an antiselection cost of c(3f (0000) -f (0100) -f (0101) -f (1101)), so that its global cost is H 1 (β 0 ) = 4a + 1300c. When a crossover mechanism is available, it is possible to build more efficient paths which avoid the difficult saddles. In our example, a good way to avoid the anti-selection of an individual containing three digits equal to one (like 1101) is to let two individuals mutate from 0000 to 1100 and 0011 simultaneously and then to perform a crossover between them:

(0000, 0000) → (1000, 0010) → (1100, 0011) → (1111, 0000). This requires four mutations, an anti-selection cost of c(2f (0000) -f (1000) -f (0010)) so that the global cost is H 1 (β) = 4a + 200c, which is much less than H 1 (β 0 ).

We finally examine the rate of increase of the optimal convergence exponent when the population size is sufficiently large. We obtain analogously

lim m→∞ α opt (β) m = min(a, 100c) 4a + 200c > lim m→∞ α opt (β 0 ) m = min(a, 100c) 4a + 1300c .
Consider now m independent simulated annealing algorithms running over this fitness landscape (the moves of the particle are determined by the mutation kernel α and the simulated annealing does not make use of the crossover mechanism). We keep track of the best point found by the m algorithms. The optimal convergence exponent of this process is m/10. Trouvé proves that in general the optimal convergence exponent for parallel annealing based on periodically interacting searches is always worse than for independent multiple searches [START_REF] Trouvé | Asymptotical behaviour of several interacting annealing processes[END_REF]. Introducing an interaction between simulated annealing algorithms may therefore damage the speed of convergence. We see that, for large populations, the optimal exponent of m independent simulated annealing is always better than the optimal exponent α opt (β 0 ) of the genetic algorithm without crossover. However, the situation changes radically whenever a crossover mechanism is available. Indeed, if we choose for instance a = 100c, we obtain α opt (β) ∼ m/6 which outperforms the m independent simulated annealing algorithms. An appropriate cooperation mechanism can therefore enhance significantly the speed of convergence.

10. Asymptotic expansion of P X l n+1 = v/X l n = u The aim of this section is to show how our model fits into the framework of the generalized simulated annealing. What we have to do is to study the asymptotic behaviour of the transition matrix of (X l n ) as l goes to infinity. By the very construction of the process (X l n ), we have

P X l n+1 = v/X l n = u = y,z∈E m P X l n+1 = v/Z l n = z P Z l n = z/Y l n = y P Y l n = y/X l n = u .
For each y, z in E m ,

P X l n+1 = v/Z l n = z P Z l n = z/Y l n = y P Y l n = y/X l n = u ∼ l→∞ (9) α(u, y) β(y, z) γ(z, v) exp -ad(u, y) + c m k=1 ( f (z) -f (v k )) ln l
where we note for u, y in

E m α(u, y) = k:u k =y k α(u k , y k )
and d(u, y) is the Hamming distance between the vectors u and y, i.e.

d(u, y) = card { k : 1 ≤ k ≤ m, u k = y k }.
The above quantity ( 9) vanishes whenever α(u, y) β(y, z) γ(z, v) = 0. Let D 1 (u, v) be the set of all four-uples (u, y, z, v) satisfying α(u, y) β(y, z) γ(z, v) > 0.

We define next the communication cost

V 1 on E m × E m by V 1 (u, v) = min (u,y,z,v)∈D 1 (u,v) ad(u, y) + c m k=1 ( f (z) -f (v k )).
and we note D * 1 (u, v) the elements of D 1 (u, v) which realize the above minimum. Putting

q 1 (u, v) = (u,y,z,v)∈D * 1 (u,v)
α(u, y) β(y, z) γ(z, v),

we have P X l n+1 = v/X l n = u ∼ l→∞ q 1 (u, v) exp (-V 1 (u, v) ln l) .
Moreover, notice that for each u, v in E m ,

P X l n+1 = v/X l n = u = 0 ⇐⇒ V 1 (u, v) = ∞ ⇐⇒ q 1 (u, v) = 0.
We are now in the framework of the generalized simulated annealing studied by Trouvé [START_REF] Trouvé | Convergence optimale pour les algorithmes de recuits généralisés[END_REF][START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF][START_REF] Trouvé | Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms[END_REF]. That is, the transition probabilities of the process (X l n ) form a family of Markov kernels on the space E m indexed by l which is admissible for the communication kernel q 1 and the cost function V 1 [27, Definition 3.1].

The paths and their costs

If S is an arbitrary set, S (N) denotes the set of paths in S, that is the set of finite sequences of elements of S. A path s in S is noted indifferently

s = (s 1 , • • • , s r ), s = (s 1 , • • • , s r ) or s = s 1 → • • • → s r
and its length is noted |s| (r in the above example). A path s in S is said to join two elements t 1 and t 2 if s 1 = t 1 and s |s| = t 2 ; the set of all paths in S joining the points t 1 and t 2 is noted S (N) (t 1 , t 2 ). We will consider paths in the sets E, E m and P(E). Paths of E m will mostly be denoted by the letter p and paths of P(E) by the letter q. By D m we denote the paths in E m which correspond to possible trajectories of the process (X l n ), i.e. the paths

p in E m satisfying ∀k 1 ≤ k < |p| V 1 (p k , p k+1 ) < ∞. The V 1 -cost of such a path is V 1 (p) = |p|-1 k=1 V 1 (p k , p k+1 ).
Notice that for the empty path (which has a null length), the cost is zero.

If p belongs to E m(N) \ D m , we put V 1 (p) = ∞.
Similarly, by D m we denote the paths in E m which correspond to possible trajectories for the whole process (the number of transitions r being variable)

X l n → Y l n → Z l n → X l n+1 → Y l n+1 → • • • → Z l n+r-1 → X l n+r
i.e. such a path p includes the intermediate populations Y l n+k and Z l n+k , 1 ≤ k < r, has a length equal to 1 modulo 3 and satisfies

∀k 1 ≤ 3k < |p| α(p 3k-2 , p 3k-1 ) β(p 3k-1 , p 3k ) γ(p 3k , p 3k+1 ) > 0.
The corresponding cost function V is defined by

V (p) = 1≤3k<|p| a d(p 3k-2 , p 3k-1 ) + c m h=1 f (p 3k ) -f (p 3k+1 h )
if the path p belongs to D m (here p 3k+1 h is the h-th component of the vector p 3k+1 ) and

V (p) = ∞ otherwise. We put also for y, z in E m D m (y, z) = D m ∩ E m(N) (y, z) , D = m∈N * D m ,
and we define similarly D m (y, z), D (just replace D by D in the above formulas).

The bracket operator [ ] provides a natural projection from the set

∪ m∈N * E m(N) onto P(E) (N) : with each path p = (p 1 , • • • , p r ) in E m we associate the path [p] = ([p 1 ], • • • , [p r ]) in P(E). Finally, we put [D] = { [p] : p ∈ D }.
12. The minimal communication cost and the virtual energy Definition 12.1. We define the minimal communication cost V for y and z in E m by

V (y, z) = inf { V 1 (p) : p ∈ D m (y, z) }.
Notice that for all x in E m , we have V (x, x) = 0. If F, G are two subsets of E m , we define

V (F, G) = inf { V 1 (p) : p ∈ D m , p 1 ∈ F, p |p| ∈ G } = inf {V (y, z) : y ∈ F, z ∈ G }.
Let g be a graph on E m . The cost of g is

V (g) = (x→y)∈g V (x, y).
This definition works also for a path p in E m if we consider the path as a graph over E m . Notice that for the empty graph (which has no arrows), the cost is zero. We recall that an x-graph is a graph with no arrow starting from x and such that for any y = x there exists a unique path in g leading from y to x. The set of all x-graphs is denoted by G(x). For more details and notations concerning graphs, see [10, chapter 6].

Definition 12.2. The virtual energy W associated with the cost function V is defined by

∀x ∈ E m W (x) = min { V (g) : g ∈ G(x) }.
We put also for any subset

F of E m W (F ) = min { W (x) : x ∈ F }, W * = { x ∈ E m : W (x) = W (E m ) }.
Proposition 5.4 of [START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF] shows that this quantity could equivalently be defined through the cost function V 1 instead of V . The point is that the sequence of the stationary measures of the Markov chains (X l n ), l ∈ N, concentrates on the set W * as l goes to infinity. Proposition 12.3. (Freidlin and Wentzell)

∀x ∈ E m lim l→∞ lim n→∞ P X l n ∈ W * /X l 0 = x = 1.
We face here the same difficulty as in the case of the mutation-selection algorithm: the size of the state space increases geometrically with the population size m. Anyway, we are mostly interested in the way the chain (X l n ) visits the populations of the attractors K. We use the same technique as in [START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF]. Since ∀x ∈ E m ∃K ∈ K V (x, K) = 0, then theorems 5.8 and 7.3 of [START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF] show that the dynamics of the process may be studied by considering only the restrictions of the communication cost V and the virtual energy W to the set of the populations belonging to the attractors. Furthermore, we have

∀K ∈ K ∀x, y ∈ K V (x, y) = 0 so that ∀K 1 , K 2 ∈ K ∀x 1 ∈ K 1 ∀x 2 ∈ K 2 V (x 1 , x 2 ) = V (K 1 , K 2 )
and similarly

∀K ∈ K ∀x ∈ K W (x) = W (K).
The functionals W and V may thus be seen as defined on the set of attractors K rather than on the set of populations belonging to attractors.

For the sake of completeness, we recall also the definition of the communication altitude, as well as the construction of the hierarchy of cycles. These tools will only be used for theorem 8.2. For the details, we refer the reader to [START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF][START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF] as well as to [8, section 4] where they are used to compute spectral estimates.

(K 1 , K 2 ) between two distinct attractors K 1 and K 2 is A(K 1 , K 2 ) = inf { max 1≤k<|p| W (p k ) + V (p k , p k+1 ) : p ∈ D m , p 1 ∈ K 1 , p |p| ∈ K 2 }. For any K in K, we put A(K, K) = W (K).
Definition 12.5. Let λ ∈ R. We define an equivalence relation R λ on the set The set of cycles in K associated with the cost function V is

W λ = { K ∈ K : W (K) ≤ λ } by ∀K 1 , K 2 ∈ W λ , K 1 R λ K 2 ⇐⇒ A(K 1 , K 2 ) ≤ λ.
C(K) = λ∈R + W λ R λ
where W λ R λ is the quotient set of the equivalence classes of W λ for the relation R λ .

We will now study the costs of the transitions between the attractors. As it turns out, the costs of the bad transitions increase linearly with the population size m, whereas the costs of the good transitions remain bounded (as functions of m).

The costs of the bad transitions

We distinguish two kinds of bad transitions: those which lose some peak fitness individuals and those which decrease the fitness.

Lemma 13.1. (loss of diversity in f * ) Let K 1 , K 2 be two elements of K such that [K 1 ] ⊂ f * , [K 2 ] ⊂ f * (i.e. K 1 , K 2 ∈ K * ).
We have

V (K 1 , K 2 ) ≥ m 2(|f * | + 1) min (a, cδ * ) card ([K 1 ] \ [K 2 ])
where

δ * = min{ f (f * ) -f (i) : i ∈ f * }. Proof. Let K 1 , K 2 be two attractors of K * . Put [K 1 ] \ [K 2 ] = { e 1 , • •
• , e r } and let p be a path joining the attractors K 1 and K 2 , i.e.

p 1 ∈ K 1 , p |p| ∈ K 2 . We define for ι in {1 • • • r}, t(ι) = min { k : 0 ≤ k < |p|, k ≡ 0 (mod 3), e ι ∈ [p k+1 ] ∩ [p k+2 ] ∩ [p k+3 ] } i.e. t(ι)
is the last time equal to 0 modulo 3 before the disappearance of e ι in the path p.

We make the conventions p 0 = p 1 and p |p|+1 = p |p|+2 = p |p| . The transition mechanism implies the following fact:

for each ι in {1 • • • r}, there exists h ι in {1 • • • | p t(ι) |} such that ∀h τ (h ι -1, | p t(ι) |) ≤ h < τ (h ι , | p t(ι) |) p t(ι)+1 h ∈ f * =⇒ p t(ι)+1 h = e ι .
Therefore, the r sets indexed by

ι in {1 • • • r} { t(ι), t(ι) + 1, t(ι) + 2 } × { h : τ (h ι -1, | p t(ι) |) ≤ h < τ (h ι , | p t(ι) |) }
have pairwise empty intersections, and it follows that

V (p) ≥ r ι=1 τ (h ι ,|b p t(ι) |)-1 h=τ (h ι -1,|b p t(ι) |) c f (p t(ι) ) -f (p t(ι)+1 h ) + a 1 -δ(p t(ι)+1) h , p t(ι)+2 h
) .

Let ι belong to {1 • • • r} and suppose

c f (p t(ι) ) -f (p t(ι)+1 h ) + a 1 -δ(p t(ι)+1) h , p t(ι)+2 h ) = 0 for some h satisfying τ (h ι -1, | p t(ι) |) ≤ h < τ (h ι , | p t(ι) |). This implies p t(ι)+1 h = p t(ι)+2 h = e ι . Suppose that 1 + 1 2 τ (h ι , | p t(ι) |) -τ (h ι -1, | p t(ι) |) = m 2(| p t(ι) | + 1) + 1
such terms vanish. Necessarily, there exists an odd index h such that

τ (h ι -1, | p t(ι) |) ≤ h < τ (h ι , | p t(ι) |) and p t(ι)+1 h = p t(ι)+2 h = p t(ι)+1 h+1 = p t(ι)+2 h+1 = e ι .
The crossover operator does not affect the pair (p

t(ι)+2 h , p t(ι)+2
h+1 ) (by condition ( 1)) and we have also p t(ι)+3 h = p t(ι)+3 h+1 = e ι . Thus the individual e ι is present in the populations p t(ι)+1 , p t(ι)+2 , p t(ι)+3 , which contradicts the definition of t(ι). We have proved that less than m/(2(| p t(ι) | + 1)) terms vanish in each sum (1 ≤ ι ≤ r)

τ (h ι ,|b p t(ι) |)-1 h=τ (h ι -1,|b p t(ι) |) c f (p t(ι) ) -f (p t(ι)+1 h ) + a 1 -δ(p t(ι)+1) h , p t(ι)+2 h
) .

Moreover, we know that f (p t(ι) ) = f (f * ) (since e ι ∈ [p t(ι) ]), and each non-zero term is necessarily greater than min (a, cδ * ), so that the above sum is greater than

τ (h ι -1, | p t(ι) |) -τ (h ι , | p t(ι) |) - m 2(| p t(ι) | + 1) min (a, cδ * ) = m 2(| p t(ι) | + 1) min (a, cδ * ). Yet p t(ι) ⊂ f * so that | p t(ι) | ≤ |f * |. Finally we obtain V (p) ≥ m 2(|f * | + 1) min (a, cδ * ) r (where r = card ([K 1 ] \ [K 2 ]
)) and taking the infimum over all paths p joining the attractors K 1 and K 2 yields the desired inequality.

To obtain a lower bound for the communication cost between two attractors, we will study the possible trajectories of a pair of contiguous individuals within a given path of populations joining the two attractors. Definition 13.2. (admissible paths) Let q be a path in P(E). We say that the pair (i k , j k ), 1 ≤ k ≤ |q|, of paths in E is admissible for

q if i) ∀k ∈ {1 • • • |q|} i k ∈ q k , j k ∈ q k ii) ∀k 1 ≤ 3k < |q| • either i 3k-2 = i 3k-1 or α(i 3k-2 , i 3k-1 ) > 0
• either j 3k-2 = j 3k-1 or α(j 3k-2 , j 3k-1 ) > 0

• β((i 3k-1 , j 3k-1 ), (i 3k , j 3k )) > 0

• f (i 3k+1 ) = f (j 3k+1 ) =⇒ i 3k+1 = j 3k+1 .
The set of all pair of paths admissible for the path q is denoted by A(q).

We define the quantity ρ(K 1 , K 2 ) for K 1 and K 2 in K to be the infimum

inf 1≤3k<|q| a 2 -δ(i 3k-2 , i 3k-1 -δ(j 3k-2 , j 3k-1 )) + c 2 f (q 3k ) -f (i 3k+1 ) -f (j 3k+1 ) where q ∈ [D], q 1 = [K 1 ], q |q| = [K 2 ], (i k , j k ) 1≤k≤|q| ∈ A(q), i 1 = j 1 .
We put

ρ = min ρ(K 1 , K 2 ) : K 1 , K 2 ∈ K, ρ(K 1 , K 2 ) > 0 .
Since the quantities ρ(K 1 , K 2 ) are finite sums involving terms of the form a or c f (i)-f (j) (where f (i) ≥ f (j)), we have ρ ≥ min (a, cδ) > 0.

Lemma 13.3. Let K 1 and K 2 belong to K. Suppose ρ(K 1 , K 2 ) = 0.

Then there exists a path q in the set [D] such that

q 1 = [K 1 ], q |q| = [K 2 ] and f (q 1 ) ≤ f (q 4 ) ≤ • • • ≤ f (q |q|-3 ) ≤ f (q |q| ),
i.e. the sequence f (q 3k+1 ) , 1 ≤ 3k + 1 ≤ |q|, is non-decreasing.

In particular, we have f (K 1 ) ≤ f (K 2 ).

Corollary 13.4. Let K 1 and K 2 be two attractors such that f (K 1 ) > f (K 2 ).

Then ρ(K 1 , K 2 ) ≥ ρ ≥ min (a, cδ) > 0.

Proof. Let K 1 and K 2 be as in the hypothesis of lemma 13.3. By definition of ρ(K 1 , K 2 ), there exists a path q in [D] and a pair (i k , j k ), 1 ≤ k ≤ |q|, of paths in E admissible for q such that q

1 = [K 1 ], q |q| = [K 2 ], i 1 = j 1 and 1≤3k<|q| a 2 -δ(i 3k-2 , i 3k-1 -δ(j 3k-2 , j 3k-1 )) + c 2 f (q 3k ) -f (i 3k+1 ) -f (j 3k+1 ) = 0.
This relation implies that, for each k, 1 ≤ 3k < |q|, we have

(10) i 3k-2 = i 3k-1 , j 3k-2 = j 3k-1 , f (i 3k+1 ) = f (j 3k+1 ) = f (q 3k ).
Since the pair of paths (i k , j k ) is admissible for the path q, the last of the above equalities implies that i 3k+1 = j 3k+1 for each k, 1 ≤ 3k < |q|. Notice also that i 1 = j 1 .

Moreover the crossover has no effect when two identical individual mates (condition (1)), so that

∀k 1 ≤ 3k < |q| i 3k = j 3k = i 3k-1 = j 3k-1 . (11)
Therefore, we conclude from [START_REF] Freidlin-A | Random perturbations of dynamical systems[END_REF] and [START_REF] Geman-D. Geman | Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images[END_REF] that

∀k 1 ≤ 3k < |q| f (q 3k+1 ) = f (q 3k ) ≥ f (q 3k-2 )
and the sequence f (q 3k+1 ) , 1 ≤ 3k + 1 ≤ |q|, is non-decreasing.

Lemma 13.5. (lower bound for the communication cost) Let K 1 and K 2 belong to K. We have the inequality

V (K 1 , K 2 ) ≥ m 4 - Λ + 3 2 ρ(K 1 , K 2 ).
(We recall that Λ = max { |f λ | : λ ∈ R * + }.) Proof. Let p be a path in D joining the attractors K 1 and K 2 (i.e. p 1 ∈ K 1 , p |p| ∈ K 2 ). We make the convention p 0 = p 1 . Putting

τ k = 1 2 τ (| p 3k-3 |, | p 3k-3 |) -1 = | p 3k-3 | m 2(| p 3k-3 | + 1) , 1 ≤ 3k < |p|,
we have

V (p) = 1≤3k<|p| m h=1 a 1 -δ(p 3k-2 h , p 3k-1 h ) + c f (p 3k ) -f (p 3k+1 h ) ≥ 1≤3k<|p| τ k -1 h=0 a 2 -δ(p 3k-2 2h+1 , p 3k-1 2h+1 -δ(p 3k-2 2h+2 , p 3k-2 2h+2 )) (12) + c 2 f (p 3k ) -f (p 3k+1 2h+1 ) -f (p 3k+1 2h+2 ) .
Let h belong to {1 • • • Λ}. Let m = 2(h + 1)q + r be the euclidean division of m by 2(h + 1); we have (since h ≥ 1 and 0 ≤ r < 2(h + 1))

2h m 2(h + 1) = 2hq = 2h m -r 2(h + 1) = h h + 1 (m -r) > 1 2 m -2(h + 1) ≥ m 2 -Λ -1.
For each k, 1 ≤ 3k < |p|, the very definition of Λ implies 1 ≤ | p 3k-3 | ≤ Λ whence

τ (| p 3k-3 |, | p 3k-3 |) > m 2 -Λ.
It follows from ( 12) that (the • • • stands for the summand in the last sum of ( 12))

V (p) ≥ 1≤3k<|p| 0≤h<τ k • • • • • • = 1≤3k<|p| 1≤2h+1<τ (|b p 3k-3 |,|b p 3k-3 |) • • • • • • ≥ 1≤3k<|p| 1≤2h+1<m/2-Λ • • • • • • = 1≤2h+1<m/2-Λ 1≤3k<|p| • • • • • •
Yet, for each h such that 1 ≤ 2h+1 < m/2-Λ, the pair of paths (p k 2h+1 , p k 2h+2 ), 1 ≤ k ≤ |p|, is admissible for [p] and satisfy also p 1 2h+1 = p 1 2h+2 : as a consequence, the sum

1≤3k<|p| a 2 -δ(p 3k-2 2h+1 , p 3k-1 2h+1 -δ(p 3k-2 2h+2 , p 3k-2 2h+2 )) + c 2 f (p 3k ) -f (p 3k+1 2h+1 ) -f (p 3k+1 2h+2 )
is greater than ρ(K 1 , K 2 ) and finally V (p) ≥ (m/4 -(Λ + 3)/2) ρ(K 1 , K 2 ). Taking the infimum over all the paths joining K 1 and K 2 gives the inequality of the lemma.

In the same flavor as the two preceding lemmas, we have the Proposition 13.6. Let K 1 , K 2 be two elements of K such that f (K 1 ) = f (K 2 ). Then

V (K 1 , K 2 ) ≥ min (a, cδ) min m 2(Λ + 1) card [K 1 ] \ [K 2 ] , m 4 - Λ + 3 2 .
Proof. Let p be a path in E m joining the attractors K 1 and K 2 . We consider two cases.

• Suppose the sequence ( f (p 3k+1 )), 1 ≤ 3k + 1 ≤ |p|, is not non-decreasing: there exists an index h, 1 < 3h + 1 ≤ |p|, such that f (K 1 ) > f (p 3h+1 ) and an attractor K 3 satisfying

V (p 3h+1 , K 3 ) = 0, f (K 3 ) = f (p 3h+1 ).
Clearly V (p) ≥ V (K 1 , K 3 ) and corollary 13.4 and lemma 13.5 imply

V (K 1 , K 3 ) ≥ min (a, cδ) m 4 - Λ + 3 2 .
• Suppose the sequence ( f (p 3k+1 )), 1 ≤ 3k + 1 ≤ |p|, is non-decreasing. Then we have

∀k 1 ≤ 3k + 1 ≤ |p| f (p 3k+1 ) = f (K 1 ) = f (K 2 ) = θ.
We modify (just for the purpose of the proof!) the function f in the following way: for each i in E, if f (i) is strictly greater than θ, we set f (i) = θ -δ. The attractors K 1 and K 2 then become elements of K * and we are in a situation analogous to lemma 13.1. Moreover the cost of the path p, i.e. the quantity

V (p) = 1≤3k<|p| a d(p 3k-2 , p 3k-1 ) + c m h=1 f (p 3k ) -f (p 3k+1 h )
decreases when evaluated with the new function f . Actually, for any indices h and k such that 1 ≤ 3k < |p|, 1 ≤ h ≤ m, the value f (p 3k+1 h ) remains unchanged (since it was lower or equal than θ) and the value f (p 3k ), which was greater or equal than θ, becomes equal to θ (since f (p 3k+1 ) = θ and [p 3k+1 ] ⊂ [p 3k ], the set [p 3k ] necessarily intersects the set f θ ). Application of lemma 13.1 yields

V (p) ≥ m 2(|f θ | + 1) min (a, cδ θ ) card ([K 1 ] \ [K 2 ])
where

δ θ = min{ θ -f (i) : i ∈ E, f (i) < θ }.
In both cases, the inequality of the lemma is satisfied.

The costs of the good transitions

We distinguish also two kinds of good transitions: those which create some new peak fitness individuals and those which increase the fitness. We note by R the minimal number of transitions necessary to join two arbitrary points of E through the kernel α, i.e. R is the smallest integer satisfying

∀i, j ∈ E ∃ r ≤ R ∃e 1 , • • • , e r+1 ∈ E such that e 1 = i, e r+1 = j, ∀k ∈ {1, • • • , r} α(e k , e k+1 ) > 0. Lemma 14.1. (increasing of diversity in f * ) Let V * = max i,j∈f * min ar + c r+1 k=1 f (f * ) -f (e k ) : e 1 = i, e r+1 = j, r k=1
α(e k , e k+1 ) > 0 .

We have

V * ≤ aR + c(R -1)∆ ≤ (a + c∆)|E| < ∞ and sup m∈N * max K 1 ∈K * , K 1 =K * min K 2 ∈K * , [K 1 ] [K 2 ] V (K 1 , K 2 ) ≤ V * .
(We recall that K * is the unique attractor such that

[K * ] = f * .) Proof. The inequalities V * ≤ aR + c(R -1)∆ ≤ (a + c∆)|E| < ∞ are straightforward. Let K 1 belong to K * \ {K * }. There exists a point i in [K 1 ], a point j in f * \ [K 1 ] and a path e 1 → • • • → e r+1 in E joining i and j such that ∀k ∈ {1 • • • r} α(e k , e k+1 ) > 0, ∀k ∈ {2 • • • r} e k ∈ f * , ar + c r+1 k=1 f (i) -f (e k ) ≤ V * .
Let p be a path in E m defined by the extremal conditions

p 1 ∈ K 1 with p 1 m = i and p r+1 ∈ K 2 where K 2 ∈ K * , [K 2 ] = [K 1 ] ∪ {j} (there exists a unique attractor K 2 satisfying [K 2 ] = [K 1 ] ∪ {j}) and having for intermediate populations ∀k ∈ {2 • • • r} ∀h ∈ {1 • • • m -1} p k h = p 1 h , p k m = e k .
In this path, the first m -1 components remain fixed and the last component follows the path e

1 → • • • → e r+1 . Clearly [K 1 ] [K 2 ] and V (K 1 , K 2 ) ≤ V (p) ≤ V * . Lemma 14.2. (increasing of fitness) Let V + = max i∈E\f * min ar + c r k=1 f (i) -f (e k ) : e 1 = i, f (e r+1 ) > f (i), r k=1
α(e k , e k+1 ) > 0 .

We have

V + ≤ aR + c(R -1)∆ ≤ (a + c∆)|E| < ∞ and (13) sup m∈N * max K 1 ∈K\K * min K 2 ∈K, f (K 2 )>f (K 1 ) V (K 1 , K 2 ) ≤ V + .
Proof. The proof is similar to the proof of the preceding lemma. Let K 1 belong to K \ K * and let i belong to [K 1 ]. By definition of V + , there exists a path e

1 → • • • → e r+1 in E such that e 1 = i, f (e r+1 ) > f (i) and ∀k ∈ {1 • • • r} α(e k , e k+1 ) > 0, f (e k ) ≤ f (i), ar + c r k=1 f (i) -f (e k ) ≤ V + .
There exists a subdivision

k 1 = 1 < k 2 < • • • < k s-1 < k s = r + 1 of {1 • • • r + 1} such that f (e k 1 ) = f (e k 2 ) = • • • = f (e k s-1 ) = f (i) and ∀k ∈ {1 • • • r + 1} \ { k 1 , • • • , k s } f (e k ) < f (i).
For each ι, 1 < ι < s, let K ι be the unique attractor such that [

K ι ] = [K 1 ]∪{ e k 2 , • • • , e k ι }.
Let K s be the attractor { (e r+1 , • • • , e r+1 ) } (i.e. K s contains only the population whose all components are equal to e r+1 ). Clearly, the attractor

K s satisfies f (K s ) > f (K 1 ). Let p be a path in E m such that, for each ι in {1 • • • s}, p k ι belongs to K ι and ∀ι ∈ {1 • • • s -1} ∀k ∈ { k ι + 1, • • • , k ι+1 -1 } p k m = e k , ∀h ∈ {1 • • • m -1} p k h = p k ι h
(during the transition from K ι to K ι+1 , the first m-1 components remain fixed and the last component follows the mutation path e k ι → • • • → e k ι+1 ). The path p belongs to D m , joins the attractors K 1 and K s , and its cost is less than

V + . It follows that V (K 1 , K s ) ≤ V + .
is satisfied, then the minimum of the virtual energy corresponds to the ideal attractor K * , i.e. W * = {K * }, and therefore

∀x ∈ E m lim l→∞ lim n→∞ P [X l n ] = f * /X l 0 = x = 1.
Proof. Let g be a graph over K. We decompose the sum V (g) in the following way:

V (g) = λ∈f (E) K 1 ∈K λ (K 1 →K 2 )∈g V (K 1 , K 2 ) = λ∈f (E) (K 1 →K 2 )∈g |λ V (K 1 , K 2 ) i.e. V (g) = λ∈f (E) V (g |λ ).
Suppose now that g is in G(K) for some

K in K. Put θ = f (K). Then g |λ belongs to G K λ (K - λ ∪ K + λ ) whenever λ = θ whence (15) V (g |λ ) ≥ W K λ (K - λ ∪ K + λ ).
We consider two cases, depending upon the value of θ.

• θ = f (f * ). In this case, g |θ belongs to G K * ({K} ∪ K - * ) so that (16) V (g |θ ) ≥ W K * ({K} ∪ K - * ).
Summing up inequalities ( 15) and ( 16) yields

V (g) ≥ λ∈f (E\f * ) W K λ (K - λ ∪ K + λ ) + W K * ({K} ∪ K - * ).
Taking the minimum over all g in G(K), we have

W (K) ≥ λ∈f (E\f * ) W K λ (K - λ ∪ K + λ ) + W K * ({K} ∪ K - * )
and taking again the minimum over all K in K * \ {K * }, we obtain [START_REF] Holley-S. Kusuoka-D | Asymptotics of the spectral gap with applications to the theory of simulated annealing[END_REF] min

K∈K * \{K * } W (K) ≥ λ∈f (E\f * ) W K λ (K - λ ∪ K + λ ) + min K∈K * \{K * } W K * ({K} ∪ K - * ). • θ = f (f * ). Let K be any element of K - θ ∪ K + θ ; then g |θ ∪ {(K → K )} is a graph belonging to G K θ (K - θ ∪ K + θ ) whence V (g |θ ) ≥ W K θ (K - θ ∪ K + θ ) -V (K, K )
and this inequality being valid for all K outside K θ , we have

(18) V (g |θ ) ≥ W K θ (K - θ ∪ K + θ ) - min K , f (K ) =f (K) V (K, K ).
Summing up inequalities ( 15) and ( 18) yields

V (g) ≥ λ∈f (E) W K λ (K - λ ∪ K + λ ) - min K , f (K ) =f (K) V (K, K ).
Taking the minimum over all g in G(K), we obtain

W (K) ≥ λ∈f (E) W K λ (K - λ ∪ K + λ ) - min K , f (K ) =f (K) V (K, K )
and taking again the minimum over all K in K \ K * = K - * , we have [START_REF] Hwang-S | Singular perturbed Markov chains and exact behaviours of simulated annealing process[END_REF] min

K∈K - * W (K) ≥ λ∈f (E) W K λ (K - λ ∪ K + λ ) -max K∈K - * min K , f (K ) =f (K) V (K, K ).
Combining together inequalities ( 17) and ( 19), we see that V (K, K ) .

min K =K * W (K) ≥ λ∈f (E\f * ) W K λ (K - λ ∪ K + λ ) + (20)
We build now a graph g of G(K * ) which describes the most desirable dynamics of our algorithm. For each λ in f (E \ f * ), we select a graph g λ in the set G * K λ (K + λ ). Let g f (f * ) be a graph of G * K * (K * ). We define the graph g as the union of the graphs (g λ ) λ∈f (E) :

(K 1 → K 2 ) ∈ g ⇐⇒ ∃ λ ∈ f (E) (K 1 → K 2 ) ∈ g λ .
Clearly g belongs to G(K * ). Furthermore, we have by construction

V (g) = λ∈f (E) V (g |λ ) = λ∈f (E\f * ) W K λ (K + λ ) + W K * (K * ).
It follows that ( 21)

W (K * ) ≤ λ∈f (E\f * ) W K λ (K + λ ) + W K * (K * ).
Putting together inequalities [START_REF] Jerrum | Large cliques elude the Metropolis process[END_REF] and ( 21) and the hypothesis ( 14) of the theorem, we see finally that W * = {K * }.

Of course, inequality ( 14) is strongly linked with the optimization problem: the quantities involved there are built with the fitness function f , the mutation kernel α, the crossover kernel β, the population size m and the parameters a, c. However, this inequality is of little practical interest: we will now derive stronger and simpler conditions to ensure W * = {K * }.

Corollary 15.3. Suppose that

(22) W K λ (K + λ ) ≤ W K λ (K - λ ∪ K + λ ) for all λ in f (E \ f * ) , (23)
W K * (K * ) < W K * (K - * ) -max K∈K - * min K , f (K ) =f (K) V (K, K ) , (24)
W K * (K * ) < min

K∈K * \{K * } W K * ({K} ∪ K - * )) .
Then W * = {K * }.

Proof. Clearly, inequalities ( 22), ( 23), [START_REF] Sorkin | Efficient simulated annealing on fractal energy landscapes[END_REF] imply inequality [START_REF] Hajek-G | Simulated annealing -to cool or not[END_REF].

We will show that these inequalities hold when the population size m is sufficiently large. First, the left-hand side member of ( 23) and ( 24) is bounded. Proof. We build a graph g belonging to G K * (K * ) whose cost is less or equal than |K * | V * . For each K in K * \ {K * }, there exists by lemma 14.1 an attractor K belonging to K * such that [K]

[K ] and V (K, K ) ≤ V * . We consider successively each attractor K of K * \ {K * } and we add such an arrow (K → K ) to the graph: the resulting graph g belongs to G K * (K * ) and its cost is less than (|K * | -1) V * . Theorem 15.5. Let m be an integer such that We recall that Λ = max { |f λ | : λ ∈ R * + }, δ * = min{ f (f * ) -f (i) : i ∈ f * }, ρ is introduced after definition 13.2, V * in lemma 14.1 and V + in lemma 14.2. Moreover, we have the crude estimates max(V * , V + ) ≤ aR + c(R -1)∆ and ρ ≥ min(a, cδ).

(26) ρ m 4 - Λ + 3 2 > max K 1 ∈K - * min K 2 , f (K 2 )>f (K 1 ) V (K 1 , K 2 ) + W K * (K * ) , (27)
Proof. The corollary is a straightforward consequence of theorem 15.5 together with inequalities ( 13) and [START_REF] Trouvé | Asymptotical behaviour of several interacting annealing processes[END_REF]. In particular, the conditions ( 26) and ( 27 Proof of theorem 15.5. We prove that if the integer m satisfies the inequalities ( 26) and [START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF], then the set of inequalities ( 22), ( 23), ( 24) is fulfilled. Let λ be in f (E \ f * ) and let g be a graph belonging to G K λ (K - λ ∪ K + λ ). This graph may contain a finite number of transitions from K λ to K - λ :

K 1 → K 1 , • • • , K r → K r .
The first inequality [START_REF] Trouvé | Convergence optimale pour les algorithmes de recuits généralisés[END_REF] implies that for each K h , 1 ≤ h ≤ r, there exists K h in K + λ such that

ρ m 4 - Λ + 3 2 > V (K h , K h )
and lemma 13.5 yields V (K h , K h ) < V (K h , K h ). Let g be the graph obtained from g by replacing the r arrows

K 1 → K 1 , • • • , K r → K r by K 1 → K 1 , • • • , K r → K r .
The graph g is in the set G K λ (K + λ ) and satisfies V (g) ≤ V (g). This construction being valid for any graph of G K λ (K - λ ∪ K + λ ), we have

W K λ (K + λ ) ≤ W K λ (K - λ ∪ K + λ )
for all λ in f (E \ f * ) and the first condition ( 22) is proved.

Concerning the second condition [START_REF] Sinclair | Improved bounds for mixing rates of Markov chains and multicommodity flow[END_REF], we notice that any graph g belonging to G K * (K - * ) contains at least an arrow starting from K * and ending in K - * . Thus

W K * (K - * ) ≥ min K∈K * ,K ∈K * V (K, K )
and lemma 13.5 implies

W K * (K - * ) ≥ m 4 - Λ + 3 2 ρ
which, together with [START_REF] Trouvé | Convergence optimale pour les algorithmes de recuits généralisés[END_REF], yields [START_REF] Sinclair | Improved bounds for mixing rates of Markov chains and multicommodity flow[END_REF].

Similarly, any graph belonging to G K * ({K} ∪ K - * ) (where K = K * ) contains either a transition from K * to an attractor K of f * or to an attractor K of K - * , so that min K∈K * ,K =K * W K * ({K} ∪ K - * ) ≥ min V (K * , K) : K ∈ K, K = K * and lemmas 13. so that inequalities [START_REF] Trouvé | Convergence optimale pour les algorithmes de recuits généralisés[END_REF], [START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF] imply the third and last condition [START_REF] Sorkin | Efficient simulated annealing on fractal energy landscapes[END_REF]. Corollary 15.3 implies that W * = {K * }. Thus the sequence of the stationary measures of (X l n ), l ∈ N, concentrates on K * as l goes to infinity (proposition 12.3).

It remains now to prove that the limiting distribution is the uniform distribution over K * . We could proceed as in [START_REF] Cerf | The dynamics of mutation-selection algorithms with large population sizes[END_REF] and use the representation formula of the stationary measure involving Freidlin-Wentzell graphs. However, this result is rather a consequence of the following fact: the virtual energy possesses a unique minimum at K * and the unperturbed process (X ∞ n ) admits a unique invariant probability measure on K * (which is the uniform distribution over K * ). We are thus in a situation analogous to Theorem 4.2 of [10, chapter 6].

  then x k is chosen at random with the uniform distribution over the set z λ = [z] ∩ f λ (k lies in the last part of the set of indices). • if there exists an index r in {1 • • • |z λ |} such that τ (r -1, |z λ |) ≤ k < τ (r, |z λ |), then we put x k = z λ σ h (r) , where h is the unique integer in {1 • • • |z λ |} satisfying λ = λ h (the index k lies in the r-th part of the set of indices, where 1 ≤ r ≤ |z λ |).

Definition 12 . 4 .

 124 (Trouvé,[START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF] Definition 3.15]) The communication altitude A

Proposition 12 . 6 .

 126 (Trouvé,[START_REF] Trouvé | Cycle decompositions and simulated annealing[END_REF] Proposition 3.21])

  min minK∈K * \{K * } W K * ({K} ∪ K - * ) , W K * (K - * ) -max K∈K - * min K , f (K ) =f (K)

Proposition 15 . 4 .

 154 The quantity W K * (K * ) is bounded as a function of m:[START_REF] Trouvé | Asymptotical behaviour of several interacting annealing processes[END_REF] supm∈N * W K * (K * ) < |K * | V * = 2 |f * | V * < ∞.

m 2 (Corollary 15 . 6 .

 2156 |f * | + 1) min (a, cδ * ) > W K * (K * ) .For this integer, we have W * = {K * } and in addition ∀x ∈ E m ∀y ∈ K * lim There exists a critical population size m * such that the conclusion of theorem 15.5 holds for all m greater than m * . In addition, m * is smaller thanmax 2(Λ + 3) + 4 ρ (2 |f * | V * + V + ) , 2 |f * |+1 V * (|f * | + 1)min(a, cδ * ) .

2

 2 |f * | V * + V + , m 2(|f * | + 1) min (a, cδ * ) ≥ 2 |f * | V * .

  1 and 13.5 show that this quantity is greater than min m 2(|f * | + 1) min (a, cδ * )

The asymptotic dynamics of the algorithm

In this section, we put together the results of the previous sections 13 and 14 in order to prove theorem 15.5 which implies theorem 8.1. We give an explicit upper bound on the critical population size m * in corollary 15.6. We end the section with theorem 15.7, which is theorem 8.2 with an explicit upper bound on M * .

The basic tools used to study the asymptotic dynamics of the process are the Freidlin-Wentzell graphs [10, chapter 6]. For completeness, we recall the basic definition. Definition 15.1. (X-graphs) Let H be a finite set and let X be a subset of H. An X-graph is a graph consisting of arrows

(1) every point of H \ X is the initial point of exactly one arrow;

(2) there are no closed cycles in the graph. Condition (2) may be replaced by [START_REF] Catoni | Large deviations for annealing[END_REF] for any point h 1 of H \ X there exists a sequence of arrows leading from h 1 to some point h 2 of X. The set of X-graphs is denoted by G(X) and we will use the letter g to denote graphs.

We will consider graphs on the set of attractors K. For any graph g over K, we define its cost by

If X and Y are two subsets of K, we denote by G X (Y ) the set of Y -graphs over X ∪ Y . For instance, we have

We note G * X (Y ) the set of graphs in G X (Y ) which realize this minimum. If g is a graph over K, its restriction g |λ to the level λ is the graph

min min

Theorem 15.7. (structure of the cycles) Let m be such that

Then each cycle over the set of attractors K not containing the attractor K * is reduced to one single attractor K.

Proof. We define an order ≺ on the set of attractors K by

Notice that this order is an extension of the previous order

Furthermore, the set K admits a greatest element which is precisely the attractor K * :

Now let π be a cycle over K not containing K * . Suppose π is not reduced to one attractor.

Let K be a maximal element of π for the order ≺. Then, for each K in π distinct from K, we have either

Proposition 13.6, corollary 13.4 and lemma 13.5 then imply

Let K be an element of π \ {K} such that V (K, K ) is minimal. Then A(K, K ) = W (K) + V (K, K ) (where A is the communication altitude) whence

Yet lemmas 14.1 and 14.2 show that there exists an attractor K such that

Inequality (28) yields A(K, K ) < A(K, K ) so that necessarily the attractor K belongs to the cycle π: but this contradicts the maximality of K in the ordered set (π, ≺).

Proof of proposition 8.3. To obtain an upper bound on H 1 , it is enough to consider only the cycles over the set of attractors K. We also know that the attractors not containing K * are reduced to one attractor. Therefore

Lemmas 14.1 and 14.2 show that H 1 ≤ max (V + , V * ). Similarly, Proposition 1.33 of [START_REF] Trouvé | Parallélisation massive du recuit simulé[END_REF], proposition 13.6 and lemma 13.5 imply that H * e is greater than an affine increasing function of m.

Proof of theorem 8.7. The definition of α opt is [27, Definition 3.22]

For a cycle π not containing K * , the quantity H e (π) remains bounded whereas the virtual energy W (π) is greater than an affine strictly increasing function of m (a graph belonging to G K (π) contains necessarily a bad transition). Finally, the virtual energy of the ideal attractor W (K * ) is bounded as a function of m.

Proof of proposition 9.1. Let f be constant over E \ {i} and such that f (i) > f (j) for all j = i. We denote by K(j) the attractor associated to the point j (which consists simply of the uniform population (j, • • • , j)). On one hand we have V (K(i), K(e)) = 0 since a massive crossover event can transform the uniform population (i, • • • , i) into the uniform population (e, • • • , e) (such an event does not involve the random perturbations and has a null cost). On the other hand, the algorithm cannot escape from K(e) without performing at least one mutation (since β((e, e), (e, e)) = 1, the crossover has no effect on (e, • • • , e)). Therefore V (K(e), K) > 0 for any attractor K. Let g be a graph in G(K(i)) realizing the value W (K(i)) (see the beginning of section 15). We remove the arrow starting from K(e) (which has a positive cost) and we add the arrow K(i) → K(e) (of null cost). This way we obtain a graph of G(K(e)) whose cost is strictly less than the cost of g. It follows that W (K(e)) < W (K(i)). Proposition 12.3 implies that the sequence of the stationary measures does not concentrate on K(i) when the perturbations vanish.