3.2.2.2 Dégradation de la température
La construction d'un schéma de refroidissement qui
garantisse une dégradation équilibrée et adéquate
du paramètre de contrôle T sur les 2000 itérations
prévues repose essentiellement sur le coefficient de dégradation
(coefficient À de Boltzmann), mais avant de fixer ce
coefficient on doit choisir le mode de dégradation qu'on adoptera.
En effet, le mode de dégradation de la
température est en relation directe avec le nombre de fois qu'on doit
vérifier le critère de Metropolis, on va donc estimer la
probabilitépour que la différence ?f soit positive, les
calculs ont étéfait sur 20 instances avec 2000 itérations
pour chaque instance (voir Tableaux 3.9 et 3.10).
Résultats expérimentaux 54
Tableau 3.9 - Probabilitépour ?f = 0 en
pourcentage sur 2000 itérations
|
n = 20
|
n = 50
|
n = 100
|
n = 150
|
|
moyenne
|
u
|
moyenne
|
u
|
moyenne
|
u
|
moyenne
|
u
|
|
F1
|
87.45
|
21.39
|
94.2
|
40.14
|
97.1
|
63.23
|
97.90
|
67.69
|
|
F2
|
86.80
|
11.59
|
93.8
|
33.89
|
96.85
|
44.98
|
97.9
|
66.62
|
|
F3
|
74.5
|
11.88
|
78.1
|
3.53
|
80.7
|
9.6
|
80.45
|
6.24
|
|
F4
|
81.10
|
18.46
|
88.05
|
4.11
|
92.6
|
17.17
|
94.45
|
12.81
|
|
F5
|
85.05
|
17.15
|
92.7
|
25.61
|
96.2
|
33.88
|
97.3
|
62.63
|
Tableau 3.10 - Résume du tableau 3.9
|
n
|
20
|
50
|
100
|
150
|
|
F1
|
90 %
|
95 %
|
97%
|
97%
|
|
F2
|
90%
|
95%
|
97%
|
97%
|
|
F3
|
80%
|
80 %
|
80%
|
80%
|
|
F4
|
90%
|
90 %
|
97%
|
95%
|
|
F5
|
90%
|
93 %
|
93%
|
97%
|
Le tableau 3.10 nous renseigne sur le pourcentage pour lequel
?f soit supérieur à zéro, autrement dit, au bout
de 2000 itérations, combien de fois peut-on calculer le rapport
?! T ? Le Tableau 3.11 illustre la réponse.
Tableau 3.11 - Nombre de vérifications du
critère de Metropolis sur 2000 itérations
|
n
|
20
|
50
|
100
|
150
|
|
F1
|
1800
|
120
|
1940
|
1940
|
|
F2
|
1800
|
160
|
1940
|
1940
|
|
F3
|
1600
|
1600
|
1600
|
1600
|
|
F4
|
1800
|
1800
|
1940
|
1900
|
|
F5
|
1800
|
1860
|
1860
|
1940
|
On remarque que la probabilitépour que ?f soit
positive est très importante, dans ce cas, on doit imposer un mode de
dégradation par palier, c'est à dire qu'on va «refroidir le
système» toutes les 20 itérations et cela au cours des 200
premières itérations de façon de garantir que le
début de recherche assure une importante exploration de l'espace de
recherche, ensuite on va dégrader la température au cours des
1800 dernières itérations de façon
Résultats expérimentaux 55
À2 = ( Tfinal)
Tinitial
1
89
de diminuer la probabilitéd'acceptation afin d'assurer
l'intensification de la recherche. Pour cela, la
probabilitéd'acceptation x sera établie comme suit :
f
[0.4, 0, 9] V 1 iteration
200
x E [0.1, 0.4] V 201
iteration 2000
La question qui se pose désormais, c'est comment
va-t-on dégrader la température?
ou encore, quelle est la valeur de À à
fixer? Pour répondre à cette question, on doit calculer les
valeurs finales de la température qui assurent une
proba-bilitéd'acceptation x appartenant à une plage
donnée de valeur, reprenant l'équation suivante :
Tfinale =
-~f Ln(0.1)
Le Tableau 3.12 illustre les valeurs finales approchées de
la températures pour les cinq familles d'instance :
Tableau 3.12 - Valeurs finales de T pour les cinq
familles d'instances
|
Températures finales
|
|
Familles
|
x E [0.4,0,9]
|
x E [0.1,0,4]
|
|
F1
|
8.73
|
3.47
|
|
F2
|
34.92
|
13.89
|
|
F3
|
91.67
|
36.48
|
|
F4
|
43.65
|
17.37
|
|
F5
|
7.63
|
3.04
|
Si pour les 200 premières itérations, on
dégrade la température toutes les 20 itérations alors on
va dégrader 9 fois, le coefficient de dégradation s'écrit
donc comme suit :
|
À1 = ( Tfinal)
Tinitial
|
1
9
|
Pour les 1800 dernières itérations, on va appliquer
89 dégradations d'oùÀ s'écrit comme suit
:
Résultats expérimentaux 56
FIGURE 3.6 - Dégradation de T
pour la famille F3, 1800 dernières itérations
A` titre d'exemple, calculons les deux valeurs de A pour
la famille F3 :
?
?
?
A =
1
(91.67 8356
)9 ? 0.60 V 1 < iteration <
200
1
(36.48
91.67) 89 ?
0.989 V 201 < iteration < 2000
Finalement, et en faisant les mêmes calculs pour toutes les
familles d'ins-tance, on a choisit les valeurs A1 =
0.60 pour i E [1, 200] et A2
= 0.989 pour i E [201, 2000].
A ` titre de confirmation, les figures 3.5 et 3.6 illustrent
cette dégradation pour
la famille F3, et la figure 3.7 page suivante
décrit l'évolution de la probabilitéd'acceptation d'une
solution voisine toujours pour la famille F3.
FIGURE 3.5 - Dégradation de T
pour la famille F3, 2000 itérations
Résultats expérimentaux 57
FIGURE 3.7 - Probabilitéd'acceptation pour la famille
F3 3.2.2.3 Critère d'arrêt
Le Recuit Simulés'arrête après un nombre
d'itération de 2000 ou si la procédure tient une solution dont le
makespan est égale à la borne inférieure.
Résultats expérimentaux 58
| 
