Addressing the Travelling Salesman Problem through Evolutionary Adaptation
Interim rept. Apr-Jul 1986
TITAN CORP LA JOLLA CA TITAN SYSTEMS INC
Pagination or Media Count:
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.
- Operations Research