2.2 Quelques illustrations
39
configuration de la chaˆ ıne X n = (X
i
n ) 1≤i≤N au temps n, l’´ etape de s´ election
consiste `
a simuler N v.a. (
X
i
n ) 1≤i≤N ind´ ependantes de mˆ eme loi
N
i=1
G(X
i
n )
N
j=1 G(X
j
n )
δ X i
n
Autrement dit chaque v.a.
X
k
n choisit l’une des valeurs X
i
n , avec la probabilit´ e
G(X
i
n )
N
j=1 G(X
j
n )
. On remarquera que ce proc´ ed´ e de s´ election peut aussi s’interpr´ eter
comme un m´ ecanisme de naissances et morts. Dans cette interpr´ etation,
les individus X
i
n disparaissent, ou donnent naissance ` a un certain nombre de
copies.
Il existe divers variantes pour s´ electionner les individus les mieux adapt´ es
au potentiel G. Dans le cas o` u le potentiel G est `
a valeurs dans [0, 1], il est bien
plus naturel “d’accepter” chaque individu X
i
n avec une probabilit´ e G(X
i
n ), et
de le remplacer (avec une probabilit´ e [1 − G(X
i
n )]) par un individu choisi avec
la loi discr` ete
N
i=1
G(X
i
n )
N
j=1 G(X
j
n )
δ X i
n
Plus formellement, ce m´ ecanisme de s´ election est ´ equivalent ` a poser pour
chaque i = 1, . . . , N
X
i
n =
X
i
n avec probabilit´ e G(X
i
n )
˜
X
i
n avec probabilit´ e 1 − G(X
i
n )
o` u ˜
X
i
n d´ esigne une v.a. de loi
N
j=1
G(X
j
n )
N
k=1 G(X k
n )
δ X
j
n
.
Pour des fonctions potentiel pouvant s’annuler sur certaines r´ egions de l’espace, il est possible que tous les individus aient des potentiels nuls. Dans cette
situation, l’algorithme est stopp´ e.
Mutation/Exploration : Durant la phase de mutation, les individus
s´ electionn´ es explorent l’espace ind´ ependamment les uns des autres, selon des
transitions de probabilit´ es ´ el´ ementaires M (x, y). Autrement dit, nous avons
X
i
n X
i
n+1 , o` u X
i
n+1 d´ esigne une v.a. de loi M (
X
i
n , .).
Plus formellement, nous avons
P
X
1
n+1 ∈ dx
1 , X
2
n+1 ∈ dx
2 , . . . , X
N
n+1 ∈ dx
N
|
X
1
n . . . ,
X
N
n
= M (
X
1
n , dx
1 )M (
X
2
n , dx
2 ) . . . M(
X
N
n , dx
N )