C. R. Acad. Sci. Paris, t. 331, Série I, p. 469–474, 2000Probabilités/Probability Theory

Un principe d’invariance pour un algorithmegénétique en population finie

Jean BÉRARD, Alexis BIENVENÜE

Laboratoire de probabilités, combinatoire et statistique, Université Claude-Bernard–Lyon-I, bâtiment 101, 43,boulevard du 11-Novembre-1918, 69622 Villeurbanne cedex, FranceCourriel : berard@jonas.univ-lyon1.fr, bienvenu@jonas.univ-lyon1.fr

(Reçu le 18 juin 2000, accepté le 26 juin 2000)

Résumé. Nous étudions le comportement asymptotique d’un algorithme génétique de mutation-sélection en population finie, défini sur les entiers et associé à une marche au hasard simpleet à la fonction d’adaptationf(x) = x. Nous prouvons un principe d’invariance pour lenuage de particules normalisé. 2000 Académie des sciences/Éditions scientifiques etmédicales Elsevier SAS

An invariance principle for a genetic algorithm with finite population

Abstract. We study the asymptotic behaviour of a mutation-selection genetic algorithm on the integerswith finite population, defined by a simple random walk and the fitness functionf(x) = x.We prove an invariance principle for the normalized population. 2000 Académie dessciences/Éditions scientifiques et médicales Elsevier SAS

Abridged English version

Let p ∈ N∗. Let Xn =(X

(i)n

)16i6p be the Markov chain with state spaceNp starting fromX0 =

(1, . . . ,1) and defined by the following transitions:1. selection step: Xn −→ Yn

If Xn = (0, . . . ,0), then Yn = (1, . . . ,1). Else, theY (i)n , 1 6 i 6 p, are chosen randomly and

independently among the{X

(i)n , 16 i6 p

}according to the probability law

1

Sn

p∑i=1

X(i)n δ

X(i)n, whereSn =

p∑i=1

X(i)n .

2. mutation step: Yn −→Xn+1

Thep particlesY (i)n evolve independently, each of them performs one step of a simple random walk on

Z (symmetric, to the nearest neighbours) and their new positions are theX(i)n+1, 16 i6 p.

Note présentée par Jean-Pierre KAHANE .

S0764-4442(00)01626-8/FLA 2000 Académie des sciences/Éditions scientifiques et médicales Elsevier SAS. Tous droits réservés. 469

J. Bérard, A. Bienvenüe

We use the following notations:

Fn = σ(X0, Y0, . . . ,Xn−1, Yn−1,Xn), Fn = Sn/p, and ∆Fn = Fn+1 −Fn.

Forx ∈Np, Ex denotes the expectation under the law of the Markov chainX starting fromX0 = x. Wedefine the barycenter ofx asm(x) = (x1 + · · ·+ xp)/p and the diameter ofx asd(x) = sup16i, j6p |xi −xj |. Finally,Zn(t) =Xbntc/

√n andZn(t) =m(Zn(t)), that isZn(t) = Fbntc/

√n.

The Markov chainX defined above is a simplified model of the random evolution of a population undermutation and selection. For more about the relevance of this model to population biology see [6] and [2].Classical references about genetic algorithms are [4] and [3].

Our result is the following:

THEOREM. – The chain(Zn) converges in law in the Skorohod spaceD([0,1],Rp+) to (1,1, . . . ,1)R,where(R(t))06t61 is a (2p− 1)-dimensional Bessel process starting from zero.

Our proof relies upon a recursive estimation of the even moments ofFn, which is expressed by thefollowing proposition:

PROPOSITION. – For all h ∈N andx ∈Np, the following property holds:

ExF 2hn = f(x,n,h) +α(x,n,h),

where

f(x,n,h) =

h∑i=0

fi(h)m(x)2inh−i, with fi(h) ∈R,

andα(x,n,h) is a finite sum of terms

ε(x,n)m(x)injd(x)k, with i, j, k ∈N, 2j + i6 2h,

whereε(x,n) is bounded and converges to zero asn goes to infinity, uniformly inx.

We then apply inductively the Markov property and the proposition to get the convergence of themomentsEZn(t1)2h1 × · · · ×Zn(tm)2hm , that yields the theorem.

1. Introduction

Depuis leur introduction par J. Holland [4], les algorithmes génétiques, dont le principe repose sur uneanalogie avec les mécanismes biologiques de l’évolution, n’ont cessé de se développer, faisant preuved’une remarquable efficacité pratique dans la résolution de problèmes difficiles d’optimisation combinatoire(cf. D. Goldberg [3]). Ils présentent par ailleurs un intérêt en biologie en tant que modèles simplifiésde l’évolution d’une population sous l’effet de mutations aléatoires et d’une pression de sélection (cf.L. Tsimring, H. Levine et D. Kessler [6] et D. Bonnaz [2]). Nous nous proposons d’étudier le comportementasymptotique d’un algorithme génétique de mutation-sélection en population finie défini sur les entiers etassocié à une marche au hasard simple et à la fonction d’adaptationf(x) = x. Plus précisément, nousétablissons un principe d’invariance pour le nuage de points normalisé associé à l’algorithme. Le modèleéquivalent en population infinie a par ailleurs été étudié par C. Mazza et D. Piau [5], et présente uncomportement radicalement différent.

