Optimisation du transport du gaz par canalisation.

4.4.4 Principe de RS :

Le principe du recuit simulé est de parcourir de manière itérative l'espace des solutions, on part d'une solution notée x initialement générée d'une manière aléatoire ( ou trouvée à l'aide d'une autre méthode approchée) qui correspond à une énergie initiale Z(x) et une température initiale o⁰, généralement élevée.

-AZ

o .

À chaque itération de l'algorithme un changement s'effectue sur la solution. Cette solution x^' fait varier l'énergie du système, AZ = Z(x^') - Z(x) si cette variation est négative ( la nouvelle solution améliore la fonction objectif) et permet de diminuer l'énergie du système, elle est acceptée. Si la solution trouvée est moins bonne que la précédente alors elle sera acceptée avec une probabilité calculée suivant y = e

En fonction du critère de Métropolis, un nombre p E [0,1] est comparé à la probabilité

y = e

-AZ o . Si y ~ p la nouvelle solution est acceptée.

Le fonctionnement de critère de Métropolis est interprété par:

- Si AZ = Z(x^') - Z(x) < 0, alors e-AZ

o > 1, donc p est toujours inférieure à cette valeur est

'

on accepte la solution x.

-AZ

- Si AZ > 0, alors eo ' 1, tout voisin est systématiquement acceptée.

- Si AZ > 0 et o <<<, alors e

-AZ o 0, une dégradation à peu de chance d'être accepté.

71

4.4. LE RECUIT SIMULÉ

4.4.5 Algorithme général du Recuit simulé

Algorithm 1 Recuit Simulé

ENTRéES: x := x⁰ ; Z = Z(x); xop := x ; Z(x_op); è := è⁰ ; n_r ; èf ; á

Début

tantque è > èf faire

tantque nb ~ n_r faire

x' := ô(x) ;

Z(x');

ÄZ = Z(x')-Z(x);

si ÄZ < 0 alors

x := x' ;

Z(x) := Z(x');

si Z(x') < Z(x_op) alors

xop := x' ;

Z(x_op) := Z(x'); finsi

sinon p E [0,1];

-ÄZ

y := eè ;

si p ~ y alors

x := x' ;

Z(x) := Z(x');

finsi

finsi

nb := nb +1;

fin tantque

è := á.è ;

fin tantque

Fin

72

4.5. LES ALGORITHMES GÉNÉTIQUES