求解二次分配问题的改进禁忌搜索算法

An Improved Tabu Search Algorithm for the Quadratic Assignment Problem

针对二次分配问题,提出了一种改进禁忌搜索算法ITS。ITS基于"集中和分散"策略,由局部搜索和精英重组两个步骤经过多次迭代完成。局部搜索采用RTS(Robust Tabu Search)。在精英重组步骤,对局部优化解中的优良个体采用MPX交叉操作,得到新的可行解。在QAPLIB典型实例上的实验结果表明,与RTS相比,改进后的禁忌搜索算法具有更优的性能。

An improved tabu search algorithm （ITS） for the quadratic assignment problem （QAP） is proposed. ITS is based on ＂intensification and diversification＂ methodology. An efficient local search and subsequent reconstruction of elite solutions is applied in an iterated way. The local search procedure uses robust tabu search （RTS）. In the reconstruction procedure, MPX crossover operator is applied to the good locally optimal solutions to produce new feasible solution. Comparisons of ITS and RTS are performed on the publicly available QAP instances from QAPLIB. The result demonstrates that ITS significantly outperforms RTS for QAP problem.