11.6 Les algo rithmes de colo nies de four mis
415
© Dunod – Toute reproduction non autorisée est un délit.
cube du nombre de chaînes [Gold94]) : c’est le paral lé lisme impli cite pro clamé par
Holland.
Chaque région de l’espace des solu tions est carac té ri sée par un motif (par exemple :
11**), qui dépend du codage choisi ; ce motif pos sède un ordre (le nombre de bits
spé ci fiés) et une lon gueur (la dis tance entre le pre mier et le der nier bit spé ci fié).
L’effi ca cité d’un algo rithme géné tique est fonc tion des motifs asso ciés aux bonnes
régions (i.e. aux régions qui contiennent une pro por tion éle vée de bonnes solu tions) :
plus ces motifs sont courts et com pacts, mieux l’algo rithme fonc tionne. En effet,
lors qu’une chaîne située dans une bonne région prend part à un croi se ment, le motif
asso cié à cette région a peu de chances d’être coupé, s’il est court : le plus sou vent,
il est trans mis au des cen dant, qui se retrouve alors dans la même région ; comme
il s’agit d’une bonne région, le parent et son des cen dant ont de bonnes chances
d’appar te nir à la géné ra tion sui vante, et d’être sélec tion nés pour la repro duc tion, ce
qui amorce une réac tion en chaîne…
On montre que, d’une géné ra tion à la sui vante, la répé tition des croi se ments accroît
exponentiellement le nombre de chaînes tes tées dans une bonne région, lorsque l’ordre
et la lon gueur du motif de cette région sont suf fi sam mentpetits par rap port à la lon
gueur des chaînes (théo rème fon da men tal des algo rithmes géné tiques [Gold94]).
En mul ti pliant ainsi les chaînes tes tées dans les bonnes régions, l’algo rithme
accroît évi dem ment les chances de ren contrer la solu tion opti male recherc hée, qui
cor res pond au regrou pe ment, dans une même chaîne, des bons motifs pré cé dents,
dénom més blocs de construc tion.
Cepen dant, ces consi dé ra tions théo riques ont des consé quences opé ra tion nelles
limi tées : en pra tique, le choix du codage relève encore plus sou vent de l’art que de
la science ... Dans les pro blèmes com bi na toires, le codage est sou vent sug géré par la
nature même du pro blème, ce qui induit des per for mances inégales des algo rithmes
géné tiques.
En résumé. Pour des pro blèmes concrets très divers, rele vant par exemple de
l’ingé nie rie (opti mi sation de struc tures méca niques), de la méde cine (ima ge
rie médi cale) ou de la théo rie des jeux, les algo rithmes géné tiques ont donné
d’emblée pleine satis faction. Sur d’autres appli ca tions par contre, comme
l’opti mi sation de fonc tions à variables conti nues, leur emploi s’est avéré déce
vant, faute de la mise en évi dence d’un codage « approp rié » du pro blème. Ce
com por te ment inégal s’oppose au suc cès plus glo bal du recuit simulé et, dans
une moindre mesure, de la méthode tabou.
11.6 les algo rithMes de colo nies de four Mis
Cette approche, due à Dorigo et al [Dori91], s’efforce de simu ler la capa cité col lec tive
de réso lu tion de cer tains pro blèmes, obser vée chez une colo nie de four mis, dont les
membres sont pour tant indi vi duel le ment dotés de facul tés très limi tées. Appa rues sur
Terre il y a quelque 100 mil lions d’années, les four mis sont en effet l’une des espèces
415
© Dunod – Toute reproduction non autorisée est un délit.
cube du nombre de chaînes [Gold94]) : c’est le paral lé lisme impli cite pro clamé par
Holland.
Chaque région de l’espace des solu tions est carac té ri sée par un motif (par exemple :
11**), qui dépend du codage choisi ; ce motif pos sède un ordre (le nombre de bits
spé ci fiés) et une lon gueur (la dis tance entre le pre mier et le der nier bit spé ci fié).
L’effi ca cité d’un algo rithme géné tique est fonc tion des motifs asso ciés aux bonnes
régions (i.e. aux régions qui contiennent une pro por tion éle vée de bonnes solu tions) :
plus ces motifs sont courts et com pacts, mieux l’algo rithme fonc tionne. En effet,
lors qu’une chaîne située dans une bonne région prend part à un croi se ment, le motif
asso cié à cette région a peu de chances d’être coupé, s’il est court : le plus sou vent,
il est trans mis au des cen dant, qui se retrouve alors dans la même région ; comme
il s’agit d’une bonne région, le parent et son des cen dant ont de bonnes chances
d’appar te nir à la géné ra tion sui vante, et d’être sélec tion nés pour la repro duc tion, ce
qui amorce une réac tion en chaîne…
On montre que, d’une géné ra tion à la sui vante, la répé tition des croi se ments accroît
exponentiellement le nombre de chaînes tes tées dans une bonne région, lorsque l’ordre
et la lon gueur du motif de cette région sont suf fi sam mentpetits par rap port à la lon
gueur des chaînes (théo rème fon da men tal des algo rithmes géné tiques [Gold94]).
En mul ti pliant ainsi les chaînes tes tées dans les bonnes régions, l’algo rithme
accroît évi dem ment les chances de ren contrer la solu tion opti male recherc hée, qui
cor res pond au regrou pe ment, dans une même chaîne, des bons motifs pré cé dents,
dénom més blocs de construc tion.
Cepen dant, ces consi dé ra tions théo riques ont des consé quences opé ra tion nelles
limi tées : en pra tique, le choix du codage relève encore plus sou vent de l’art que de
la science ... Dans les pro blèmes com bi na toires, le codage est sou vent sug géré par la
nature même du pro blème, ce qui induit des per for mances inégales des algo rithmes
géné tiques.
En résumé. Pour des pro blèmes concrets très divers, rele vant par exemple de
l’ingé nie rie (opti mi sation de struc tures méca niques), de la méde cine (ima ge
rie médi cale) ou de la théo rie des jeux, les algo rithmes géné tiques ont donné
d’emblée pleine satis faction. Sur d’autres appli ca tions par contre, comme
l’opti mi sation de fonc tions à variables conti nues, leur emploi s’est avéré déce
vant, faute de la mise en évi dence d’un codage « approp rié » du pro blème. Ce
com por te ment inégal s’oppose au suc cès plus glo bal du recuit simulé et, dans
une moindre mesure, de la méthode tabou.
11.6 les algo rithMes de colo nies de four Mis
Cette approche, due à Dorigo et al [Dori91], s’efforce de simu ler la capa cité col lec tive
de réso lu tion de cer tains pro blèmes, obser vée chez une colo nie de four mis, dont les
membres sont pour tant indi vi duel le ment dotés de facul tés très limi tées. Appa rues sur
Terre il y a quelque 100 mil lions d’années, les four mis sont en effet l’une des espèces