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

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

A Performance Comparison of GA and ACO Applied to TSP

by Sabry Ahmed Haroun, Benhra Jamal, El Hassani Hicham
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 117 - Number 20
Year of Publication: 2015
Authors: Sabry Ahmed Haroun, Benhra Jamal, El Hassani Hicham
10.5120/20674-3466

Sabry Ahmed Haroun, Benhra Jamal, El Hassani Hicham . A Performance Comparison of GA and ACO Applied to TSP. International Journal of Computer Applications. 117, 20 ( May 2015), 28-35. DOI=10.5120/20674-3466

@article{ 10.5120/20674-3466,
author = { Sabry Ahmed Haroun, Benhra Jamal, El Hassani Hicham },
title = { A Performance Comparison of GA and ACO Applied to TSP },
journal = { International Journal of Computer Applications },
issue_date = { May 2015 },
volume = { 117 },
number = { 20 },
month = { May },
year = { 2015 },
issn = { 0975-8887 },
pages = { 28-35 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume117/number20/20674-3466/ },
doi = { 10.5120/20674-3466 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:59:58.116642+05:30
%A Sabry Ahmed Haroun
%A Benhra Jamal
%A El Hassani Hicham
%T A Performance Comparison of GA and ACO Applied to TSP
%J International Journal of Computer Applications
%@ 0975-8887
%V 117
%N 20
%P 28-35
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This work presents a contribution to comparing two nature inspired metaheuristics for solving the TSP. We run ACO and GA on three benchmark instances with varying size and complexity, in addition to one real world application in the field of urban transportation and logistics. A first chapter presents algorithmic approaches. Results and discussion chapter outlines the computational behavior of the algorithms throughout the problem sets. The conclusion closes the discussion with recommendations and future scopes.

References
  1. K. Menger, Ergebnisse eines mathematischen Kolloquiums: Deuticke, 1932.
  2. A. Punnen, "The Traveling Salesman Problem: Applications, Formulations and Variations," in The Traveling Salesman Problem and Its Variations. vol. 12, G. Gutin and A. Punnen, Eds. , ed: Springer US, 2007, pp. 1-28.
  3. C. H. Papadimitriou, "The Euclidean travelling salesman problem is NP-complete," Theoretical Computer Science, vol. 4, pp. 237-244, 1977.
  4. P. Siarry, "La méthode du recuit simulé: théorie et applications," Automatique-productique informatique industrielle, vol. 29, pp. 535-561, 1995.
  5. H. El Hassani, J. Benhra, and S. Benkachcha, "Utilisation des algorithmes génétiques (AG) dans l'Optimisation multi-objectif en logistique avec prise en compte de l'aspect environnemental (émissions du CO2)," in Colloque international LOGISTIQUA, RABAT, 2012.
  6. TALBI, El-Ghazali. Metaheuristics: from design to implementation. John Wiley & Sons, 2009.
  7. M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53-66, 1997.
  8. J. H. Holland, "Adaption in Natural and Artificial Systems," The University of Michigan Press, 1975.
  9. L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence Through Simulated Evolution: John Wiley & Sons, 1966
  10. D. B. Fogel, "The evolution of intelligent decision making in gaming," Cybernetics and Systems, vol. 22, pp. 223-236, 1991.
  11. L. D. Davis, Handbook Of Genetic Algorithms, 1 ed. : Van Nostrand Reinhold;, 1991.
  12. M. Vazquez and L. D. Whitley, "A Hybrid Genetic Algorithm for the Quadratic Assignment Problem," in GECCO, 2000, pp. 135-142.
  13. M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 26, pp. 29-41, 1996.
  14. J. -L. Deneubourg, S. Aron, S. Goss, and J. M. Pasteels, "The self-organizing exploratory pattern of the argentine ant," Journal of insect behavior, vol. 3, pp. 159-168, 1990.
  15. T. Stützle and H. H. Hoos, "MAX–MIN ant system," Future generation computer systems, vol. 16, pp. 889-914, 2000.
  16. A. Colorni, M. Dorigo, and V. Maniezzo, "Distributed optimization by ant colonies," in Proceedings of the first European conference on artificial life, 1991, pp. 134-142.
  17. G. Gutin and A. P. Punnen, The traveling salesman problem and its variations vol. 12: Springer Science & Business Media, 2002.
  18. SHIN, Soo-Yong, LEE, In-Hee, KIM, Dongmin, et al. Multiobjective evolutionary optimization of DNA sequences for reliable DNA computing. Evolutionary Computation, IEEE Transactions on, 2005, vol. 9, no 2, p. 143-158.
  19. G. Reinelt, "TSPLIB—A Traveling Salesman Problem Library," ORSA Journal of Computing, vol. 3, pp. 376-384, 1991.
  20. A. H. Sabry, A. Bacha, and J. Benhra, "A contribution to solving the traveling salesman problem using ant colony optimization and web mapping platforms Application to logistics in a urban context," in Codit'14, Metz, France, 2014.
  21. WALL, Matthew. GAlib: A C++ library of genetic algorithm components. Mechanical Engineering Department, Massachusetts Institute of Technology, 1996, vol. 87, p. 54.
Index Terms

Computer Science
Information Sciences

Keywords

Traveling salesman problem Genetic algorithm Ant colony optimization

Powered by PhDFocusTM