3.2.1.3 Critères d'arrêt
Pour les procédure unitaires de la recherche taboue on
a fait le choix d'arrêter le processus après un nombre
d'itération choisit de manière à permettre à la
procédure de faire au moins cinq aspiration ou d'avoir une bonne
solution.
Pour la procédure RTG on a établie un
double critère d'arrêt expliquépar l'Algorithme 3.2.
Algorithme 3.2: Critères d'arrêt
pour RTG
Initialiser Taux;
i ? 0;
tant que (i = 5) Et (Taux =
1%) faire
Exécuter RTG
Calculer Taux d'amélioration
i ? i + 1;
Toutes les méta-heuristiques s'arrêtent
automatiquement si elles tiennent un makespan égale à la borne
inférieur.
Résultats expérimentaux 52
3.2.2 Recuit Simulé
«La performance du Recuit Simuléest
étroitement liée au schéma de refroidissement
considéré» [51].
3.2.2.1 Variance de ?f
Une solution qui ne minimise pas le makespan doit valider le
critère de Metropolis pour qu'elle puisse être
acceptée, ce critère se base sur l'inverse de l'exponentielle du
rapport entre ?f et T, s'il est proche de zéro alors
cette solution a une grande probabilitéd'être acceptée,
c'est d'ailleurs une des propriétés de cette
méta-heuristique oùles premières itérations
semblent être une diversification et les dernières
itérations semblent être une intensification. La
dégradation de la température s'avère donc une tâche
très critique dont le choix doit être pris avec soin.
On doit fixer la valeur initiale de la température de
façon de garantir que le rapport ?! T soit
très proche de zéro au début de la recherche, T
doit donc être très importante par rapport à
?f, pour cela on a effectuédes test pour estimer les valeurs
moyennes du gain ?f sur les cinq familles d'instance avec quatre
tailles de problème (20, 50, 100 et 150 jobs), le
Tableau 3.6 synthétise la moyennes des résultats sur 20 instances
et 2000 itérations pour chaque instance. Les résultats sont
simplifiés dans le Tableau 3.7.
Tableau 3.6 - Valeurs moyennes de ?f pour cinq familles
d'instance
|
n = 20
|
n = 50
|
n = 100
|
n = 150
|
|
moyenne
|
u
|
moyenne
|
u
|
moyenne
|
u
|
moyenne
|
u
|
|
F1
|
6.7
|
0.2
|
6.5
|
0.2
|
6.5
|
0.2
|
6.2
|
0.1
|
|
F2
|
30.3
|
1.1
|
30.6
|
1.1
|
31.5
|
1.1
|
29.8
|
1
|
|
F3
|
63.7
|
9.4
|
80.5
|
3.5
|
73.2
|
11.4
|
76.4
|
5.7
|
|
F4
|
9.1
|
27.2
|
9.9
|
0.7
|
10.3
|
15.7
|
9.9
|
14
|
|
F5
|
6.6
|
0.2
|
6.7
|
0.2
|
6.6
|
0.2
|
6.8
|
0.5
|
Tableau 3.7 - Résumédu tableau 3.6
|
n
|
20
|
50
|
100
|
150
|
|
F1
|
8
|
7
|
7
|
7
|
|
F2
|
32
|
32
|
32
|
30
|
|
F3
|
73
|
84
|
84
|
84
|
|
F4
|
40
|
10
|
26
|
25
|
|
F5
|
7
|
7
|
7
|
7
|
Résultats expérimentaux 53
Maintenant qu'on a une idée sur les valeurs de ?f
on peut fixer les valeurs initiales de la température T de
manière a ce que pour les premières itérations on ait une
probabilitéimportante d'accepter les mouvements (0.99).
Si on prend l'exemple de la famille F2, et pour une
probabilitéde 0.99 on a,
|
Tinitiale =
|
-?f
Ln(0.99)
|
-32
Ln(0.99) ? 3184
|
Le Tableau 3.8 synthétise les différents valeurs de
la température pour toutes le familles d'instance.
Tableau 3.8 - Valeurs initiales de T pour les cinq
familles d'instances
|
Familles d'instance
|
Température initiale
|
|
F1
|
796
|
|
F2
|
3184
|
|
F3
|
8356
|
|
F4
|
3980
|
|
F5
|
696
|
| 
