基于CW节约算法和遗传算法的网络优化

张赛男, 刘东亮

(1. 吉林财经大学 新闻与传播学院, 长春 130117； 2. 东北师范大学 信息科学与技术学院, 长春 130117)

作为互联网的最基础设施, 通信网络的质量和速度目前已严重影响人们的生活质量[1]. 在网络发展初期, 主要采用人工方式进行网络规划, 这在现在庞大的网络通信工程中是不可行的； 后来人们采用最小生成树方法搜索问题的全局最优解, 但随着网络通信越来越复杂, 规模越来越庞大, 该方法效果越来越不理想. 一方面最小生成树方法未考虑到实际工程的限制, 无法找到最优解, 甚至无法找到近似最优解; 另一方面, 随着网络规模的逐渐增大, 最小生成树法的耗时呈指数增长[2].

在实际网络优化问题中, 最显著的特点是网络连接未知. 模拟退火算法基本始于一个已知状态, 继而随机进行搜索, 这与网络优化问题不符[3-4]. 在进化策略中, 由于选择机制的制约, 易使算法过早收敛, 进而导致在很多情况下无法使问题得到最优解. 遗传算法的特点是以随机生成的初始种群开始, 不断地迭代, 求解适应度函数, 最终得出最佳解, 符合通信网络的优化条件. 本文提出在遗传算法迭代时, 结合CW(Clarke Wright)节约算法, 使遗传算法的收敛速度加快, 且不会影响遗传算法的随机性, 即能找到近似最优解[5].

1 通信网络优化问题模型

假设有7个通信节点需要连接, 初始连接图如图1所示. 其中, 连接线的数字为设计距离, 现需要对该通信网络图进行优化, 以最小的成本代价实现对网络的连通. 其中, 网络规划方案需要结合系统连通、 连接限制控制表和节点负载控制表等制约条件计算网络投资的大小.

2 CW节约算法

CW节约算法的思想较简单且易实现, 假设有一个中间连接节点A, 两个通信节点B,C与其进行连接, 如图2(A)所示, 则此时的连接代价为

2×S(A,B)+2×S(B,C),

如果把连接方式改为如图2(B)所示, 则此时的连接代价为

S(A,B)+S(A,C)+S(B,C),

减少的代价即为节约值, 表示为

S(A,B)+S(A,C)-S(B,C).

在所有这种通信节点中找出节约值最大的, 调整连接方式. 然后不断循环上述操作, 直到满足连通条件[6]为止.

图1 通信网络规划设计初始连接图Fig.1 Initial connection diagram of communication network planning and design

图2 CW节约算法应用通信连接前后比较Fig.2 Comparison of CW saving algorithm before and after application of communication connection

如果把CW节约算法直接应用到通信网络规划中, 该算法只能考虑到距离成本问题, 无法考虑其他限制条件, 如负载限制、 连接数量限制等[7]. 所以本文把CW节约算法和遗传算法相结合, 以加快遗传算法的收敛速度, 而遗传算法的特点是可以求适应度函数, 该适应度函数可包含所有实际工程中的问题[8].

3 遗传算法

遗传算法广泛应用于组合优化问题中, 尤其在规模庞大的组合优化问题中, 遗传算法相对于其他算法表现出更好的结果和更高的效率[9]. 遗传算法基本思想： 提出适应度函数, 作为整个种群要优化的衡量标准, 个体适应环境的能力越强, 其适应度函数值越大, 反之越小. 每个个体都是待优化的向量, 从初始种群开始, 在相应的概率下进行选择、 交叉和变异操作, 产生新的个体, 形成下一代种群, 重复迭代过程, 直到符合预期的标准. 最后, 在种群中适应度函数值最大的即为最优解[10].

下面举例描述遗传算法的过程. 给出一个函数, 求出该函数的最大值：

1) 种群个体的编码. 类似于生物的染色体带有多个基因, 遗传算法中的个体是带有多个信息段的信息串, 或者在有些应用中为多维向量. 本文采用两个三位二进制分别表示x1和x2, 将二者的组合作为种群中的个体, 且个体的取值范围为8个值, 种群个体编码列于表1.

表1 种群个体编码

2) 生成初始种群. 在实际运算过程中, 对由个体组成的种群进行运算, 所以首先要产生初始种群, 一般采用随机策略产生. 本文初始种群为4个个体, 结果列于表2.

3) 计算个体适应度. 产生初始种群后, 首先要对初始种群计算适应度函数值, 用于评判每个个体适应环境的好坏, 实际的适应度函数根据具体的应用场景设计, 本文适应度函数即为给出的待求最大值的函数, 结果列于表2.

