Improving the Hopfield Model for TSP Feasible Solutions by Synapse Dynamical Systems

Yoshikane TAKAHASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.5   pp.694-708
Publication Date: 1996/05/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Neural Networks
Hopfield model,  traveling salesman problem,  feasible solutions,  synapse dynamical systems,  continuous optimization problems,  

Full Text: PDF>>
Buy this Article

It is well known that the Hopfield Model (HM) for neural networks to solve the TSP suffers from three major drawbacks: (D1) it can converge to non-optimal local minimum solutions; (D2) it can also converge to non-feasible solutions; (D3) results are very sensitive to the careful tuning of its parameters. A number of methods have been proposed to overcome (D1) well. In contrast, work on (D2) and (D3) has not been sufficient; techniques have not been generalized to larger classes of optimization problems with constraint including the TSP. We first construct Extended HMs (E-HMs) that overcome both (D2) and (D3). The extension of the E-HM lies in the addition of a synapse dynamical system cooperated with the corrent HM unit dynamical system. It is this synapse dynamical system that makes the TSP constraint hold at any final states for whatever choices of the HM parameters and an initial state. We then generalize the E-HM further into a network that can solve a larger class of continuous optimization problems with a constraint equation where both of the objective function and the constraint function are non-negative and continuously differentiable.