Introduces a method of solution for maximizing annealing, while minimizing cost, using massively parallel processing for quick execution. Establishes a correspondence between the free energy of the material being annealed and the cost function, and between the solutions and the physical states--the result is a solution method of combinatorial optimization based on a simulation of the annealing process. This method features general applicability and the ability to produce solutions arbitrarily close to an optimum. Part I treats the simulated annealing algorithm in detail. Part II addresses the problem of designing parallel annealing algorithms on the basis of Boltzmann machines.
Simulated Annealing and Boltzmann Machines A Stochastic Approach to Combinatorial Optimization and Neural Computing Emile Aarts, Philips Research Laboratories, Eindhoven, and Eindhoven University of Technology, The Netherlands Jan Korst, Philips Research Laboratories, Eindhoven, The Netherlands Simulated annealing is a solution method in the field of combinatorial optimization based on an analogy with the physical process of annealing. The method is generally applicable, and can obtain solutions arbitrarily close to an optimum. However, finding high quality solutions can require large computational effort. The computational effort required can be greatly reduced by using the computational model of the Boltzmann machine. This is a neural network model which belongs to the class of connectionist models. It is characterized by massive parallelism and distributed representations. These features lead to a conceptually simple yet powerful model, which can be seen as an architectural blueprint for future parallel computers which can cope with higher order optimization problems such as learning. This book brings together in one volume the theory of simulated annealing and the model of the Boltzmann machine. It combines a mathematical treatment with a clear view of the applications which are already possible and the exciting developments which are beginning. It will be of great interest to graduate students and researchers in combinatorial optimization, numerical optimization, parallel processing, neural networks, computer science, artificial intelligence and automaton theory. Contents Preface
- Simulated Annealing
- Combinatorial Optimization
- Simulated Annealing
- Asymptotic Convergence
- Finite-Time Approximation
- Simulated Annealing in Practice
- Parallel Simulated Annealing Algorithms
- Boltzmann Machines
- Neural Computing
- Boltzmann Machines
- Combinatorial Optimization and Boltzmann Machines
- Classification and Boltzmann Machines
- Learning and Boltzmann Machines
Appendix A: The EUR100 Instance Bibliography