11.4 La recherche tabou
411
© Dunod – Toute reproduction non autorisée est un délit.
l’une ou l’autre des com po santes de base de Tabou ont été pro po sés : par exemple,
une ges tion dyna mique de la taille de la liste tabou, ou de la taille du voi si nage de la
solu tion cou rante. Mal heu reu se ment, la plu part des variantes publiées reposent sur
une ana lyse empi rique spé ci fique au pro blème par ti cu lier traité : une amé lio ra tion
signi fi ca tive de l’effi ca cité se paye par une perte de géné ra lité de la démarche.
Pour un exposé com plet et très détaillé de la méthode, nous ren voyons le lec teur à
l’ouvrage récent de F. Glover et M. Laguna [Glov97]. Des pré sen ta tions didac tiques
de Tabou figurent dans les articles [Pirl92, Sori97] et dans le cha pitre 3 de l’ouvrage
[Reev95].
Figure 11.4 Orga ni gramme de l’algo rithme Tabou simple.
En résumé. Pour cer tains pro blèmes d’opti mi sation com bi na toire, comme des
pro blèmes de colo riage de graphes ou d’emploi du temps, Tabou a donné d’excel
lents résul tats. En outre, sous sa forme élé men taire (« Tabou simple »), la méthode
com porte moins de para mètres de réglage que le recuit simulé, ce qui la rend plus
411
© Dunod – Toute reproduction non autorisée est un délit.
l’une ou l’autre des com po santes de base de Tabou ont été pro po sés : par exemple,
une ges tion dyna mique de la taille de la liste tabou, ou de la taille du voi si nage de la
solu tion cou rante. Mal heu reu se ment, la plu part des variantes publiées reposent sur
une ana lyse empi rique spé ci fique au pro blème par ti cu lier traité : une amé lio ra tion
signi fi ca tive de l’effi ca cité se paye par une perte de géné ra lité de la démarche.
Pour un exposé com plet et très détaillé de la méthode, nous ren voyons le lec teur à
l’ouvrage récent de F. Glover et M. Laguna [Glov97]. Des pré sen ta tions didac tiques
de Tabou figurent dans les articles [Pirl92, Sori97] et dans le cha pitre 3 de l’ouvrage
[Reev95].
Figure 11.4 Orga ni gramme de l’algo rithme Tabou simple.
En résumé. Pour cer tains pro blèmes d’opti mi sation com bi na toire, comme des
pro blèmes de colo riage de graphes ou d’emploi du temps, Tabou a donné d’excel
lents résul tats. En outre, sous sa forme élé men taire (« Tabou simple »), la méthode
com porte moins de para mètres de réglage que le recuit simulé, ce qui la rend plus