Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing
Aarts E. (ed), Korst J., John Wiley & Sons, Inc., New York, NY, 1989. Type: Book (9789780471921462)
Date Reviewed: Oct 1 1989

Large combinatorial optimization problems (the most famous example is the traveling salesman problem) are notably difficult because the number of feasible configurations grows exponentially with the size of the problem. Algorithms exist that require fewer calculations and find the optimum solution most of the time or a good suboptimal solution, but they are hard to design and depend strongly upon the problem. A stochastic (i.e., Monte Carlo) approach is an attractive alternative, for the same reasons that such an approach is applied to solving large continuous numerical problems such as multidimensional integro-differential equations: stochastic models are typically simple in concept, easy to implement, and relatively independent of the particulars of the problem. That they are also well suited to parallel computing compensates in part for their slow convergence and the large number of iterations they require.

This book surveys methods and results for two related stochastic approaches to combinatorial optimization: simulated annealing and Boltzmann machines. The annealing process involves heating a solid having a highly irregular lattice structure to a temperature sufficiently high to allow the atoms to migrate. The solid then rearranges itself to an ordered state of lowest energy and settles at the highly ordered ground state when the temperature is slowly decreased. In simulated annealing the lattice structures are identified with the different configurations of the problem (e.g., different routes for the traveling salesman), the energy E corresponds to the optimization parameter (for example, the total length of the routes), and the temperature T is represented by a control parameter of the algorithm. Starting from any configuration of the problem, a random change is made and the resulting change of the optimization parameter dE is calculated. If dE is negative (i.e, closer to the optimum) the change is automatically accepted; if dE is positive the change is accepted with probability exp(−dE/T), corresponding to the laws of statistical thermodynamics. When this procedure is applied repeatedly while the control parameter T is slowly changed from sufficiently high values to zero, the configuration tends to migrate toward an absolute optimum; at the same time, it can escape minima that are only local.

A fair amount of the first part of the text is devoted to proofs of convergence. Except for some minor confusion between discrete and continuous probability distributions, these proofs are complete, detailed, and mathematically rigorous. They show that the number of iterations required to obtain the absolute optimum with probability one grows exponentially with the size of the problem, but to obtain a good suboptimal solution requires a number of trials that grows only polynomially with size. The theoretical part is followed by details of implementation for the traveling salesman problem and a number of graph-theoretic problems such as graph coloring. The authors provide no explicit program listings, but they do give enough information for any competent programmer to create a specific implementation, and they also discuss possible uses of parallel processing. The rest of the first part lists numerical results for the previously discussed problems as well as many others, including scheduling, assignment, and VLSI design problems.

In the second part of the book, the authors discuss the use of a special type of neural network called a Boltzmann machine to realize the same stochastic approximation. The brain functions by means of a large number of nerve cells (neurons) interconnected by synapses. Hardware and software simulations of the brain have been studied intensely for some time, and it has been shown that these simulations can perform many learning and pattern recognition tasks. The Boltzmann machines that the authors describe differ somewhat from anatomical neural networks and their conventional simulations in that connections between neurons are symmetrically bidirectional rather than unidirectional; also, the object of study is not the flow of information (which would be more common) but rather the degree of consensus between neurons. Depending upon whether their connection is excitatory or inhibitory, a consensus between two neurons is achieved when they have either the same or opposite zero-one states.

A combinatorial optimization problem is mapped onto the neural network in such a way that each possible configuration of the problem corresponds to a unique set of zero-one states of the neurons, and the optimum configuration corresponds to the set of the largest consensus. The simulated annealing algorithm can then be applied to the neural network and will lead to mathematically equivalent results. A hardware implementation used as a special-purpose computer for combinatorial optimization problems will have the advantages of higher speed and massive parallel processing, as compared to software implementations on general-purpose computers.

After a description of neural networks and Boltzmann machines that includes a discussion of the simulation of the annealing process on such machines, the authors provide details of implementation for the problems discussed in part 1. The final chapter deals with the application of Boltzmann machines to problems in learning and pattern recognition.

This book contains all the necessary information for someone who wishes to become familiar with this new and exciting field or who plans to begin working actively in it. The theoretically inclined will appreciate the comprehensive discussion of convergence, but someone interested only in implementations and results can easily skip this part. The list of references is good and up to date (to 1988). It was a pleasure to read this book, and I congratulate the publisher for its excellent layout, including the indices and the list of symbols. The book is obviously not intended for classroom use, but it is well suited for use in a graduate seminar in computer science.

Reviewer:  F. W. Stallmann Review #: CR113419
Bookmark and Share
 
Optimization (G.1.6 )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Parallel Processors (C.1.2 ... )
 
 
Approximation (G.1.2 )
 
 
General (I.6.0 )
 
 
Learning (I.2.6 )
 
Would you recommend this review?
yes
no
Other reviews under "Optimization": Date
A general-purpose global optimizer: implementation and applications
Pronzato L., Walter E., Venot A., Lebruchec J. Mathematics and Computers in Simulation XXVI(5): 412-422, 1984. Type: Article
Jul 1 1985
Minkowski matrices.
Cryer C. ACM Transactions on Mathematical Software 9(2): 199-214, 1983. Type: Article
Feb 1 1985
Numerical optimization techniques
Evtushenko Y., Springer-Verlag New York, Inc., New York, NY, 1985. Type: Book (9789780387909493)
Jun 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy