Name
Abstract | ||
|---|---|---|
Ant colony optimization (ACO) is a promising metaheuristic and a great amount of research has been devoted to its empirical and theoretical analysis. Recently, with the introduction of the hypercube framework, Blum and Dorigo have explicitly raised the issue of the invariance of ACO algorithms to transformation of units. They state (Blum and Dorigo, 2004) that the performance of ACO depends on the scale of the problem instance under analysis. In this paper, we show that the ACO internal state - commonly referred to as the pheromone - indeed depends on the scale of the problem at hand. Nonetheless, we formally prove that this does not affect the sequence of solutions produced by the three most widely adopted algorithms belonging to the ACO family: ant system, MAX-MIN ant system, and ant colony system. For these algorithms, the sequence of solutions does not depend on the scale of the problem instance under analysis. Moreover, we introduce three new ACO algorithms, the internal state of which is independent of the scale of the problem instance considered. These algorithms are obtained as minor variations of ant system, MAX-MIN ant system, and ant colony system. We formally show that these algorithms are functionally equivalent to their original counterparts. That is, for any given instance, these algorithms produce the same sequence of solutions as the original ones. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/TEVC.2007.892762 | IEEE Trans. Evolutionary Computation |
Keywords | Field | DocType |
combinatorial opti- mization,new aco algorithm,ant colony optimization,aco internal state,index terms— ant colony optimization,aco family,ant colony system,internal state,swarm intelligence,problem instance,aco algorithm,weak and strong invariance.,max-min ant system,ant system,monte carlo methods,combinatorial optimization,constraint optimization,feedback,particle swarm optimization,indexing terms,artificial life,algorithm design and analysis,hypercubes,shortest path problem | Particle swarm optimization,Ant colony optimization algorithms,Mathematical optimization,Evolutionary algorithm,Parallel metaheuristic,Swarm intelligence,Combinatorial optimization,Artificial intelligence,Ant colony,Mathematics,Machine learning,Metaheuristic | Journal |
Volume | Issue | ISSN |
11 | 6 | 1089-778X |
Citations | PageRank | References |
22 | 0.89 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mauro Birattari | 1 | 471 | 30.81 |
| P. Pellegrini | 2 | 22 | 0.89 |
| Marco Dorigo | 3 | 14031 | 1211.61 |