基于改进蚁群算法的全终端网络可靠性优化问题的研究
|
摘要
针对计算机网络在社会发展的影响以及其在人们生活中的重要性,各国学者纷纷投入了大量的精力研究分析了计算机网络的性能,并对其拓扑结构进行优化。特别是最近几年社会上已无处不“网络”,人们在依赖计算机网络的同时更加关注其可靠性,计算机网络的崩盘将会导致政府、企业、交通、医疗机构等部门不同程度的瘫痪。因此计算机网络的可靠性问题已成为研究的一个热点。
考虑到计算机网络设计的核心在于主干网的设计,而网络的全终端的可靠性又是体现其可靠性的关键指标,基于以上分析,本文旨在解决全终端网络可靠性优化问题。针对运营商的最大利益需求,提出了全终端网络成本优化问题;又针对客户安全性最高的需求,提出了全终端网络可靠性优化问题;同时为了共同兼顾二者的利益需求,提出了多目标全终端网络可靠性优化问题。在优化模型构建方面,结合了泰国学者Kanyapat Watcharasitthiwat在解决网络优化问题的建模思想,综合了上述问题的特点,提出了具体的模型。
国内外学者已证实了全终端网络可靠度的计算问题是NP-hard问题,由于自身的复杂性,使得传统的启发式方法和枚举法并不适用于大规模网络的优化设计问题,不过新兴的智能算法弥补了这一缺憾,且大量文献表明,智能算法在解决组合优化问题上具有一定的优越性。其中蚁群算法在求解组合优化问题时,表现出了极强的寻优能力和较好的性能,并在很多领域获得了广泛的应用。但是传统的蚁群算法也存在着一些弊端,主要体现在收敛速度慢、计算时间长、易于陷入局部最优等一些问题。针对以上弊端,本文对基本的蚁群算法进行了改进并应用于模型的优化求解中,结果表明改进后的蚁群算法在寻优速度和寻优效果上有了明显的提高。
通过仿真实验验证了改进蚁群算法在解决全终端网络可靠性优化问题上是十分有效的。为通信运营商设计可靠的主干网络提供了一个可执行的参考方案。
For the effect of computer networks in the social development and the importance of people's lives, scholars from various countries have put a lot of energy research on and analyze the performance of computer network, and optimize its topology structure. Especially in recent years has been "network”everywhere in society, people rely on computer networks at the same time pay more attention to its reliability, computer network collapse will lead to government, business, transportation, medical institutions and other departments of different degree of paralysis. Therefore, the reliability of computer network reliability has become a hot research field.
Considering that the computer network design is the core of the backbone network design, and the terminal is the key index of reliability performance, based on the above analysis, this paper aims to solve the problem of all-terminal networks reliability optimization. For the operator maximum benefit demand, put forward the all-terminal network cost optimization problem, and for customer safety highest demand, put forward all-terminal networks reliability optimization problem; at the same time in order to balance the interests of the two common demands, put forward multi-objective all terminal networks reliability optimization problems. In the optimization model, combined with the modeling idea of Thailand scholar Kanyapat Watcharasitthiwat in solutions of network optimization, the characteristic of the problem put forward specific model.
Domestic and foreign scholars have been confirmed that all terminal networks reliability calculation problem is a NP-hard problem, due to its complexity, the traditional heuristic method and enumeration method is not applicable to large-scale network optimization design problem, but new intelligent algorithm to make up for this deficiency, and a large number of literature suggests, intelligent algorithm in solving combinatorial optimization problems has certain advantages. The ant colony algorithm in solving combinatorial optimization problems, showed strong searching ability and good performance, and in many areas has been widely used. But the traditional ant colony algorithm also has this some drawbacks, mainly embodied in the slow convergence speed; the computing time is long, easy to fall into local optimal problems. In view of the above problems, in this paper, the basic ant algorithm is improved and applied to the model of optimization; the results show that the improved ant colony algorithm in cruise speed and optimization effect is improved obviously.
The simulation experiment results show that the improved ant colony algorithm to solve the optimization problem of all-terminal networks reliability is very effective. For telecommunications operators to design a reliable backbone network provides an executable program for reference.
考虑到计算机网络设计的核心在于主干网的设计,而网络的全终端的可靠性又是体现其可靠性的关键指标,基于以上分析,本文旨在解决全终端网络可靠性优化问题。针对运营商的最大利益需求,提出了全终端网络成本优化问题;又针对客户安全性最高的需求,提出了全终端网络可靠性优化问题;同时为了共同兼顾二者的利益需求,提出了多目标全终端网络可靠性优化问题。在优化模型构建方面,结合了泰国学者Kanyapat Watcharasitthiwat在解决网络优化问题的建模思想,综合了上述问题的特点,提出了具体的模型。
国内外学者已证实了全终端网络可靠度的计算问题是NP-hard问题,由于自身的复杂性,使得传统的启发式方法和枚举法并不适用于大规模网络的优化设计问题,不过新兴的智能算法弥补了这一缺憾,且大量文献表明,智能算法在解决组合优化问题上具有一定的优越性。其中蚁群算法在求解组合优化问题时,表现出了极强的寻优能力和较好的性能,并在很多领域获得了广泛的应用。但是传统的蚁群算法也存在着一些弊端,主要体现在收敛速度慢、计算时间长、易于陷入局部最优等一些问题。针对以上弊端,本文对基本的蚁群算法进行了改进并应用于模型的优化求解中,结果表明改进后的蚁群算法在寻优速度和寻优效果上有了明显的提高。
通过仿真实验验证了改进蚁群算法在解决全终端网络可靠性优化问题上是十分有效的。为通信运营商设计可靠的主干网络提供了一个可执行的参考方案。
For the effect of computer networks in the social development and the importance of people's lives, scholars from various countries have put a lot of energy research on and analyze the performance of computer network, and optimize its topology structure. Especially in recent years has been "network”everywhere in society, people rely on computer networks at the same time pay more attention to its reliability, computer network collapse will lead to government, business, transportation, medical institutions and other departments of different degree of paralysis. Therefore, the reliability of computer network reliability has become a hot research field.
Considering that the computer network design is the core of the backbone network design, and the terminal is the key index of reliability performance, based on the above analysis, this paper aims to solve the problem of all-terminal networks reliability optimization. For the operator maximum benefit demand, put forward the all-terminal network cost optimization problem, and for customer safety highest demand, put forward all-terminal networks reliability optimization problem; at the same time in order to balance the interests of the two common demands, put forward multi-objective all terminal networks reliability optimization problems. In the optimization model, combined with the modeling idea of Thailand scholar Kanyapat Watcharasitthiwat in solutions of network optimization, the characteristic of the problem put forward specific model.
Domestic and foreign scholars have been confirmed that all terminal networks reliability calculation problem is a NP-hard problem, due to its complexity, the traditional heuristic method and enumeration method is not applicable to large-scale network optimization design problem, but new intelligent algorithm to make up for this deficiency, and a large number of literature suggests, intelligent algorithm in solving combinatorial optimization problems has certain advantages. The ant colony algorithm in solving combinatorial optimization problems, showed strong searching ability and good performance, and in many areas has been widely used. But the traditional ant colony algorithm also has this some drawbacks, mainly embodied in the slow convergence speed; the computing time is long, easy to fall into local optimal problems. In view of the above problems, in this paper, the basic ant algorithm is improved and applied to the model of optimization; the results show that the improved ant colony algorithm in cruise speed and optimization effect is improved obviously.
The simulation experiment results show that the improved ant colony algorithm to solve the optimization problem of all-terminal networks reliability is very effective. For telecommunications operators to design a reliable backbone network provides an executable program for reference.
引文
[1]龚波,张文,杨红霞.网络基础.北京:电子工业出版社,2003.
[2] Boesch F T. On unreliability polynomials and graph connectivity in reliable network synthesis, J graph theory, 1986, 10(3): 339~352.
[3] Dengiz B, Altiparmak F, smith A E. Efficient optimization of all-terminal Reliability Reliable nerwork using an evolutionary approach. IEEE transaction on Reliability, 1997, 41(1): 18~26.
[4] Deeter D L, smith A E. Heuristic optimization of network design considering all-terminal reliability. Proceedings of the Reliability and Maintainability symposium, 1997: 194~199.
[5] Aggarwal K, Chopra Y C, Bajwa J S. Topological layout of links for optimizing the overall reliability in a computer communication system. Microelectronics and reliability, 1982, 22: 347~351.
[6] K. Watcharasitthiwat, Paramote Wardkein. Reliability optimization of topology communication network design using an improved ant colony optimization. Computer and Electrical Engineering. 2009, (35): 730~747.
[7] Satyanaranyana A, Prabhakar A. New topological formula and rapid algorithm for reliability analysis of complex networks, IEEE Tran, Reliability, 1978, 27(1): 82~100.
[8] Satyanarayana A, Hagstrom J N. A new algorithm for reliability analysis of muti-terminal networks, IEEE Trans. Reliability, 1981, 30(4): 325~324.
[9] Elmallah E S. Algorithms for K-terminal reliability problems with node failures, Networks, 1992, 22: 369~384.
[10] Ayoub J N, Saafin W H, Kahhaleh B Z. K-Terminal Reliability of Communication Networks. Electronics, Circuits and systerms, 2000, ICECS 2000, The 7th IEEE International Conference on, 2000, 1: 374~377.
[11] Jan R H. Design of reliable networks. Computer & Operations Research, 1993, 20(1): 25~24.
[12] Konak A, smith A E. An Improved General Upper Bound for All-Terminal Network Reliability, www.pitt.edu/aesmith/postscript/bound.pdf.
[13] Colbourn C J. The Combinatorics of Network Reliability, New York Oxford: Oxford University Press, 1987.
[14] Politof Th, Satyananrayana A. A linear time algorithm to Computer the reliability of planar cube free networks. IEEE Tran Reliability, 1990, 39(12): 557~563.
[15]郭彤城,慕春棣.并行遗传算法在一类计算机网络可靠性优化问题中的应用.系统工程理论与实践,2003,23(1):31~36.
[16]罗景峰,刘艳秋.智能算法在全终端网络可靠性优化设计中的应用.计算机测量与控制,2007,15(6):782~785.
[17]刘艳秋,罗景峰.基于MGA的全终端网络可靠性优化设计.沈阳工业大学学报,2008,30(02):199~202.
[18]罗景峰,王莹莹.基于鱼群算法的全终端网络可靠性优化设计.微电子学与计算机,2009,(02):93~96.
[19]程世娟,卢伟,陈虬.蚁群算法在网络路径可靠性研究中的应用.计算机工程与应用,2009,45(14):109~121.
[20]戴伏生.通信网络可靠性指标的新定义及计算方法.系统工程与电子技术,2006,28(11):1641~1651.
[21]宋月,刘三阳,冯海林.节点失效下全端可靠性的上界.数学的实践与认识,2006,36(1):165~169.
[22]何明,裘杭萍,刘勇.一种新的网络2-终端可靠性评估算法.计算机科学,2009,(07):40~42.
[23]赵虎,卢文.边失效概率不同情况下网络全终端可靠度的近似计算.电子设计工程,2011,(05):139~142.
[24]金庆风,刘胜利.基于可靠性理论的计算机通信网络分析及多目标优化.微型电脑应用,2009,25(01):19~21.
[25] Fratta L, Montanari U. G. . A Boolean Algebra Method for Computing the Terminal Reliability of a Communication Network, IEEE Trans. Circuit Theory, Vol. CT-20, May 1973: 203~211.
[26]牛义锋,徐秀珍.一种计算网络可靠度的不交和算法.科学技术与工程,2008,(21):5898~5900.
[27]孙艳蕊,赵连昌,张祥德.计算网络可靠度的容斥原理算法.小型微型计算机系统,2007,(05):830~833.
[28]孔繁甲,王光兴,张祥德.利用因子分解方法计算网络的根通信可靠性.电子与信息学报,1999,21(03):379~383.
[29]张艳,黄敏,赵宇等.基于置信分布的系统可靠度评估蒙特卡罗方法.北京航空航天大学学报,2006,(09):1023~1025.
[30]陈伦军等.机械优化设计遗传算法.北京:机械工业出版社,2006.
[31]高立群,吴沛锋,邹德旋.基于变异策略的粒子群算法.东北大学学报(自然科学版), 2010,31(11):1530~1533.
[32]倪庆剑,邢汉承,张志政等.粒子群优化算法研究进展.模式识别与人工智能, 2007,20(03):349~354.
[33]肖思和,鲁红英,范安东等.模拟退火算法在求解组合优化问题中的应用研究.四川理工学院学报(自然科学版),2010,23(01):116~118.
[34]张颖,刘艳秋.软计算方法.北京:科学出版社,2002.
[35] M. Dorigo, G. Di. Caro. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo and F. Glover,editors, New Ideas in Optimization, Megraw 111, London, UK, 1999: 11~32.
[36] A. Colorni, M. Dorigo, F. Maffioli et al. Heuristics from nature forward Combinational problems. International Transactions in Operational Research, vol.3, no.l, 1996: 1~21.
[37] Eric Bonabeau, Marco Dorigo, Guy TheraulaZ, Swarm intelligence: from natural to artificial systems, New York: Oxford University Press, 1999.
[38] James Kennedy, Russell C. Eberhart, Yuhui Shi. Swarm Intelligence. San Francesco: Morgan Kaufmann, 2001.
[39] Marco Dorigo, Tommas Stutzle. Ant Colony Optimization, MIT Press, 2004.
[40] Bonabeau E, Dorigo M, Theraulaz G. Inspiration for optimization from social insect behavior. Nature, 2000, 406(6): 39~42.
[41] Katija V, Ann N. Colonies of learning automata. IEEE Transactions on Systems, Man and Cybernetics Part B, 2002, 32(6): 772~780.
[42] Chu S C, Roddick J F, Pan J S. Ant colony system with communication strategies. Information Sciences, 2004, 167(1-4): 63~76.
[43] Chu S C, Roddick J F, Pan J S. Parallel ant colony systems. Lecture Notes in Artificial Intelligence, 2003, 2871: 279~284.
[44]段海滨.蚁群算法原理及其应用.北京:科学出版社,2005.
[45]宋雪梅,李兵.蚁群算法及应用.河南理工学院学报,2006,28(01):42~45.
[46]王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报,2002,14(1):32~33.
[47] Wang Y, Xie J Y, Ant colony optimization for multicast routing. Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems, 2000, 54~57.
[48]徐精明,曹先彬,王煦法.多态蚁群算法.中国科学技术大学学报,2005,35(1):59~65.
[49] Lee. Zne-Jung, Lee. Chou-Yuan, Su. Sun-Fang. An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem. Applied Soft Computing Journal, 2002, 2(1): 39~47.
[50]高尚,杨静宇,吴小俊等.可靠性优化的蚁群算法.计算机应用与软件,2004,21(12):94-96.
[51] Bernard Wong, A. Slivkings, Meridian. A Lightweight Network Location Service without Virtual Coordinates. Proceedings of SIGCOMM 2005, New York, N Y, USA: ACM, 2005: 85~96.
[52] Frank Dabek, Russ Cox, Vivaldi. A Decent realized Network Coordinate System. Proceedings of SIGCOMM Computer Communication Review 2004, New York, N Y, USA: ACM, 2004, 34(4): 15~26.
[53] Doerner K, Gutjahr W J, Hartl R F et al. Pareto ant colony optimization: a metaheuristic approach to multi-objective portfolio selection. Annals of Operations Research, 2004, 131(1): 79~99.
[54]符杨,孟令合,朱兰等.Pareto蚁群算法在多目标电网规划中的应用.电力系统及其自动化学报,2009,21(04):41~45.
[55]丁力平,谭建荣,冯毅雄等.基于Pareto蚁群算法的拆卸线平衡多目标优化.计算机集成制造系统,2009,13(07):1406~1413. .
[2] Boesch F T. On unreliability polynomials and graph connectivity in reliable network synthesis, J graph theory, 1986, 10(3): 339~352.
[3] Dengiz B, Altiparmak F, smith A E. Efficient optimization of all-terminal Reliability Reliable nerwork using an evolutionary approach. IEEE transaction on Reliability, 1997, 41(1): 18~26.
[4] Deeter D L, smith A E. Heuristic optimization of network design considering all-terminal reliability. Proceedings of the Reliability and Maintainability symposium, 1997: 194~199.
[5] Aggarwal K, Chopra Y C, Bajwa J S. Topological layout of links for optimizing the overall reliability in a computer communication system. Microelectronics and reliability, 1982, 22: 347~351.
[6] K. Watcharasitthiwat, Paramote Wardkein. Reliability optimization of topology communication network design using an improved ant colony optimization. Computer and Electrical Engineering. 2009, (35): 730~747.
[7] Satyanaranyana A, Prabhakar A. New topological formula and rapid algorithm for reliability analysis of complex networks, IEEE Tran, Reliability, 1978, 27(1): 82~100.
[8] Satyanarayana A, Hagstrom J N. A new algorithm for reliability analysis of muti-terminal networks, IEEE Trans. Reliability, 1981, 30(4): 325~324.
[9] Elmallah E S. Algorithms for K-terminal reliability problems with node failures, Networks, 1992, 22: 369~384.
[10] Ayoub J N, Saafin W H, Kahhaleh B Z. K-Terminal Reliability of Communication Networks. Electronics, Circuits and systerms, 2000, ICECS 2000, The 7th IEEE International Conference on, 2000, 1: 374~377.
[11] Jan R H. Design of reliable networks. Computer & Operations Research, 1993, 20(1): 25~24.
[12] Konak A, smith A E. An Improved General Upper Bound for All-Terminal Network Reliability, www.pitt.edu/aesmith/postscript/bound.pdf.
[13] Colbourn C J. The Combinatorics of Network Reliability, New York Oxford: Oxford University Press, 1987.
[14] Politof Th, Satyananrayana A. A linear time algorithm to Computer the reliability of planar cube free networks. IEEE Tran Reliability, 1990, 39(12): 557~563.
[15]郭彤城,慕春棣.并行遗传算法在一类计算机网络可靠性优化问题中的应用.系统工程理论与实践,2003,23(1):31~36.
[16]罗景峰,刘艳秋.智能算法在全终端网络可靠性优化设计中的应用.计算机测量与控制,2007,15(6):782~785.
[17]刘艳秋,罗景峰.基于MGA的全终端网络可靠性优化设计.沈阳工业大学学报,2008,30(02):199~202.
[18]罗景峰,王莹莹.基于鱼群算法的全终端网络可靠性优化设计.微电子学与计算机,2009,(02):93~96.
[19]程世娟,卢伟,陈虬.蚁群算法在网络路径可靠性研究中的应用.计算机工程与应用,2009,45(14):109~121.
[20]戴伏生.通信网络可靠性指标的新定义及计算方法.系统工程与电子技术,2006,28(11):1641~1651.
[21]宋月,刘三阳,冯海林.节点失效下全端可靠性的上界.数学的实践与认识,2006,36(1):165~169.
[22]何明,裘杭萍,刘勇.一种新的网络2-终端可靠性评估算法.计算机科学,2009,(07):40~42.
[23]赵虎,卢文.边失效概率不同情况下网络全终端可靠度的近似计算.电子设计工程,2011,(05):139~142.
[24]金庆风,刘胜利.基于可靠性理论的计算机通信网络分析及多目标优化.微型电脑应用,2009,25(01):19~21.
[25] Fratta L, Montanari U. G. . A Boolean Algebra Method for Computing the Terminal Reliability of a Communication Network, IEEE Trans. Circuit Theory, Vol. CT-20, May 1973: 203~211.
[26]牛义锋,徐秀珍.一种计算网络可靠度的不交和算法.科学技术与工程,2008,(21):5898~5900.
[27]孙艳蕊,赵连昌,张祥德.计算网络可靠度的容斥原理算法.小型微型计算机系统,2007,(05):830~833.
[28]孔繁甲,王光兴,张祥德.利用因子分解方法计算网络的根通信可靠性.电子与信息学报,1999,21(03):379~383.
[29]张艳,黄敏,赵宇等.基于置信分布的系统可靠度评估蒙特卡罗方法.北京航空航天大学学报,2006,(09):1023~1025.
[30]陈伦军等.机械优化设计遗传算法.北京:机械工业出版社,2006.
[31]高立群,吴沛锋,邹德旋.基于变异策略的粒子群算法.东北大学学报(自然科学版), 2010,31(11):1530~1533.
[32]倪庆剑,邢汉承,张志政等.粒子群优化算法研究进展.模式识别与人工智能, 2007,20(03):349~354.
[33]肖思和,鲁红英,范安东等.模拟退火算法在求解组合优化问题中的应用研究.四川理工学院学报(自然科学版),2010,23(01):116~118.
[34]张颖,刘艳秋.软计算方法.北京:科学出版社,2002.
[35] M. Dorigo, G. Di. Caro. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo and F. Glover,editors, New Ideas in Optimization, Megraw 111, London, UK, 1999: 11~32.
[36] A. Colorni, M. Dorigo, F. Maffioli et al. Heuristics from nature forward Combinational problems. International Transactions in Operational Research, vol.3, no.l, 1996: 1~21.
[37] Eric Bonabeau, Marco Dorigo, Guy TheraulaZ, Swarm intelligence: from natural to artificial systems, New York: Oxford University Press, 1999.
[38] James Kennedy, Russell C. Eberhart, Yuhui Shi. Swarm Intelligence. San Francesco: Morgan Kaufmann, 2001.
[39] Marco Dorigo, Tommas Stutzle. Ant Colony Optimization, MIT Press, 2004.
[40] Bonabeau E, Dorigo M, Theraulaz G. Inspiration for optimization from social insect behavior. Nature, 2000, 406(6): 39~42.
[41] Katija V, Ann N. Colonies of learning automata. IEEE Transactions on Systems, Man and Cybernetics Part B, 2002, 32(6): 772~780.
[42] Chu S C, Roddick J F, Pan J S. Ant colony system with communication strategies. Information Sciences, 2004, 167(1-4): 63~76.
[43] Chu S C, Roddick J F, Pan J S. Parallel ant colony systems. Lecture Notes in Artificial Intelligence, 2003, 2871: 279~284.
[44]段海滨.蚁群算法原理及其应用.北京:科学出版社,2005.
[45]宋雪梅,李兵.蚁群算法及应用.河南理工学院学报,2006,28(01):42~45.
[46]王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报,2002,14(1):32~33.
[47] Wang Y, Xie J Y, Ant colony optimization for multicast routing. Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems, 2000, 54~57.
[48]徐精明,曹先彬,王煦法.多态蚁群算法.中国科学技术大学学报,2005,35(1):59~65.
[49] Lee. Zne-Jung, Lee. Chou-Yuan, Su. Sun-Fang. An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem. Applied Soft Computing Journal, 2002, 2(1): 39~47.
[50]高尚,杨静宇,吴小俊等.可靠性优化的蚁群算法.计算机应用与软件,2004,21(12):94-96.
[51] Bernard Wong, A. Slivkings, Meridian. A Lightweight Network Location Service without Virtual Coordinates. Proceedings of SIGCOMM 2005, New York, N Y, USA: ACM, 2005: 85~96.
[52] Frank Dabek, Russ Cox, Vivaldi. A Decent realized Network Coordinate System. Proceedings of SIGCOMM Computer Communication Review 2004, New York, N Y, USA: ACM, 2004, 34(4): 15~26.
[53] Doerner K, Gutjahr W J, Hartl R F et al. Pareto ant colony optimization: a metaheuristic approach to multi-objective portfolio selection. Annals of Operations Research, 2004, 131(1): 79~99.
[54]符杨,孟令合,朱兰等.Pareto蚁群算法在多目标电网规划中的应用.电力系统及其自动化学报,2009,21(04):41~45.
[55]丁力平,谭建荣,冯毅雄等.基于Pareto蚁群算法的拆卸线平衡多目标优化.计算机集成制造系统,2009,13(07):1406~1413. .