Fixonsp ∈ N∗. SoitXn =(X

(i)n

)16i6p la chaîne de Markov surNp issue deX0 = (1, . . . ,1) et définie

par les transitions suivantes :

470

Un principe d’invariance pour un algorithme génétique

1. Étape de sélection: Xn −→ YnSi Xn = (0, . . . ,0), alors Yn = (1, . . . ,1). Sinon, lesY (i)

n , 1 6 i 6 p, sont choisis de manière

indépendante parmi{X

(i)n , 16 i6 p

}selon la loi :

1

Sn

p∑i=1

X(i)n δ

X(i)n, oùSn =

p∑i=1

X(i)n .

2. Étape de mutation: Yn −→Xn+1

Les p particulesY (i)n évoluent indépendamment, chacune effectuant un pas d’une marche au hasard

simple surZ symétrique, au plus proche voisin, donnant ainsi lesX(i)n+1.

Nous utiliserons les notations suivantes :

Fn = σ(X0, Y0, . . . ,Xn−1, Yn−1,Xn), Fn = Sn/p et ∆Fn = Fn+1 − Fn.

Si x ∈ Np, Ex désigne l’espérance sous la loi de la chaîne de MarkovX partant deX0 = x. Ondéfinit également le barycentre dex commem(x) = (x1 + · · · + xp)/p et le diamètre dex commed(x) = sup16i, j6p |xi − xj |.

Enfin,Zn(t) =Xbntc/√n etZn(t) =m(Zn(t)), c’est-à-direZn(t) = Fbntc/

√n.

Notre résultat est le suivant :

THÉORÈME. – La chaîne(Zn)n>0 converge en loi dans l’espace de SkorohodD([0,1],Rp+) vers levecteur(1,1, . . . ,1)R, où (R(t))06t61 est un processus de Bessel de dimension2p− 1 issu de zéro.

2. Résultats préliminaires

Le lemme 1 montre que le nuage de particulesXn est minoré stochastiquement par un processus demutation-sélectionVn associé à une sélection uniforme. Remarquons qu’àn fixé, chaqueV (i)

n suit la loi dela position au tempsn d’une marche simple réfléchie. Cependant, ài fixé, (V

(i)n )n>0 n’est pas une marche

simple réfléchie.

LEMME 1. – On fait partir la chaîne d’un pointX0 = x ∈ Np quelconque. On peut construire unprocessusVn = (V

(i)n )16i6p ne dépendant pas dex et tel que, pour tousn> 1 et 16 i6 p :

– V(i)n 6X(i)

n ,– V

(i)n suit la loi de la position au tempsn d’une marche au hasard simple surN issue de zéro et de

probabilités de transitionspi→i−1 = pi→i+1 = 1/2 pour i ∈N∗, etp0→0 = p0→1 = 1/2.

COROLLAIRE 1. – Pour chaque16 i6 p fixé,X(i)n −−−−→

n→+∞+∞ en probabilité.

Le lemme suivant fournit une majoration stochastique du diamètre du nuage considéré.

LEMME 2. – On fait partir la chaîne d’un pointX0 = x ∈ Np quelconque. Pour toutn ∈ N∗, il existeune variable aléatoireAn suivant une loi géométrique surN∗ de paramètrep1−p, telle que

d(Xn)6 2An 1{An6n} +(d(x) + 2n

)1{An>n}.

En particulier, sid(x) = 0, on a:

d(Xn)6 2An.

Le lemme qui suit, joint au corollaire 1 et au lemme 2, permet de montrer que les probabilités de transitionassociées à l’étape de sélection peuvent être approchées en moyenne par celles qui correspondent à unesélection uniforme.

471

J. Bérard, A. Bienvenüe

LEMME 3. – On fait partir la chaîne deX0 = x ∈ Np quelconque. Pour1 6 i, j 6 p, sur l’ensemble{Xn 6= 0}, on a: ∣∣∣∣X(i)

n X(j)n

S2n

− 1

p2

∣∣∣∣6 2pd(Xn)

Fn,

et ∣∣∣∣X(i)n

Sn− 1

p

∣∣∣∣6 p d(Xn)

Fn.

3. Démonstration du théorème

Nous prouvons le théorème par la méthode des moments. La proposition suivante, qui fournit uneestimation récursive des moments d’ordre pair deFn, est le résultat-clé.

PROPOSITION 1. – Pour toush ∈N etx∈Np, la propriété suivante, notée(Ph), est vérifiée:

