Algorithme des fourmis (ant)
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
