Ant colonies for the quadratic assignment problem
Ant colonies for the quadratic assignment problem
复制标题
DOI：
10.1057/palgrave.jors.2600676
复制
发表时间：
1999-02
影响因子：
3.6
通讯作者：
L. Gambardella;É. Taillard;M. Dorigo
中科院分区：
文献类型：
--
作者：
L. Gambardella;É. Taillard;M. Dorigo
本文提出了一种结合局部搜索的混合蚁群算法HAS-QAP，并将其应用于二次分配问题。HAS-QAP使用信息素线索信息来执行对QAP解决方案的修改，不像更传统的蚂蚁系统使用信息素线索信息来构造完整的解决方案。HAS-QAP进行了分析和比较，与一些最好的算法可用于QAP：两个版本的禁忌搜索，即鲁棒性和反应禁忌搜索，混合遗传算法，和模拟退火方法。实验结果表明，HAS-QAP算法和混合遗传算法在求解真实的、不规则和结构化问题时具有较好的性能，而在求解随机、规则和非结构化问题时性能较差.
This paper presents HAS–QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS–QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS–QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. Experimental results show that HAS–QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS–QAP performance is less competitive on random, regular and unstructured problems.