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.