Generalized deterministic annealing
Authors:
- 1 May 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 7 (3) , 686-699
Abstract
We develop a general formalism for computing high quality, low-cost solutions to nonconvex combinatorial optimization problems expressible as distributed interacting local constraints. For problems of this type, generalized deterministic annealing (GDA) avoids the performance-related sacrifices of current techniques. GDA exploits the localized structure of such problems by assigning K-state neurons to each optimization variable. The neuron values correspond to the probability densities of K-state local Markov chains and may be updated serially or in parallel; the Markov model is derived from the Markov model of simulated annealing (SA), although it is greatly simplified. Theorems are presented that firmly establish the convergence properties of GDA, as well as supplying practical guidelines for selecting the initial and final temperatures in the annealing process. A benchmark image enhancement application is provided where the performance of GDA is compared to other optimization methods. The empirical data taken in conjunction with the formal analytical results suggest that GDA enjoys significant performance advantages relative to current methods for combinatorial optimization.Keywords
This publication has 7 references indexed in Scilit:
- Mean field annealing: a formalism for constructing GNC-like algorithmsIEEE Transactions on Neural Networks, 1992
- Improving the performance of the Hopfield-Tank neural network through normalization and annealingBiological Cybernetics, 1989
- Restoration of piecewise-constant images by mean-field annealingJournal of the Optical Society of America A, 1989
- A NEW METHOD FOR MAPPING OPTIMIZATION PROBLEMS ONTO NEURAL NETWORKSInternational Journal of Neural Systems, 1989
- Cooling Schedules for Optimal AnnealingMathematics of Operations Research, 1988
- “Neural” computation of decisions in optimization problemsBiological Cybernetics, 1985
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1984