Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 3 sur 3
  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
    193
    Détails du profil
    Informations forums :
    Inscription : mai 2006
    Messages : 193
    Points : 158
    Points
    158

    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 actif
    Inscrit en
    mars 2008
    Messages
    209
    Détails du profil
    Informations forums :
    Inscription : mars 2008
    Messages : 209
    Points : 193
    Points
    193

    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

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •