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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Hoofdstuk › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Titel	Meta-heuristics : theory and applications
Redacteuren	I.H. Osman, J.P. Kelly
Uitgeverij	Kluwer Academic Publishers
Pagina's	605-618
ISBN van geprinte versie	0-7923-9700-2
Status	Gepubliceerd - 1996

Citeer dit

@inbook{f62ebb3c8b4943ba8dc47376d30397d8,

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

editor = "I.H. Osman and J.P. Kelly",

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

A2 - Osman, I.H.

A2 - Kelly, J.P.

PB - Kluwer Academic Publishers

ER -

A probabilistic analysis of local search

Samenvatting

Vingerafdruk

Citeer dit