Discussion :

[ymoreau]

Bonjour à tous, j'ai trouvé quelques sujets en parlant mais très vagues donc j'en crée un nouveau.

Tout d'abord le problème de mon projet :
Un espace (2D) avec des balises et un point de départ. Chaque balise a un score. Le but est de trouver une tournée partant du point de départ et y revenant en un temps limité tout en faisant le meilleur score possible.

J'ai donc opté pour l'algorithme des fourmis qui m'avait l'air intéressant.
Voici comment je l'ai implémenté :

Pour un certain nombre de génération

Pour un certain nombre de fourmis

On crée la fourmi i selon la règle de transition
on compare à la meilleure_fourmi trouvée jusque là

On met à jour la matrice de phéromones
On évapore la matrice de phéromones

Avec comme règle de transition :
On prend comme balise suivante la balise ayant le meilleur critère, avec comme critère :
((valeur_phéromone)coef u) * (( score / distance )coef v) * [nombre aléatoire entre 0.7 et 1.3]

Mise à jour de la matrice de phéromones :
Chaque arête (distance entre deux balises) a une valeur de phéromone. Pour chaque fourmi trouvée on multiplie chaque arête de sa solution par le rapport :
k * (score de la solution / score de la meilleure solution)

Pour évaporer les phéromones :
On multiplie chacune d'elle par un coefficient global e compris entre 0 et 1
(dans mon cas assez proche de 1).


Mon problème est que l'augmentation des phéromones se concentre sur une minorité d'arêtes très rapidement ("converge vers une minorité d'arcs"), et donc ça tourne en rond et les solutions ne valent pas mieux d'une génération sur l'autre. J'ai essayé de jouer avec les coefficients mais ça ne change rien à la convergence.
Pour info avec une génération j'approche entre 80 et 90% de la meilleure solution trouvée (par les autres promos), et je dois être entre 90 et 100.

Si quelqu'un a des conseils, ça me serait d'une grande aide il me reste deux jours ^^

Merci d'avance

[pseudocode]

Pour un certain nombre de génération

Pour un certain nombre de fourmis

On crée la fourmi i selon la règle de transition
on compare à la meilleure_fourmi trouvée jusque là

On met à jour la matrice de phéromones
On évapore la matrice de phéromones

Il vient d'ou cet algorithme ? Tu l'as trouvé dans un document ?

[ymoreau]

Disons qu'on a eu les grandes lignes en cours et que j'ai ensuite fait ce que j'en avais compris. Mon algorithme est pas bon ?

[ToTo13]

Bonjour,

il me semble que lorsqu'une fourmie trouve une source de nourriture, elle retourne le plus directement possible vers la fourmillière, mais en laissant une trace BEAUCOUP plus forte qu'à l'ordinaire...
Cela paliera ton problème d'une trace insuffisante.

[pseudocode]

Tu peux egalement regarder un exemple d'implémentation sur ce site:

http://www.crdp.ac-grenoble.fr/imel/...c/infogene.htm

[ymoreau]

Bonjour,

il me semble que lorsqu'une fourmie trouve une source de nourriture, elle retourne le plus directement possible vers la fourmillière, mais en laissant une trace BEAUCOUP plus forte qu'à l'ordinaire...
Cela paliera ton problème d'une trace insuffisante.

Oui ça c'est le principe de base, sauf que dans mon problème ça ne s'applique pas, car je ne cherche pas un plus court chemin, mais un parcours le plus rentable, donc on ne connait l'intérêt du parcours que lorsqu'il est entièrement fait.

Même chose sur le lien, il s'agit d'une recherche de plus court chemin, mais je trouverai peut être des idées, merci.

[pseudocode]

Oui ça c'est le principe de base, sauf que dans mon problème ça ne s'applique pas, car je ne cherche pas un plus court chemin, mais un parcours le plus rentable, donc on ne connait l'intérêt du parcours que lorsqu'il est entièrement fait.

On pourrait utiliser un algo AS classique avec une heuristique d'insertion.

Sinon, pour les problemes "Time Dependent" (TDVRP,...) on découpe généralement le temps en tranche (slice) et on applique l'algo AS sur chaque tranche. Il faudrait voir si c'est applicable dans ton cas.

[ToTo13]

Bonjour,

Oui ça c'est le principe de base, sauf que dans mon problème ça ne s'applique pas, car je ne cherche pas un plus court chemin, mais un parcours le plus rentable, donc on ne connait l'intérêt du parcours que lorsqu'il est entièrement fait.

En fait en guise de plus court chemin, tu fais un plus court parcourt.
Les fourmis vont aller vers le lieu le plus proche, puis le suivant et ainsi de suite...
Donc ça revient au même sauf qu'il te faut laisser finir tout le travail des fourmis.

[ymoreau]

Oui sauf que si le principe est de laisser des phéromones quand on a trouvé de la nourriture, dans mon cas il n'y a jamais (ou toujours) de nourriture. Chercher la balise la plus intéressante au niveau du parcours c'est déjà géré par le critère score/distance. Mon problème est plutôt sur le dépot des phéromones après tout ça.
Et j'ai du mal à imaginer un découpement du temps dans ce cas là. Tu voulais dire chercher le plus court chemin pour une portion de balises ? Seulement le score entre en compte aussi.

[ToTo13]

Bonjour,

dans l'algorithme des fourmis, les phéromones ont une durée de vie ainsi que le dépot.
Sinon deux problèmes immédiats :
- les phéromones s'accumulent et les fourmis passent toujours au même endroit.
- le dépot est toujours ouvert et s'il est le plus près, les fourmis vont toujours se nourir au même endroit.

[ymoreau]

Pour la durée de vie des phéromones il y a l'évaporation générale à chaque génération. Par contre j'ai du mal à voir comment le principe de dépot peut s'appliquer dans le problème de course d'orientation.
J'ai eu beau tatonner avec les paramètres rien n'y fait, les phéromones convergent toujours vers les mêmes solutions.

[ToTo13]

Bonjour,

je pense que dans ton problème, il faut que lorsqu'une source de nourriture est finie, la fourmilière se déplace vers la source qui vient de se tarir. Sinon les fourmis vont continuellement repartir de ton point de départ.
Une fois que la dernière source sera tarie, tu remets la fourmillière à son point d'origine.

[pseudocode]

Après une recherche rapide, les solutions pour le TD-TSP avec profit utilisent la notion de "mesure d'apprentissage" (Learning Measure).

D'après ce que j'ai compris, on allonge progressivement un chemin en inserant un nouveau point de passage. Pour choisir un point de passage, on utilise l'algo AS sur le chemin initial et on choisi le point de passage qui maximise la rentabilité du chemin total (score/temps). Une fois le point de passage trouvé, on l'ajoute au chemin et on recommence.

[Sve@r]

Ca me rappelle quelque chose => http://mute-net.sourceforge.net/howAnts.fr.shtml...

[pseudocode]

Ca me rappelle quelque chose => http://mute-net.sourceforge.net/howAnts.fr.shtml...

Non, ce n'est pas vraiment cela... dans le PO Il y a une contrainte de temps. D'ou le fait d'utiliser plusieurs colonnies: une par "periode" de temps.