194
Recherche opérationnelle
pour chromosome la concaténation, dans l'ordre des sous-chromosomes, des
sous-chromosomes de numéro impair du premier parent et des souschromosomes de numéro pair du second (situation inverse pour le second
enfant). Par exemple, pour un croisement « 3 points » :
Parents :
Enfants :
c) croisement uniforme : on prend un des deux parents, et on répète fois
l'opération suivante : on tire au hasard un deux enfants (avec la probabilité ) et
on place à la jème position de l'enfant le j
ème gène du parent, cela pour
Pour l'enfant non tiré au sort, on place en j
èm
e position le j
ème gène
de l'autre parent.
Ces trois opérateurs de croisement ont la propriété suivante : si les deux parents
ont le même gène à la même position, cette caractéristique va se reproduire sur
les enfants. On a là la traduction de l'idée intuitive qui guide ce type de
méthode, à savoir que l'on essaye de garder ce qui fait la force des individus
(des solutions).
- Mutation
L'opérateur de mutation, appliqué sur les enfants obtenus à l'étape précédente,
doit permettre de créer une certaine diversité dans les populations engendrées.
En effet, la propriété des croisements que l'on vient d'évoquer (conservation des
gènes identiques des parents pour leurs descendants) a malgré tout
l'inconvénient potentiel de conduire à des individus '' faussement forts ''
(minimum local dans le langage des solutions) et de ne pas pouvoir en sortir.
L'opérateur de mutation le plus banal consiste à choisir aléatoirement un gène et
à changer sa valeur, mais cette opération est surtout valable pour des codages
du type
. Pour d'autres problèmes, il faudra adapter l'opérateur (par
exemple pour le problème du voyageur de commerce on pourra prendre la
transformation 2-opt décrite plus haut).
Par ailleurs, on peut considérer que la mutation suit un objectif contradictoire avec celui
du croisement, d'après ce que l'on vient de dire. Donc, comme on vise avant tout le
perfectionnement des descendants par le mariage des solutions, on appliquera l'opérateur
de mutation avec une probabilité faible.
De nombreuses variantes, encore une fois, ont été testées sur ces algorithmes génétiques;
on peut notamment mixer les heuristiques que l'on vient de voir, par exemple en
combinant algorithme génétique et recuit simulé (modification aléatoire d'une solution).
De même, les opérateurs de croisement et de mutation doivent être adaptés au type de
Recherche opérationnelle
pour chromosome la concaténation, dans l'ordre des sous-chromosomes, des
sous-chromosomes de numéro impair du premier parent et des souschromosomes de numéro pair du second (situation inverse pour le second
enfant). Par exemple, pour un croisement « 3 points » :
Parents :
Enfants :
c) croisement uniforme : on prend un des deux parents, et on répète fois
l'opération suivante : on tire au hasard un deux enfants (avec la probabilité ) et
on place à la jème position de l'enfant le j
ème gène du parent, cela pour
Pour l'enfant non tiré au sort, on place en j
èm
e position le j
ème gène
de l'autre parent.
Ces trois opérateurs de croisement ont la propriété suivante : si les deux parents
ont le même gène à la même position, cette caractéristique va se reproduire sur
les enfants. On a là la traduction de l'idée intuitive qui guide ce type de
méthode, à savoir que l'on essaye de garder ce qui fait la force des individus
(des solutions).
- Mutation
L'opérateur de mutation, appliqué sur les enfants obtenus à l'étape précédente,
doit permettre de créer une certaine diversité dans les populations engendrées.
En effet, la propriété des croisements que l'on vient d'évoquer (conservation des
gènes identiques des parents pour leurs descendants) a malgré tout
l'inconvénient potentiel de conduire à des individus '' faussement forts ''
(minimum local dans le langage des solutions) et de ne pas pouvoir en sortir.
L'opérateur de mutation le plus banal consiste à choisir aléatoirement un gène et
à changer sa valeur, mais cette opération est surtout valable pour des codages
du type
. Pour d'autres problèmes, il faudra adapter l'opérateur (par
exemple pour le problème du voyageur de commerce on pourra prendre la
transformation 2-opt décrite plus haut).
Par ailleurs, on peut considérer que la mutation suit un objectif contradictoire avec celui
du croisement, d'après ce que l'on vient de dire. Donc, comme on vise avant tout le
perfectionnement des descendants par le mariage des solutions, on appliquera l'opérateur
de mutation avec une probabilité faible.
De nombreuses variantes, encore une fois, ont été testées sur ces algorithmes génétiques;
on peut notamment mixer les heuristiques que l'on vient de voir, par exemple en
combinant algorithme génétique et recuit simulé (modification aléatoire d'une solution).
De même, les opérateurs de croisement et de mutation doivent être adaptés au type de