article

"Neural" computation of decisions in optimization problems

Authors:

J. J. Hopfield,

D. W. TankAuthors Info & Claims

Biological Cybernetics, Volume 52, Issue 3

Pages 141 - 152

Published: 01 July 1985 Publication History

Abstract

Highly-interconnected networks of nonlinear analog neurons are shown to be extremely effective in computing. The networks can rapidly provide a collectively-computed solution (a digital output) to a problem on the basis of analog input information. The problems to be solved must be formulated in terms of desired optima, often subject to constraints. The general principles involved in constructing networks to solve specific problems are discussed. Results of computer simulations of a network designed to solve a difficult but well-defined optimization problem-the Traveling-Salesman Problem-are presented and used to illustrate the computational power of the networks. Good solutions to this problem are collectively computed within an elapsed time of only a few neural time constants. The effectiveness of the computation involves both the nonlinear analog response of the neurons and the large connectivity among them. Dedicated networks of biological or microelectronic neurons could provide the computational capabilities described for a wide class of problems having combinatorial complexity. The power and speed naturally displayed by such collective networks may contribute to the effectiveness of biological information processing.

References

[1]

Anderson, P.W.: Ch. 2. In: Basic notions of condensed matter physics. Menlo Park: Benjamin Cummings 1984.

[2]

Arbib, M.A.: Artificial intelligence and brain theory: unities and diversities. Ann. Biomed. Eng. 3, 238-274 (1975).

[3]

Ballard, D.H.: Cortical connections and parallel processing: structure and function. Behav. Brain Sci. (1985, in press).

[4]

Ballard, D.H., Hinton, G.E., Sejnowski, T.J.: Parallel visual computation. Nature 306, 21-26 (1983).

[5]

Feldman, J.A., Ballard, D.H.: Connectionist models and their properties. Cog. Sci. 6, 205-254 (1982).

[6]

Garey, M.R., Johnson, D.S.: Computers and intractability. New York: W.H. Freeman 1979.

[7]

Gelperin, A.E., Hopfield, JJ., Tank, D.W.: The logic of Limax learning. In: Model neural networks and behavior. Selverston, A., ed. New York: Plenum Press 1985.

[8]

Goldman-Rakic, P.S.: Modular organization of the prefrontal cortex. Trends Neurosci. 7, 419-424 (1984).

[9]

Gross, DJ., Mezard, M.: The simplest spin glass. Nucl. Phys. FS B 240, 431-452 (1984).

[10]

Hinton, G.E., Sejnowski, TJ.: Optimal perceptual inference. In: Proc. IEEE Comp. Soc. Conf. Comp. Vision & Pattern Recog., pp. 448-453, Washington, D.C., June 1983.

[11]

Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. USA 79, 2554-2558 (1982).

[12]

Hopfield, J.J.: Neurons with graded response have collective computational properties like those of two-state neurons. Proc. Natl. Acad. Sci. USA 81, 3088-3092 (1984).

[13]

Huskey, H.D., Korn, G.A.: Computer Handbook, pp. 1-4. New York: McGraw Hill 1962.

[14]

Ikeuchi, K., Horn, B.K.P.: Numerical shape from shading and occluding boundaries. Artif. Intell. 17, 141-184 (1981).

Digital Library

[15]

Jackson, W.A.: Analog computation, pp. 5-8. New York: McGraw Hill 1960.

[16]

Julesz, B.: In: Foundations of cyclopean vision. Chicago: University of Chicago Press 1971.

[17]

Julesz, B.: Textons, the elements of texture perception, and their interactions. Nature 290, 91-97 (1981).

[18]

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671-680 (1983).

[19]

Koch, C., Poggio, T., Torte, V.: Nonlinear interactions in a dendritic tree: Localization, timing, and role in information processing. Proc. Natl. Acad. Sci. USA 80, 2799 (1983).

[20]

Lawler, E.L., Lenstra, A., Rinnooy Kan, H.G., Eds.: The traveling salesman problem. New York: John Wiley (in press).

[21]

Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 498-516 (1973).

Digital Library

[22]

Marr, D.: Vision. New York: W. H. Freeman 1982.

[23]

Mead, C., Conway, L.: Introduction to VLSI systems, pp. 12, 265. Reading, MA: Addison-Wesley 1980.

[24]

Poggio, T., Koch, C.: An analog model of computation for the ill-posed problems of early vision. M.I.T. Artif. Intell. Lab. A.I. Memo No. 783, 1984.

[25]

Poggio, T., Torte, V.: Ill-posed problems in early vision. Proc. Roy. B. (1985, in press).

[26]

Sebestyn, G.S.: Decision-making processes in pattern recognition. New York: McMillan 1962.

[27]

Shepherd, G.M.: Microcircuits in the nervous system. Sci. Am. 238, 92-103 (1978).

[28]

Terzopoulos, D.: Multilevel reconstruction of visual surfaces: variational principles and finite element representations. In: Multi-resolution image processing and analysis. Rosenfeld, A., ed. Berlin, Heidelberg, New York: Springer 1984.

