XIA Xiaoyun, ZHOU Yuren. Performance Analysis of ACO on the Quadratic Assignment Problem[J]. Chinese Journal of Electronics, 2018, 27(1): 26-34. doi: 10.1049/cje.2017.06.004
Citation: XIA Xiaoyun, ZHOU Yuren. Performance Analysis of ACO on the Quadratic Assignment Problem[J]. Chinese Journal of Electronics, 2018, 27(1): 26-34. doi: 10.1049/cje.2017.06.004

Performance Analysis of ACO on the Quadratic Assignment Problem

doi: 10.1049/cje.2017.06.004
Funds:  This work is supported by the National Natural Science Foundation of China (No.61703183, No.61773410), the Scientific Research Special Plan of Guangzhou Science and Technology Programme (No.201607010045), the Education Scientific Planning Project of Zhejiang Province (No.2017SCG048), and the Natural Science Foundation of Jiangxi Province of China (No.20151BAB217008).
  • Received Date: 2016-03-15
  • Rev Recd Date: 2016-12-01
  • Publish Date: 2018-01-10
  • The Quadratic assignment problem (QAP) is to assign a set of facilities to a set of locations with given distances between the locations and given flows between the facilities such that the sum of the products between flows and distances is minimized, which is a notoriously difficult NP-hard combinatorial optimization problem. A lot of heuristics have been proposed for the QAP problem, and some of them have proved to be efficient approximation algorithms for this problem. Ant colony optimization (ACO) is a general-purpose heuristic and usually considered as an approximation algorithms for NP-hard optimization problems. However, we know little about the performance of ACO for QAP from a theoretical perspective. This paper contributes to a theoretical understanding of ACO on the QAP problem. The worst-case bound on a simple ACO algorithm called (1+1) Max-min ant algorithm ((1+1) MMAA) for the QAP problem is presented. It is shown that a degenerate (1+1) MMAA finds an approximate solution on the QAP problem. Finally, we reveal that ACO can outperform the 2-exchange local search algorithm on an instance of the QAP problem.
  • loading
  • M. Dorigo, V. Maniezzo and A. Colorni, "Ant system:Optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, Cybernetics-Part B, Vol.26, No.1, pp.29-41, 1996.
    M. Dorigo and T. Stützle, Ant Colony Optimization, Cambridge, MA:MIT Press, 2004.
    W.J. Gutjahr, "Mathematical runtime analysis of ACO algorithms:Survey on an emerging issue", Swarm Intelligence, Vol.1, No.1, pp.59-79, 2007.
    W.J. Gutjahr, "First steps to the runtime complexity analysis of ant colony optimization", Computers and Operations Research, Vol.35, No.9, pp.2711-2727, 2008.
    F. Neumann and C. Witt, "Runtime analysis of a simple ant colony optimization algorithm", Algorithmica, Vol.54, No.2, pp.243-255, 2009.
    S. Droste, T. Jansen and I. Wegener, "On the analysis of the (1+1) evolutionary algorithm", Theoretical Computer Science, Vol.276, No.1-2, pp.51-81, 2002.
    B. Doerr, F. Neumann, D. Sudholt, et al., "Runtime analysis of the 1-ANT ant colony optimizer", Theoretical Computer Science, Vol.412, No.17, pp.1629-1644, 2011.
    T. Stützle and H.H. Hoos, "MAX-MIN ant system", Future Generation Computer Systems, Vol.16, No.8, pp.889-914, 2000.
    W.J. Gutjahr and G. Sebastiani, "Runtime analysis of ant colony optimization with best-so-far reinforcement", Methodology and Computing in Applied Probability, Vol.10, No.3, pp.409-433, 2008.
    F. Neumann, D. Sudholt and C. Witt, "Analysis of different MMAS ACO algorithms on unimodal functions and plateaus", Swarm Intelligence, Vol.3, No.1, pp.35-68, 2009.
    F. Neumann and C. Witt, "Ant colony optimization and the minimum spanning tree problem", Theoretical Computer Science, Vol.411, No.25, pp.2406-2413, 2010.
    Y. Zhou, "Runtime analysis of an ant colony optimization algorithm for TSP instances", IEEE Transactions on Evolutionary Computation, Vol.13, No.5, pp.1083-1092, 2009.
    T. Kötzing, F. Neumann, H. Röglin, et al., "Theoretical analysis of two ACO approaches for the traveling salesman problem", Swarm Intelligence, Vol.6, No.1, pp.1-21, 2012.
    N. Attiratanasunthron and J. Fakcharoenphol, "A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs", Information Processing Letters, Vol.105, No.3, pp.88-92, 2008.
    D. Sudholt and C. Thyssen, "Running time analysis of ACO systems for shortest path problems", Journal of Discreate Algorithm, Vol.10, pp.165-180, 2012.
    A. Lissovoi and C. Witt, "MMAS versus population-based EA on a family of dynamic fitness functions", Algorithmica, Vol.75, No.3, pp. 554-576, 2016.
    T. Friedrich, T. Kötzing, M.S. Krejca, et al., "Robustness of ant colony optimization to noise", Evolutionary Computation, Vol.24, No.2, pp.237-254, 2016.
    T.C. Koopmans and M.J. Beckman, "Assignment problems and the location of economic activities", Econometrica, Vol.25, No.1, pp. 53-76, 1957.
    S. Sahni and T. Gonzalez, "P-Complete approximation problems", Journal of the ACM, Vol.23, No.3, pp.555-565, 1976.
    E. Angel and V. Zissimopoulos, "On the quality of local search for the quadratic assignment problem", Discrete Applied Mathematics, Vol.82, No.1-3, pp.15-25, 1998.
    I. Wegener, "Methods for the analysis of evolutionary algorithms on pseudo-boolean functions", in:Sarker R, Mohammadian M and Yao X, eds. Evolutionary Optimization, Dordrecht:Kluwer, pp.349-369, 2002.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (186) PDF downloads(357) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint