基于遗传珊瑚礁优化算法的负载均衡问题

袁赫潞,温长吉,2,吴建双,朱允刚,于合龙,2

(1.吉林农业大学 信息技术学院,长春 130118;2.吉林省精准农业与大数据工程研究中心,长春 130118;3.吉林大学 计算机科学与技术学院,长春 130012)

信息时代,云计算技术能实现其强大的资源配置功能,其核心技术是通过负载均衡策略层收集量化信息,并根据负载均衡策略完成分配任务.在目前的拓扑网络下,负载均衡提供了一种廉价且透明有效的方法,扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性.

早期集中式负载均衡方法具有部署简单、高效且平台易维护的特点[1].但当面对高峰用户访问量和任务数量过多时,中心管理服务器将会面临单点失效的瓶颈[2].针对上述问题,分布式负载均衡具有不设中心控制服务器,即每个服务器都参与任务调度和分配,因此具有较好的拓展性.分布式负载均衡如何优化平台资源配置,提升资源能耗利用率是研究的关键问题之一,代表性工作包括传统优化调度模型和基于群智能算法.Bittencourt等[3]提出了一种基于博弈论的分布式负载均衡算法,网络服务器之间通过博弈相互转嫁负载使自己的负载最小化,从而使系统达到均衡实现最优的负载均衡；文献[4]提出了一种优化配置模型,该模型通过计算不同工作负载下关于服务器的功耗运行动态优化管理,进而有效减少基础资源的能源消耗并增加能源的应用效率；文献[5]提出了通过WiFi接入点把卸载任务给云的一种节能调度模型,在总完工时间的约束下得到了最少设备的消耗；文献[6]提出了一种引入局部搜索算子提高搜索能力和加速收敛速度的改进遗传算法模型,实现了节能任务调度;文献[7]提出了利用人工蜂群算法解决负载均衡问题,并设计了新的问题模型；Kechagiopoulos等[8]提出了基于粒子群优化算法；Nayeem等[9]提出了基于精英策略的遗传算法负载均衡设计方案.

珊瑚礁优化(coral reef optimization,CRO)算法[10]是一种模拟珊瑚虫群体行为和珊瑚礁组成的智能优化算法,通过珊瑚虫种群的繁殖、竞争、淘汰等环节实现优化.珊瑚礁优化算法中的有性和无性繁殖,以及毁灭机制实现信息的种群间共享机制,增强全局搜索能力.文献[11]运用珊瑚礁优化算法得到了较客观的效果.针对无线接入网的分布问题,文献[12]证明了珊瑚礁优化算法在实际应用中具有较强解决问题的能力.但目前基本珊瑚礁优化算法仍存在缺陷,如在繁殖过程中种群多样性受限,搜索精度偏低,易陷入局部最优解等.针对上述问题,本文提出一种改进的珊瑚礁优化算法----遗传珊瑚礁优化算法(cenetic algorithm and coral reef optimization,GACRO),即在珊瑚虫的每次进化过程中,将遗传算法中的交叉和变异算子引入到珊瑚礁优化算法的种群进化迭代中,在保留基本珊瑚礁优化算法中每个珊瑚虫信息共享机制的同时,有效提升全局搜索能力,增加种群多样性,提升算法的优化性能,避免算法过早陷入局部最优的问题,并将改进的遗传珊瑚礁优化算法应用于负载均衡中.

1 相关理论及问题描述

1.1 算法简介

遗传算法(GA)是模拟生物进化论中自然选择和遗传学机理的生物进化过程计算模型,其通过对问题所属解空间中的解向量进行编码,利用生成的染色体建立初始种群,通过选择、交叉和变异等操作从适应度函数中选出优秀个体,进而实现问题寻优.

珊瑚礁优化算法(CRO)是一种模拟珊瑚虫群体行为和珊瑚礁组成的智能优化算法.珊瑚虫种群的进化行为分为繁殖、竞争、淘汰等阶段.繁殖行为又可分为外部有性繁殖、内部有性繁殖和无性繁殖.首先将珊瑚礁记为Am×n,外部有性繁殖概率记为Pb,内部有性繁殖概率记为1-Pb,死亡概率记为Pd,无性繁殖概率记为Pa,且Pa=Pd[13]；然后进行外部有性繁殖和内部有性繁殖,若在迭代次数(步长K)内未被选择则会被释放到水中,根据适应度函数对计算珊瑚虫的健康值进行排序并进行幼虫安置；进行无性繁殖时,在礁上所有的珊瑚虫都会通过健康值进行水平排序,根据概率Pa进行复制并再次排序,若礁上存在一些不健康的珊瑚虫则为死亡概率.一系列操作完成则表示一次迭代完成,若符合算法的终止条件则输出,若不符合算法的终止条件则需进行第二次迭代,直至满足算法的终止条件为止,输出最优解.珊瑚礁优化算法流程如图1所示.

