zbMATH — the first resource for mathematics

Engineering stochastic local search algorithms: A case study in estimation-based local search for the probabilistic travelling salesman problem. (English) Zbl 1159.90467
Cotta, Carlos (ed.) et al., Recent advances in evolutionary computation for combinatorial optimization. Most papers are extended versions of selected papers from the 7th conference on evolutionary computation and metaheuristics in combinatorial optimization (EvoCOP’2007), Valencia, Spain, April 11–13, 2007. Berlin: Springer (ISBN 978-3-540-70806-3/hbk). Studies in Computational Intelligence 153, 53-66 (2008).
Summary: 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.
For the entire collection see [Zbl 1146.90002].

90C15 Stochastic programming
90C35 Programming involving graphs or networks
Full Text: DOI