Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

August Edition 2021

International Journal of Applied Information Systems solicits high quality original research papers for the August 2021 Edition of the journal. The last date of research paper submission is July 15, 2021.

A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem

Adewole A. P. , Otubamowo K., Egunjobi T. O. Published in Algorithms

International Journal of Applied Information Systems
Year of Publication 2012
© 2010 by IJAIS Journal
10.5120/ijais12-450678
Download full text
  1. Adewole A.p., Otubamowo K. and Egunjobi T.o.. Article: A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem. International Journal of Applied Information Systems 4(4):6-12, October 2012. BibTeX

    @article{key:article,
    	author = "Adewole A.p. and Otubamowo K. and Egunjobi T.o.",
    	title = "Article: A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem",
    	journal = "International Journal of Applied Information Systems",
    	year = 2012,
    	volume = 4,
    	number = 4,
    	pages = "6-12",
    	month = "October",
    	note = "Published by Foundation of Computer Science, New York, USA"
    }
    

Abstract

Metaheuristic algorithms have proved to be good solvers for the traveling salesman problem (TSP). All metaheuristics usually encounter problems on which they perform poorly so the programmer must gain experience on which optimizers work well in different classes of problems. However due to the unique functionality of each type of meta-heuristic, comparison of metaheuristics is in many ways more difficult than other algorithmic comparisons. In this paper, solution to the traveling salesman problem was implemented using genetic algorithm and simulated annealing. These algorithms were compared based on performance and results using several benchmarks. It was observed that Simulated Annealing runs faster than Genetic Algorithm and runtime of Genetic Algorithm increases exponentially with number of cities. However, in terms of solution quality Genetic Algorithm is better than Simulated Annealing.

Reference

  1. Ahuja, R. , Orlin, J. 1993. Use of representative operation counts in computational testing of algorithms. INFORMS Journal on Computing 8(3), 318-330
  2. Ali Hamdar 2008. Simulated Annealing-Solving the Travelling Salesman Problem.
  3. Anthony Ralston and Edwin D. Reilly 1993. Encyclopedia of Computer Science, Chapman & Hall.
  4. Aybars U. , Serdar K. , Ali C. , Muhammed C. and Ali A 2009. Genetic Algorithm Based Solution of TSP on a Sphere, Mathematical and Computational Applications, Vol. 14, No. 3, pp. 219-228.
  5. Bertsimas D. and Tsitsiklis J. 1993. "Simlated Annealing", Journal of Statistical Science, Vol. 8, No 1, 10-15.
  6. Bland, R. G. and Shallcross, D. F. 1989. Large Traveling Salesman Problems Arising from Experiments in X-ray Crystallography: A preliminary report on computation, Operations Research. Letter. pg. 125-128.
  7. Dorigo M. , Vittorio M. and Alberto C. 1996. The Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, MAN, and cybernetic, vol. 26, No. 1.
  8. Fan Yang 2010. Solving Traveling Salesman Problem Using Parallel Genetic Algorithm and Simulated Annealing.
  9. Hiroaki Sengoku and Ikuo Yoshihara 1993, A Fast TSP solver using GA on JAVA.
  10. Holland, J. H. 1992, Adaptation in Natural and Artificial systems, Cambridge, MA, USA: MIT Press.
  11. John Silberholz and Bruce Golden 2010, Comparison of Metaheuristics.
  12. Kirkpatrick, S. , Gelatt, Jr. C. D. and Vecchi, M. P. 1983. "Optimization by Simulated Annealing", Journal of Mathematical Sciences, Vol. 220: pg. 109-120.
  13. Korte, B. 1988. Applications of Combinatorial Optimization, talk at the 13th International Mathematical Programming Symposium, Tokyo.
  14. Lawler, E. L. , Lenstra, J. K. , Rinnooy Kan, A. H. G. , and Shmoys, D. B. 1985. The Traveling Salesman Problem, John Wiley & Sons, Chichester.
  15. Mark Dorigo and Thomas Stutzle(2009), Ant Colony Optimization.
  16. Nazif, H. and Lee, L. S. 2010. "Optimized Crossover Genetic Algorithm for Vehicle Routing Problem with Time Windows, American", Journal of Applied Sciences 7 (1): pg. 95-101.
  17. Roland Braune, Stefan Wagner and Michael Affenzeller 2005, Applying Genetic Algorithms to the Optimization of Production Planning in a real world Manufacturing Environment, Institute of Systems Theory and Simulation Johannes Kepler University.
  18. Sachin Jayaswal 2004. A Comparative study of Tabu Search and Simulated Annealing for Travelling Salesman problem.
  19. TSP2010. http://www. tsp. gatech. edu/history/tspinfo
  20. Wikipedia 2010. The Free Encyclopedia, http://en. wikipedia. org/wiki/Main_Page.
  21. Zuhaimy Ismail, Wan Rohaizad and Wan Ibrahim 2008. "Travelling Salesman problem for solving Petrol Distribution using Simulated-Annealing", American Journal of Applied Sciences 5(11): 1543-1546.

Keywords

Genetic Algorithm, simulated Annealing, Travelling Salesman Problem, Candidate solution, Optimization problem