电子产品世界

　　遗传组播路由算法

　　算法描述

　　1.求出从源节点到每个目的节点记为DestSet[i]满足式4的路径，并通过K-shortest方法获得组成备选路径集合，记为PathSet。其中的K-shortest方法采用Dijkstra算法[4]在原图中求两节点间的最短路径，然后依次删除最短路径上的边，每删除一条边就生成一个子图，再在子图中用Dijkstra算法求最短路径，所有子图中的最短路径计算完毕后，对这些路径进行排序，选择最短的一条，就对应原图中的次短路径。依次类推，可求得第k最短路径。

　　2.从备选路径集合PathSet中依次选取路径组成一个组播树，通过遗传算法搜索最优组播树。下面给出求解组播树的遗传算法(GA)中的算子设计。

　　算子设计

　　编码：采用按路径编码的方案，这其实是一种整数编码法。编码以组播树作为染色体，以路径作为基因，一棵组播树由从源节点到各目的节点的路径组成。采用K-shortest算法计算出符合时延约束的备选路径集P={P1,P2，... ，Pm }，Pi={Pi0,Pi1，... ，Pi k-1 } (m为目的节点数)。用染色体Chrome表示一棵组播树，其编码长度为|DestSet| ，每个基因位Chrome[i]的取值为0 ~ (k-1)之间的任一整数，对应DestSet[i].PathSet中的一条路径。

　　适应度函数：适应度函数是遗传算法用来判断个体好坏的衡量尺度，该算法中组播树费用和越小，其适应度值应当越高。这里将适应度函数定为：

　　产生初始种群：种群记为ChromeSet。其中的每个个体ChromeSet[i](i∈0 ~ PopScale-1，PopScale是种群规模)也即Chrome采用随机产生的方式，具体方法为：将一个随机整数RAND∈[0, k-1]赋给Chrome[j]，( j∈0 ~| DestSet | -1)。

　　选择算子：算法采用轮盘赌选择机制，选择概率 PS 取区间[0.5,1)内的值。

　　交叉算子：算法采用单点交叉。首先选择一对染色体ChromSet[i]，ChromSet[j]，随机产生一个0~(k-1)之间的整数作为交叉点，然后交换这对染色体在该位置的基因值。

　　变异算子：变异概率Pm取区间[0.1,0.2)内的值。变异时按变异概率对每个个体ChromSet[i]的每个基因位赋0~(k-1)之间的随机整数。

　　算法复杂度分析

　　复杂度为搜索备选路径的时间复杂度和利用遗传算法求解最优组播树的时间复杂度两部分。假设网络节点总数为n，目的节点数为m，搜索备选的时间复杂度为利用遗传算法求解的时间复杂度为其中gen为算法迭代次数，Popscale为种群规模，L为染色体串的长度，因此算法总的时间复杂度为

关键词： 遗传算法 组播路由 201011