A Fuzzy Hopfield-Tank Traveling Salesman Problem Model

This article describes a Hopfield-Tank model of the Euclidean traveling salesman problem (using Aiyer's subspace approach) that incorporates a “fuzzy” interpretation of the rows of the activation array. This fuzzy approach is used to explain the network's behavior. The fuzzy interpretation consists of computing the center of mass of the positive activations in each row. This produces real numbers along the time line, one for each city, and defines a tour in a natural way (referred to as a “fuzzy tour”). A fuzzy tour is computed at each iteration, and examination of such tours exposes fine features of the network dynamics. For example, these tours demonstrate that the network goes through (at least) three phases: “centroid,” “monotonic,” and “nearest-city.” The centroid (initial) phase of the network produces an approximation to the centroid tour (i.e., the tour that orders the cities by central angle with respect to the centroid of the cities). The second phase produces an approximation to the monotonic tour (i.e., the tour that orders the cities by their projection onto the principal axis of the cities). The third phase produces an approximation to a nearest-city tour, that is, a tour whose length is between the tour lengths of the nearest-city-best (best starting city) and nearest-city-worst (worst starting city). Simulations are presented for up to 125 uniformly randomly generated cities.