September 2008
Table of Contents |
The application of ant colony optimization for solving stochastic optimization problems is one of hot topics in recent years. In this paper, we customize the ant colony optimization algorithms to tackle a stochastic optimization problem, the Probabilistic Traveling Salesman Problem. The proposed customization consists of using an empirical estimation approach to evaluate the cost of the solutions constructed by the ants and integrating the newly proposed estimation-based iterative improvement algorithm as local search. Experimental results on a large number of problem instances show that the customized ant colony optimization algorithms completely outperforms the current best ant colony optimization algorithm tailored to solve the given problem. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithms for the Probabilistic Traveling Salesman Problem.
Keywords: Probabilistic Traveling Salesman Problem, Ant Colony Optimization, Iterative Improvement Algorithm, Empirical Estimation
Experimental set | File |
---|---|
Tuning |
Clustered homogeneous instances (1.6 MB) |
Experimental set | File |
---|---|
Effectiveness of 2.5-opt-EEais in pACS |
PTSPLIB proposed by Bianchi (1.5 MB) |
Estimation-based ant colony system |
Clustered homogeneous instances of size 1000 from DIMACS instance generator (1.6 MB) |
Comparison among estimation-based ACO variants |
Clustered homogeneous instances of size 1000 from DIMACS instance generator (1.6 MB) |
The absolute values for all the results in the form of tables. In these tables, we present the final solution quality and the corresponding computational time for each probabiltiy range. Moreover, in order to test that the observed difference between the cost of the solutions reached by the considered algorithms are significant in a statistical sense, we use a t test and we present the 95% confidence interval obtained from the t-test. The results are composed in a single pdf file: