一种基于遗传框架的组播树优化方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN105978816A(43)申请公布日2016.09.28(21)申请号201610265453.6(22)申请日2016.04.27(71)申请人西南大学地址400715重庆市北碚区天生路2号西南大学计算机与信息科学学院(72)发明人高超梁鸣心张自力(51)Int.Cl.H04L12/753(2013.01)H04L12/761(2013.01)权利要求书3页说明书6页附图6页(54)发明名称一种基于遗传框架的组播树优化方法(57)摘要一种基于遗传框架的组播树优化方法，用以解决如何从根本提高GA的局部搜索能力，并且保持算法的搜索范围的问题。包括：S1、将染色体放入染色体池；S2、选择父代染色体；S3、对每一对所述的父代染色体判断是否执行交叉算子，若是，则转入步骤S4，否则，转入步骤S5；S4、保留父代相同链路的组播树，并基于保留链路计算出子代组播树；S5、判断是否执行变异算子，若是，则转入步骤S6，否则，转入步骤S7；S6、执行变异算子；S7、判断演化是否达到最大繁殖代数，若是，则转入步骤S8，否则，转入步骤S1；S8、输出优化后的组播树。CN105978816ACN105978816A权利要求书1/3页1.一种基于遗传框架的组播树优化方法，其特征在于，包括下列步骤：S1、将染色体放入染色体池；S2、选择父代染色体；S3、对每一对所述的父代染色体判断是否执行交叉算子，若是，则转入步骤S4，否则，转入步骤S5；S4、基于父代组播树中相同链路，产生子代组播树；S5、判断是否执行变异算子，若是，则转入步骤S6，否则，转入步骤S7；S6、执行变异算子；S7、判断演化是否达到最大繁殖代数，若是，则转入步骤S8，否则，转入步骤S1；S8、输出优化后的组播树。2.如权利要求1所述的基于遗传框架的组播树优化方法，其特征在于，在所述的步骤S1之前，还包括步骤：S01、初始化参数；S02、过滤链路；S03、初始化种群。3.如权利要求2所述的基于遗传框架的组播树优化方法，其特征在于，步骤S01中所述初始化的参数包括：种群数量N，交叉概率Pc，变异概率Pm，每一代产生的子代染色体数量Pn，最大繁殖代数MG；多头绒泡菌网络中初始信息素量I0，多头绒泡菌网络中每条管道初始传导性的值D0，PM收敛的传导性变化阈值β，反馈方程系数k和保留阈值η，以及保留链路权值ε。并设置源节点s和目标节点集合DE。4.如权利要求2所述的基于遗传框架的组播树优化方法，其特征在于，步骤S03所述初始化种群中，每个初始个体形成的具体过程如下：设置源节点s为当前结点c，即c＝s；从c的邻边中随机选择一条边，记为ec，b，若b不是目的节点，则更新当前结点为b，重复操作直到访问到目的节点，此时将访问过的点和边组成的子图记为T；从还未访问过的目的节点中随机选择一个节点作为当前结点c，从c的邻边中随机选择一条边，记为ec，b，若b不是T中节点，则更新当前结点为b，重复操作直到访问到T中的节点；以及将访问过的边和点并入T；此时若还有目的节点未在T中，则重新随机选择未在T中的目的节点为当前结点c，重复上述步骤，直到所有目的节点均在T中；最后基于从源节点起的深度优先遍历，将多余的边删除，得到初始的组播树，并将初始组播树编码，形成初始的染色体。5.如权利要求1所述的基于遗传框架的组播树优化方法，其特征在于，步骤S1具体是将新产生染色体放入染色体池，并将当前染色体池中的染色体按照适应度排序，并保留适应度较高的N个染色体。6.如权利要求1所述的基于遗传框架的组播树优化方法，其特征在于，步骤S2中采用轮盘选择法，在当前染色体池中选择出Pn对父代染色体。7.如权利要求1所述的基于遗传框架的组播树优化方法，其特征在于，步骤S4中所述产生保留父代相同链路的组播树，具体是产生一个与当前拓扑结构相同的网络NG，并按照如2CN105978816A权利要求书2/3页下公式设置NG中边的权值：其中Lij代表NG中边ei，j的权值，cij、分别代表连接路由i和j链路的代价和服务质量属性，wn代表对应服务质量在当前问题中的重要程度；之后对比父代染色体中的链路，将父代染色体相同链路在NG中的权值设置为ε。8.如权利要求2所述的基于遗传框架的组播树优化方法，其特征在于，步骤S4中所述计算出子代组播树，具体是将与当前拓扑结构相同的网络NG，节点s，点集DE输入多头绒泡菌数学模型，得到子代组播树，步骤如下：在多头绒泡菌模型中，设置节点s为入口，点集DE中所有点都为出口；用代表节点i在t时刻的压力值，则根据基尔霍夫定律可得到如下方程组：其中Dij表示管道的传导性，与管道直径成正比；Lij代表NG中边的权值；M代表目标节点的个数；I0代表多头绒泡菌网络中总