AN ANALOG NEURAL-NETWORK TO SOLVE THE HAMILTONIAN CYCLE PROBLEM

Hopfield's (analog) neural net algorithm shows very different characte ristics when the net is allowed to evolve while the gain factor of the neural response is gradually increased. The study of the new approach (called quasi stationary flow) yields that (1) The net converges if t he weights are symmetric and the strength of inhibitory self connectio n is less than the slope of the transfer function (i.e., -w(a,a) < g(l ambdamin)-1'); and (2) The energy of the net decreases, and the distan ce of the state from the center of the cube, in the unit cube represen tation of the state space, increases with the increase in the gain fac tor (i.e., (1/lambda)dR2/dlambda = -2dE/dlambda > 0). This approach ha s been successful in solving very large optimization problems. The qua si stationary approach is applied to the Hopfield and Tank's algorithm to solve the Traveling Salesman Problem (TSP). Besides the method of approaching the stable state, modifications are also suggested in (i) the energy function; (ii) the method of determining the energy coeffic ients; and (iii) the connectivity of the network. Results are reported of experiments with the Hamiltonian Cycle Problem (HCP or discrete TS P) on graphs of up to 500 nodes. The result of experiments with the we ll known 318 city TSP is also reported and compared with its best know n solution computed by linear programming.