Graduation Year
2000
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Arthur Benjamin
Reader 2
Lisette de Pillis
Abstract
Genetic algorithms are an evolutionary technique that use crossover and mutation operators to solve optimization problems using a survival of the fittest idea. They have been used successfully in a variety of different problems, including the traveling salesman problem. In the traveling salesman problem we wish to find a tour of all nodes in a weighted graph so that the total weight is minimized. The traveling salesman problem is NP-hard but has many real world applications so a good solution would be useful. Many different crossover and mutation operators have been devised for the traveling salesman problem and each give different results. We compare these results and find that operators that use heuristic information or a matrix representation of the graph give the best results.
Recommended Citation
Bryant, Kylie, "Genetic Algorithms and the Travelling Salesman Problem" (2000). HMC Senior Theses. 126.
https://scholarship.claremont.edu/hmc_theses/126
Thesis Proposal
