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

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