Discussion :

[Jarek_Mace]

Bonjour à tous,

Je réalise en ce moment l'algorithme des fourmis sur Python, algorithme permettant de trouver une solution approchée à un problème d'optimisation. (le plus court chemin parmi n villes)

J'ai ainsi réalisé sur Python cet algorithme, qui fonctionne et qui me donne des résultats, mais qui sont, je pense, loin d'être optimaux.
Ainsi, je me demandais comment on pouvait faire pour déterminer les coefficients et les différents paramètres de l'algorithme, tel que le taux de phéromones initial, les coefficients alpha et bêta correspondant à la visibilité et aux phéromones (ceux qui connaissent un peu cet algo savent certainement de quoi je parle), ainsi que les phéromones déposés en route, ceux évaporés, etc...

En effet, j'ai des résultats, mais je n'ai aucune solution qui converge, c'est à dire qu'après 50 à 100 générations de fourmis, je n'ai pas un meilleur résultat que les deux premières générations.
Ainsi, mon algo est un peu inutile, il se base du coup plus sur l'aléa que sur un taux de phéromones indiquant précisément le chemin à suivre.

Merci pour vos éclaircissements et précisions,

Bonne soirée.

[dinobogan]

Toutes ces variables sont "magiques". Elles sont déterminées de façon empirique. Tu dois faire les réglages toi-même en fonction de tes observations.
Une approche possible est de générer régulièrement une carte en niveau de gris pour visualiser la quantité de phéromones. Tu vas obtenir une vue d'ensemble régulière et tu vas pouvoir distinguer des problèmes de réglages comme la quantité de phéromones déposée lors du retour au nid si l'image est quasi blanche ou au contraire si un chemin noir apparait très vite. Tu verras aussi la vitesse d'évaporation, trop rapide si l'image est trop blanche ou trop lente si elle vire rapidement au noir...

[Jarek_Mace]

Je te remercie pour tes conseils.
En effet, je pense que c'est ce qu'il y a de mieux à faire.

Toutefois, si quelqu'un a déjà créé cet algorithme et qu'il voulait partager ses données, qu'il n'hésite pas !

[250rgv]

Bonjour,

Ce qui me parait étonnant, c'est que tu obtienne tes meilleurs résultats dès le début. Tu a vérifié en lançant plusieurs fois de suite les calculs ?

Tu as essayé de comparer par rapport à du hasard 'simple' ? Ayant eu à d'implémenter le même problème (bin packing 2D) avec plusieurs méta-heuristiques, j'avais des doutes sur les résultats de l'une d'elles, j'ai implémenté ce problème sur de l'aléatoire 'simple'. En lançant le même problème (avec les mêmes données en entrée ainsi que les mêmes paramètres de 'réglage') plusieurs fois sur chaque méta puis en comparant les résultats, j'ai pu confirmer que cette implémentation était buggée : j'avais le même type de résultats qu'avec du hasard seul.

Ensuite, bien que le paramétrage soit effectivement empirique, as-tu regardé les publications pour ce couple problème/méta-heuristique en ce qui concerne le paramétrage ? Tu devrais y trouver des informations sur les valeurs non pas optimales mais à éviter, etc...