The week's pick
Random Articles
Reseach Article
Modified Ant Colony Optimization Algorithm for Travelling Salesman Problem
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 97 - Number 10 |
| Year of Publication: 2014 |
| Authors: Rohit Chaturvedi, Haider Banka |
10.5120/17043-7353
|
Rohit Chaturvedi, Haider Banka . Modified Ant Colony Optimization Algorithm for Travelling Salesman Problem. International Journal of Computer Applications. 97, 10 ( July 2014), 20-24. DOI=10.5120/17043-7353
Abstract
Limited amount of time and computational resources in industrial domain makes Ant Colony Optimization (ACO) a useful approach to find near optimal solutions in polynomial time for Nondeterministic Polynomial time (NP) problems. For dynamically changing graphs, such as in case of network routing and urban transportation systems which are based on Travelling Salesman Problem (TSP), the ant colony algorithm is superior to simulated annealing and genetic algorithm approaches as it can be run continuously and acclimatize to changes in real time. The objective of this paper is to find a competent method which improves ACO in terms of iteration count and ability to find better solutions for TSP so that it can be used in different areas like industrial and educational, for solving NP problems more efficiently. This paper proposes a modified ant colony optimization (MACO) algorithm which uses the peculiarity of Elitist Ant System (EAS) and Ant Colony System (ACS). Using EAS property, the convergence speed is optimized by additional pheromone deposition on the arcs of the best tour and pseudorandom proportional rule and local pheromone update of ACS tunes the degree of exploration and prevents the algorithm from stagnation. The experiments done on benchmark datasets from TSPLIB manifest clearly that MACO has an upper hand in terms of performance on conventional ACO, ACO-GA and ACO-PSO.
References
- Colorni, A. ; Dorigo, M. ; Maniezzo, V. Distributed optimization by ant colonies. Proceedings of the 1st European Conference on Artificial Life; Varela, F. , Bourgine, P. , Eds. ; Elsevier: Paris, France, 1991; pp 134-142.
- Reinelt, G. The Traveling Salesman: Computational Solutions for TSP Applications, Lecture Notes in Computer Science, Berlin: Springer, 1994, vol. 840.
- TSPLIB - A Travelling Salesman Problem Library. http://www. iwr. uni-heidelberg. de/groups/comopt/ software/TSPLIB95/.
- Dorigo, M. , Maniezzo, V. , and Colorni, A. , The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. Systems, Man Cybernetics, Part B, 1996, vol. 26, no. 1, pp. 29–41.
- Dorigo, M. , and Gambardella, L. M. , Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Trans. Evolutionary Computation, 1997, vol. 1, no. 1, pp. 53–66.
- Baue, A. ; Bullnheimer, B. ; Hartl, R. F. ; et al. An ant colony optimization approach for the single machine total tardiness problem. CEC 99, Proceedings of the 1999 Congress on Evolutionary Computation;1999; Vol. 2, pp 1450-1456.
- Cassillas, J. , Cordon, O. , and Herrera, F. , Learning Fuzzy Rules Using Ant Colony Optimization Algorithms, Proc. of ANTS2000—From Ant Colonies to Artificial Ants: A Series of Int. Workshops on Ant Algorithms, Brussels, 2000, pp. 13–21.
- Bonabeau, E. ; Dorigo, M. ; Theraulaz, G. Inspiration for optimization from social insect behavior. Nature2000, 406, 39-42.
- Krieger, M. J. ; Billeter, J. B. ; Keller, L. Ant-like task allocation and recruitment in cooperative robots. Nature2000, 406, 992-995.
- Wang, Y. ; Xie, J. Y. Ant colony optimization for multicast routing in Circuits and Systems. IEEE: The 2000 IEEE Asia-Pacific Conference; 2000; pp 54-57.
- J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm Intelligence. Morgan Kaufmann, 2001.
- Silva, A. R. M. ; Ramalho, G. L. Ant system for the set covering problem Systems. 2001 IEEE International Conference on Man and Cybernetics;2001; Vol. 5, pp 3129-3133.
- Dorigo, M. and Stutzle, T. The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, in Handbook of Metaheuristics, Glover, F. and Kochenberger, G. , Eds. , Norwell: Kluwer, 2002.
- Xiong, W. Q. ; Wei, P. A kind of ant colony algorithm for function optimization. Machine Learning and Cybernetics. International Conference on Proceedings; 2002; Vol. 1, pp 552-555.
- Gutiahr, W. J. , A Converging ACO Algorithm for Stochastic Combinatorial Optimization, Lecture Notes in Computer Science (Proc. of SAFA-2003 (Stochastic Algorithms: Foundations and Applications)), Berlin: Springer, 2003, no. 2827, pp. 10–25.
- Li, Y. M. ; Xu, Z. B. An ant colony optimization heuristic for solving maximum independent set problems. Fifth International Conference on Computational Intelligence and Multimedia Applications; 2003; pp 206-211.
- Gomez, J. F. ; Khodr, H. M. ; DeOliveira, P. M. ; et al. Ant Colony System Algorithm for the Planning of Primary Distribution Circuits Power Systems. IEEE Transactions on Power Systems2004, 19, 996-1004.
- Dorigo, M. and Stutzle, T. , Ant Colony Optimization, Bradford Book, 2004.
- Gueret, C. , Monmarche, N. , and Slimane, M. , Ants Can Play Music, Lecture Notes in Computer Science (Proc. of IV Int. Workshop on Ant Colony Optimization and Swarm Intelligence ANTS-2004), Berlin: Springer, 2004, no. 3172, pp. 310–317.
- Shtovba, S. D. , Ant Algorithms: Theory and Applications, Programming and Computer Software, Vol. 31, No. 4, 2005, pp. 167-178.
- A. P. Engelbrecht, Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, 2006.
- Nonsiri, Sarayut, and Siriporn Supratid. "Modifying ant colony optimization. " Soft Computing in Industrial Applications, 2008. SMCia'08. IEEE Conference on. IEEE, 2008.
- Hlaing, Z. C. S. S. , and Khine, M. A. , Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm, International Journal of Information and Education Technology, Vol. 1, No. 5, December 2011.
Index Terms
Keywords