11.7 Les méthodes hybrides
417
© Dunod – Toute reproduction non autorisée est un délit.
En s’ins pi rant de la modé li sa tion de ce com por te ment, Dorigo et al. ont pro posé
un nou vel algo rithme pour la réso lu tion du célèbre pro blème du voya geur de com
merce. Depuis ces tra vaux, la démarche a été éten due à beau coup d’autres pro blèmes
d’opti mi sation, com bi na toires ou mêmes conti nus.
En résumé. Les algo rithmes de colo nies de four mis pos sèdent plu sieurs carac
té ris tiques inté res santes ; men tion nons notam ment le paral lé lisme intrin sèque
élevé, la flexi bi lité (une colo nie de four mis est capable de s’adap ter à des modi
fi ca tions de l’envi ron ne ment), la robus tesse (une colo nie est apte à main te nir
son acti vité, même si quelques indi vi dus sont défaillants), la décen tra li sa
tion (une colo nie n’obéit pas à une auto rité cen tra li sée) et l’auto organisation
(une colo nie trouve d’elle même une solu tion, qui n’est pas connue à
l’avance). Cette démarche paraît de ce fait par ti cu liè re ment indi quée pour les
pro blèmes dis tri bués par nature, sus cep tibles d’évo lu tion dyna mique, ou qui
requièrent une forte tolé rance aux pannes. À ce stade de déve lop pe ment de
ces algo rithmes récents, la trans po si tion à chaque pro blème d’opti mi sation ne
va cepen dant pas de soi : elle doit faire l’objet d’un trai te ment spé ci fique, plus
ou moins ardu…
11.7 les Méthodes hybrides
Le suc cès rapide des méta heu ris tiques est dû aux dif fi cul tés ren contrées par les
méthodes clas siques d’opti mi sation dans les pro blèmes d’ingé nie rie com plexes.
Après le triom pha lisme des débuts des tenants de telle ou telle méta heu ris tique,
l’heure est venue de faire un bilan réa liste et d’accep ter la com plé men ta rité de ces
nou velles méthodes entre elles, ainsi qu’avec d’autres approches : d’où l’émer gence
actuelle de méthodes hybrides [Rend96].
RéFé Rences
[Cern85] V. Cerny, “Thermodynamical approach to the tra ve ling salesman problem : an effi -
cient simu la tion algorithm”, J. of Optimization Theory and Appli ca tions, Vol. 45, N° 1,
p. 4151, 1985.
[Coho91] J.P. Cohoon, S.U. Hegde, W.N. Martin, D.S. Richards, “Distributed genetic
algorithms for the floorplan design problem”, IEEE Trans. on CAD, Vol. 10, N° 4, p. 483492, April 1991.
[Coll88] N.E. Collins, R.W. Eglese, B.L. Gol den, “Simulated annealing – An annotated
bibliography”, American Jour nal of Mathematical and Mana ge ment Sciences, Vol. 8,
p. 209-307, 1988.
[Davi87] L. Davis (Ed.), “Genetic algorithms and simulated annealing”, London : Pitman,
1987.
417
© Dunod – Toute reproduction non autorisée est un délit.
En s’ins pi rant de la modé li sa tion de ce com por te ment, Dorigo et al. ont pro posé
un nou vel algo rithme pour la réso lu tion du célèbre pro blème du voya geur de com
merce. Depuis ces tra vaux, la démarche a été éten due à beau coup d’autres pro blèmes
d’opti mi sation, com bi na toires ou mêmes conti nus.
En résumé. Les algo rithmes de colo nies de four mis pos sèdent plu sieurs carac
té ris tiques inté res santes ; men tion nons notam ment le paral lé lisme intrin sèque
élevé, la flexi bi lité (une colo nie de four mis est capable de s’adap ter à des modi
fi ca tions de l’envi ron ne ment), la robus tesse (une colo nie est apte à main te nir
son acti vité, même si quelques indi vi dus sont défaillants), la décen tra li sa
tion (une colo nie n’obéit pas à une auto rité cen tra li sée) et l’auto organisation
(une colo nie trouve d’elle même une solu tion, qui n’est pas connue à
l’avance). Cette démarche paraît de ce fait par ti cu liè re ment indi quée pour les
pro blèmes dis tri bués par nature, sus cep tibles d’évo lu tion dyna mique, ou qui
requièrent une forte tolé rance aux pannes. À ce stade de déve lop pe ment de
ces algo rithmes récents, la trans po si tion à chaque pro blème d’opti mi sation ne
va cepen dant pas de soi : elle doit faire l’objet d’un trai te ment spé ci fique, plus
ou moins ardu…
11.7 les Méthodes hybrides
Le suc cès rapide des méta heu ris tiques est dû aux dif fi cul tés ren contrées par les
méthodes clas siques d’opti mi sation dans les pro blèmes d’ingé nie rie com plexes.
Après le triom pha lisme des débuts des tenants de telle ou telle méta heu ris tique,
l’heure est venue de faire un bilan réa liste et d’accep ter la com plé men ta rité de ces
nou velles méthodes entre elles, ainsi qu’avec d’autres approches : d’où l’émer gence
actuelle de méthodes hybrides [Rend96].
RéFé Rences
[Cern85] V. Cerny, “Thermodynamical approach to the tra ve ling salesman problem : an effi -
cient simu la tion algorithm”, J. of Optimization Theory and Appli ca tions, Vol. 45, N° 1,
p. 4151, 1985.
[Coho91] J.P. Cohoon, S.U. Hegde, W.N. Martin, D.S. Richards, “Distributed genetic
algorithms for the floorplan design problem”, IEEE Trans. on CAD, Vol. 10, N° 4, p. 483492, April 1991.
[Coll88] N.E. Collins, R.W. Eglese, B.L. Gol den, “Simulated annealing – An annotated
bibliography”, American Jour nal of Mathematical and Mana ge ment Sciences, Vol. 8,
p. 209-307, 1988.
[Davi87] L. Davis (Ed.), “Genetic algorithms and simulated annealing”, London : Pitman,
1987.