Improving the performance of the Hopfield-Tank neural network through normalization and annealing

A simple formulation of the TSP energy function is described which, in combination with a normalized Hopfield-Tank neural network, eliminates the difficulty in finding valid tours.

Abstract

A simple formulation of the TSP energy function is described which, in combination with a normalized Hopfield-Tank neural network, eliminates the difficulty in finding valid tours. This technique is applicable to many other optimization problems involving n-way decisions (such as VLSI layout and resource allocation) and is easily implemented in a VLSI neural network. The solution quality is shown to be dependent on the formation of seed-points which are influenced by the constraint penalties and the temperature (i.e. the neural gain). Near-optimal tours are found by annealing the network down to a critical temperature at which a single seed-point is dominant. The seed-points and critical temperature (which also affect standard Hopfield network solutions to the TSP) can be predicted with reasonable accuracy. It is also shown that the annealing process is not necessary and good tours result if the network is allowed to converge solely at the critical temperature. The seed-points can be eliminated entirely by assigning different temperatures to groups of neurons such that the tour evolves uniformly throughout the cities. The resulting network finds the optimum tour in a 30-city example in 30% of the trials.