Iterated local search for the quadratic assignment problem
Iterated local search for the quadratic assignment problem
复制标题
DOI：
10.1016/j.ejor.2005.01.066
复制
发表时间：
2006-11
期刊：
影响因子：
--
通讯作者：
T. Stützle
中科院分区：
文献类型：
--
作者：
T. Stützle
迭代局部搜索（ILS）是一种简单而有效的随机局部搜索方法。本文提出并分析了ILS在二次分配问题（QAP）中的应用。我们证明了潜在的有用性ILS的方法来解决这个问题的QAP搜索空间的分析。然而，一个基本的ILS算法的运行时行为的分析揭示了一个停滞的行为，强烈地损害其性能。为了避免这种停滞的行为，我们加强ILS算法使用验收标准，允许移动到更差的局部最优，我们提出了基于人口的ILS扩展。增强ILS算法的实验评估表明，其优异的性能相比，其他国家的最先进的算法的QAP。
Iterated local search (ILS) is a simple and powerful stochastic local search method. This article presents and analyzes the application of ILS to the quadratic assignment problem (QAP). We justify the potential usefulness of an ILS approach to this problem by an analysis of the QAP search space. However, an analysis of the run-time behavior of a basic ILS algorithm reveals a stagnation behavior which strongly compromises its performance. To avoid this stagnation behavior, we enhance the ILS algorithm using acceptance criteria that allow moves to worse local optima and we propose population-based ILS extensions. An experimental evaluation of the enhanced ILS algorithms shows their excellent performance when compared to other state-of-the-art algorithms for the QAP.