Analysis of TSP: Simulated Annealing and Genetic Algorithm Approaches

Authors : Ahmet Reha BOTSALI, Kemal ALAYKIRAN

Pages : 23-28

Doi:10.22399/ijcesen.637445

View : 23 | Download : 11

Publication Date : 2020-03-31

Article Type : Research Paper

Abstract :This paper analyzes the performance of the popular heuristic methods ‘Simulated Annealing insert ignore into journalissuearticles values(SA);’ and ‘Genetic Algorithm insert ignore into journalissuearticles values(GA);’  on  the symmetric TSP.  TSP is a well-known combinatorial optimization problem in NP-complete class. NP-completeness of TSP originates many specific approximation algorithms to find optimal or near optimal solutions in a reasonable time. On the other hand, both SA and GA are general purpose heuristic methods that are applicable to almost every kind of problem whose solution lies inside a search space. The performance of SA and GA depends on many factors such as the nature of the problem, design of the algorithm, parameter values, etc. In this paper, a GA and an SA algorithm are given  and their performance with re-spect to several factors is analyzed. The algorithms are tested on some benchmark problems insert ignore into journalissuearticles values(TSPLIB); which are obtainable via Internet from http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html.
Keywords : TSP, Simulated Annealing SA, Genetic Algorithms GA, Integer Programming MIP,