### Abstract

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 |

### Fingerprint

### Cite this

*Meta-heuristics : theory and applications*(pp. 605-618). Kluwer Academic Publishers.

}

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

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Scientific › peer-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 -