Abstract
The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.
Original language | English |
---|---|
Pages (from-to) | 223-242 |
Number of pages | 20 |
Journal | Swarm Intelligence |
Volume | 3 |
Issue number | 3 |
DOIs | |
State | Published - 2009 |
Externally published | Yes |
Funding
Acknowledgements The authors thank Leonora Bianchi for providing the source code of pACS+1-shift. This research has been supported by COMP2SYS, an Early Stage Training project funded by the European Commission within the Marie Curie Actions program (MEST-CT-2004-505079), and by ANTS and META-X, which are ARC projects funded by the French Community of Belgium. The authors acknowledge support from the fund for scientific research F.R.S.-FNRS of the French Community of Belgium, of which PB and ZY are research fellows, MB and TS are research associates, and MD is a research director.
Keywords
- Ant colony optimization
- Empirical estimation
- Estimation-based local search
- Probabilistic traveling salesman problem