Chapitre 11 • Métaheuristiques en optimisation combinatoire
402
11.2.1 Exemple de pro blème d’opti mi sation :
le pro blème du placement- routage
La concep tion d’un cir cuit élec tro nique, quelle que soit la tech no lo gie uti li sée, se
ter mine tou jours par l’étape de « pla ce ment », dans laquelle les com po sants choi sis
doivent être dis po sés dans un plan, et de « rou tage », dans laquelle ces com po sants
doivent être reliés entre eux par des conduc teurs. Lorsque le nombre de com po sants
du cir cuit est grand, il s’agit là d’un pro blème d’opti mi sation com bi na toire qui peut
être très com plexe. En effet, le des sin du cir cuit doit répondre à plu sieurs impé ra tifs :
d’une part, les connexions doivent être aussi courtes que pos sible, ceci pour réduire
les temps de tran sit des signaux, et pour des rai sons de fia bi lité et de « lisi bilité » du
cir cuit (néces saire notam ment en cas de dépan nage). D’autre part, les connexions
entre les com po sants se font par des che mins conduc teurs (par dépôt de métal ou par
gra vure dans le sili cium) situés dans plu sieurs plans super po sés. Le pas sage d’un
niveau à un autre néces site un trou conduc teur, qui consti tue poten tiel le ment un point
faible pour le cir cuit : on cherche donc à minimi ser le nombre de trous conduc teurs,
en minimi sant le nombre de croi se ments entre les connexions. Le pro blème de la
concep tion du cir cuit se ramène ainsi à la recherche d’un com pro mis entre plu sieurs
exi gences contra dic toires. À cet effet, on minimise une fonc tion objec tif, obte nue
en ras sem blant les gran deurs carac té ris tiques du pro blème dans une fonc tion nelle
(par exemple une com bi nai son linéaire de ces grandeurs) ; dans celle ci, on affecte à
chaque gran deur un poids qui reflète le degré de priorité que le concep teur lui attri -
bue. En outre, la solu tion recherc hée doit res pec ter des contraintes ; par exemple :
la forme et la sur face de la place dis po nible pour l’ensemble des com po sants et
des connexions sont sou vent impo sées. Pour des rai sons de com mo dité, cer taines
contraintes sont incor po rées dans la fonc tion objec tif ; d’autres consti tuent une limi
ta tion des degrés de liberté du pro blème. L’allure d’une telle fonc tion objec tif est le
plus sou vent non convexe, du type de celle repré sen tée en Figure 11.1 :
Figure 11.1 Allure de la fonc tion objec tif d’un pro blème com plexe
en fonc tion de la confi gu ra tion du sys tème.
Lorsque l’espace de toutes les confi gu ra tions pos sibles pré sente une struc ture aussi
tour men tée, il est dif fi cile de repérer le mini mum glo bal c* de la fonction objectif : la
recherche de celui ci risque fort d’être un pro blème NP- difficile, c’est- à-dire – sché -
ma ti que ment – dont la réso lu tion exacte n’est pas pos sible en un temps poly no mial
qui serait pro por tion nel à N
n
(où n désigne un entier), plus exactement : en O (N
n
).
402
11.2.1 Exemple de pro blème d’opti mi sation :
le pro blème du placement- routage
La concep tion d’un cir cuit élec tro nique, quelle que soit la tech no lo gie uti li sée, se
ter mine tou jours par l’étape de « pla ce ment », dans laquelle les com po sants choi sis
doivent être dis po sés dans un plan, et de « rou tage », dans laquelle ces com po sants
doivent être reliés entre eux par des conduc teurs. Lorsque le nombre de com po sants
du cir cuit est grand, il s’agit là d’un pro blème d’opti mi sation com bi na toire qui peut
être très com plexe. En effet, le des sin du cir cuit doit répondre à plu sieurs impé ra tifs :
d’une part, les connexions doivent être aussi courtes que pos sible, ceci pour réduire
les temps de tran sit des signaux, et pour des rai sons de fia bi lité et de « lisi bilité » du
cir cuit (néces saire notam ment en cas de dépan nage). D’autre part, les connexions
entre les com po sants se font par des che mins conduc teurs (par dépôt de métal ou par
gra vure dans le sili cium) situés dans plu sieurs plans super po sés. Le pas sage d’un
niveau à un autre néces site un trou conduc teur, qui consti tue poten tiel le ment un point
faible pour le cir cuit : on cherche donc à minimi ser le nombre de trous conduc teurs,
en minimi sant le nombre de croi se ments entre les connexions. Le pro blème de la
concep tion du cir cuit se ramène ainsi à la recherche d’un com pro mis entre plu sieurs
exi gences contra dic toires. À cet effet, on minimise une fonc tion objec tif, obte nue
en ras sem blant les gran deurs carac té ris tiques du pro blème dans une fonc tion nelle
(par exemple une com bi nai son linéaire de ces grandeurs) ; dans celle ci, on affecte à
chaque gran deur un poids qui reflète le degré de priorité que le concep teur lui attri -
bue. En outre, la solu tion recherc hée doit res pec ter des contraintes ; par exemple :
la forme et la sur face de la place dis po nible pour l’ensemble des com po sants et
des connexions sont sou vent impo sées. Pour des rai sons de com mo dité, cer taines
contraintes sont incor po rées dans la fonc tion objec tif ; d’autres consti tuent une limi
ta tion des degrés de liberté du pro blème. L’allure d’une telle fonc tion objec tif est le
plus sou vent non convexe, du type de celle repré sen tée en Figure 11.1 :
Figure 11.1 Allure de la fonc tion objec tif d’un pro blème com plexe
en fonc tion de la confi gu ra tion du sys tème.
Lorsque l’espace de toutes les confi gu ra tions pos sibles pré sente une struc ture aussi
tour men tée, il est dif fi cile de repérer le mini mum glo bal c* de la fonction objectif : la
recherche de celui ci risque fort d’être un pro blème NP- difficile, c’est- à-dire – sché -
ma ti que ment – dont la réso lu tion exacte n’est pas pos sible en un temps poly no mial
qui serait pro por tion nel à N
n
(où n désigne un entier), plus exactement : en O (N
n
).