求解网络编码优化问题的混合启发式算法*

徐志翔 杨余旺 郭利强 牛晓春 肖高权

（1.南京理工大学 南京 210094）（2.兵器淮海工业集团有限公司 长治 046000）（3.兵装云箭集团有限公司 怀化 419503）

1 引言

A.Rhlswede等在2000年提出网络编码（Network Coding）的理论，其主要思想来源于图论中著名的最大流最小割理论［1］。不同与传统的网络传输技术中中间节点仅负责转发信息，网络编码赋予中间节点编码和转发的功能，即中间节点从各个输入链路中获取信息并进行编码，然后把编码后的数据传输给所有输出链路［2］，更好地利用网络带宽，增大网络吞吐量。但网络编码同时也带来了编解码的开销。因此，如何在保证网络编码带来优势的同时，将随之带来的资源损耗将降低就成了一个研究的热点问题。

网络编码优化［3］是指在给定的网络拓扑下，针对优化的目标，在保证达到理论多播速率［4］的前提下，尽可能地降低网络编码的开销。文献［5］证明了网络编码优化问题是NP难问题，并使用传统遗传算法优化网络编码以求得最小编码边方案。但是随着网络拓扑的复杂度提升，算法运行时间倍增，得到解的质量下降。文献［6］将模拟退火算法融合到网络编码优化领域，提出基于模拟退火遗传算法的网络编码优化方案，该算法一方面采用了模拟退火的个体接收策略保证了种群多样性，另一方面用网络转移矩阵指导遗传操作，提高了收敛速度。文献［7］将多目标优化理论和小生境遗传算法融合到网络编码优化领域，提出基于多目标小生境遗传算法的网络编码优化方案，在设计适应度函数的适合引入了多目标优化的概念，兼顾了最小化编码边数和带宽利用率。虽然这些算法优化了传统的遗传算法，但是遗传算法局部搜索能力不足的问题还是没有得到有效解决。

在上述的研究基础上，本文提出一种求解网络编码优化问题的混合启发式算法，算法结合了遗传算法并行的大规模搜索能力和局域搜索能力强的禁忌搜索算法。实验表明，相比传统GA算法，能有效得出最少编码节点方案，加快了收敛速度，降低网络编码的开销。

2 网络编码优化模型

2.1 网络优化模型

为了方便研究，我们做出如下约定：

1）G=（V，E）表示一个单源有向无环网络，其中V节点集合，E是边集合，Rj是网络的宿点，|R|表示宿点的个数，h表示最大理论传输容量，Ni是编码节点标识。

2）G（V，E）中每条边拥有单位传输速率，即单位时间内可传输单位数据。

3）采用随机线性网络编码［8］，编码操作是基于有限域的线性操作。对于每个节点v，分配一个节点编码向量，标识该节点输入链路的编码情况。

4）将需要进额外编码操作的节点称为编码节点，不需要进行编码操作的节点称为普通转发节点。

5）输出链路传输的信息是由各输入链路上传输信息的基于有限域运算的线性组合，这种组合的系数所构成的向量称为该链路的局部编码向量。输出链路的信息相对于源节点的各信息分量的一个映射系数称为该输出链路的全局编码向量。

则对于宿点Rj的h条输入信息流，传输的信息流向量可表示为公式：

目标函数：编码节点的总数最小，即

约束条件：达到网络的组播速率即

2.2 图分解法

对一个网络拓扑中的中间节点分为两类，第一类为入度为1的中间节点，显然这种节点是不需要编码的。第二类为入度大于等于2的中间节点称为汇点。针对汇点，当出度大于1后，无法确实其是否需要执行编码操作以及需要编码操作时如何编码都是不可确定的，因此，我们参考文献［9］提出的图分解法。假设一个汇点有N个输入，有M个输出，其中N＞1，M＞1，则引入N个输入辅助节点，M个输出辅助节点，把汇点的N个输入连接在对应的输入辅助节点上，M个输出流连接到对于的输出辅助节点上，同时，每个输入辅助节点连接所有的输出辅助节点。具体如图1所示。

图1 图分解法

2.3 节点的编码

在有向图G（V，E）中，针对所有汇点，我们为汇点的输入链路分配二进制编码向量，用来标识该输入链路是否参与编码运算。

