NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 16/10/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Topologie

 

Débutants

Géométrie

Graphe

 

Glossaire

Topologie

 

 

INDEX

 

Topologie

 

Logique

Eulérien

Planaire

 Fourmis

Nœuds

 

Sommaire de cette page

>>> Principe

>>> Anglais

 

 

 

 

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).

 

 

 

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

Voir

*         Code Gray

*         Croissance logistique

*         Énigmes et paradoxes

*         Intelligence artificielle

*         JeuxIndex

*         Logique formelle

*         TopologieGlossaire

*         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