zbMATH — the first resource for mathematics

Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. (English) Zbl 0707.65039
Simulated annealing (SA) has become since its invention by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Science 220, No.4598, 671-680 (1983; MR 85f.90091)] a popular tool for a wide class of combinatorial optimization problems. This method needs to perform computation of probabilities or to make random decisions at the “new configuration choice steps.
The authors propose a threshold accepting (TA) method which is formally similar to SA, but the rules of acceptance are different. TA accepts every new configuration which is much worse than the old one.
It is demonstrated by solving the traveling salesman problems and the problems of generation of error-correction codes that TA is superior to SA. Even the deterministic TA versions yield very good results in practice.
Reviewer: A.Roose

65K05 Numerical mathematical programming methods
90C27 Combinatorial optimization
90C15 Stochastic programming
Full Text: DOI
[1] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Science, 220, 671, (1983)
[2] Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., J. chem. phys., 21, 1087, (1953)
[3] \scM. Grötschel, Preprint No. 38, Universität Augsburg (unpublished).
[4] Rossier, Y.; Troyon, M.; Liebling, Th.M., OR spektrum, 8, 151, (1986)
[5] Mühlenbein, H.; Gorges-Schleuter, M.; Krämer, O., Parallel comput., 7, 65, (1988)
[6] Holland, O.A., (), (unpublished)
[7] Padberg, M.; Rinaldi, G., Oper. res. lett., 6, 1, (1987)
[8] El Gamal, A.A.; Hemachandra, L.A.; Shperling, I.; Wei, V.K., IEEE trans. inform. theory, IT-33, 116, (1987)
[9] Lin, S., Bell syst. tech. J., 44, 2245, (1965)
[10] \scH. Mühlenbein, preprint (1988).
[11] Conway, J.H.; Sloane, N.J.A., IEEE trans. inform. theory, IT-32, 337, (1987)
[12] Lin, S.; Kernighan, B., Oper. res., 21, 498, (1973)
[13] \scI. Althöfer and K.-U. Koschnick, SIAM J. Control Optim. submitted.
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.