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

摘要：

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

关键词：QAP、近似骨架、ABFANT、QAPLIB

所属期刊栏目：16

分类号：TP301(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划973计划G1998030403

在线出版日期：2005-11-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1691-1698