Algorithmes d'optimisation des colonies de fourmis - Ant colony optimization algorithms

Le comportement des fourmis a inspiré la technique d'optimisation métaheuristique
Lorsqu'une colonie de fourmis est confrontée au choix d'atteindre sa nourriture par deux voies différentes dont l'une est beaucoup plus courte que l'autre, son choix est totalement aléatoire. Cependant, ceux qui empruntent le chemin le plus court atteignent la nourriture plus rapidement et font donc des allers-retours plus fréquents entre la fourmilière et la nourriture.

En informatique et en recherche opérationnelle , l' algorithme d' optimisation des colonies de fourmis ( ACO ) est une technique probabiliste pour résoudre des problèmes informatiques qui peuvent être réduits à trouver de bons chemins à travers des graphes . Les fourmis artificielles représentent des méthodes multi-agents inspirées du comportement des vraies fourmis. La communication à base de phéromones des fourmis biologiques est souvent le paradigme prédominant utilisé. Les combinaisons de fourmis artificielles et d' algorithmes de recherche locale sont devenues une méthode de choix pour de nombreuses tâches d'optimisation impliquant une sorte de graphique , par exemple, le routage des véhicules et le routage Internet .

Par exemple, l'optimisation des colonies de fourmis est une classe d' algorithmes d' optimisation modélisés sur les actions d'une colonie de fourmis . Des « fourmis » artificielles (par exemple des agents de simulation) localisent les solutions optimales en se déplaçant dans un espace de paramètres représentant toutes les solutions possibles. Les vraies fourmis déposent des phéromones qui se dirigent vers les ressources tout en explorant leur environnement. Les « fourmis » simulées enregistrent de la même manière leurs positions et la qualité de leurs solutions, de sorte que, dans les itérations ultérieures de la simulation, davantage de fourmis trouvent de meilleures solutions. Une variante de cette approche est l'algorithme des abeilles , qui est plus analogue aux schémas de recherche de nourriture de l' abeille mellifère , un autre insecte social.

Cet algorithme fait partie de la famille des algorithmes de colonies de fourmis, dans les méthodes d' intelligence en essaim , et il constitue des optimisations métaheuristiques . Initialement proposé par Marco Dorigo en 1992 dans sa thèse de doctorat, le premier algorithme visait à rechercher un chemin optimal dans un graphe, basé sur le comportement des fourmis cherchant un chemin entre leur colonie et une source de nourriture. L'idée originale s'est depuis diversifiée pour résoudre une classe plus large de problèmes numériques, et en conséquence, plusieurs problèmes ont émergé, s'appuyant sur divers aspects du comportement des fourmis. Dans une perspective plus large, ACO effectue une recherche basée sur un modèle et partage certaines similitudes avec l' estimation des algorithmes de distribution .

Aperçu

Dans le monde naturel, les fourmis de certaines espèces errent (initialement) au hasard et, lorsqu'elles trouvent de la nourriture, retournent dans leur colonie tout en traçant des pistes de phéromones . Si d'autres fourmis trouvent un tel chemin, il est probable qu'elles ne continueront pas à voyager au hasard, mais qu'elles suivront plutôt la piste, la revenant et la renforçant si elles finissent par trouver de la nourriture (voir Communication avec les fourmis ).

Au fil du temps, cependant, la traînée de phéromone commence à s'évaporer, réduisant ainsi sa force d'attraction. Plus il faut de temps à une fourmi pour parcourir le chemin et revenir, plus les phéromones ont de temps pour s'évaporer. Un chemin court, en comparaison, est parcouru plus fréquemment, et ainsi la densité de phéromones devient plus élevée sur les chemins plus courts que sur les plus longs. L'évaporation des phéromones a également l'avantage d'éviter la convergence vers une solution localement optimale. S'il n'y avait pas du tout d'évaporation, les chemins choisis par les premières fourmis auraient tendance à être excessivement attractifs pour les suivantes. Dans ce cas, l'exploration de l'espace des solutions serait contrainte. L'influence de l'évaporation des phéromones dans les systèmes de fourmis réelles n'est pas claire, mais elle est très importante dans les systèmes artificiels.

