基于差分进化人工蜂群算法的云计算资源调度

2018-11-17李志敏

计算机工程与设计 2018年11期

李志敏，张伟

(1.无锡工艺职业技术学院电子信息系，江苏无锡 214000；2.江南大学物联网学院，江苏无锡 214000)

0 引言

云计算资源调度策略[1]包括先进先出调度算法、计算能力调度算法、公平调度算法、智能调度算法等[2]。先进先出就是简单的排队策略，计算能力调度策略是在先进先出基础上，参考队列资源饥饿程度再次分配，公平调度算法以用户为单位进行资源分配，以用户提交的任务量为权重分配计算资源，有效避免了不必要等待时间；智能调度算法是使用智能控制算法对云计算资源的调度，通过算法寻求计算资源的最优配置，达到某一最优目标，比如能耗最优、总体时间最优、等待时间最优、负载平衡等。

本文引入高斯变异和自适应因子对人工蜂群算法进行改进，引入自适应交叉概率对差分进化算法进行改进，而后将两改进算法进行结合提出了差分进化人工蜂群算法，使两改进算法并行寻优，并及时交流最优解及位置信息，最终提高了最优解精度、减少了算法迭代次数和收敛时间。

1 改进人工蜂群算法

人工蜂群算法是模拟蜂群采蜜行为的群体智能算法，每个蜜源位置代表一个可行解，蜂群找到最优蜜源的速度代表算法的收敛速度，蜂群寻找最优蜜源的过程就是算法寻优的过程[3]。

1.1 人工蜂群算法原理

在人工蜂群算法中使用到的参数包括种群数量N、算法最大迭代次数maxCycle、蜜源停留最大次数Limit。

初始化蜜源，此时所有蜜蜂都是侦查蜂，寻找到N个蜜源，也就是随机产生N个蜜源[4]

Xi(n)=Xmin+rand(0,1)(Xmax-Xmin)

(1)

式中：i=1,2,…,N，Xmax、Xmin分别为可行域的最大值和最小值，rand(0,1)为(0,1)间的随机数。

对蜜源收益度进行评价。收益靠前的侦查蜂转化为雇佣蜂，收益靠后的侦查蜂转化为观察蜂，评价函数为

(2)

观察蜂根据雇佣蜂的摇摆舞得知各蜜源花粉浓度，根据蜜源花粉浓度进行选择，蜜源花粉浓度越高则招募的观察蜂越多，即

(3)

式中:pi为观察蜂选择某一蜜源的概率，SN为雇佣蜂数量。

雇佣蜂进行局部搜索。每只雇佣蜂在原蜜源附近搜索新蜜源，根据贪婪规则若搜寻的新蜜源适应度高于原蜜源，则原蜜源取代原蜜源[5]。位置更新方式为

new_xij=xij+φij(xij-xkj)

(4)

式中:new_xij为雇佣蜂搜寻到的新食物源，xij为当前食物源，xkj为随机选取的异于当前食物源的另一食物源，φij为[-1,1]的随机数。

观察蜂按照花粉浓度成比例选择蜜源后，在此蜜源附近搜索新蜜源，若新蜜源浓度大于原蜜源，则此观察蜂转化为雇佣蜂，开始招募观察蜂，其位置更新方式与雇佣蜂一致。若观察蜂和雇佣蜂在花源附近搜索Limit次以上时，仍未能找到更优蜜源，则放弃此蜜源而随机产生一新蜜源，防止算法陷入局部最优[6]。

记录当前蜂群找到的所有最优蜜源，再次进行蜜源收益度评价，直至算法循环次数大于maxCycle或者符合误差要求，算法结束。

1.2 改进人工蜂群算法

1.2.1 引进高斯变异思想

引入高斯变异就是在算法完成一次迭代之后，对剩余的蜜源进行高斯变异，若变异后的蜜源适应度值高于原蜜源，则保留新蜜源，否则保留原蜜源。引入高斯变异，是为了使算法有更好的局部搜索能力，尤其是对于有大量局部极小值的问题，可以使算法快速收敛到全局最小值点。高斯变异方法为

mutation(x)=x×(1+N(0,1))

(5)

式中：mutation(x)为高斯变异后蜜源位置，x为现在位置，N(0,1)为均值为0、方差为1的高斯分布随机数。

1.2.2 引进自适应因子

由人工蜂群算法原理可以看出，φij对算法收敛速度和精度影响很大，算法前期较大的φij可以扩大算法搜索范围进行全域搜素，避免陷入局部最优；算法后期较小的φij可以加强局部搜索能力进行局部细致搜索，提高搜索精度和收敛速度。

皮埃尔在研究人口增长时定义了Logistic曲线，此曲线包含两个参数a、b，参数的变化可以调整算法平滑度，本文以此曲线定义自适应因子θk，使用此因子调节φij大小，即

(6)

式中：θk为自适应调节因子，且0<θk

2 改进差分进化算法

差分进化算法[7,8]是一种特殊的遗传算法，使用差分方法进行变异和一对一的竞争生成策略，大大降低了遗传算法复杂度。

2.1 差分进化算法