如图2，汇点v1入度为3，分别是i1，i2，i3，出度为1，所以该汇点的编码向量用三位的二进制向量表示。当汇点v1的编码向量为（1，0，0）时，表示只有链路i1参与编码运算。若编码向量为（1，1，1）时，则表示三条链路上的信息全部参与编码运算。当整个网络中的所有汇点的二进制编码分配完毕后，整个网络的信息流进而得以确定。

图2 编码向量为（1，0，0）的节点

3 遗传算法

遗传算法［10］是一种模拟自然界生物演化过程的计算模型，最先由美国的Holland教授提出。遗传算法具有很好全局搜索能力，不会陷入类似梯度下降算法致使快速下降引发的局部收敛陷阱，是一种运算简单、能有效解决问题的普适方法。但是，传统的遗传算法同样存在不少缺点，例如局部搜索能力差，容易早熟，无法收敛于全局最优解。其主要起影响作用的遗传操作主要有选择算子、交叉算子、变异算子，下面我们对主要传统的遗传算法的主要算子和适应度函数进行说明并进行初步的优化。

图3 传统遗传算法

3.1 选择算子

本文算法中选择算子采用轮盘赌选择方法（Roulette Whell Selection）。轮盘赌选择方法属于一种回放式的随机的采样方法，它的基本思想就是个体适应度值在整个种群中适应度值总和的占比决定该个体进入到子代种群的概率。即产生一随机数p，p∈（0，1），若

则个体i被选中，其中fitnessj为个体j的适应度值，N是种群的大小。

3.2 交叉算子

遗传算法中，交叉率选择对于遗传算法的性能有着重要的影响。当交叉率过大时，不利于精英种群基因的传承而当交叉率过小时，又不利于产生新解。因此，不同于传统遗传算法采用常数交叉率，本文算法采用自适应交叉率，每个个体都以一定的交叉率进行交叉运算，第i条个体的交叉率Pc的计算公式如下：

其中c1、c2是大于1的常系数，fitnessmax，是种群中最大的适应值，fitnessavg是最种群中平均适应度值。

针对网络编码的场景，交叉运算采用单元交叉，以节点的编码系数为单元，即随机地找出一个节点，交换两个相互配对染色体的该节点的编码系数。这种方法实现简单且也能使得子代保留父代基本特征。

3.3 变异算子

同交叉算子，当变异算子的变异率过小时，不利于新解的产生，过大时，效果则趋向于随机算法，失去原有的意义。因此，采用自适应变异率，每个个体都以一定的变异率进行变异运算，第i条个体的变异率Pc的计算公式如下

其中m1、m2是大于1的常系数。

变异是指对每个个体编码串随机地指定一位或者几位基因位以一定的变异概率进行变异的运算。本文的变异运算采用取反运算代。变异运算对于改进遗传算法的局部搜索的能力及维持种群多样性，并防止早熟现象的出现都有比较好的效果。

3.4 适应度函数

在遗传算法中，适应度函数用于评价染色体性能优劣的指标，需要结合具体求解问题来进行设计，是整个遗传算法的核心。本算法除对满足约束条件的解进行区分外，针对不满足约束条件的解，根据能解码的目标节点个数进行区分，对染色体i，其适应度函数设计如下：

其中G（i）是在i满足约束条件下，能解码的目的节点数，N是网络总结点数，T（i）是指需要编码的网络节点，C1、C2为常数。

4 改进的遗传算法

针对遗传算法长于全局搜索短于局部搜索的特点，我们引进了禁忌搜索算法。禁忌搜索（Taboo Search TS）由Glover于1989年提出的一种基于局部搜索的算法［11～12］，是一种高效的逐步优化算法。相对于一般的局部搜索来说，为避免无效的重复搜索，禁忌算法模拟人类大脑中的记忆功能，引入了禁忌表的概念，通过禁忌表记录近期访问过的解，在一定时间内禁止访问该解，进而更快地搜索更大范围的解空间。禁忌搜索的伪代码如表1所示。

表1 禁忌搜索算法伪代码

禁忌搜索虽然搜索能力比较快且易于实现，但是它的性能优劣很大程度上依赖初始解的质量，如果初始解质量较差，也会容易陷入局部最优解。同时，禁忌算法作为一种串行算法，即它的运算过程是一个解向另外一个解转化的过程，相对遗传操作来说迭代次数多，计算时间长。而遗传算法在初期迭代时，群体在解空间的分布还不是很稳定，如果在初期就是用禁忌局部搜索，会导致计算量过大，花费较大的时间成本，而且得到的解的质量也不高。

