Addressing the Travelling Salesman Problem through Evolutionary Adaptation
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1987
- Accession Number
- ADA179992
Entities
People
- David B. Fogel
Organizations
- Titan Corp.