Algorithme de colonies de fourmis

Le premier algorithme de colonies de fourmis proposé est appelé le Ant system[5] (système fourmi). Il vise notamment à résoudre le problème du voyageur de commerce, où le but est de trouver le plus court chemin permettant de relier un ensemble de villes.

L’algorithme général est relativement simple, et repose sur un ensemble de fourmis, chacune parcourant un trajet parmi ceux possibles. À chaque étape, la fourmi choisit de passer d’une ville à une autre en fonction de quelques règles :

1. elle ne peut visiter qu’une fois chaque ville ;
2. plus une ville est loin, moins elle a de chance d’être choisie (c’est la « visibilité ») ;
3. plus l'intensité de la piste de phéromone disposée sur l’arête entre deux villes est grande, plus le trajet aura de chance d’être choisi ;
4. une fois son trajet terminé, la fourmi dépose, sur l’ensemble des arêtes parcourues, plus de phéromones si le trajet est court ;
5. les pistes de phéromones s’évaporent à chaque itération.

L’algorithme «système formique» optimisant le problème du voyageur de commerce : 1) une fourmi choisit un trajet, et trace une piste de phéromone. 2) l’ensemble des fourmis parcourt un certain nombre de trajets, chaque fourmi déposant une quantité de phéromone proportionnelle à la qualité du parcours. 3) chaque arête du meilleur chemin est plus renforcée que les autres. 4) l’évaporation fait disparaître les mauvaises solutions.

La règle de déplacement, appelée « règle aléatoire de transition proportionnelle », est écrite mathématiquement sous la forme suivante :

