A method for solving the travelling salesman problem by the two-state neural network model

Hopfield has shown that the travelling salesman problem (TSP) can be solved on a neural network minimizing the quadratic energy function. However, the network converges to the steady state with not the global but a local minimum of the function, which varies greatly with the penalty factor (r) on the constraints in the energy function. The best value of r depends on the structure of the TSP and no systematic method for finding such r has been proposed. The authors call the minimum r satisfying all the constraints the minimum possible r(r*) and propose an algorithmic procedure to find r* with the 2-state neural networks. Furthermore, they introduce the augmented penalty function to succeed to decrease r* and improve the local minimum of the TSP. Computational results for the TSPs with 5 to 20 cities are also presented. [In Japanese.]