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.
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
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C27 | Combinatorial optimization |
| 90C15 | Stochastic programming |
Keywords:
stochastic optimization; threshold accepting method; Simulated annealing; combinatorial optimization; traveling salesman problems; generation of error-correction codesReferences:
| [1] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Science, 220, 671 (1983) · Zbl 1225.90162 |
| [2] | Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., J. Chem. Phys., 21, 1087 (1953) · Zbl 1431.65006 |
| [4] | Rossier, Y.; Troyon, M.; Liebling, Th. M., OR Spektrum, 8, 151 (1986) · Zbl 0596.90069 |
| [5] | Mühlenbein, H.; Gorges-Schleuter, M.; Krämer, O., Parallel Comput., 7, 65 (1988) · Zbl 0646.65054 |
| [6] | Holland, O. A., (Dissertation (1987), University of Bonn), (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) · Zbl 0136.14705 |
| [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) · Zbl 0256.90038 |
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.
