Nous avons abordé en cours des éléments sur les heuristiques inspirées du comportement des fourmis (Ant Algorithms, que l'on peut traduire par Fourmorithmes en Français). Ces algorithmes peuvent être considérés comme des heuristiques approximatives permettant de trouver des bonnes solutions à des problèmes d'optimisation combinatoires tels que celui du voyageur de commerce.
Nous avons également vu, dans le cours sur l'apprentissage, les algorithmes d'optimisation d'origine statistique appelées Support Vector Machines (que l'on peut traduire par Séparateurs à Vaste Marge en Français). La mise en oeuvre de ces méthodes est basée sur la technique des multiplicateurs de Lagrange, qui suppose une dualisation du problème.
Certaines approches récentes ont proposé d'aborder le problème direct (sans dualisation) avec des algorithmes génétiques. C'est cette approche que nous proposons d'approfondir avec les fourmorithmes, en particulier sur le point de rendre les méthodes incrémentales (par rapport aux exemples d'apprentissage).
L'aspect expérimental pourra partir de MadKit et du Plugin "AntKit" qui modélise l'application des fourmorithmes au problème du Voyageur de Commerce.
Ce stage se déroulera au sein du groupe Coconut dans le projet Kayou. Il est conseillé d'avoir suivi les modules M2R d'Apprentissage et de Systèmes Multi-Agents.
[Stoean et al., 2006] Stoean, R., Preuss, M., Stoean, C., and Dumitrescu, D. (2006). Evolutionary support vector machines and their application for classification. Technical Report CI-212/06, University of Dortmund.