图1 珊瑚礁优化算法流程Fig.1 Flow chart of CRO algorithm

1.2 遗传珊瑚礁优化算法

1.2.1 算法设计 遗传珊瑚礁优化算法基本思想为: 在每次种群进化过程中,由基本珊瑚礁优化算法进化获得的珊瑚虫种群并不直接进入下一次迭代操作,而是在进入下一次迭代前对种群中的每个珊瑚虫进行选择、变异和交叉等一系列操作后得到新的种群.设第t代种群记为S1,依次进行珊瑚礁有性繁殖,判断K步内是否选择到双亲,如果无双亲则进行内部有性繁殖,在K步长内选择母珊瑚虫,否则将其释放到水中.之后对幼虫进行安置,通过适应度函数计算健康值,再进行无性繁殖,对健康值高低进行排序,此时进行遗传算法中的选择、交叉、变异操作,形成种群S2,再对新种群S2进行幼虫安置,判断是否为最优值进行输入,否则将进入毁灭机制.遗传珊瑚礁优化算法执行步骤如下：

1) 初始化GACRO算法的各参数，初始化种群S1；

2) 种群S1进行外部有性繁殖,根据概率Pb选择双亲；

3) 若K步长内选择双亲,则执行步骤6),K步长内未选择双亲,则执行步骤4)；

4) 内部有性繁殖,根据概率(1-Pb)选择母珊瑚虫；

5) 若K步长内选择母珊瑚虫，则执行步骤6),K步长内未选择母珊瑚虫则将其释放到水中；

6) 进行幼虫安置,根据适应度函数计算健康值并进行排序；

7) 无性繁殖,根据概率Pd进行复制,并重复步骤8)进行幼虫安置,形成种群S2；

8) 利用遗传算法对新珊瑚虫种群进行选择操作,选择操作后的珊瑚虫种群S2中的珊瑚虫xi,被选中概率为P(xi),在S2中选出一个珊瑚虫进行复制操作,共进行M次,复制产生的M个珊瑚虫成为种群S3；

9) 利用遗传算法对种群S3进行交叉操作,交叉概率为Pc,在种群S3中随机选出c个珊瑚虫进行交叉操作,通过交叉操作随机交换两个珊瑚虫某些基因,产生新基因组合,用S4替代S3；

10) 利用遗传算法对S4进行变异操作,确定变异数m,在种群S4中随机选取m个珊瑚虫变异,新的种群S5代替S4,成为新一代种群；

11) 重复步骤6),根据健康值进行排序；

12) 判断是否为最优值,若不是则将进入毁灭机制；

13) 输出最优值.

1.2.2 适应度函数设计 云环境中拥有计算资源、存储资源和带宽等资源,用户可根据自己的需求,对不同资源进行申请和计费.由于系统对各种资源的管理和使用方式不同,因此本文将所有的服务器都视为计算服务器进行处理.在负载均衡策略针对大量并发请求任务进行分配时,负载调度机制通过最小化响应时间及服务器最大化利用率实现负载均衡,优化资源配置及效率.

适应度函数设计原则如下：设定任务数量、服务器数量和计算能力(每台服务器计算能力相同)为已知,使用矩阵表示每个任务在每个服务器上的预计花费时间(expect time to complete,ETC).ETCij表示第i个任务在第j个服务器上花费的时间,设任务的数量为m,服务器的数量为n,则

(1)

因为所有任务大小和服务器的计算能力己知,因此可计算出所有任务执行的总时间.设服务器j上所有任务组成的集合为Cj,则服务器j执行完所有任务所需的时间为

(2)

花费的总时间为

totalTime=maxCij,

(3)

基于时间的适应度函数为

(4)

1.2.3 问题描述 为解决云计算环境中服务器负载均衡的问题,需要合适的方式将服务器与任务的关系映射到一起,通过编码的方式确定种群中个体的算法表现形式,每个经过编码后得到的数组表示一个任务在服务器上的分配方案.对每个任务和服务器进行唯一性标记,经过编码得到的数组长度由任务总数确定,数组中每个元素对应的值则为任务对应的服务器编号.利用云计算的特征,本文对每个云计算中的子任务所需占用的服务器进行编码,子任务的数量决定了编码的长度,将编码与云任务分配相对应,采用服务器—任务的间接编码方式.设有3个任务,4台云计算服务器,其中任务1和2分别由3个子任务,任务3有4个子任务,共计10个子任务,此时珊瑚礁优化算法编码列于表1.由表1可见,CRO算法编码序列为{4,1,2,3,2,1,4,2,1,3},对该序列进行解码，结果列于表2.

表1 珊瑚礁优化算法编码

表2 珊瑚礁优化算法解码

由表2可见,子任务{2,6,9}分配给1号服务器,{3,5,8}分配给2号服务器,{4,10}分配给3号服务器,{1,7}分配给4号服务器.一个珊瑚虫对应一个任务集分配策略,则CRO算法编码序列为{4,1,2,3,2,1,4,2,1,3},与一个任务对应服务器的分配方案相对应.服务器j上执行完所分配的任务集所用时间F(j)及执行完所有任务的总时间Completetime分别为

