改进的蚁群算法及其在QoS中的应用
|
摘要
蚁群优化算法是继模拟退火算法、遗传算法、禁忌搜索等智能启发式搜索算法之后,可以有效的求解组合优化问题的一种新型的模拟进化算法。它由MarcoDorigo于1992年在他的博士论文中最先提出,其灵感来源于蚂蚁在寻找食物过程中发现最短路径的行为。最新研究表明蚁群优化算法是一种基于群体的具有正反馈、分布式和强鲁棒性等优点的自组织的进化算法,该算法通过模拟蚂蚁的觅食行为,采用信息素正反馈机制、蚂蚁个体的分布式计算与路径启发式信息相结合的方法,能够很快地发现较好的解路径。然而,初期信息素无法反映路径的优劣导致初始搜索时间过长、容易陷入局部最优解等缺点在一定程度上影响了算法的求解性能。
本文从介绍常用于分析蚁群算法性能的经典NP问题——TSP问题入手,对蚁群优化算法的机制原理、模型、实现步骤和优缺点进行了详细的介绍,介绍了针对该算法本身缺点进行的诸多改进策略,并对基本蚁群算法模型进行了参数分析,用以指导算法参数的设置,在最大最小蚁群算法的基础上,加入了四个改进策略,使改进后的E-MMAS算法收敛速度和解路径的质量有了明显的提高,仿真实验中给出了E-MMAS在解决经典TSP问题和最小比率TSP问题上的性能优势。然后介绍了QoS路由技术的概况和及网络模型、数学模型,结合QoS路由问题对路径约束的新特征,基于E-MMAS快速收敛的特性,增加邻居探测、修改其概率转移公式,提出了一个性能优越的适用于解决QoS路由的QoS-MMAS算法,对于路径的优劣给出了两个适应度评价函数,在最后的实验仿真中,给出了在无向图和有向图中的实验对比结果,实验结果证实QoS-MMAS算法可以有效的解决QoS路由问题。
Ant colony optimization algorithm, as a new kind of novel simulated evolutionaryalgorithm after genetic algorithm, simulated annealing algorithm, tabu search algorithm andso on, provides a new way to efficiently solve complicated combinatorial optimizationproblems. Ant colony optimization was first proposed in 1992 by Italian researchers M.Dorigo in his doctoral dissertation, the inspiration first came from the fact that ants can foundthe shortest path in their process of searching for food. The latest research showed that antcolony optimization algorithm is a population-based and self-organized algorithm which ispositive feedback, distributed computing, better robust and combined with heuristic pathinformation, etc, so it can find better solution paths in a very short time. However, as theinitial pheromone information cant't reflect the quality of the path, it will spend a long time inthe early search and it is easy to fall into local optimal solution, all of which have a badinfluence on the performance of searching the shortest path.
This dissertation introduces the most representative NP problem, so-called TravelingSalesman Problem as a start, which is usually used to analyze the performance of ant colonyalgorithm. Then the model, mechanism, advantages, disadvantages and the implementationsteps of the ant colony optimization algorithm are discussed in detail. After that we bring forthto the main improvement strategies on the basic ant colony optimization algorithm andpresent an analysis on its model parameters to guide the parameter setting later. Adding fourimprovement strategies to max-min ant algorithm, we call it E-MMAS that get a betterperformance, the later TSP's and Minimum Ratio TSP's simulation experiments proves thatE-MMAS has the advantage of a better convergence speed and a better solution path. In thefollowing we discuss the QoS routing technology, network model, the mathematical modeland the new features about the path constraints on QoS routing problem. Based on the fasterconvergence speed of E-MMAS, adding neighbors detection method and modifying itsprobability formula, we implement a superior algorithm called QoS-MMAS which is suited tosolve QoS routing problem. This paper uses two evaluation functions for the quality of thesolution paths. In the last part, a performance comparison between QoS-MMAS and otheralgorithms is made on solving QoS routing problem represented in both directed graph model and undirected graph model. The results indicate that the QoS-MMAS algorithm caneffectively solve the QoS routing problem.
本文从介绍常用于分析蚁群算法性能的经典NP问题——TSP问题入手,对蚁群优化算法的机制原理、模型、实现步骤和优缺点进行了详细的介绍,介绍了针对该算法本身缺点进行的诸多改进策略,并对基本蚁群算法模型进行了参数分析,用以指导算法参数的设置,在最大最小蚁群算法的基础上,加入了四个改进策略,使改进后的E-MMAS算法收敛速度和解路径的质量有了明显的提高,仿真实验中给出了E-MMAS在解决经典TSP问题和最小比率TSP问题上的性能优势。然后介绍了QoS路由技术的概况和及网络模型、数学模型,结合QoS路由问题对路径约束的新特征,基于E-MMAS快速收敛的特性,增加邻居探测、修改其概率转移公式,提出了一个性能优越的适用于解决QoS路由的QoS-MMAS算法,对于路径的优劣给出了两个适应度评价函数,在最后的实验仿真中,给出了在无向图和有向图中的实验对比结果,实验结果证实QoS-MMAS算法可以有效的解决QoS路由问题。
Ant colony optimization algorithm, as a new kind of novel simulated evolutionaryalgorithm after genetic algorithm, simulated annealing algorithm, tabu search algorithm andso on, provides a new way to efficiently solve complicated combinatorial optimizationproblems. Ant colony optimization was first proposed in 1992 by Italian researchers M.Dorigo in his doctoral dissertation, the inspiration first came from the fact that ants can foundthe shortest path in their process of searching for food. The latest research showed that antcolony optimization algorithm is a population-based and self-organized algorithm which ispositive feedback, distributed computing, better robust and combined with heuristic pathinformation, etc, so it can find better solution paths in a very short time. However, as theinitial pheromone information cant't reflect the quality of the path, it will spend a long time inthe early search and it is easy to fall into local optimal solution, all of which have a badinfluence on the performance of searching the shortest path.
This dissertation introduces the most representative NP problem, so-called TravelingSalesman Problem as a start, which is usually used to analyze the performance of ant colonyalgorithm. Then the model, mechanism, advantages, disadvantages and the implementationsteps of the ant colony optimization algorithm are discussed in detail. After that we bring forthto the main improvement strategies on the basic ant colony optimization algorithm andpresent an analysis on its model parameters to guide the parameter setting later. Adding fourimprovement strategies to max-min ant algorithm, we call it E-MMAS that get a betterperformance, the later TSP's and Minimum Ratio TSP's simulation experiments proves thatE-MMAS has the advantage of a better convergence speed and a better solution path. In thefollowing we discuss the QoS routing technology, network model, the mathematical modeland the new features about the path constraints on QoS routing problem. Based on the fasterconvergence speed of E-MMAS, adding neighbors detection method and modifying itsprobability formula, we implement a superior algorithm called QoS-MMAS which is suited tosolve QoS routing problem. This paper uses two evaluation functions for the quality of thesolution paths. In the last part, a performance comparison between QoS-MMAS and otheralgorithms is made on solving QoS routing problem represented in both directed graph model and undirected graph model. The results indicate that the QoS-MMAS algorithm caneffectively solve the QoS routing problem.
引文
[1].Goss S, Aron S, Deneubourg J L, et al. Self-organized shortcuts in the argentine ant[J].Naturwissenschaften, 1989, 76 : 579~581
[2].Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]. Proceedings ofthe 1st European Conference on Artificial Life,1991,134~142
[3].Gutjahr W J. A generalized convergence result for the graph based ant system[C].TechnicalReport 99-09, Dept. of Statistics and Decision Support Systems, University of Vienna, Austria,1999
[4].Gutjahr W J. A grapth-based ant system and its convergence[J]. Future Generation ComputerSystems, 2000,16(8) : 873~888
[5].Hua Z, Fan H, Li J J. et al. Solving point covering problem by ant algorithm[C]. Proceedingsof the 2004 International Conferrence on Machine Learning and Cybernetics,2004,6:3501~3504.
[6].Dorigo M, Optimization,learning and natural algorithms[D]. Ph. D. Thesis, Department ofElectronics,Politecnico diMilano,Italy,1992
[7].Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperatingagents[C]. IEEE Transaction on Systems, Man, and Cybernetics-Part B,1996,36(1):29~41
[8].Colorni A, Dorigo M, Maniezzo V. Ant system for job-shop scheduling[J]. Belgian J. Oper.Res. Statist. Compute. Sci. 1994,34:39~53
[9].Gambardella L M,Taillard E,Agazzi G. MACS-VRPTW:a multiple ant colony system forvehicle routing problems with time windows[J]. New Ideas in Optimization,McGraw-Hill,London,UK,1999,63~76
[10].Costa D, Hertz A. Ants can color graphs[J]. Journal of the Operational ResearchSociety,1997,48(3):395~305
[11].陈志平，徐宗本.计算机数学[M].北京：清华大学出版社，2001
[12].陈崚，秦玲，陈宏建等.具有感觉和知觉特征的蚁群算法[J].系统仿真学报，2003，15(10):1418~1425
[13].M. Dorigo, L. M. Gambardella . Ant Colony System: A Cooperative Learning Approach tothe Traveling Salesman Problem[C]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53~66
[14].N.Monarche,G.Venturini and M.Slimane.On how Pachycondyla apicalis ants suggest a newsearch algorithm[J].Future Generation Computer System. 2000, 16(8): 937-946.
[15].陈峻，沈洁，秦玲，陈宏建.基于分布均匀度的自适应蚁群算法[J].软件学报.2003，14(8):1379~1387.
[16].Stutzle T,Hoos H. Max-min ant system[J]. Future Generation ComputerSystem,2000,16:889~914
[17].张锦,李伟,费腾.交叉变异蚁群算法在VRP问题中的应用研究[J].计算机工程与应用，2009，45（34）201～203
[18].吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法计算机研究与发展[J].计算机研究与发展，1999，36（10）：1240-1245.
[19].Peng Y Q, Hou X D, Liu S. The K-means clustering algorithm based on density and antcolony[C]. Proceedings of the 2003 International Conferrence on Neural Networks and SignalProcessing, 2003, 1:457~460
[20].郝晋，石立宝，周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程理论与实践. 2002，9(9)：89~91
[21].Abbattista F, Abbattista N, Caponetti L. An evolutionary and cooperating agents modelfor optimization[C]. Proceedings of the IEEE International Conferrence on EvolutionaryComputation, 1995, 2:668~671
[22].侯云鹤，鲁丽娟，熊信艮等.广义蚁群与粒子群结合算法在电力系统经济负荷分配中的应用.电网技术, 2004，28(21):34~38
[23].M.L.Gambardella,M.Dorigo.HAS-SOP：An Hybrid ant system for the sequential orderingproblem[R]. Technical Report IDSIA–ll-97，IDSIA，Lugano，Switzerland，1997.
[24].唐增明，蒋泰.一种改进的动态自适应最大-最小蚁群算法[J].计算机与现代化，2008,90~92
[25].郗建国,郝会霞.车辆路径问题的最大—最小蚁群算法研究[J].山东交通学院学报,2007, 15(2):19~22
[26].Bullnheimer，RFHartl，CStrauss. A New Rank-based Version of The Ant System:AComPutational Study[R].Technieal RePort POM－03/97，Institute of Management Scienee，University of Vienna，1997.AecePted for Publication in the Central EuroPean Journal forOperations Researeh and Eeonomie.
[27].Crawley, E., Nair, R., Rajagopalan, B. et al. A framework for QoS-based routing in theInternet[M]. RFC 2386, 1998.
[28].林闯，单志广，任丰原.计算机网络的服务质量(QoS)[M].北京:清华大学出版社2004
[29].Charikar Moses,Naor Joseph,Schieber Baruch.Resource optimization in QoS multicastrouting of real-time multimedia[C].In:Proceedings-IEEE INFOCOM 19th Annual JointConference of the IEEE Computer and Communications Societies-IEEE INFOCOM 2000.TelAviv,Isr.Mar 26-Mar 30 2000 v3:1518-1527.
[30].E.Crawley,R.Nair,B.Rajagopalan et al. A framework for QoS-based routing in theInternet[M].RFC 2386,IETF.August 1998.
[31].Lu Guoying, Liu Zemin, Zhou Zheng. Multicast Routing Based on Ant Algorithm forDelay-Bounded and Load-Banlancing Traffic[J]. IEEE. 2000,362~368
[32].Barati H. Movaghar A. Barati A.et al. Routing Algorithms Study and Comparing inInterconnection Networks[C].Information and Communication Technologies: From Theory toApplications, 2008. ICTTA 2008. 3rd International Conference. 2008: 1 ~ 5
[33].Maalaoui K. Belghith A.Bonnin J. et al. Performance evaluation of QoS routingalgorithms[C]. Computer Systems and Applications, The 3rd ACS/IEEE InternationalConference. July, 2005:66~70.
[34].H.Eriksson. MBONE:The Multicast Backbone[J].Communications of the ACM, 1994,37(8):54-61.
[35].Wang Z，Crowcroft J. Quality of service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications, 1996, 14(7)：1228-1234.
[36].崔勇，吴建平，徐烙，徐明伟.互联网络服务质量路由算法研究综述[J].软件学报.2002，(11)
[37].J.Nagle. Congestion Control in IP/TCP Internet works[M].RFC 896, January 1984.
[38].Guerin, R.A., Orda, A. QoS routing in networks with inaccurate information: theory andalgorithms[M]. IEEE/ACM Transactions on Networking, 1999,7(3):350~364.
[39].Wang, B., Hou, J.C. Multicast routing and its QoS extension: problems, algorithms, andprotocols[J]. IEEE Network, 2000,14(1):22~36.
[40].胡小兵，黄席樾.基于混合行为蚁群算法的研究[J].控制与决策，2005，20(1):69~71
[41].谢铎，周井泉.基于蚁群算法的QoS最佳路由选择问题的研究[J].计算机工程与应用。2007，43（3）：112～118
[42].刘萍. IPQoS路由算法的研究[D].扬州大学硕士学位论文.2007,3:32~42
[43].Apostolopoulos, G., Guerin, R., Kamat, S. Implementation and performance measurements ofQoS routing extensions to OSPF[C]. In:Doshi, B., ed. Precedings of the IEEE INFOCOM’99.New York, NY: IEEE Communication Society, 1999. 680~68
[44].朱刚，马良，姚俭等.若干扩展TSP的元胞蚂蚁算法[J].系统管理学报，2007，16(5):492~496
[2].Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]. Proceedings ofthe 1st European Conference on Artificial Life,1991,134~142
[3].Gutjahr W J. A generalized convergence result for the graph based ant system[C].TechnicalReport 99-09, Dept. of Statistics and Decision Support Systems, University of Vienna, Austria,1999
[4].Gutjahr W J. A grapth-based ant system and its convergence[J]. Future Generation ComputerSystems, 2000,16(8) : 873~888
[5].Hua Z, Fan H, Li J J. et al. Solving point covering problem by ant algorithm[C]. Proceedingsof the 2004 International Conferrence on Machine Learning and Cybernetics,2004,6:3501~3504.
[6].Dorigo M, Optimization,learning and natural algorithms[D]. Ph. D. Thesis, Department ofElectronics,Politecnico diMilano,Italy,1992
[7].Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperatingagents[C]. IEEE Transaction on Systems, Man, and Cybernetics-Part B,1996,36(1):29~41
[8].Colorni A, Dorigo M, Maniezzo V. Ant system for job-shop scheduling[J]. Belgian J. Oper.Res. Statist. Compute. Sci. 1994,34:39~53
[9].Gambardella L M,Taillard E,Agazzi G. MACS-VRPTW:a multiple ant colony system forvehicle routing problems with time windows[J]. New Ideas in Optimization,McGraw-Hill,London,UK,1999,63~76
[10].Costa D, Hertz A. Ants can color graphs[J]. Journal of the Operational ResearchSociety,1997,48(3):395~305
[11].陈志平，徐宗本.计算机数学[M].北京：清华大学出版社，2001
[12].陈崚，秦玲，陈宏建等.具有感觉和知觉特征的蚁群算法[J].系统仿真学报，2003，15(10):1418~1425
[13].M. Dorigo, L. M. Gambardella . Ant Colony System: A Cooperative Learning Approach tothe Traveling Salesman Problem[C]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53~66
[14].N.Monarche,G.Venturini and M.Slimane.On how Pachycondyla apicalis ants suggest a newsearch algorithm[J].Future Generation Computer System. 2000, 16(8): 937-946.
[15].陈峻，沈洁，秦玲，陈宏建.基于分布均匀度的自适应蚁群算法[J].软件学报.2003，14(8):1379~1387.
[16].Stutzle T,Hoos H. Max-min ant system[J]. Future Generation ComputerSystem,2000,16:889~914
[17].张锦,李伟,费腾.交叉变异蚁群算法在VRP问题中的应用研究[J].计算机工程与应用，2009，45（34）201～203
[18].吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法计算机研究与发展[J].计算机研究与发展，1999，36（10）：1240-1245.
[19].Peng Y Q, Hou X D, Liu S. The K-means clustering algorithm based on density and antcolony[C]. Proceedings of the 2003 International Conferrence on Neural Networks and SignalProcessing, 2003, 1:457~460
[20].郝晋，石立宝，周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程理论与实践. 2002，9(9)：89~91
[21].Abbattista F, Abbattista N, Caponetti L. An evolutionary and cooperating agents modelfor optimization[C]. Proceedings of the IEEE International Conferrence on EvolutionaryComputation, 1995, 2:668~671
[22].侯云鹤，鲁丽娟，熊信艮等.广义蚁群与粒子群结合算法在电力系统经济负荷分配中的应用.电网技术, 2004，28(21):34~38
[23].M.L.Gambardella,M.Dorigo.HAS-SOP：An Hybrid ant system for the sequential orderingproblem[R]. Technical Report IDSIA–ll-97，IDSIA，Lugano，Switzerland，1997.
[24].唐增明，蒋泰.一种改进的动态自适应最大-最小蚁群算法[J].计算机与现代化，2008,90~92
[25].郗建国,郝会霞.车辆路径问题的最大—最小蚁群算法研究[J].山东交通学院学报,2007, 15(2):19~22
[26].Bullnheimer，RFHartl，CStrauss. A New Rank-based Version of The Ant System:AComPutational Study[R].Technieal RePort POM－03/97，Institute of Management Scienee，University of Vienna，1997.AecePted for Publication in the Central EuroPean Journal forOperations Researeh and Eeonomie.
[27].Crawley, E., Nair, R., Rajagopalan, B. et al. A framework for QoS-based routing in theInternet[M]. RFC 2386, 1998.
[28].林闯，单志广，任丰原.计算机网络的服务质量(QoS)[M].北京:清华大学出版社2004
[29].Charikar Moses,Naor Joseph,Schieber Baruch.Resource optimization in QoS multicastrouting of real-time multimedia[C].In:Proceedings-IEEE INFOCOM 19th Annual JointConference of the IEEE Computer and Communications Societies-IEEE INFOCOM 2000.TelAviv,Isr.Mar 26-Mar 30 2000 v3:1518-1527.
[30].E.Crawley,R.Nair,B.Rajagopalan et al. A framework for QoS-based routing in theInternet[M].RFC 2386,IETF.August 1998.
[31].Lu Guoying, Liu Zemin, Zhou Zheng. Multicast Routing Based on Ant Algorithm forDelay-Bounded and Load-Banlancing Traffic[J]. IEEE. 2000,362~368
[32].Barati H. Movaghar A. Barati A.et al. Routing Algorithms Study and Comparing inInterconnection Networks[C].Information and Communication Technologies: From Theory toApplications, 2008. ICTTA 2008. 3rd International Conference. 2008: 1 ~ 5
[33].Maalaoui K. Belghith A.Bonnin J. et al. Performance evaluation of QoS routingalgorithms[C]. Computer Systems and Applications, The 3rd ACS/IEEE InternationalConference. July, 2005:66~70.
[34].H.Eriksson. MBONE:The Multicast Backbone[J].Communications of the ACM, 1994,37(8):54-61.
[35].Wang Z，Crowcroft J. Quality of service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications, 1996, 14(7)：1228-1234.
[36].崔勇，吴建平，徐烙，徐明伟.互联网络服务质量路由算法研究综述[J].软件学报.2002，(11)
[37].J.Nagle. Congestion Control in IP/TCP Internet works[M].RFC 896, January 1984.
[38].Guerin, R.A., Orda, A. QoS routing in networks with inaccurate information: theory andalgorithms[M]. IEEE/ACM Transactions on Networking, 1999,7(3):350~364.
[39].Wang, B., Hou, J.C. Multicast routing and its QoS extension: problems, algorithms, andprotocols[J]. IEEE Network, 2000,14(1):22~36.
[40].胡小兵，黄席樾.基于混合行为蚁群算法的研究[J].控制与决策，2005，20(1):69~71
[41].谢铎，周井泉.基于蚁群算法的QoS最佳路由选择问题的研究[J].计算机工程与应用。2007，43（3）：112～118
[42].刘萍. IPQoS路由算法的研究[D].扬州大学硕士学位论文.2007,3:32~42
[43].Apostolopoulos, G., Guerin, R., Kamat, S. Implementation and performance measurements ofQoS routing extensions to OSPF[C]. In:Doshi, B., ed. Precedings of the IEEE INFOCOM’99.New York, NY: IEEE Communication Society, 1999. 680~68
[44].朱刚，马良，姚俭等.若干扩展TSP的元胞蚂蚁算法[J].系统管理学报，2007，16(5):492~496