11.5 Les algo rithmes géné tiques
413
© Dunod – Toute reproduction non autorisée est un délit.
opé ra teurs les plus uti li sés sont le croi se ment (« crossover ») et la muta tion, dont le
prin cipe est illus tré par la Figure 11.6 :
• le croi se ment pro duit deux des cen dants à par tir de deux parents, selon le méca nisme
sui vant (Figure 11.6(a) : croi se ment mono point) : les deux chaînes parents sont cou
pées au même niveau (choisi aléa toi re ment), for mant ainsi cha cune deux sous chaînes ;
deux chaînes des cen dantes sont alors construites en met tant bout à bout la sous chaîne
de gauche d’un parent et la sous chaîne de droite de l’autre parent ;
• la muta tion pro duit un nou vel indi vidu à par tir d’un seul indi vidu, dont cer tains
bits de la chaîne de bits qui le code, sont complémentés (Figure 11.6(b) : muta tion
d’un seul bit).
La phase de repro duc tion est orga ni sée selon les règles sui vantes :
• elle com porte un nombre donné d’opé ra tions géné tiques (suc ces sion pseudoaléatoire de croi se ments ou de muta tions, selon des taux fixés ; géné ra le ment, les
muta tions sont rares) ;
• les indi vi dus de la popu la tion qui prennent part à la repro duc tion sont préa la ble -
ment sélec tion nés, en res pec tant le prin cipe sui vant : plus un indi vidu est com pétent,
plus sa pro ba bi lité de sélec tion est éle vée ;
• les des cen dants ainsi pro duits n’éli minent pas leurs parents, qui demeurent dans la
popu la tion cou rante ; mais ces des cen dants sont mémo ri sés sépa ré ment.
La phase de rem pla ce ment consiste à sélec tion ner les membres de la nou velle
géné ra tion : on peut, par exemple, rem pla cer les plus « mau vais » indi vi dus (au sens
Figure 11.5 Orga ni gramme de prin cipe d’un algo rithme géné tique.
N « individus » : N points x pris au hasard
Chaque individu est codé par une chaîne de bits
POPULATION INITIALE
REPRODUCTION
production de M « descendants » , par application des
opérateurs génétiques : « croisement » et « mutation »
NON
OUI
SELECTION
formation de la nouvelle « génération », par
sélection des N meilleurs individus (jaugés
par f ), parmi les N+M disponibles
nombre maximal de générations successives atteint ?
résultat = meilleur individu x rencontré
413
© Dunod – Toute reproduction non autorisée est un délit.
opé ra teurs les plus uti li sés sont le croi se ment (« crossover ») et la muta tion, dont le
prin cipe est illus tré par la Figure 11.6 :
• le croi se ment pro duit deux des cen dants à par tir de deux parents, selon le méca nisme
sui vant (Figure 11.6(a) : croi se ment mono point) : les deux chaînes parents sont cou
pées au même niveau (choisi aléa toi re ment), for mant ainsi cha cune deux sous chaînes ;
deux chaînes des cen dantes sont alors construites en met tant bout à bout la sous chaîne
de gauche d’un parent et la sous chaîne de droite de l’autre parent ;
• la muta tion pro duit un nou vel indi vidu à par tir d’un seul indi vidu, dont cer tains
bits de la chaîne de bits qui le code, sont complémentés (Figure 11.6(b) : muta tion
d’un seul bit).
La phase de repro duc tion est orga ni sée selon les règles sui vantes :
• elle com porte un nombre donné d’opé ra tions géné tiques (suc ces sion pseudoaléatoire de croi se ments ou de muta tions, selon des taux fixés ; géné ra le ment, les
muta tions sont rares) ;
• les indi vi dus de la popu la tion qui prennent part à la repro duc tion sont préa la ble -
ment sélec tion nés, en res pec tant le prin cipe sui vant : plus un indi vidu est com pétent,
plus sa pro ba bi lité de sélec tion est éle vée ;
• les des cen dants ainsi pro duits n’éli minent pas leurs parents, qui demeurent dans la
popu la tion cou rante ; mais ces des cen dants sont mémo ri sés sépa ré ment.
La phase de rem pla ce ment consiste à sélec tion ner les membres de la nou velle
géné ra tion : on peut, par exemple, rem pla cer les plus « mau vais » indi vi dus (au sens
Figure 11.5 Orga ni gramme de prin cipe d’un algo rithme géné tique.
N « individus » : N points x pris au hasard
Chaque individu est codé par une chaîne de bits
POPULATION INITIALE
REPRODUCTION
production de M « descendants » , par application des
opérateurs génétiques : « croisement » et « mutation »
NON
OUI
SELECTION
formation de la nouvelle « génération », par
sélection des N meilleurs individus (jaugés
par f ), parmi les N+M disponibles
nombre maximal de générations successives atteint ?
résultat = meilleur individu x rencontré