Catalogue of Artificial Intelligence Techniques
Keywords: Travelling Salesman Problem, neural networks
Categories: Neural Networks
Author(s): Ashley Walker
The Hopfield Network, introduced in the early 1980s by John Hopfield, can be used (i) as an Associative Memory, (ii) to perform Constraint Satisfaction, or (iii) as a model of a physical (spin glass) system. Hopfield not only formulated a network model, but also contributed a set of analysis tools which employ the concept of an energy function. Hopfield's network is implemented as a fully connected array of nodes which contain symmetrical connections (or weights). Each node calculates the weighted sum of its binary inputs (minus a threshold value) and applies a step-function to the result in order to determine its output state. When employed as an associative memory, a recipe is used to calculate the weights as a function of the input patterns to be stored (i.e., inputs are associated with each other). Recall is performed by presenting the net with an unknown pattern (e.g., a degraded version of a stored pattern) as a set of starting states for all the nodes. The network then proceeds to cycle through a succession of states until it converges on a stable solution. The operation of the network can also be understood from an energy perspective. This involves creating an energy function such that the programmed patterns are basins of attraction within some energy landscape which describes the possible states of the system. In order to perform combinatorial and optimisation problems (e.g, the Travelling Salesman Problem), the network cannot be programmed using the desired attractors (because they comprise the solution), but rather is programmed directly from the energy function of which a minimum is sought.
- Hertz, J., Krough, A. and Palmer, R.G., Introduction to the Theory of Neural Computation
, Addison Wesley, 1991.