Le résultat global est que lorsqu'une fourmi trouve un bon (c'est-à-dire un court) chemin de la colonie à une source de nourriture, les autres fourmis sont plus susceptibles de suivre ce chemin, et un retour positif conduit finalement de nombreuses fourmis à suivre un seul chemin. L'idée de l'algorithme de colonie de fourmis est d'imiter ce comportement avec des "fourmis simulées" se promenant autour du graphique représentant le problème à résoudre.

Réseaux ambiants d'objets intelligents

De nouveaux concepts sont nécessaires puisque « l'intelligence » n'est plus centralisée mais se retrouve dans tous les objets minuscules. Les concepts anthropocentriques sont connus pour conduire à la production de systèmes d'information dans lesquels le traitement des données, les unités de contrôle et les forces de calcul sont centralisés. Ces unités centralisées ont continuellement augmenté leurs performances et peuvent être comparées au cerveau humain. Le modèle du cerveau est devenu la vision ultime des ordinateurs. Les réseaux ambiants d'objets intelligents et, tôt ou tard, une nouvelle génération de systèmes d'information encore plus diffusés et basés sur les nanotechnologies, changeront profondément ce concept. Les petits appareils comparables à des insectes ne disposent pas à eux seuls d'une grande intelligence. En effet, leur intelligence peut être qualifiée d'assez limitée. Il est par exemple impossible d'intégrer une calculatrice performante et capable de résoudre tout type de problème mathématique dans une biopuce implantée dans le corps humain ou intégrée dans une étiquette intelligente conçue pour tracer des articles commerciaux. Cependant, une fois que ces objets sont interconnectés, ils disposent d'une forme d'intelligence qui peut être comparée à une colonie de fourmis ou d'abeilles. Dans le cas de certains problèmes, ce type d'intelligence peut être supérieur au raisonnement d'un système centralisé semblable au cerveau.

La nature offre plusieurs exemples de la façon dont de minuscules organismes, s'ils suivent tous la même règle de base, peuvent créer une forme d' intelligence collective au niveau macroscopique. Les colonies d'insectes sociaux illustrent parfaitement ce modèle très différent des sociétés humaines. Ce modèle est basé sur la coopération d'unités indépendantes au comportement simple et imprévisible. Ils se déplacent dans leur environnement pour effectuer certaines tâches et ne disposent que d'une quantité très limitée d'informations pour le faire. Une colonie de fourmis, par exemple, représente de nombreuses qualités qui peuvent également s'appliquer à un réseau d'objets ambiants. Les colonies de fourmis ont une très grande capacité d'adaptation aux changements de l'environnement ainsi qu'une énorme force pour faire face aux situations où un individu ne parvient pas à accomplir une tâche donnée. Une telle flexibilité serait également très utile pour les réseaux mobiles d'objets en perpétuelle évolution. Les paquets d'informations qui passent d'un ordinateur à un objet numérique se comportent de la même manière que les fourmis le feraient. Ils parcourent le réseau et passent d'un nœud à l'autre avec l'objectif d'arriver le plus rapidement possible à leur destination finale.

Système de phéromone artificielle

La communication à base de phéromones est l'un des moyens de communication les plus efficaces qui est largement observé dans la nature. La phéromone est utilisée par les insectes sociaux tels que les abeilles, les fourmis et les termites ; à la fois pour les communications inter-agents et agents-essaim. En raison de sa faisabilité, des phéromones artificielles ont été adoptées dans des systèmes robotiques multi-robots et en essaim. La communication basée sur les phéromones a été mise en œuvre par différents moyens tels que des moyens chimiques ou physiques (étiquettes RFID, lumière, son). Cependant, ces implémentations n'étaient pas en mesure de reproduire tous les aspects des phéromones comme on le voit dans la nature.

L'utilisation de la lumière projetée a été présentée dans un article de l'IEEE de 2007 par Garnier, Simon et al. comme dispositif expérimental pour étudier la communication à base de phéromones avec des micro-robots autonomes. Une autre étude a présenté un système dans lequel des phéromones étaient mises en œuvre via un écran LCD horizontal sur lequel les robots se déplaçaient, les robots ayant des capteurs de lumière orientés vers le bas pour enregistrer les motifs sous eux.

