Iterated Local Search

By Helena Ramalhinho Lourenço, Olivier C. Martin, Thomas Stützle. Handbook of Metaheuristics, 2001

1,715 citations recorded by the source corpus.

Iterated Local Search has many of the desirable features of a metaheuristic: it is simple, easy to implement, robust, and highly effective. The essential idea of Iterated Local Search lies in focusing the search not on the full space of solutions but on a smaller subspace defined by the solutions that are locally optimal for a given optimization engine. The success of Iterated Local Search lies in the biased sampling of this set of local optima. How effective this approach turns out to be depends mainly on the choice of the local search, the perturbations, and the acceptance criterion. So far, in spite of its conceptual simplicity, it has lead to a number of state-of-the-art results without the use of too much problem- specific knowledge. But with further work so that the different modules are well adapted to the problem at hand, Iterated Local Search can often become a competitive or even state of the art algorithm. The purpose of this review is both to give a detailed description of this metaheuristic and to show where it stands in terms of performance.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/c7caeb614cba94577949ce96d695621f1a3c03e0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Industrial and Manufacturing Engineering

Citations in the corpus

A joint quantile and expected shortfall regression framework (2017, positive): “More specifically, we use the Iterated Local Search (ILS) meta-heuristic of Lourenço et al. (2003), which successively refines the parameter estimates by repeated optimizations with iteratively perturbed starting values.”
Greedy Randomized Adaptive Search Procedures. (2003, background): “[110] point out that ILS has been rediscovered many times and is also known as iterated descent [35, 36], large step Markov chains [118], iterated Lin-Kernighan [98], and chained local optimization [117].”
Heuristic Optimization Methods in Econometrics (2009, background): “…this point is not accepted (left panel) we return to xc (not xi) and continue (right panel). xc F (xc) xi xn xc F (xc) xi xn xi xn Iterated local search (Lourenço et al., 2002) and variable neighborhood search (VNS) (Mladenovic and Hansen, 1997) also fall into this class of hybrid meta-heuristics.”
Beam-ACO - hybridizing ant colony optimization with beam search: an application to open shop scheduling (2005, background): “Examples are tabu search (TS) [7], simulated annealing (SA) [8], and iterated local search (ILS) [9].”
Automated Algorithm Configuration and Parameter Tuning (2012, methodology): “…algorithm configuration (Hutter et al, 2007b, 2009a) lies Iterated Local Search (ILS), a well-known and versatile stochastic local search method that has been applied with great success to a wide range of difficult combinatorial problems (see, e.g., Lourenço et al, 2002; Hoos and Stützle, 2004).”
An improved grey wolf optimizer for solving engineering problems (2021, methodology): “Although a few algorithms have been developed in the first category such as the tabu search (TS) (Glover, 1989, 1990), iterated local search (ILS) (Lourenço et al., 2003), and adaptive dimensional search (ADS) (Hasançebi et al., 2015), many metaheuristic algorithms have been inspired by nature.”
Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm (2008, methodology): “IG is closely related to another technique, iterated local search (ILS), in which the algorithm iterates over a local search neighbourhood (e.g. Lourenço et al. 2002).”
ParamILS: An Automatic Algorithm Configuration Framework (2014, methodology): “A more sophisticated approach is to employ iterated local search (ILS) (Lourenço et al., 2002) to search for performance-optimizing parameter configurations.”
A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem (2007, methodology): “The criterion that is most commonly studied in the literature is the minimization of the total completion time, also called makespan (Cmax), of the production sequence.”
A hybrid heuristic algorithm for the open-pit-mining operational planning problem (2010, methodology): “(Mladenovic and Hansen, 1997) and Iterated Local Search - ILS (Lourenço et al., 2003).”
An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times (2014, methodology): “For a comprehensive description of the ILS approach we refer to Lourenço, Martin, and Stützle (2003) who provide the characteristics of the algorithmic framework and discuss implementation details.”
Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (2024, background): “…and practitioners, leading to simulated annealing (Van Laarhoven et al., 1987), tabu search (Glover & Laguna, 1998), and iterated local search (Lourenc¸o et al., 2003), among many other noticeable methods (Mart et al., 1 Department of Computer Science, City University of Hong Kong, Hong Kong…”
Boosting Verification by Automatic Tuning of Decision Procedures (2007, background): “cal Search (ILS)[20], [21], which provides the basis for PARAM ILS.”