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

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.