蚁群算法的改进与应用
|
摘要
人们从仿生学的机理中受到启发，提出许多解决复杂优化问题的新方法，统称为元启发(metahueristic)算法，如遗传算法、进化策略、模拟退火、蚁群算法、禁忌搜索(tabu search)算法等，并成功地应用于实际问题，蚁群算法(ant colony algorithm，简称ACA)是最近几年才提出来的一种新型的模拟进化算法，它是由意大利学者M．Dorigo，V．Mahiezzo，A．Colorni等人受到人们对自然界中真实蚁群集体行为的研究成果的启发而首先提出来的。他们充分利用蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性，通过人工模拟蚂蚁搜索食物的过程中个体之间的信息交流与相互协作最终找到从蚁群到食物源的最短路径的原理解决了TSP问题，取得了很好的结果。随后，蚁群算法被用来求解job-shop调度问题、指派问题、序列求序(sequential ordering)等NP完全问题，显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的优越性，证明它是一种具有广阔发展前景的好方法。
但是，蚁群算法仍然存在一些缺陷：如在性能方面，算法的收敛速度和所得解的多样性、稳定性等性能间存在矛盾：这是因为蚁群中多个个体的运动是随机的，虽然通过信息的交流能够向着最优路径进化，但是当群体规模较大时，很难在较短时间内从复杂无章的路径中找出一条较好的路径，如果一味加快收敛速度则很可能导致蚂蚁的搜索陷入局部最优造成早熟、停滞现象。应用范围方面，蚁群算法的应用尚且局限在较小的范围中，难以处理连续空间的优化问题：由于每个蚂蚁在每个阶段所作的选择总是有限的，它要求离散的解空间，因而它对组合优化等离散优化问题很适用，而对线性和非线性规划等连续空间的优化问题的求解不能直接应用。
本文首先详细介绍了基本蚁群算法并综述了当前国内外蚁群算法的研究现状；分析了蚁群算法中蚂蚁搜索过程的本质，针对上述蚁群算法存在的问题，在第四章提出了平衡蚁群算法收敛速度解的性能之间矛盾，提高其性能的四种改进蚁群算法，并总结当前研究工作，分析相关问题，给出了我们在该方面工作的进一步研究思路。
第一种算法是基于分布均匀度的自适应蚁群算法，根据优化过程中蚂蚁的分布均匀度，动态地调整下一次迭代过程中蚂蚁分布的大致范围，同时根据不同蚂蚁选择的各条路径构成解的好坏程度有差别的自适应更新相应路径上的信息量。第二种算法模拟蚂蚁感觉和知觉行为，将蚂蚁的搜索过程分为三个阶段，在不同阶段有差别的采取不同的优化机制，成功地避免蚂蚁完全受信息量影响的“道听途说”而造成的干
扬州大学石贞{一学位论文
扰和自日选路，第三种算法是改进的增强型蚁群算法，通过增强全局(或局部)最优解
和全局(或局部_次优解的路径上的信息量浓度以及对它们进行交叉和变异操作的遗
传优化方法来改进增强型蚁群算法.第四种算法在算法中引入免疫遗传学
(i mmunogenetics)及免疫系统中的浓度控制机制，调节蚂蚁遍历过程中的信息量分布，
弓!用小生境技术(n iche)，将蚁群分化为若干小子群独立进化.实验证明这四种算法平
衡了收敛速度与解的多样性之间的矛后，有效避免了早熟和停滞现象.
在研究过程中，我们发现基本蚁群算法的一个不可忽视的应用缺陷是不太适合
求解连续性优化问题，为此在第五章，我们还提出一种用蚁群算法求解连续空间优化
问题的方法，将解空间划分成若干子域，在蚁群算法的每一次迭代中，首先根据信息量
求出解所在的子域，然后在该子域内已有的解中确定解的具体的值.实践证明，这种方
、法可推广应用到其他连续空间的优化问题之中，突破了基本蚁群算法的应用局限，为
将该算法应用于连续性优化问题提出了新的途径，
另外，我们还把蚁群算法应用于o一1背包问题，武器一目标分配问题、Flow一shoP
问题以及Qos路由问题，都获得了比较好的应用，取得了较好的效果.特别是在解决
Qos成组多播路由问题的改进蚁群算法中，不但简化了算法中参数的选取过程，还避
免了将各个度量参数的简单归一，算法能充分保证实际网络Qos需求.
在本文中，我们提出求解TSP问题的四种提高蚁群算法性能的改进算法，给出该
方面工作的进一步研究思路;同时改进基本蚁群算法结构，使其适应于求解连续优化
问题;研究其优化本质，将其应用于除TSP问题外的五种不同应用问题，大量应用实例
的实验结果证明，这些改进的蚁群算法不但加速了蚁群算法的收敛速度，提高了优化
所得解的质量，而且扩大了蚁群算法的应用范围.
Ant colony algorithm (AC) has emerged recently as a new meta-heuristic for NP-hard problems in combinatorial optimization. This meta-heuristic also includes evolutionary algorithms, neural networks, simulated annealing which all belong to the class of problem-solving strategies derived from nature. Dorigo, Maniezzo, and Colorni [Dorigo M, Maniezzo V, Colorni A., 1996], using the Traveling Salesman Problem (TSP) [Dorigo M, Gambardella L. M.,1997] as example, introduced the first AC algorithm. With the further study in this area, ant colony algorithm is widely applied to the problems of Job-shop Scheduling Problem (JSP)[ Colorni A., Dorigo M, Maniezzo V.,1994], the Quadratic Assignment Problem (QAP)[ Maniezzo V,1999, Maniezzo V, Carbonaro A.,2000], the Sequential Ordering Problem (SOP)[Gambardella L. M., Dorigo M.,1997] and some other NP complete problems. It demonstrates its superiority of solving complicated combinatorial optimization problems.
But,there are still some faults in ant colony algorithm. Firstly, the diversity and stability of the solutions searched by ant colony are in conflict with convergence speed of the algorithm. The reason is that the movements of the individuals in ant colony are stochastic though they can evolve to the optimal path by interchange information, and they can hardly find a optimum one from a mass of paths within a short time when the problem scale is large enough, eyelessly accelerate the convergence speed will make the ants' local search and lead to premature and stagnation of the algorithm easily. Secondly, classical ant colony algorithm demands of discrete solution space since each ant only can selete limitedly at each step, so this algorithm is useful for discrete optimization problems such as combinational optimization problem, but not suitable for solving optimization problems with continuous space such as linear or non-linear programming problems.
In this paper, we first introduce classical ant colony algorithm and give a summary about its current research work. In chapter four, we analyze the essence of its search processe , produce four kinds of new unproved algorithms, and discuss our intending research work in this area.
The first algorithm is based on the equilibrium of ant distribution, in this method,the distribute area of ants in the interation were adjusted automaticly, and the pheromone on the trail was updated differently according the quality of the solution it constructed. The second algorithm is produced according to the sensor and consciousness behavior of ants, the optimization process was looked as three distinguished phase, and in each phase we use different optimiazation mechanism. Thus, the blindness trail selection only by pheromone was avoided successfully. The third algorithm is an improved augment ant colony optimization method.it uses the operations of crossover and mutation of GA and has higher capacity of global optimization. The fourth algorithm introduces density control mechanism in immunogenetics to adjust the distribute of ants, and the ant colony is devided into some small independent colonies using niche technology in the iteration process. The experimental results show that these four algorithms overcome the conflict between the convergence speed and solution diversity, and avoid the premature and phenominon efficiently.
In our research work, we find a noteworthy defect of basic ant colony algorithm that it is not suitable for solving continuous optimization problem. So, in chaper five, we bring forward a new novel algorithm to which crossover and mutation operation is added , and the experimental results tested on non-linear programming problems demenstrate the superiority of our method ,it shows that this algorithm is suitable for solving continus problems especially such problems with large scale.
Meanwhile,, we also make full use of the ants' capability of finding optimal solutions, applicate the ant colony algorithm to 0-1 Knapsack problem ,Weapon Target Assignment problem, Flow-Shop problem. Particularly, we produce an improved
但是，蚁群算法仍然存在一些缺陷：如在性能方面，算法的收敛速度和所得解的多样性、稳定性等性能间存在矛盾：这是因为蚁群中多个个体的运动是随机的，虽然通过信息的交流能够向着最优路径进化，但是当群体规模较大时，很难在较短时间内从复杂无章的路径中找出一条较好的路径，如果一味加快收敛速度则很可能导致蚂蚁的搜索陷入局部最优造成早熟、停滞现象。应用范围方面，蚁群算法的应用尚且局限在较小的范围中，难以处理连续空间的优化问题：由于每个蚂蚁在每个阶段所作的选择总是有限的，它要求离散的解空间，因而它对组合优化等离散优化问题很适用，而对线性和非线性规划等连续空间的优化问题的求解不能直接应用。
本文首先详细介绍了基本蚁群算法并综述了当前国内外蚁群算法的研究现状；分析了蚁群算法中蚂蚁搜索过程的本质，针对上述蚁群算法存在的问题，在第四章提出了平衡蚁群算法收敛速度解的性能之间矛盾，提高其性能的四种改进蚁群算法，并总结当前研究工作，分析相关问题，给出了我们在该方面工作的进一步研究思路。
第一种算法是基于分布均匀度的自适应蚁群算法，根据优化过程中蚂蚁的分布均匀度，动态地调整下一次迭代过程中蚂蚁分布的大致范围，同时根据不同蚂蚁选择的各条路径构成解的好坏程度有差别的自适应更新相应路径上的信息量。第二种算法模拟蚂蚁感觉和知觉行为，将蚂蚁的搜索过程分为三个阶段，在不同阶段有差别的采取不同的优化机制，成功地避免蚂蚁完全受信息量影响的“道听途说”而造成的干
扬州大学石贞{一学位论文
扰和自日选路，第三种算法是改进的增强型蚁群算法，通过增强全局(或局部)最优解
和全局(或局部_次优解的路径上的信息量浓度以及对它们进行交叉和变异操作的遗
传优化方法来改进增强型蚁群算法.第四种算法在算法中引入免疫遗传学
(i mmunogenetics)及免疫系统中的浓度控制机制，调节蚂蚁遍历过程中的信息量分布，
弓!用小生境技术(n iche)，将蚁群分化为若干小子群独立进化.实验证明这四种算法平
衡了收敛速度与解的多样性之间的矛后，有效避免了早熟和停滞现象.
在研究过程中，我们发现基本蚁群算法的一个不可忽视的应用缺陷是不太适合
求解连续性优化问题，为此在第五章，我们还提出一种用蚁群算法求解连续空间优化
问题的方法，将解空间划分成若干子域，在蚁群算法的每一次迭代中，首先根据信息量
求出解所在的子域，然后在该子域内已有的解中确定解的具体的值.实践证明，这种方
、法可推广应用到其他连续空间的优化问题之中，突破了基本蚁群算法的应用局限，为
将该算法应用于连续性优化问题提出了新的途径，
另外，我们还把蚁群算法应用于o一1背包问题，武器一目标分配问题、Flow一shoP
问题以及Qos路由问题，都获得了比较好的应用，取得了较好的效果.特别是在解决
Qos成组多播路由问题的改进蚁群算法中，不但简化了算法中参数的选取过程，还避
免了将各个度量参数的简单归一，算法能充分保证实际网络Qos需求.
在本文中，我们提出求解TSP问题的四种提高蚁群算法性能的改进算法，给出该
方面工作的进一步研究思路;同时改进基本蚁群算法结构，使其适应于求解连续优化
问题;研究其优化本质，将其应用于除TSP问题外的五种不同应用问题，大量应用实例
的实验结果证明，这些改进的蚁群算法不但加速了蚁群算法的收敛速度，提高了优化
所得解的质量，而且扩大了蚁群算法的应用范围.
Ant colony algorithm (AC) has emerged recently as a new meta-heuristic for NP-hard problems in combinatorial optimization. This meta-heuristic also includes evolutionary algorithms, neural networks, simulated annealing which all belong to the class of problem-solving strategies derived from nature. Dorigo, Maniezzo, and Colorni [Dorigo M, Maniezzo V, Colorni A., 1996], using the Traveling Salesman Problem (TSP) [Dorigo M, Gambardella L. M.,1997] as example, introduced the first AC algorithm. With the further study in this area, ant colony algorithm is widely applied to the problems of Job-shop Scheduling Problem (JSP)[ Colorni A., Dorigo M, Maniezzo V.,1994], the Quadratic Assignment Problem (QAP)[ Maniezzo V,1999, Maniezzo V, Carbonaro A.,2000], the Sequential Ordering Problem (SOP)[Gambardella L. M., Dorigo M.,1997] and some other NP complete problems. It demonstrates its superiority of solving complicated combinatorial optimization problems.
But,there are still some faults in ant colony algorithm. Firstly, the diversity and stability of the solutions searched by ant colony are in conflict with convergence speed of the algorithm. The reason is that the movements of the individuals in ant colony are stochastic though they can evolve to the optimal path by interchange information, and they can hardly find a optimum one from a mass of paths within a short time when the problem scale is large enough, eyelessly accelerate the convergence speed will make the ants' local search and lead to premature and stagnation of the algorithm easily. Secondly, classical ant colony algorithm demands of discrete solution space since each ant only can selete limitedly at each step, so this algorithm is useful for discrete optimization problems such as combinational optimization problem, but not suitable for solving optimization problems with continuous space such as linear or non-linear programming problems.
In this paper, we first introduce classical ant colony algorithm and give a summary about its current research work. In chapter four, we analyze the essence of its search processe , produce four kinds of new unproved algorithms, and discuss our intending research work in this area.
The first algorithm is based on the equilibrium of ant distribution, in this method,the distribute area of ants in the interation were adjusted automaticly, and the pheromone on the trail was updated differently according the quality of the solution it constructed. The second algorithm is produced according to the sensor and consciousness behavior of ants, the optimization process was looked as three distinguished phase, and in each phase we use different optimiazation mechanism. Thus, the blindness trail selection only by pheromone was avoided successfully. The third algorithm is an improved augment ant colony optimization method.it uses the operations of crossover and mutation of GA and has higher capacity of global optimization. The fourth algorithm introduces density control mechanism in immunogenetics to adjust the distribute of ants, and the ant colony is devided into some small independent colonies using niche technology in the iteration process. The experimental results show that these four algorithms overcome the conflict between the convergence speed and solution diversity, and avoid the premature and phenominon efficiently.
In our research work, we find a noteworthy defect of basic ant colony algorithm that it is not suitable for solving continuous optimization problem. So, in chaper five, we bring forward a new novel algorithm to which crossover and mutation operation is added , and the experimental results tested on non-linear programming problems demenstrate the superiority of our method ,it shows that this algorithm is suitable for solving continus problems especially such problems with large scale.
Meanwhile,, we also make full use of the ants' capability of finding optimal solutions, applicate the ant colony algorithm to 0-1 Knapsack problem ,Weapon Target Assignment problem, Flow-Shop problem. Particularly, we produce an improved
引文
[1] Dorigo, M., Maniezzo, V., Colorni, A. Ant system: optimization by a colony of coorperating agents. IEEE Transactions on SMC, 1996,26(1): 8～41.
[2] Dorigo, M., Gambardella, L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computing, 1997,1 (1):53～56.
[3] Colorni, A., Dorigo, M., Maniezzo, V. Ant colony system for job-shop scheduling. Belgian Journal of Operations Research Statistics and Computer Science, 1994,34(1):39-53.
[4] Maniezzo, V. Exact and approximate nonditerministic tree search procedures for the quadratic assignment problem. Informs Journal of Computer, 1999,:358～369.
[5] Maniezzo, V., Carbonaro, A. An ANTS heuristic for the frequency assignment problem. Future Generation Computer Systems, 2000, :927～935.
[6] Gambardella, L.M., Dorigo, M. HAS-SOP: an hybrid ant system for the sequential ordering problem. Technique Report, No. IDSIA 97-11, IDSIA, Lugano, Switzerland, 1997
[7] 张纪会，徐心和．带遗忘因子的蚁群算法，系统仿真学报，2000，(2)
[8] 张纪会，徐心和．具有变异特征的蚁群算法，计算机研究与发展，2000，(1)
[9] Bilchev, G., Parmee, I.C. The ant colony metaphor for searching continuous design spaces. In: Fogarty, Y., ed., Lecture Notes in Computer Science, Vol.993, New York: Springer-Verlag, 1995.25～39.
[10] 李秋霞，贺达汉，长有德，刘丽丹．蚂蚁取食行为研究概况．宁夏农学院报 2000，21(2)：94-97
[11] Marco Dorigo, Gianni Di Caro. Ant algorithms for discrete optimization. Artificial Life, 1999,5(3): 137-172
[12] M.Dorigo, V.Maniezzo, A. Colorni. Ant system: An autocatalytic optimization process. Tech Rep:91-061,1991.
[13] Walter J, Gutjahr. A Graph-based Ant System and its convergence. Future Generation Computer System[J]. 2000,16:837-888.
[14] Monarche.N, Venturini G, Slimane M. on how pachycondyla apicalis ants suggests a new algorithm. Future Generation Computer System,2000,16:937-946.
[15] Gambardella L M, Dorigo M. Solving symmetric and asymmetric TSPs by ant colonie[A]. Proc of the IEEE Conference on Evolutionary Computation[C]. [s.l]:[s.n.], 1996,622-627.
[16] Gambardella L.M. Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem.In:Proceedings of ML-95, the 12th International Conference on Machine Learning.Morgan Kaufmann: IEEE Press, 1995.252-260.
[17] Dorigo M, Luca M. The Ant-Q algorithm applied to the nuclear reload problem. Annals of Nuclear Energy,2002,29(12): 1455-1470.
[18] 智能蚂蚁系统研究．河北工业大学硕士研究生学位论文 2001，1：9-10
[19] Stützle T., Hoos H.H.. MAX-MIN Ant System. Future Generation Computer Systems Journal. 2000, 16(8):889-914.
[20] Stutzle T., Hoos H.H.. The MAX-MIN Ant System:Introdcing MAX-MIN Ant System. In proc. Int.Conf. Artificial Neural Networks and Genetic Algorithms, 1997. Springer Verlag, Wien.
[21] Stützle T., Hoos H.H. The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem. In Proc.IEEE Int.Conf. Evolut.Comp.(ICEC'97), 1997,309-314.
[22] 吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法．计算机研究与发展，1999，36(10)：1240-1245．
[23] Akihide Hiura, ToshiyaKuroda, Nobuhiro Inuzuka, etal. Cooperative behavior of various agents in dynamic environment[J]. Computers&Industrial Engineering, 1997,33(3):601-604
[24] 侯向丹．蚁群算法扩展性及应用研究．河北工业大学硕土学位论文，2002，02-081203-01M．
[25] 吴斌，史忠植．一种基于蚁群算法的TSP问题分段求解算法．计算机学报，2001，24(12)：1328-1333．
[26] Gambardella L.M, Dorigo M. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem. Informs Journal on Computing, 2000,12(3):237-255.
[27] Botee H.M.,Bonabeau E., Evolving ant colony optimization.Adv. Complex Systems, 1998,1(2): 149-159.
[28] Bilchev G., Parmee I.C. Adaptive search strategies for heavily constrained design spaces.Proceedings of 22nd International Conference on Computer Aided Design '95 Yelta: Ukraine, 1995, 230-235.
[29] 张纪会，高齐圣，徐心和．自适应蚁群算法．控制理论与应用，2000，17(1)：1-3
[30] 魏平，熊伟清．一种求解函数优化的蚁群算法．计算机科学，2002，29(9)：227-229
[31] 郝晋，石立宝，周家启．求解复杂TSP问题的随机扰动蚁群算法．系统工程理论与实践，2002，9
[32] 陈烨．带杂交算子的蚁群算法．计算机工程，2001，27(12)：74-76．
[33] 詹士昌，徐婕，吴俊．蚁群算法中有关算法参数的最优选择．科技通报，2003，19(5)：381-386．
[34] Walter J.Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002(82): 145-153.
[35] 孙焘，王秀坤，刘业欣，张名举．一种简单蚂蚁算法及其收敛性分析．2003，24(8)：1525-1527．
[36] 赵清江，邵之江，钱积新．用蚁群算法求解类TSP问题的研究．铁道运输与经济，2003，2．
[37] 赵学峰．基于蚁群算法的一类扩展型TSP研究．系统工程．2003，21(1)：17-21．
[38] 王颖，谢剑英．一种自适应蚁群算法及其仿真研究．系统仿真学报，2002，14(1)：730-733．
[39] 黄岚，王康平，周春光，原媛，庞巍．基于蚂蚁算法的混合方法求解旅行商问题．吉林大学学报．2002，40(4)：369-373．
[40] Bullnheimer B., Hartl R.F., Strauss C.. A New Rank Based Version of the Ant System-A Computational Study.Central European Journal for Operations Research and Economics, 1999,7(1):25-38.
[41] www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95.
[42] 陈录生，马剑侠．新编心理学[M]．北京：北京师范大学出版社．1996．3：53-61
[43] 叶奕乾，祝蓓里．心理学[M]．华东师范大学出版社，1996．3：84-85
[44] Dorigo M.,Gambardella L.M. A study of some properties of Ant-Q. In:Voigt H.-M, Ebeling W., Rechenberg I., Schwefel H.-S(Eds.). Proceedings of PPSN IV-Fourth International Conference on Parallet Problem Solving From Nature. Berlin:Springer-Verlag, 1996.656-665.
[45] Sheng, Jie, Chen, Ling. A new approach to solving nonlinear programming. Journal of System Science and System Engineering, 2002,11(1):28～36.
[46] Zbigniew, Michalewicz. Genetic Algorithms+Data Structures=Evolutionary Programs. 3th ed. Berlin: Springer-Verlag; Berlin Heidelberg Press, 1996. 261～262.
[47] 燕忠，袁春伟．增强型的蚁群优化算法．计算机工程与应用，2003，39(23)62-64．
[48] 陈峻，沈洁，秦玲．蚁群算法求解连续型优化问题的一种新方法．软件学报，2002，13(12)：2317-2322．
[49] 陈峻，沈洁，秦玲．基于分布均匀度的蚁群算法．软件学报，2003，14(6)：1148-1151．
[50] 林焰，郝聚民，纪卓尚，戴寅生．隔离小生境遗传算法研究．系统工程学报，2000，5(1)：86-91．
[51] Wenjian Luo, Xianbin Cao, Xufa Wang. An immune genetic algorithm based on immune regulation[A]. Proceedings of 2002 Congress on Evolutionary Computation[C]. Honolulu, Hawaii: IEEE Press,2002.801-806.
[52] 罗小平，韦巍．一种基于生物免疫遗传学的新优化方法．电子学报，2003，31(1)：59-62．
[53] Goldberg E E. Genetic algorithms in search, optimization and machine learning. Reading, MA:Addison Wesley Publishing Company,1989.
[54] 凌军，曹阳，尹建华，徐国雄，黄天赐．基于小生境技术的多样性抗体生成算法．电子学报，2003，31(8)：1130-1133．
[55] 王磊，潘进，焦李成．免疫算法．电子学报，2000，28(7)：74-78．
[56] 刘静，钟伟才，刘芳，焦立成．免疫进化聚类算法．电子学报，2001，29(12)1868-1872．
[57] 陈国良，王熙法，庄镇泉等编著．遗传算法及其应用．北京：人民邮电出版社，1999
[58] Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing problem[J]. Annals of operations Research, 1999,8(9):319-328.
[59] 崔雪丽，马良．有缺货限制的VRP蚂蚁算法研究．上海理工大学学报，2003，25(1)：39-44．
[60] A.Colorni, M.Dorigo, V.Maniezzo. An investigation of some properties of an ant algorithm, inProc. Parallel Problem Solving from Nature Conference (PPSN'92), R.Manner and B.Manderick Eds. Brussels, Belgium:Elsevi-er, 1992,pp.509-520
[61] A.Colorni, M.Dorigo, V.Maniezzo, M.Trubian. Ant system for job-shop scheduling, JORBEL-Bel-gian J.Oper.Res., Statist. Comp.Sci., 34(1):39-53
[62] V.Maniezzo, A.Colorni, M.Dorigo. Algodesk: an Experimental Comparison of Eight Evolutionary Heuristics Applied to the Quadratic Assignment Problem, European Journal of Operational Research,81,1995,188-201.
[63] 马良，蒋馥．度限制最小树的蚂蚁算法．系统工程学报，1999，14(3)：211-214．
[64] 马良，项培军．蚁群算法在组合优化问题中的应用，管理科学学报，2001，4(2)：32-37．
[65] 庄昌文，范明钰，李春辉，虞厥邦．采用面向Agent技术的并行布线系统，计算机研究与发展，1999，36(12)．
[66] 李智，许川佩，陈光(礻禹)．基于蚂蚁算法的同步时序电路初始化研究．电子测量与仪器学报，2002，16(4)：33-38．
[67] 李生红，刘泽民，周正,"ATM网上基于蚂蚁算法的VC路由选择方法”，通信学报，2000，21(1)：22-28．
[68] Sysio, M.M, et al. Discrete optimization Algorithms. Englewood Cliffs, New Jersey: Prentice-Hall, 1983,118-165.
[69] 张景中等．数学辞海，中国科学技术出版社，东南大学出版社，山西教育出版社，2002．
[70] 霍红卫，许进，保铮．基于遗传算法的0／1背包问题求解．西安电子科技大学学报，1999，26(4)493-497．
[71] 马良，王龙德．背包问题的蚂蚁优化算法．计算机应用，2001，21(8)：4-5．
[72] Chen HongJian, Chen Ling, Qing Ling, Xu Xiaohua. Application of genetic algorithm based on the strategy of gene reconfiguration. The proceedings of the
second Asian Workshop on Foundations of Software, Southeast University Press (China),2003 (1): 89 -92.
[73] Lly S P. An algorithm for the weapon-target assignment problem[J]. Defence Technique, 1991.
[74] 高尚．武器-目标分配问题的蚁群算法．计算机工程与应用，2003，3：78-79．
[75] 黄宇纯，王树青，王骥程．Flow-Shop调度问题的遗传启发算法．信号与控制，1996，25(4)：212-216．
[76] Sahasrabuddhe L H. Mukherjee B. Multicast routing algorithm and protocols: a tutorial [J]. IEEE Network, 2000,14(1):90-102
[77] WaxMan BM. Routing of multipoint connections[J]. IEEE JSAC, 1998,6(9): 1617-1622
[78] Takahashi H, Matsuyama A. An approximate solution for the Steiner problem in graphs[J]. Math Japonica,, 1980,24:573-577
[79] 余燕平，仇佩亮．一种改进的 Steiner树启发式算法．通信学报，2002，23(11)：35-40
[80] Rouskas G N, Baldine I. Multicast routing with end-to end delay variation constraints[J]. IEEE JSAC, 1997,15(3):346-356
[81] 余燕平，仇佩亮．一种时延和时延抖动受约束的启发式多播路由算法，通信学报[J]，2003，24(2)：132-137
[82] 王征应，石冰心．基于启发式遗传算法的QoS组播路由问题求解．计算机学报[J]，2001，24(1)：55-61
[83] M Parsa, Qing Zhu, J J Garcia-Luna-Aceves. An iterative algorithm for delay-constrained minimum-cost multicasting. IEEE INFOCOM'92. 2078-2085
[84] Walter J.Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002,82:145-153
[85] 王颖，谢剑英．一种自适应的蚁群算法及其仿真研究．系统仿真学报，2002，14(1)：531-533
[86] 王颖，谢剑英．一种基于蚁群系统的多点路由新算法．计算机工程[J]，2001，27(1)：55-56
[87] T Ballardie, P Francis, J Crowcroft. Core based trees(CBT)[A].Proceedings of the ACM SIGCOMM'93 Conference on Communications Architectures, Protocols and Applications[C]. San Francisco 1993:85-95
[88] Kou L, Markowsky G, Berman L. A fast algorithm for Steiner trees[J]. Acta Informatica, 1981, 15:141-145
[89] Bin Wang, Jennifer C Hou. Multicast routing and its QoS extension: Problem, algorithms and protocols[J]. IEEE Network, January/February, 2000,14(1):22-35
[90] C P Low, N Wang. An efficient algorithm for group multicast routing with bandwidth reservation[J]. Computer Communication, 2000, 23(8): 1740-1746
[91] 胡光岷，李乐民，安红岩．带宽预留的成组多播快速路由算法．电子学报[J]，2003，31(4)：569-572
[92] Maniezzo, V., Carbonaro, A. An ANTS heuristic for the frequency assignment problem. Future Generation Computer Systems, 2000, 16(8):927～935.
[93] R Schoonderwoerd, O Holland, J Bruten et al. Ant based load balancing in telecommunications networks[J]. Adaptive Behavior. 1997,5:169-207
[94] E.Bonabeau, F Henaux, S Guerin et al. Routing in telecommunications networks with smart ant-like agents[J]. Agent Word. 1998
[95] K Oida, M Sekido. ARS: an efficient agent-based routing system for QoS guarantees[J]. Computer Communications.2000,23:1437-1447
[96] Wang Z, Crowcroft J. Quality of service routing for supporting multimedia applications[J]. JSAC, 1996,14(7): 1228-1234
[97] 陈崚，秦玲，陈宏建，徐晓华．具有感觉和知觉特征的蚁群算法．系统仿真学报[JJ]，2003，15(10)
[98] 张纪会，高齐圣，徐心和．自适应蚁群算法[J]．控制理论与应用，2000，17(1)：1-3
[2] Dorigo, M., Gambardella, L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computing, 1997,1 (1):53～56.
[3] Colorni, A., Dorigo, M., Maniezzo, V. Ant colony system for job-shop scheduling. Belgian Journal of Operations Research Statistics and Computer Science, 1994,34(1):39-53.
[4] Maniezzo, V. Exact and approximate nonditerministic tree search procedures for the quadratic assignment problem. Informs Journal of Computer, 1999,:358～369.
[5] Maniezzo, V., Carbonaro, A. An ANTS heuristic for the frequency assignment problem. Future Generation Computer Systems, 2000, :927～935.
[6] Gambardella, L.M., Dorigo, M. HAS-SOP: an hybrid ant system for the sequential ordering problem. Technique Report, No. IDSIA 97-11, IDSIA, Lugano, Switzerland, 1997
[7] 张纪会，徐心和．带遗忘因子的蚁群算法，系统仿真学报，2000，(2)
[8] 张纪会，徐心和．具有变异特征的蚁群算法，计算机研究与发展，2000，(1)
[9] Bilchev, G., Parmee, I.C. The ant colony metaphor for searching continuous design spaces. In: Fogarty, Y., ed., Lecture Notes in Computer Science, Vol.993, New York: Springer-Verlag, 1995.25～39.
[10] 李秋霞，贺达汉，长有德，刘丽丹．蚂蚁取食行为研究概况．宁夏农学院报 2000，21(2)：94-97
[11] Marco Dorigo, Gianni Di Caro. Ant algorithms for discrete optimization. Artificial Life, 1999,5(3): 137-172
[12] M.Dorigo, V.Maniezzo, A. Colorni. Ant system: An autocatalytic optimization process. Tech Rep:91-061,1991.
[13] Walter J, Gutjahr. A Graph-based Ant System and its convergence. Future Generation Computer System[J]. 2000,16:837-888.
[14] Monarche.N, Venturini G, Slimane M. on how pachycondyla apicalis ants suggests a new algorithm. Future Generation Computer System,2000,16:937-946.
[15] Gambardella L M, Dorigo M. Solving symmetric and asymmetric TSPs by ant colonie[A]. Proc of the IEEE Conference on Evolutionary Computation[C]. [s.l]:[s.n.], 1996,622-627.
[16] Gambardella L.M. Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem.In:Proceedings of ML-95, the 12th International Conference on Machine Learning.Morgan Kaufmann: IEEE Press, 1995.252-260.
[17] Dorigo M, Luca M. The Ant-Q algorithm applied to the nuclear reload problem. Annals of Nuclear Energy,2002,29(12): 1455-1470.
[18] 智能蚂蚁系统研究．河北工业大学硕士研究生学位论文 2001，1：9-10
[19] Stützle T., Hoos H.H.. MAX-MIN Ant System. Future Generation Computer Systems Journal. 2000, 16(8):889-914.
[20] Stutzle T., Hoos H.H.. The MAX-MIN Ant System:Introdcing MAX-MIN Ant System. In proc. Int.Conf. Artificial Neural Networks and Genetic Algorithms, 1997. Springer Verlag, Wien.
[21] Stützle T., Hoos H.H. The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem. In Proc.IEEE Int.Conf. Evolut.Comp.(ICEC'97), 1997,309-314.
[22] 吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法．计算机研究与发展，1999，36(10)：1240-1245．
[23] Akihide Hiura, ToshiyaKuroda, Nobuhiro Inuzuka, etal. Cooperative behavior of various agents in dynamic environment[J]. Computers&Industrial Engineering, 1997,33(3):601-604
[24] 侯向丹．蚁群算法扩展性及应用研究．河北工业大学硕土学位论文，2002，02-081203-01M．
[25] 吴斌，史忠植．一种基于蚁群算法的TSP问题分段求解算法．计算机学报，2001，24(12)：1328-1333．
[26] Gambardella L.M, Dorigo M. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem. Informs Journal on Computing, 2000,12(3):237-255.
[27] Botee H.M.,Bonabeau E., Evolving ant colony optimization.Adv. Complex Systems, 1998,1(2): 149-159.
[28] Bilchev G., Parmee I.C. Adaptive search strategies for heavily constrained design spaces.Proceedings of 22nd International Conference on Computer Aided Design '95 Yelta: Ukraine, 1995, 230-235.
[29] 张纪会，高齐圣，徐心和．自适应蚁群算法．控制理论与应用，2000，17(1)：1-3
[30] 魏平，熊伟清．一种求解函数优化的蚁群算法．计算机科学，2002，29(9)：227-229
[31] 郝晋，石立宝，周家启．求解复杂TSP问题的随机扰动蚁群算法．系统工程理论与实践，2002，9
[32] 陈烨．带杂交算子的蚁群算法．计算机工程，2001，27(12)：74-76．
[33] 詹士昌，徐婕，吴俊．蚁群算法中有关算法参数的最优选择．科技通报，2003，19(5)：381-386．
[34] Walter J.Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002(82): 145-153.
[35] 孙焘，王秀坤，刘业欣，张名举．一种简单蚂蚁算法及其收敛性分析．2003，24(8)：1525-1527．
[36] 赵清江，邵之江，钱积新．用蚁群算法求解类TSP问题的研究．铁道运输与经济，2003，2．
[37] 赵学峰．基于蚁群算法的一类扩展型TSP研究．系统工程．2003，21(1)：17-21．
[38] 王颖，谢剑英．一种自适应蚁群算法及其仿真研究．系统仿真学报，2002，14(1)：730-733．
[39] 黄岚，王康平，周春光，原媛，庞巍．基于蚂蚁算法的混合方法求解旅行商问题．吉林大学学报．2002，40(4)：369-373．
[40] Bullnheimer B., Hartl R.F., Strauss C.. A New Rank Based Version of the Ant System-A Computational Study.Central European Journal for Operations Research and Economics, 1999,7(1):25-38.
[41] www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95.
[42] 陈录生，马剑侠．新编心理学[M]．北京：北京师范大学出版社．1996．3：53-61
[43] 叶奕乾，祝蓓里．心理学[M]．华东师范大学出版社，1996．3：84-85
[44] Dorigo M.,Gambardella L.M. A study of some properties of Ant-Q. In:Voigt H.-M, Ebeling W., Rechenberg I., Schwefel H.-S(Eds.). Proceedings of PPSN IV-Fourth International Conference on Parallet Problem Solving From Nature. Berlin:Springer-Verlag, 1996.656-665.
[45] Sheng, Jie, Chen, Ling. A new approach to solving nonlinear programming. Journal of System Science and System Engineering, 2002,11(1):28～36.
[46] Zbigniew, Michalewicz. Genetic Algorithms+Data Structures=Evolutionary Programs. 3th ed. Berlin: Springer-Verlag; Berlin Heidelberg Press, 1996. 261～262.
[47] 燕忠，袁春伟．增强型的蚁群优化算法．计算机工程与应用，2003，39(23)62-64．
[48] 陈峻，沈洁，秦玲．蚁群算法求解连续型优化问题的一种新方法．软件学报，2002，13(12)：2317-2322．
[49] 陈峻，沈洁，秦玲．基于分布均匀度的蚁群算法．软件学报，2003，14(6)：1148-1151．
[50] 林焰，郝聚民，纪卓尚，戴寅生．隔离小生境遗传算法研究．系统工程学报，2000，5(1)：86-91．
[51] Wenjian Luo, Xianbin Cao, Xufa Wang. An immune genetic algorithm based on immune regulation[A]. Proceedings of 2002 Congress on Evolutionary Computation[C]. Honolulu, Hawaii: IEEE Press,2002.801-806.
[52] 罗小平，韦巍．一种基于生物免疫遗传学的新优化方法．电子学报，2003，31(1)：59-62．
[53] Goldberg E E. Genetic algorithms in search, optimization and machine learning. Reading, MA:Addison Wesley Publishing Company,1989.
[54] 凌军，曹阳，尹建华，徐国雄，黄天赐．基于小生境技术的多样性抗体生成算法．电子学报，2003，31(8)：1130-1133．
[55] 王磊，潘进，焦李成．免疫算法．电子学报，2000，28(7)：74-78．
[56] 刘静，钟伟才，刘芳，焦立成．免疫进化聚类算法．电子学报，2001，29(12)1868-1872．
[57] 陈国良，王熙法，庄镇泉等编著．遗传算法及其应用．北京：人民邮电出版社，1999
[58] Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing problem[J]. Annals of operations Research, 1999,8(9):319-328.
[59] 崔雪丽，马良．有缺货限制的VRP蚂蚁算法研究．上海理工大学学报，2003，25(1)：39-44．
[60] A.Colorni, M.Dorigo, V.Maniezzo. An investigation of some properties of an ant algorithm, inProc. Parallel Problem Solving from Nature Conference (PPSN'92), R.Manner and B.Manderick Eds. Brussels, Belgium:Elsevi-er, 1992,pp.509-520
[61] A.Colorni, M.Dorigo, V.Maniezzo, M.Trubian. Ant system for job-shop scheduling, JORBEL-Bel-gian J.Oper.Res., Statist. Comp.Sci., 34(1):39-53
[62] V.Maniezzo, A.Colorni, M.Dorigo. Algodesk: an Experimental Comparison of Eight Evolutionary Heuristics Applied to the Quadratic Assignment Problem, European Journal of Operational Research,81,1995,188-201.
[63] 马良，蒋馥．度限制最小树的蚂蚁算法．系统工程学报，1999，14(3)：211-214．
[64] 马良，项培军．蚁群算法在组合优化问题中的应用，管理科学学报，2001，4(2)：32-37．
[65] 庄昌文，范明钰，李春辉，虞厥邦．采用面向Agent技术的并行布线系统，计算机研究与发展，1999，36(12)．
[66] 李智，许川佩，陈光(礻禹)．基于蚂蚁算法的同步时序电路初始化研究．电子测量与仪器学报，2002，16(4)：33-38．
[67] 李生红，刘泽民，周正,"ATM网上基于蚂蚁算法的VC路由选择方法”，通信学报，2000，21(1)：22-28．
[68] Sysio, M.M, et al. Discrete optimization Algorithms. Englewood Cliffs, New Jersey: Prentice-Hall, 1983,118-165.
[69] 张景中等．数学辞海，中国科学技术出版社，东南大学出版社，山西教育出版社，2002．
[70] 霍红卫，许进，保铮．基于遗传算法的0／1背包问题求解．西安电子科技大学学报，1999，26(4)493-497．
[71] 马良，王龙德．背包问题的蚂蚁优化算法．计算机应用，2001，21(8)：4-5．
[72] Chen HongJian, Chen Ling, Qing Ling, Xu Xiaohua. Application of genetic algorithm based on the strategy of gene reconfiguration. The proceedings of the
second Asian Workshop on Foundations of Software, Southeast University Press (China),2003 (1): 89 -92.
[73] Lly S P. An algorithm for the weapon-target assignment problem[J]. Defence Technique, 1991.
[74] 高尚．武器-目标分配问题的蚁群算法．计算机工程与应用，2003，3：78-79．
[75] 黄宇纯，王树青，王骥程．Flow-Shop调度问题的遗传启发算法．信号与控制，1996，25(4)：212-216．
[76] Sahasrabuddhe L H. Mukherjee B. Multicast routing algorithm and protocols: a tutorial [J]. IEEE Network, 2000,14(1):90-102
[77] WaxMan BM. Routing of multipoint connections[J]. IEEE JSAC, 1998,6(9): 1617-1622
[78] Takahashi H, Matsuyama A. An approximate solution for the Steiner problem in graphs[J]. Math Japonica,, 1980,24:573-577
[79] 余燕平，仇佩亮．一种改进的 Steiner树启发式算法．通信学报，2002，23(11)：35-40
[80] Rouskas G N, Baldine I. Multicast routing with end-to end delay variation constraints[J]. IEEE JSAC, 1997,15(3):346-356
[81] 余燕平，仇佩亮．一种时延和时延抖动受约束的启发式多播路由算法，通信学报[J]，2003，24(2)：132-137
[82] 王征应，石冰心．基于启发式遗传算法的QoS组播路由问题求解．计算机学报[J]，2001，24(1)：55-61
[83] M Parsa, Qing Zhu, J J Garcia-Luna-Aceves. An iterative algorithm for delay-constrained minimum-cost multicasting. IEEE INFOCOM'92. 2078-2085
[84] Walter J.Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002,82:145-153
[85] 王颖，谢剑英．一种自适应的蚁群算法及其仿真研究．系统仿真学报，2002，14(1)：531-533
[86] 王颖，谢剑英．一种基于蚁群系统的多点路由新算法．计算机工程[J]，2001，27(1)：55-56
[87] T Ballardie, P Francis, J Crowcroft. Core based trees(CBT)[A].Proceedings of the ACM SIGCOMM'93 Conference on Communications Architectures, Protocols and Applications[C]. San Francisco 1993:85-95
[88] Kou L, Markowsky G, Berman L. A fast algorithm for Steiner trees[J]. Acta Informatica, 1981, 15:141-145
[89] Bin Wang, Jennifer C Hou. Multicast routing and its QoS extension: Problem, algorithms and protocols[J]. IEEE Network, January/February, 2000,14(1):22-35
[90] C P Low, N Wang. An efficient algorithm for group multicast routing with bandwidth reservation[J]. Computer Communication, 2000, 23(8): 1740-1746
[91] 胡光岷，李乐民，安红岩．带宽预留的成组多播快速路由算法．电子学报[J]，2003，31(4)：569-572
[92] Maniezzo, V., Carbonaro, A. An ANTS heuristic for the frequency assignment problem. Future Generation Computer Systems, 2000, 16(8):927～935.
[93] R Schoonderwoerd, O Holland, J Bruten et al. Ant based load balancing in telecommunications networks[J]. Adaptive Behavior. 1997,5:169-207
[94] E.Bonabeau, F Henaux, S Guerin et al. Routing in telecommunications networks with smart ant-like agents[J]. Agent Word. 1998
[95] K Oida, M Sekido. ARS: an efficient agent-based routing system for QoS guarantees[J]. Computer Communications.2000,23:1437-1447
[96] Wang Z, Crowcroft J. Quality of service routing for supporting multimedia applications[J]. JSAC, 1996,14(7): 1228-1234
[97] 陈崚，秦玲，陈宏建，徐晓华．具有感觉和知觉特征的蚁群算法．系统仿真学报[JJ]，2003，15(10)
[98] 张纪会，高齐圣，徐心和．自适应蚁群算法[J]．控制理论与应用，2000，17(1)：1-3