Scribd Logo
Importer

Bienvenue sur Scribd !

  • 63 vues

    03 - TD3

    Transféré par

    Elghaza Fatima
    Le document présente un exercice sur le problème du voyageur de commerce. Il décrit un graphe et demande de résoudre le problème avec différentes méta-heuristiques comme la recherche avec tabous, le recuit simulé et les algorithmes génétiques.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    03 - TD3

    Transféré par

    Elghaza Fatima
    63 vues6 pages
    Le document présente un exercice sur le problème du voyageur de commerce. Il décrit un graphe et demande de résoudre le problème avec différentes méta-heuristiques comme la recherche avec tabous, le recuit simulé et les algorithmes génétiques.

    Description originale:

    td

    Titre original

    03- TD3

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document présente un exercice sur le problème du voyageur de commerce. Il décrit un graphe et demande de résoudre le problème avec différentes méta-heuristiques comme la recherche avec tabous, le recuit simulé et les algorithmes génétiques.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    63 vues6 pages

    03 - TD3

    Transféré par

    Elghaza Fatima
    Le document présente un exercice sur le problème du voyageur de commerce. Il décrit un graphe et demande de résoudre le problème avec différentes méta-heuristiques comme la recherche avec tabous, le recuit simulé et les algorithmes génétiques.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 6

    12/01/2014

    2013 – 2014

    RCP104
    Optimisation en Informatique

    TD 3 : Méta-heuristiques

    Dr. Nazih OUWAYED


    [email protected]
    http://nouwayed.yolasite.com

    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
    Q3.Algorithme 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

    Vous aimerez peut-être aussi