Engineering Stochastic Local Search Algorithms: A Case Study in Estimation-Based Local Search for the Probabilistic Travelling Salesman Problem Export

@incollection{citeulike:4313313, 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.}, author = {Balaprakash, Prasanna and Birattari, Mauro and St\"{u}tzle, Thomas}, citeulike-article-id = {4313313}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-70807-0_4}, citeulike-linkout-1 = {http://www.springerlink.com/content/1138240075624001}, doi = {10.1007/978-3-540-70807-0_4}, journal = {Recent Advances in Evolutionary Computation for Combinatorial Optimization}, keywords = {algorithm-engineering, comparison, neighborhood, parameter-setting, performance-assessment, stochastic, stochastic-local-search, travelling-salesman-problem}, pages = {53--66}, posted-at = {2009-04-15 14:21:29}, priority = {5}, title = {Engineering Stochastic Local Search Algorithms: A Case Study in Estimation-Based Local Search for the Probabilistic Travelling Salesman Problem}, url = {http://dx.doi.org/10.1007/978-3-540-70807-0_4}, year = {2008} }

TY - CHAP ID - citeulike:4313313 L3 - citeulike-article-id:4313313 N2 - 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. JF - Recent Advances in Evolutionary Computation for Combinatorial Optimization EP - 66 TI - Engineering Stochastic Local Search Algorithms: A Case Study in Estimation-Based Local Search for the Probabilistic Travelling Salesman Problem SP - 53 KW - algorithm-engineering KW - comparison KW - neighborhood KW - parameter-setting KW - performance-assessment KW - stochastic KW - stochastic-local-search KW - travelling-salesman-problem AU - Balaprakash, Prasanna AU - Birattari, Mauro AU - Stützle, Thomas PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-70807-0_4 ER -