差分进化算法包括变异、交叉和选择等操作[9]。变异操作为

vi,j=xbest,j+F*(xr1,j-xr2,j)

(7)

式中：xbest,j为当前种群中的最优个体，xr1,j、xr2,j为种群中的任意两个个体，且i≠r1≠r2，F∈(0,1)控制个体变异程度。

将变异得到的个体与父代进行交叉操作，为

(8)

式中：CR是交叉概率，为(0,1)间的一个定值。

选择操作就是优胜劣汰的过程，将变异交叉后的个体与父代进行比较，保留适应度强的个体，即

(9)

式中：xi+1为下一代选择的个体，xi为父代个体，vi为变异交叉得到的个体，f()为适应度函数。

2.2 改进差分进化算法

在差分进化算法中，交叉概率CR对基因多样性、算法搜索能力、算法收敛速度影响很大，因此本文引入了自适应交叉概率，使CR随着算法的搜素不断减小，既保证前期基因的多样性，也保证后期搜索的细致性和速度。经研究，交叉概率CR在0.4到0.9之间[10]，因此本文提出的自适应交叉概率为

(10)

式中：k为算法迭代次数，K为算法最大循环次数。

3 差分进化人工蜂群算法

当对算法的优化和改进遇到瓶颈时，可以考虑将两者智能算法进行结合，使两者智能算法优势互补，基于这一思想本文提出了差分进化人工蜂群算法，将改进的人工蜂群算法和改进差分进化算法进行结合。考虑到两算法解的编码方式可以进行统一，因此采用双种群并行寻优，寻优过程中两算法进行最优解和位置共享，从而提高算法收敛速度和精度。

引入参数D，当两算法均寻优D次后，两算法交换最优解和最优解位置，各自以自身算法的适应度值对两个最优解进行评价，保留最优解进行寻优。参数D的选择对算法性能影响很大，若D较小时两算法会区域一致，失去了并行寻优的意义，若D较大则两算法交流较少，所有D的选取要根据实验确定。

经过以上分析，给出差分进化人工蜂群算法的流程如图1所示。

图1 差分进化人工蜂群算法流程

4 实验验证

4.1 实验设计

本文的实验环境使用虚拟化软件VMware Workstation建立11个节点，选择其中某一节点作为主节点用于计算资源调度，其余10个节点用于数据的处理和存储。本文共设计了4组实验：

实验一：比较人工蜂群算法与改进人工蜂群算法的云计算时间。任务个数分别为10、30、50、70、100、150，任务大小均为512 MB，分别使用传统人工蜂群算法和改进算法进行计算资源调度，比较云计算时间。

实验二：比较差分进化算法与改进差分进化算法的云计算时间。任务个数分别为10、30、50、70、100、150，任务大小均为512 MB，分别使用传统差分进化算法和改进算法进行计算资源调度，比较云计算时间。

实验三：D值的选取。将任务数分别设置为30、70、150，任务大小均为512 MB，设定D值变化范围为[5,50]，通过观察云计算时间随D值的变化趋势来确定D值。

实验四：比较改进差分进化算法、改进人工蜂群算法、差分进化人工蜂群算法的云计算时间。任务个数分别为10、30、50、70、100、150，每个任务大小均为512 MB，分别使用3种算法进行计算资源调度，比较云计算时间。

4.2 数据处理及结论分析

实验一：人工蜂群算法和改进人工蜂群算法的调度运算时间如图2所示。

图2 人工蜂群算法和改进算法调度时间比较

从图2中可以看出，当任务数量较少时，传统算法与改进算法调度的云计算时间相差不大，但是当任务数量增大后，两算法的云计算时间相差较大，这是因为改进算法通过引进高斯变异和自适应因子使算法具有全局寻优能力和局部细致搜索能力，使主节点能够找到更优的计算资源分配方式，减少云计算时间。

实验二：差分进化算法和改进差分进化算法的调度运算时间如图3所示。

图3 差分进化算法和改进算法调度时间比较

从图3中可以看出，任务数量在10到30之间时，由于任务数量少使得计算资源压力小，所以改进算法与传统算法调度的云计算时间大体一致，但是当任务数量超过30，也就是任务数量较大时，改进算法调度的云计算时间明显少于传统算法，这是因为自适应交叉概率在算法前期保留了基因多样性，使得算法更能够找到最优解。

实验三：任务数分别设置为30、70、150，则差分进化人工蜂群算法调度的云计算时间随D值变化的曲线如图4所示。

图4 云计算时间随D值变化曲线

从图4中可以看出，当任务数量少时，D值大小对云计算时间影响不大，这是因为任务数量少，计算资源压力小。当任务数量大时，云计算时间随着D值变化先减少后增多，因为D值较小会使两算法寻优过程趋于一致，失去并行寻优意义，D值较大又会使并行寻优缺少交流而各行其是，所以适当的D值使两算法寻优时能够及时交流最优解和位置，实现信息共享和交互学习提高。从图中可以看出D取为15时云计算时间最少。

实验四：改进人工蜂群算法、改进差分进化算法和差分进化人工蜂群算法的调度运算时间如图5所示。