A hybrid approach to the travelling salesman problem (TSP) using adaptive resonance theory and self organizing feature maps
“Neural approaches to solving the Travelling Salesman Problem (TSP) have used either the Hopfield network or modified forms of the Self-Organizing Feature Maps (SOFM). While the Hopfield networks have not scaled well, algorithms based on SOFM have shown much promise. However a large gap exists between neural net solutions and the best known heuristic or approximation algorithms for TSP partly because neural net approaches need to incorporate techniques from the classical heuristic methods. Here we borrow the principle of divide and conquer from approximation methods and combine it with neural nets to make them more effective, using ART to form clusters of cities and the SOFM for linking both the cities within clusters, and the clusters themselves.
We divide our algorithm into three phases. Phase one uses ART to form clusters of cities. Phase two uses a novel modification of the SOFM algorithm to solve a slight variant of the TSP in each cluster of cities. Phase three uses another version of the SOFM to link all the clusters. A heuristic is used to remove crossings that occur when the clusters are linked together. We tested our algorithm on random and clustered random instances of the TSP of up to 20000 cities. We compared our results with the chained Lin Kernighan approach. The worst case tour lengths obtained by our approach were 15% longer and our approach shows potential for larger instances due to good scalability”--Abstract, page iii.
Wunsch, Donald C.
Moss, Randy Hays, 1953-
Dagli, Cihan H., 1949-
Electrical and Computer Engineering
M.S. in Electrical Engineering
University of Missouri--Rolla
viii, 47 pages
Note about bibliography
Includes bibliographical references (pages 44-46).
© 2001 Narayan Vishwanathan, All rights reserved.
Thesis - Restricted Access
Print OCLC #
Link to Catalog Record
Electronic access to the full-text of this document is restricted to Missouri S&T users. Otherwise, request this publication directly from Missouri S&T Library or contact your local library.http://merlin.lib.umsystem.edu/record=b4756100~S5
Vishwanathan, Narayan, "A hybrid approach to the travelling salesman problem (TSP) using adaptive resonance theory and self organizing feature maps" (2001). Masters Theses. 4410.
Share My Thesis If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.