基于自适应遗传算法网络资源均衡与优化

　　 [摘 要]文章以均衡网络业务为优化目标，提出了一种基于自适应遗传算法的资源优化路由算法，采用改进的适应度函数和自适应的交叉变异算子。理论分析表明该算法改善了最短路径路由算法容易发生阻塞及安全性不好的缺点，与基本遗传算法相比，它显著提高了收敛性能，并且具有很强的自适应能力。

[关键词]负载均衡；遗传算法；资源优化利用


1 引 言

传统的Internet路由协议默认的总是使用最短路径转发数据分组，常常导致网络上的流量分布不平衡,使得网络上有些链路因为过负荷产生拥塞现象，而另一些链路资源却处于闲置状态,增加丢包率和恶化资源利用率。流量工程的主要目的就是优化资源利用率，提高网络性能，增加网络的健壮性。使在满足业务质量要求的前提下，使网络中的资源得到全面合理的利用，尽量避免出现一部分资源被过度利用而另一部分资源却没有被充分利用的情况。

在流量工程研究之前，普遍采用的静态路由配置方法是使用手工配置或简单的路由算法，如最短路径算法，但随着网络的日益复杂，原先的配置方法已经无法适应现有的网络环境，而且由于每次只能配置一条LSP，不能使网络达到全局的优化，由文献知，在静态业务下可为多条LSP同时分配网络资源,使网络资源达到优化利用。本文将具有强约束条件的网络资源均衡与优化的问题转化为组合优化的最短路问题，并设计利用一种改进的遗传算法进行一定迭代数使其以最快速度得到最优解。

2 网络模型假设及衡量指标的数学描述

