Complexité des problèmes et heuristiques
193
La sélection prend alors la forme d'une loterie ; chaque solution
va avoir la
probabilité:
)
(
)
(
=
)
(
1
=
j
N
j
i
i
x
F
x
F
x
p
d'être choisie.
Le procédé pour ce faire est très simple :
On définit les bornes de la fonction de répartition liée à la distribution :
)
(
=
)
(
1
=
k
i
k
i
x
p
x
l
On tire (cf ci-dessus pour le recuit simulé) un nombre aléatoire
compris
entre
. Si
alors on sélectionne la solution .
On répète fois cette procédure de façon à obtenir toujours
individus. Un
individu fort sera en principe (mais le hasard peut s'y opposer) sélectionné
plusieurs fois.
- Croisement
Dans l'étape 4 introduite ci-dessus, on apparie deux à deux les solutions
sélectionnées par la procédure précédente. Soit une telle paire de solutions, avec
leurs chromosomes respectifs
. Cette paire de parents va engendrer une
paire d'enfants, par l'intermédiaire d'une certaine combinaison des
chromosomes (opérateur de croisement).
Il existe plusieurs opérateurs de croisement (et à la limite on peut en imaginer
plein d'autres). En voici quelques uns :
a) croisement « un point » : supposons que les chromosomes soient constitués
par une suite de p caractères, les gènes, pris dans un même vocabulaire. On tire
un nombre aléatoire entier compris entre
Soit ce nombre.
Avant le croisement les deux chromosomes s'écrivent :
)
,....
,
....
..........
(
=
1
1
p
l
l
a
a
a
a
a
)
,....
,
....
..........
(
=
1
1
p
l
l
b
b
b
b
b
Après le croisement, les chromosomes des enfants sont :
)
.....
,
...
..........
(
=
1
1
p
l
l
'
b
b
a
a
a
)
...
,
.....
(
=
1
1
p
l
l
'
a
a
b
b
b
b) croisement
: on génère aléatoirement non un nombre compris entre
mais , créant ainsi
sous-chromosomes. Le premier enfant aura