A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem

E.H.L. Aarts, J.H.M. Korst, P.J.M. Laarhoven van

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)187-206
Number of pages20
JournalJournal of Statistical Physics
Volume50
Issue number1-2
DOIs
Publication statusPublished - 1988
Externally publishedYes

Cite this

@article{a4b674b99f74449aabecc3a20903b131,
title = "A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem",
abstract = "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.",
author = "E.H.L. Aarts and J.H.M. Korst and {Laarhoven van}, P.J.M.",
year = "1988",
doi = "10.1007/BF01022991",
language = "English",
volume = "50",
pages = "187--206",
journal = "Journal of Statistical Physics",
issn = "0022-4715",
publisher = "Springer New York",
number = "1-2",

}

A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem. / Aarts, E.H.L.; Korst, J.H.M.; Laarhoven van, P.J.M.

In: Journal of Statistical Physics, Vol. 50, No. 1-2, 1988, p. 187-206.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem

AU - Aarts, E.H.L.

AU - Korst, J.H.M.

AU - Laarhoven van, P.J.M.

PY - 1988

Y1 - 1988

N2 - 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.

AB - 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.

U2 - 10.1007/BF01022991

DO - 10.1007/BF01022991

M3 - Article

VL - 50

SP - 187

EP - 206

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 1-2

ER -