一个网络可以数学表示为一个有向图G（V，E），其中V为网络节点的集合，E表示路由器之间的链路集合。假设网络的链路数为n，即 =n，链路l的带宽容量是。设所要配置的路径组为LSP＝（，，…，）, 为其中一条要配置的路径(1



网络资源优化的一个重要指标是让网络中每个链路的资源利用率保持在一种趋于平衡的状态，使得网络对请求的接受率尽量高。因网络预留带宽为，设为第i条LSP的带宽需求。设 为第i条LSP中链路l的剩余带宽（=-），则有链路l的资源空闲率：

=

如果1，则表示链路几乎被占满，此链路不安全。当<<1时，说明链路l还有很多剩余带宽可供使用，这条链路是安全的。当>1时，此链路不能满足要求。

通过可以求出网络中链路的资源空闲率的均值，即：

=

　　该文用网络负载平衡度来表征网络各链路的资源空闲率相对于均值的偏离程度，记为DU ,显然有DU的值越小，负载越均衡。所以网络资源优化的问题转换为在消耗网络资源较少情况下，尽量使网络负载保持均衡即DU最小，其数学公式描述如下：

DU=

3 基于自适应遗传算法的网络资源优化路由算法

遗传算法是通过模拟自然进化过程搜索最优解的方法。它将问题的求解表示成“染色体”的适者生存过程,通过“染色体”群的一代代不断进化,包括复制、交叉和变异等操作,直到满足一定性能指标和收敛条件终止,从而求得问题的最优解或满意解。对于基本遗传算法，在搜索过程的起始阶段，群体中常常有极少的个体相对于大多数个体而言适应度非常好，在比例选择下这几个非常好的个体就可能会控制整个选择过程，使得进一步进化成为不可能，从而导致所谓得“早熟”现象；另一方面，在搜索过程得后期，群体中可能还存在足够得多样性，然而群体的平均适应度可能会接近群体中的最优适应度，这时在后继代中具有平均适应度的个体和最好的个体就几乎会得到相同的复制数目，导致群体进化困难，降低了收敛速度。基于这一问题，本文拟通过一种自适应的比例变换方式来改进遗传算法，使群体能够以最快速度向最优解进化，提高收敛速度，并且避免早熟。


3.1染色体编码

这里将对应终端节点对（, , ）的所有满足约束条件的路由组成的集合称为(1
例如，如果要建立4条LSP，每条LSP有3条备选路径，则个体1234(即=(1224))表示LSP1选择第1条备选路径，LSP2选择第2条备选路径，LSP3选择第2条备选路径，LSP4选择第4条备选路径。编码确定后，随机产生一组个体组成初始群体。

3.2适应度函数的选择

首先求出每个个体的适应度函数f(x)=DU,再利用公式F(x)=f(x)-β。

其中f(x)变换前的适应度；

变换前的适应度的最小值；F(x)变换后的适应度；　　

β———自适应控制参数；β＝0.9-(-)/；

其中———变换前适应度的最大值。

当群体种个体差异很大时，即(-)/ >0.9时，β为负数，此时个体适应度增大，并且相对于适应度小的个体来说，其增长的幅度较大，从而保证差的个体也有机会进化；当群体种的个体差异很小时，即(-)/0时，此时β0.9，导致所有的个体适应度下降，整个群体的平均适应度也下降，并且拉大了个体之间的差异，有利于向更优的解进行

3.3选择算子

选择的基础是对群体中个体适应度的评价。采用比例选择法结合最优个体保存策略。比例选择法,也称轮盘赌选择法。在该办法中，各个个体的选择概率与其适应度值成比例。设群体规模大小为S，个体x的适应度为F(x)，则个体x被选中的概率用如下公式计算。

　　

适应度越高的个体被选中的概率也越大,反之亦然.由于这种方法是基于概率选择,存在统计误差.因此结合最优保存策略,来保证当前适应度最好的个体能够进化到下一代,不被遗传操作的随机性破坏掉,保证算法的收敛性.

3.4 自适应交叉算子与变异算子

设计交叉和变异算子的两个原则是：

3.4.1 不要太多地破坏群体中表示优良性状的优良模式，以保证算法的收敛性；

3.4.2 能够有效地产生出一些新的个体模式，保持群体的多样性，避免陷入局部最优解。根据与调整适应度同样的思想，也可以对交叉率和变异率进行自适应调整。取=(0.9-β), 的取值范围为[0,1]。由计算公式知当个体差异较大时，Pc取值较大，这是因为较优的个体比重大，从而经交叉后产生更好的解可机率也大，以加快寻优过程；而差异小时，则减少交叉率，避免多余的计算。而取变异率=0.01*(0.1+β), 的取值范围为[0,0.05]。变异的作用在于保持群体的多样性，由公式知当个体差异较大时，较小，可保持群体多样性；而当个体差异小时，较大，以向更广的解空间进行搜索，避免落入局部极少点。这种随适应度自适应变化的交叉变异算子一方面能保持群体整体朝适应度高的方向进化，提高算法收敛效率，另一方面，当群体中的个体差异不大时，增大变异率，避免早熟。

　　4 算法复杂性分析与正确性验证

上面算法的关键步骤是利用Dijkstra算法找出满足带宽约束的从源节点s到目的节点d对之间的最短路径、第二最短路径、…、第k最短路径。由文献知，网络中计算最短路径的复杂度是O()，计算第二最短路径的复杂度是O(),…，计算第k最短路径的复杂度是O()。根据网络的带宽需求和实际的预留带宽，该算法的计算复杂度取决于算法实现中所确定的需要计算的第k条最短路径的复杂度即O()。为避免算法复杂度过高，可以根据实际需要和时延的限制，指定k的取值范围。

算法正确性的验证：该算法是应用负载平衡度作为衡量链路负载指标，其所选路径尽量让负载分布均衡，远离拥挤区域。在尽量减小网络资源消耗的基础上，充分考虑了网络的负载平衡，达到了优化网络资源的目的。

5 总 结

本文利用文献所提出的算法基本思想，对其进行改进，设计一种自适应的遗传算法来实现网络的资源优化利用。该算法简单，高效。与最短路径算法和基本遗传算法相比，性能更稳定，并且提高了算法效率以及优化性能，因此该算法将在网络资源优化利用中具有一定的理论和实际意义。



[参考文献]

[1]杨帅，郑有才．一种基于遗传算法的资源优化利用路由算法[J]．计算机应用，2003，(23).
[2]谢政，李建平着．网络算法与复杂性理论[M]．长沙：国防科技大学出版社，1995.