Share Email Print

Proceedings Paper

Perturbation method for probabilistic search for the traveling salesperson problem
Author(s): James P. Cohoon; John E. Karro; Worthy N. Martin; William D. Niebel; Klaus Nagel
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

The Traveling Salesperson Problem (TSP), is an MP-complete combinatorial optimization problem of substantial importance in many scheduling applications. Here we show the viability of SPAN, a hybrid approach to solving the TSP that incorporates a perturbation method applied to a classic heuristic in the overall context of a probabilistic search control strategy. In particular, the heuristic for the TSP is based on the minimal spanning tree of the city locations, the perturbation method is a simple modification of the city locations, and the control strategy is a genetic algorithm (GA). The crucial concept here is that the perturbation of the problem allows variant solutions to be generated by the heuristic and applied to the original problem, thus providing the GA with capabilities for both exploration in its search process. We demonstrate that SPAN outperforms, with regard to solution quality, one of the best GA system reported in the literature.

Paper Details

Date Published: 13 October 1998
PDF: 10 pages
Proc. SPIE 3455, Applications and Science of Neural Networks, Fuzzy Systems, and Evolutionary Computation, (13 October 1998); doi: 10.1117/12.326703
Show Author Affiliations
James P. Cohoon, Univ. of Virginia (United States)
John E. Karro, Univ. of Virginia (United States)
Worthy N. Martin, Univ. of Virginia (United States)
William D. Niebel, Univ. of Virginia (United States)
Klaus Nagel, Siemens AG (Germany)

Published in SPIE Proceedings Vol. 3455:
Applications and Science of Neural Networks, Fuzzy Systems, and Evolutionary Computation
Bruno Bosacchi; David B. Fogel; James C. Bezdek, Editor(s)

© SPIE. Terms of Use
Back to Top