Addressing the Travelling Salesman Problem through Evolutionary Adaptation
David B. Fogel · 1987
Abstract : The optimization of the traveling saleman problem continues to receive attention for three reasons: (1) its solution is computationally difficult although the algorithm itself is easily expressed; (2) it is broadly applicable to a variety of engineering problems; and (3) it has become somewhat of a comparison benchmark problem. The task is to arrange a tour of n cities such that each city is visited only once and the length of the tour (or some other cost function) is minimized. For an exact solution the only known algorithms require the number of steps to grow at least exponentially with the number of elements in the program. Brute force methods of finding of the shortest path by which a traveling salesman can complete a tour of n cities requires compiling a list of (n-1) alternative tours, a number that grows faster than any finite power of n. The task quickly becomes unmanageable.