Bonjour,
J'essai de résoudre le problème du voyageur de commerce. Je pars de très simple pour ensuite améliorer les différentes étapes de l'algo. Seulement j'ai un petit problème (qui doit être normal). J'ai toujours le même résultat quelque soit le nombre d'itération.
 
Je part sur un total de 5 villes (gène) et 6 trajets (individu).
Un trajet est une liste de villes.
 
Je vous décris ma méthode, ma boucle principale :
 

 
Tout ce base sur la distance. Pour récupérer le meilleur individu, je prend celui qui à la distance la plus courte. Inversement pour l'individu le plus mauvais (distance la plus longue).
 
La fonction recombine crée un fils à partir des parents :
Pour la recombinaison, je prends le meilleur individu et un individu au hasard
 
Je détermine une position de façon aléatoire dans ma liste de villes (entre 0 et nbvilles - 1)
 
Je mets les villes du Parent1 dans le fils jusqu'à positionAlétatoire
Je fais la même chose à partir de positionAléatoire jusqu'à la fin avec le ParentB
 

 
 
Ensuite j'applique une mutation au fils. Dans mon cas, elle est très simple, elle inverse deux villes de façon aléatoire.
 
Puis je réinsert le fils créé si celui-ci n'est pas le plus mauvais individu. Si ce n'est pas le plus mauvais, je supprime le plus mauvais et j'insère mon fils.
 
Or j'ai toujours le même résultat (distance). Est-ce du à mon nombre de ville et d'individu assez faible ? De plus j'imagine que c'est pas le chemin optimal car en représentant le chemin de façon graphique, des liaisons se coupent entre elles.
 
Petite question sinon, pour moi le trajet optimal aura aucune laision qui s'entrecoupe, je me trompe ?
 
Si vous avez des conseils d'amélioration, etc
 
Merci de m'avoir lu et de votre aide!

l'approche par un algo génétique, j'aime bien Mais tu fais combien d'itérations? Parce que 5 villes et 6 individus, c'est peu. T'as sans doute mis un nb d'itérations suffisant pour couvrir tous les trajets possibles. Y'a combien de trajets possibles entre tes villes?
 
Sinon, pourquoi ne pas avoir utilisé l'algo "classique" utilisé en théorie des graphes?

Je fais 100 itérations en tout. Pour le nombre de possibilités, 12 enfait...
Je vais augmenter mon nombre de ville et mon nombre de trajets.
 
Je développe ça juste pour essayer de faire un algo génétique enfait. Et je connais pas du tout l'algo classique utilisé en théorie de graphes du coup. Mon but n'étant pas d'utiliser à terme tout ça, c'est juste pour le fun
 
Je vais voir tout ça avec plus d'éléments.
 
Merci de ta réponse.

ben 100 itérations pour 12 chemins possibles, t'as forcément le trajet optimum. Il faudrait un rapport inverse, genre 100 chemins possibles et 12 itérations.
Rappel :
Nb de chemins tests avec un algo génétique = nb individus * nb itérations
Donc, même avec 100 chemins possibles, 12 itérations et 6 individus dans ta population, t'as un rapport proche de 1 (72/100), ce qui n'est pas bon. Pour montrer l'intérêt d'un algo génétique, faut rapport bien supérieur, genre 1000 chemins et rester à 6 individus et 12 itérations.
 
J'avais codé un soft avec un algo génétique pour optimiser la place perdu sur la gravures de plusieurs CDs. http://chris-jav.servhome.org/projects_optcd.php
Le nb de combinaisons à tester était = (nb de CD + 1)^(nb de fichiers dans la liste), le +1 correspondant au fait que le fichier pouvait ne pas être pris pour être gravé. Avec une population de 50 individus et 250 itérations, j'avais le résultat optimal à chaque coup ou une solution très proche de l'optimal pour 3 cds et 20 fichiers en entrée, soit 1099511627776 combinaisons possibles alors qu'avec mon algo, je testais finalement 50*250= 12500 combinaisons. Pas mal comme ratio! (il est proche de 0)...
 
http://forum.hardware.fr/hfr/Progr [...] 6299_1.htm

Du coup j'essai de générer automatique plus d'individus (trajet). Actuellement je les initialisais en code, mais là, si j'augmente le nombre d'individus, je veux le faire de façon automatique.
 
J'ai lu que le nombre de possibilité pour n villes est de (n - 1)! / 2
 
J'ai un peu perdu niveau maths, comment ça se traduit ?
 
