ALGORITHME GÉNÉTIQUE: PROBLÈME DU VOYAGEUR
cs_MAURICIO
Messages postés
2106
Date d'inscription
mardi 10 décembre 2002
Statut
Modérateur
Dernière intervention
15 décembre 2014
-
22 avril 2005 à 15:29
cs_rahma123 Messages postés 2 Date d'inscription mardi 22 février 2011 Statut Membre Dernière intervention 26 février 2011 - 26 févr. 2011 à 16:29
cs_rahma123 Messages postés 2 Date d'inscription mardi 22 février 2011 Statut Membre Dernière intervention 26 février 2011 - 26 févr. 2011 à 16:29
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/30906-algorithme-genetique-probleme-du-voyageur
https://codes-sources.commentcamarche.net/source/30906-algorithme-genetique-probleme-du-voyageur
26 févr. 2011 à 16:29
et comment l'appliquer avec matlab? c trés urgent!! merci bcp
23 mars 2010 à 18:05
2:backet brigade
3:algorithmz génétique
4:Q-learning
13 août 2007 à 01:08
Je ne sais pas par ou commencé ci vous avait une idée.
le projet consiste de tracée le contour une image
Merci d'avance de votre aide mon email capi64@voila.fr
16 mars 2006 à 17:42
trés bonne modélisation des AG ,pas évidente mais néanmoins excellente.
28 juin 2005 à 00:52
...(blahblah)...
selection
croisement
rech locale / tabu search / rts <--- et hop
mutation
...(blahblah)...
y'a toujours le hasard de la selection mais la
rts permet de pas tomber dans les optima locaux.
et la rts peut faire un echappement si jamais
on a itere trop longtemps (parametre ?) sans
amelioration notable.
27 juin 2005 à 22:47
NéoFoenix, pour éviter la dégénérescence dans un algo génétique on utilise la mutation ainsi que la méthode de la roulette lors de la sélection, ce que cette source. De plus les méthodes dite méta heuristique ne s'applique pas aux algos génétiques ( pour diverses raisons que je n'expliquerai pas ici si ce n'est un mot : le hasard ).
Sinon pour la méthode de croisement je te l'accorde il y mieu ( mais je l'ai déjà dit et ton exemple est bon )
21 juin 2005 à 11:19
pour eviter la degenerescence tu peux hybrider l'algo genetique
avec une methode qui travaille sur le voisinage. Il y a aussi
la mutation qui influe, mais un facteur trop fort et ca ne conserve
plus suffisament longtemps les bonnes carac.
21 juin 2005 à 11:16
le piege serait de tomber sur des optimums locaux.
(ca y ressemble quand tu peux pas optimiser plus parce que t'as deja
utilisé des longueurs plus courtes).
si tes chromosomes ont n-1 genes (il y a n villes, et on a le point de
depart et d'arrivee)
ex :
n = 6
depart = 1
population initiale :
chromosome1 = 2 3 4 5 6
chromosome2 = 5 3 4 2 6
chromosome3 = 4 6 3 5 2
...
avec une coupure a 1 point
chromosome1 = 2 3:4 5 6
chromosome2 = 5 3:4 2 6
tu copies le debut et recopies les villes non presentes dans
l'ordre ou elles sont chez l'autre parent.
chromosome1 = 2 3:4 5 6
chromosome2 = 5 3:4 2 6
enfant1 = 2 3 5 4 6 (2 et 3, puis dans l'ordre 5, 4, 6)
enfant2 = 5 3 2 4 6
21 mai 2005 à 09:30
je ne vois pas comment dans un algo de ce type (avec les permutations), on peut garder les parties de chaque parent. mais à mon avis ca doit bcp compliquer le code.
pour la selection, j'utilise la méthode de la roulette mais en classant les chromosomes, car la méthode de la roulette (si on parle bien de la meme) a tendance, dans les cas extremes, à eliminer les moins bons. mais peut etre parlait-tu d'1 equiprobabilite.
la methode que j'utilise est la suivante:
sur 4 chromosomes, la probabilité que le meilleur soit selectionné est de 4/10, le 2e de 3/10, le 3e de 2/10 et le dernier 1/10 (10 étant la somme 1 + 2 + 3 + 4).
maid c'est sur il y a des ameliorations a faire.
@+
20 mai 2005 à 22:44
J'ai un peu regardé ton code et surtout quel était ta méthode d'algo génétique.
Tu suis bien la méthode, cependant ton principe de sélection des individus et ton cross-over sont un peu à améliorer...
En effet, pour le cross-over, le principe est de garder les caractéristiques des parents, or toi tu gardes qu'une partie d'un seul parent, donc une seule caractéristique, et ensuite tu complète l'enfant. D'où le principe n'est pas 100% respecté.
Deuxièmement, lors de la sélection des individus pour la population suivante, on ne doit pas garder que les meilleurs individus, sinon il y a une dégénérescense de la population. Et oui cela peut paraitre bizard, mais pour faire de bonne solution il en faut aussi des mauvaises lors du cross-over. D'où il existe la méthode de la roulette pour le choix des individus lors de la sélection.
Voilà pour les remarques, et oui pour s'améliorer il faut bien qq remarque lol. Allez bon courage.
24 avril 2005 à 18:44
j'ai regardé les possibilites de la théorie des graphes (qui sont vraiment énormes) et on peut résoudre ce problème de manière systématique mais étant donné que dans mon cas il s'agirait d'1 graphe complet (tous les points sont connectés entre eux), je me demande si ca ne serait pas 1 peu long, (mais c'est sur ces algos sont tres performants).
sinon une petite amélioration: remplacer Nbmutations := 1 par NbMutation := random(2); car le nombre de mutations etait trop élevé pour un nombre de ville < 100.
@+ et merci
24 avril 2005 à 16:15
pour le problème du voyageur de commerce, avec n villes, un algorithme naif (qui teste toutes les solutions) demanderait (n-1)!/2 itérations, se qui est énorme. Les algorithmes génétiques permettent de trouver rapidement une bonne solution.
a+
24 avril 2005 à 15:05
Bon boulot concernant l'approche génétique... Mais à mon avis dans ce cas là, un Algo génétique n'est pas la meilleur solution pour trouver le plus cours chemin (dans le cas d'un contexte systèmatique). Avec un algo du plus court chemin c'est n-1 itérations (si mes souvenirs sont bon) et avec toujours le même résultat qu'il y ait 10 ou 1000 villes !!! ;)
des algos tels que Floyd ou Disjktra sont trés performants !!!
Si les graphes (et bien d'autres choses) vous interresses, rendez-vous sur mon site : http://ffert.free.fr/ Rubrique "cours" puis "cours de recherche opérationnelle"
Bonne lecture...
23 avril 2005 à 08:24
d'abord merci; ensuite il faut savoir qu'il existe d'autres méthodes pour chaque étape de l'algorithme génétique qui rendent un peu moins aléatoire (les mutations...). Cependant le hasard est quand même à la base des évolutions génétiques.
Enfin le problème est que cette méthode n'est pas systématique (pour 1 grand nombre de villes) et qu'il garde effectivement certains morceaux qui ne sont pas forcement les meilleurs.
Il parait qu'on peut faire la même chose de manière systématique avec la théorie des graphes...
@+
22 avril 2005 à 15:29
Bon, j' ai pas analysé le code en detail mais je comprends mieux pourquoi ont a pas 2 fois le même résultat.
Le fait de garder les morceaux les plus cours n' est pas forcement une bonne idée parce que ça va provoquer de longs déplacements pour les villes restantes.
Je pense qu' un systeme de localisation des villes les plus proches (dans un rayon autour d' une ville) serait plus judicieux en testant à partir d' une ville, les 2 prochaines etapes avec la distance la plus courte.
Bref, ça rejoins ce que fait cette méthode mais elle est trop aleatoire à mon goût.
Bravo en tout cas. 10/10
PS: mets Button1.Enabled à false puis à true dans Button2Click!!!