[29]

Thouless, D.J., Anderson, P.W., Palmer, R.G.: Solution of "solvable model of a spin glass". Phil. Mag. 35, 593-601 (1977).

[30]

Tomovic, R., Karplus, W.J.: High speed analog computers, p. 4. New York: Wiley 1962.

[31]

Wannier, G.H.: Statistical physics, p. 330ff. New York: Wiley 1966.

Cited By

Darintsev OMigranov A(2024)Modification of the Hopfield Neural Network Model for Solving the Problem of Optimal Task Allocation in a Group of Mobile RobotsJournal of Computer and Systems Sciences International10.1134/S106423072470025463:2(371-383)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1134/S1064230724700254
Cursino CDias L(2024)Hybrid Hopfield Neural NetworkSN Computer Science10.1007/s42979-023-02575-65:2Online publication date: 27-Jan-2024
https://dl.acm.org/doi/10.1007/s42979-023-02575-6
Kikuta DIkeuchi HTajiri KNakano Y(2024)RouteExplainer: An Explanation Framework for Vehicle Routing ProblemAdvances in Knowledge Discovery and Data Mining10.1007/978-981-97-2259-4_3(30-42)Online publication date: 7-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2259-4_3
Show More Cited By

"Neural" computation of decisions in optimization problems
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Dynamics of information and emergent computation in generic neural microcircuit models

Numerous methods have already been developed to estimate the information contained in single spike trains. In this article we explore efficient methods for estimating the information contained in the simultaneous firing activity of hundreds of neurons. ...
Finite-State Computation in Analog Neural Networks: Steps towards Biologically Plausible Models?
Emergent Neural Computational Architectures Based on Neuroscience - Towards Neuroscience-Inspired Computing

Finite-state machines are the most pervasive models of computation, not only in theoretical computer science, but also in all of its applications to real-life problems, and constitute the best characterized computational model. On the other hand, neural ...
Polychronization: Computation with Spikes

We present a minimal spiking network that can polychronize, that is, exhibit reproducible time-locked but not synchronous firing patterns with millisecond precision, as in synfire braids. The network consists of cortical spiking neurons with axonal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Biological Cybernetics

Biological Cybernetics Volume 52, Issue 3

July 1985

69 pages

ISSN:0340-1200

Issue’s Table of Contents

Copyright © Copyright © 1985 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 1985

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

446
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Darintsev OMigranov A(2024)Modification of the Hopfield Neural Network Model for Solving the Problem of Optimal Task Allocation in a Group of Mobile RobotsJournal of Computer and Systems Sciences International10.1134/S106423072470025463:2(371-383)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1134/S1064230724700254
Cursino CDias L(2024)Hybrid Hopfield Neural NetworkSN Computer Science10.1007/s42979-023-02575-65:2Online publication date: 27-Jan-2024
https://dl.acm.org/doi/10.1007/s42979-023-02575-6
Kikuta DIkeuchi HTajiri KNakano Y(2024)RouteExplainer: An Explanation Framework for Vehicle Routing ProblemAdvances in Knowledge Discovery and Data Mining10.1007/978-981-97-2259-4_3(30-42)Online publication date: 7-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2259-4_3
Grinsztajn NFurelos-Blanco DSurana SBonnet CBarrett TOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Winner takes it allProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668227(48485-48509)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668227
Caramanis CFotakis DKalavasis AKontonis VTzamos COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Optimizing solution-samplers for combinatorial problemsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666741(14035-14069)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666741
Chalumeau FSurana SBonnet CGrinsztajn NPretorius ALaterre ABarrett TOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Combinatorial optimization with policy adaptation using latent space searchProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666470(7947-7959)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666470
Sun HGoshvadi KNova ASchuurmans DDai HKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Revisiting sampling for combinatorial optimizationProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619772(32859-32874)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619772
Bani Hassan JMirzazadeh ZAbdi SEshaghnezhad MMansoori A(2023)A Novel Neurodynamic Model for Data Envelopment Analysis: A Case Study on Iran’s Olympic Sports CaravanNeural Processing Letters10.1007/s11063-023-11410-155:9(12079-12092)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s11063-023-11410-1
Behera RGerontitis DStanimirović PKatsikis VShi YCao X(2023)An efficient zeroing neural network for solving time-varying nonlinear equationsNeural Computing and Applications10.1007/s00521-023-08621-x35:24(17537-17554)Online publication date: 12-May-2023
https://dl.acm.org/doi/10.1007/s00521-023-08621-x
Kleyko DBybee CKymn COlshausen BKhosrowshahi ANikonov DSommer FFrady E(2022)Integer Factorization with Compositional Distributed RepresentationsProceedings of the 2022 Annual Neuro-Inspired Computational Elements Conference10.1145/3517343.3517368(73-80)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1145/3517343.3517368
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents