Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing (Q919753): Difference between revisions

Simulated annealing (SA) has become since its invention by \textit{S. Kirkpatrick}, \textit{C. D. Gelatt} and \textit{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.