Chapitre 11 • Métaheuristiques en optimisation combinatoire
412
simple d’emploi. Cepen dant, les divers méca nismes annexes (comme l’inten si
fi ca tion, la diver si fi ca tion et l’aspi ra tion) apportent une notable com plexité. De
plus, la méthode souffre de l’inexis tence de fon de ments théo riques bien éta blis.
11.5 les algo rithMes géné tiques
Les algo rithmes géné tiques sont des tech niques de recherche sto chas tiques, ins pi rées
par l’évo lu tion bio lo gique des espèces. Intro duits par J.H. Holland au début des années
soixante- dix [Holl75], ils ont d’abord eu un déve lop pe ment limité, du fait de leur impor -
tant coût d’exé cu tion informatique. Ils connaissent un regain d’inté rêt (voir les pré sen
ta tions géné rales [Holl92, Gold94]), notam ment suite à l’appa ri tion des archi tec tures
mas si ve ment paral lèles, qui exploitent leur paral lé lisme intrin sèque (voir par exemple
[Coho91]).
On dis tingue deux grands domaines d’appli ca tions :
• l’opti mi sation com bi na toire : les algo rithmes géné tiques risquent moins d’être
« pié gés » dans des mini mums locaux que les algo rithmes clas siques, parce qu’ils
explorent en paral lèle un ensemble de solu tions pos sibles au pro blème posé ; en
outre, ils n’uti lisent pas les gra dients des fonc tions objec tifs. Ces carac té ris tiques les
placent en concur rence avec le recuit simulé (voir notam ment [Davi87]) ;
• l’intel li gence arti fi cielle : grâce à leur exten sion aux “sys tèmes de clas seurs”
[Holl92], les algo rithmes géné tiques servent à étu dier et à résoudre les pro blèmes
d’appren tis sage par machine.
Nous pré sen tons le prin cipe des algo rithmes géné tiques (voir Figure 11.5), dans
le seul cas de l’opti mi sation. Soit, par exemple, une fonc tion f com por tant n variables
réelles : on recherche le (ou un) point x de l’espace R
n
en lequel cette fonc tion atteint
un mini mum glo bal. Un ensemble de N points (ou “individus”), qui peuvent être choi
sis au hasard, consti tue la popu la tion ini tiale ; chaque indi vidu de la popu la tion pos
sède une cer taine com pé tence, qui mesure son degré d’adap ta tion à l’objec tif visé : ici,
x est d’autant plus com pétent que f (x) est plus petit. Un algo rithme géné tique consiste
à faire évo luer pro gres si ve ment, par géné ra tions suc ces sives, la com po si tion de cette
popu la tion, en main te nant sa taille constante : d’une géné ra tion à la sui vante, la « com
pé tence » de la popu la tion doit glo ba le ment s’amé lio rer. Un tel résul tat est obtenu en
mimant les deux prin ci paux méca nismes qui régissent l’évo lu tion des êtres vivants :
la sélec tion natu relle (qui déter mine quels membres d’une popu la tion sur vivent et se
repro duisent) et la repro duc tion (qui assure le bras sage et la re com bi nai son des gènes
paren taux, pour for mer des des cen dants aux poten tia li tés nou velles).
En pra tique, chaque indi vidu est géné ra le ment codé par une chaîne de bits de
lon gueur don née (de même qu’un chro mo some est formé d’une chaîne de gènes).
Pour fixer les idées, nous sup po sons ci- après que cette lon gueur est égale à 8. Le
pas sage d’une géné ra tion à la sui vante se déroule en deux phases : une phase de
repro duc tion et une phase de rem pla ce ment.
La phase de repro duc tion consiste à appli quer des opé ra teurs, dits géné tiques, sur
les indi vi dus de la popu la tion cou rante, pour engen drer de nou veaux indi vi dus. Les
412
simple d’emploi. Cepen dant, les divers méca nismes annexes (comme l’inten si
fi ca tion, la diver si fi ca tion et l’aspi ra tion) apportent une notable com plexité. De
plus, la méthode souffre de l’inexis tence de fon de ments théo riques bien éta blis.
11.5 les algo rithMes géné tiques
Les algo rithmes géné tiques sont des tech niques de recherche sto chas tiques, ins pi rées
par l’évo lu tion bio lo gique des espèces. Intro duits par J.H. Holland au début des années
soixante- dix [Holl75], ils ont d’abord eu un déve lop pe ment limité, du fait de leur impor -
tant coût d’exé cu tion informatique. Ils connaissent un regain d’inté rêt (voir les pré sen
ta tions géné rales [Holl92, Gold94]), notam ment suite à l’appa ri tion des archi tec tures
mas si ve ment paral lèles, qui exploitent leur paral lé lisme intrin sèque (voir par exemple
[Coho91]).
On dis tingue deux grands domaines d’appli ca tions :
• l’opti mi sation com bi na toire : les algo rithmes géné tiques risquent moins d’être
« pié gés » dans des mini mums locaux que les algo rithmes clas siques, parce qu’ils
explorent en paral lèle un ensemble de solu tions pos sibles au pro blème posé ; en
outre, ils n’uti lisent pas les gra dients des fonc tions objec tifs. Ces carac té ris tiques les
placent en concur rence avec le recuit simulé (voir notam ment [Davi87]) ;
• l’intel li gence arti fi cielle : grâce à leur exten sion aux “sys tèmes de clas seurs”
[Holl92], les algo rithmes géné tiques servent à étu dier et à résoudre les pro blèmes
d’appren tis sage par machine.
Nous pré sen tons le prin cipe des algo rithmes géné tiques (voir Figure 11.5), dans
le seul cas de l’opti mi sation. Soit, par exemple, une fonc tion f com por tant n variables
réelles : on recherche le (ou un) point x de l’espace R
n
en lequel cette fonc tion atteint
un mini mum glo bal. Un ensemble de N points (ou “individus”), qui peuvent être choi
sis au hasard, consti tue la popu la tion ini tiale ; chaque indi vidu de la popu la tion pos
sède une cer taine com pé tence, qui mesure son degré d’adap ta tion à l’objec tif visé : ici,
x est d’autant plus com pétent que f (x) est plus petit. Un algo rithme géné tique consiste
à faire évo luer pro gres si ve ment, par géné ra tions suc ces sives, la com po si tion de cette
popu la tion, en main te nant sa taille constante : d’une géné ra tion à la sui vante, la « com
pé tence » de la popu la tion doit glo ba le ment s’amé lio rer. Un tel résul tat est obtenu en
mimant les deux prin ci paux méca nismes qui régissent l’évo lu tion des êtres vivants :
la sélec tion natu relle (qui déter mine quels membres d’une popu la tion sur vivent et se
repro duisent) et la repro duc tion (qui assure le bras sage et la re com bi nai son des gènes
paren taux, pour for mer des des cen dants aux poten tia li tés nou velles).
En pra tique, chaque indi vidu est géné ra le ment codé par une chaîne de bits de
lon gueur don née (de même qu’un chro mo some est formé d’une chaîne de gènes).
Pour fixer les idées, nous sup po sons ci- après que cette lon gueur est égale à 8. Le
pas sage d’une géné ra tion à la sui vante se déroule en deux phases : une phase de
repro duc tion et une phase de rem pla ce ment.
La phase de repro duc tion consiste à appli quer des opé ra teurs, dits géné tiques, sur
les indi vi dus de la popu la tion cou rante, pour engen drer de nou veaux indi vi dus. Les