Guaranteed convergence in a class of Hopfield networks
Authors:
- S. DasguptaSDS. Dasgupta
- S.M. ReddySRS.M. Reddy
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 3 (6) , 951-961
Abstract
A class of symmetric Hopfield networks with nonpositive synapses and zero threshold is analyzed in detail. It is shown that all stationary points have a one-to-one correspondence with the minimal vertex covers of certain undirected graphs, that the sequential Hopfield algorithm as applied to this class of networks converges in at most 2n steps (n being the number of neurons), and that the parallel Hopfield algorithm either converges in one step or enters a two-cycle in one step. The necessary and sufficient condition on the initial iterate for the parallel algorithm to converge in one step are given. A modified parallel algorithm which is guaranteed to converge in [3n/2] steps ([x] being the integer part of x) for an n-neuron network of this particular class is also given. By way of application, it is shown that this class naturally solves the vertex cover problem. Simulations confirm that the solution provided by this method is better than those provided by other known methods.Keywords
This publication has 6 references indexed in Scilit:
- Neural networks, error-correcting codes, and polynomials over the binary n-cubeIEEE Transactions on Information Theory, 1989
- A generalized convergence theorem for neural networksIEEE Transactions on Information Theory, 1988
- “Neural” computation of decisions in optimization problemsBiological Cybernetics, 1985
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 1982
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981