基于遗传算法的最小组播路由算法-应用数学专业论文.docxVIP

摘要由于计算机网络的迅速发展，目前出现了许多新的实时性业务， 摘要 由于计算机网络的迅速发展，目前出现了许多新的实时性业务， 如多媒体业务，它对网络提出了更高的要求，既要满足实时性，又要 高效的利用网络资源。它对路由机制提出了以下要求：(1)满足时实 应用的端到端的时延要求；(2)有效的管理网络资源。当前Internet 上的路由机制主要是根据最短径算法，它只能在给定的单个代价准则 下找到基于最短时延或最多某种可用资源的路径。寻找满足时延约束 的最小代价路径是一个NP完全问题。实验表明，本文提出的基于遗 传算法的最小组播路由选择算法能够使得路由选择既能满足时延的 要求，又能够有效的管理网络资源，即可以使碍网络费用接近于最小。 本文算法是在已有文献的基础加以改进，主要是下面两方面得到 改进。首先，该算法通过改进基因的编码方案，使得算法实现简单； 其次，在遗传算法的交叉操作时，采用保留相同链路的方法，使得算 法收敛更快。通过计算机仿真实验结果说明本文算法要大大优于已有 文献算法。 关键词：QoS；组播路由算法；遗传算法；NP一完全问题；斯坦利最 小树 ABSTRACTAs ABSTRACT As the development of computer and network at present，it appears a lot of new real—time services，such as multimedia services，which need the network to guarantee the real-time requirement and the network resource efficiently．It puts forward request to routing mechanism as follow：(1)end—to—end delay constraints，(2)the network resource efficiently．Now,Internet routing mechanism according as the shortest approach arithmetic，which only can find the shortest delay constraints approach or most some available resource approach on single rule．It is a NP—complete problem to find a low-cost approach，which satisfy delay constraint．In this paper,an approach based on genetic algorithm is proposed，which finds the low-cost multicasting tree with end—to-end delay constraints and the network resource efficiently． This paper algorithm improves on literature algorithm．Firstly,this paper algorithm improves the method of genetic coding，which leads to the algorithm realization more easily．Secondly,this paper algorithm adopts keeping the same approach in crossover of genetic algorithm， which leads to the algorithm constringency more quickly．At last，it shows this paper algorithm is better than literature algorithm by the result of experiment． Keyword：QoS；multicasting approach algorithm；genetic algorithm； NP—complete problem；minimum Steiner tree 北京邮电大学硕士论文 北京邮电大学硕士论文 绪论 第一章绪论 1．1遗传算法发展现状简介 近年来，一种在思路和方法上别开生面的新的优化算法一遗传算法 (Geneti c algorithms，简称gas)正在迅速发展。遗传算法以其很强的解决问题 的能力和广泛的适应性渗透到研究与工程的各个领域，并取得