Learning-enhanced simulated annealing: Method, evaluation, and application to lung nodule registration

Shaohua Sun, Feng Zhuge, Jarrett Rosenberg, Robert M. Steiner, Geoffrey D. Rubin, Sandy Napel

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


Simulated Annealing (SA) is a popular global minimization method. Two weaknesses are associated with standard SA: firstly, the search process is memory-less and therefore can not avoid revisiting regions that are less likely to contain global minimum; and secondly the randomness in generating a new trial does not utilize the information gained during the search and therefore, the search can not be guided to more promising regions. In this paper, we present the Learning-Enhanced Simulated Annealing (LESA) method to overcome these two difficulties. It adds a Knowledge Base (KB) trial generator, which is combined with the usual SA trial generator to form the new trial for a given temperature. LESA does not require any domain knowledge and, instead, initializes its knowledge base during a "burn-in" phase using random samples of the search space, and, following that, updates the knowledge base at each iteration. This method was applied to 9 standard test functions and a clinical application of lung nodule registration, resulting in superior performance compared to SA. For the 9 test functions, the performance of LESA was significantly better than SA in 8 functions and comparable in 1 function. For the lung nodule registration application, the residual error of LESA was significantly smaller than that produced by a recently published SA system, and the convergence time was significantly faster (9.3±3.2 times). We also give a proof of LESA's ergodicity, and discuss the conditions under which LESA has a higher probability of converging to the true global minimum compared to SA at infinite annealing time.

Original languageEnglish (US)
Pages (from-to)83-99
Number of pages17
JournalApplied Intelligence
Issue number1
StatePublished - Feb 2008
Externally publishedYes


  • Guided search
  • Knowledge base
  • Search history memorization
  • Simulated annealing

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Learning-enhanced simulated annealing: Method, evaluation, and application to lung nodule registration'. Together they form a unique fingerprint.

Cite this