首页 | 本学科首页   官方微博 | 高级检索  
     

求解QAP问题的近似骨架导向快速蚁群算法
引用本文:邹鹏,周智,陈国良,江贺,顾钧.求解QAP问题的近似骨架导向快速蚁群算法[J].软件学报,2005,16(10):1691-1698.
作者姓名:邹鹏  周智  陈国良  江贺  顾钧
作者单位:1. 中国科学技术大学,计算机科学技术系,国家高性能计算中心(合肥),安徽,合肥,230027
2. 中国科学技术大学,计算机科学技术系,国家高性能计算中心,合肥,安徽,合肥,230027;香港科学技术大学,计算机科学系,香港
基金项目:Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030403(国家重点基础研究发展规划(973))
摘    要:QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法--近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一-快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.

关 键 词:QAP  近似骨架  ABFANT  QAPLIB
收稿时间:07 28 2003 12:00AM
修稿时间:1/6/2004 12:00:00 AM

Approximate-Backbone Guided Fast Ant Algorithms to QAP
ZOU Peng,ZHOU Zhi,CHEN Guo-Liang,JIANG He and GU Jun.Approximate-Backbone Guided Fast Ant Algorithms to QAP[J].Journal of Software,2005,16(10):1691-1698.
Authors:ZOU Peng  ZHOU Zhi  CHEN Guo-Liang  JIANG He and GU Jun
Affiliation:1 National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China;2 Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, China
Abstract:Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. This paper presents a new fast ant heuristic for the QAP, the approximatebackbone guided fast ant colony algorithm (ABFANT). The main idea is to fix the approximatebackbone which is the intersection of several local optimal permutations to the QAP. After fixing it, the authors can smooth the search space of the QAP instance without losing the search capability, and then solve the instance using the known fast ant colony algorithm (FANT) which is one of the best heuristics to the QAP in the much smoother search space. Comparisons of ABFANT and FANT within a given iteration number are performed on the publicly available QAP instances from QAPLIB. The result demonstrates that ABFANT significantly outperforms FANT.Furthermore, this idea is general and applicable to other heuristics of the QAP.
Keywords:QAP  approximate-backbone  ABFANT  QAPLIB
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号