The week's pick
Random Articles
Reseach Article
Optimization of Traveling Salesman Problem based on Adaptive Affinity Propagation and Ant Colony Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 181 - Number 29 |
| Year of Publication: 2018 |
| Authors: Wesam Ashour, Riham Muqat, Haneen Al-Talli |
10.5120/ijca2018918147
|
Wesam Ashour, Riham Muqat, Haneen Al-Talli . Optimization of Traveling Salesman Problem based on Adaptive Affinity Propagation and Ant Colony Algorithms. International Journal of Computer Applications. 181, 29 ( Nov 2018), 25-31. DOI=10.5120/ijca2018918147
Abstract
The Travelling Salesman Problem (TSP) is a Well-known nondeterministic problem aims to find the shortest route that visits each city once and finally returns back to the starting city. Ant Colony Optimization (ACO) technique gives a good solution to TSP, However it takes a lot of computational time. In This paper, a novel algorithm as proposed to solve TSP. Adaptive Affinity Propagation (AAP) was used to optimize the performance of Ant Colony Optimization. The basic idea of the new proposed approach is to group cities into many clusters using AAP and then find the optimal path for each cluster separately using ACO. Thus, the computational time decreases. Experimental results show that the proposed algorithm has preferable performance compared to ACO in term of computational time and optimal path length.
References
- Harikrishna, J. Ant Colony optimization. IJSRSET, Volume i, Issue i, 2014.
- Ugur, A., and Aydin, D. An interactive simulation and analysis software for solving TSP using Ant Colony Optimization Algorithms. Advances in Engineering Software 40 (2009) 341-349, available in (www.elsevier.com/locate/advengsoft).
- Dorigo, M., Gambardella, M. Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.
- Alhanjouri , M., and Alfarra, B. Ant Colony versus Genetic Algorithm based on Travelling Salesman Problem. Int. J. Comp. Tech. Appl., Vol 2 (3), 570-578.
- El-Samak, A., and Ashour, W. Optimization of Traveling Salesman Problem Using Affinity Propagation Clustering and Genetic Algorithm. JAISCR, 2015, Vol. 5, No. 4, pp. 239-245.
- Phienthrakul, T. Clustering Evolutionary Computation for Solving Travelling Salesman Problems. International Journal of Advanced Computer Science and Information Technology (IJACSIT), Vol. 3, Issue 3, Page: 243-262, 2014.
- Chao, D., Cheng Y., and Miao H. Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs. Tsinghua Science & Technology, Vol. 12, Issue 4, Pages 459–465, August 2007.
- Thavikulwat, p. Affinity Propagation: A clustering Algorithm for Computer-Assisted Business Simulation and Experimental Exercises. Developments in business Simulation and Experimental Learning, Volume 35, 2008.
- Frey, B. J. and Dueck D. Clustering by Passing Messages Between Data Points. Science 2007, pp 972–976.
- Refianti, R., Mutiara, A., and Syamsudduha, A. Performance Evaluation of Affinity Propagation Approaches on Data Clustering. (IJACSA) International Journal of Advanced Computer Science and Applications,Vol. 7, No. 3, 2016.
- Fujiwara , Y., Irie , G., and Kitahara, M. Fast Algorithm for Affinity Propagation. Proceedings of the Twenty-Second International Joint Conference on Artificial Intellegence.
- Wang , K., Zhang, J., Dan, Li., Zhang, X., and Guo, T. Adaptive Affinity Propagation Clustering. Acta Automatica Sinica, 33(12):1242-1246, 2007..
- Shrivastava, S., Rana, j., and Jain, R. Fast Affinity Propagation Clustering based on Machine Learning. IJCSI International Journal of Computer Science Issues, Vol. 10, Issue 1, No 1, January 2013.
- Santana, R., Bielza, C., and Larrañaga, p. Affinity Propagation Enhanced by Estimation of Distribution Algorithms. Supported by TIN2010-20900-C04-04, Consolider Ingenio 2010 -CSD2007-00018 projects (Spanish Ministry of Science and Innovation) and the CajalBlueBrain project.
- Hlaing, Z., and Khine, M. An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem. International Conference on Information Communication and Management IPCSIT vol.16 (2011).
- Dorigo, M., Caro, G., Gambardella L. Ant Algorithms for Discrete Optimization. Artificial Life Volume 5, Number 2.
- Diwekar, W., and Gebreslassie, B. Efficient Ant Colony Optimization (EACO) Algorithm for Deterministic Optimization. Int J Swarm Intel Evol Comput 2016, 5:2, ISSN: 2090-4908 SIEC, http://dx.doi.org/10.4172/2090-4908.1000131.
- Bajpai, A., and Yadav, R. Ant Colony Optimization (ACO) For The Traveling Salesman Problem (TSP) Using Partitioning. International Journal Of Scientific & Technology Research Volume 4, Issue 09, September 2015 ISSN 2277-8616.
- Yanga, J., Shia, X., Marcheseb, M., and Lianga, yY. An ant colony optimization method for generalized TSP problem. Progress in Natural Science Volume 18, Issue 11, 10 November 2008, Pages 1417–1422.
- TSP-Library (TSPLIB), http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/XML-TSPLIB/instances/Communication and Management IPCSIT vol.16 (2011).
Index Terms
Keywords