|
Published Articles >> Table of Contents >> Abstract
June 1994 (Vol. 16, No. 6)
pp. 652-656
Simulated Annealing: A Proof of Convergence
V. Granville
M. Krivanek
J.P. Rasson
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/34.295910
Send link to a friend
| Abstract |
|
We prove the convergence of the simulated annealing procedure when the decision to change the current configuration is blind of the cost of the new configuration. In case of filtering binary images, the proof easily generalizes to other procedures, including that of Metropolis. We show that a function Q associated with the algorithm must be chosen as large as possible to provide a fast rate of convergence. The worst case (Q constant) is associated with the "blind" algorithm. On the other hand, an appropriate Q taking sufficiently high values yields a better rate of convergence than that of Metropolis procedure.
|
 References
|
[1] J. Besag, "On the statistical analysis of dirty pictures,"JRSS B, vol. 48, pp. 259-302, 1986.
[2] M. E. Johnson, Ed.,Simulated Annealing and Optimization: Modern Algorithms With VLSI, Optimal Design and Missile Defense Applications. New York: American Science Press, 1989.
[3] G. R. Cross and A. K. Jain, "Markov random field texture models,"IEEE Trans. Pattern Anal. Machine Intell., vol. 5, no. 1, pp. 25-39, 1983.
[4] S. B. Gelfand and S. K. Mitter, "Simulated annealing," inProc. Advanced school CISM, Udine, Italy, 1987, pp. 1-51.
[5] D. Geman, "Random fields and inverse problems in imaging,"Lectures Notes in Mathematics, vol. 1427, pp. 117-196, 1988.
[6] S. Geman and D. Geman, "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 6, 721-741, June 1984.
[7] B. Gidas, "Non stationary Markov chains and convergence of simulated annealing algorithms,"J. Statist. Phys., vol. 39, pp. 73-131, 1985.
[8] V. Granville and J. P. Rasson, "A new modelisation of noise in image remote sensing,"Statist. and Probab. Lett.vol. 14, pp. 61-65, 1992.
[9] V. Granville and J. P. Rasson, "A Bayesian filter for a mixture model of noise in image remote sensing,"Comput. Statist. Data Anal.vol. 15, pp. 297-308, 1993.
[10] V. Granville, J. P. Rasson, and F. Orban-Ferauge, "Un modèle Bayesien de segmentation d'images," inProc. 4th Journées Scientifiques du Réseau de Télédétection de L'UREF, Montréal, Oct. 1991 (to appear).
[11] X. Guyon, "Champs stationnaires surZ2: Modéles, statistique et simulations," UniversitéParis I., 1985.
[12] B. Hajek, "Cooling schedules for optimal annealing,"Math. Oper. Res., vol. 13, no. 2, pp. 311-329, May 1988.
[13] J. M. Hammersley and D. C. Handscomb,Monte Carlo Methods. London: Methuen, 1964.
[14] S. Lakshmanan and H. Derin, "Simultaneous parameter estimation and segmentation of Gibbs random fields using simulated annealing,"IEEE Trans. Pattern Anal. Machine Intell., vol. 11, no. 8, 799-813, Aug. 1989.
[15] P.J.M. van Laarhoven and E.H.L. Aarts,Simulated Annealing: Theory and Applications, Kluwer Academic, Boston, 1987.
[16] R. S. Varga,Matrix Iterative Analysis. Englewood Cliffs, NJ: Prentice-Hall, 1962.
|
 Additional Information
|
Index Terms- simulated annealing; convergence; image processing; simulated annealing; convergence; binary image filtering; Metropolis procedure
Citation:
V. Granville, M. Krivanek, J.P. Rasson,
"Simulated Annealing: A Proof of Convergence,"
IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 16,
no. 6,
pp. 652-656,
Jun.,
1994
|
|
RSS Feed