A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem
No Thumbnail Available
Date
2012-10
Authors
Otubamowo, K.
Egunjobi, T.O.
Adewole, A.P.
Journal Title
Journal ISSN
Volume Title
Publisher
International Journal of Applied Information Systems (IJAIS)
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.
Description
Staff publication
Keywords
Genetic Algorithm , Simulated Annealing , Travelling Salesman Problem , Candidate solution , Optimization problem. , Research Subject Categories::TECHNOLOGY::Information technology::Computer science::Computer science
Citation
Adewole, A.P., Otubamowo, K., Egunjobi, T.O. (2012). A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem. International Journal of Applied Information Systems (IJAIS), Vol.4(4):6-12pp.