The population-based ant colony optimization algorithm (P-ACO) differs from other ACO algorithms through its implementation of the pheromone update management. P-ACO keeps track of a population of solutions, which serves as an archive of solutions generated by the ants’ colony. Pheromone updates in P-ACO are only done based on solutions that enter or leave the solution archive. The population-based scheme reduces considerably the computation time needed for the pheromone update when compared to ACO algorithms such as Ant System. In this work, we study P-ACO’s behavior for solving the traveling salesman problem and the quadratic assignment problem. In particular, we investigate the impact of a local search on P-ACO parameters and performance. The results clearly show that P-ACO is a very competitive tool in which its parameters and behavior depend strongly on the problem tackled and whether or not a local search is used.
Titolo: | A detailed analysis of the population-based ant colony optimization algorithm for the TSP and the QAP |
Autore/i: | S. M. Oliveira; M. S. Hussin; T. Stuetzle; ROLI, ANDREA; M. Dorigo |
Autore/i Unibo: | |
Anno: | 2011 |
Titolo del libro: | GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation |
Pagina iniziale: | 13 |
Pagina finale: | 14 |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1145/2001858.2001866 |
Abstract: | The population-based ant colony optimization algorithm (P-ACO) differs from other ACO algorithms through its implementation of the pheromone update management. P-ACO keeps track of a population of solutions, which serves as an archive of solutions generated by the ants’ colony. Pheromone updates in P-ACO are only done based on solutions that enter or leave the solution archive. The population-based scheme reduces considerably the computation time needed for the pheromone update when compared to ACO algorithms such as Ant System. In this work, we study P-ACO’s behavior for solving the traveling salesman problem and the quadratic assignment problem. In particular, we investigate the impact of a local search on P-ACO parameters and performance. The results clearly show that P-ACO is a very competitive tool in which its parameters and behavior depend strongly on the problem tackled and whether or not a local search is used. |
Data prodotto definitivo in UGOV: | 27-giu-2013 |
Appare nelle tipologie: | 4.02 Riassunto (Abstract) |