ExF 2hn = f(x,n,h) +α(x,n,h),

où(i) f(x,n,h) =

∑hi=0 fi(h)m(x)2inh−i, avecfi(h) ∈R ;

(ii) α(x,n,h) est une somme finie de termes de la forme:

ε(x,n)m(x)injd(x)k, aveci, j, k ∈N, 2j + i6 2h,

oùε(x,n) est borné et tend vers zéro lorsquen tend vers l’infini, uniformément enx.

Démonstration. –La propriété (P0) est bien vérifiée (avecf(x,n,0) = 1). Montrons par récurrence que(Ph) est vérifiée pour touth ∈N. Supposons donc que (Pi) est vérifiée pour touti6 h− 1.

On écrit :

ExF 2hn =m(x)2h + Ex

n−1∑r=0

(F 2hr+1 −F 2h

r

); (1)

Ex(F 2hr+1 −F 2h

r

)= Ex

((Fr + ∆Fr)

2h − F 2hr

)=C1

2hEx(F 2h−1r Ex(∆Fr | Fr)

)+C2

2hEx(F 2h−2r Ex

((∆Fr)

2 | Fr))

+

2h∑`=3

C`2hEx(F 2h−`r (∆Fr)

`), (2)

puis on insère l’égalité (2) dans (1).D’après l’estimation du lemme 2 et l’hypothèse de récurrence, la contribution dans (1) du dernier terme

de (2) vérifie la propriété ii de la proposition 1.Pour étudier la contribution des deux premiers termes, on explicite les espérances conditionnelles

Ex(∆Fr | Fr) et Ex((∆Fr)

2 | Fr),

et l’on approche les probabilités de transition de l’étape de sélection grâce au lemme 3.

472

Un principe d’invariance pour un algorithme génétique

On obtient finalement :

ExF 2hn =m(x)2h +

[2h(p− 1) + h(2h− 1)

]n−1∑r=0

f(x, r, h− 1) + β(x,n,h),

oùβ(x,n,h) vérifie la propriété ii de la proposition 1.Ainsi, la propriété (Ph) est satisfaite, avec le choix :

fh(h) = 1,

fi(h) =2h(p− 1) + h(2h− 1)

h− i fi(h− 1), 06 i6 h− 1.

(3)

2Les fonctions(fi(h))06i6h de (3) sont reliées au processus de Bessel(R(t))t>0 de dimension2p− 1

issu de zéro via le lemme suivant, qui permettra d’identifier la loi limite comme étant celle deR :

LEMME 4. – Pouru ∈R+, on a:

EuR(t)2h =

h∑i=0

fi(h)u2ith−i.

Nous étudions maintenant les marginales de dimension finie deZn :

PROPOSITION 2. –(a) Les marginales de dimension finie de la loi du processusZn convergent en loi vers celles du

processusR ;(b) Il existe une constanteCp telle que, pour tous06 t1 6 t6 t2 6 1, on ait :

E(Zn(t)−Zn(t1)

)2(Zn(t)−Zn(t2)

)2 6Cp(t2 − t1)3/2.

Démonstration. –Pour établir (a), on démontre par récurrence la convergence des moments

EZn(t1)2h1 × · · · ×Zn(tm)2hm .

À cet effet, on utilise la propriété de Markov deX ainsi que les estimations fournies par la proposition 1.Le lemme 4 permet alors d’identifier la loi limite, dont les moments sont les limites des moments deZn.

Pour établir (b), on fait appel aux estimations fournies par la proposition 1.2La convergence des lois des processus(Zn)n>0 vers celle deR est une conséquence de la proposition 2

et du théorème classique 15.6 de [1]. Il reste à remarquer que, d’après le lemme 2, le vecteur

n−1/2(X

(i)bn·c −X

(1)bn·c)

16i6p

tend vers zéro en probabilité pour la norme uniforme sur[0,1], donc aussi pour la topologie de Skorokhod,ce qui conclut la preuve du théorème.

Remerciements.Nous remercions vivement C. Mazza et D. Piau pour leurs commentaires et suggestions.

473

J. Bérard, A. Bienvenüe

Références bibliographiques

[1] Billingsley P., Convergence of Probability Measures, John Wiley & Sons, New York, 1968.[2] Bonnaz D., Modèles stochastiques de dynamique des populations, Thèse de doctorat, Université de Lausanne, 1998.[3] Goldberg D.E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading,

MA, 1989.[4] Holland J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Mich., 1975,

pp. ix+183. An introductory analysis with applications to biology, control, and artificial intelligence.[5] Mazza C., Piau D., On the effect of selection in genetic algorithms, (2000) (soumis).[6] Tsimring L.S., Levine H., Kessler D.A., RNA virus evolution via a fitness-space model, Phys. Rev. Lett. 76 (1996)

4440.

474