25 March 1998 Summary of the neural centroid TSP
Author Affiliations +
Abstract
This paper summarizes a new interpretation of the Hopfield- Tank model as it applies to the Planar Traveling Salesman Problem (TSP). We demonstrate that the network solves the TSP in a 'centroidal' manner, that is, it provides tours that are similar to those obtained by the traditional centroid algorithm. The traditional centroid algorithm computes the center of mass of the cities and then orders the cities by the corresponding central angles. This algorithm gives excellent results on near-circular city configurations, and abysmal results on near-linear city configurations. We demonstrate that for up to 30 randomly generated cities the centroid results are very competitive with well known heuristics, such as the nearest city and 2-opt, but after about 40 cities the centroid algorithm produces poor results in comparison. We claim that this effect is inherent to the Hopfield-Tank model and explains why such networks do not scale up.
© (1998) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
William J. Wolfe, William J. Wolfe, Frank A. Duca, Frank A. Duca, } "Summary of the neural centroid TSP", Proc. SPIE 3390, Applications and Science of Computational Intelligence, (25 March 1998); doi: 10.1117/12.304856; https://doi.org/10.1117/12.304856
PROCEEDINGS
7 PAGES


SHARE
RELATED CONTENT

HOG-based multi-scale motion detection
Proceedings of SPIE (December 18 2013)
Emotion detection model of Filipino music
Proceedings of SPIE (February 07 2017)
Task scheduling neural networks
Proceedings of SPIE (January 31 1994)
Recursive ULV decomposition
Proceedings of SPIE (November 12 2000)
Parametrization of curves and surfaces
Proceedings of SPIE (July 31 1990)

Back to Top