40
2 Chaˆ ınes de Markov abstraites
`
A titre d’exemple, si M (x, y) d´ esigne la matrice de transition d’une marche
al´ eatoire sur Z
d , on peut r´ ealiser dynamiquement ces explorations locales en
posant
X
i
n+1 =
X
i
n + U
i
n+1
o` u U
i
n+1 d´ esigne une suite de v.a. ind´ ependantes de mˆ eme loi p, sur l’ensemble
des vecteurs unitaires directionnels U = {u ∈ Z
d : |u| = 1}.
Un exemple sch´ ematique d’´ evolution de N = 4 individus est repr´ esent´ e
dans la figure suivante. Les nombres entiers entre parenth` eses correspondent
au nombre d’individus sur le site en question, apr` es l’´ etape de s´ election.
Mutation
Selection
(0)
(2)
(2)
Mutation
Selection
Mutation
(0)
(1)
(3)
(0)
(0)
Fig. 2.4. Algorithme g´ en´ etique (N = 4 individus)
Exercice 2.2.3 D´ ecrire math´ ematiquement, et sch´ ematiquement, l’algorithme
g´ en´ etique sur Z associ´ e ` a la fonction potentiel indicatrice G(x) = 1 [−L,L] , avec
L ≥ 1. On conviendra que les mutations sont donn´ ees par les transitions d’une
marche al´ eatoire sur Z, et l’on initialisera les individus en l’origine.
Exercice 2.2.4 D´ ecrire l’algorithme g´ en´ etique sur R associ´ e ` a des mutations
gaussiennes
M (x, dy) =
1
√
2π
exp
−
1
2
(y − x)
2
dy
et un potentiel quadratique centr´ e autour d’un point a ∈ R
G(x) = exp
−
1
2
(x − a)
2
Mod` eles d’arbres g´ en´ ealogiques
Mod` eles non homog` enes : L’algorithme g´ en´ etique d´ ecrit dans la section pr´ ec´ edente peut ˆ etre ´ etendu de fa¸ con naturelle ` a des espaces d’´ etats E n
d´ ependants du param` etre temporel n ∈ N. Dans ce contexte, les individus X
i
n
vivent ` a chaque instant n dans l’espace E n . Les s´ elections s’effectuent dans
ces mˆ emes espaces, tandis que les mutations s’expriment comme des passages
al´ eatoires d’un ´ etat de E n vers un nouvel ´ etat dans E n+1 .
2 Chaˆ ınes de Markov abstraites
`
A titre d’exemple, si M (x, y) d´ esigne la matrice de transition d’une marche
al´ eatoire sur Z
d , on peut r´ ealiser dynamiquement ces explorations locales en
posant
X
i
n+1 =
X
i
n + U
i
n+1
o` u U
i
n+1 d´ esigne une suite de v.a. ind´ ependantes de mˆ eme loi p, sur l’ensemble
des vecteurs unitaires directionnels U = {u ∈ Z
d : |u| = 1}.
Un exemple sch´ ematique d’´ evolution de N = 4 individus est repr´ esent´ e
dans la figure suivante. Les nombres entiers entre parenth` eses correspondent
au nombre d’individus sur le site en question, apr` es l’´ etape de s´ election.
Mutation
Selection
(0)
(2)
(2)
Mutation
Selection
Mutation
(0)
(1)
(3)
(0)
(0)
Fig. 2.4. Algorithme g´ en´ etique (N = 4 individus)
Exercice 2.2.3 D´ ecrire math´ ematiquement, et sch´ ematiquement, l’algorithme
g´ en´ etique sur Z associ´ e ` a la fonction potentiel indicatrice G(x) = 1 [−L,L] , avec
L ≥ 1. On conviendra que les mutations sont donn´ ees par les transitions d’une
marche al´ eatoire sur Z, et l’on initialisera les individus en l’origine.
Exercice 2.2.4 D´ ecrire l’algorithme g´ en´ etique sur R associ´ e ` a des mutations
gaussiennes
M (x, dy) =
1
√
2π
exp
−
1
2
(y − x)
2
dy
et un potentiel quadratique centr´ e autour d’un point a ∈ R
G(x) = exp
−
1
2
(x − a)
2
Mod` eles d’arbres g´ en´ ealogiques
Mod` eles non homog` enes : L’algorithme g´ en´ etique d´ ecrit dans la section pr´ ec´ edente peut ˆ etre ´ etendu de fa¸ con naturelle ` a des espaces d’´ etats E n
d´ ependants du param` etre temporel n ∈ N. Dans ce contexte, les individus X
i
n
vivent ` a chaque instant n dans l’espace E n . Les s´ elections s’effectuent dans
ces mˆ emes espaces, tandis que les mutations s’expriment comme des passages
al´ eatoires d’un ´ etat de E n vers un nouvel ´ etat dans E n+1 .