Discussion :

[marmarnassouf]

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

[Clercq]

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 .

[benDelphic]

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