Abstract
The potential of Boltzmann machines to cope with difficult combinatorial optimization problems is investigated. A discussion of various (parallel) models of Boltzmann machines is given based on the theory of Markov chains. A general strategy is presented for solving (approximately) combinatorial optimization problems with a Boltzmann machine. The strategy is illustrated by discussing the details for two different problems, namely MATCHING and GRAPH PARTITIONING.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aarts, E. H. L., and J. H. M. Korst [1989a],Simulated Annealing and Boltzmann Machines, Wiley, Chichester.
Aarts, E. H. L., and J. H. M. Korst [1989b], Boltzmann machines and the travelling salesman problem,The European Journal of Operational Research,39, 79–95.
Alspector, J., and R. B. Allen [1987], A neuromorphic VLSI learning system, in: P. Losleben (Ed.),Advanced Research in VLSI, MIT Press, Cambridge, MA, pp. 313–349.
Amit, D. J., H. Gutfreund, and H. Sompolinsky [1987], Information storage in neural networks with low levels of activity,Physical Review A,35, 2293–2303.
Dennis, J., and E. Van Horn [1966], Programming semantics for multiprogrammed computations,Communications of the ACM,9, 143–154.
Dolev, D., N. A. Lynch, S. S. Pinter, E. W. Stark, and W. E. Weihl [1986], Reaching approximate agreement in the presence of faults, Programming semantics for multiprogrammed computations,Journal of the ACM,33, 499–516.
Fahlman, S. E., and G. E. Hinton [1987], Connectionist architectures for artificial intelligence,Computer,20, 100–109.
Feldman, J. A., and D. H. Ballard [1982], Connectionist models and their properties,Cognitive Science,6, 205–254.
Feller, W. [1950],An Introduction to Probability Theory and Its Applications, Vol. 1, Wiley, New York.
Garey, M. R., and D. S. Johnson [1979],Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco.
Genesereth, M. R., M. L. Ginsberg, and J. S. Rosenschein [1986], Cooperation about communication,Proceedings of the Fifth National Conference on Artificial Intelligence, Vol. 1, pp. 551–557.
Gutzmann, K. M. [1987], Combinatorial optimization using a continuous state Boltzmann machineProceedings of the International Conference on Neural Networks, San Diego, Vol. 3, pp. 721–734.
Hinton, G. E., T. J. Sejnowski and D. H. Ackley [1984], Boltzmann Machines: Constraint Satisfaction Networks that Learn, Technical Report CMU-CS-84-119, Carnegie-Mellon University.
Hopfield, J. J. [1982], Neural networks and physical systems with emergent collective computational abilities,Proceedings of the National Academy of Sciences of the USA,79, 2554–2558.
Hopfield, J. J., and D. W. Tank [1985], Neural computation of decisions in optimization problems,Biological Cybernetics,52, 141–152.
Hopfield, J. J., and D. W. Tank [1986], Computing with neural circuits: a model,Science,233, 625–633.
Kirkpatrick, S., C. D. Gelatt Jr., and M. P. Vecchi [1983], Optimization by simulated annealing,Science,220, 671–680.
Korst, J. H. M., and E. H. L. Aarts [1989], Combinatorial optimization on a Boltzmann machine,Journal of Parallel and Distributed Computing,6, 331–357.
Levy, B. C., and M. B. Adams [1987], Global optimization with stochastic networks,Proceedings of the International Conference on Neural Networks, San Diego, Vol. 3, pp. 681–690.
Little, W. A. [1974], The existence of persistent states in the brain,Mathematical Biosciences,19, 101–120.
Little, W. A., and G. L. Shaw [1978], Analytic study of the memory storage capability of a neural network,Mathematical Biosciences,39, 281–290.
Morgenstern, I. [1987], Spin glasses, optimization and neural networks, in: J. L. van Hemmen and I. Morgenstern (Eds.), Lecture Notes in Physics, Vol. 275, Springer-Verlag, Berlin, pp. 399–427.
Moussouris, J. [1974], Gibbs and Markov random systems with constraints,Journal of Statistical Physics,10, 11–33.
Peretto, P. [1984], Collective properties of neural networks: a statistical physics approach,Biological Cybernetics,50, 51–62.
Personnaz, L., I. Guyon, and G. Dreyfus [1985], Information storage and retrieval in spin-glass like neural networks,Journal de Physique Lettres,46, 359–365.
Rumelhart, D. E., J. L. McClelland, and the P.D.P. Research Group (Eds.) [1986],Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Bradford Books, Cambridge, MA.
Ticknor, A. J., and H. H. Barrett [1987], Optical implementations in Boltzmann machines,Optical Engineering,26, 16–21.
Toulouse, G., S. Dehaene, and J. Changeux [1986], Spin-glass models of neural networks,Proceedings of the National Academy of Sciences of the USA,83, 1695–1698.
Treleaven, P. C. [1988], Parallel architectures for neurocomputers,Proceedings of the European Seminar on Neural Computing, London.
Van Hemmen, J. L. [1982], Classical spin-glass model,Physics Review Letters,49, 409–412.
Van Laarhoven, P. J. M., and E. H. L. Aarts [1987],Simulated Annealing: Theory and Applications, Reidel, Dordrecht.
Author information
Authors and Affiliations
Additional information
Communicated by Alberto Sangiovanni-Vincentelli.
Rights and permissions
About this article
Cite this article
Aarts, E.H.L., Korst, J.H.M. Boltzmann machines as a model for parallel annealing. Algorithmica 6, 437–465 (1991). https://doi.org/10.1007/BF01759053
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01759053