|
Ant Colony Optimization (ACO) For The Traveling Salesman Problem (TSP) Using Partitioning
[Full Text]
AUTHOR(S)
Alok Bajpai, Raghav Yadav
KEYWORDS
Index Terms: Ant Colony Optimization (ACO), Mathematical Model of ACS, Traveling Salesman Problem (TSP), stigmergic communication, Candidate List, local optimization, Partitioning.
ABSTRACT
Abstract: An ant colony optimization is a technique which was introduced in 1990’s and which can be applied to a variety of discrete (combinatorial) optimization problem and to continuous optimization. The ACO algorithm is simulated with the foraging behavior of the real ants to find the incremental solution constructions and to realize a pheromone laying-and-following mechanism. This pheromone is the indirect communication among the ants. In this paper we introduces the partitioning technique based on the divide and conquer strategy for the traveling salesman problem (which is one of the most important combinatorial problem) in which the original problem is partitioned into the group of sub problems. And then we apply the ant colony algorithm using candidate list strategy for each smaller sub problems. After that by applying the local optimization and combining the sub problems to find the good solution for the original problem by improving the exploration efficiency of the ants. At the end of this paper we have also be presented the comparison of result with the normal ant colony system for finding the optimal solution to the traveling salesman problem.
REFERENCES
[1] Dorigo M., Maniezzo V. & Colorni A., “The Ant System: Optimization by a colony of cooperating agents,” IEEE Trans. Systems, Man, and Cybernetics- Vol.26,N 1, pp.1-13, 1996.
[2] Dorigo M, Gambardella L M. Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1) 53-66.
[3] A. Colorni, M. Dorigo, V. Maniezzo, "Distributed optimization by ant colonies”.Proceedings of European Conference on Artificial Life, Paris, France, pp. 134-142, 1991
[4] C.P. Ravikumar. "Solving Large-scale Travelling salesperson Problems on Parallel Machines”. Microprocessors and Microsystems 16(3), pp. 149-158, 1992.
[5] Y.H. Song, K.Y. Lee, J.G. Vlachogiannis, Y.H. Lu and I.K. Yu “Ant colony search algorithms in power system optimization,” In “Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems,” Eds. K.Y. Lee and M.A. El-Sharkawi, IEEE Press Book
[6] Yingzi Wei Yulan Hu, Kanfeng Gu “Parallel Search Strategies for TSPs using a Greedy Genetic Algorithm” Third International Conference on Natural Computation IEEE 2007.
[7] Dorigo M. & Di Caro G., “AntNet: Distributed tigmergetic Control for Communication Networks,” Journal ofArtificial Intelligence Research, Number 9, pp 317-365, 1999.
[8] G. Reinelt. The Traveling Salesman: Computational Solutions for TSP Applications, volume 840 of LNCS. Springer Verlag, 1994.
[9] H. Md. Rais, Z. A. Othman, A.R. Hamdan, Reducing Iteration Using Candidate List, IEEE, 2008.
[10] B. Hölldobler and E. O. Wilson, The Ants. Berlin: Springer-Verlag, 1990.
[11] R.M. Karp, “Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman in the Plane”, Math. Oper. Res. 2 (1977), 209-224.
[12] Stutzle T, Hoos H H. Max-Min Ant System and Local Search for the Traveling Salesman Problem II Proceedings of IEEE International Conference on Evolutionary Computation. New York,USA: IEEE Press, 1997 309-314.
[13] Christian Nilsson, “Heuristics for the Traveling Salesman Problem”.
[14] M. Dorigo, L. M. Gambardella, “Ant colonies for the traveling salesman problem”, BioSystems, 1997.
[15] MA Ying, TIAN wei-jian and FAN yang-yu, “Improved quantum ant colony algorithm for solving TSP problem”,2014 IEEE workshop on electronics, computer and application
[16] Ramlakhan Singh Jadon, Unmukh Datta, “Modified Ant Colony Optimization Algorithm with Uniform Mutation using Self-Adaptive Approach for Travelling Salesman Problem” 4th ICCCNT IEEE 2013.
[17] Guiqing Liu, Juxia Xiong, “Ant Colony Algorithm Based on Dynamci Adaptive pheromone Updating and its Simulation.” Sixth International Symposium on ComputationalIntelligence and Design. 2013 IEEE.
[18] Dong-Hyun Lee and Ju- Jang Lee “Global path planning using improved ant colony optimization algorithm through bilateral cooperative exploration ” IEEE 2011
[19] Cai Shukai and Jiang Yanbin “A Brief review of Ant Algorithms” The 1st International Conference on Information Science and Engineering IEEE 2009.
[20] Xiao-Min Hu, Jun Zhang, Henry Shu-Hung Chung, Yun Li “SamACO: Variable Sampling Ant Colony Optimization Algorithm for Continuous Optimization” ieee transactions on systems, man, and cybernetics—part b: cybernetics, vol. 40, no. 6, december 2010.
[21] Sorin Ilie and Costin Badica “Effectiveness of Solving Traveling Salesman Problem Using Ant Colony Optimization on Distributed Multi-Agent Middleware” Proceedings of the International Multiconference on Computer Science and Information Technology 2010 IEEE.
[22] Helmi Md Rais, Zulaiha Ali Othman, Abdul Razak Hamdan “Reducing Iteration Using Candidate List” 2008 IEEE.
[23] K. Sheibani “The Fuzzy Greedy Search in Combinatorial Optimization with Specific Reference to the Travelling Salesman Problem” 2010 IEEE
[24] Reinelt, G.: TSP-Library (TSPLIB) (2008). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms https://en.wikipedia.org/wiki/Travelling_salesman_problem
|
