|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Fall 2012 Using an Adaptive Genetic Algorithm to Solve the Traveling Salesman Problem Munther Hussain 
ABSTRACT Given n cities, the Traveling Salesman Problem (TSP) is the task of finding the shortest tour that visits every city exactly once and returns to the starting city. The TSP is considered to be an NP-hard problem that has not been solved in polynomial time yet. In this project, we proposed an Adaptive Genetic Algorithm (AGA) that employs an improved modified version of the adaptive population size scheme of the PRoFI-GA, combined with the use of the Neighbor-Join (NJ) operator as a local search algorithm. Our results and analysis indicate that, when applied to the TSP, our AGA is superior in performance and efficiency to the Standard Genetic Algorithm (SGA), the original PRoFI-GA, as well as other adaptive genetic algorithms. |
||||||
|
