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

[摘 要]文章以均衡网络业务为优化目标，提出了一种基于自适应遗传算法的资源优化路由算法，采用改进的适应度函数和自适应的交叉变异算子。理论分析表明该算法改善了最短路径路由算法容易发生阻塞及安全性不好的缺点，与基本遗传算法相比，它显着提高了收敛性能，并且具有很强的自适应能力。
[关键词]负载均衡；遗传算法；资源优化利用
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 基于自适应遗传算法的网络资源优化路由算法
遗传算法是通过模拟自然进化过程搜索最优解的方法。它将问题的求解表示成“染色体”的适者生存过程,通过“染色体”群的一代代不断进化,包括复制、交叉和变异等操作,直到满足一定性能指标和收敛条件终止,从而求得问题的最优解或满意解。对于基本遗传算法，在搜索过程的起始阶段，群体中常常有极少的个体相对于大多数个体而言适应度非常好，在比例选择下这几个非常好的个体就可能会控制整个选择过程，使得进一步进化成为不可能，从而导致所谓得“早熟”现象；另一方面，在搜索过程得后期，群体中可能还存在足够得多样性，然而群体的平均适应度可能会接近群体中的最优适应度，这时在后继代中具有平均适应度的个体和最好的个体就几乎会得到相同的复制数目，导致群体进化困难，降低了收敛速度。基于这一问题，本文拟通过一种自适应的比例变换方式来改进遗传算法，使群体能够以最快速度向最优解进化，提高收敛速度，并且避免早熟。