神经网络与遗传算法在网络通信路由问题中的应用研究
|
摘要
网络通信路由问题是现代通信网络与服务中的基本问题之一。网络通信路由问题通常分为动态和静态两个类型。在本文中我们只考虑静态网络通信路由问题。静态网络通信路由问题通常可描述为一个约束Steiner树,而已知Steiner树本身是一个NP(Nondeterministic Polynomical)困难的问题,求得最优解相当困难,所以本论文在总结已有求解该问题的传统方法优、缺点的基础上,分别应用神经网络算法与遗传算法这两类典型的智能算法对其进行求解,获得了较满意的效果。为了应用神经网络算法求解,我们将原问题用一个带等式约束的二次0-1规划问题加以模型化,然后将该问题运用函数法转化到一个无约束二次能量函数,并给出求解网络通信路由问题的具体的Hopfield神经网络算法。在进行了一系列的数值模拟实验后我们发现,其计算速度快,而且对中、小规模问题,通常总能以非常快的速度找到问题的局部最优解。在本文,为了应用遗传算法求解,本文采取将原问题转换到一个所谓的“距离完备形”问题考虑,然后依据这一转换,设计一个新的可行解表示(即所谓解的染色体编码)和设置一个有效的适应性度量,并给出具体的遗传操作和求解网络通信路由问题的遗传算法。在进行了一系列的数值模拟实验后我们发现:遗传算法通常总能收敛到问题的全局最优解,而且计算效果稳定。
该文对网络通信路由问题进行了研究,其主要工作有以下几个方面:
(1)对网络通信路由问题的数学模型以及研究方法进行了探讨,构造出了数学模型,并对不同的研究方法进行了归纳总结,并提出了自己的研究方法。
(2)对神经网络算法进行了研究,并给出了能够用神经网络算法求解网络通信路由问题的数学模型及相应求解算法。
(3)对遗传算法进行了研究,并给出了能够用遗传算法求解网络通信路由问题的数学模型及相应求解算法。
(4)对不同规模的网络分别应用求解网络通信路由问题的神经网络算法与遗传算法进行数值模拟,体现了本文提出的以上求解网络通信路由问题的模型与算法的可行性与有效性。
本文研究的网络通信路由问题与实际问题有一定的差距,求解网络通信路由问题的神经网络算法和遗传算法只适用于单源多目的地网络通信路由问题,则下一步工作目标是设计更能符合实际网络通信路由的算法,即分别用神经网络算法和遗传算法求解动态的多源多目的地网络通信路由问题的算法,通过实验和实际运用验证其有效性和实用性。
The network routing problem is one of fundamental problems encounted in modern communication service. The network routing problem contains dynamic problem and static problem. We only consider about the static network routing problem. The static network routing problem can be formulated as a constraint Steiner tree, but as we all know the Steiner tree is a NP(Nondeterministic Polynomical) hard problem, the network routing problem can’t be resolved to achieve the perfect outcome. So based on the analysis for the existing heuristics for the network routing problem, the two typical computational intelligence methods– neural network and genetic algorithm is considered by this paper, in solving the network routing problem show that these two algorithms are effective and efficient. For solving the problem by neural network, we formulate the problem as a quadratic 0-1 planning problem that have a equality constraints, then we transfer the problem as a unconstrained quadratic energy function by function method,we give out concrete Hopfield neural network algorithm.We find the computing speed is quick, and the perfect outcome can be found for the middle scale、small scale problem after a series of numerical simulation experiments. In this paper,to apply the genetic algorithm for solving problems,the counter measures bellow will be put into our practice:First and foremost,the original problems have to be alter into a so-called complete form in distance;Last,a new feasible solution(that is,so called the chromosome coding of the solution) will be designed to express and set an efficient adjusting weight and generate an concrete genetic processing.It is found that the genetic algorithm can convergence the excellent result, and the computing effection is stable after a series of numerical simulation experiments.
This paper contributes to the research of the research of the network routing problem in four aspects:
(1) Discuss the mathematics model of the network routing and the research methods. After that this paper establishes the mathematics model and then puts its own research method.
(2) Study the neural network, and we establish the mathematics model and the solving algorithm of the network routing problem that can be solved by the neural network.
(3) Study the genetic algorithm, and we establish the mathematics model and solving algorithm of the network routing problem that can be solved by the genetic algorithm.
(4) This paper uses neural network and genetic algorithm for many different scales of network to do numerical simulation,it is showed that the effectivity and feasibility of the models and the algorithms of solving the network routing problem that be proposed in this paper.
In this paper there is still some difference between the academic research and the real life using. The two algorithms in this paper are suit for the single source-multiple destination network routing problem. Our next step is to invent new algorithms to resolve the real problems in logistics, and justify them by testing in experiment or the application of real life.
该文对网络通信路由问题进行了研究,其主要工作有以下几个方面:
(1)对网络通信路由问题的数学模型以及研究方法进行了探讨,构造出了数学模型,并对不同的研究方法进行了归纳总结,并提出了自己的研究方法。
(2)对神经网络算法进行了研究,并给出了能够用神经网络算法求解网络通信路由问题的数学模型及相应求解算法。
(3)对遗传算法进行了研究,并给出了能够用遗传算法求解网络通信路由问题的数学模型及相应求解算法。
(4)对不同规模的网络分别应用求解网络通信路由问题的神经网络算法与遗传算法进行数值模拟,体现了本文提出的以上求解网络通信路由问题的模型与算法的可行性与有效性。
本文研究的网络通信路由问题与实际问题有一定的差距,求解网络通信路由问题的神经网络算法和遗传算法只适用于单源多目的地网络通信路由问题,则下一步工作目标是设计更能符合实际网络通信路由的算法,即分别用神经网络算法和遗传算法求解动态的多源多目的地网络通信路由问题的算法,通过实验和实际运用验证其有效性和实用性。
The network routing problem is one of fundamental problems encounted in modern communication service. The network routing problem contains dynamic problem and static problem. We only consider about the static network routing problem. The static network routing problem can be formulated as a constraint Steiner tree, but as we all know the Steiner tree is a NP(Nondeterministic Polynomical) hard problem, the network routing problem can’t be resolved to achieve the perfect outcome. So based on the analysis for the existing heuristics for the network routing problem, the two typical computational intelligence methods– neural network and genetic algorithm is considered by this paper, in solving the network routing problem show that these two algorithms are effective and efficient. For solving the problem by neural network, we formulate the problem as a quadratic 0-1 planning problem that have a equality constraints, then we transfer the problem as a unconstrained quadratic energy function by function method,we give out concrete Hopfield neural network algorithm.We find the computing speed is quick, and the perfect outcome can be found for the middle scale、small scale problem after a series of numerical simulation experiments. In this paper,to apply the genetic algorithm for solving problems,the counter measures bellow will be put into our practice:First and foremost,the original problems have to be alter into a so-called complete form in distance;Last,a new feasible solution(that is,so called the chromosome coding of the solution) will be designed to express and set an efficient adjusting weight and generate an concrete genetic processing.It is found that the genetic algorithm can convergence the excellent result, and the computing effection is stable after a series of numerical simulation experiments.
This paper contributes to the research of the research of the network routing problem in four aspects:
(1) Discuss the mathematics model of the network routing and the research methods. After that this paper establishes the mathematics model and then puts its own research method.
(2) Study the neural network, and we establish the mathematics model and the solving algorithm of the network routing problem that can be solved by the neural network.
(3) Study the genetic algorithm, and we establish the mathematics model and solving algorithm of the network routing problem that can be solved by the genetic algorithm.
(4) This paper uses neural network and genetic algorithm for many different scales of network to do numerical simulation,it is showed that the effectivity and feasibility of the models and the algorithms of solving the network routing problem that be proposed in this paper.
In this paper there is still some difference between the academic research and the real life using. The two algorithms in this paper are suit for the single source-multiple destination network routing problem. Our next step is to invent new algorithms to resolve the real problems in logistics, and justify them by testing in experiment or the application of real life.
引文
[1]邓欣.基于遗传算法的多车场车辆路径问题研究[D].重庆大学硕士学位论文.2007.
[2]王永庆.人工智能原理与方法[M].西安:西安交通大学出版社,1998.
[3]刘勇.非数值并行算法——遗传算法[M].北京:科学出版社,1998.
[4]徐宗本,陈志平,章祥荪.遗传算法理论研究的新近发展[J].数学进展,22000,29(2):97.
[5]刘勇,康立山.大规模推销员问题的并行演化算法[A].全国第二届数学软件与科技工程软件学术会议论文集[C].1992,A - 42 - A– 44.
[6]崔屹.图像处理与分析——数学形态学方法及应用[M].北京:科学出版社,2000.
[7]王涛,卢显良.基于遗传算法的Peer-to-Peer路由算法R-GA.计算机应用研究[D],2007(1):316-317.
[8]徐新黎.反馈神经网络优化方法及其在作业车间调度和ATM网络路由选择中的应用[D].浙江工业大学硕士论文.2003.
[9]张晓波.并行遗传算法求解应急系统最短路径的研究[D].太原理工大学硕士论文.2005.
[10]林仰峰.基于遗传算法的QoS多播路由算法的研究[D].福州大学硕士论文.2006.
[11]杨旭华.神经网络及其在控制中的应用研究[D].浙江大学博士论文.2004.
[12] Jinwook Go;Gunhee Han;Hagbae Kim.Chulhee Lee.Multigradient:a new neural network learning algorithm for pattern classification[J].Geoscience and Remote Sensing, IEEE Transactions on,Volume:39,Issue:5,May 2001, Pages:986-993.
[13] Donq-Liang Lee.Pattern sequence recognition using a time-varying Hopfield network.Neural Networks[J],IEEE Transactions on,Volume:13,Issue:2,March 2002, Pages:330-342.
[14] Suganthan P.N..Hierarchical overlapped SOM's for pattern classification:Neural Networks[J]. IEEE Transactions on,Volume:10,Issue:1 Jan.1999,Pages:193-196.
[15] Maki Y.,Loparo K. A..A neural-network approach to fault detection and diagnosis in industrial processes:Control Systems Technology[J].IEEE Transactions on,Volume:5,Issue:6,Nov, 1997,Pages:529-541.
[16] Koh Jean,Suk Minsoo,Bhandarkar, Suchendra M..A Multilayer Self-Organizing Feature Map for Range Image Segmentation[J].Neural Networks ,Volume:8, Issue:1,1995, pp: 67-86.
[17] Ching-Hung Lee, Ching-Cheng Teng. Identification and control of dynamic systems using recurrent fuzzy neural networks[J].Fuzzy Systems,IEEE Transactions on,Volume:8,Issue:4,Aug. 2000,Pages:349-366.
[18] Messmer A.,Papageorgiou M.,Azema J.,Drewanz D..A neural network approach to freewaynetwork traffic control[J].Control Engineering Practice, Volume:3, Issue:12, December, 1995,pp:1719-1726.
[19] Youshen Xia, Jun Wang.A discrete-time recurrent neural network for shortest-path routing. Automatic Control[J], IEEE Transactions on , Volume:45 , Issue:11 , Nov,2000, Pages:2129-2134.
[20] Sun Yi.A generalized updating rule for modified Hopfield neural network for quadratic optimization[J].Neurocomputing ,Volume:19, Issue:1-3, Apri1 21,1998, pp. 133-143.
[21] Pham D. T.,Oh S. J..Identification of plant inverse dynamics using neural networks[J].Artificial Intelligence in Engineering, Volume:13, Issue:3, Ju1y,1999,pp:309-320.
[22]李树涛,王耀南,张昌凡.基于燃烧火焰图象特征的回转窑神经网络控制系统[J].自动化学报,2002年04期.
[23]张军英,王德峰,石美红.基于点火祸合神经网络的多约束QoS路由选择算法[J].通信学报,2002,23(7),p40-46.
[24]王万良,吴启迪,徐新黎.基于Hopfield神经网络的作业车间生产调度方法[J].自动化学报,2002,28(5),p838-844.
[25] Simon Haykin,叶世伟,史忠植.神经网络原理[M].北京:机械工业出版社,2004.1.
[26]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[27]何兴无.基于用户行为和遗传算法的用户建模研究[D].重庆大学硕士学位论文.2007.
[28]陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社,2001年.
[29] Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems,Man and Cybernetics,1994 ,24 (4):656-667.
[30]唐世浩,朱启疆.遗传算法中初始种群与交叉、变异率对解的影响及其解决方案[J].科技通报,2001,17(3).
[31]李敏强,寇纪淞等.遗传算法的基本理论与应用[M].北京:科学出版社,2003年.
[32] B.M.Waxman.Routing of Multipoint Connections[J].IEEE JSAC 1988,6(9):1617-1622.
[33]陈燕.基于遗传算法的选播QoS路由算法研究与仿真实现[D].广西大学硕士论文.2005.
[34]王燕琳.基于QoS约束的多播路由问题研究.天津大学博士论文[D].2004.
[35]杨建军.基于遗传算法的移动IP路由和性能分析.浙江大学博士论文[D].2004.
[36]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1996.
[37]高传善,钱松荣,毛迪林.数据通信与计算机网络[M].北京:高等教育出版社,2000.
[38]施鸿宝.神经网络及其应用[M].西安交通大学出版社,1993.
[2]王永庆.人工智能原理与方法[M].西安:西安交通大学出版社,1998.
[3]刘勇.非数值并行算法——遗传算法[M].北京:科学出版社,1998.
[4]徐宗本,陈志平,章祥荪.遗传算法理论研究的新近发展[J].数学进展,22000,29(2):97.
[5]刘勇,康立山.大规模推销员问题的并行演化算法[A].全国第二届数学软件与科技工程软件学术会议论文集[C].1992,A - 42 - A– 44.
[6]崔屹.图像处理与分析——数学形态学方法及应用[M].北京:科学出版社,2000.
[7]王涛,卢显良.基于遗传算法的Peer-to-Peer路由算法R-GA.计算机应用研究[D],2007(1):316-317.
[8]徐新黎.反馈神经网络优化方法及其在作业车间调度和ATM网络路由选择中的应用[D].浙江工业大学硕士论文.2003.
[9]张晓波.并行遗传算法求解应急系统最短路径的研究[D].太原理工大学硕士论文.2005.
[10]林仰峰.基于遗传算法的QoS多播路由算法的研究[D].福州大学硕士论文.2006.
[11]杨旭华.神经网络及其在控制中的应用研究[D].浙江大学博士论文.2004.
[12] Jinwook Go;Gunhee Han;Hagbae Kim.Chulhee Lee.Multigradient:a new neural network learning algorithm for pattern classification[J].Geoscience and Remote Sensing, IEEE Transactions on,Volume:39,Issue:5,May 2001, Pages:986-993.
[13] Donq-Liang Lee.Pattern sequence recognition using a time-varying Hopfield network.Neural Networks[J],IEEE Transactions on,Volume:13,Issue:2,March 2002, Pages:330-342.
[14] Suganthan P.N..Hierarchical overlapped SOM's for pattern classification:Neural Networks[J]. IEEE Transactions on,Volume:10,Issue:1 Jan.1999,Pages:193-196.
[15] Maki Y.,Loparo K. A..A neural-network approach to fault detection and diagnosis in industrial processes:Control Systems Technology[J].IEEE Transactions on,Volume:5,Issue:6,Nov, 1997,Pages:529-541.
[16] Koh Jean,Suk Minsoo,Bhandarkar, Suchendra M..A Multilayer Self-Organizing Feature Map for Range Image Segmentation[J].Neural Networks ,Volume:8, Issue:1,1995, pp: 67-86.
[17] Ching-Hung Lee, Ching-Cheng Teng. Identification and control of dynamic systems using recurrent fuzzy neural networks[J].Fuzzy Systems,IEEE Transactions on,Volume:8,Issue:4,Aug. 2000,Pages:349-366.
[18] Messmer A.,Papageorgiou M.,Azema J.,Drewanz D..A neural network approach to freewaynetwork traffic control[J].Control Engineering Practice, Volume:3, Issue:12, December, 1995,pp:1719-1726.
[19] Youshen Xia, Jun Wang.A discrete-time recurrent neural network for shortest-path routing. Automatic Control[J], IEEE Transactions on , Volume:45 , Issue:11 , Nov,2000, Pages:2129-2134.
[20] Sun Yi.A generalized updating rule for modified Hopfield neural network for quadratic optimization[J].Neurocomputing ,Volume:19, Issue:1-3, Apri1 21,1998, pp. 133-143.
[21] Pham D. T.,Oh S. J..Identification of plant inverse dynamics using neural networks[J].Artificial Intelligence in Engineering, Volume:13, Issue:3, Ju1y,1999,pp:309-320.
[22]李树涛,王耀南,张昌凡.基于燃烧火焰图象特征的回转窑神经网络控制系统[J].自动化学报,2002年04期.
[23]张军英,王德峰,石美红.基于点火祸合神经网络的多约束QoS路由选择算法[J].通信学报,2002,23(7),p40-46.
[24]王万良,吴启迪,徐新黎.基于Hopfield神经网络的作业车间生产调度方法[J].自动化学报,2002,28(5),p838-844.
[25] Simon Haykin,叶世伟,史忠植.神经网络原理[M].北京:机械工业出版社,2004.1.
[26]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[27]何兴无.基于用户行为和遗传算法的用户建模研究[D].重庆大学硕士学位论文.2007.
[28]陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社,2001年.
[29] Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems,Man and Cybernetics,1994 ,24 (4):656-667.
[30]唐世浩,朱启疆.遗传算法中初始种群与交叉、变异率对解的影响及其解决方案[J].科技通报,2001,17(3).
[31]李敏强,寇纪淞等.遗传算法的基本理论与应用[M].北京:科学出版社,2003年.
[32] B.M.Waxman.Routing of Multipoint Connections[J].IEEE JSAC 1988,6(9):1617-1622.
[33]陈燕.基于遗传算法的选播QoS路由算法研究与仿真实现[D].广西大学硕士论文.2005.
[34]王燕琳.基于QoS约束的多播路由问题研究.天津大学博士论文[D].2004.
[35]杨建军.基于遗传算法的移动IP路由和性能分析.浙江大学博士论文[D].2004.
[36]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1996.
[37]高传善,钱松荣,毛迪林.数据通信与计算机网络[M].北京:高等教育出版社,2000.
[38]施鸿宝.神经网络及其应用[M].西安交通大学出版社,1993.