Previous: AIDA-99-02 Next: AIDA-99-04 Index 1999

Intellectics Group: Technical Report 99-03

Iterated Local Search for the Quadratic Assignment Problem

Thomas Stützle

Iterated local search (ILS) is a surprisingly simple but at the same time powerful metaheuristic for finding high quality approximate solutions for combinatorial optimization problems. ILS is based on the repeated application of a local search algorithm to initial solution which are obtained by mutations of previously found local optima - in most ILS algorithms these mutations are applied to the best found solution since the start of the search.

In this article we present and analyze the application of ILS to the quadratic assignment problem (QAP). We first justify the usefulness of an ILS approach to this problem by an analysis of the QAP search space. An investigation of the run-time behavior of the ILS algorithm reveals a stagnation behavior of the algorithm - it may get stuck for many iterations in local optima. To avoid such stagnation situations we propose enhancements of the ILS algorithm based on extended acceptance criteria as well as population-based extensions. A final experimental evaluation of the ILS algorithm and the proposed extensions shows an excellent performance when compared to other state-of-the art heuristic methods for the QAP.

Full Paper: Gzipped postscript BibTeX entry