A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem
Journal of Statistical PhysicsPublished 1 January 1988
Emile Aarts, Jan Korst, Peter J. M. van Laarhoven
Citations129
SJR quartileQ2
SJR score0.67
SNIP1.00
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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.
Keywords
Computer ScienceEngineering
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The Journal of Chemical PhysicsEquation of State Calculations by Fast Computing Machines
37,074 Citations1953N. Metropolis, Arianna W. Rosenbluth +3 more
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
Journal of Optimization Theory and ApplicationsThermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
3,357 Citations1985V. Černý
It is conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.
Mathematics and Computers in SimulationSimulated annealing: theory and applications.
3,005 Citations1988
Simulated Annealing: Theory and Applications
2,372 Citations1987Peter J. M. van Laarhoven, Emile Aarts
Performance of the simulated annealing algorithm and the relation with statistical physics and asymptotic convergence results are presented.
The Traveling Salesman Problem
1,622 Citations2019Lawrence Snyder, Zuo‐Jun Max Shen
Lecture notes in economics and mathematical systemsTraveling Salesman Problem
800 Citations1986H. T. Lau
The traveling salesman problem is to start from a node in G, visit every other node exactly once and return back to the starting node in such a way that the total traveled distance is minimum.
Disordered Systems and Biological Organization
315 Citations1986Elie Bienenstock, Françoise Fogelman Soulié +1 more
The present introduction outlInes the relationships between the contributions presented at the NATO workshop on Disordered Systems and Biological Organization and discusses each paper in its particular scientific context.
Journal de physiqueConfiguration space analysis of travelling salesman problems
233 Citations1985Scott Kirkpatrick, G. Toulouse
A random distance TSP as similar as possible to the idealized infinite-ranged model of spin glasses, and evidence for freezing due to frustration and for a hierarchical, ultrametric structure of configuration space is presented.
A tutorial survey of theory and applications of simulated annealing
149 Citations1985Bruce Hajek
The basic theory of simulated annealing is reviewed, its recent applications are surveyed, and the theoretical approaches that have been used to study the technique are surveyed.
Physical Review LettersCooling-Rate Dependence for the Spin-Glass Ground-State Energy: Implications for Optimization by Simulated Annealing
119 Citations1986Gary S. Grest, Costas M. Soukoulis +1 more
The zero-temperature ground-state properties of five spin-glass models have been studied as a function of the cooling rate requivalent-..delta..T/t to speculate that this difference is related to the fact that the 2D models are not NP-complete while the other three models are.
Operations ResearchNonoptimal Edges for the Symmetric Traveling Salesman Problem
38 Citations1984Roy Jonker, Ton Volgenant
For the symmetric traveling salesman problem, a set of undirected edges that can be eliminated while still retaining at least one optimal solution of the problem are identified.