Où puis-je en apprendre davantage sur les optimisations «colonie de fourmis»?

Question

Cela fait un moment que je lis des choses ici et là sur l'utilisation d'une "colonie de fourmis". modèle comme une approche heuristique pour l'optimisation de divers types d'algorithmes. Cependant, je n'ai pas encore trouvé d'article ni de livre qui traite des optimisations de colonie de fourmis de manière préliminaire ou même avec beaucoup de détails. Quelqu'un peut-il m'indiquer des ressources où je peux en apprendre davantage sur cette idée?

Answer 1

Si vous connaissez l'allemand (oui, désolé, un ami et moi avons écrit un introduction avec code sur ce sujet que je trouve moi-même passable. Le texte et le code utilisent l'exemple de TSP pour introduire le concept.

Même si vous ne connaissez pas l'allemand, regardez le code et les formules dans le texte, cela pourrait quand même servir.

Answer 2

lien Wikipedia m'a réellement permis de démarrer. J'ai lu l'article et suis arrivé à coder. Je résolvais une mauvaise variante du problème du voyageur de commerce. C'est une méta-heuristique incroyable. Fondamentalement, tout type de problème de recherche pouvant être inséré dans un graphique (nœuds, arêtes, symétriques ou non) peut être résolu avec un ACO.

Recherchez la différence entre les traces de phéromones globales et locales. Les phéromones locales découragent une génération de fourmis de suivre le même chemin. Ils empêchent le modèle de converger. Les phéromones globales sont des attracteurs et devraient attraper au moins une fourmi par génération. Ils encouragent des chemins optimaux sur plusieurs générations.

La meilleure suggestion que j'ai, est simplement de jouer avec l'algorithme. Configurez un solveur TSP de base et une visualisation de base des colonies. Alors amusez-vous. Travailler avec des fourmis, conceptuellement, c'est vraiment cool. Vous programmez leurs comportements de base, puis vous les libérez. Je les aime même beaucoup. :)

Les ACO sont une forme plus sophistiquée d’algorithmes génétiques. Jouer avec eux. Modifiez leurs comportements de communication et de comportement. Vous commencerez rapidement à voir la programmation réseau / graphique d’une manière totalement différente. C’est leur plus grand avantage, pas la recette que la plupart des gens voient comme.

Vous devez juste jouer avec pour vraiment le comprendre. Livres & amp; Les documents de recherche ne donnent qu’une très bonne compréhension générale. Comme un vélo, il faut juste commencer à rouler. :)

Les ACO sont de loin mon abstraction préférée pour les problèmes de graphes.

Answer 3

National Geographic a écrit un article intéressant il y a quelque temps des théories.

Answer 4

La meilleure ressource pour ces sujets est Google scholar . Je travaille sur les algorithmes d'optimisation Ant Colony depuis un moment. Voici quelques bons articles:

• Optimisation de la colonie de fourmis - Une nouvelle métaheuristique
• Optimisation de la colonie de fourmis - fourmis artificielles en tant que technique de l'intelligence numérique

Il vous suffit de rechercher " Ant Colony " sur Google Scholar .

Recherchez également les articles publiés par Marco. Dorigo .

Answer 5

Je suis surpris que personne n'ait mentionné la bible d'ACO:

Marco Dorigo & amp; Thomas Stützle: Optimisation de la colonie de fourmis

Ce livre est écrit par l’auteur d’ACO et est très lisible. Vous pouvez le prendre à la plage et vous amuser à le lire. Mais c’est aussi la ressource la plus complète de toutes, très utile comme référence lors de la mise en œuvre de la chose.

Vous pouvez lire des extraits de Google Livres .

Une autre grande source de sagesse est la page d'accueil ACO

Answer 6

Voir par exemple, cet article sur scholarpedia.

Il y a également une discussion ici dans le Quel est le moyen le plus efficace de trouver un chemin à travers un petit graphe du monde? question.

Answer 7

À première vue, cela semble être étroitement lié (ou peut-être même à un cas particulier) la Algorithme Metropolis . C'est donc une autre direction possible pour la recherche.

Ajout: Ce fichier PDF inclut une référence au papier Metropolis original de 1953.

Answer 8

J'ai trouvé le page d'accueil d'Eric Rollins et ses différentes implémentations (Haskell, Scala, Erlang, ...) d'un algorithme ACO utile. Et aussi le livre d'Enrique Alba intitulé "Métaheuristiques parallèles: une nouvelle classe d'algorithmes". où vous trouverez un chapitre complet d’explications sur les algorithmes ACO et leurs différents usages.

Hth