(5)

其中：L(j)表示初始负载；task表示任务总数分配到j上；R(i,j)表示任务i在服务器j上的执行时间；N表示服务器总数.

1.3 评价指标

假设一批小任务由若干大任务分解组成,且子任务划分数量相同,再假设任务数量超过服务器数量多倍.用M表示任务总数,Ti表示第i个子任务,N表示服务器数量,VMj表示第j个服务器,则第j个服务器完成系统交付的所有子任务时间为

(6)

其中：Time(Ti,VMj)表示子任务Ti在服务器VMj上的执行时间；m表示分配到VMj上的子任务数量.所有服务器执行任务所用的最长时间定义为总任务执行时间评价函数,即completeTime=max{vmTime(VMj)},j∈[1,N].负载均衡度DLB评价函数为

(7)

DBL值越接近1负载均衡度越高,即每个服务器完成任务所用的时间与总任务完成时间越接近表示负载越均衡.

2 实验结果与分析

2.1 实验参数初始化

珊瑚礁优化算法种群多样性受限,因此需引入遗传算法的交叉和变异操作增加种群多样性,避免陷入局部最优.交叉概率函数为

(8)

其中:fmax表示种群最大适应度值;favg表示群体平均适应度值；f′表示较大的适应度值在两个交叉个体中.如果f′>favg,则交叉概率Pc变小,避免适应度值大的个体统治群体,出现陷入局部最优解的问题,设k1=0.36;如果f′

2.2 CloudSim云计算仿真工具

CloudSim云计算仿真工具是一种云计算仿真软件[15],以GridSim模型为基础进一步发展得到了CloudSim,支持云计算的资源管理和调度模拟,本文在CloudSim3.0中对数据中心(Datacenter)、虚拟(VM)以及云任务(Cloudlet)的环境参数进行配置,见表3.

表3 CloudSim3.0环境参数配置

注：MI表示百万条指令.

2.3 实验结果与分析

下面将本文提出的珊瑚礁遗传算法(CROGA)与遗传算法(GA)[13]、珊瑚礁优化算法(CRO)[16]、蚁群算法(ACO)[17]、蜂群算法(ABC)[18]、遗传退火融合算法(GASA)[19-20]、狼群算法(WA)[21]、蛙跳算法(SFLA)的负载均衡在Cloudsim仿真模拟实验平台中实现.基于服务器负载率最大值和机电负载标准差两方面进行对比.采用服务器负载率最大值和服务器负载率标准差对负载均衡度进行评价,其中迭代次数可证明改进算法的有效性.重复执行每项实验10次,最后取实验结果的平均值.

假设测试参数为：测试任务数量1 000个；群体M=20；迭代次数T=35；交叉因子C=0.5；变异因子D=0.7；珊瑚礁大小为Am×n;外部有性繁殖概率Pb=0.8；内部有性繁殖概率1-Pb=0.2;无性繁殖概率Pa=0.3;死亡概率Pd=Pa=0.3.测试函数定义为适应度函数.

2.3.1 算法的有效性分析 下面针对上述8种算法在任务数量由25逐渐增加到250的过程中,对最优解所需的迭代次数进行比较，不同算法迭代次数的对比结果列于表4.由表4可见：当任务数量增加时,迭代次数持续递增；在任务数量相同的情况下,遗传算法和蜂群算法的迭代次数与其他算法相比最多；当任务数量等于或小于75时,本文提出的遗传珊瑚礁优化算法与其他几种算法在迭代次数方面相差不多；当任务数量逐渐增多且大于75时,遗传珊瑚礁优化算法体现出优势,所需的迭代次数相比于其他算法更少.表明在运行效率上,遗传珊瑚礁优化算法优于其他算法,证明了改进遗传珊瑚礁优化算法的有效性.

表4 不同算法迭代次数对比

2.3.2 评价算法的负载均衡度 服务器执行任务分配不均衡是导致系统功耗成本过高的一个主要原因.表5列出了不同算法服务器负载率最大值对比结果.由表5可见,当任务数量逐渐增多时,8种算法的服务器负载率最大值均增大,但本文提出的遗传珊瑚礁优化算法服务器的负载率最大值始终比其他算法小,并且任务数量50～300时负载率均低于60%,表明本文提出的遗传珊瑚礁优化算法任务分配更合理.

表5 不同算法服务器负载率(%)最大值对比

综上所述,本文将遗传算法的选择、交叉和变异操作引入到基本珊瑚礁优化算法中,提出了一种基于遗传算法环境下的遗传珊瑚礁优化算法,能将遗传算法中的遗传选择操作更大地优化,有效增加了种群的多样性,增强了算法的全局搜索能力,提高了网络资源利用率,明显改善了网络负载不均衡的情况.