2006 | OriginalPaper | Chapter
Incremental Local Search in Ant Colony Optimization: Why It Fails for the Quadratic Assignment Problem
Authors : Prasanna Balaprakash, Mauro Birattari, Thomas Stützle, Marco Dorigo
Published in: Ant Colony Optimization and Swarm Intelligence
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Ant colony optimization algorithms are currently among the best performing algorithms for the quadratic assignment problem. These algorithms contain two main search procedures: solution construction by artificial ants and local search to improve the solutions constructed by the ants. Incremental local search is an approach that consists in re-optimizing partial solutions by a local search algorithm at regular intervals while constructing a complete solution. In this paper, we investigate the impact of adopting incremental local search in ant colony optimization to solve the quadratic assignment problem. Notwithstanding the promising results of incremental local search reported in the literature in a different context, the computational results of our new ACO algorithm are rather negative. We provide an empirical analysis that explains this failure.