Perturbation method for probabilistic search for the traveling salesperson problem

James P. Cohoon; John E. Karro; Worthy N. Martin; William D. Niebel; Klaus Nagel

doi:10.1117/12.326703

13 October 1998 Perturbation method for probabilistic search for the traveling salesperson problem

James P. Cohoon, John E. Karro, Worthy N. Martin, William D. Niebel, Klaus Nagel

Proceedings Volume 3455, Applications and Science of Neural Networks, Fuzzy Systems, and Evolutionary Computation; (1998) https://doi.org/10.1117/12.326703
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1998, San Diego, CA, United States

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.

Citation Download Citation

James P. Cohoon, John E. Karro, Worthy N. Martin, William D. Niebel, and Klaus Nagel "Perturbation method for probabilistic search for the traveling salesperson problem", Proc. SPIE 3455, Applications and Science of Neural Networks, Fuzzy Systems, and Evolutionary Computation, (13 October 1998); https://doi.org/10.1117/12.326703

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available