12/01/2014
2013 – 2014
RCP104
Optimisation en Informatique
TD 3 : Méta-heuristiques
Dr. Nazih OUWAYED
[Link]@[Link]
[Link]
Exercice 1 (1/1)
Considérez le problème de voyageur de commerce représenté par le graphe suivant
(le sommet 1 représente la ville de départ)
2 RCP104 – Optimisation en Informatique Janvier 2014
1
12/01/2014
Exercice 1 (2/2)
Q1. Énumérez toutes les solutions possibles et spécifiez la distance totale parcourue
pour chaque solution
Q2. A partir de la solution 1-2-3-4-5-1, énumérez toutes les solutions obtenues par
inversion de sous-tours
Q3. Effectuez une itération de la méthode de descente (basée sur l’inversion de
sous- tours) à partir de la solution 1-2-3-4-5-1. Si vous deviez effectuer une seconde
itération, que se passerait-il?
Q4. Supposez que nous procédions à une itération de la méthode de recuit simulé
(basée sur l’inversion de sous-tours) à partir de la solution 1-2-3-4-5-1. Pour chaque
solution candidate identifiée en Q2, évaluez sa probabilité d’acceptation si cette
solution était générée au hasard (prenez T = 2 comme valeur du paramètre de
température). Rappel : Probabilité ex, où x = (Zn – Zc)/T
3 RCP104 – Optimisation en Informatique Janvier 2014
Exercice 1 – Solution
Q1. Voici toutes les solutions possibles, avec la distance totale associée :
1-2-3-4-5-1 34
1-2-3-5-4-1 34
1-2-4-3-5-1 36
1-2-4-5-3-1 31
1-2-5-3-4-1 30
1-2-5-4-3-1 25
1-3-2-4-5-1 32
1-3-2-5-4-1 26
1-3-4-2-5-1 28
1-3-5-2-4-1 28
1-4-2-3-5-1 37
1-4-3-2-5-1 31
4 RCP104 – Optimisation en Informatique Janvier 2014
2
12/01/2014
Exercice 1 – Solution
Q2. Solution initiale : 1-2-3-4-5-1 (34)
Inversions de sous-tours :
1-4-3-2-5-1 (31)
1-3-2-4-5-1 (32)
1-2-5-4-3-1 (25)
1-2-4-3-5-1 (36)
1-2-3-5-4-1 (34)
5 RCP104 – Optimisation en Informatique Janvier 2014
Exercice 1 – Solution
Q3. À partir de la solution 1-2-3-4-5-1 (34)
La solution obtenue par inversion de sous-tours qui améliore le
plus la valeur de l’objectif est : 1-2-5-4-3-1 (25)
C’est donc la nouvelle solution à la fin de cette itération. Si nous
devions effectuer une seconde itération, nous ne trouverions
aucune solution qui permette d’améliorer la valeur de l’objectif,
puisque la solution est optimale (voir Q1). La méthode de
descente s’arrêterait donc.
6 RCP104 – Optimisation en Informatique Janvier 2014
3
12/01/2014
Exercice 1 – Solution
Q4. À partir de la solution 1-2-3-4-5-1 (34). Voici les solutions
et leur probabilité d’acceptation :
1-4-3-2-5-1 (31) . Prob(acceptation) = e (34-31)/2= e 1
1-3-2-4-5-1 (32) . Prob(acceptation) = e (34-32)/2= e 1
1-2-5-4-3-1 (25) . Prob(acceptation) = e (34-25)/2= e 4.5
1-2-4-3-5-1 (36) . Prob(acceptation) = e (34-36)/2= e -1
1-2-3-5-4-1 (34) . Prob(acceptation) = e (34-34)/2= e 0 =1
Probabilité ex, où x = (Zn – Zc)/T
7 RCP104 – Optimisation en Informatique Janvier 2014
Exercice 2 (1/2)
Voici les données d’un problème de voyageur de
commerce suivant :
8 RCP104 – Optimisation en Informatique Janvier 2014
4
12/01/2014
Exercice 2 (2/2)
Appliquer les trois méta-heuristiques :
Q1. Recherche avec tabous (utiliser 1-2-3-4-5-6-7-8-1
comme solution initiale)
Q2. Recuit simulé (5 itérations,T=2) A rendre Q2 ou Q3
[Link] génétique avant Jeudi 16-Janvier 23H59
Quelle méthode donne la meilleure solution pour ce
problème ?
9 RCP104 – Optimisation en Informatique Janvier 2014
Exercice 2 – Solution.Q1
10 RCP104 – Optimisation en Informatique Janvier 2014
5
12/01/2014
Références
Modèles de recherche opérationnelle - Bernard Gendron,
Université de montréal
11 RCP104 – Optimisation en Informatique Janvier 2014