A probabilistic analysis of local search

H.M.M. Eikelder ten, M.G.A. Verhoeven, T.W.M. Vossen, E.H.L. Aarts

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

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.
Original languageEnglish
Title of host publicationMeta-heuristics : theory and applications
PublisherKluwer Academic Publishers
Pages605-618
Number of pages14
ISBN (Print)0-7923-9700-2
Publication statusPublished - 1996
Externally publishedYes

Fingerprint

Probabilistic Analysis
Local Search
Average-case Analysis
Empirical Analysis
Travelling salesman problems
Theoretical Analysis
Model

Cite this

Eikelder ten, H. M. M., Verhoeven, M. G. A., Vossen, T. W. M., & Aarts, E. H. L. (1996). A probabilistic analysis of local search. In Meta-heuristics : theory and applications (pp. 605-618). Kluwer Academic Publishers.
Eikelder ten, H.M.M. ; Verhoeven, M.G.A. ; Vossen, T.W.M. ; Aarts, E.H.L. / A probabilistic analysis of local search. Meta-heuristics : theory and applications. Kluwer Academic Publishers, 1996. pp. 605-618
@inbook{2cbd3bed62944df883e2b0444e3413ec,
title = "A probabilistic analysis of local search",
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.",
author = "{Eikelder ten}, H.M.M. and M.G.A. Verhoeven and T.W.M. Vossen and E.H.L. Aarts",
year = "1996",
language = "English",
isbn = "0-7923-9700-2",
pages = "605--618",
booktitle = "Meta-heuristics : theory and applications",
publisher = "Kluwer Academic Publishers",
address = "Netherlands",

}

Eikelder ten, HMM, Verhoeven, MGA, Vossen, TWM & Aarts, EHL 1996, A probabilistic analysis of local search. in Meta-heuristics : theory and applications. Kluwer Academic Publishers, pp. 605-618.

A probabilistic analysis of local search. / Eikelder ten, H.M.M.; Verhoeven, M.G.A.; Vossen, T.W.M.; Aarts, E.H.L.

Meta-heuristics : theory and applications. Kluwer Academic Publishers, 1996. p. 605-618.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

TY - CHAP

T1 - A probabilistic analysis of local search

AU - Eikelder ten, H.M.M.

AU - Verhoeven, M.G.A.

AU - Vossen, T.W.M.

AU - Aarts, E.H.L.

PY - 1996

Y1 - 1996

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

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

M3 - Chapter

SN - 0-7923-9700-2

SP - 605

EP - 618

BT - Meta-heuristics : theory and applications

PB - Kluwer Academic Publishers

ER -

Eikelder ten HMM, Verhoeven MGA, Vossen TWM, Aarts EHL. A probabilistic analysis of local search. In Meta-heuristics : theory and applications. Kluwer Academic Publishers. 1996. p. 605-618