Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU

The Traveling Salesman Problem (TSP) is one of the most intensively studied problems in computational mathematics. TSP has been used as a benchmark for many new algorithm ideas and optimization methods. Exact method for solving TSP, which has practically acceptable running time, has not been found....

Full description

Saved in:
Bibliographic Details
Main Author: Quang, Mau Bach.
Other Authors: Low Yoke Hean, Malcolm
Format: Final Year Project
Language:English
Published: 2011
Subjects:
Online Access:http://hdl.handle.net/10356/44993
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-44993
record_format dspace
spelling sg-ntu-dr.10356-449932023-03-03T20:35:26Z Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU Quang, Mau Bach. Low Yoke Hean, Malcolm School of Computer Engineering Parallel and Distributed Computing Centre DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity The Traveling Salesman Problem (TSP) is one of the most intensively studied problems in computational mathematics. TSP has been used as a benchmark for many new algorithm ideas and optimization methods. Exact method for solving TSP, which has practically acceptable running time, has not been found. Therefore, various heuristics and approximation algorithms, which quickly yield good solutions, have been devised. Among those algorithms, the Genetic Algorithm (GA), modeled after the process of natural evolution, can be quickly implemented and deployed. However, GA does not utilize explicitly the knowledge of the problem on searching for the solutions. Consequently, hybrid methods that combine GA with other local search techniques have been attempted. Bachelor of Engineering (Computer Engineering) 2011-06-08T01:26:06Z 2011-06-08T01:26:06Z 2011 2011 Final Year Project (FYP) http://hdl.handle.net/10356/44993 en Nanyang Technological University 66 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
spellingShingle DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
Quang, Mau Bach.
Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU
description The Traveling Salesman Problem (TSP) is one of the most intensively studied problems in computational mathematics. TSP has been used as a benchmark for many new algorithm ideas and optimization methods. Exact method for solving TSP, which has practically acceptable running time, has not been found. Therefore, various heuristics and approximation algorithms, which quickly yield good solutions, have been devised. Among those algorithms, the Genetic Algorithm (GA), modeled after the process of natural evolution, can be quickly implemented and deployed. However, GA does not utilize explicitly the knowledge of the problem on searching for the solutions. Consequently, hybrid methods that combine GA with other local search techniques have been attempted.
author2 Low Yoke Hean, Malcolm
author_facet Low Yoke Hean, Malcolm
Quang, Mau Bach.
format Final Year Project
author Quang, Mau Bach.
author_sort Quang, Mau Bach.
title Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU
title_short Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU
title_full Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU
title_fullStr Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU
title_full_unstemmed Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU
title_sort solving the traveling salesman problem using genetic algorithm on nvidia cuda gpu
publishDate 2011
url http://hdl.handle.net/10356/44993
_version_ 1759857008676175872