N-city traveling salesman problem: Optimization by simulated annealings
Journal of Statistical PhysicsPublished 1 December 1986
R. E. Randelman, Gary S. Grest
Citations30
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.
TL;DR
It is shown that the length of tour depends logarithmically on the cooling rateQ in a simulated Monte Carlo anneal, and it is speculated that this is a general property of all Np-complete problems.
Abstract
The problem of finding the shortest closed path connectingN randomly chosen points is one of the classicNp-complete problems. We show that the length of tour depends logarithmically on the cooling rateQ in a simulated Monte Carlo anneal. We speculate that this is a general property of allNp-complete problems.
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
Journal of Statistical PhysicsOptimization by simulated annealing: Quantitative studies
1,809 Citations1984Scott Kirkpatrick
Experimental studies of the simulated annealing method are presented and its computational efficiency when applied to graph partitioning and traveling salesman problems are presented.
Journal of Computational PhysicsA Monte carlo simulated annealing approach to optimization over continuous variables
433 Citations1984David Vanderbilt, Steven G. Louie
Numerical optimization methods based on thermodynamic concepts are extended to the case of continuous multidimensional parameter spaces, and a self-regulatory mechanism for choosing the random step distribution is described.
SIAM ReviewThe <i>N</i>-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
251 Citations1984Ernesto Bonomi, Jean‐Luc Lutton
The Metropolis algorithm is used to generate a sequence of tours that may be viewed as the random evolution of a physical system in contact with a heat-bath, and it appears that for large N one arrives within a few percent of the optimal solution in better than quadratic time.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsGlobal Wiring by Simulated Annealing
239 Citations1983M.P. Vecchi, Scott Kirkpatrick
Simulated annealing, a new general-purpose method of multivariate optimization, is applied to global wire routing for both idealized (synthetic) and actual designs of realistic size and complexity.
NatureOptimization strategies gleaned from biological evolution
186 Citations1985R. M. Brady
Computer algorithms are used to investigate new strategies for the 64-city travelling salesman problem, which combine conventional optimization or ‘quenching’ with biological elements, namely having a population of trial solutions, helping weaker individuals to survive, and an analogue of sexual crossing-over of genes.
Mathematical programming studiesOn the symmetric travelling salesman problem: A computational study
153 Citations1980Manfred Padberg, Saman Hong
The empirical results lend convincing support to the hypothesis that inequalities defining facets of the convex hull of tours are of substantial computational value in the solution of this difficult combinatorial problem.
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.
Physical Review LettersResidual Energies after Slow Cooling of Disordered Systems
100 Citations1986David A. Huse, Daniel S. Fisher
Etude pour des systemes desordonnes, dont des verres de spins, Proposition d'un comportement general pour de tels systemes frustres.
Journal of the Optical Society of America AImage reconstruction from coded data: I Reconstruction algorithms and experimental results
47 Citations1985Warren E. Smith, Richard G. Paxman +1 more
It is found that reconstructing from multiplexed data is not so serious a problem as reconstructioning from data obtained with a limited viewing angle and that the fidelity of a reconstruction depends much more strongly on the design of the data-taking system (the coded apertures) than on the reconstruction algorithm.