zbMATH — the first resource for mathematics

A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem. (English) Zbl 1084.90014
Summary: A quantitative study is presented of the typical behavior of the simulated annealing algorithm based on a cooling schedule presented previously by the authors. The study is based on the analysis of numerical results obtained by systematically applying the algorithm to a 100-city traveling salesman problem. The expectation and the variance of the cost are analyzed as a function of the control parameter of the cooling schedule. A semiempirical average-case performance analysis is presented from which estimates are obtained on the expectation of the average final result obtained by the simulated annealing algorithm as a function of the distance parameter, which determines the decrement of the control parameter.

90B10 Deterministic network models in operations research
82-08 Computational methods (statistical mechanics) (MSC2010)
82D99 Applications of statistical mechanics to specific types of physical systems
90C27 Combinatorial optimization
Full Text: DOI
[1] E. H. L. Aarts and P. J. M. van Laarhoven,Philips J. Res. 40:193-226 (1985).
[2] E. H. L. Aarts and P. J. M. van Laarhoven, inProceedings International Conference on Computer-Aided Design (Santa Clara, November 1985), pp. 206-208.
[3] K. Binder,Monte Carlo Methods in Statistical Physics (Springer-Verlag, Berlin, 1986). · Zbl 0593.65003
[4] V. ?erny,J. Optim. Theory Appl. 45:41-51 (1985). · Zbl 0534.90091
[5] G. S. Grest, C. M. Soukoulis, and K. Levin,Phys. Rev. Lett. 56:1148-1151 (1986).
[6] B. Hajek, inProceedings 24th Conference on Decision and Control (Ft. Lauderdale, December 1985), pp. 755-760.
[7] R. Jonker and T. Volgenant,Oper. Res. 32:837-846 (1984). · Zbl 0546.90095
[8] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi,Science 220:671-680 (1983). · Zbl 1225.90162
[9] S. Kirkpatrick and G. Toulouse,J. Phys. (Paris) 46:1277-1292 (1985).
[10] P. J. M. van Laarhoven and E. H. L. Aarts,Simulated Annealing: Theory and Applications (Kluwer, Dordrecht, 1987). · Zbl 0643.65028
[11] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys,The Traveling Salesman Problem (Wiley, Chichester, 1985). · Zbl 0563.90075
[12] S. Lin and B. W. Kernighan,Oper. Res. 21:498-516 (1973). · Zbl 0256.90038
[13] M. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller,J. Chem. Phys. 21:1087-1092 (1953).
[14] E. Palmer,Graphical Evolution (Wiley Interscience, New York, 1985). · Zbl 0566.05002
[15] F. Romeo and A. L. Sangiovanni-Vincentelli, inProceedings 1985 Chapel Hill Conference on VLSI (May 1985), pp. 393-417.
[16] G. H. Sasaki and B. Hajek,J. ACM, to appear.
[17] S. Solla, G. Sorkin, and S. White, inDisordered Systems and Biological Organization (Springer-Verlag, Berlin, 1985).
[18] S. R. White, inProceedings International Conference Computer Design (Port Chester, November 1984), pp. 646-651.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.