On étudiera dans cette partie la méta-heuristique ACO (ant colony optimization / optimisation par colonies de fourmis) qui s'inspire du comportement collectif des colonies de fourmis pour résoudre des problèmes d'optimisation combinatoire. L'idée est de représenter le problème à résoudre sous la forme de la recherche d'un «meilleur» chemin dans un graphe. Des fourmis artificielles circulent dans ce graphe de façon aléatoire et incomplète, à la recherche de «bons» chemins. Elles communiquent entre elles, à travers l'environnement, en déposant sur les arcs du graphe une trace d'hormone volatile appelée «phéromone» : cette hormone tend à attirer les fourmis artificielles dans une boucle de rétroaction positive, guidant de manière émergente la colonie vers une solution satisfaisante, si ce n'est la meilleure.
On étudiera tout d'abord les principaux mécanismes qui permettent l'émergence de comportement «intelligents» dans les colonies d'insectes «sociaux». On introduira ensuite le principe général de la méta-heuristique ACO. On verra enfin, à travers un certain nombre d'applications, que cette métaheuristique permet effectivement de résoudre des problèmes complexes.
Compétences acquises
Méthodologiques : Techniques de résolution de problèmes complexes
