求解QAP问题的近似骨架导向快速蚁群算法(英文)

被引：11

作者：

邹鹏

周智

陈国良

江贺

顾钧

机构：

[1] 中国科学技术大学计算机科学技术系国家高性能计算中心(合肥)

来源：

软件学报 | 2005年 / 10期

关键词：

QAP; 近似骨架; ABFANT; QAPLIB;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法——近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一??快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.

引用

页码：1691 / 1698

页数：8

共 14 条

[1] 求解TSP问题的多级归约算法
邹鹏
周智
陈国良
顾钧
[J]. 软件学报, 2003, (01) : 35 - 42
[2] A new genetic algorithm for the quadratic assignment problem
Drezner, Z
[J]. INFORMS JOURNAL ON COMPUTING, 2003, 15 (03) : 320 - 330
[3] A modified simulated annealing algorithm for the quadratic assignment problem
Misevicius, A
[J]. INFORMATICA, 2003, 14 (04) : 497 - 514
[4] Constrained neural approaches to quadratic assignment problems
Ishii, S
Sato, M
[J]. NEURAL NETWORKS, 1998, 11 (06) : 1073 - 1082
[5] Searching for backbones — an efficient parallel algorithm for the traveling salesman problem[J] . Johannes Schneider,Christine Froschhammer,Ingo Morgenstern,Thomas Husslein,Johannes Maria Singer.Computer Physics Communications . 1996 (2)
[6] Comparison of iterative searches for the quadratic assignment problem[J] . éric D. Taillard.Location Science . 1995 (2)
[7] A modification of threshold accepting and its application to the quadratic assignment problem[J] . Volker Nissen,Henrik Paul.OR Spektrum . 1995 (2)
[8] The Reactive Tabu Search[J] . Roberto Battiti,Giampietro Tecchiolli.ORSA Journal on Computing . 1994 (2)
[9] Configuration space analysis of travelling salesman problems[J] . S. Kirkpatrick,G. Toulouse.Journal de Physique . 1985 (8)
[10] Hospital Layout as a Quadratic Assignment Problem[J] . Operational Research Quarterly (1970-1977) . 1977 (1)

← 1 2 →