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

• 作者: 周智 江贺 邹鹏 陈国良 顾钧
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: QAP 近似骨架 ABFANT QAPLIB
• 年，卷（期）: 2005,（10）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1691-1698
• 页数: 8页
• 分类号: TP301
• 语种: 中文

摘要

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