Solution of the recirculant multilayer graph problem using compensated simulated annealing

Wesley E. Snyder; Terri Johnson; David M. Herrington; Griff L. Bilbro

doi:10.1117/12.130851

Translator Disclaimer

16 December 1992 Solution of the recirculant multilayer graph problem using compensated simulated annealing

Wesley E. Snyder, Terri Johnson, David M. Herrington, Griff L. Bilbro

Author Affiliations +

Proceedings Volume 1766, Neural and Stochastic Methods in Image and Signal Processing; (1992) https://doi.org/10.1117/12.130851
Event: San Diego '92, 1992, San Diego, CA, United States

Abstract

Stochastic simulated annealing (SSA) is a popular method for solving optimization functions in which the objective function has multiple minima. Not only can SSA find minima, but it has been proven to converge (under certain conditions) to the global minimum. The principal drawback to SSA has been its convergence rate. In order to preserve the conditions of the convergence proof, the algorithm must be run so slowly as to be impractical for many applications. In this paper, an extension to SSA is described which allows the user to provide additional a priori information to the algorithm which may allow much more rapid convergence. The new method, called `compensated simulated annealing' (CSA) is also guaranteed to converge. A problem of finding a minimum path through a recurrent multilayer graph is described. Then a practical motivating application from medical imaging is presented. The graph structure is used to model the boundary of an artery in an intra-arterial ultrasound image. The optimization problem is posed and solved by SSA and CSA as a means of comparing the two methods. The CSA approach is shown to converge significantly faster than SSA.

Citation Download Citation

Wesley E. Snyder, Terri Johnson, David M. Herrington, and Griff L. Bilbro "Solution of the recirculant multilayer graph problem using compensated simulated annealing", Proc. SPIE 1766, Neural and Stochastic Methods in Image and Signal Processing, (16 December 1992); https://doi.org/10.1117/12.130851

ACCESS THE FULL ARTICLE