表2 初始种群及适应度

4) 选择运算. 选择运算的过程即为遗传算法的优胜劣汰过程. 选择过程就是依据适应度大小对种群进行筛选, 较高的适应度会有较高的几率被选中. 本文采用的选择方法为函数值较大的则以一定的概率确定其被复制到下一代的个体数量. 编号为2的个体由于适应度函数值较大被选择了两次, 而其余个体则只被选择一次.

5) 交叉运算. 交叉运算是为了把整体解中较好的特征传入下一代种群. 交叉运算主要采用以一定的概率在染色体中选择交叉点, 把每个母染色体分为两部分, 然后两个染色体互换这两部分. 本文的交叉过程即为随机进行配对, 然后随机选择交叉点, 把染色体串互换即可. 交换过程如图3所示.

图3 交叉运算示意图Fig.3 Schematic diagram of cross-operation

6) 变异运算. 变异运算与交叉运算相同, 是产生下一代个体的方法, 但其模拟基因突变的过程, 主要是染色体中某段基因以极小的概率发生突变. 本文发生突变的过程是随机选择一个突变点, 然后按某个指定的突变概率, 对参数串中突变点的二进制取反即可.

7) 循环运算. 循环计算即计算上述步骤1)～6), 不断产生新一代种群, 并且记录每代种群的最佳个体, 用于判断是否满足停止条件.

8) 停止. 当在新一代种群中找到符合条件的个体, 或达到设定的最大迭代次数时, 即可停止算法. 当前找到的最佳个体即为算法最优解.

4 加入CW算子的遗传算法

在遗传算法中, 产生下一代的步骤主要是选择、 复制交叉、 突变等方式, 但其缺点是相对耗时较大, 本文提出加入CW节约算子, 作为遗传算法产生下一代的算子, 加快算法的收敛速度.

(1)

其中:x=(x1,x2,…,xn)T为目标函数的向量; f(x)为目标函数. 式(1)为约束条件, 满足该条件的解称为可行解. 遗传算法中, 将n维决策变量x=(x1,x2,…,xn)T用n个xi(i=1,2,…,n)所组成的符号串X=x1x2…xn表示. 每个xi即为一个遗传基因, 其全部可能的取值称为等位基因. X是由n个遗传基因组成的一个染色体. 染色体的长度一般为定长, 少数情况可以是变长的. 这里的等位基因可以是一组整数, 或是可行解范围内的实数,也可以是一种记号. 然后染色体进行选择、 交叉、 突变, 都在向量上操作, 其中突变是随机的选择向量的某一维参数做运算. 遗传算法由于交叉点和突变点都是随机选择的, 所以种群向较好的趋势发展, 导致算法的速度较慢. 本文提出在产生下一代时, 加入CW节约算子, 从而加快遗传算法的收敛速度. 改进后的遗传算法流程如图4所示.

图4 结合CW算子的遗传算法流程Fig.4 Flow chart of genetic algorithm combined with CW operator

改进算法的基本步骤如下：

1) 对通信网络问题进行编码;

2) 随机的初始化种群个体x0=(x1,x2,…,xn);

3) 循环：

① 判断是否有满足条件的个体, 如果有, 则退出循环, 输出最优解, 如果没有则继续;

② 应用交叉算子、 突变算子、 CW算子到种群个体中;

③ 计算种群中个体xi的适应度值F(xi);

④ 淘汰适应度较差的个体, 其余部分即为下一代种群X(t+1);

⑤t=t+1.

5 实验结果与讨论

实验对比传统最小生成树法、 传统遗传算法以及结合CW算子的遗传算法的效果, 并且对比不同节点个数的通信网络规划结果. 随着通信节点数目的增加, 不同算法的成本费用和计算速度比较分别如图5和图6所示.

图5 不同算法的计算结果成本比较Fig.5 Comparison of costs of calculaiton results of different algorithms

图6 不同算法的计算耗时成本比较Fig.6 Comparison of costs of computational time of different algorithms

由图5和图6可见, 最小生成树方法生成的最佳可行解由于只考虑了距离的成本, 所以找到的可行解较差, 基本无法使用, 且随着通信节点数量的增长, 计算时间呈指数增长. 而结合CW算子的遗传算法与传统遗传算法的可行解结果接近, 但由于CW算子的快速收敛效果, 使改进遗传算法的计算时间降低了约40%, 且随着通信节点的增长, 效率会更高. 因此, 结合CW算子的遗传算法在解决通信网络规划问题上效果显著, 运算效率更快.