Comparison of Optimization strategies for the TSP
COMPARISMS OF OPTIMIZATION STRATEGIES FOR THE TRAVELLING SALESMAN
PROBLEM
Department of Information Systems and Computing
B.Sc. (Hons) Computer Science, Artificial Intelligence
Academic Year 2012-2013
Comparison of Optimization Strategies for the Travelling Salesman Problem
Adewale Oluwaseun Mako (0941620)
A Report Submitted in the partial fulfilment of the requirement for the degree of Bachelor of Science
Brunel University
Department of Information Systems and Computing
Uxbridge, Middlesex UB8 3PH
United Kingdom
Tel: +44 (0) 1895 203397
Fax: +44 (0) 1895 251686
COMPARISON OF OPTIMISATION STRATEGIES FOR THE TRAVELLING SALESMAN
PROBLEM
ABSTRACT
In this report, the topic been discussed is how to Compare Optimisation
Strategies for the Travelling Salesman Problem (T.S.P). With the topic above I would like
1|Page
COMPARISMS OF OPTIMIZATION STRATEGIES FOR THE TRAVELLING SALESMAN
PROBLEM
to say that the real problem is the T.S.P and the approach taken to compare the optimization strategies.
So first of all, what is the T.S.P? The Travelling Salesman Problem (T.S.P) is the problem of finding a tour through a specified set of cities that minimizes the total travel distance; or, more formally, the Problem of finding a Hamiltonian circuit of minimum cost in an edge-weighted graph. It is probably the most well-known NP-hard combinatorial optimization problem, and arises in many practical applications, either directly or as a subproblem. (Lawler et al. 1985; Reinelt 1994; Gutin and Punnen 2002).
In this project I will be implementing the various heuristics search methods such as
Hill Climber, Random Mutation Hill Climber, Random Restart Hill Climber and Simulated
Annealing to solve TSP and check the fitness level of the algorithms to see how well the algorithms work against the standard of TSP.
2|Page
COMPARISMS OF OPTIMIZATION STRATEGIES FOR THE TRAVELLING SALESMAN
PROBLEM
ACKNOWLEDGEMENT
Great is the Lord for he has
PROBLEM
Department of Information Systems and Computing
B.Sc. (Hons) Computer Science, Artificial Intelligence
Academic Year 2012-2013
Comparison of Optimization Strategies for the Travelling Salesman Problem
Adewale Oluwaseun Mako (0941620)
A Report Submitted in the partial fulfilment of the requirement for the degree of Bachelor of Science
Brunel University
Department of Information Systems and Computing
Uxbridge, Middlesex UB8 3PH
United Kingdom
Tel: +44 (0) 1895 203397
Fax: +44 (0) 1895 251686
COMPARISON OF OPTIMISATION STRATEGIES FOR THE TRAVELLING SALESMAN
PROBLEM
ABSTRACT
In this report, the topic been discussed is how to Compare Optimisation
Strategies for the Travelling Salesman Problem (T.S.P). With the topic above I would like
1|Page
COMPARISMS OF OPTIMIZATION STRATEGIES FOR THE TRAVELLING SALESMAN
PROBLEM
to say that the real problem is the T.S.P and the approach taken to compare the optimization strategies.
So first of all, what is the T.S.P? The Travelling Salesman Problem (T.S.P) is the problem of finding a tour through a specified set of cities that minimizes the total travel distance; or, more formally, the Problem of finding a Hamiltonian circuit of minimum cost in an edge-weighted graph. It is probably the most well-known NP-hard combinatorial optimization problem, and arises in many practical applications, either directly or as a subproblem. (Lawler et al. 1985; Reinelt 1994; Gutin and Punnen 2002).
In this project I will be implementing the various heuristics search methods such as
Hill Climber, Random Mutation Hill Climber, Random Restart Hill Climber and Simulated
Annealing to solve TSP and check the fitness level of the algorithms to see how well the algorithms work against the standard of TSP.
2|Page
COMPARISMS OF OPTIMIZATION STRATEGIES FOR THE TRAVELLING SALESMAN
PROBLEM
ACKNOWLEDGEMENT
Great is the Lord for he has
References: Abdelbar, A.M.; Abdelshahid, S.; Wunsch, D.C., II . (2005). Fuzzy PSO. A generalization of particle swarm optimization Applegate D., Bixby, R., Chvatal, V., and Cook, W.. (1998.). on the solution of travelling salesman problems Daoxiong Gong; Xiaogang Ruan . (2004). A hybrid approach of GA and ACO for TSP,". De-Shuang Huang, Kang Li and Co. (2006). International conference on intelligent computing: ICIC. Dorigo, M. (1997). Ant colony system. A cooperative learning approach to the Travelling Salesman Problem Dorigo, M.; Birattari, M.; Stutzle, T. (2006). Ant colony optimization. Computational Intelligence Magazine, IEEE Dorigo, M.; Di Caro, G. . (1999). Ant colony optimization: a new meta-heuristic. Fogel D. (1998). Evolutionary Computation and the Traveling Salesman Problem. Michalewicz Z, Fogel D. (2004). How to solve It. Modern Heuristics. 2nd ed. London. : Springer Norouzzadeh, M.S.; Ahmadzadeh, M.R.; Palhang, M. (2010). Plowing PSO. : A novel approach to effectively initializing particle swarm optimization Stephen, S. 2012, the Travelling Salesman Problem CS2004, Algorithms and their Applications, Brunel University Peng-Yeng Yin; Glover, F.; Laguna, M.; Jia-Xian Zhu . (2007). Scatter PSO. A more effective form of Particle Swarm Optimization, p2289 - 2296. TSPLIB. (2012). Searching the library data sets. Available: http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/. [Last accessed 18th Jan 2013].