Donc je vais créer ma population, mais je me pose une question. Celle-ci doit-être composée unique de trajets unique ? <= Pas très clair : (en gros, je ne peux pas avoir 2 trajets identique dans ma population ?)
 
Merci pour tes infos rufo

le !, c'est la factorielle. Donc, si on a 5 villes, ça fait (5-1)!/2 =  
4*3*2*1 / 2 = 24/2 = 12
 
Tes individus, faut les générer de manière aléatoire. Après, y'a différentes stratégies pour générer ta population et mettre plus ou moins de contraintes sur cette génération, genre, générer que des chemins possibles, générer que des chemins uniques... Mais plus y'a de contraintes, plus ça va mettre du temps pour générer ta population de base. En +, ça va pas forcément aider l'algo à converger vers la solution optimale. par contre, faut soigner ta fonction d'évaluation d'un individu et mettre des grosses pénalités pour les chemins impossibles, histoire de les éliminer rapidement. Pareil, faut se poser la question si le croisement et la mutation ont un sens dans ton pb et si oui, quelle proba leur fixer (en général, y'a un rapport d'au moins 10 entre les 2, ex : 0.1 pour le croisement et 0.01 pour la mutation)?
Enfin, l'algo de sélection des individus pour faire la population de l'itération suivante va pas mal influencer la manière dont ton algo va converger : sélection aléatoire pure, sélection proportionnelle à la valeur  de la fonction d'éval de l'individu (meilleure sa fonction est, plus il a de chances d'être sélectionné pour le tour suivant), sélection par tournoi (on prend des paires d'individus et on les fait "combattre" entre eux avec une probabilité de gagner qui peut dépendre de la fonction d'éval de l'individu ou d'un autre critère)...
Un algo génétique, c'est surtout une question de réglage.

Super réponse merci !
 
Je vais créer deux fonctions pour générer ma population, une qu'avec des trajets unique, et l'autre de façon aléatoire.
 
Je vais également mettre en place un système de proba pour ne pas faire à chaque itération un croisement et une mutation.
 
Et afficher de façon graphique le résultat.
 
Je vais voir si les résultats changent déjà avec ces 2 modifications.
 

 
Tu parles de la partie où l'on réintègre le fils généré par le croisement (recombine) des deux parents ou alors justement, la sélection des deux parents ?
 
Pour la sélection, je prends le meilleur et un au hasard.
 

 
C'est ce que j'ai pu comprendre
 
Edit : Certaines phrases pas compréhensibles...

Les proba sur les croisements et mutations concernent les individus, pas les itérations. En gros, pour chaque itération, c'est :
- quelle est la proba qu'un individu subisse un croisement?
- quelle est la proba qu'un individu subisse une mutation?
Ca fait qu'à chaque itération, si t'as une population assez grande par rapport aux probas définies, t'auras qq individus qui auront subi un croisement et certains qui auront (mais beaucoup moins) subi une mutation.
 
Ensuite, à chaque itération, tu dois avoir la même taille de population, celle-ci étant créée à partir de la population obtenue à la fin de l'itération précédente. Mais effectivement, c'est bien de conserver le meilleur individu obtenu durant l'exécution de l'algo. A chaque itération, faut vérifier si le meilleur individu de la population est meilleur que celui stocké en mémoire. Si oui, alors, faut le remplacer par le meilleur, sinon, on n'y touche pas.
Je te conseille de télécharger le code source de mon composant Delphi relatif à l'optimisation de cds. Le gros du code est réutilisable (ou adaptable d'un point de vue algorithmie) si tu développes dans un autre langage...
Je te conseille aussi de t'informer un peu plus sur les algos génétiques parce que j'ai l'impression que tes bases ne sont pas très solides.

Enfait le but de cette exercice est justement de comprendre les algorithmes génétiques
 
A lire ta réponse, il est possible de "modifier" (croisement ou mutation) plusieurs individus dans une même itération ?
 
Je vais regarder ton composant, merci !

Ah oui, j'ai trouvé ce lien qui est plutôt pas mal et sur lequel je me base : http://labo.algo.free.fr/pvc/algorithme_genetique.html
 
Mais est-ce que tu aurais d'autres liens interessants et surtout abordables sur le problème ?

ton lien est très bien est dit en gros ce que je t'ai dit, en plus détaillé. Ce que j'appelle croisement, c'est le crossover.
Là, comme ça, j'ai pas d'autres sites à te proposer, c'est pas ma spécialité (j'en code pas souvent).

Bonjour,  
 
J'ai ce problème à résoudre mais sous matlab et j'ai qq soucis, qqun pourrait m'aider ?