Chapitre 11 • Métaheuristiques en optimisation combinatoire
414
de la fonc tion objec tif) de la popu la tion cou rante par les meilleurs indi vi dus pro duits
(en nombre égal).
L’algo rithme est inter rompu après un nombre donné de géné ra tions, ou bien dès
qu’une bonne solu tion est trou vée.
Figure 11.6 Prin cipe des opé ra teurs de croi se ment et de muta tion,
dans le cas d’indi vi dus codés sous la forme de chaînes de 8 bits.
Cepen dant, dans l’état actuel de la théo rie des algo rithmes géné tiques [Holl92],
il n’existe aucune garan tie que la méthode découvre la solu tion opti male. En outre,
le suc cès de la méthode dépend beau coup du codage des indi vi dus, qui est lui­ même
fonc tion du pro blème d’opti mi sation com bi na toire traité. Cette impor tance du codage
s’explique de la manière sui vante. Une chaîne de bits appar tient à toutes les régions
que ses bits défi nissent. Par exemple, la chaîne 1101 appar tient aux régions 11**, *1*1,
*101, etc ... : où les * indiquent que la valeur du bit n’est pas spé ci fiée. Il en résulte
qu’un algo rithme géné tique, qui mani pule au total, typi que ment, quelques milliers
de chaînes, échan tillonne en réa lité un nombre bien supé rieur de régions (en gros, le