Algorithme et formules

Dans les algorithmes d'optimisation des colonies de fourmis, une fourmi artificielle est un simple agent de calcul qui recherche de bonnes solutions à un problème d'optimisation donné. Pour appliquer un algorithme de colonie de fourmis, le problème d'optimisation doit être converti en problème de recherche du chemin le plus court sur un graphique pondéré. Dans la première étape de chaque itération, chaque fourmi construit stochastiquement une solution, c'est-à-dire l'ordre dans lequel les arêtes du graphe doivent être suivies. Dans la deuxième étape, les chemins trouvés par les différentes fourmis sont comparés. La dernière étape consiste à mettre à jour les niveaux de phéromones sur chaque bord.

procedure ACO_MetaHeuristic is
    while not terminated do
        generateSolutions()
        daemonActions()
        pheromoneUpdate()
    repeat
end procedure

Sélection de bord

Chaque fourmi doit construire une solution pour se déplacer dans le graphique. Pour sélectionner le prochain bord de son tour, une fourmi considérera la longueur de chaque bord disponible à partir de sa position actuelle, ainsi que le niveau de phéromone correspondant. A chaque étape de l'algorithme, chaque fourmi passe d'un état à un état , correspondant à une solution intermédiaire plus complète. Ainsi, chaque fourmi calcule un ensemble d'expansions réalisables jusqu'à son état actuel à chaque itération, et se déplace vers l'une d'entre elles en probabilité. Pour ant , la probabilité de passer d'un état à l'autre dépend de la combinaison de deux valeurs, l' attractivité du mouvement, calculée par une heuristique indiquant la désirabilité a priori de ce mouvement et le niveau de suivi du mouvement, indiquant à quel point il est compétent. a été dans le passé de faire ce mouvement particulier. Le niveau de piste représente une indication a posteriori de l'opportunité de ce mouvement.

En général, la fourmi se déplace d'état en état avec probabilité

est la quantité de phéromone déposée pour la transition de l'état à , 0 ≤ est un paramètre pour contrôler l'influence de , est la désirabilité de la transition d'état ( connaissance a priori , typiquement , où est la distance) et ≥ 1 est un paramètre pour contrôler la influence de . et représentent le niveau de piste et l'attractivité pour les autres transitions d'état possibles.

Mise à jour des phéromones

Les pistes sont généralement mises à jour lorsque toutes les fourmis ont terminé leur solution, augmentant ou diminuant le niveau des pistes correspondant aux mouvements qui faisaient respectivement partie des "bonnes" ou "mauvaises" solutions. Un exemple de règle de mise à jour globale des phéromones est

où est la quantité de phéromone déposée pour une transition d'état , est le coefficient d'évaporation de la phéromone , est le nombre de fourmis et est la quantité de phéromone déposée par la fourmi, généralement donnée pour un problème TSP (avec des mouvements correspondant aux arcs du graphique) par

où est le coût du tour de la fourmi (typiquement la durée) et est une constante.

Extensions communes

Voici quelques-unes des variantes les plus populaires des algorithmes ACO.

Système de fourmis (AS)

Le système des fourmis est le premier algorithme ACO. Cet algorithme correspond à celui présenté ci-dessus. Il a été développé par Dorigo.

Système de colonie de fourmis (ACS)

Dans l'algorithme du système de colonies de fourmis, le système de fourmis d'origine a été modifié sous trois aspects :

  1. La sélection des bords est biaisée vers l'exploitation (c'est-à-dire en favorisant la probabilité de sélectionner les bords les plus courts avec une grande quantité de phéromone) ;
  2. Lors de la construction d'une solution, les fourmis modifient le niveau de phéromone des bords qu'elles sélectionnent en appliquant une règle de mise à jour locale des phéromones ;
  3. À la fin de chaque itération, seule la meilleure fourmi est autorisée à mettre à jour les pistes en appliquant une règle de mise à jour globale des phéromones modifiée.

Système de fourmis élitiste

