基于改进蚁群算法的集群负载均衡研究

摘　要：在集群负载均衡技术中，负载均衡算法的好坏直接影响负载均衡系统的性能。蚁群算法是一种很有效的组合优化算法。在蚁群算法的基础上，文章提出了一种与遗传算法相融合的基于基本蚁群算法的混合智能负载平衡算法。算法中遗传特征的引入，有效地改善了传统蚁群算法容易陷入局部最优解的缺陷，极大地提高了算法的收敛速度，有效地实现了集群的动态负载均衡。

关键词：集群；负载均衡；蚁群算法；遗传算法；混合智能

0　引言

集群技术以其高可用性等特性，近年内得到了快速发展。但现行的集群系统，大多采用静态负载均衡机制，由于影响客户访问频率的因素很多，且难以预测，静态调度往往不能令人满意，因此设计出一种高效、适用面广、稳定可靠的负载均衡算法，在计算机集群系统中就显得非常重要。此时，可以考虑根据各服务器运行时的负载情况及其它信息进行动态的负载均衡，最直观的办法是将客户请求分配给当前负载最低的成员服务器。

目前，各种负载平衡算法层出不穷，但由于这些算法往往基于特定的集群结构，因此非但不具备通用性，而且对于异构集群，造成了软件资源的极大浪费。为了解决以上问题，本文在基本蚁群算法的基础上，提出了一种比较理想的负载均衡解决方案――一种蚁群算法和遗传算法相融合的混合智能负载均衡算法。此算法以当前集群中可用节点机CPU的占用率作为系统实时负载对请求进行动态分配的依据，在蚁群算法的基础上，融入遗传算法，利用蚁群算法和遗传算法良好的全局搜索能力，将其运用到网络请求分配中，实现了一个性能优良的负载均衡系统。

1　基于基本蚁群模型的集群负载均衡算法及其实现

1．1蚁群算法

蚁群优化算法是由意大利学者M.Don20等人受到蚂蚁觅食行为的启发提出来的一种可以用来解决NP-hard问题中的离散组合优化问题的优化算法。蚁群算法以其并行性、协同工作机制、全局优化、鲁棒性和易于与其它启发式算法结合等特点，应用范围遍及到许多科学技术及工程领域。

1．2集群负载均衡

在集群负载均衡技术中，负载均衡算法是核心，它的好坏直接影响均衡系统的性能，客户端请求的分配与作业调度原理一致，所以可将多个请求分配到后台若干个服务器上处理，以使总的请求响应时间“最小化”，进而“最优化”服务器端CPU的利用率。

集群服务器动态负载均衡可以描述成：在N个新到的任务、M个节点机、各个节点机的负载状况各不相同的情况下，找到一个最优的调度方法，使得整个任务处理的时间最短，从而提高整个集群服务器系统的响应速度。由于在一次分配方案中，负载偏差率反映的是各CPU负载的总体分布规律，所以本文的目标函数就采用这个负载偏差率。目标函数可以表示如下：

ei=fi-F(X)　(2)

