11.2 La tâche impar tie aux méta heu ris tiques
403
© Dunod – Toute reproduction non autorisée est un délit.
En pra tique, le but d’un indus triel n’est pas d’obte nir nécessairement ce mini
mum absolu, mais seule ment une bonne solu tion et l’assu rance qu’il n’existe pas de
solu tion sen si ble ment meilleure. Pour atteindre ce but en un temps de cal cul rai son
nable, il est néces saire d’avoir recours à des méthodes sto chas tiques, c’est àdire à
des méthodes qui, face à l’impos si bi lité d’explo rer la tota lité des confi gu ra tions du
sys tème, per mettent d’évo luer vers une solu tion en pas sant par un nombre limité de
confi gu ra tions, le par cours étant guidé, en par tie, par le hasard.
11.2.2 Pié geage de l’algo rithme ité ra tif « clas sique »
dans un mini mum local
Un algo rithme clas sique est celui de l’« amé lio ra tion ité ra tive », dont le prin cipe est le
sui vant : on part d’une confi gu ra tion ini tiale c 0 , qui peut être choi sie au hasard, ou bien
– par exemple dans le cas du pla ce ment et du rou tage d’un cir cuit élec tro nique – qui
peut être celle d’un concep teur. On essaie alors une modi fi ca tion élé men taire, sou vent
appe lée « mou ve ment » (par exemple, on per mute deux com po sants choi sis au hasard,
ou bien on trans late l’un d’entre eux), et l’on com pare les valeurs de la fonc tion de
coût, avant et après cette modi fi ca tion. Si le chan ge ment conduit à une dimi nu tion de la
fonc tion de coût, il est accepté, et la confi gu ra tion obte nue, qui est « voi sine » de la pré
cé dente, sert de point de départ pour un nou vel essai. Dans le cas contraire, on revient
à la confi gu ra tion pré cé dente, avant de faire une autre ten ta tive. Le pro ces sus est itéré
jus qu’à ce que toute modi fi ca tion rende le résul tat moins bon. La Figure 11.1 montre
que cet algo rithme d’amé lio ra tion ité ra tive (dési gné aussi sous les termes de méthode
clas sique, ou méthode de des cente, ou méthode de la plus grande pente) ne conduit
pas, en géné ral, au mini mum absolu, mais seule ment à un mini mum local (cf les points
gras), qui consti tue la meilleure des solu tions acces sibles compte tenu de l’hypo thèse
ini tiale : partant de c 0 , on aboutit seulement au minimum local c n .
Pour amé lio rer l’effi ca cité de la méthode, on peut évi dem ment l’appli quer plu -
sieurs fois, avec des condi tions ini tiales dif fé rentes choi sies arbi trai re ment, et rete nir
comme solu tion finale le meilleur des mini mums locaux obte nus ; cepen dant, cette
pro cé dure aug mente sen si ble ment le temps de cal cul de l’algo rithme, et ne garan tit
pas de trou ver la confi gu ra tion opti male c*.
11.2.3 Capa cité des méta heu ris tiques à s’extraire
d’un mini mum local
Pour sur mon ter l’obs tacle des mini mums locaux, une autre idée s’est mon trée très
fruc tueuse, au point qu’elle est à la base de toutes les méta heu ris tiques dites de voi
si nage (recuit simulé, méthode tabou) : il s’agit d’auto ri ser, de temps en temps, des
mou ve ments de remon tée, autre ment dit d’accep ter une dégra da tion tem po raire de la
situa tion, lors du chan ge ment de la confi gu ra tion cou rante. C’est le cas si l’on passe
de c n à cr n (Figure 11.1). Un méca nisme de contrôle des dégra da tions – spé ci fique à
chaque méta heu ris tique – per met d’évi ter la non convergence du pro cédé. Il devient,
dès lors, pos sible de s’extraire du piège que repré sente un mini mum local, pour par tir
explo rer une autre « val lée » plus pro met teuse… Ici, repartant de cr n , on aboutirait à
c* (qui, par chance, se trouve être le minimum absolu de f(c).
403
© Dunod – Toute reproduction non autorisée est un délit.
En pra tique, le but d’un indus triel n’est pas d’obte nir nécessairement ce mini
mum absolu, mais seule ment une bonne solu tion et l’assu rance qu’il n’existe pas de
solu tion sen si ble ment meilleure. Pour atteindre ce but en un temps de cal cul rai son
nable, il est néces saire d’avoir recours à des méthodes sto chas tiques, c’est àdire à
des méthodes qui, face à l’impos si bi lité d’explo rer la tota lité des confi gu ra tions du
sys tème, per mettent d’évo luer vers une solu tion en pas sant par un nombre limité de
confi gu ra tions, le par cours étant guidé, en par tie, par le hasard.
11.2.2 Pié geage de l’algo rithme ité ra tif « clas sique »
dans un mini mum local
Un algo rithme clas sique est celui de l’« amé lio ra tion ité ra tive », dont le prin cipe est le
sui vant : on part d’une confi gu ra tion ini tiale c 0 , qui peut être choi sie au hasard, ou bien
– par exemple dans le cas du pla ce ment et du rou tage d’un cir cuit élec tro nique – qui
peut être celle d’un concep teur. On essaie alors une modi fi ca tion élé men taire, sou vent
appe lée « mou ve ment » (par exemple, on per mute deux com po sants choi sis au hasard,
ou bien on trans late l’un d’entre eux), et l’on com pare les valeurs de la fonc tion de
coût, avant et après cette modi fi ca tion. Si le chan ge ment conduit à une dimi nu tion de la
fonc tion de coût, il est accepté, et la confi gu ra tion obte nue, qui est « voi sine » de la pré
cé dente, sert de point de départ pour un nou vel essai. Dans le cas contraire, on revient
à la confi gu ra tion pré cé dente, avant de faire une autre ten ta tive. Le pro ces sus est itéré
jus qu’à ce que toute modi fi ca tion rende le résul tat moins bon. La Figure 11.1 montre
que cet algo rithme d’amé lio ra tion ité ra tive (dési gné aussi sous les termes de méthode
clas sique, ou méthode de des cente, ou méthode de la plus grande pente) ne conduit
pas, en géné ral, au mini mum absolu, mais seule ment à un mini mum local (cf les points
gras), qui consti tue la meilleure des solu tions acces sibles compte tenu de l’hypo thèse
ini tiale : partant de c 0 , on aboutit seulement au minimum local c n .
Pour amé lio rer l’effi ca cité de la méthode, on peut évi dem ment l’appli quer plu -
sieurs fois, avec des condi tions ini tiales dif fé rentes choi sies arbi trai re ment, et rete nir
comme solu tion finale le meilleur des mini mums locaux obte nus ; cepen dant, cette
pro cé dure aug mente sen si ble ment le temps de cal cul de l’algo rithme, et ne garan tit
pas de trou ver la confi gu ra tion opti male c*.
11.2.3 Capa cité des méta heu ris tiques à s’extraire
d’un mini mum local
Pour sur mon ter l’obs tacle des mini mums locaux, une autre idée s’est mon trée très
fruc tueuse, au point qu’elle est à la base de toutes les méta heu ris tiques dites de voi
si nage (recuit simulé, méthode tabou) : il s’agit d’auto ri ser, de temps en temps, des
mou ve ments de remon tée, autre ment dit d’accep ter une dégra da tion tem po raire de la
situa tion, lors du chan ge ment de la confi gu ra tion cou rante. C’est le cas si l’on passe
de c n à cr n (Figure 11.1). Un méca nisme de contrôle des dégra da tions – spé ci fique à
chaque méta heu ris tique – per met d’évi ter la non convergence du pro cédé. Il devient,
dès lors, pos sible de s’extraire du piège que repré sente un mini mum local, pour par tir
explo rer une autre « val lée » plus pro met teuse… Ici, repartant de cr n , on aboutirait à
c* (qui, par chance, se trouve être le minimum absolu de f(c).