Arbre de recouvrement d'un graphe via algo de colonie de fourmis

Question

Bonjour à tout le monde,
Je suis ravis de vous rejoindre, au faite je suis un nouveau sur ce forum..
J'ai eu à implémenter (séquentiellement) l'arbre de recouvrement d'un graphe en java, en C via algorithme de Prim et Kruskal sans problème. Mais cette fois-ci on m'a fait découvrir qu'il y'a une approche de construction de façon distribuée plus intéressante. Ceci en utilisant un algorithme basé sur les colonies de fourmis. Ce que je veux bien implémenter en JAVA.
J'ai beaucoup réfléchi dessus et voici le principe de construction que j'ai envie d'adopter:
- Pour un graphe donnée, chaque nœud constituent un nid de fourmis à un instant t et les autre nœuds du graphe deviennent des sources de nourriture.
- Chaque fourmi ou agent doit se balader pour rallier le prochain nœud en tenant compte d'un certain nombre de critère: En suivant toujours la piste qui contient un maximum de phéromones déposé par d'autres. Ce qui formera le plus court chemin pour rallier le nid de la source la plus proche.
- L'algorithme devant s'exécuter sur chaque nœud d'après le principe du distribué, à la fin on doit obtenir un arbre de recouvrement.
Je ne sais pas si je me suis bien exprimé mais il faut seulement garder en tête que l'idée est de construire de façon distribuée à partir d'un graphe donnée un arbre de recouvrement en utilisant l'approche par colonies de fourmis (algorithme de résolution de divers problèmes dont les modèles sont basés sur les Graphes)
Merci de me faire signe si quelqu'un a une idée et pourrait m'aider via un LIEN IMPORTANT ou CODE SOURCE QUELCONQUE ou bien même UN PRINCIPE INTÉRESSANT pouvant m'aider sur la question car je ne m’en-sort pas trop en java pour ce qui est des interfaces graphiques mais je me bât très bien à comprendre..
Toutefois je suis disposé à répondre à vos questions de compréhension du sujet
Merci d'avance pour vos contributions.

KX · Answer

Bonjour,
Tu peux déjà regarder GraphStream que ce soit pour la structure Java de ton graphe ou les interfaces graphiques.
Visuellement tu auras surement quelque chose proche de l'exemple "Information System" dans leur vidéo d'exemple, à part que l'algorithme Random Walk qu'ils ont utilisés serait à remplacer par le tien.
Quant à ton choix de modélisation, je ne suis pas sûr qu'il soit utile de mettre des fourmis à tous les nœuds du graphe.
Déjà dans un premier temps, si tu arrives à faire partir les fourmis d'un noeud A et qu'elles arrivent à trouver le plus court chemin vers un noeud B où tu auras mis la nourriture, tu auras fait le plus gros.
Ensuite tu peux rajouter une nouvelle espèce de fourmis, qui partiraient toujours du même noeud A, mais attirées par un noeud C de nourriture. Et t'assurer que les deux espèces trouvent bien les chemins les plus courts AB et AC, sans se court-circuiter l'une l'autre.
Mais attention, en rajoutant une troisième espèces de fourmis en B et de la nourriture en C, celles-ci pourraient être tenté de faire BC sans passer par A, et dans ce cas tu n'aurais plus un arbre.
D'où l'intérêt de plutôt laisser toutes les espèces de fourmis partir du même nœud, même si en cas d'égalité de distance tu pourrais quand même te retrouver avec des cycles.
Remarque : un des avantages des colonies de fourmis c'est leur capacité d'adaptation. Si dynamiquement ton graphe évolue (suppression ou ajout d'un arc) les fourmis vont pouvoir prendre en compte ce changement et progressivement reconstruire la solution optimale.
Tu peux par exemple regarder le modèle NetLogo AntLines pour voir comment est implémenté leur algorithme de recherche de nourriture (moins de 100 lignes de code)

Arbre de recouvrement d'un graphe via algo de colonie de fourmis

1 réponse

Votre réponse

Discussions similaires