CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Optimization of Traveling Salesman Problem based on Adaptive Affinity Propagation and Ant Colony Algorithms

by Wesam Ashour, Riham Muqat, Haneen Al-Talli
journal cover thumbnail

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

@article{ 10.5120/ijca2018918147,
author = { Wesam Ashour, Riham Muqat, Haneen Al-Talli },
title = { Optimization of Traveling Salesman Problem based on Adaptive Affinity Propagation and Ant Colony Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { Nov 2018 },
volume = { 181 },
number = { 29 },
month = { Nov },
year = { 2018 },
issn = { 0975-8887 },
pages = { 25-31 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume181/number29/30126-2018918147/ },
doi = { 10.5120/ijca2018918147 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T01:07:40.570542+05:30
%A Wesam Ashour
%A Riham Muqat
%A Haneen Al-Talli
%T Optimization of Traveling Salesman Problem based on Adaptive Affinity Propagation and Ant Colony Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 181
%N 29
%P 25-31
%D 2018
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Harikrishna, J. Ant Colony optimization. IJSRSET, Volume i, Issue i, 2014.
  2. 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).
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. Frey, B. J. and Dueck D. Clustering by Passing Messages Between Data Points. Science 2007, pp 972–976.
  10. 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.
  11. Fujiwara , Y., Irie , G., and Kitahara, M. Fast Algorithm for Affinity Propagation. Proceedings of the Twenty-Second International Joint Conference on Artificial Intellegence.
  12. Wang , K., Zhang, J., Dan, Li., Zhang, X., and Guo, T. Adaptive Affinity Propagation Clustering. Acta Automatica Sinica, 33(12):1242-1246, 2007..
  13. 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.
  14. 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.
  15. 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).
  16. Dorigo, M., Caro, G., Gambardella L. Ant Algorithms for Discrete Optimization. Artificial Life Volume 5, Number 2.
  17. 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.
  18. 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.
  19. 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.
  20. TSP-Library (TSPLIB), http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/XML-TSPLIB/instances/Communication and Management IPCSIT vol.16 (2011).
Index Terms

Computer Science
Information Sciences

Keywords

Travelling Salesman Problem Ant Colony Optimization Adaptive Affinity Propagation.

Powered by PhDFocusTM