11.2 La tâche impar tie aux méta heu ris tiques
401
© Dunod – Toute reproduction non autorisée est un délit.
– cer tains pro blèmes d’opti mi sation à variables conti nues, pour les quels on ne
connaît pas d’algo rithme per met tant de repérer un opti mum glo bal à coup sûr
et en un nombre fini de cal culs. Ce cas est moins fré quent que le pré cé dent en
recherche opé ra tion nelle.
Un grand nombre d’algorithmes approchés ou : « heu ris tiques », qui pro duisent des
solu tions proches de l’opti mum, ont été déve lop pées, his to ri que ment, d’abord pour les
pro blèmes d’opti mi sation com bi na toire dif fi cile. La plu part d’entre elles sont conçues
spé ci fi que ment pour un type de pro blème donné. D’autres, au contraire, appe lées méta
heu ris tiques, s’adaptent à dif fé rents types de pro blèmes com bi na toires (ou même conti
nus). Le recuit simulé et les autres méthodes récentes énu mé rées plus haut sont des méta
heu ris tiques. Ces méthodes ont en com mun, en outre, les carac té ris tiques sui vantes :
• elles sont, au moins pour par tie, sto chas tiques : cette approche per met de faire face
à l’explo sion com bi na toire des pos si bi li tés ;
• du fait de leur ori gine com bi na toire, elles ne peuvent s’appli quer aux pro blèmes
conti nus qu’après adap ta tion (plus ou moins aisée…) ; en rai son de cette ori gine,
elles ont l’avan tage, déci sif dans le cas continu, d’être directes, c’est àdire qu’elles
ne recourent pas au cal cul des gra dients de la fonc tion objec tif ;
• elles sont ins pi rées par des ana lo gies : avec la phy sique (recuit simulé...), avec la
bio lo gie (recherche tabou, algo rithmes géné tiques, réseaux de neu rones...) ou avec
l’étho lo gie (algo rithmes de colo nies de four mis…).
Ces méthodes ne s’excluent pas mutuel le ment : en effet, dans l’état actuel de la
recherche, il est le plus sou vent impos sible de pré voir avec cer ti tude l’effi ca cité d’une
méthode don née plutôt qu’une autre, quand elle est appli quée à un pro blème donné. De
plus, la ten dance actuelle est l’émer gence de méthodes hybrides [Rend96], qui s’efforcent
de tirer parti des avan tages spé ci fiques de deux approches dif fé rentes en les com bi nant.
11.2 la tâche iMpar tie aux Méta heu ris tiques
Un pro blème d’opti mi sation peut être exprimé sous la forme géné rale sui vante :
Minimi ser f(x)
sous les contraintes :
g i ( x) > b i
i 5 1, c, m
h i ( x) 5 c j
j 5 1, c, n
où x désigne un vec teur regrou pant les « variables de déci sion », et f, g i et h j expriment
res pec ti ve ment la fonc tion objec tif, les contraintes en inéga lité et les contraintes en
éga lité. L’opti mi sation com bi na toire concerne le cas où les variables de déci sion sont
dis crètes, c’est àdire où chaque solu tion est un ensemble ou bien une suite d’entiers.
En pra tique, le nombre N de « degrés de liberté » (i.e. les variables de déci sion) peut
être élevé, et la fonc tion f doit prendre en consi dé ra tion de nom breux objec tifs sou vent
plus ou moins contra dic toires. Pour illus trer cette idée par un exemple concret, nous
nous inté res sons au pro blème du « pla ce ment » et du « rou tage » des cir cuits élec tro
niques, défini ci- dessous et traité plus loin par la méthode du recuit simulé.
401
© Dunod – Toute reproduction non autorisée est un délit.
– cer tains pro blèmes d’opti mi sation à variables conti nues, pour les quels on ne
connaît pas d’algo rithme per met tant de repérer un opti mum glo bal à coup sûr
et en un nombre fini de cal culs. Ce cas est moins fré quent que le pré cé dent en
recherche opé ra tion nelle.
Un grand nombre d’algorithmes approchés ou : « heu ris tiques », qui pro duisent des
solu tions proches de l’opti mum, ont été déve lop pées, his to ri que ment, d’abord pour les
pro blèmes d’opti mi sation com bi na toire dif fi cile. La plu part d’entre elles sont conçues
spé ci fi que ment pour un type de pro blème donné. D’autres, au contraire, appe lées méta
heu ris tiques, s’adaptent à dif fé rents types de pro blèmes com bi na toires (ou même conti
nus). Le recuit simulé et les autres méthodes récentes énu mé rées plus haut sont des méta
heu ris tiques. Ces méthodes ont en com mun, en outre, les carac té ris tiques sui vantes :
• elles sont, au moins pour par tie, sto chas tiques : cette approche per met de faire face
à l’explo sion com bi na toire des pos si bi li tés ;
• du fait de leur ori gine com bi na toire, elles ne peuvent s’appli quer aux pro blèmes
conti nus qu’après adap ta tion (plus ou moins aisée…) ; en rai son de cette ori gine,
elles ont l’avan tage, déci sif dans le cas continu, d’être directes, c’est àdire qu’elles
ne recourent pas au cal cul des gra dients de la fonc tion objec tif ;
• elles sont ins pi rées par des ana lo gies : avec la phy sique (recuit simulé...), avec la
bio lo gie (recherche tabou, algo rithmes géné tiques, réseaux de neu rones...) ou avec
l’étho lo gie (algo rithmes de colo nies de four mis…).
Ces méthodes ne s’excluent pas mutuel le ment : en effet, dans l’état actuel de la
recherche, il est le plus sou vent impos sible de pré voir avec cer ti tude l’effi ca cité d’une
méthode don née plutôt qu’une autre, quand elle est appli quée à un pro blème donné. De
plus, la ten dance actuelle est l’émer gence de méthodes hybrides [Rend96], qui s’efforcent
de tirer parti des avan tages spé ci fiques de deux approches dif fé rentes en les com bi nant.
11.2 la tâche iMpar tie aux Méta heu ris tiques
Un pro blème d’opti mi sation peut être exprimé sous la forme géné rale sui vante :
Minimi ser f(x)
sous les contraintes :
g i ( x) > b i
i 5 1, c, m
h i ( x) 5 c j
j 5 1, c, n
où x désigne un vec teur regrou pant les « variables de déci sion », et f, g i et h j expriment
res pec ti ve ment la fonc tion objec tif, les contraintes en inéga lité et les contraintes en
éga lité. L’opti mi sation com bi na toire concerne le cas où les variables de déci sion sont
dis crètes, c’est àdire où chaque solu tion est un ensemble ou bien une suite d’entiers.
En pra tique, le nombre N de « degrés de liberté » (i.e. les variables de déci sion) peut
être élevé, et la fonc tion f doit prendre en consi dé ra tion de nom breux objec tifs sou vent
plus ou moins contra dic toires. Pour illus trer cette idée par un exemple concret, nous
nous inté res sons au pro blème du « pla ce ment » et du « rou tage » des cir cuits élec tro
niques, défini ci- dessous et traité plus loin par la méthode du recuit simulé.