|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Fall 2009 Application of Genetic Algorithm to the Traveling Salesman Problem Christopher Boardman 
ABSTRACT The traveling salesman problem is to produce the shortest tour of a graph if available. This is considered an NP-complete problem due to the computational expense required in producing the correct result. However, for many instances of the traveling salesman problem a near enough solution is acceptable. With this in mind, I wish to design and implement a genetic algorithm that will produce a heuristic solution to the traveling salesman problem. Since genetic algorithms depend on successive improvements to a solution population in order of fitness, and that the Traveling Salesman Problem has a very obvious measure of fitness (i.e. tour value), I think that a genetic algorithm would be a suitable match for this problem. |
||||||
|