${\displaystyle p_{ij}^{k}\left(t\right)=\left\{{\begin{matrix}{\frac {\tau _{ij}\left(t\right)^{\alpha }\cdot \eta _{ij}^{\beta }}{{\scriptscriptstyle \sum _{l\in J_{i}^{k}}}\tau _{il}\left(t\right)^{\alpha }\cdot \eta _{il}^{\beta }}}&{\textrm {si}}\,j\in J_{i}^{k}\\0&{\textrm {si}}\,j\notin J_{i}^{k}\end{matrix}}\right.}$

où J_i^k est la liste des déplacements possibles pour une fourmi k lorsqu’elle se trouve sur une ville i, η_ij la visibilité, qui est égale à l’inverse de la distance de deux villes i et j (1/d_ij) et τ_ij (t) l’intensité de la piste à une itération donnée t. Les deux principaux paramètres contrôlant l’algorithme sont α et β, qui contrôlent l’importance relative de l’intensité et de la visibilité d’une arête.

En pratique, pour que les fourmis explorent des pistes non découvertes, on attribue une probabilité non nulle d'exploration de ces villes « inconnues », contrôlée par le paramètre γ. De cette façon, la probabilité de déplacement s'écrit:

${\displaystyle p_{ij}^{k}\left(t\right)=\left\{{\begin{matrix}{\frac {\gamma +\tau _{ij}\left(t\right)^{\alpha }\cdot \eta _{ij}^{\beta }}{{\scriptscriptstyle \sum _{l\in J_{i}^{k}}}(\gamma +\tau _{il}\left(t\right)^{\alpha }\cdot \eta _{il}^{\beta })}}&{\textrm {si}}\,j\in J_{i}^{k}\\0&{\textrm {si}}\,j\notin J_{i}^{k}\end{matrix}}\right.}$

Une fois la tournée des villes effectuée, une fourmi k dépose une quantité ${\displaystyle \Delta \tau _{ij}^{k}}$ de phéromone sur chaque arête de son parcours :

${\displaystyle \Delta \tau _{ij}^{k}(t)=\left\{{\begin{matrix}{\frac {Q}{L^{k}(t)}}&{\textrm {si}}\,(i,j)\in T^{k}(t)\\0&{\textrm {si}}\,(i,j)\notin T^{k}(t)\end{matrix}}\right.}$

où T^k (t) est la tournée faite par la fourmi k à l’itération t, L^k (t) la longueur du trajet et Q un paramètre de réglage.

À la fin de chaque itération de l’algorithme, les phéromones déposées aux itérations précédentes par les fourmis s’évaporent de :

${\displaystyle \rho \tau _{ij}(t)}$

Et à la fin de l'itération, on a la somme des phéromones qui ne se sont pas évaporées et de celles qui viennent d'être déposées :

${\displaystyle \tau _{ij}(t+1)=(1-\rho )\tau _{ij}(t)+\sum _{k=1}^{m}\Delta \tau _{ij}^{k}(t)}$

où m est le nombre de fourmis utilisées pour l’itération t et ρ un paramètre de réglage.

Une partie des algorithmes (notamment ceux conçus par M. Dorigo et ses collègues) sont maintenant regroupés sous le terme de « Ant Colony Optimisation » (ACO). Ce cadre se limite cependant aux algorithmes construisant des solutions sous la forme de paramètres associés aux composants d'un graphe, à l'aide d'un modèle statistique biaisé.

Une méthode de type ACO suit le schéma algorithmique suivant, paramétré par :

un critère d'arrêt de l’algorithme

un temps de calcul ou un nombre d'itérations alloué dépassé, un seuil d'amélioration des solutions qui n’est plus satisfaisant, ou une combinaison de critères

des heuristiques

(éventuellement) un critère de choix des pistes à explorer ou à éliminer, ...^{[réf. souhaitée]}

une construction des solutions et des pistes de phéromones

dépendant du problème à résoudre et de sa structure

Initialisation des pistes de phéromone ;

Boucler tant que critère d'arrêt non atteint :
 
   construire les solutions composant par composant,
 
   utilisation (facultative) d'une heuristique,
 
   mise à jour des pistes de phéromone ;

Fin de la boucle.

Une variante efficace du système formique est le Max-Min Ant System (MMAS)[6], où seules les meilleures fourmis tracent des pistes et où le dépôt de phéromones est limité par une borne supérieure (empêchant une piste d’être trop renforcée) et une borne inférieure (laissant la possibilité d’être explorée à n’importe quelle solution). Cet algorithme atteint de meilleurs résultats que l’original, et évite notamment une convergence prématurée.

L’autre variante la plus connue est le Ant Colony System (ACS)[7], où à une nouvelle règle de déplacement (appelée « règle pseudo-aléatoire proportionnelle ») s’ajoute un processus de mise à jour « locale » des éléments des pistes de phéromones, l’objectif de ce mécanisme étant d’augmenter la diversification de la recherche.

Il est possible, pour certaines versions, de prouver que l’algorithme est convergent (c’est-à-dire qu’il est capable de trouver l’optimum global en un temps fini). La première preuve de convergence d'un algorithme de colonies de fourmis fut apportée en 2000, pour l’algorithme graph-base ant system, puis pour les algorithmes ACS et MMAS. Comme pour la plupart des métaheuristiques, il est très difficile d’estimer théoriquement la vitesse de convergence.

En 2004, Zlochin et ses collègues ont montré[8] que les algorithmes de type ACO pouvaient être assimilés aux méthodes de descente stochastique de gradient, d'entropie croisée et des algorithmes à estimation de distribution. Ils ont proposé de regrouper ces métaheuristiques sous le terme de « recherche à base de modèle ».

Avec un algorithme de colonies de fourmis, le plus court chemin, au sein d’un graphe, entre deux points A et B, est construit à partir de la combinaison de plusieurs chemins.

Il n’est pas facile de donner une définition précise de ce qu’est ou ce que n’est pas un algorithme de colonies de fourmis, car la définition peut varier selon les auteurs et les usages.

D’une façon très générale, les algorithmes de colonies de fourmis sont considérés comme des métaheuristiques à population, où chaque solution est représentée par une fourmi se déplaçant sur l’espace de recherche. Les fourmis marquent les meilleures solutions, et tiennent compte des marquages précédents pour optimiser leur recherche.

On peut les considérer comme des algorithmes multi-agents probabilistes, utilisant une distribution de probabilité implicite pour effectuer la transition entre chaque itération. Dans leurs versions adaptées à des problèmes combinatoires, ils utilisent une construction itérative des solutions.

D’après certains auteurs, ce qui différencierait les algorithmes de colonies de fourmis d’autres métaheuristiques proches (telles que les algorithmes à estimation de distribution ou l’optimisation par essaim particulaire) serait justement son aspect constructif. En effet, dans les problèmes combinatoires, il est possible que la meilleure solution finisse par être trouvée, alors même qu’aucune fourmi ne l’aura éprouvée effectivement. Ainsi, dans l’exemple du problème du voyageur de commerce, il n’est pas nécessaire qu’une fourmi parcoure effectivement le chemin le plus court : celui-ci peut être construit à partir des segments les plus renforcés des meilleures solutions. Cependant, cette définition peut poser problème dans le cas des problèmes à variables réelles, où aucune structure du voisinage n’existe.

Le comportement collectif des insectes sociaux reste une source d’inspiration pour les chercheurs. La grande diversité d’algorithmes (pour l’optimisation ou non) se réclamant de l’auto-organisation dans les systèmes biologiques a donné lieu au concept d’« intelligence en essaim », qui est un cadre très général, dans lequel s’inscrivent les algorithmes de colonies de fourmis.

On observe en pratique qu’un grand nombre d’algorithmes se réclament d’une inspiration « colonies fourmis », sans toujours partager le cadre général de l’optimisation par colonies de fourmis canonique (ACO). En pratique, l’utilisation d’un échange d’informations entre fourmis via l’environnement (principe dénommé « stigmergie ») suffit à rentrer dans la catégorie des algorithmes de colonies de fourmis. Ce principe a mené certains auteurs à créer le terme d’« optimisation stigmergique »[9].

On trouve ainsi des méthodes s’inspirant de comportements de recherche de nourriture, de tri de larves, de division du travail ou de transport coopératif.

• Insectes sociaux, Intelligence collective, Système complexe.
• Algorithmes à estimation de distribution, descente stochastique de gradient, Entropie croisée, algorithmes équivalents au formalisme ACO.
• Optimisation par essaims particulaires, Algorithme évolutionnaire, méthodes similaires.

• (en) Ant Colony Optimization Home Page, site maintenu par Marco Dorigo, bibliographie, codes sources.
• (en)Une introduction aux algorithmes de colonies de fourmis (version archivée par Internet Archive)
• (en)« Une liste de références bibliographiques sur les fourmis artificielles »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}
• (en) ANT Colony Algorithm Une simulation en Java de l'algorithme de colonies de fourmis avec terrain modifiable. Présentation, dossier et code source téléchargeables.
• (fr) Application d'un algorithme de colonie de fourmis au problème du voyageur de commerce

• Portail de l'informatique théorique
• Portail de l’entomologie