|Table of Contents|

Survey on Ant Colony Algorithm for the Traveling Salesman Problem(PDF)

南京师范大学学报(工程技术版)[ISSN:1006-6977/CN:61-1281/TN]

Issue:
2014年04期
Page:
39-
Research Field:
Publishing date:

Info

Title:
Survey on Ant Colony Algorithm for the Traveling Salesman Problem
Author(s):
Zhang GuangshuaiZhang YudongJi Genlin
School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China
Keywords:
ant colony algorithant systemant colony systemmax-min ant systemTSP
PACS:
TP182
DOI:
-
Abstract:
Ant colony algorithm(ACA)is a swarm intelligence-based method for solving computational problems that can be reduced to finding good paths through graphs.It was initially proposed by M.Dorigo in 1992,inspired by the behavior of ants seeking a shortest paths between the colony and a source of food.The paper concentrates on the discussions of the typical ACA extension for solving the traveling salesman problem(TSP)and their respective advantages and disadvantages,and finally summarize and expect their academic and industrial applied fields and reasonable developments.

References:

[1] 许殿,史小卫,程睿.回归蚁群算法[J].西安电子科技大学学报,2005,32(6):944-947.
Xu Dian,Shi Xiaowei,Cheng Rui.Returned ant algorithm[J].Journal of Xidian University,2005,32(6):944-947.(in Chiness)
[2]Dorigo M,Birattari M,Stutzle T.Ant colony optimization[J].IEEE on Computational Intelligence Magazine,2006,1(4):28-39.
[3]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B:Cybernetics,1996,26(1):29-41.
[4]Dorigo M.Optimization,Learning and Natural Algorithms[D].Politecnico di Milano,Italy,1992.
[5]张煜东,吴乐南,韦耿.智能算法求解TSP问题的比较[J].计算机工程与应用,2009(11):11-15.
Zhang Yudong,Wu Lenan,Wei Gen.Comparison on solving TSP via intelligent algorithm[J].Computer Engineering and Applications,2009(11):11-15.(in Chinese)
[6]Zhang Y,Agarwal P,Bhatnagar V,et al.Swarm intelligence and its applications[J].The Scientific World Journal,2013(2013):528 069.
[7]Hinchey M G,Sterritt R,Rouff C.Swarms and swarm intelligence[J].Computer,2007,40(4):111-113.
[8]De Castro L N.Fundamentals of natural computing:an overview[J].Physics of Life Reviews,2007,4(1):1-36.
[9]Marinakis Y,Marinaki M,Doumpos M,et al.Ant colony and particle swarm optimization for financial classification problems[J].Expert Systems with Applications,2009,36(7):10 604-10 611.
[10]Blum C,Valles M Y,Blesa M J.An ant colony optimization algorithm for DNA sequencing by hybridization[J].Computers & Operations Research,2008,35(11):3 620-3 635.
[11]Enagls C,Manthey B.Average-case approximation ratio of the 2-opt algorithm for the TSP[J].Operations Research Letters,2009,37(2):83-84.
[12]Escoffier B,Monnot J.A better differential approximation ratio for symmetric TSP[J].Theoretical Computer Science,2008,396(1-3):63-70.
[13]Abrahamson J,Shokoufandeh A,Winter P.Euclidean TSP between two nested convex obstacles[J].Information Processing Letters,2005,95(2):370-375.
[14]Li B,Zhou Z,Zou W X,et al.Ant intelligence inspired blind data detection for ultra-wideband radar sensors[J].Information Sciences,2014,255:204-220.
[15]Yu H,Gu G,Liu H,et al.A modified ant colony optimization algorithm for tumor marker gene selection[J].Genomics,Proteomics & Bioinformatics,2009,7(4):200-208.
[16]Forsati R,Moayedikia A,Jensen R,et al.Enriched ant colony optimization and its application in feature selection[J].Neurocomputing,2014,142:354-371.
[17]Powell C M,Hanson J D,Bextine B R.Bacterial community survey of solenopsis invicta buren(red imported fire ant)colonies in the presence and absence of solenopsis invicta virus(SINV)[J].Current Microbiology,2014,69(4):580-585.
[18]Huang X W,Zou X B,Zhao J W,et al.Measurement of total anthocyanins content in flowering tea using near infrared spectroscopy combined with ant colony optimization models[J].Food Chemistry,2014,164:536-543.
[19]Wei X,Han L,Hong L.A modified ant colony algorithm for traveling salesman problem[J].International Journal of Computers Communications & Control,2014,9(5):633-643.
[20]张煜东,吴乐南,韦耿.一种改进的基于隶属云模型的蚁群算法[J].计算机工程与应用,2009,45(27):11-14,23.
Zhang Yudong,Wu Lenan,Wei Gen.Improved ant colony algorithm based on membership cloud models[J].Computer Engeering and Application,2009,45(27):11-14,23.(in Chinese)
[21]Lu M L,Xu B L,Sheng A D,et al.Modeling analysis of ant system with multiple tasks and its application to spatially adjacent cell state estimate[J].Applied Intelligence,2014,41(1):13-29.
[22]Goodarzi M,Freitas M P,Jensen R.Ant colony optimization as a feature selection method in the QSAR modeling of anti-HIV-1 activities of 3-(3,5-dimethylbenzyl)uracil derivatives using MLR,PLS and SVM regressions[J].Chemometrics and Intelligent Laboratory Systems,2009,98(2):123-129.
[23]Matteucci M,Mussone L.An ant colony system for transportation user equilibrium analysis in congested networks[J].Swarm Intelligence,2013,7(4):255-277.
[24]Crawford B,Soto R,Johnson F,et al.A max-min ant system algorithm to solve the software project scheduling problem[J].Expert Systems with Applications,2014,41(15):6 634-6 645.
[25]周勇,陈洪亮.蚁群算法的研究现状及其展望[J].微型电脑应用,2002,5(2):23-25.
Zhou Yong,Chen Hongliang.The status quo and foresight on ant colony algorithm[J].Microcomputer Applications,2002,5(2):23-25.(in Chinese)
[26]张煜东,吴乐南,韦耿.基于正负反馈机制的蚁群算法用于软硬件划分[J].电子测量与仪器学报,2009,23(8):32-38.
Zhang Yudong,Wu Lenan,Wei Gen.Appliation of improved ant colony algorithm based on formard/backward feedback in hardware/software partition[J].Journal of Electronic Measurement and Instrument,2009,23(8):32-38.(in Chinese)
[27]Ahmmed A,Rana M A A,Mahmudul Haque A A M,et al.A multiple ant colony system for dynamic vehicle routing problem with time window[C]//Proceedings of the Convergence and Hybird Information Technology,2008 ICCIT’08 Third International Conference on.Khulna,Bangladesh,2008:182-187.
[28]Boltuzic F,Rakipovic A.A hybird ant colony system approach for solving capacitated vehicle routing problems with time windows[C]//Proceedings of the MIPRO,2012 Proceedings of the 35th International Convention.Opatija,Croatia,2012:1 758-1 762.
[29]何靖华,肖人彬,师汉民.蚂蚁算法在机构同构判定中的实现[J].模式识别与人工智能,2001,14(4):406-412.
He Jinghua,Xiao Renbin,Shi Hanmin.Implementation of ant algorithm for isomorphism identification of mechnisms[J].PR&AI,2001,14(4):406-412.(in Chinese)
[30]张煜东,吴乐南,唐磊.隶属云模型蚁群算法的新应用:生鲜食品多阶段动态定价[J].统计与决策,2009,22:26-29.
Zhang Yudong,Wu Lenan,Tang Lei.Cloud model based ant colony algorithm for multi-period dynamic pricing of fresh foods[J].Statistics and Dection,2009,22:26-29.(in Chinese)
[31]Wang S,Wu L,Zhang Y,et al.Ant colony algorithm used for bankruptcy prediction[C]//Proceedings of the Information Science and Engineering(ISISE),2009 Second International Symposium on.Shanghai,2009:137-139.
[32]Qi C M,Li P.An exponential entropy-based hybrid ant colony algorithm for vehicle routing optimization[J].Applied Mathematics & Information Sciences,2014,8(6):3 167-3 173.
[33]Guerrero G D,Cecilia J M,Llanes A,et al.Comparative evaluation of platforms for parallel ant colony optimization[J].Journal of Supercomputing,2014,69(1):318-329.

Memo

Memo:
-
Last Update: 2014-12-31