Quelques question sur le PVC .

Bonjour à tous !
En tant que petit projet d'algo, j'ai choisit de regarder de plus prés les algorithme génétique , avec en exemple concret, le problème du voyageur de commerce . ( PVC pour les intimes :) )

Je vient tout juste d'en finir une première ébauche, qui semble donner des résultats "corrects", mais j'aimerai en être sur ;o)

Tout d'abord, j'initialise mes distances inter-ville, aléatoirement a chaque lancement du programme .
Je me demande si je ne devrai pas travaillé avec des valeur fixe ? (mais bon, je n'ai que peu de temps, et pas vraiment l'envie de coder ca :p donc si je pouvais m'en passer .... )

en gros, voila avec quoi je me retrouve pour 10 ville, sur 2 sessions :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Distancer inter-ville 0 10 7 8 5 9 6 8 3 8 10 0 2 3 5 8 6 7 7 4 7 2 0 2 3 7 4 5 4 3 8 3 2 0 2 5 6 4 5 1 5 5 3 2 0 5 5 3 2 3 9 8 7 5 5 0 10 1 6 4 6 6 4 6 5 10 0 8 4 7 8 7 5 4 3 1 8 0 5 3 3 7 4 5 2 6 4 5 0 5 8 4 3 1 3 4 7 3 5 0

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Distancer inter-ville 0 4 7 5 4 5 5 8 6 7 4 0 4 5 1 3 1 5 6 8 7 4 0 4 3 2 2 1 5 8 5 5 4 0 4 2 4 5 1 4 4 1 3 4 0 2 1 4 5 7 5 3 2 2 2 0 2 3 4 7 5 1 2 4 1 2 0 3 5 8 8 5 1 5 4 3 3 0 6 9 6 6 5 1 5 4 5 6 0 3 7 8 8 4 7 7 8 9 3 0

---

Et des distance de chemins entre 15 et 25 ( pour le meilleur ) selon les grilles ( pas forcément celle-ci dessus .

En partant sur l'hypothése que la distance moyenne d'un chemin est de
(NombreDeVille^2)/2, je doit pouvoir tester a peu prés mon algo sur un grand nombre de ville et aprés en faisant varier les paramètre, voir ce qu'il se passse,non?

Salut,

Il y a deux choses qui m'intrigue dans tes resultats.

- il n'y a que 10 iterations
- A quoi correpsondent tes valeurs ?

Maintenant je suppose que tu fais tes tests sur un cas connu dont tu peux determiner le parcours optimal. A quel point tes resultats sont-ils proches du trajet optimal ?

XXiemeciel

ok autant pour moi je viens de comprendre a quoi correspondent tes grilles

c'est un tableau de distance (c<est pour ca qu'il y a des zeros sur la diagonale)

Donc pour repondre a ta premiere question de prendre une valeure de depart aleatoire ne devrait pas changer grand chose pour ton programme.

maintenant pour tester ton algo prend un cas dont tu connais le resultat et compare.

XXiemeciel

Citation:

---

maintenant pour tester ton algo prend un cas dont tu connais le resultat et compare.

---

Le problème est la .

Soit je prend un cas connu,( ce que je n'ai pas ) ry je doit réécrire la routine de lecture de donné :p

Soit je prend mes cas au hasard, et je tape un algo qui teste TOUTE les possibilité ( mais la ca ne va marcher quavec des petite grille, et surtout je n'ai pas le temps/l'envie d'implmenter ca :p )

edit: ...oui je suis chiant :D je veux le beurre, l'argent du beurre, et la crémière ^^

Bon,

En principe si tu as bien codé ton algorithme tu as une population de solution avec des genes contenant un parcours pour chaque individu.

chaque parcours ayant une distance.

- Tu fais se reproduire ta population
- Tu introduit quelques mutations dans certains genes
- Tu selectionnes ceux dont le parcours est le plus court pour ta prochaine population.

Normalement ton algo ainsi codé va te donner une population dont la distance du parcours du voygaeur va etre de plus en plus petite et va se rapprocher de plus en plus de ta solution optimale.

Attention un algo génétique ne te donne aucune assurance sur le fais d'obtenir cette solution optimale. Il t'assure que tu vas t'en rapprocher le plus possible en fonction du nombre d'iteration.

Maintenant il t'est tres facile de generer ton propre parcours entre toute les villes optimisant la longueur du chemin ... prend une feuille de papier, place dix points en une espece de cercle et relie les, hop tu as un parcours optimale pour ce cas la.

entre le dans ton programme et regarde si l'ordre de parcours des villes correspond a celui de la feuille.

XXiemeciel

hum, oui je constate si je regarde les génération successive que la longeur des chemin tend a diminuer .
Qaund au cout de la feuille de papier, c'est comme ca que je génère mes distance en gros :D
Enfin bon :) je voir potasser tout ca :p

Bon j'ignore si c'est bon ou pas, mais pour 250 ville ( avec une distance moyenne entre chaque ville de 125 ) , j'obtient aprés 1 minute de calcul un trajet de 5.000 .
En terme de comparaison, le meilleur trajet, si on considére 50.000 individus au hasard est de environ 30.000 a chaque fois .

J'ai été surprit de voir que ce qui importait le p^lus était le nombre de génération calculé et non la taille de la population ( j'arrive a ~7500 avec seulement 10 individus, en a peine 10 seconde ! )

Exacte,

c'est le nombre de generation d'individus et non la quantité d'individus qui compte. Mais ce qui est tres important dans un algorithme genetique c'est la regle de selection des individus.

Je suppose dans ton cas tu prends tout les individus qui ont une taille de parcours inferieur a la moyenne ?

XXiemeciel

J'ai implmenter une méthode de sélection sans trop réfléchir, enfin, une fois comprit le principe, je peut toujours revenir la dessus aprés :p
J'ai opté pour un modèle elitiste simple, ou les parents sont choisi parmis les meilleux individus de la génération précédente .

En fait, je vient de tomber sur un site qui propose un "concours" pour un parcous a 250 ville . Dans leur cas, toute les ville sont situé ( je supose alétoirement ), dans un carré de 1*1 et le meilleur résultat est un chemin de taille 12 a peu prés .

Sachant que mes ville sont diposé alétoirement dans un carré de 250*250, je suppose que dans l'idéal je devrai avoir un chemin de 12*250, soit 3000, c'est ca?
( chemin calculé en plusieur minute il est écrit )

Bon je suis arrivé entre 4500 et 5000 au mieux en 1 minute , donc c'est pas si mal pour un algo vraiment de base ( aucune optimisation nul part ).

Si j'ai le temps j'implementerai une autre méthode de sélection, ou un cross-over en 2 point ect ...

Une dernière question me tracasse, dans ce cas, les résultat sont facilement évaluable ... enfin je veux dire qu'il est assez facile de constater un changement de performance dans l'algo selon les moifications qu'on y apporte. Mais dans le cadre de quelque chose de plus abstrait ; par exemple , le changement d'un groupe d'individus, face a leur environnement ( en l'occurrence, une tribu d'animaux par exemple ) Ca devient moins simple non ?

Je suis pas sur de te suivre mais c'est sur que les algorithmes genetiques ne font pas de la magie.

Il faut pouvoir transposer ton probleme dans les genes de ta population, que le nombre de genes soit limité pour avoir une convergence rapide et que chaque individu puisse etre evalué pour la selection (Ce qui mine de rien n'est pas toujours evident)

XXiemeciel

En fait c'est bon, pour vérifier mes résultat, j'ai juste mis tout ca sur pied graphiquement , et j'ai vu mes chemins ( nickel sur un petit nombre de ville , et honnete sur un grand nombre ) :)

Problème résolu :)