ALGORITHME GÉNÉTIQUE: PROBLÈME DU VOYAGEUR

Commentaire de MAURICIO le 22/04/2005 15:29:43

Excelente démonstration !!!
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!!!

Commentaire de ffert le 24/04/2005 15:05:08

Salut,
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...

Commentaire de Gimli le 24/04/2005 18:44:41

salut,
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

Commentaire de Gimli le 21/05/2005 09:30:02

salut, merci de tes remarques, mais j'ai moi aussi quelques commentaires à faire:
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.
@+

Commentaire de NeoFoenix le 21/06/2005 11:19:44

j'oubliais...
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.

Commentaire de NeoFoenix le 28/06/2005 00:52:37

Je pensais a hybrider l'ag avec une rts (reactive tabu search)

...(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.