A probabilistic analysis of local search

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

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 proceeding › Chapter › Scientific › peer-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 language	English
Title of host publication	Meta-heuristics : theory and applications
Publisher	Kluwer Academic Publishers
Pages	605-618
Number of pages	14
ISBN (Print)	0-7923-9700-2
Publication status	Published - 1996
Externally published	Yes

Cite this

@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",

}

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 -

A probabilistic analysis of local search

Abstract

Fingerprint

Cite this