11 Méta heu ris tiques
en opti Mi sation
coM bi na toire
la Méthode du recuit
siMulé, la recherche
tabou, les algo rithMes
géné tiques et les
algo rithMes de colo nies
de four Mis
1
11.1 intro duc tion
Les ingé nieurs se heurtent quo ti dien ne ment à des pro blèmes tech no lo giques de com ­
plexité gran dis sante, qui sur gissent dans des sec teurs tech niques très divers, comme
dans la recherche opé ra tion nelle, la concep tion assis tée par ordi na teur (C.A.O.)
de sys tèmes méca niques ou élec triques, le trai te ment des images... Le pro blème
à résoudre peut fré quem ment être for mulé sous la forme géné rale d’un pro blème
d’opti mi sation, dans lequel on défi nit une fonc tion objec tif (ou fonc tion de coût),
que l’on cherche à opti mi ser par rap port à tous les para mètres concer nés. Nous nous
inté res sons dans ce chapitre à un groupe de méthodes, com pre nant notam ment la
méthode du recuit simulé, la méthode de recherche tabou, les algo rithmes géné tiques
etc., appa rues au cours des années 1980 avec une ambi tion com mune : résoudre au
mieux les pro blèmes dits d’opti­ ­ mi­ ­ sation­dif­ ­ fi­ ­ cile.
Deux sortes de pro blèmes reçoivent, dans la lit té ra ture, cette appel la tion, non
défi nie stric te ment (et liée, en fait, à l’état de l’art en matière d’opti mi sation) :
– cer tains pro blèmes d’opti mi sation com bi na toire (donc à variables discrètes), pour les ­
quels on ne connaît pas d’algo rithme optimal rapide (c’est le cas, en par ti cu lier, des
pro blèmes NP­ difficiles) ;
1. Cha pitre rédigé par M. Patrick SIARRY, Pro fes seur à l’Uni ver sité de Paris­12 ,Val de Marne.