Paper #513

Título:

Iterated local search

Autores:

Helena Ramalhinho-Lourenço, Olivier C. Martin y Thomas Stützle

Data:

Noviembre 2000

Resumen:

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.

Palabras clave:

Metaheuristics, local search, combinatorial optimization

Códigos JEL:

C61, C63, D83

Área de investigación:

Gestión de la Producción y de las Operaciones

Publicado en:

Handbook of Metaheuristics, F. Glover and G. Kochenberger, (eds.), Kluwer Academic Publishers, International Series in Operations Research & Management Science, pp. 321-353 (2002)

Descargar el paper en formato PDF