基于粒子群算法的多播路由方法

摘要

本发明将粒子群算法运用于解决多播路由问题。首先，基于Floyd算法将连接网络转换为距离完全图。然后，在距离完全图的基础上运用粒子群算法搜索最佳的多播树。在粒子群算法中，将每个粒子编码为一个二进制字符串表示用以构造多播树的节点，其中“1”表示用到该节点，“0”表示不用改节点。基于二进制串，每个粒子均运用Prim算法构造多播树。将冗余的部分剪除后，就可以对构造出的多播树进行评价。实验结果显示，与传统启发式算法相比，发明的粒子群算法能得到更好的结果。

主权项

1、一种基于粒子群算法的多播路由方法，其特征在于，该方法包括以下步骤：(1)运用Floyd算法建立多播路由网络的距离完全图。(2)初始化算法的各个参数，并建立第一代的粒子群，其中，粒子的编码方式为二进制编码。二进制串的长度与网络中的节点数目相同。所有的目标节点的编码均为1，以表示这些节点一直都在多播树中。对于中间节点，如果其编码为1，则表示该节点用于构造多播树，如果编码为0则表示不用于构造多播树。用于表示粒子位置的向量如下：X_i＝[x_i1，x_i2，...，x_iN]，其中x_ij＝0或者1(3)每个粒子基于当前位置根据Prim算法构造多播树，进行冗余剪枝并计算适应值。(4)更新每个粒子的个体最优位置，以及所有粒子的全局最优位置。(5)对每个粒子执行速度更新。其中，粒子速度向量的可以表示为：$V_i=\left[\begin{array}{c}{v}_{i1}^0,v_{i2}^0,...,v_{\mathrm{iN}}^0\\ v_{i1}^1,v_{i2}^1,...,v_{\mathrm{iN}}^1\end{array}\right],$其中$0\le v_{\mathrm{ij}}^0,$$v_{\mathrm{ij}}^1\le 1$在上式中，向量V_i的第j维有两个取值。是x_ij为0的概率，而是x_ij为1的概率。(6)根据每个粒子更新后的速度执行位置更新。当决定X_i的第j维的取值的时候，首先生成一个0到1之间均匀分布的随机数α。如果和均大于α，那么就随机将x_ij设置为0或者1。如果只有大于α，那么就将x_ij设置为b。如果和均小于α，那么就不改变x_ij。(7)重复步骤(3)至(6)直到满足算法的终止条件。