Fast TSP algorithm based on binary neuron output and analog neuron input using the zero-diagonal interconnect matrix and necessary and sufficient constraints of the permutation matrix

摘要

Alleged difficulties of the original Hopfield and Tank (H-T) neural network model reported by G.V. Wilson and G.S. Pawley (1988) in attempting a scaled-up VLSI implementation of the traveling salesman problem (TSP) are clarified and repudiated. A simple refinement is presented that has sped up and eliminated the decaying dynamics compounded by the feeble and indecisive analog neurons having a self-decaying interconnect. In summary, the modified TSP version is based on binary neuronic output, analog neuronic input, a zero diagonal interconnect matrix, the necessary and sufficient constraint of a permutation matrix, Lagrangian multipliers a=b=c=1, and Euler's first-order integration with the step constant about 10/sup -4/. Programs, one written in True Basic running on a microcomputer (Macintosh Plus or Mac II) and the other written in C on a mainframe computer, are briefly mentioned.