Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics

1. Front Matter

   PDF

2. High-Performance Local Search for Task Scheduling with Human Resource Allocation

   1. High-Performance Local Search for Task Scheduling with Human Resource Allocation

      • Bertrand Estellon, Frédéric Gardi, Karim Nouioua

      Pages 1-15

   2. On the Use of Run Time Distributions to Evaluate and Compare Stochastic Local Search Algorithms

      • Celso C. Ribeiro, Isabel Rosseti, Reinaldo Vallejos

      Pages 16-30

   3. Estimating Bounds on Expected Plateau Size in MAXSAT Problems

      • Andrew M. Sutton, Adele E. Howe, L. Darrell Whitley

      Pages 31-45

   4. A Theoretical Analysis of the k-Satisfiability Search Space

      • Andrew M. Sutton, Adele E. Howe, L. Darrell Whitley

      Pages 46-60

   5. Loopy Substructural Local Search for the Bayesian Optimization Algorithm

      • Claudio F. Lima, Martin Pelikan, Fernando G. Lobo, David E. Goldberg

      Pages 61-75

   6. Running Time Analysis of ACO Systems for Shortest Path Problems

      • Christian Horoba, Dirk Sudholt

      Pages 76-91

   7. Techniques and Tools for Local Search Landscape Visualization and Analysis

      • Franco Mascia, Mauro Brunato

      Pages 92-104

3. Short Papers

   1. High-Performance Local Search for Solving Real-Life Inventory Routing Problems

      • Thierry Benoist, Bertrand Estellon, Frédéric Gardi, Antoine Jeanjean

      Pages 105-109

   2. A Detailed Analysis of Two Metaheuristics for the Team Orienteering Problem

      • Pieter Vansteenwegen, Wouter Souffriau, Dirk Van Oudheusden

      Pages 110-114

   3. On the Explorative Behavior of MAX–MIN Ant System

      • Daniela Favaretto, Elena Moretti, Paola Pellegrini

      Pages 115-119

   4. A Study on Dominance-Based Local Search Approaches for Multiobjective Combinatorial Optimization

      • Arnaud Liefooghe, Salma Mesmoudi, Jérémie Humeau, Laetitia Jourdan, El-Ghazali Talbi

      Pages 120-124

   5. A Memetic Algorithm for the Multidimensional Assignment Problem

      • Gregory Gutin, Daniel Karapetyan

      Pages 125-129

   6. Autonomous Control Approach for Local Search

      • Julien Robet, Frédéric Lardeux, Frédéric Saubion

      Pages 130-134

   7. EasyGenetic: A Template Metaprogramming Framework for Genetic Master-Slave Algorithms

      • Stefano Benedettini, Andrea Roli, Luca Di Gaspero

      Pages 135-139

   8. Adaptive Operator Selection for Iterated Local Search

      • Dirk Thierens

      Pages 140-144

   9. Improved Robustness through Population Variance in Ant Colony Optimization

      • David C. Matthews, Andrew M. Sutton, Doug Hains, L. Darrell Whitley

      Pages 145-149

   10. Mixed-Effects Modeling of Optimisation Algorithm Performance

       • Matteo Gagliolo, Catherine Legrand, Mauro Birattari

       Pages 150-154

4. Back Matter

   PDF

Stochastic local search (SLS) algorithms are established tools for the solution of computationally hard problems arising in computer science, business adm- istration, engineering, biology, and various other disciplines. To a large extent, their success is due to their conceptual simplicity, broad applicability and high performance for many important problems studied in academia and enco- tered in real-world applications. SLS methods include a wide spectrum of te- niques, ranging from constructive search procedures and iterative improvement algorithms to more complex SLS methods, such as ant colony optimization, evolutionary computation, iterated local search, memetic algorithms, simulated annealing, tabu search, and variable neighborhood search. Historically, the development of e?ective SLS algorithms has been guided to a large extent by experience and intuition. In recent years, it has become - creasingly evident that success with SLS algorithms depends not merely on the adoption and e?cient implementation of the most appropriate SLS technique for a given problem, but also on the mastery of a more complex algorithm - gineering process. Challenges in SLS algorithm development arise partly from the complexity of the problems being tackled and in part from the many - grees of freedom researchers and practitioners encounter when developing SLS algorithms. Crucial aspects in the SLS algorithm development comprise al- rithm design, empirical analysis techniques, problem-speci?c background, and background knowledge in several key disciplines and areas, including computer science, operations research, arti?cial intelligence, and statistics.

• Scheduling
• algorithm performance
• algorithms
• ant colony
• autonomous systems
• combinatorial optimization
• complexity
• genetic algorithms
• k-sat
• metaheuristic
• optimization
• search algorithms
• search space
• shortest path
• visualization
• data structures
• algorithm analysis and problem complexity

• IRIDIA, CoDE, Université Libre de Bruxelles, Brussels, Belgium

  Thomas Stützle, Mauro Birattari

• Computer Science Department, University of British Columbia, Vancouver, Canada

  Holger H. Hoos

Policies and ethics