2008 | OriginalPaper | Chapter
Engineering Stochastic Local Search Algorithms: A Case Study in Estimation-Based Local Search for the Probabilistic Travelling Salesman Problem
Authors : Prasanna Balaprakash, Mauro Birattari, Thomas Stützle
Published in: Recent Advances in Evolutionary Computation for Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.