蚁群优化算法及在网络路由中的应用研究
|
摘要
蚂蚁具有找到蚁穴与食物源之间最短路径的能力,受此启发提出的蚁群算法最初用于解决旅行商问题,具有自适应性、鲁棒性及本质上的并行性等许多特点,广泛适用于各种静态和动态的组合优化问题中,具有潜在的应用前景。
由Dorigo等提出的蚁群算法的描述可知,在通用启发式蚁群算法的起始阶段,信息素值被初始化为统一的值,对解的搜索没有指导意义,启发值此时反而能够提供有用的局部信息,有助于算法的快速收敛。随着算法的进行,根据搜索到的不同路径而更新的信息素值,存储了解空间的全局最优解信息,相对于启发值而言,所起的作用不断提高。因此设计了一种自适应的启发值因子,能够随着算法的进行调整信息素值和启发值之间的相对权重,加速算法的收敛速度。
网络路由问题所具有的一些特征,如内部信息、分布计算、随机动态,以及异步的网络状态更新等,与蚁群优化算法的特征匹配得很好,能很好地解决这一问题。本论文的另一个主要研究成果就是在蚁群优化的基础上,提出了新的路由算法。这种算法具有本质上的可扩展性,能有效解决大型通信网络资源的分配问题。整个算法应用概率选择数据包转发的路径,能够充分利用多条可行路径,从而提高网络负载的均衡性、鲁棒性、负载流量以及网络的利用率。
本文以基于图论的蚁群算法为基础,给出了蚁群算法的一般性模型,讨论了其收敛性及在静态TSP和动态网络路由问题中的应用,主要工作内容有:
第一章给出了蚁群算法的描述和在静态、动态情况下的各类应用,并指出蚁群算法所具有的分布式计算、鲁棒性、应用简单等特点,以及蚁群算法潜在的广泛应用前景。
第二章分析了蚁群算法的基本原理,针对蚁群算法所能解决的问题
A general-purpose metaheuristic named Ant Colony Optimization algorithm, which take inspiration from real ant's behavior in finding shortest paths using as information only the trail of a chemical substance (called pheromone) deposited by other ants, boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, and have recently been successfully applied to several discrete optimization problems. In all these algorithms a set of artificial ants collectively solve the problem under consideration through a cooperative effort. This effort is mediated by indirect communication of information on the problem structure the ants concurrently collect while building solutions by using a stochastic policy. The details were studied as follows:In the first chapter of this paper, the definition, taxonomy and characteristics of the routing problem are reported. The routing problem is a stochastic distributed multi-objective problem. Information propagation delays, and the difficulty to completely characterize the network dynamics under arbitrary traffic patterns, make the general routing problem intrinsically distributed. Routing decision can only be made on the basis of local and approximate information about the current and the future network states. These features make the problem well suited for Ant Colony Optimization algorithm.The second chapter presents a formal definition of graphs and the theory of ant algorithms, self-organization and the Ant Colony Optimization metaheuristic. The pheromone-based parameterized probabilistic model for the ACO algorithm is presented as the solution construction graph that the combinatorial optimization problem can be mapped on. Based on the solution construction graph, the unified framework of the ACO algorithm is presented. And this paper proposed several extensions of the Ant System that was the prototype of the ant algorithms. All these extensions were in some sense "greedier" than Ant System, but differ significantly in main aspects of the search control.In the third chapter, the solution of a metaheuristic following the ant colony optimization paradigm, the graph-based ant system, converge with a probability that can be made arbitrarily close to unity to one element of the set of optimal solutions.The 4~(th) chapter introduces an Enhance Ant-Q, a family of algorithms that present
many similarities with Q-learning. In initialization phase, a same value is given to pheromone trail, so in the early stages of the computation the use of the heuristic improves the performance and pheromone trail have no special meaning. As computation goes on, pheromone trail become more and more useful to direct agents in finding good solutions. Thus we apply a non-linearity parameter to weigh more importance of the heuristic values than pheromone trail in the first iterations. The results obtained by Enhance Ant-Q are competitive with those obtained by other heuristic approaches.The 5~(th) chapter presents a distributed algorithm based on the self-organized capacity of ants for routing and load balancing in dynamic communication networks. Agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. The algorithms' performance is shown to significantly improve the network's relaxation and its response to perturbations.The 6~(th) chapter describes an adaptive swarm-based routing algorithm inspired by the social behavior of ants which boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, which are well suited for routing in modern communication networks. The algorithm increases convergence speed, reduces routing instabilities and oscillations by using a novel variation of reinforcement learning and a technique called momentum. We run many experiments over real IP datagram networks and under several traffic distributions. Results are very encouraging.In the 7~(th) chapter all of the work in this dissertation was summed up, and the future researches in this area were prospected.
由Dorigo等提出的蚁群算法的描述可知,在通用启发式蚁群算法的起始阶段,信息素值被初始化为统一的值,对解的搜索没有指导意义,启发值此时反而能够提供有用的局部信息,有助于算法的快速收敛。随着算法的进行,根据搜索到的不同路径而更新的信息素值,存储了解空间的全局最优解信息,相对于启发值而言,所起的作用不断提高。因此设计了一种自适应的启发值因子,能够随着算法的进行调整信息素值和启发值之间的相对权重,加速算法的收敛速度。
网络路由问题所具有的一些特征,如内部信息、分布计算、随机动态,以及异步的网络状态更新等,与蚁群优化算法的特征匹配得很好,能很好地解决这一问题。本论文的另一个主要研究成果就是在蚁群优化的基础上,提出了新的路由算法。这种算法具有本质上的可扩展性,能有效解决大型通信网络资源的分配问题。整个算法应用概率选择数据包转发的路径,能够充分利用多条可行路径,从而提高网络负载的均衡性、鲁棒性、负载流量以及网络的利用率。
本文以基于图论的蚁群算法为基础,给出了蚁群算法的一般性模型,讨论了其收敛性及在静态TSP和动态网络路由问题中的应用,主要工作内容有:
第一章给出了蚁群算法的描述和在静态、动态情况下的各类应用,并指出蚁群算法所具有的分布式计算、鲁棒性、应用简单等特点,以及蚁群算法潜在的广泛应用前景。
第二章分析了蚁群算法的基本原理,针对蚁群算法所能解决的问题
A general-purpose metaheuristic named Ant Colony Optimization algorithm, which take inspiration from real ant's behavior in finding shortest paths using as information only the trail of a chemical substance (called pheromone) deposited by other ants, boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, and have recently been successfully applied to several discrete optimization problems. In all these algorithms a set of artificial ants collectively solve the problem under consideration through a cooperative effort. This effort is mediated by indirect communication of information on the problem structure the ants concurrently collect while building solutions by using a stochastic policy. The details were studied as follows:In the first chapter of this paper, the definition, taxonomy and characteristics of the routing problem are reported. The routing problem is a stochastic distributed multi-objective problem. Information propagation delays, and the difficulty to completely characterize the network dynamics under arbitrary traffic patterns, make the general routing problem intrinsically distributed. Routing decision can only be made on the basis of local and approximate information about the current and the future network states. These features make the problem well suited for Ant Colony Optimization algorithm.The second chapter presents a formal definition of graphs and the theory of ant algorithms, self-organization and the Ant Colony Optimization metaheuristic. The pheromone-based parameterized probabilistic model for the ACO algorithm is presented as the solution construction graph that the combinatorial optimization problem can be mapped on. Based on the solution construction graph, the unified framework of the ACO algorithm is presented. And this paper proposed several extensions of the Ant System that was the prototype of the ant algorithms. All these extensions were in some sense "greedier" than Ant System, but differ significantly in main aspects of the search control.In the third chapter, the solution of a metaheuristic following the ant colony optimization paradigm, the graph-based ant system, converge with a probability that can be made arbitrarily close to unity to one element of the set of optimal solutions.The 4~(th) chapter introduces an Enhance Ant-Q, a family of algorithms that present
many similarities with Q-learning. In initialization phase, a same value is given to pheromone trail, so in the early stages of the computation the use of the heuristic improves the performance and pheromone trail have no special meaning. As computation goes on, pheromone trail become more and more useful to direct agents in finding good solutions. Thus we apply a non-linearity parameter to weigh more importance of the heuristic values than pheromone trail in the first iterations. The results obtained by Enhance Ant-Q are competitive with those obtained by other heuristic approaches.The 5~(th) chapter presents a distributed algorithm based on the self-organized capacity of ants for routing and load balancing in dynamic communication networks. Agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. The algorithms' performance is shown to significantly improve the network's relaxation and its response to perturbations.The 6~(th) chapter describes an adaptive swarm-based routing algorithm inspired by the social behavior of ants which boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, which are well suited for routing in modern communication networks. The algorithm increases convergence speed, reduces routing instabilities and oscillations by using a novel variation of reinforcement learning and a technique called momentum. We run many experiments over real IP datagram networks and under several traffic distributions. Results are very encouraging.In the 7~(th) chapter all of the work in this dissertation was summed up, and the future researches in this area were prospected.
引文
[1] T.Stiitzie and M. Dorigo, ACO Algorithms for the Quadratic Assignment Problem. New Methods in Optimization Mc Graw-Hill, 1999.
[2] A. Colorni and M. Dorigo, Ant System for Job-shop Scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), 1994.34(39).
[3] B. Bullnheimer, An Improved ant System Algorithm for the Vehicle Routing Problem. Technical Report POM-10/97. Institute of Management Science, University of Vienna, 1997.
[4] B. Bullnheimer, Applying the ant System to the Vehicle Routing Problem. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, 1998.
[5] R.M. Gambardella and M. Dorigo, An hybrid ant system for the sequential ordering problem, technical Report, IDSIA, Lugano, CH, 1997.
[6] R. Schoonderwoerd, O. Holland, and J. Bruten, Ant-like agents for load balancing in telecommunications networks. In proceedings of the First International Conference on Autonomous Agents, 1997: p. 209-216.
[7] R. Schoonderwoerd, O. Holland, and j. Bruten, ant-based load balancing in telecommunications networks. Adaptive Behavior, 1996. 5(2): p. 169-207.
[8] E. Bonabeau, et al., Routing in telecommunication networks with "smart" ant-like agents for telecommunication applications. Lectures Notes in AI, 1998. 1437.
[9] R. van der Put, Routing in the faxfactory using mobile agents, technical Report R&D-SW-98-276 KPN Research, 1998.
[10] R.van der Put and L. Rothkrantz, Routing in packet switched networks using agents. Simulation Practice and Theory, 1999.
[11] Dorigo, M., Optimization, Learning and Natural Algorithms. Ph.D. thesis, 1992.
[12] Dorigo, M. and L. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem problem. IEEE Transactions on Evolutionary Computation, 1997. 1(1): p. 53-66.
[13] Dorigo, M., V. Maniezzo, and A. Colorni, The ant system: an autocatalytic optimization process. Tech. rep. 91-016 Politecnico di Milano, Dipartimento di Elettronica ed Informatic, 1991.
[14] Dorigo, M., V. Maniezzo, and A. Colorni, The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-PartB, 1996. 26(1): p. 29-41.
[15] Schoonderwoed, R., et al., Load balancing in telecommunications networks. Adaptive Behavior, 1997.5(2).
[16] Dorigo, M. and G. Di Caro, Ant algorithms for discrete opetimization. Artificial Life, 1999. 5(3): p. 137-172.
[17] Di Caro, G. and M. Dorigo, Extending Antnet for best-effort Qualty-of-Service Routing. ANTS'98-From Ant Colonies to artificial Ants: First International Workshop on ant colony optimization, 1998.
[18] Kuntz, P., P. Layzell, and D. Snyers, A colony of ant-like agents for partitioning in VLSI technology. Proc. of the 4th European Conf. On Artificial Life., 1997: p. 417-424.
[ 19] Song, Y.H., Combined heat and power economic dispatch by improved ant colony search algorithm. Electric Power System Research, 1999. 52: p. 115-121.
[20] Chang, C.S., A new approach to fault section estimation in power systems using ant system. Electric Power System Research, 1999. 49: p. 63-70.
[21 ] Cordon, O., F. Herrera, and L. Sanchez, Solving Electrical distribution problems using Hybrid evolutionary data analysis techniques. Applied Intelligence, 1999. 10: p. 251-270.
[22] Maniezzo, V., An ANTS heuristic for the frequency assignment problem. Antonella Carbonaro Future Generation Computer Systems, 2000. 16: p. 927-935.
[23] Navarro Varela, G. and M.C. Sinclair. Ant colony optimisation for virtual-wavelength-path routing and wavelength allocation, in Proc. 1999 Congress on Evolutionary Computation. 1999. Washington DC, USA.
[24] Bullnheimer, B., R.F. Hartl, and Strauss.C, An improved ant system algorithm for the vehicle routing problem. Technical Report POM-10/97, Institute of Management Science, University of Vienna, 1997.
[25] Brelaz, D., New methods to color vertices of a graph. Communications of the ACM, 1979. 22: p.251-256.
[26] Costa, D. and A. Hertz., Ants can colour graphs. Journal of the Operational Research
Society, 1997. 48: p. 295-305.
[27] Costa, D., A. Hertz, and Dubuis.O., Embedding of a sequential algorithm within an evolutionary algorithm for coloring problems in graphs. Journal of Heuristics, 1995. 1:p. 105-128.
[28] COSTA, D. and A. HERTZ, Ants Can Colour Graphs. Journal of the Operational Research Society, 1997. 48: p. 295-305.
[29] Gallager, R., Discrete Stochastic Processes. Kluwer Academic Publishers, Dordrecht, 1996.
[30] Feo, T.A. and M.G.C. Resends, Greedy Randomized Adaptive Search Procedures. J Global Optimization, 1995. 6: p. 109-133.
[31 ] Dorigo, M. and L. Gambardella, ant colonies for the traveling salesman problem. BioSystems, 1997. 43: p. 73-81.
[32] Bullnheimer, B., R.F. Hartl, and C. Strauss, A new rank-based version of the ant system: a computational study. Technical Report POM-03/97, Institute of Management Science, University of Vienna, 1997.
[33] Chen, K., A simple learning algorithm for the traveling salesman problem. Physical Review E, 1997.
[34] Colorni, A., M. Dorigo, and Maniezzo.V., Distributed optimization by ant colonies. In Proceedings of the First European Conference on Artificial Life, 1992: p. 134-142.
[35] Gambardella, L.M. and M. Dorigo, Solving symmetric and asymmetric TSPs by ant colonies. In Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96, 1996: p. 622-627.
[36] Johnson, D.S. and L.A. McGeoch, The traveling salesman problem: A case study. In E.H. Aarts and J. K. Lenstra, editors, In Local Search in Combinatorial Optimization, 1997: p. 215-310.
[37] Colorni, A., Ant system for Job-shop Sheduling. JORBEL, 1994. 34(1): p. 39-53.
[38] Bullnheimer, B., G. Kotsis, and Strauss.C, Parallelization strategies for the ant system. Technical Report POM 9-97, Institute of Management Science, University of Vienna, 1997.
[39] Gambardella, L.M., E.D. Taillard, and M. Dorigo, Ant colonies for the QAP. Technical Report 4-97, IDSIA, Lugano, Switzerland, 1997.
[40] Maniezzo, V. and A. Colorni, The ant system applied to the quadratic assignment problem. IEEE Trans. Knowledge and Data Engineering, 1999.
[41] Maniezzo, V., A. Colorni, and M. Dorigo, The ant system applied to the quadratic assignment problem. Technical Report IRIDIA/94-28, Universit'e Libre de Bruxelles, Belgium, 1994.
[42] Stutzle, T., MAX-MIN ant system for the quadratic assignment problem. Technical Report AIDA-97-4, FG Intellektik, TU Darmstadt, 1997.
[43] Taillard, E., Comparison of Iterative Search for the Quadratic Assignment Problem. Location Science, 1995.3: p. 87-103.
[44] Bullnheimer, B., R.F. Hartl, and Strauss.C, Applying the ant system to the vehicle routing problem. In I. H. Osman S. Voβ, S. Martello and C. Roucairol, editors,Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 109-120. Kluwer Academics, 1998.
[45] Colorni, A., et al., Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 1994.34: p. 39-53.
[46] Di Caro, G. and M. Dorigo, An adaptive multi-agent routing algorithm inspired by ants behavior. In Proceedings of PART98-5th Annual Australasian Conference on Parallel and Real-Time Systems, 1998: p. 261-272.
[47] Di Caro, G. and M. Dorigo, Ant colonies for adaptive routing in packet-switched communications networks. In A. E. Eiben, T. Back, M. Schoenauer, and H.-P.Schwefel, editors, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, 1998: p. 673-682.
[48] Di Caro, G. and M. Dorigo, Extending AntNet for best-effort Quality-of-Service routing. http://iridia.ulb.ac.be/ants98/ants98.html, October 15-16, 1998.
[49] Di Caro, G. and M. Dorigo, Two ant colony algorithms for best-effort routing in datagram networks. In Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems, 1998: p. 541-546.
[50] Heusse, M., et al., Adaptive agent-driven routing and load balancing in communication networks. Technical Report RR-98001-1ASC, Department Intelligence Artificielle et Sciences Cognitives, ENST Bretagne, 1998.
[51] Witten, I.H., An adaptive optimal controller for discrete-time Markov environments. Information and Control, 1997.34: p. 286-295.
[52] Grasse, P.P., La reconstruction du nid et les coordiniations interindividuelles chez bellicositermes natalensis et cubitermes sp. La theorie de la stigmergic: essai d'interpretation du comportement des termites constru teurs. Insectes Sociaux, 1959. 6: p. 41-81.
[53] Raiha, K.-J. and E. Ukkonen, The shortest common supersequence problem over binary alphabet is NP-complete. Theoretical Computer Science, 1981. 16: p. 187-198.
[54] Dorigo, M., The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on System, Man, and Cybernetics-part B, 1996.26(1): p. 1-13.
[55] Bullnheimer, B., R.F. Hartl, and Strauss.C., A new rank-based version of the ant system." a computational study. Technical Report POM-03/97, Institute of Management Science, University of Vienna, 1997.
[56] Stutzle, T. and H. Hoos, The MAX-MIN ant system and local search for the traveling salesman problem. In T. Baeck, Z. Michalewicz, and X. Yao, editors, Proceedings of IEEE-ICEC-EPS (?) 97, IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference, 1997: p. 309-314.
[57] Stutzle, T. and H. Hoes, Improvements on the ant system: Introducing MAX-MIN ant system. In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, 1997: p. 245-249.
[58] Stutzle, T. and H. Hoos, MAX-MIN Ant system and local search for combinatorial optimization problems. In S. Voβ, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization: p. 137-154.
[59] Dorigo, M. and L.M. Gambardella, A study of some properties of Ant-Q. In Proceedings of PPSN-Ⅳ, Fourth International Conference on Parallel Problem Solving From Nature, 1996: p. 656-665.
[60] Gambardella, L.M. and M. Dorigo, Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. Proc. of ML-95, Twelfth Intern. Conf. on Machine Learning, 1995: p. 252-260.
[61] Blum, C., A. Roli, and M. Dorigo. HC-ACO: The hyper-cube framework for Ant Colony Optimization. in In Proceedings of MIC (?) 2001 Meta heuristics International Conference. 2001.
[62] Gutjahr, W.J., A graph{based Ant System and its convergence. Future Generation Computer Systems, 2000. 16(8): p. 873-882.
[63] Kaelbling, L.R, M.L. Littman, and A.W. Moore, Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 1996.4: p. 237-285.
[64] Durbin, R. and D. Willshaw, An analogue approach to the travelling salesman problem using an elastic net method. Nature, 1987. 326: p. 689-691.
[65] Whitley, D., T. Starkweather, and D. Fuquay. Scheduling problems and travelling salesman: the genetic edge recombination operator, in Proceedings of the Third International Conference on Genetic Algorithms. 1989. Morgan Kaufmann.
[66] Reinelt, G., The traveling salesman: Computational solutions for TSP applications. Springer- Verlag, 1994.
[67] Fogel, D., Applying evolutionary programming to selected traveling salesman problems. Cybernetics and Systems: An International, 1993. 24: p. 27-36.
[68] Bersini, H., C. Oury, and M. Dorigo, Hybridization of genetic algorithms. Tech. Rep. No. IRIDIA/95-22, IRIDIA, University libre de Bruxelles, Belgium, 1995.
[69] Lin, F.-T., C.-Y. Kao, and C.-C. Hsu, Applying the genetic approach to simulated annealing in solving some NP-hard problems. IEEE Transactions on System, Man, and Cybernetics, 1993. 23: p. 1752-1767.
[70] Borthick, s., Today's internet can't scale. Business Communication Review, Mayt 2001.
[71] Bonabeau, E., et al., Routing in telecommunication networks with (?) Smart(?) ant-like agents telecommunication applications. In Proceedings of IATA メ 98, Second Int. Workshop on Intelligent Agents for Telecommunication Applications., 1998. 1437.
[72] White, T., B. Pagurek, and F. Oppacher, Connection management using adaptive mobile agents, agents. In H.R. Arabnia, editor, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1998: p. 802-809.
[73] Schoonderwoerd, R., O. Holland, and J. Bruten, Ant-like agents for load balancing in telecommunications networks. Hewlett-Packard Laboratories, Bristol-England, 1997.
[74] Bieszczad, A., B. Pagurek, and T. White, Mobile agents for network management. IEEE Communication Surveys, 1998. 1(1).
[75] White, T., Swarm intelligence and problem solving in telecommunications. Canadian Artificial Intelligence Magazine, 1997.
[76] White, T., Routing with swarm intelligence. Technical Report SCE-97-15, Systems and Computer Engineering Department, Carleton University, September 1997.
[77] White, T. and B. Pagurek, Towards multi-swarm problem solving in networks. Proc. 3rd Intl. Conf. on Multi-Agent Systems (ICMAS '98), July 1998: p. 333-340.
[78] White, T., B. Pagurek, and F. Oppacher, ASGA: improving the ant system by integration with genetic algorithms. Proc. 3rd Genetic Programming Conference, July 1998: p. 610-617.
[79] White, T., B. Pagurek, and F. Oppacher, Ant search with genetic algorithms: application to path finding in networks. Combinatorial Optimization '98, Brussels, Belgium, April 15-17 1998.
[80] Baran, B. and R. Sosa, AntNet routing algorithm for data networks based on mobile agents. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial, 2001. 12: p. 75-84.
[81] Schoonderwoerd, R., et al., Ant-based load balancing in telecommunication networks. Adaptive Behavior, 1996. 5(2): p. 169-207.
[82] Di Caro, G. and M. Dorigo, AntNet: a mobile agents approach to adaptive routing. Tech. Rep. IRID1A/97-12, IR1DIA, Universite Libre de Bruxelles, Belgium, 1997.
[83] Subramanian, D., Ants and reinforcement learning: a case study in routing in dynamic networks. In Proceedings of IJCA1-97, International Joint Conference on Artificial Intelligence, 1997: p. 832-838.
[84] Dorigo, M., Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di MilanoIT, 1991.
[85] Colorni, A., Distributed optimization by ant colonies. In Proceedings of ECAL91-European Conference on Artificial Life, 1991: p. 134-142.
[86] Feit, S., TCP/IP. Architecture, Protocols and Implementation. McGraw & Hill, 1996.
[87] Boyan, J.A. and M.L. Littman, Packet routing in dynamically changing networks: A reinforcement approach. In Advances in Neural Information Processing Systems, 1994. 6: p. 671-678.
[88] Choi, S. and D.Y. Yeung, Predictive Q-routing: A memory-based reinforcement learning approach to adaptive traffic control. In Advances in Neural Information Processing Systems, 1996. 8: p. 945-951.
[89] Di Caro, G. and M. Dorigo, AntNet: a mobile agents approach to adaptive routing. ech. Rep. IRIDIA/97-12, IRIDIA, Universite Libre de Bruxelles, Belgium, 1997.
[90] Sandick, H. and E. Crawley, QoS Routing Working Group Report. Internet Draft, Internet Engineering Task Force, 1997.
[91] Walrand, J. and J. Crowcroft, High-performance Communication Networks. Morgan Kaufmann, 1996.
[92] Dorigo, M., Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano,IT., 1991.
[93] Goss, S., et al., Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 1989.76: p. 579-581.
[94] Beckers, R., J.L. Deneubourg, and S. Goss, Trails and U-turns in the selection of the shortest path by the ant Lasius Niger. Journal of Theoretical Biology, 1992. 159(397-415).
[95] Dorigo, M. and L.M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997. 1(1): p. 53-66.
[96] Gambardella, L.M., Ant-Q: A reinforcement learning approach to the traveling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, 1995: p. 252-260.
[97] Colorni, A. and M. Dorigo, Distributed optimization by ant colonies. In Proceedings of ECAL91-European Conference on Artificial Life, 1991: p. 134-142.
[98] Stutzle, T. and M. Dorigo, ACO algorithms for the quadratic assignment problem. New Ideas in Optimization, McGraw-Hill, 1999.
[99] Taillard, E.D. and L.M. Gambardella, Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research, 2000(135): p. 1-16.
[100] Dorigo, M., Ant algorithms for discrete optimization. Artificial Life, 1999.3(5): p. 137-172.
[101] Maniezzo, V., Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. Technical Report CSR98-1, Scienze dell'Informazione, Universit?di Bologa, Sede di Cesena, 1998.
[102] Gambardella, L., HAS-SOP: Hybrid ant system for the sequential ordering problem. Technical Report IDSIA 11-97, IDSIA, Lugano, Switzerland, 1997.
[103] Colorni, A. and M. Dorigo, Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 1994.34(1): p. 39-53.
[104] Dorigo, M., Ant algorithms and stigmergy. Future Generation Computer System. 2000(16): p. 851-871.
[105] 阎平凡 and 张长水,人工神经网络与模拟进化计算.清华大学出版社,2000.
[106] 王永骥 and 涂健,神经元网络控制.机械工业出版社,1998.
[107] McQuillan, J.M., I. Richer, and E. Rosen, C., The new routing algorithm for the ARPANET. IEEE Transactions on Communications, 1980. 28(711-719).
[108] Khanna, A. and J. Zinky, The revised ARPANET routing metric. ACM SIGCOMM Computer Communication Review, 1989. 19(4): p. 45-56.
[109] Singh, S.P., T. Jaakkola, and M.I. Jordan. Learning without state estimation in partially observable Markovian decision processes, in In Proceedings of Eleventh Machine Learning Conference. 1994. New Brunswick, NJ:Morgan Kaufmann.
[110] Rubistein, R.Y., Simulation and the Monte Carlo Method. John Wiley & Sons, 1981.
[111] Bak, S., J. Cobb, and E. Leiss, Load Balancing Routing via Randomization. XXV Informatic Latinoamerican Conf.-CLEI, Asuncion-Paraguay, 1999: p. 999-1010.
[2] A. Colorni and M. Dorigo, Ant System for Job-shop Scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), 1994.34(39).
[3] B. Bullnheimer, An Improved ant System Algorithm for the Vehicle Routing Problem. Technical Report POM-10/97. Institute of Management Science, University of Vienna, 1997.
[4] B. Bullnheimer, Applying the ant System to the Vehicle Routing Problem. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, 1998.
[5] R.M. Gambardella and M. Dorigo, An hybrid ant system for the sequential ordering problem, technical Report, IDSIA, Lugano, CH, 1997.
[6] R. Schoonderwoerd, O. Holland, and J. Bruten, Ant-like agents for load balancing in telecommunications networks. In proceedings of the First International Conference on Autonomous Agents, 1997: p. 209-216.
[7] R. Schoonderwoerd, O. Holland, and j. Bruten, ant-based load balancing in telecommunications networks. Adaptive Behavior, 1996. 5(2): p. 169-207.
[8] E. Bonabeau, et al., Routing in telecommunication networks with "smart" ant-like agents for telecommunication applications. Lectures Notes in AI, 1998. 1437.
[9] R. van der Put, Routing in the faxfactory using mobile agents, technical Report R&D-SW-98-276 KPN Research, 1998.
[10] R.van der Put and L. Rothkrantz, Routing in packet switched networks using agents. Simulation Practice and Theory, 1999.
[11] Dorigo, M., Optimization, Learning and Natural Algorithms. Ph.D. thesis, 1992.
[12] Dorigo, M. and L. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem problem. IEEE Transactions on Evolutionary Computation, 1997. 1(1): p. 53-66.
[13] Dorigo, M., V. Maniezzo, and A. Colorni, The ant system: an autocatalytic optimization process. Tech. rep. 91-016 Politecnico di Milano, Dipartimento di Elettronica ed Informatic, 1991.
[14] Dorigo, M., V. Maniezzo, and A. Colorni, The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-PartB, 1996. 26(1): p. 29-41.
[15] Schoonderwoed, R., et al., Load balancing in telecommunications networks. Adaptive Behavior, 1997.5(2).
[16] Dorigo, M. and G. Di Caro, Ant algorithms for discrete opetimization. Artificial Life, 1999. 5(3): p. 137-172.
[17] Di Caro, G. and M. Dorigo, Extending Antnet for best-effort Qualty-of-Service Routing. ANTS'98-From Ant Colonies to artificial Ants: First International Workshop on ant colony optimization, 1998.
[18] Kuntz, P., P. Layzell, and D. Snyers, A colony of ant-like agents for partitioning in VLSI technology. Proc. of the 4th European Conf. On Artificial Life., 1997: p. 417-424.
[ 19] Song, Y.H., Combined heat and power economic dispatch by improved ant colony search algorithm. Electric Power System Research, 1999. 52: p. 115-121.
[20] Chang, C.S., A new approach to fault section estimation in power systems using ant system. Electric Power System Research, 1999. 49: p. 63-70.
[21 ] Cordon, O., F. Herrera, and L. Sanchez, Solving Electrical distribution problems using Hybrid evolutionary data analysis techniques. Applied Intelligence, 1999. 10: p. 251-270.
[22] Maniezzo, V., An ANTS heuristic for the frequency assignment problem. Antonella Carbonaro Future Generation Computer Systems, 2000. 16: p. 927-935.
[23] Navarro Varela, G. and M.C. Sinclair. Ant colony optimisation for virtual-wavelength-path routing and wavelength allocation, in Proc. 1999 Congress on Evolutionary Computation. 1999. Washington DC, USA.
[24] Bullnheimer, B., R.F. Hartl, and Strauss.C, An improved ant system algorithm for the vehicle routing problem. Technical Report POM-10/97, Institute of Management Science, University of Vienna, 1997.
[25] Brelaz, D., New methods to color vertices of a graph. Communications of the ACM, 1979. 22: p.251-256.
[26] Costa, D. and A. Hertz., Ants can colour graphs. Journal of the Operational Research
Society, 1997. 48: p. 295-305.
[27] Costa, D., A. Hertz, and Dubuis.O., Embedding of a sequential algorithm within an evolutionary algorithm for coloring problems in graphs. Journal of Heuristics, 1995. 1:p. 105-128.
[28] COSTA, D. and A. HERTZ, Ants Can Colour Graphs. Journal of the Operational Research Society, 1997. 48: p. 295-305.
[29] Gallager, R., Discrete Stochastic Processes. Kluwer Academic Publishers, Dordrecht, 1996.
[30] Feo, T.A. and M.G.C. Resends, Greedy Randomized Adaptive Search Procedures. J Global Optimization, 1995. 6: p. 109-133.
[31 ] Dorigo, M. and L. Gambardella, ant colonies for the traveling salesman problem. BioSystems, 1997. 43: p. 73-81.
[32] Bullnheimer, B., R.F. Hartl, and C. Strauss, A new rank-based version of the ant system: a computational study. Technical Report POM-03/97, Institute of Management Science, University of Vienna, 1997.
[33] Chen, K., A simple learning algorithm for the traveling salesman problem. Physical Review E, 1997.
[34] Colorni, A., M. Dorigo, and Maniezzo.V., Distributed optimization by ant colonies. In Proceedings of the First European Conference on Artificial Life, 1992: p. 134-142.
[35] Gambardella, L.M. and M. Dorigo, Solving symmetric and asymmetric TSPs by ant colonies. In Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96, 1996: p. 622-627.
[36] Johnson, D.S. and L.A. McGeoch, The traveling salesman problem: A case study. In E.H. Aarts and J. K. Lenstra, editors, In Local Search in Combinatorial Optimization, 1997: p. 215-310.
[37] Colorni, A., Ant system for Job-shop Sheduling. JORBEL, 1994. 34(1): p. 39-53.
[38] Bullnheimer, B., G. Kotsis, and Strauss.C, Parallelization strategies for the ant system. Technical Report POM 9-97, Institute of Management Science, University of Vienna, 1997.
[39] Gambardella, L.M., E.D. Taillard, and M. Dorigo, Ant colonies for the QAP. Technical Report 4-97, IDSIA, Lugano, Switzerland, 1997.
[40] Maniezzo, V. and A. Colorni, The ant system applied to the quadratic assignment problem. IEEE Trans. Knowledge and Data Engineering, 1999.
[41] Maniezzo, V., A. Colorni, and M. Dorigo, The ant system applied to the quadratic assignment problem. Technical Report IRIDIA/94-28, Universit'e Libre de Bruxelles, Belgium, 1994.
[42] Stutzle, T., MAX-MIN ant system for the quadratic assignment problem. Technical Report AIDA-97-4, FG Intellektik, TU Darmstadt, 1997.
[43] Taillard, E., Comparison of Iterative Search for the Quadratic Assignment Problem. Location Science, 1995.3: p. 87-103.
[44] Bullnheimer, B., R.F. Hartl, and Strauss.C, Applying the ant system to the vehicle routing problem. In I. H. Osman S. Voβ, S. Martello and C. Roucairol, editors,Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 109-120. Kluwer Academics, 1998.
[45] Colorni, A., et al., Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 1994.34: p. 39-53.
[46] Di Caro, G. and M. Dorigo, An adaptive multi-agent routing algorithm inspired by ants behavior. In Proceedings of PART98-5th Annual Australasian Conference on Parallel and Real-Time Systems, 1998: p. 261-272.
[47] Di Caro, G. and M. Dorigo, Ant colonies for adaptive routing in packet-switched communications networks. In A. E. Eiben, T. Back, M. Schoenauer, and H.-P.Schwefel, editors, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, 1998: p. 673-682.
[48] Di Caro, G. and M. Dorigo, Extending AntNet for best-effort Quality-of-Service routing. http://iridia.ulb.ac.be/ants98/ants98.html, October 15-16, 1998.
[49] Di Caro, G. and M. Dorigo, Two ant colony algorithms for best-effort routing in datagram networks. In Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems, 1998: p. 541-546.
[50] Heusse, M., et al., Adaptive agent-driven routing and load balancing in communication networks. Technical Report RR-98001-1ASC, Department Intelligence Artificielle et Sciences Cognitives, ENST Bretagne, 1998.
[51] Witten, I.H., An adaptive optimal controller for discrete-time Markov environments. Information and Control, 1997.34: p. 286-295.
[52] Grasse, P.P., La reconstruction du nid et les coordiniations interindividuelles chez bellicositermes natalensis et cubitermes sp. La theorie de la stigmergic: essai d'interpretation du comportement des termites constru teurs. Insectes Sociaux, 1959. 6: p. 41-81.
[53] Raiha, K.-J. and E. Ukkonen, The shortest common supersequence problem over binary alphabet is NP-complete. Theoretical Computer Science, 1981. 16: p. 187-198.
[54] Dorigo, M., The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on System, Man, and Cybernetics-part B, 1996.26(1): p. 1-13.
[55] Bullnheimer, B., R.F. Hartl, and Strauss.C., A new rank-based version of the ant system." a computational study. Technical Report POM-03/97, Institute of Management Science, University of Vienna, 1997.
[56] Stutzle, T. and H. Hoos, The MAX-MIN ant system and local search for the traveling salesman problem. In T. Baeck, Z. Michalewicz, and X. Yao, editors, Proceedings of IEEE-ICEC-EPS (?) 97, IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference, 1997: p. 309-314.
[57] Stutzle, T. and H. Hoes, Improvements on the ant system: Introducing MAX-MIN ant system. In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, 1997: p. 245-249.
[58] Stutzle, T. and H. Hoos, MAX-MIN Ant system and local search for combinatorial optimization problems. In S. Voβ, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization: p. 137-154.
[59] Dorigo, M. and L.M. Gambardella, A study of some properties of Ant-Q. In Proceedings of PPSN-Ⅳ, Fourth International Conference on Parallel Problem Solving From Nature, 1996: p. 656-665.
[60] Gambardella, L.M. and M. Dorigo, Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. Proc. of ML-95, Twelfth Intern. Conf. on Machine Learning, 1995: p. 252-260.
[61] Blum, C., A. Roli, and M. Dorigo. HC-ACO: The hyper-cube framework for Ant Colony Optimization. in In Proceedings of MIC (?) 2001 Meta heuristics International Conference. 2001.
[62] Gutjahr, W.J., A graph{based Ant System and its convergence. Future Generation Computer Systems, 2000. 16(8): p. 873-882.
[63] Kaelbling, L.R, M.L. Littman, and A.W. Moore, Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 1996.4: p. 237-285.
[64] Durbin, R. and D. Willshaw, An analogue approach to the travelling salesman problem using an elastic net method. Nature, 1987. 326: p. 689-691.
[65] Whitley, D., T. Starkweather, and D. Fuquay. Scheduling problems and travelling salesman: the genetic edge recombination operator, in Proceedings of the Third International Conference on Genetic Algorithms. 1989. Morgan Kaufmann.
[66] Reinelt, G., The traveling salesman: Computational solutions for TSP applications. Springer- Verlag, 1994.
[67] Fogel, D., Applying evolutionary programming to selected traveling salesman problems. Cybernetics and Systems: An International, 1993. 24: p. 27-36.
[68] Bersini, H., C. Oury, and M. Dorigo, Hybridization of genetic algorithms. Tech. Rep. No. IRIDIA/95-22, IRIDIA, University libre de Bruxelles, Belgium, 1995.
[69] Lin, F.-T., C.-Y. Kao, and C.-C. Hsu, Applying the genetic approach to simulated annealing in solving some NP-hard problems. IEEE Transactions on System, Man, and Cybernetics, 1993. 23: p. 1752-1767.
[70] Borthick, s., Today's internet can't scale. Business Communication Review, Mayt 2001.
[71] Bonabeau, E., et al., Routing in telecommunication networks with (?) Smart(?) ant-like agents telecommunication applications. In Proceedings of IATA メ 98, Second Int. Workshop on Intelligent Agents for Telecommunication Applications., 1998. 1437.
[72] White, T., B. Pagurek, and F. Oppacher, Connection management using adaptive mobile agents, agents. In H.R. Arabnia, editor, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1998: p. 802-809.
[73] Schoonderwoerd, R., O. Holland, and J. Bruten, Ant-like agents for load balancing in telecommunications networks. Hewlett-Packard Laboratories, Bristol-England, 1997.
[74] Bieszczad, A., B. Pagurek, and T. White, Mobile agents for network management. IEEE Communication Surveys, 1998. 1(1).
[75] White, T., Swarm intelligence and problem solving in telecommunications. Canadian Artificial Intelligence Magazine, 1997.
[76] White, T., Routing with swarm intelligence. Technical Report SCE-97-15, Systems and Computer Engineering Department, Carleton University, September 1997.
[77] White, T. and B. Pagurek, Towards multi-swarm problem solving in networks. Proc. 3rd Intl. Conf. on Multi-Agent Systems (ICMAS '98), July 1998: p. 333-340.
[78] White, T., B. Pagurek, and F. Oppacher, ASGA: improving the ant system by integration with genetic algorithms. Proc. 3rd Genetic Programming Conference, July 1998: p. 610-617.
[79] White, T., B. Pagurek, and F. Oppacher, Ant search with genetic algorithms: application to path finding in networks. Combinatorial Optimization '98, Brussels, Belgium, April 15-17 1998.
[80] Baran, B. and R. Sosa, AntNet routing algorithm for data networks based on mobile agents. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial, 2001. 12: p. 75-84.
[81] Schoonderwoerd, R., et al., Ant-based load balancing in telecommunication networks. Adaptive Behavior, 1996. 5(2): p. 169-207.
[82] Di Caro, G. and M. Dorigo, AntNet: a mobile agents approach to adaptive routing. Tech. Rep. IRID1A/97-12, IR1DIA, Universite Libre de Bruxelles, Belgium, 1997.
[83] Subramanian, D., Ants and reinforcement learning: a case study in routing in dynamic networks. In Proceedings of IJCA1-97, International Joint Conference on Artificial Intelligence, 1997: p. 832-838.
[84] Dorigo, M., Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di MilanoIT, 1991.
[85] Colorni, A., Distributed optimization by ant colonies. In Proceedings of ECAL91-European Conference on Artificial Life, 1991: p. 134-142.
[86] Feit, S., TCP/IP. Architecture, Protocols and Implementation. McGraw & Hill, 1996.
[87] Boyan, J.A. and M.L. Littman, Packet routing in dynamically changing networks: A reinforcement approach. In Advances in Neural Information Processing Systems, 1994. 6: p. 671-678.
[88] Choi, S. and D.Y. Yeung, Predictive Q-routing: A memory-based reinforcement learning approach to adaptive traffic control. In Advances in Neural Information Processing Systems, 1996. 8: p. 945-951.
[89] Di Caro, G. and M. Dorigo, AntNet: a mobile agents approach to adaptive routing. ech. Rep. IRIDIA/97-12, IRIDIA, Universite Libre de Bruxelles, Belgium, 1997.
[90] Sandick, H. and E. Crawley, QoS Routing Working Group Report. Internet Draft, Internet Engineering Task Force, 1997.
[91] Walrand, J. and J. Crowcroft, High-performance Communication Networks. Morgan Kaufmann, 1996.
[92] Dorigo, M., Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano,IT., 1991.
[93] Goss, S., et al., Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 1989.76: p. 579-581.
[94] Beckers, R., J.L. Deneubourg, and S. Goss, Trails and U-turns in the selection of the shortest path by the ant Lasius Niger. Journal of Theoretical Biology, 1992. 159(397-415).
[95] Dorigo, M. and L.M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997. 1(1): p. 53-66.
[96] Gambardella, L.M., Ant-Q: A reinforcement learning approach to the traveling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, 1995: p. 252-260.
[97] Colorni, A. and M. Dorigo, Distributed optimization by ant colonies. In Proceedings of ECAL91-European Conference on Artificial Life, 1991: p. 134-142.
[98] Stutzle, T. and M. Dorigo, ACO algorithms for the quadratic assignment problem. New Ideas in Optimization, McGraw-Hill, 1999.
[99] Taillard, E.D. and L.M. Gambardella, Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research, 2000(135): p. 1-16.
[100] Dorigo, M., Ant algorithms for discrete optimization. Artificial Life, 1999.3(5): p. 137-172.
[101] Maniezzo, V., Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. Technical Report CSR98-1, Scienze dell'Informazione, Universit?di Bologa, Sede di Cesena, 1998.
[102] Gambardella, L., HAS-SOP: Hybrid ant system for the sequential ordering problem. Technical Report IDSIA 11-97, IDSIA, Lugano, Switzerland, 1997.
[103] Colorni, A. and M. Dorigo, Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 1994.34(1): p. 39-53.
[104] Dorigo, M., Ant algorithms and stigmergy. Future Generation Computer System. 2000(16): p. 851-871.
[105] 阎平凡 and 张长水,人工神经网络与模拟进化计算.清华大学出版社,2000.
[106] 王永骥 and 涂健,神经元网络控制.机械工业出版社,1998.
[107] McQuillan, J.M., I. Richer, and E. Rosen, C., The new routing algorithm for the ARPANET. IEEE Transactions on Communications, 1980. 28(711-719).
[108] Khanna, A. and J. Zinky, The revised ARPANET routing metric. ACM SIGCOMM Computer Communication Review, 1989. 19(4): p. 45-56.
[109] Singh, S.P., T. Jaakkola, and M.I. Jordan. Learning without state estimation in partially observable Markovian decision processes, in In Proceedings of Eleventh Machine Learning Conference. 1994. New Brunswick, NJ:Morgan Kaufmann.
[110] Rubistein, R.Y., Simulation and the Monte Carlo Method. John Wiley & Sons, 1981.
[111] Bak, S., J. Cobb, and E. Leiss, Load Balancing Routing via Randomization. XXV Informatic Latinoamerican Conf.-CLEI, Asuncion-Paraguay, 1999: p. 999-1010.