基于遗传模拟退火算法的网络负载平衡研究

摘要：介绍了网络负载平衡的基本算法，建立了负载平衡的数学模型，重点阐述了遗传算法和模拟退火算法相结合的重要意义。并提出将遗传模拟退火算法应用于解决网络负载平衡问题的算法，通过实例证明了其有效性。

关键词：网络负载平衡；遗传模拟退火

中图分类号：TP311 文献标识码：A文章编号：1009-3044(2008)17-21415-03

网络负载平衡是分布式作业调度系统的一种实现。在并行分布计算中，负载平衡牵涉到把一个问题分成一系列能够并行处理的小任务，并且把每一个任务分配到合适的计算资源上，这样的计算资源有可能是一个处理机，也有可能是一台计算机。当作业量不断增加的时候，就有可能出现有的处理器或计算机因系统负担过重而导致性能下降或者死机，而有的处理器则因空闲而浪费资源。网络负载平衡研究的目标就是如何研究一些可以将负载平衡地分配给网络内的各个处理器（计算机）的策略方法，使得整个问题的处理时间减短，而计算资源的利用率得到最大化的利用。

1 负载平衡问题的数学模型[1]

负载平衡问题的数学模型可以描述为：假设系统由M台处理计算机组成，依次标记为p0,p1,…,pM-1，处理机之间通过线路进行连接，为了便于评测系统的平衡性，用每台处理机所拥有的数据数来表示其负载，记为w[i]，整个系统的总负载可表示为w=∑w(i)，其中0≤N-1，系统的平均负载为w*=W/N。

2 遗传模拟退火算法

遗传算法和模拟退火算法是较为常用的两种智能优化算法，而且各有优缺点，将这两种算法有机地结合在一起，应用于网络负载平衡问题的解决，会取得更好的结果。

2.1 遗传算法

遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接收，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到了广泛的应用。遗传算法给我们呈现出的是一种通用的算法框架，该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。隐含并行性和全局搜索特性是遗传算法的两大显著特征。

2.2 模拟退火算法

模拟算法是基于Mente Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

在金属热加工工艺中，退火是指将金属材料加热到某一高温状态，然后让其慢慢冷却下来这样一个金属热处理过程。从统计热力学的观点来说，随着温度的降低，物质的能量将逐渐走近于一个较低的状态，并最终达到某种平衡。

模拟退火算法就是基于金属退火的机理而建立起的一种全局最优化方法，它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。

2.3 遗传算法与模拟退火算法的结合

遗传算法由于其运算简单和解决问题的有效能力而被广泛应用到众多的领域。理论上已经证明，遗传算法能从概率的意义上以随机的方式寻求到问题的最优解。但另一方面，应用实践表明，在遗传算法的应用中也会出现一些不尽人意的问题，比如收敛较慢且易陷入局部极值点。另外，遗传算法也无法避免多次搜索同一个可行解，这也是影响遗传算法运行效率的一个因素。

另一方面，梯度法、爬山法、模拟退火算法、列表寻优法等一些优化算法却具有很强的局部搜索能力，而另一些含有问题与相关知识的启发式算法的运行效率也比较高。比如模拟退火算法对具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解。可以预计，在遗传算法的搜索过程中整合这些优化方法的思想、构成一种混合遗传算法(Hybrid Genetic Algorithm)是提高遗传算法运行效率和求解质量的一个有效手段。

遗传模拟退火算法的结构如图1所示：

遗传模拟退火算法可以理解为在遗传算法中引入模拟退火算法的思想，这有效地缓解了遗传算法的选择压力，并对基因操作产生的新个体实施概率接受版图，不但增强了算法的全局收敛性，而且使算法在优化后期有较强的爬山能力，加快了进化后期的收敛速度。另一方面，遗传模拟退火算法以遗传算法控制寻优的方向，发挥搜索速度快的特点；而用模拟退火算法解决局部收敛的问题，以提高搜索精度。充分发挥了遗传算法的快速全局搜索性能和模拟退火算法的局部搜索能力，因此具有较高的效率和广泛的适用性。

2.4 遗传模拟退火算法的基本步骤

简单地说，遗传模拟退火算法的特点在于利用模拟退火算法克服遗传算法的早熟问题，利用遗传算法克服模拟退火算法对初值的依赖性。以下是该算法的一种基本结：

(1)给定群体规模n,k:=0；初始温度tk:=t0，群体pop(k)；

(2)若满足停止规则，则停止计算；否则，在群体pop(k)中每一个染色体i∈pop(k)的领域中随机选一状态j∈N(i)，按模拟退火中的接受概率Aij(tk)： (1)

接受或拒绝j，其中f(i)为状态i的目标值，其中f(j)为状态j的目标值，这一阶段n次迭代选出新群体newpop1(k+1)。