因此，本文提出了一种基于改进遗传算法的网络编码节点最小化算法。该算法主要引入了禁忌搜索，将长于全局搜索的遗传算法和长于局部搜索的禁忌搜索算法结合，即首先利用遗传算法进行全局搜索，使群体中的个体相对稳定的分布在解空间的大部分区域，然后用禁忌搜索算法进行局部搜索以优化解的质量。该算法有效整合了传统遗传算法并行大范围搜索能力和禁忌搜索优秀的局部搜索能力，大大降低了局部收敛的可能性，提高了全局收敛性能。其算法流程下所示。该混合策略的计算过程如下。

步骤1：设置相关参数，种群population，最大迭代次数T，禁忌搜索触发持续代数S，当前迭代代数t=0，最大适应值持续代数BestfitConAlg=0；

步骤2：确定编码方式，产生初始种群；

步骤3：计算每个个体的适应值，保存最大适应值的个体进入新的种群；

步骤4：t++；如果满足触发禁忌遗传算法的条件，执行步骤9，否则执行步骤5；

步骤5：采用轮盘赌选择进行选择操作；

步骤6：采用自适应交叉概率选择个体执行单元交叉操作；

步骤7：采用自适应变异概率选择个体执行变异操作；

步骤8：如果满足终止条件，停止运算，否则，转而执行步骤4；

步骤9：t++；调用禁忌搜索算法，对种群的每个个体进行局部搜索；执行步骤4；

步骤10：如果满足终止条件，停止运算，否则，转而执行步骤8。

其中，触发禁忌遗传算法的条件：

当BestfitConAlg==S时，触发一次禁忌搜索，每触发一次S值降低一半，BestfitConAlg=0s；当最大适应值改变时，S恢复初始值，如图4所示，假设初始S值为20。

图4 S值变化图

在0～10次中，最大适应值不变时，每执行一次禁忌算子，S值将为一半，当降至0时，即一直执行禁忌算子。当最大适应值改变时，S值恢复初始设定值。

5 仿真

为验证改进算法的有效性，本文设计了仿真实验，通过不同网络拓扑和不同算法的实验结果对比，验证了本算法的有性能。

5.1 实验环境与实验数据集

本文仿真环境为Dell PC机，处理器为Intel（R）Core（TM）i5-3210M CPU@2.50GHz，内存为4.00GB，操作系统为64位Win7系统，对2～4层蝶形图扩展网络从算法有效性、运行时间及收敛性方面与传统遗传算法进行仿真比较分析。3层蝶形图扩展网络如图5所示。

图5 三层蝴蝶网络模型

5.2 实验结果与分析

表2给出了本文算法和传统的遗传算法在3组网络拓扑结构下多次实验得到的平均值，即在保证最大组播速率的前提下，所需编码的最小节点数。从表中我们看出相对与传统GA算法，本文算法能有效地得出最小编码节点数。

表2 本文算法与传统遗传算法有效性验证结果比较

为了分析和比较算法的收敛性能，实验中记录了三层蝴蝶模型的网络拓扑下，群体最佳适应度的变化情况。从图6我们看出，传统的遗传算法适应度增长速度比较缓慢，40代的时候发生突变，表明搜索到符合约束的解。80代的时候传统的遗传算法收敛于局部最优解。改进后的遗传算法适应度增长速度明显较快，但是在70代左右时仍然收敛于局部最优解。本文提出的混合禁忌改进遗传算法适应值稳步上升，并在140代后达到最优解。这是因为本文算法引入了禁忌算法，弥补了遗传算法局部搜索能力不足的缺点，有效结合了遗传算法出色的并行大范围搜索和禁忌搜索出色的局部搜索能力，提高了解的质量。

图6 收敛性能比较

6 结语

本文在代数网络编码的框架下提出了网络编码优化模型，在此模型基础上给出了一种求解网络编码优化问题的混合启发式算法。本文算法是在传统遗传算法的基本之上，针对遗传算法的不足引入了一些新的解决措施，减少无效的遗传操作，提高了遗传多样性；设计了新的适应度函数，将没有达到约束条件的解根据能解码的目的节点的个数进行区分，提高了种群的多样性。最后，引入了禁忌算法，改进了遗传算法局部搜索能力不足的缺点，有效避免了算法的局部收敛。实验结果表明，本文算法在达到理论多播速率的基础上，能有效得出最小编码节点数，降低网络编码的编解码开销，同时提高了收敛速度，解决了遗传算法在网络编码应用中的陷入局部最优的问题，展现出的性能明显优于传统遗传算法。