Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem

Optimization is defined as a process of finding the best solution in the most effective way of a given problem. Generally, this means solving problems by choosing the values of real or integer variables from a given set of values in order to minimize or maximize a real function. Traveling Salesman P...

Full description

Saved in:

Bibliographic Details
Main Author:	Pang, Li Sim
Format:	Thesis
Language:	English
Published:	2010
Subjects:	QA75 Electronic computers Computer science
Online Access:	http://eprints.utm.my/id/eprint/16395/7/PangLiSimMFSKSM2010.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.16395
record_format	uketd_dc
spelling	my-utm-ep.163952017-09-13T04:35:32Z Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem 2010 Pang, Li Sim QA75 Electronic computers. Computer science Optimization is defined as a process of finding the best solution in the most effective way of a given problem. Generally, this means solving problems by choosing the values of real or integer variables from a given set of values in order to minimize or maximize a real function. Traveling Salesman Problem (TSP) is a one of the famous optimization problem in finding the shortest distance that passes through a given number of cities (each exactly once) and return to the starting point. This study proposed an enhanced Genetic Algorithm (GA) with Simulated Annealing (SA) which can be implemented and solve TSP. GA may have the advantages in finding a solution in a very short of time when dealing with small dataset. But, GA still needs to overcome its long computation time when handling large number datasets. Besides that, GA lacks in local search ability and sometimes it may have premature convergence. On the other hand, SA often used to find global solution but required a large computation time. The proposed algorithm can speed up the computation time while giving an optimum solution, which is the shortest distance compared to the conventional GA. The proposed method gives a better result in terms of shortest distance and smaller computation time when dealing five datasets from TSPLIB. The results have proved that the proposed method is convincing compared to other related method. 2010 Thesis http://eprints.utm.my/id/eprint/16395/ http://eprints.utm.my/id/eprint/16395/7/PangLiSimMFSKSM2010.pdf application/pdf en public masters Universiti Teknologi Malaysia, Faculty of Computer Science and Information System Faculty of Computer Science and Information System
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA75 Electronic computers Computer science
spellingShingle	QA75 Electronic computers Computer science Pang, Li Sim Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem
description	Optimization is defined as a process of finding the best solution in the most effective way of a given problem. Generally, this means solving problems by choosing the values of real or integer variables from a given set of values in order to minimize or maximize a real function. Traveling Salesman Problem (TSP) is a one of the famous optimization problem in finding the shortest distance that passes through a given number of cities (each exactly once) and return to the starting point. This study proposed an enhanced Genetic Algorithm (GA) with Simulated Annealing (SA) which can be implemented and solve TSP. GA may have the advantages in finding a solution in a very short of time when dealing with small dataset. But, GA still needs to overcome its long computation time when handling large number datasets. Besides that, GA lacks in local search ability and sometimes it may have premature convergence. On the other hand, SA often used to find global solution but required a large computation time. The proposed algorithm can speed up the computation time while giving an optimum solution, which is the shortest distance compared to the conventional GA. The proposed method gives a better result in terms of shortest distance and smaller computation time when dealing five datasets from TSPLIB. The results have proved that the proposed method is convincing compared to other related method.
format	Thesis
qualification_level	Master's degree
author	Pang, Li Sim
author_facet	Pang, Li Sim
author_sort	Pang, Li Sim
title	Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem
title_short	Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem
title_full	Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem
title_fullStr	Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem
title_full_unstemmed	Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem
title_sort	enhanced genetic algorithm with simulated annealing in solving travelling salesman problem
granting_institution	Universiti Teknologi Malaysia, Faculty of Computer Science and Information System
granting_department	Faculty of Computer Science and Information System
publishDate	2010
url	http://eprints.utm.my/id/eprint/16395/7/PangLiSimMFSKSM2010.pdf
_version_	1747815033261260800

Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem

Similar Items