Engineering stochastic local search algorithms: A case study in estimation-based local search for the probabilistic travelling salesman problem

Prasanna Balaprakash, Mauro Birattari, Thomas Stützle

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

2 Scopus citations

Abstract

In this article, we describe the steps that have been followed in the development of a high performing stochastic local search algorithm for the probabilistic travelling salesman problem, a paradigmatic combinatorial stochastic optimization problem. In fact, we have followed a bottom-up algorithm engineering process that starts from basic algorithms (here, iterative improvement) and adds complexity step-by-step. An extensive experimental campaign has given insight into the advantages and disadvantages of the prototype algorithms obtained at the various steps and directed the further algorithm development. The final stochastic local search algorithm was shown to substantially outperform the previous best algorithms known for this problem. Besides the systematic engineering process for the development of stochastic local search algorithms followed here, the main reason for the high performance of our final algorithm is the innovative adoption of techniques for the estimation of the cost of neighboring solutions using delta evaluation.

Original languageEnglish
Title of host publicationRecent Advances in Evolutionary Computation for Combinatorial Optimization
EditorsCarlos Cotta, Jano Hemert
Pages53-66
Number of pages14
DOIs
StatePublished - 2008
Externally publishedYes

Publication series

NameStudies in Computational Intelligence
Volume153
ISSN (Print)1860-949X

Keywords

  • Algorithm engineering
  • Estimation-based local search
  • Probabilistic travelling salesman problem
  • Stochastic local search
  • Stochastic optimization problems

Fingerprint

Dive into the research topics of 'Engineering stochastic local search algorithms: A case study in estimation-based local search for the probabilistic travelling salesman problem'. Together they form a unique fingerprint.

Cite this