Genetic Algorithms and the Traveling Salesman Problem a historical Review

The problem has been excessively studied[1][2][3][4][5][6] and a vast array of methods have been introduced to either find the optimal tour or a good less time consuming approximation. This paper will concentrate onthe second path of meta-heuristics and specifically on genetic algorithms(GA) and the historical association with the TSP. GA's have been around since 1957[7], starting with simulations for biological evolution. GA's are used for optimization problems with large search spaces. The TSP as an optimization problem therefore fits the usage and an application of GA's to the TSP was conceivable. In1975 Holland [8] laid the foundation for the success and the resulting interestin GA's. With his fundamental theorem of genetic algorithms he proclaimed the efficiency of GA's for optimization problems. A generic GA starts with the generation of a population of several different tours.