上式中的fi(ni，si表示在本次分配方案下，第i个节点机上分配代价的一个预测函数，其定义如下：

fi=(ni+1)×Si　(3)

式(3)中的Si为第i个节点机的CPU占用率。

式(2)中的F(X)表示系统的CPU平均分配代价的预算值，其定义如下：

负载偏差率总是在0～1之间取值，值越小，表明CPU的负载分布越均匀，系统整体的性能越高。

1．3基本蚁群算法实现

在每个任务处分别设置1个蚂蚁，如果任务分配给节点机j，j＝1，2……N，蚂蚁就在节点j上留下信息素(也就是一定的信息)，信息素的浓度越高表明该计算机完成作业的数量多，速度快，该计算机被选择的概率越大。

当有一个节点机i加入时，先初始化该资源的信息素：

令Tshartj=L，其中：shartj为初始时刻个节点机上的信息素强度，L为常数。

将任务分配给某个节点机后，如果任务完成，则该节点上的信息素信息调整公式如下：

式(5)中，newj表示信息素修改后节点机j上的信息素强度，oldj表示信息素修改前节点机j上的信息素强度，p表示信息素挥发系数(取0.2)，1-p则表示信息素残留因子，Tj表示在本次任务分配中节点机j上的信息素的增量。初始时刻，shartj=L，T=0。式(6)中，TKj：表示第k只蚂蚁在本次循环中在节点j上释放的信息素强度，其中k=1，2……N。

式中，Q表示蚂蚁循环一周后释放在所经过节点上的信息素总量。

根据任务的完成情况，相应节点机的信息素信息也在跟着发生变化，则在资源列表中，节点机j被选中的概率pi为

式中，n为资源快表中的资源数；Tj节点机j的信息素浓度；ηj为启发函数，每个节点机的启发值取该节点机当前CPU占用率的倒数；α表示信息素的重要性；β为启发信息在蚂蚁选择路径中的相对重要性。

2　经遗传算法改进的算法

蚁群算法虽然是一种很有效的组合优化算法，但也有其不足，收敛速度不够快就是一个主要方面。导致收敛速度慢的一个主要原因是：在蚁群搜索初期，由于信息素之间的差异不明显，信息素对蚁群搜索方向的指导作用不强，因此蚁群搜索呈现出较大的盲目性。

本文在基本蚁群算法的基础上结合遗传算法，利用他们各自的优点，提出了一种经遗传算法改进的混合智能算法。该算法引入了简单遗传算法中的选择、交叉、变异三种基本的操作，以充分利用现有的信息，进行蚂蚁之间关于路径的信息交换，扩大搜索范围，加大信息素对蚂蚁搜索方向的指导作用，加快搜索速度、减少陷入局部最优的可能性；还增加了一种替代操作，用通过蚁群搜索得到的解替代种群中的若干较劣个体，这种替代操作不仅会减少搜索进入停滞阶段的可能性，而且能够整合共享各种群的优良基因，改良种群，加快种群的进化速度，

改进算法的实现流程描述如下：

a．设定遗传参数和蚁群搜索参数，产生初始种群；

b．置每只蚂蚁到初始节点；

c．对所有蚂蚁计算概率p，确定每只蚂蚁要转移的下一个节点；

d．按式(2)以局部更新规则对各节点的信息素进行更新；

e．循环执行c、d步，直至所有蚂蚁都走完所有节点，然后再执行下一步：

f．比较这次循环的结果，若目标函数E(X)有所改进，则当前分配方案为最佳方案，对各个节点上的信息素按全局更新规则进行更新，否则，分配方案不改变，各节点的信息素采用上次 最好分配方案时的信息素；

g．判断算法收敛条件是否满足，若满足，则转到l，否则执行下一步；

h．进行替换操作，用通过蚁群搜索得到的解替代种群中的若干较劣个体；

i．根据适应度大小以一定方式执行选择操作，按交叉概率执行交叉操作，按变异概率执行变异操作；

j．根据搜索结果按全局更新规则对各个节点上的信息素进行更新；

k．转到c；

l．结束，输出结果。

算法的结束条件为：①目标函数值小于某一给定常数A(A取0.15)；②目标函数值连续B次无明显改进(B取5)；③整个搜索过程循环次数超过给定最大循环次数C(C取50)。以上三个条件中的任一个条件满足时，计算结束。

改进后的算法中，遗传算法为蚁群搜索提供最优个体，用算法中得到的带有先验信息的结果修改信息素信息，能使蚁群算法更快达到最优解；用蚁群算法的结果对种群进行优化，也极大地增加了种群的进化速度。两种算法结合，虽然使整个搜索过程的复杂度有所增加，但是，这两种算法的相互融合，相互促进，不但能加快整个算法的收敛速度，而且能有效地保证算法的收敛。

改进算法中用到的相关函数和算子如下：

(1)适应度函数

根据适应度函数设计要求，本算法中的适应度函数为：

g(X)=I-E(X)　(9)

它的取值在0～1之间，值越大，表明该染色体的适应度越好，对应的请求分配方案被选中的概率越高。

(2)选择操作

本算法中用到的选择操作是典型的赌方法。每个染色体占有一个槽，第一个染色体的槽的范围为0到它的适应值，以后每个染色体的槽的范围为上一个染色体的槽的上界到这个值加上自己的适应值。

(3)杂交操作

按照一定的交换概率Pc，从群体中选出一个个体，然后随机地选出个体上的交叉点赋给不同的字符值(基因)，交换它们的值；即对一个被选中的分配方案中的两个服务器上分配的任务数进行交换，从而产生新的分配方案。本处取Pc=0.8。

(4)变异操作

变异操作不能随便改变某个染色体的基因值，否则就会产生错误的调度方案，可以按照一定概率Pm随机地改变染色体的宇符值。操作时，在选中的一个个体中，任意选取个体的两个不同的字符，对其进行交换操作，从而产生新的个体。本处取Pm=0.05。

变异操作只有在停滞状态下才进行。当循环在近一段时间内所产生的最优路径没有变化的时候称为停滞状态。

3　算法分析

为了检验算法的有效性，我们在C环境下对算法进行了模拟测试。该实验旨在测试算法的搜索能力。为了在PC机上模拟网络环境，预先设置了5个可用节点机，15个待分配的任务。初始时刻，设置5个节点机的CPU占用率各为5％，20％，35％，45％，60％，分别用基本蚁群算法模型和经遗传算法改进的算法进行模拟。达到收敛所需的循环次数和目标函数值的比较如表1所示。

由试验结果对比分析可知，在目标函数值相近的情况下，改进后算法的循环次数大大减少。

4　结束语

本文根据基本的蚁群算法模型提出了一种蚁群算法与遗传算法相融合的算法模型，由于遗传算法的引入，有效地改善了传统蚁群算法容易陷入局部最优解的缺陷，极大地提高了算法的收敛速度，使算法具有更好的全局搜索能力和更快的收敛速度。通过比较分析可以看出，改进算法可以弥补蚁群算法自身存在的不足，提高负载平衡，有效地解决集群的负载均衡问题。

本文创新点：

(1)把节点机负载偏差率作为目标函数，并把该目标函数小于某一给定值作为算法收敛的条件。

(2)在传统蚁群算法的的基础上，融入了遗传算法，利用遗传算法的进化结果修改各节点信息素，加大了信息素对蚂蚁搜索方向的指导作用，加快了整个算法的收敛速度。