[1]张广帅,张煜东,吉根林.蚁群算法求解TSP综述[J].南京师范大学学报(工程技术版),2014,14(04):039.
　Zhang Guangshuai,Zhang Yudong,Ji Genlin.Survey on Ant Colony Algorithm for the Traveling Salesman Problem[J].Journal of Nanjing Normal University(Engineering and Technology),2014,14(04):039.
点击复制

蚁群算法求解TSP综述
分享到：

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

卷:
14卷
期数:
2014年04期
页码:
039
栏目:
出版日期:
2014-12-31

文章信息/Info

Title:
Survey on Ant Colony Algorithm for the Traveling Salesman Problem
作者:
张广帅; 张煜东; 吉根林
南京师范大学计算机科学与技术学院,江苏 南京 210023
Author(s):
Zhang Guangshuai; Zhang Yudong; Ji Genlin
School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China
关键词:
蚁群算法; 蚂蚁系统; 蚁群系统; 最大最小蚂蚁系统; 旅行商问题
Keywords:
ant colony algorith; ant system; ant colony system; max-min ant system; TSP
分类号:
TP182
文献标志码:
A
摘要:
蚁群算法是一种群智能算法,可用于求解图模型最优化路径的计算问题.它于1992年由Dorigo M.提出,借鉴蚂蚁在蚁群与食物之间寻找最短路径.本文集中讨论了几种典型的求解旅行商问题的蚁群算法扩展,讨论其相应的优缺点,并对其学术与工业的应用领域与合理发展进行了总结与展望.
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.

相似文献/References:

[1]王俊峰,朱庆保.基于蚁群算法的知识约简[J].南京师范大学学报(工程技术版),2005,05(02):050.
　WANG Junfeng,ZHU Qingbao.A Knowledge Reduction Method based on Ant Colony Algorithm[J].Journal of Nanjing Normal University(Engineering and Technology),2005,05(04):050.
[2]王水花,张煜东,吉根林.群智能算法的理论及应用综述[J].南京师范大学学报(工程技术版),2014,14(04):031.
　Wang Shuihua,Zhang Yudong,Ji Genlin.Survey on Theories and Applications of Swarm Intelligence Algorithms[J].Journal of Nanjing Normal University(Engineering and Technology),2014,14(04):031.
[3]张文祺,王 琦,徐乾宸,等.考虑时序特性的分布式光伏接入配电网的选址定容问题研究[J].南京师范大学学报(工程技术版),2017,17(03):022.[doi:10.3969/j.issn.1672-1292.2017.03.004]
　Zhang Wenqi,Wang Qi,Xu Qianchen,et al.Optimal Locating and Sizing of Distributed Photovoltaic in DistributionNetwork Considering Timing Characteristics[J].Journal of Nanjing Normal University(Engineering and Technology),2017,17(04):022.[doi:10.3969/j.issn.1672-1292.2017.03.004]

备注/Memo

备注/Memo:
收稿日期:2013-12-17.
基金项目:国家自然科学基金(610011024)、南京师范大学高层次人才科研启动
基金项目(2013119XGQ0061).
通讯联系人:张煜东,博士,教授,研究方向:人工智能与医学图像处理.E-mail:zhangyudong@njnu.edu.cn
更新日期/Last Update: 2014-12-31