Résumé : On étudie un processus d’apprentissage par renforcement, pour la recherche de plus courts chemins dans un graphe, dans lequel des fourmis partent d’un nid (aléatoire, N1 ou N2) et font une marche aléatoire (pondérée par les poids des arêtes) jusqu’à une source de nourriture F. À leur retour, elles renforcent les arêtes (en ajoutant 1 à leur poids) appartenant au chemin aller auquel on a enlevé les boucles inutiles. Ce modèle a déjà été étudié sur divers graphes dans le cas où le nid est déterministe, notamment les graphes séries-parallèles, mais aussi pour d’autres politiques de renforcements (articles de Kious, Mailler et Schapira). Nous étudions le cas à deux nids, dans des graphes obtenus en joignant trois graphes séries-parallèles pour former un triangle. On montre que les poids des arêtes (normalisés) convergent, vers des variables aléatoires nulles si et seulement si les arêtes associées n’appartiennent pas à un plus court chemin d’un sommet de {N1 , N2 , F } à un autre. Nous présenterons plusieurs outils utiles pour prouver cette convergence, notamment la comparaison avec des processus d'urnes, et quelques résultats sur les approximations stochastiques. La présentation se basera sur un travail en commun avec Cécile Mailler.

Dernière modification : Friday 06 June 2025

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr