A hybrid approach to the travelling salesman problem (TSP) using adaptive resonance theory and self organizing feature maps

Author

Narayan Vishwanathan

Abstract

“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.

Advisor(s)

Wunsch, Donald C.

Committee Member(s)

Moss, Randy Hays, 1953-
Dagli, Cihan H., 1949-

Department(s)

Electrical and Computer Engineering

Degree Name

M.S. in Electrical Engineering

Publisher

University of Missouri--Rolla

Publication Date

Fall 2001

Pagination

viii, 47 pages

Note about bibliography

Includes bibliographical references (pages 44-46).

Rights

© 2001 Narayan Vishwanathan, All rights reserved.

Document Type

Thesis - Restricted Access

File Type

text

Language

English

Thesis Number

T 7988

Print OCLC #

49507890

Recommended Citation

Vishwanathan, Narayan, "A hybrid approach to the travelling salesman problem (TSP) using adaptive resonance theory and self organizing feature maps" (2001). Masters Theses. 4410.
https://scholarsmine.mst.edu/masters_theses/4410