Simulated annealing: Practice versus theory. (English) Zbl 0819.90080

Ingber, L.

Math. Comput. Modelling 18, No. 11, 29-57 (1993).

Summary: Simulated annealing (SA) presents an optimization technique with several striking positive and negative features. Perhaps its most salient feature, statistically promising to deliver an optimal solution, in current practice is often spurned to use instead modified faster algorithms, “simulated quenching” (SQ). Using the author’s Adaptive Simulated Annealing (ASA) code, some examples are given which demonstrate how SQ can be much faster than SA without sacrificing accuracy.

MSC:

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

Keywords:

random algorithm; simulated annealing; simulated quenching

Software:

ASA; simannf90

References:

[1]	Ma, S. K., Statistical Mechanics (1985), World Scientific: World Scientific Philadelphia
[3]	Gelfand, S. B., Analysis of simulated annealing type algorithms, (Ph.D. Thesis (1987), MIT: MIT Cambridge, MA) · Zbl 0651.90059
[4]	van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), D. Reidel: D. Reidel Dordrecht, The Netherlands · Zbl 0643.65028
[5]	Collins, N. E.; Egelese, R. W.; Golden, B. L., Simulated annealing—An annotated bibliography, Am. J. Math. Management Sci., 8, 3/4, 209-307 (1988) · Zbl 0669.65047
[6]	Ingber, L., Adaptive simulated annealing (ASA) (1993), L. Ingber Research: L. Ingber Research McLean, VA, ftp.caltech.edu:/pub/ingber/ASA-shar.Z, ASA.tar.gz · Zbl 0819.90080
[7]	Charnes, A.; Wolfe, M., Extended Pincus theorems and convergence of simulated annealing, Int. J. Systems Sci., 20, 8, 1521-1533 (1989) · Zbl 0685.93081
[8]	Pincus, M., A Monte Carlo method for the approximate solution of certain types of constrained optimization problems, Oper. Res., 18, 1225-1228 (1970) · Zbl 0232.90063
[9]	Kirkpatrick, A. S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[10]	Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equation of state calculations by fast computing machines, J. Chem. Phys., 21, 6, 1087-1092 (1953) · Zbl 1431.65006
[11]	Geman, S.; Geman, D., Stochastic relaxation, Gibbs distribution and the Bayesian restoration in images, IEEE Trans. Patt. Anal. Mac. Int., 6, 6, 721-741 (1984) · Zbl 0573.62030
[13]	Szu, H.; Hartley, R., Fast simulated annealing, Phys. Lett. A, 122, 3/4, 157-162 (1987)
[14]	Binder, K.; Stauffer, D., A simple introduction to Monte Carlo simulations and some specialized topics, (Binder, K., Applications of the Monte Carlo Method in Statistical Physics (1985), Springer-Verlag: Springer-Verlag Berlin), 1-36
[15]	Mathews, J.; Walker, R. L., Mathematical Methods of Physics, ((1970), Benjamin: Benjamin New York, NY) · Zbl 0238.00005
[16]	Ingber, L., Very fast simulated re-annealing, Mathl. Comput. Modelling, 12, 8, 967-973 (1989) · Zbl 0681.90091
[17]	Holland, J., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI
[18]	De Jong, K. A., Genetic algorithms are NOT function optimizers, (Whitley, D., (Vail, CO), July 24-29, 1992. (Vail, CO), July 24-29, 1992, Foundations of Genetic Algorithms: Proceedings (1992), Morgan Kaufman)
[19]	Michalewicz, Z.; Janikow, C. Z., Genetic algorithms for numerical optimization, Statistics Computing, 1, 75-91 (1991)
[20]	Schaffer, J. D.; Eshelman, L. J.; Offutt, D., Spurious correlations and premature convergence in genetic algorithms, (Rawlins, G., Foundations of Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 102-112
[21]	Ingber, L.; Rosen, B., Genetic algorithms and very fast simulated reannealing: A comparison, Mathl. Comput. Modelling, 16, 11, 87-100 (1992) · Zbl 0791.68138
[23]	Fogel, D. B.; Atmar, J. W., Comparing genetic operators with Gaussian mutations in simulated evolutionary processes using linear systems, Biol. Cybern, 63, 111-114 (1990)
[24]	Goldberg, D. E., A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing, Complex Sys., 4, 445-460 (1990) · Zbl 0717.68083
[25]	Sen, M. K.; Stoffa, P. L., Comparative analysis of simulated annealing and genetic algorithms: Theoretical aspects and asymptotic convergence, Geophys. (1993), (submitted)
[26]	Corana, A.; Marchesi, M.; Martini, C.; Ridella, S., Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm, ACM Trans. Mathl. Software, 13, 3, 272-280 (1987) · Zbl 0632.65075
[27]	Ingber, L.; Rosen, B., Very Fast Simulated Reannealing (VFSR) (1992), University of Texas: University of Texas San Antonio, TX, ringer.cs.utsa.edu:/pub/rosen/vfsr.Z · Zbl 0791.68138
[29]	Rosen, B., Function optimization based on advanced simulated annealing, (IEEE Workshop on Physics and Computation—PhysComp ’92 (1992), IEEE Press: IEEE Press Dallas, TX), 289-293
[30]	Simic, P. D., Statistical mechanics as the underlying theory of ‘elastic’ and ‘neural’ optimisations, Network, 1, 89-103 (1990) · Zbl 0850.82038
[31]	Bonomi, E.; Lutton, J.-L., The N-city travelling salesman problem: Statistical mechanics and the metropolis algorithm, SIAM Rev., 26, 4, 551-568 (1984) · Zbl 0551.90095
[33]	Murray, M.; Burr, J. B.; Stork, D. S.; Leung, M.-T.; Boonyanit, K.; Wolff, G. J.; Peterson, A. M., Deterministic Boltzmann machine VLSI can be scales using multi-chip modules, (Fortes, J.; Lee, E.; Meng, T., Application Specific Array Processors (1992), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 206-217
[34]	Bucy, R. S.; DiEsposti, R. S., Decision tree design by simulated annealing, Math. Modelling Numer. Anal. (1992), (submitted) · Zbl 0784.90104
[36]	Jagota, A., Efficiently approximating Mac-Clique in a Hopfield-style network, (International Joint Conference on Neural Networks (1992), IEEE: IEEE Baltimore, MD), 248-353
[37]	Elliot, J. R.; Gibbons, P. B., The construction of subsquare free Latin squares by simulated annealing, Australasian J. Combinatorics, 5, 209-228 (1992) · Zbl 0761.05017
[38]	Peterson, C.; Anderson, J. R., Neural networks and NP-complete optimization problems: A performance study on the graph bisection problem, Complex Sys., 2, 59-89 (1988) · Zbl 0653.90086
[40]	Packer, C. V., Applying row-column permutation to matrix representations of large citation networks, Inform. Processing Management, 25, 3, 307-314 (1989)
[41]	Klein, R. W.; Dubes, R. C., Experiments in projection and clustering by simulated annealing, Pattern Recognition, 22, 2, 213-220 (1989) · Zbl 0709.62613
[42]	Kelly, J.; Golden, B.; Assad, A., Using simulated annealing to solve controlled rounding problems, ORSA J. Comput., 2, 2, 174-185 (1990) · Zbl 0762.65027
[43]	Raittinen, H.; Kaski, K., Image deconvolution with simulated annealing method, Physica Scripta, T33, 126-130 (1990)
[44]	Bilbro, G., Efficient generators in simulated annealing, (Report TR-91/12 (1991), North Carolina State University: North Carolina State University Raleigh, NC)
[45]	Black, M. J.; Anandan, P., Robust dynamic motion estimation over time, (CVPR-91, Maui, HI, June 3-6, 1991. CVPR-91, Maui, HI, June 3-6, 1991, Proc. Comput. Vis. Patt. Recog. (1991), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 296-302
[46]	Kishida, K., Physical Langevin model and the time-series model in systems far from equilibrium, Phys. Rev. A, 25, 496-507 (1982)
[47]	Kishida, K., Equivalent random force and time-series model in systems far from equilibrium, J. Math. Phys., 25, 1308-1313 (1984)
[48]	Ingber, L., Statistical mechanics algorithm for response to targets (SMART), (Cheeseman, P., UC Los Angeles, August 14-16, 1985. UC Los Angeles, August 14-16, 1985, Workshop on Uncertainty and Probability in Artificial Intelligence (1985), American Association for Artificial Intelligence: American Association for Artificial Intelligence Menlo Park, CA), 258-264
[49]	Ackley, D. H.; Hinton, G. E.; Sejnowski, T. J., A learning algorithm for Boltzmann machines, Cog. Sci., 9, 147-169 (1985)
[50]	Hertz, J.; Krogh, A.; Palmer, R. G., Introduction to the Theory of Neural Computation (1991), Addison-Wesley: Addison-Wesley Redwood City, CA
[52]	Bilbro, G.; Mann, R.; Miller, T. K.; Snyder, W. E.; Van der Bout, D. E.; White, M., Optimization by mean field annealing, (Touretzky, D., Advances in Neural Network Information Processing Systems (1989), Morgan-Kaufman: Morgan-Kaufman San Mateo, CA), 91-98
[53]	Simic, P. D., Constrained nets for graph matching and other quadratic assignment, Neural Comput., 3, 2 (1991)
[54]	Peterson, C.; Söderberg, B., Artificial neural networks and combinatorial optimization problems, (Aarts, E. H.L.; Lenstra, J. K., Local Search in Combinatorial Optimization (1992), John Wiley & Sons: John Wiley & Sons New York, NY), (to appear)
[55]	Niittylahti, J., Hardware implementation of Boolean neural network using simulated annealing, (Report 8-92 (1992), Tampere University of Technology: Tampere University of Technology Tampere, Finland)
[56]	Goodwin, J. M.; Rosen, B. E.; Vidal, J. J., Image recognition and reconstruction using associative magnetic processing, Int. J. Patt. Recog. Artif. Intell., 6, 1, 157-177 (1992)
[57]	Ingber, L., Generic mesoscopic neural networks based on statistical mechanics of neocortical interactions, Phys. Rev. A, 45, 4, R2183-R2186 (1992)
[58]	Bohr, H.; Brunak, S., A travelling salesman approach to protein conformation, Complex Sys., 3, 9-28 (1989) · Zbl 0724.92008
[59]	Bouzida, D.; Kumar, S.; Swendsen, R. H., A simulated annealing approach for probing biomolecular structures, (Proceedings of the \(26^{th}\) Hawaii International Conference on Systems Sciences (HICSS) (1993), Carnegie Mellon University: Carnegie Mellon University Pittsburgh, PA), (to appear)
[60]	Dowe, D. L.; Oliver, J.; Dix, T. I.; Allison, L.; Wallace, C. S., A decision graph explanation of protein secondary structure prediction, (Proceedings of \(26^{th}\) Hawaii International Conference on Systems Sciences (HICSS) (1993), Carnegie Mellon University: Carnegie Mellon University Pittsburgh, PA), (to appear)
[61]	Lukashin, A. V.; Engelbrecht, J.; Brunak, S., Multiple alignment using simulated annealing: Branch point definition in human mRNA splicing, Nucleic Acids Res., 20, 10, 2511-2516 (1992)
[62]	Goradia, T. M.; Lange, J., Applications of coding theory to the design of somatic cell hybrid panels, Math. Biosci., 91, 201-219 (1988) · Zbl 0654.92005
[63]	Palmer, D. E.; Pattaroni, C.; Nunami, K.; Chadha, R. K.; Goodman, M.; Wakamiya, T.; Fukase, K.; Horimoto, S.; Kitazawa, M.; Fujita, H.; Kubo, A.; Shiba, T., Effects of dehydroalanine on peptide conformations, J. Am. Chem. Soc., 114, 14, 5634-5642 (1992)
[64]	Ingber, L., Statistical mechanics of neocortical interactions: A scaling paradigm applied to electroencephalography, Phys. Rev. A, 44, 6, 4017-4060 (1991)
[65]	Haneishi, H.; Masuda, T.; Ohyama, N.; Honda, T.; Tsujiuchi, J., Analysis of the cost function used in simulated annealing for CT image reconstruction, Appl. Optics, 29, 2, 259-265 (1990)
[66]	Marinari, E.; Parisi, G., Simulated tempering: A new Monte Carlo scheme, Europhys. Lett. (1992), (submitted)
[67]	Schulman, L. S., Techniques and Applications of Path Integration (1981), J. Wiley & Sons: J. Wiley & Sons New York · Zbl 0587.28010
[68]	Beck, T. L.; Doll, J. D.; Freeman, D. L., Locating stationary paths in functional integrals: An optimization method utilizing the stationary phase Monte Carlo sampling function, J. Chem. Phys., 90, 6, 3181-3191 (1989)
[69]	Rothman, D. H., Nonlinear inversion, statistical mechanics, and residual statics estimation, Geophys., 50, 2784-2796 (1985)
[70]	Vasudevan, K.; Wilson, W. G.; Laidlaw, W. G., Simulated annealing statics computation using an order-based energy function, Geophys., 56, 1831-1839 (1991)
[71]	Sen, M. K.; Stoffa, P. L., Nonlinear one-dimensional seismic waveform inversion using simulated annealing, Geophys., 56, 1624-1638 (1991)
[72]	Marshall, J. F.; Bansal, V. K., Financial Engineering: A Complete Guide to Financial Innovation (1992), New York Institute of Finance: New York Institute of Finance New York, NY
[73]	Ingber, L., Statistical mechanical aids to calculating term structure models, Phys. Rev. A, 42, 12, 7057-7064 (1990)
[74]	Ingber, L.; Wehner, M. F.; Jabbour, G. M.; Barnhill, T. M., Application of statistical mechanics methodology to term-structure bond-pricing models, Mathl. Comput. Modelling, 15, 11, 77-98 (1991) · Zbl 0754.60124
[75]	Goffe, W. L.; Ferrier, G. D.; Rogers, J., Global optimization of statistical functions with simulated annealing, J. Econometrics (1993), (to appear)
[76]	Goffe, W. L.; Ferrier, G. D.; Rogers, J., Simulated annealing (1992), AT&T Bell Labs: AT&T Bell Labs Murray Hill, NJ, ftp research.att.com:/netlib/opt/simann.f.Z · Zbl 0850.62871
[77]	Bohachevsky, I. O.; Johnson, M. E.; Stein, M. L., Optimal deployment of missile interceptors, Am. J. Math. Management Sci., 8, 3/4, 361-387 (1988)
[78]	Bohachevsky, I. O.; Johnson, M. E.; Stein, M. L., Generalized simulated annealing for function optimization, Technometrics, 28, 3, 209-217 (1986) · Zbl 0609.65045
[79]	Kuperman, W. A.; Collins, M. D.; Perkins, J. S.; Davis, N. R., Optimal time-domain beamforming with simulated annealing including application of a priori information, J. Acoust. Soc. Am., 88, 4, 1802-1810 (1990)
[80]	Ingber, L.; Fujio, H.; Wehner, M. F., Mathematical comparison of combat computer models to exercise data, Mathl. Comput. Modelling, 15, 1, 65-90 (1991)
[81]	Greene, J. A.; Supowit, K. J., Simulated annealing without rejected moves, IEEE Trans. Comput-Aided Design, CAD-5, 1, 221-228 (1986)
[82]	Hastings, W. K., Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 1, 97-109 (1970) · Zbl 0219.65008
[83]	Basu, A.; Frazer, N., Rapid determination of the critical temperature in simulated annealing inversion, Science, 249, 1409-1412 (1990) · Zbl 1226.86005
[85]	Rammal, R.; Toulouse, G.; Virasoro, M. A., Ultrametricity for physicists, Rev. Mod. Phys., 58, 3, 765-788 (1986)
[86]	Duane, S.; Kennedy, A. D.; Pendelton, B. J.; Roweth, D., Hybrid Monte Carlo, Phys. Lett. B, 195, 216-222 (1987)
[87]	Neal, R. M., Bayesian training of backpropagation networks by the hybrid Monte Carlo Method, (Report CRG-TR-92-1 (1992), University of Toronto: University of Toronto Toronto, Canada)
[88]	Langouche, F.; Roekaerts, D.; Tirapegui, E., Functional Integration and Semiclassical Expansions (1982), Reidel: Reidel Dordrecht, The Netherlands · Zbl 0505.28009
[89]	Hoffmann, K. H.; Würtz, D.; de Groot, C.; Hanf, M., Concepts in optimizing simulated annealing schedules: an adaptive approach for parallel and vector machines, (Grauer, M.; Pressmar, D. B., Lecture Notes in Economics and Mathematical Systems, Vol. 367 (1991), Springer-Verlag: Springer-Verlag Heidelberg), 154-174 · Zbl 0825.90721
[91]	Savage, J. E.; Wloka, M. G., Parallelism in graph-partitioning, J. Parallel Distrib. Comput., 13, 257-272 (1991)
[92]	Kimura, K.; Taki, K., Time-homogeneous parallel annealing algorithm, (Report TR-673 (1991), Institute for New Generation Computer Technology: Institute for New Generation Computer Technology Tokyo, Japan)
[93]	Mahfoud, S. W.; Goldberg, D. E., Parallel recombinative simulated annealing: A genetic algorithm, (Illigal Report No. 92002 (1992), University of Illinois: University of Illinois Urbana, IL) · Zbl 0875.68482
[94]	ter Laak, A.; Hertzberger, L. O.; Sloot, P. M.A., Nonconvex continuous optimization experiments on a transputer system, (Allen, A., Transputer Systems—Ongoing Research (1992), IOS Press: IOS Press Amsterdam, Holland), 251-265
[95]	Ferrari, P. A.; Frigessi, A.; Schonmann, R., Convergence of some partially parallel Gibbs sampler with annealing, Ann. Appl. Probab. (1993), (to appear) · Zbl 0771.60050
[96]	Shanno, D. F.; Phua, K. H., Minimization of unconstrained multivariate functions, ACM Trans. Mathl. Software, 2, 87-94 (1976) · Zbl 0319.65042
[97]	Ingber, L.; Sworder, D. D., Statistical mechanics of combat with human factors, Mathl. Comput. Modelling, 15, 11, 99-127 (1991) · Zbl 0754.60125
[98]	Wofsey, M., Technology: Shortcut tests validity of complicated formulas, The Wall Street Journal, CCXXII, 60, B1 (1993)