A Probabilistic Analysis of Local Search
MetaheuristicsPublished 1 January 1996
ten Hmm Huub Eikelder, Mga Marco Verhoeven, Twm Thomas Vossen, Ehl Emile Aarts
Citations21
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
A model which allows us to compute the required number of steps and the distribution of final solutions found by a best improvement algorithm is given and is empirically validated for a restricted version of the 2-opt neighborhood.
Abstract
We present a theoretical average-case analysis of a 2-opt algorithm for the traveling salesman problem. First, we give a model which allows us to compute the required number of steps and the distribution of final solutions found by a best improvement algorithm. This model is empirically validated for a restricted version of the 2-opt neighborhood. Secondly, we present a semi-empirical analysis of the average-case performance of an iterated 2-opt and Lin-Kernighan algorithm based on empirically obtained parameters.
Keywords
Computer ScienceEngineering
Journal of the American Statistical AssociationProbability, Random Variables, and Stochastic Processes.
16,350 Citations1984Julia Abrahams, A. Papoulis
Princeton University Press eBooksLocal Search in Combinatorial Optimization
2,059 Citations2003Emile Aarts, Jan Karel Lenstra
Operations ResearchA Method for Solving Traveling-Salesman Problems
1,532 Citations1958G. A. Croes
A method of solution for the traveling-salesman problem that is applicable to both symmetric and asymmetric problems with random elements, and does not use subjective decisions, so that it can be completely mechanized.
Journal of Computer and System SciencesHow easy is local search?
714 Citations1988David S. Johnson, Christos H. Papadimitriou +1 more
A natural class PLS is defined consisting essentially of those local search problems for which local optimality can be verified in polynomial time, and it is shown that there are complete problems for this class.
Lecture notes in computer scienceLocal optimization and the Traveling Salesman Problem
376 Citations2005David S. Johnson
This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.
Operations Research LettersA new adaptive multi-start technique for combinatorial global optimizations
351 Citations1994Kenneth D. Boese, Andrew B. Kahng +1 more
This work motivates a new adaptive multi-start paradigm for heuristic global optimization, wherein starting points for greedy descent are adaptively derived from the best previously found local minima.
Large-step Markov chains for the Traveling Salesman Problem
322 Citations2018Olivier Martin
A new class of Markov chain Monte Carlo search procedures are introduced, leading to more powerful optimizat~on methods than simulated annealing, and a new best heuristic is introduced.
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.
Physical Review ALocal properties of Kauffman’s<i>N</i>-<i>k</i>model: A tunably rugged energy landscape
215 Citations1991Edward D. Weinberger
Physics Letters AThe landscape of the traveling salesman problem
131 Citations1992Peter F. Stadler, Wolfgang Schnabl
The landscape of traveling salesman problems is investigated by random walk techniques and the autocorrelation functions for different metrics on the space of tours are calculated and turns out to be AR(1) for symmetric TSPs.
TechnometricsKendall's Advanced Theory of Statistics, Vol. 1: Distribution Theory
113 Citations1989Eric R. Ziegel, Alan D. Stuart +1 more
SIAM Journal on Algebraic and Discrete MethodsHill Climbing with Multiple Local Optima
63 Citations1985Craig A. Tovey
The behavior of local improvement algorithms applied to combinatorial optimization problems with multiple local optima is investigated, and it is shown that the expected number of iterations is linear for a wide range of randomness assumptions, and that the number of localoptima tends to be exponentially large.
Symposium on Discrete AlgorithmsNew results on the old k-opt algorithm for the TSP
29 Citations1994Barun Chandra, Howard Karloff +1 more
Several results some worst case and some probabilistic on the performance of and k opt local search for the TSP with respect to both the quality of the solution and the speed with which it is obtained are developed.
TechnometricsKendall's Advanced Theory of Statistics, Vol. 1: Distribution Theory
27 Citations1989Eric R. Ziegel
Mathematical ProgrammingA probabilistic analysis of the switching algorithm for the euclidean TSP
26 Citations1989Walter Kern
The well-known switching algorithm proposed by Lin and Kernighan for the Euclidean Travelling Salesman Problem is derived theoretically and a bound of O(n18) with probability 1 −c/n is come up with, whereas in practice the algorithm works slightly better.