×

Best-so-far vs. where-you-are: Implications for optimal finite-time annealing. (English) Zbl 0791.90048

Summary: The simulated annealing (SA) algorithm is widely used for heuristic global optimization due to its high-quality results and its ability, in theory, to yield optimal solutions with probability one. Standard SA implementations use monotone decreasing, or ‘cooling’ temperature schedules that are motivated by the algorithm’s proof of optimality as well as by an analogy with statistical thermodynamics. In this paper, we challenge this motivation. The theoretical framework under which monotone cooling schedules are ‘optimal’ fails to capture the practical performance of the algorithm; we therefore propose a ‘best-so-far’ (BSF) criterion that measures the practical utility of a given annealing schedule. For small instances of two classic combinatorial problems, we determine annealing schedules that are optimal in terms of expected cost of the output solution. When the global is to optimize the cost of the last solution seen by the algorithm (the ‘where-you-are’ criterion used in previous theoretical analyses), we confirm the traditional wisdom of cooling temperature schedules. However, if the goal is to optimize the cost of the best solution seen over the entire algorithm execution (i.e., the BSF criterion), we give evidence that optimal schedules do not decrease monotonically toward zero, and are in fact periodic or warming. These results open up many interesting research issues, including the BSF analysis of simulated annealing and how to best apply hill-climbing to difficult global optimizations.

MSC:

90C27 Combinatorial optimization
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Software:

TimberWolf
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baum, E. B., Iterated descent: a better algorithm for local search in combinatorial optimization problems, (Touretzky, D., Proc. Neural Information Processing Systems (1987))
[2] Boese, K. D.; Kahng, A. B.; Tsao, C. W., Best-so-far vs. Where-you-are: new directions in simulated annealing for CAD, UCLA CSD TR-920050 (1992)
[3] Cerny, V., Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. Optim. Theory Appl., 45, 1, 41-51 (1985) · Zbl 0534.90091
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039
[5] Geman, S.; Geman, D., Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. on Pattern Analysis and Machine Intelligence, 6, 721-741 (1984) · Zbl 0573.62030
[6] Hajek, B., Cooling schedules for optimal annealing, Math. Oper. Res., 13, 2, 311-329 (1985) · Zbl 0652.65050
[7] Hajek, B.; Sasaki, G., Simulated annealing — to cool or not, Systems Control Lett., 12, 443-447 (1989) · Zbl 0685.93075
[8] Johnson, D. S., Local optimization and the traveling salesman problem, (Proc. 17th Internat. Colloquium on Automata, Languages and Programming (1990)), 446-460 · Zbl 0766.90079
[9] Johnson, D. S.; Aragon, C. R.; McGeoch, L. A.; Schevon, C., Optimization by simulated annealing: an experimental evaluation; part i, graph partitioning, Oper. Res., 37, 865-892 (1989) · Zbl 0698.90065
[10] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[11] Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), D. Reidel: D. Reidel Boston · Zbl 0643.65028
[12] Lasserre, J. B.; Varaiya, P. P.; Walrand, J., Simulated annealing, random search, multistart or SAD?, Systems Control Lett., 8, 297-301 (1987) · Zbl 0609.90098
[13] Lawler, E. L.; Lenstra, J. K.; Rinnooy-Kan, A.; Shmoys, D., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley Chichester · Zbl 0562.00014
[14] Lengauer, T., Combinatorial Algorithms for Integrated Circuit Layout (1990), Wiley-Teubner: Wiley-Teubner Berlin · Zbl 0709.68039
[15] Lundy, M.; Mees, A., Convergence of an annealing algorithm, Math. Programming, 34, 111-124 (1986) · Zbl 0581.90061
[16] Sechen, C.; Sangiovanni-Vincentelli, A., The timberwolf placement and routing package, IEEE J. Solid-State Circuits, 20, 2, 510-522 (1985)
[17] Sorkin, G. B., Efficient simulated annealing on fractal energy landscapes, Algorithmica, 6, 367-418 (1991) · Zbl 0728.90073
[18] Strenski, P.; Kirkpatrick, S., Analysis of finite length annealing schedules, Algorithmica, 6, 346-366 (1991) · Zbl 0719.90094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.