摘要
蚂蚁算法是一种的新的启发式算法，是目前国内外启发式算法研究的热点和前沿问题。它的应用已涉及许多领域，如旅行商问题、指派问题、job-shop调度问题、图着色问题等等，并且取得了很好的效果。但是关于蚂蚁算法的理论分析和实践应用远未像GA、SA等算法那样成熟，还存在许多有待进一步研究的问题。
本文讨论了生物中蚁群的觅食行为特点，论述了人工蚂蚁算法的原理与模型，分析了人工蚁群与真实蚁群之间的联系与区别。对TSP问题、QoS组播路由、VC路由、话网路由、凸整数规划以及度限制树的求解等问题，分别运用基本蚂蚁算法和改进蚂蚁算法进行求解，对它们的结果进行了比较，指出改进蚂蚁算法优于基本蚂蚁算法。在QoS组播路由问题中将蚂蚁算法与当前流行的另一类启发式算法——遗传算法进行比较，阐述了蚂蚁算法的优越性。另外，本文创造性地提出了人工蚂蚁算法的扩展性，并在一些问题中采用蚂蚁算法的扩展性进行求解，分析了它的优越性和高效性。
还在求解度限制树问题的基础上，提出了基于蚂蚁算法的聚类分析方法。该方法虽然求解效率比较低，但具有克服聚类盲目性的优点。
Ant algorithm is a new meta-heuristic algorithm. There is currently a lot of ongoing activity in the scientific community to extend or apply ant-based algorithms to many different discrete optimization problems. It has been used successfully in many fields, such as TSP, assignment problem, job-shop scheduling and graph coloring. The theory and application of ant algorithm are not mature as genetic algorithms and simulated annealing, so we must study it more.
In this paper, we discuss the characteristic of ants when they search for food, give the theory and model of ant algorithm, and analyze the relation and difference between artificial ants and real ants. We use based and improved ant algorithm to solve problems, such as TSP, QoS multicast routing, VC routing, phone net routing, convex integer programming and degree-constrained minimum spanning tree problem, then compare the results to show that the improved ant algorithm is better. When solving the QoS multicast routing problem, we compare this algorithm with the other meta-heuristic algorithm梘enetic algorithm, and find this algorithm has good effect. Otherwise, we first put forward a viewpoint梕xpansibility of ant algorithm. We use this new viewpoint in some fields and find it is predominant and effective.
Base on solving the problem of degree-constrained minimum spanning tree, we put forward a new method to solving clustering problem. The efficiency of this method is not high, but it can conquer the blindly of clustering.
引文
[1] 赵凯，王珏。适应性计算。模式识别与人工智能，2000，13(4)：407-414
[2] Kaelbing L P, Littman M L, Moore A W. Reinforcement Learning: A Survey. Journal of Artificial Intelligence Research, 1996, 4: 237-285
[3] Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning. Massacheusettes: Addison-Wesley Pub, 1989
[4] Marco Dorigo, Luca M. Garnbardella. Ant colonied for the Travelling Salesman Problem. 1997, 43: 73-81
[5] Colorni A, Dorigo Mand Maniezzo V. Distributed optimization by ant colonies[A]. In: Proc. of 1st European Conf. Artificial Life[C]. Pans, France: Elsevier, 1991, 134-142
[6] Colorni A, Dorigo Mand Maniezzo V. An investigation of some propertied of an ant algorithm[A]. In: Proc. Of Parallel Problem Solving from Nature (PPSN)[C]. France: Elsiver, 1992, 509-520
[7] 张纪会，徐心和．带遗忘因子的蚁群算法，系统仿真学报，2000，(2)
[8] 张纪会，徐心和．具有变异特征的蚁群算法，计算机研究与发展，2000，(1)
[9] Colorni A, Dorigo Mand Maniezzo V, et al. Ant system for job shop scheduling[J]. Belgian J. of Operations Research Statistics and computer science, 1994, 34(1): 39-53
[10] Dorigo M, Maniezzo Vand Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Trans. on Systems, Man and Cybernatics, 1996, 26(1): 28-41
[11] Dorigo M, Maniezzo Vand Colorni A. Ant system: an autocatalytic optimizing process [R]. Technical Report 91-O16, Politecnico di Milano, 1991
[12] 王征应，石冰心。基于启发式遗传算法的QoS组播路由问题求解。计算机学报，2001，24(1)：55-61
[13] 李生红，刘泽民，周正。ATM网上基于蚂蚁算法的VC路由选择方法。通信学报，2000，21(1)：22-28
[14] 闫亮。蚂蚁与话网路由优化。信息工作，1999(3)：22-24
[15] 马良，蒋馥。度限制最小树的蚂蚁算法。系统工程学报，1999，14(3)：211-214
[16] 李秋霞，贺达汉，长有德，刘丽丹。蚂蚁取食行为研究概况。宁夏农学院学报，2000，21(2)：94-97蔡利剑。
[17] Marco Dorigo, Gianni Di Caro. Ant algorithms for discrete Optimization. Artificial Life, 1999, 5(3): 137-172
[18] 智能蚂蚁系统研究。河北工业大学硕士研究生学位论文，2001，1：9-10
[19] 吴卫。基于多项服务质量的组播路由算法。电子技术应用，2000，266(8)
[20] 王颖，谢剑英。一种基于蚁群系统的多点路由新算法。计算机工程，2001，27(1)：55-75
[21] 王明中，谢剑英。ATM网络拥塞预防的动态负载平衡策略。ftp://202. 120.8. 134/incoming/wangmz/my document/paper accepted
[22] 陶洋。网间控制关键技术研究[博士论文]。重庆大学，1997
[23] 林锦，朱文兴。凸整数规划问题的混合蚁群算法。福州大学学报，1999，27(6)：5-9
[24] Jiawei Han，Micheline Kamber．数据挖掘概念与技术。机械工业出版社，pp．223
[25] Dorigo M, Gambardella L M. Ant Colony System A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, 1997: 53-66.
[26] Edmund Burke, Graham Kendall. Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem. http://www, asap. cs. nott. ac. uk/publications/pdf/gk.ai99, pdf
[27] Dorgo M and Luca M. A study of some properties of ant-Q[A]. In: H M Voigt, W Ebeling and I Rechenberg, et al eds. Proc. Of 4th Int. Conf. On Parallel Problem Solving from Nature (PPSN)[C]. Berlin: Springer Verlag, 1996, 656-665
[28] Marco Dorigo and Gianni Di Caro. The Ant Colony Optimization Meta-Heuristic. http://wwwmayr.informatik.tu-muenchen.de/lehre/1999SS/optprak/BC.04-DorDic-NIO99.pdf
[29] Bruno Guerrieri. Use of a Colony of Cooperating Agents and MAPLE to Solve the Traveling Salesman Problem. http://archives, math. utk. edu/ICTCM/EP-13/C39/pdf/paper, pdf
[30] Eric Bonabeau, Florian Henaux, Sylvain Gu. Routing in telecommunications networks with smart ant-like agents. Intelligent Agents for Telecommunications Applications '98
[31] Zhang Su-bing Liu Zemin. Neural Network Training Using Ant Algorithm in ATM Traffic Control. ISCAS-2001 Manuscript Information for Paper 1221.
[32] Luk Schools, Bart Naudts. Ant Colonies are Good at Solving Constraint Satisfaction Problems. In: Proceedings of 2000 Congress on Evolutionary Computation. IEEE press, pp. 1190-1195.
[33] Lu Guoying, Liu Zemin, Zhou Zheng. Multicast Routing Based on Ant Algorithm for Delay-Bounded and Load-Balancing Traffic. The 25th Annual IEEE Conference on Local Computer Networks (LCN).
[34] Ying Wang, Jianying Xie. Ant Colony Optimization For Multicast Routing. Proceedings of the 25th Annual IEEE Conference on Local Computer Networks (LCN'00).
[35] Guoying Lu, Zemin Liu. Multicast Routing Based on Ant-Algorithm with Delay and Delay Variation Constraints.
[36] Zhang Subing, Liu Zemin. A QoS Routing Algorithm Based on Ant Algorithm. Proceedings of the 25th Annual IEEE Conference on Local Computer Networks (LCN'00).
[37] 王磊，戚飞虎。大矢量空间聚类的遗传k-均值算法。上海交通大学学报，1999，33(9)
[38] 徐勇，刘弈文，陈贺新，戴逸松。一种基于自适应遗传算法的聚类方法。系统工程与电子技术，1997，(9)
[39] 邓先礼。最优化技术。重庆大学出版社。
[40] 于兴伟，黄敏，刘积仁。基于服务质量的多媒体组通信目的节点加入与退出算法的研究。计算机学报，2001，24(8)：838-844
[41] 王兴伟，王志军，黄敏等。基于服务质量的多媒体通信初始路由建立算法的研究。计算机学报，2001，24(8)：830-837
[42] 杨沛。蚁群社生物学及多样性。昆虫知识，1999，36(6)：243-247
[43] 顾立尧。带有度约束的最小耗费生成树的分支限界算法。计算机应用与软件，1989，6(6)：49-54
[44] 马良，蒋馥。度约束最小生成树的快速算法。运筹与管理，1998，7(1)：1-5
[45] Stutzle T, Hoos H. The MAX-MIN ant system and local search for the traveling salesman problem, Proc. of ICEC'97-1997 1EEE 4th Int. Conf. On Evolutionary Computation, IEEE Press, 1997, 308-313
[46] 彭斯俊，黄樟灿，刘道海等。基于蚂蚁系统的TSP问题的新算法。武汉汽车工业大学学报，1998，10(5)：88-92
[47] 周正，刘泽民。智能蚂蚁算法及其在电信网动态路由优化中的应用。电信科学，1998，11：10-13
[48] 李生红，潘理，诸鸿文等。基于蚂蚁算法的组播路由调度方法。计算机工程，2001，27(4)：63-65
[49] 徐智敏，沈钧贤。蚂蚁捷径返巢及其朝向机制的研究。昆虫学报，2000，43(3)：242-247
[50] 张纪会，高齐圣，徐心和。自适应蚁群算法。控制理论与应用，2000，17(1)：2-8