In this paper we consider Max-Min and Ant Colony System. They are generally recognized to be the best performing algorithms of the Ant Colony Optimization family. They are characterized by a quite different way for dealing with the pheromone trail. We propose an experimental analysis for observing whether this difference impacts significantly on the characteristics of the pheromone distributions produced during the runs. The results obtained are analyzed by using some concepts derived by the literature on small-world networks. It comes out that ants actually build small-world pheromone graphs during their runs. This behavior is interpreted here as a sort of decomposition of the instances tackled.

The Small World of Pheromone Trails

ELLERO, Andrea;PELLEGRINI, Paola
2008-01-01

Abstract

In this paper we consider Max-Min and Ant Colony System. They are generally recognized to be the best performing algorithms of the Ant Colony Optimization family. They are characterized by a quite different way for dealing with the pheromone trail. We propose an experimental analysis for observing whether this difference impacts significantly on the characteristics of the pheromone distributions produced during the runs. The results obtained are analyzed by using some concepts derived by the literature on small-world networks. It comes out that ants actually build small-world pheromone graphs during their runs. This behavior is interpreted here as a sort of decomposition of the instances tackled.
2008
Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science,
File in questo prodotto:
File Dimensione Formato  
PellegriniElleroAnts2008.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso gratuito (solo visione)
Dimensione 404.63 kB
Formato Adobe PDF
404.63 kB Adobe PDF Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/23658
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact