主权项 |
一种基于遗传算法的光多播树最小代价路由方法,其特征在于,包括以下步骤:101、获取网络拓扑G(V,E),其中V表示网络拓扑G的节点集,E表示网络中节点之间的连接边,当连接边的容量n≥2时,则将该连接边转化为n条并列且容量为1的边,完成初始化,跳转至步骤102;102、获取步骤101中经过初始化后网络拓扑G(V,E)的源节点S及目的节点集t,构造源节点S到目的节点集t的多播树,确定源节点S到目的节点集t的最大多播速率T,并设定目的节点的接收速率为k,其中1≤k≤T;获取源节点S到目的节点ti所有存在的N条路径,其中目的节点ti为目的节点集t中的一个元素,计算出该目的节点ti的k条边路径组合的方式mi,产生基因库,并采用遗传算法构造源节点S到目的节点集t的染色体种群,每个染色体表示网络的一种路由方式,其中每个染色体由与目的节点的个数相等的U个基因组成,每个基因表示源节点S到对应目的节点ti的一种路径;103、构造步骤102中染色体的适应度函数f=a1*NC(R)+a2*NCL,且a1>a2式中,f为适应度函数值;NC(R)为满足多播请求速率的多播树的链路代价,NCL为编码链路数目;a1、a2为权重系数;当适应度函数f根据遗传算法迭代更新的次数大于或者等于设定次数N1时,则输出该最优染色体的路径及适应度函数值f,跳转至步骤106;或当适应度函数f根据遗传算法迭代更新的次数大于N2且适应度函数值f不变时,则输出该最优染色体的路径及适应度函数值f,跳转至步骤106,结束;否则,跳转至步骤104;104、采用比例选择法对步骤103中的染色体加入到初始染色体种群中,并依次经过交叉步骤、变异步骤求得最优染色体及适应度函数值;105、对步骤104中求得的最优染色体及适应度函数值代入步骤102建立的染色体种群中,删除掉适应度函数值大于该最优染色体适应度函数值的基因;106、输出最终的最优染色体及其适应度值,并按照该最优染色体所代表的 源节点到目的节点的路径进行路由。 |