1. #1
    Invité de passage
    Inscrit en
    avril 2009
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : avril 2009
    Messages : 4
    Points : 0
    Points
    0

    Par défaut Algorithme génétique et probleme de voyageur de commerce avec graphe non complet

    Salut tout le monde,
    Je suis encours de développement d'un algorithme génétique pour résoudre le problème de voyageurs de commerce, l'environnement de mon projet m'impose un graphe de villes qui n'est pas complet, c'est à dire qu'il n'y a pas nécessairement des routes qui relient toutes les villes avec les autres villes, il y a des routes qui ne sont pas définies.
    Je me demande est ce que ça sera possible d'utiliser l'algorithme génétique pour résoudre ce problème avec une telle contrainte?
    Si oui comment le faire??

    Merci

  2. #2
    Membre actif
    Inscrit en
    mai 2006
    Messages
    194
    Détails du profil
    Informations forums :
    Inscription : mai 2006
    Messages : 194
    Points : 172
    Points
    172

    Par défaut

    Je ne suis pas spécialiste en algorithme génétique mais à priori ça ne change pas grand choses.
    Si le génome de ta population code le chemin, il y aura juste moins de possibilité dans la recherche de ton circuit hamiltonien.
    Je pense que le plus simple est d'avoir un génome de la taille du nombre de ville à traversé, et d'avoir un codage pour dire je vais de A à B, de B à D ...
    Ensuite tu génére une première population, tu calcul la fitness (hamiltonien O/N, si O coût ?).
    Ensuite tu croise, mute et hop .

  3. #3
    Membre confirmé
    Inscrit en
    mars 2008
    Messages
    209
    Détails du profil
    Informations forums :
    Inscription : mars 2008
    Messages : 209
    Points : 218
    Points
    218

    Par défaut

    et ben tout simplement il suffit de rajouter tes aretes ou arcs manquants en leurs donnant un poids infini comme cela tu seras sur qu il ne seront pas dans ta solution ... et puis de toutes les façon tu peut inclure les aretes ou arcs à interdire dans ta population initiale et tes fonctions de mutation et de croisement

Discussions similaires

  1. Bibliothèque TSPLIB > Le probleme du voyageur de commerce
    Par sheridan08 dans le forum Intelligence artificielle
    Réponses: 1
    Dernier message: 05/04/2011, 09h01
  2. Réponses: 1
    Dernier message: 12/02/2011, 18h13
  3. Réponses: 2
    Dernier message: 03/02/2009, 20h21
  4. Probleme du Voyageur de Commerce, mais plus compliquée, avec des chemins interdit
    Par Midou45 dans le forum Statistiques et Data Mining
    Réponses: 6
    Dernier message: 03/01/2008, 13h14
  5. Voyageur de commerce avec Lisp
    Par abdo dans le forum Lisp
    Réponses: 2
    Dernier message: 11/03/2007, 02h42

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo