A comparison of genetic and other algorithms for the traveling salesman problem |
Posted on:1998-10-01 | Degree:M.S | Type:Thesis |
University:San Jose State University | Candidate:Schlapfer, Martin Felix | Full Text:PDF |
GTID:2468390014974514 | Subject:Computer Science |
Abstract/Summary: | |
This thesis begins with a short introduction to the Traveling Salesman Problem and a discussion of the role of Genetic Algorithms and how they work. The application of the Genetic Algorithm to the Traveling Salesman Problem is discussed and a description of the resources that were drawn from is provided. Also discussed, are two crossover operators for the TSP, (Bui-Moon and Whitley's Edge Recombination). Results of experiments applied using both operators combined with the two most common GA models and various local optimization procedures are presented. Traditional approximation heuristics for the Traveling Salesman Problem are also provided as well as some results of experiments using these other heuristics and comparisons to the Genetic Algorithm. In the final chapter I conclude a discussion of what research is being presented in Johnson et al. and give my own conclusions about the promises of GA with respect to the Traveling Salesman Problem. |
Keywords/Search Tags: | Traveling salesman problem, Genetic |
|
Related items |