(3)在群体newpop1(k+1)中计算适应函数fi(tk)：

(2)

其中fmax是newpop1(k+1)中的最大适应值；按由适应函数决定的概率分布从newpop1(k+1)中随机选n个染色体形成种群newpop1(k+1)。

(4)按遗传算法的常规方法进行交叉得到crosspop1(k+1)；再变异得到mutpop1(k+1)。

(5)Tk+1=d(tk)，k=K+1， pop(k)=mutpop1(k+1)，返回第二步。

在遗传模拟退火算法中，在第二步的群体选择时随机搜索了每一个体的领域，选择的范围比单纯的遗传算法要大，实际上是用所有个体的领域取代遗传算法中的 ，而且采用Metropolis准则由式(1)所确定的概率选取，这是模拟退火的一个显著特征。式(2)是一个加速适应值尺度变换函数，在温度较高时加速性不明显，当温度较低时加速性非常显著，是根据退火的第二个特征。第四步中的交叉和变异操作与一般遗传算法中的处理方法一致。

3 应用实例

在这一小节中，我们将用一个实际的例子来说明遗传模拟退火算法在网络负载平衡中的应用。

假定我们在一个拥有4台服务器的网络中对16个任务进行网络负载平衡的规划，并且这16个任务各自独立，相互之间没有依存关系，同时这16个任务完成所需要的时间各不相同。

设定实例的任务编号，所需时间如表1所示。

3.1 编码

利用遗传算法求解优化问题时，先要将实际问题转换成由基因按一定结构组成的染色体或个体，这一转换操作我们称之为编码。编码的方式比较灵活，在这里，我们设定一个三元组为个体的基因：(I,m,n)，其中，i为任务的编号，m为完成任务所需的时间，n为网络中该任务被分配到的服务器(处理机)编号。例如(1,2,3)表示编号为1的任务所需的完成时间是2个单位时间长度，它被分配到了3号服务器(处理机)上。于是，仿真实验中，一个染色体就可以表示为｛(i,m,n)1≤i≤16,0

3.2 初始群体的产生

为了满足遗传算法的群体型操作的需要，必须为遗传操作准备一个若干初始解组成的初始群体。我们设定初始群体规模为20，给定的16个任务编号为1至16，任务完成所需要的时间已知，即三元组(i,m,n)中i和m已经确定。在1至4中随机选择一个数字分配给16个三元组，组成一个染色体，即：｛(1,5,1),(2,6, 2)(3,8,2)…｝，共随机产生出20条染色体，生成群体。

3.3 适应度函数

遗传算法使用目标函数即适应度函数来评估个体或解的优劣，并作为以后遗传操作的依据。对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果。由于是研究负载平衡问题，故利用方差和作为适应度函数。具体如下：

设所有任务完成的时间和为T，服务器的个数为 ，则理想状态下每台服务器的平均负载为w*=T/n。对于每一个染色体来说，每一个处理器上的任务总完成时间w与w*的差越小越好，故适应度函数为 ，F的值越小，则染色体的适应度越好。

3.4 模拟退火操作

遗传模拟退火算法中的模拟退火操作主要是在个体选择阶段，在这一阶段中，由于遗传算法只选择适应度最好的，而对适应度较低的染色体选择的机率很小，所以容易出现过早收敛的问题，故引入模拟退火算法，使适应度较小的染色体同样有机会被选中，从而跳出局部最优，有利于寻找到全局最优解。我们取初始温度t0为50度，降温系数为0.95。

3.5 实例结果及对比

以假定任务为基础，利用VC++编写仿真程序，分析利用普通遗传算法和模拟退火算法进行运算，在初始群体规模、交叉概率、变异概率及遗传代数相同的情况下，得到如下运算结果，

由实验结果可以得出，遗传模拟退火算法比普通的优化算法具有更好的寻求最优解的性能，在相同的条件下，寻找到最优解的概率更大。

4 结论

遗传模拟退火算法是遗传算法和模拟退火算法相结合的一种优化算法。遗传算法的并行处理和快速收敛的特点和模拟退火跳出局部最优的能力得以保存，两种不同的领域结构有机结合，搜索效率更高。

本文首次将遗传模拟退火算法应用于网络负载平衡，给出了该算法的结构与运算过程，并通过一个实例证明了其在网络负载平衡方面的有效性，为进一步利用智能化算法解决网络负载平衡问题打下了基础。

参考文献：

[1] 彭国震,邱毓兰,彭德纯.若干随机型负载平衡算法[J].计算机工程,27(2):22-23.

[2] 林凡,杨晨晖.一种动态网络负载平衡集群的实践方法[J].厦门大学学报(自然科学版).42(4):534-535.

[3] 邢文训,谢金星.现代优化计算方法,北京:清华大学出版社,1999.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文