CFP last date
16 December 2024
Call for Paper
January Edition
IJAIS solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 16 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Ordered Frequent Itemsets Matrix Based On Fp-Tree Structure And Apriori Algorithm

Abdulkader M. Al-Badani Abdualmajed A. Al-Khulaidi
Random Articles
Reseach Article

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

by Adewole A.p., Otubamowo K., Egunjobi T.o.
journal cover thumbnail

International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 4 - Number 4
Year of Publication: 2012
Authors: Adewole A.p., Otubamowo K., Egunjobi T.o.
10.5120/ijais12-450678

Adewole A.p., Otubamowo K., Egunjobi T.o. . A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem. International Journal of Applied Information Systems. 4, 4 ( October 2012), 6-12. DOI=10.5120/ijais12-450678

@article{ 10.5120/ijais12-450678,
author = { Adewole A.p., Otubamowo K., Egunjobi T.o. },
title = { A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem },
journal = { International Journal of Applied Information Systems },
issue_date = { October 2012 },
volume = { 4 },
number = { 4 },
month = { October },
year = { 2012 },
issn = { 2249-0868 },
pages = { 6-12 },
numpages = {9},
url = { https://www.ijais.org/archives/volume4/number4/290-0678/ },
doi = { 10.5120/ijais12-450678 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T10:47:18.386456+05:30
%A Adewole A.p.
%A Otubamowo K.
%A Egunjobi T.o.
%T A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 4
%N 4
%P 6-12
%D 2012
%I Foundation of Computer Science (FCS), NY, 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.

References
  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.
Index Terms

Computer Science
Information Sciences

Keywords

Genetic Algorithm simulated Annealing Travelling Salesman Problem Candidate solution Optimization problem

Powered by PhDFocusTM