Dans cet algorithme, la meilleure solution globale dépose de la phéromone sur sa piste après chaque itération (même si cette piste n'a pas été revisitée), avec toutes les autres fourmis. La stratégie élitiste a pour objectif de diriger la recherche de toutes les fourmis pour construire une solution pour contenir les liens de la meilleure route actuelle.

Système de fourmis max-min (MMAS)

Cet algorithme contrôle les quantités maximales et minimales de phéromones sur chaque piste. Seul le meilleur tour mondial ou le meilleur tour d'itération est autorisé à ajouter des phéromones à son parcours. Pour éviter la stagnation de l'algorithme de recherche, la plage de quantités de phéromones possibles sur chaque piste est limitée à un intervalle [τ maxmin ]. Toutes les arêtes sont initialisées à max pour forcer une exploration plus poussée des solutions. Les traînées sont réinitialisées à max à l'approche de la stagnation.

Système de fourmis basé sur le rang (ASrank)

Toutes les solutions sont classées en fonction de leur longueur. Seul un nombre fixe des meilleures fourmis de cette itération sont autorisés à mettre à jour leurs essais. La quantité de phéromone déposée est pondérée pour chaque solution, de sorte que les solutions avec des chemins plus courts déposent plus de phéromones que les solutions avec des chemins plus longs.

Colonie de fourmis orthogonale continue (COAC)

Le mécanisme de dépôt de phéromone du COAC est de permettre aux fourmis de rechercher des solutions de manière collaborative et efficace. En utilisant une méthode de conception orthogonale, les fourmis dans le domaine réalisable peuvent explorer les régions choisies rapidement et efficacement, avec une capacité et une précision de recherche globale améliorées. La méthode de conception orthogonale et la méthode d'ajustement du rayon adaptatif peuvent également être étendues à d'autres algorithmes d'optimisation pour offrir des avantages plus larges dans la résolution de problèmes pratiques.

Optimisation récursive des colonies de fourmis

C'est une forme récursive de système de fourmis qui divise l'ensemble du domaine de recherche en plusieurs sous-domaines et résout l'objectif sur ces sous-domaines. Les résultats de tous les sous-domaines sont comparés et les meilleurs d'entre eux sont promus au niveau suivant. Les sous-domaines correspondant aux résultats sélectionnés sont encore subdivisés et le processus est répété jusqu'à ce qu'une sortie de la précision souhaitée soit obtenue. Cette méthode a été testée sur des problèmes d'inversion géophysique mal posés et fonctionne bien.

Convergence

Pour certaines versions de l'algorithme, il est possible de prouver qu'il est convergent (c'est-à-dire qu'il est capable de trouver l'optimum global en temps fini). La première preuve de convergence pour un algorithme de colonie de fourmis a été faite en 2000, l'algorithme de système de fourmis basé sur des graphes, et plus tard pour les algorithmes ACS et MMAS. Comme la plupart des métaheuristiques , il est très difficile d'estimer la vitesse théorique de convergence. Une analyse des performances d'un algorithme de colonie continue de fourmis en ce qui concerne ses différents paramètres (stratégie de sélection des bords, métrique de mesure de distance et taux d'évaporation des phéromones) a montré que ses performances et son taux de convergence sont sensibles aux valeurs des paramètres choisis, et en particulier à la valeur du taux d'évaporation des phéromones. En 2004, Zlochin et ses collègues ont montré que les algorithmes de type COAC pouvaient être assimilés à des méthodes de descente de gradient stochastique , sur l' entropie croisée et l'algorithme d'estimation de la distribution . Ils ont proposé ces métaheuristiques comme un « modèle basé sur la recherche ».

Applications

Problème de sac à dos : Les fourmis préfèrent la plus petite goutte de miel au sucre plus abondant, mais moins nutritif

Les algorithmes d'optimisation des colonies de fourmis ont été appliqués à de nombreux problèmes d' optimisation combinatoire , allant de l'affectation quadratique au repliement des protéines ou aux véhicules de routage et de nombreuses méthodes dérivées ont été adaptées aux problèmes dynamiques dans les variables réelles, les problèmes stochastiques, les multi-cibles et les implémentations parallèles . Il a également été utilisé pour produire des solutions quasi optimales au problème du voyageur de commerce . Ils ont un avantage sur les approches de recuit simulé et d'algorithme génétique de problèmes similaires lorsque le graphe peut changer de manière dynamique ; l'algorithme de colonie de fourmis peut être exécuté en continu et s'adapter aux changements en temps réel. Cela présente un intérêt pour le routage des réseaux et les systèmes de transport urbain.

Le premier algorithme ACO s'appelait le système des fourmis et visait à résoudre le problème du voyageur de commerce, dans lequel l'objectif est de trouver le trajet aller-retour le plus court pour relier une série de villes. L'algorithme général est relativement simple et basé sur un ensemble de fourmis, chacune effectuant l'un des allers-retours possibles le long des villes. A chaque étape, la fourmi choisit de se déplacer d'une ville à l'autre selon quelques règles :

  1. Il doit visiter chaque ville exactement une fois ;
  2. Une ville lointaine a moins de chance d'être choisie (la visibilité) ;
  3. Plus la piste de phéromone tracée sur un bord entre deux villes est intense, plus la probabilité que ce bord soit choisi est grande ;
  4. Ayant terminé son voyage, la fourmi dépose plus de phéromones sur tous les bords qu'elle a traversés, si le voyage est court ;
  5. Après chaque itération, des traînées de phéromones s'évaporent.
Aco TSP.svg

Problème d'ordonnancement

  • Problème de commande séquentielle (SOP)
  • Problème d' ordonnancement de l'atelier (JSP)
  • Problème d' ordonnancement en magasin ouvert (OSP)
  • Problème d'atelier de flux de permutation (PFSP)
  • Problème de retard total sur une seule machine (SMTTP)
  • Problème de retard total pondéré sur une seule machine (SMTWTP)
  • Problème de planification de projet à ressources limitées (RCPSP)
  • Problème d'ordonnancement groupe-boutique (GSP)
  • Problème de retard total sur une seule machine avec des temps de configuration dépendants de la séquence (SMTTPDST)
  • Problème d'ordonnancement d'atelier en plusieurs étapes (MFSP) avec des temps d'installation/de changement dépendant de la séquence

Problème de tournée de véhicule

  • Problème de tournées de véhicules avec capacité (CVRP)
  • Problème de tournées de véhicules multi-dépôts (MDVRP)
  • Problème de tournée de véhicule d'époque (PVRP)
  • Problème de routage de véhicule de livraison fractionné (SDVRP)
  • Problème de tournées de véhicules stochastiques (SVRP)
  • Problème de tournée de véhicule avec enlèvement et livraison (VRPPD)
  • Problème de tournées de véhicules avec fenêtres horaires (VRPTW)
  • Problème d'itinéraire de véhicule dépendant du temps avec des fenêtres de temps (TDVRPTW)
  • Problème de tournées de véhicules avec des fenêtres de temps et plusieurs agents de service (VRPTWMS)

Problème d'affectation

Définir le problème

  • Définir le problème de couverture (SCP)
  • Problème de partition (SPP)
  • Problème de partition d'arbre de graphe sous contrainte de poids (WCGTPP)
  • Problème d'arbre à l-cardinalité pondéré en arc (AWlCTP)
  • Problème de sac à dos multiple (MKP)
  • Problème d'ensemble indépendant maximum (MIS)

Problème de dimensionnement des dispositifs dans la conception physique de la nanoélectronique

  • L'optimisation basée sur l'optimisation des colonies de fourmis (ACO) du circuit amplificateur de détection à base de CMOS 45 nm pourrait converger vers des solutions optimales en un temps très minimal.
  • La synthèse de circuits réversibles basée sur l'optimisation des colonies de fourmis (ACO) pourrait améliorer considérablement l'efficacité.

Optimisation et synthèse d'antennes

Vibrateurs de bouclage 10×10, synthétisés au moyen de l'algorithme ACO
Vibrateurs Unloopback 10×10, synthétisés au moyen de l'algorithme ACO

Pour optimiser la forme des antennes, des algorithmes de colonie de fourmis peuvent être utilisés. A titre d'exemple, on peut considérer des antennes RFID-tags basées sur des algorithmes de colonie de fourmis (ACO), des vibrateurs loopback et unloopback 10×10

Traitement d'image

L'algorithme ACO est utilisé dans le traitement d'images pour la détection des contours d'images et la liaison des contours.

  • Détection des contours :

Le graphique ici est l'image 2-D et les fourmis traversent à partir d'un pixel déposant une phéromone. Le mouvement des fourmis d'un pixel à l'autre est dirigé par la variation locale des valeurs d'intensité de l'image. Ce mouvement provoque le dépôt de la densité la plus élevée de la phéromone sur les bords.

Voici les étapes impliquées dans la détection des contours à l'aide de l'ACO :

Étape 1 : Initialisation :
placez au hasard des fourmis sur l'image où . Les matrices de phéromones sont initialisées avec une valeur aléatoire. Le défi majeur dans le processus d'initialisation est de déterminer la matrice heuristique.

Il existe différentes méthodes pour déterminer la matrice heuristique. Pour l'exemple ci-dessous, la matrice heuristique a été calculée sur la base des statistiques locales : les statistiques locales à la position du pixel (i, j).

Où est l'image de taille , qui est un facteur de normalisation

peut être calculé à l'aide des fonctions suivantes : Le paramètre de chacune des fonctions ci-dessus ajuste les formes respectives des fonctions. Étape 2 Processus de construction : Le mouvement de la fourmi est basé sur 4 pixels connectés ou 8 pixels connectés . La probabilité avec laquelle la fourmi se déplace est donnée par l'équation de probabilité Étape 3 et Étape 5 Processus de mise à jour : La matrice de phéromones est mise à jour deux fois. à l'étape 3, la traînée de la fourmi (donnée par ) est mise à jour tandis que, comme à l'étape 5, le taux d'évaporation de la traînée est mis à jour, ce qui est donné par l'équation ci-dessous. , où est le coefficient de désintégration de la phéromone









Étape 7 Processus de décision :
Une fois que les fourmis K se sont déplacées d'une distance fixe L pour N itérations, la décision s'il s'agit d'une arête ou non est basée sur le seuil T sur la matrice de phéromonesτ. Le seuil pour l'exemple ci-dessous est calculé sur la base de la méthode d'Otsu .

Bord de l'image détecté à l'aide de l'ACO :
Les images ci-dessous sont générées à l'aide de différentes fonctions données par l'équation (1) à (4).

(a) Image originale (b) Image générée à l'aide de l'équation (1) (c) Image générée à l'aide de l'équation (2) (d) Image générée à l'aide de l'équation (3) (e) Image générée à l'aide de l'équation (4).jpg
  • Liaison de périphérie : ACO s'est également avéré efficace dans les algorithmes de liaison de périphérie.

Autres applications

Difficulté de définition

Aco shortpath.svg

Avec un algorithme ACO, le chemin le plus court dans un graphe, entre deux points A et B, est construit à partir d'une combinaison de plusieurs chemins. Il n'est pas facile de donner une définition précise de quel algorithme est ou n'est pas une colonie de fourmis, car la définition peut varier selon les auteurs et les usages. D'une manière générale, les algorithmes de colonie de fourmis sont considérés comme des métaheuristiques peuplées, chaque solution étant représentée par une fourmi se déplaçant dans l'espace de recherche. Les fourmis marquent les meilleures solutions et tiennent compte des marquages ​​antérieurs pour optimiser leur recherche. Ils peuvent être vus comme des algorithmes multi-agents probabilistes utilisant une distribution de probabilité pour effectuer la transition entre chaque itération . Dans leurs versions pour les problèmes combinatoires, ils utilisent une construction itérative de solutions. Selon certains auteurs, ce qui distingue les algorithmes ACO d'autres apparentés (comme les algorithmes d'estimation de la distribution ou l'optimisation d'essaim de particules) est précisément leur aspect constructif. Dans les problèmes combinatoires, il est possible que la meilleure solution soit finalement trouvée, même si aucune fourmi ne s'avérerait efficace. Ainsi, dans l'exemple du problème du voyageur de commerce, il n'est pas nécessaire qu'une fourmi parcoure réellement le chemin le plus court : le chemin le plus court peut être construit à partir des segments les plus forts des meilleures solutions. Cependant, cette définition peut être problématique dans le cas de problèmes à variables réelles, où aucune structure de « voisins » n'existe. Le comportement collectif des insectes sociaux reste une source d'inspiration pour les chercheurs. La grande variété d'algorithmes (d'optimisation ou non) cherchant à s'auto-organiser dans les systèmes biologiques a conduit au concept d'« intelligence en essaim », qui est un cadre très général dans lequel s'intègrent les algorithmes de colonie de fourmis.

Algorithmes de stigmatisation

Il existe en pratique un grand nombre d'algorithmes se réclamant des « colonies de fourmis », sans toujours partager le cadre général de l'optimisation par colonies de fourmis canoniques. En pratique, le recours à un échange d'informations entre fourmis via l'environnement (principe appelé « stigmergie ») est jugé suffisant pour qu'un algorithme appartienne à la classe des algorithmes de colonie de fourmis. Ce principe a conduit certains auteurs à créer le terme « valeur » pour organiser des méthodes et des comportements basés sur la recherche de nourriture, le tri des larves, la division du travail et le transport coopératif.

Méthodes associées

Algorithmes génétiques (AG)
Ceux-ci maintiennent un pool de solutions plutôt qu'une seule. Le processus de recherche de solutions supérieures imite celui de l'évolution, les solutions étant combinées ou mutées pour modifier le pool de solutions, les solutions de qualité inférieure étant rejetées.
Algorithme d'estimation de la distribution (EDA)
Un algorithme évolutif qui substitue les opérateurs de reproduction traditionnels par des opérateurs guidés par modèle. De tels modèles sont appris de la population en utilisant des techniques d'apprentissage automatique et représentés sous forme de modèles graphiques probabilistes, à partir desquels de nouvelles solutions peuvent être échantillonnées ou générées à partir d'un croisement guidé.
Recuit simulé (SA)
Une technique d'optimisation globale connexe qui traverse l'espace de recherche en générant des solutions voisines de la solution actuelle. Un voisin supérieur est toujours accepté. Un voisin inférieur est accepté de manière probabiliste en fonction de la différence de qualité et d'un paramètre de température. Le paramètre de température est modifié au fur et à mesure que l'algorithme progresse pour modifier la nature de la recherche.
Optimisation réactive de la recherche
Se concentre sur la combinaison de l'apprentissage automatique et de l'optimisation, en ajoutant une boucle de rétroaction interne pour ajuster automatiquement les paramètres libres d'un algorithme aux caractéristiques du problème, de l'instance et de la situation locale autour de la solution actuelle.
Recherche Tabou (TS)
Similaire au recuit simulé en ce sens que les deux traversent l'espace des solutions en testant les mutations d'une solution individuelle. Alors que le recuit simulé ne génère qu'une seule solution mutée, la recherche tabou génère de nombreuses solutions mutées et se déplace vers la solution avec la plus faible fitness de celles générées. Pour empêcher le cyclisme et encourager un plus grand mouvement dans l'espace de solution, une liste taboue est maintenue de solutions partielles ou complètes. Il est interdit de passer à une solution qui contient des éléments de la liste tabou, qui est mise à jour au fur et à mesure que la solution traverse l'espace des solutions.
Système immunitaire artificiel (AIS)
Modelé sur le système immunitaire des vertébrés.
Optimisation de l'essaim de particules (PSO)
Une méthode d' intelligence en essaim .
Gouttes d'eau intelligentes (IWD)
Un algorithme d'optimisation en essaim basé sur des gouttes d'eau naturelles s'écoulant dans les rivières
Algorithme de recherche gravitationnelle (GSA)
Une méthode d' intelligence en essaim .
Méthode de regroupement des colonies de fourmis (ACCM)
Une méthode qui utilise l'approche de clustering, étendant l'ACO.
Recherche de diffusion stochastique (SDS)
Une technique de recherche et d'optimisation globale probabiliste basée sur des agents la mieux adaptée aux problèmes où la fonction objectif peut être décomposée en plusieurs fonctions partielles indépendantes.

Histoire

Les inventeurs sont Frans Moyson et Bernard Manderick . Les pionniers du domaine incluent Marco Dorigo , Luca Maria Gambardella .

Chronologie des algorithmes COA

Chronologie des algorithmes d'optimisation des colonies de fourmis.

  • 1959, Pierre-Paul Grassé invente la théorie de la stigmergie pour expliquer le comportement de nidification des termites ;
  • 1983, Deneubourg et ses collègues étudient le comportement collectif des fourmis ;
  • 1988, et Moyson Manderick ont ​​un article sur l' auto-organisation chez les fourmis ;
  • 1989, les travaux de Goss, Aron, Deneubourg et Pasteels sur le comportement collectif des fourmis argentines , qui donneront l'idée d'algorithmes d'optimisation des colonies de fourmis ;
  • 1989, mise en place d'un modèle de comportement alimentaire par Ebling et ses collègues ;
  • 1991, M. Dorigo a proposé le système des fourmis dans sa thèse de doctorat (publiée en 1992). Un rapport technique extrait de la thèse et co-écrit par V. Maniezzo et A. Colorni a été publié cinq ans plus tard ;
  • 1994, Appleby et Steward of British Telecommunications Plc publient la première application aux réseaux de télécommunications
  • 1995, Gambardella et Dorigo ont proposé ant-q , la version préliminaire du système de colonie de fourmis comme première estension du système de fourmis ;.
  • 1996, Gambardella et Dorigo ont proposé un système de colonie de fourmis
  • 1996, publication de l'article sur le système des fourmis ;
  • 2000, Hoos et Stützle inventent le système de fourmis max-min ;
  • 1997, Dorigo et Gambardella ont proposé un système de colonie de fourmis hybridé avec une recherche locale ;
  • 1997, Schoonderwoerd et ses collègues ont publié une application améliorée aux réseaux de télécommunication ;
  • 1998, Dorigo lance la première conférence dédiée aux algorithmes ACO ;
  • 1998, Stützle propose des premières implémentations parallèles ;
  • 1999, Gambardella, Taillard et Agazzi ont proposé macs-vrptw , premier système multi-colonies appliqué aux problèmes de tournées de véhicules avec fenêtres temporelles,
  • 1999, Bonabeau, Dorigo et Theraulaz publient un livre traitant principalement des fourmis artificielles
  • 2000, numéro spécial de la revue Future Generation Computer Systems sur les algorithmes des fourmis
  • 2000, premières applications à l' ordonnancement , à la séquence d'ordonnancement et à la satisfaction de contraintes ;
  • 2000, Gutjahr fournit la première preuve de convergence pour un algorithme de colonies de fourmis
  • 2001, première utilisation des algorithmes COA par les entreprises ( Eurobios et AntOptima ) ;
  • 2001, Iredi et ses collègues ont publié le premier algorithme multi-objectifs
  • 2002, premières applications dans la conception d'horaires, réseaux bayésiens ;
  • 2002, Bianchi et ses collègues ont suggéré le premier algorithme pour le problème stochastique ;
  • 2004, Dorigo et Stützle publient le livre Ant Colony Optimization avec MIT Press
  • 2004, Zlochin et Dorigo montrent que certains algorithmes sont équivalents à la descente de gradient stochastique , la méthode d'entropie croisée et des algorithmes pour estimer la distribution
  • 2005, premières applications aux problèmes de repliement des protéines .
  • 2012, Prabhakar et ses collègues publient des recherches sur le fonctionnement de fourmis individuelles communiquant en tandem sans phéromones, reflétant les principes de l'organisation des réseaux informatiques. Le modèle de communication a été comparé au Transmission Control Protocol .
  • 2016, première application à la conception de séquences peptidiques.
  • 2017, intégration réussie de la méthode d'aide à la décision multicritères PROMETHEE dans l'algorithme ACO ( algorithme HUMANT ).

Les références

Publications (sélectionnées)

Liens externes