Algorithme colonie de fourmis

Édition du: 28/03/2023

INDEX Graphe Topologie Dénombrement Logique Jeux	GRAPHES
	Graphes – Introduction	Arbres – Introduction	Chemin le plus court
	Chemin eulérien	Cinq pays	Voyageur de commerce
	Graphe planaire	Trois maisons	Multiple et diviseurs
	Graphe de Delaunay	Petit monde	Nombres de Delannoy
	Ivrogne	Colonies de fourmis	Nœuds

Faites un double-clic pour un retour en haut de page

Algorithmes de colonies de fourmis

Ant Colony Opimization (ACO)

Étant donné une multitude de chemins qui conduisent d'un point de départ à un point d'arrivée, quel est celui qui est optimal? Une ribambelle de fourmis les explorent et laissent leur trace (phéromone). Certains chemins seront gorgés de phéromones, d'autres moins. D'autant que les phéromones s'évaporent. Conséquences: les chemins préférés sont balisés de phéromone alors que sur les moins empruntés les phéromones se sont évaporées.

1990: apparitions des premiers algorithmes fourmis (Marco Dorigo).

Sommaire de cette page

>>> Principe

>>> Anglais

Débutants

Dénombrement

Glossaire

Combinatoire

Trajet de la fourmi dans le réseau

Principe de l'exploration algorithmique

Le réseau

Prenons le cas du voyageur de commerce: les villes sont les nœuds du graphe et les trajets les arêtes.

· Tous les trajets entre villes sont possibles: le graphe est complètement connecté.

· On tient compte de la longueur entre villes, représentée par la distance entre nœuds.

· On fera vivre une valeur d'intensité de phéromone pour chaque arête pour refléter l'expérience accumulée par les fourmis le long du réseau.

· La méthode de recherche des chemins optimums se fait en lâchant une colonie de fourmis dans le réseau.

L'exploration

· Chaque fourmi part d'une ville au hasard. Elle choisit les villes les plus proches.

· Chaque fourmi conserve une mémoire de son passage en déposant des phéromones lors du trajet de retour (stigmergie).

· Une fourmi tient une solution lorsqu'elle est passée par toutes les villes (nœuds) une seule fois.

· Au tour suivant (construction d'une nouvelle solution), une fourmi choisit un trajet selon un tirage au hasard biaisé par l'intensité des phéromones.

Actualisation

· Quand toutes les fourmis ont réalisé leur construction, les intensités des phéromones sont mises à jour:

· toutes les valeurs sont décrémentées d'un point et

· seules celles correspondant à des parcours de qualité (distances courtes, par exemple) sont augmentées, et cela autant de fois que de bons parcours construits.

Finalisation

· La procédure de construction par les fourmis est répétée jusqu'à satisfaction d'un critère de fin.

Implémentation

· En logiciel, la fourmi est remplacé par un agent logiciel (une fourmi artificielle; software agent). Il s'agit donc d'un algorithme multi-agents réactifs.

· Algorithme assez général (métaheuristique) pour convenir à de nombreuses applications sans changement profond de la procédure d'optimisation.

· On notera la similitude avec les réseaux neuroniques à apprentissage où les recherches pertinentes sont récompensées et conservées.

English corner

· The ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

Suite	· Chemin le plus court · Vocabulaire des graphes · Petit monde · Les fourmis de Bernard Werber – Roman · Graphe – Index
Voir	· Code Gray · Croissance logistique · Énigmes et paradoxes · Intelligence artificielle · Jeux – Index · Logique formelle · Topologie – Glossaire · Tour de Brahmâ
Sites	· Algorithmes de fourmis artificielles: applications à la classification et à l’optimisation – Thèse de 2000 par Nicolas Monmarché (pdf)
Cette page	http://villemin.gerard.free.fr/aMaths/Topologi/aaaGraph/Fourmis.htm