求解QAP问题的近似骨架导向快速蚁群算法
作者:
基金项目:

Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030403(国家重点基础研究发展规划(973))

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [31]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

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

    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.

    参考文献
    [1]Koopmans TC, Berkmann MJ. Assignment problems and the location of economic activities. Econometrica, 1957,25:53-76.
    [2]Sahni S, Gonzalez T. P-Complete approximation problems. Journal of the Association of Computing Machinery, 1976,23(3):555-565.
    [3]Taillard ED. Comparison of iterative searches for the quadratic assignment problem. Location Science, 1995,3:87-105.
    [4]Elshafei AN. Hospital layout as a quadratic assignment problem. Operations Research Quarterly, 1977,28(1):167-179.
    [5]Steinberg L. The backboard wiring problem: A placement algorithm. SIAM Review, 1961,3:37-50.
    [6]Finke G, Burkard RE, Rendl F. Quadratic assignment problems. Annals of Discrete Mathematics, 1987,31:61-82.
    [7]Maniezzo V, Colorni A. The ant system applied to the quadratic assignment problem. IEEE Trans. on Data and Knowledge Engineering, 1999,11(5):769-778.
    [8]Gambardella L, Taillard E, Dorigo M. Ant colonies for the QAP. Journal of the Operations Research Society, 1999, 50:167-176.
    [9]Nissen V. Solving the Quadratic Assignment Problem with Clues from Nature. IEEE Trans. on Neural Networks, 1994,5(1): 66-72.
    [10]Merz P, Freisleben B. A genetic local search approach to the quadratic assignment problem. In: Proc. of the 7th Int'l Conf. of Genetic Algorithms, Morgan Kanffman Publishers, 1997. 465-472.
    [11]Misevicius A. A modified simulated annealing algorithm for the quadratic assignment problem. Informatica, 2003,14:497-514.
    [12]Ishii S, Sato M. Constrained neural approaches to quadratic assignment problems. Neural Networks, 1998,11:1073-1082.
    [13]Battiti R, Tecchiolli G. The reactive tabu search. ORSA Journal on Computing, 1994,2:126-140.
    [14]Nissen V, Paul H. A modification of threshold accepting and its application to the quadratic assignment Problem. OR Spektrum,1995,17:205-210.
    [15]Maniezzo V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. Technical Report, CSR 98-1, Sede di Cesena: Universit'a di Bologna, 1998.
    [16]Oliveira CAS, Pardalos PM, Resende MGC. GRASP with path-relinking for the QAP. In: MIC2003: the 5th Metaheuristics Int'l Conf. 2003.
    [17]Mills P, Tsang E, Ford J. Applying an extended guided local search to the quadratic assignment problem. Submission to Annals of Operation Research 2002.
    [18]Drezner Z. A new genetic algorithm for the quadratic assignment problem. INFORMS Journal on Computing, 2003,15(3):320-330.
    [19]Drezner Z. Robust heuristic algorithms for the quadratic assignment problem, mathematical methods in manufacturing and logistics.Mathematisches Forschungsinstitut, Oberwolfach, Germany, December 2001.
    [20]Kirkpatrick S, Toulouse G. Configuration space analysis of traveling salesman problems. Journal de Physique, 1985,46:1277-1292.
    [21]Zhang W. Phase transitions and backbones of 3-sat and maximum 3-sat. In: Proc. of the 7th Int'l Conf. on Principles and Practice of Constraint Programming (CP2001). 2001. 153-167.
    [22]Johnson DS, Gutin G, McGeoch LA, Yeo A, Zhang W, Zverovich A. Experimental analysis of heuristics for the ATSP. In: Gutin G,Punnen A, eds. The Traveling Salesman Problem and Its Variations. Kluwer Academic Publishers, 2002.445-488.
    [23]Climer S, Zhang W. Searching for backbones and fat: A limit-crossing approach with applications. In: Proc. of the AAAI2002.2002.707-712.
    [24]Zhang W, Rangan A, Looks M. Backbone guided local search for maximum satisfiability. In: Proc. of the 18th Int'l Joint Conf. on AI (IJCAI2003). Acapulco, Mexico, 2003.1179-1184.
    [25]Zou P, Zhou Z, Chen GL, Guo J. Multilevel reduction algorithm to TSP.Journal of Software, 2003,14(1):35-42 (in Chinese with English abstract). http:∥www.jos.org.cn/1000-9825/14/35.pdf
    [26]Taillard ED. FANT: Fast ant system. Technical Report, IDSIA-46-98, Lugano: IDSIA, 1998.
    [27]Taillard ED, Gambardella L. Adaptive memories for the quadratic assignment problems. Technical Report, IDSIA-87-97, Lugano:IDSIA, 1997.
    [28]Schneider J, Froschhammer C, Morgenstern I, Husslein T, Singer JM. Searching for backbones-An efficient parallel algorithm for the traveling salesman problem. Computer Physics Communications, 1996,96:173-188.
    [29]Burkard RE, Karisch S, Rendl F. QAPLIB-A quadratic assignment problem library. European Journal of Operational Research,1991,55:115 - 119. http:∥www.opt.math.tu-graz.ac.at/qaplib/
    [30]Vollmann TE, Buffa ES. The facilities layout problem in perspective. Management Science, 1966,12(10):450-468.
    [31]邹鹏,周智,陈国良,顾钧.求解TSP问题的多级归约算法.软件学报,2003,14(1):35-42.http:∥www.jos.org.cn/1000-9825/14/35.pdf
    引证文献
引用本文

邹鹏,周智,陈国良,江贺,顾钧.求解QAP问题的近似骨架导向快速蚁群算法.软件学报,2005,16(10):1691-1698

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2003-07-28
  • 最后修改日期:2004-01-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号