基于蚁群优化蛙跳算法的云计算资源调度算法

2018-08-28徐见炜

计算机应用 2018年6期

陈暄，徐见炜，龙丹

(1.浙江工业职业技术学院，浙江绍兴312000; 2.浙江大学理学部，杭州310058)

(*通信作者电子邮箱chenxuan1979@sina.com)

0 引言

云计算下的资源调度一直以来都是研究的重点，能否有效、合理地分配资源关系到云计算下是其效率能否提高的关键［1］。将启发式智能算法运用在资源调度中已经成为了当前研究的热点，国内外学者从不同的方向进行了研究。将基本的蚁群优化(Ant Colony Optimization，ACO)算法［4－5］、粒子群优化(Particle Swarm Optimization，PSO) 算法［2－3］、遗传算法(Genetic Algorithm，GA)［6－7］运用在云计算资源调度中取得了一定的效果。文献［8］提出了基于改进量子遗传算法(Improved Quantum Genetic Algorithm，IQGA)的云计算资源调度，该算法通过改进量子遗传算法的二进制编码使其适用于实数编码，仿真实验结果表明与遗传算法(GA)和粒子群优化(PSO)算法相比能够提高云资源调度效率;但存在的问题是调度模型的假设条件设置得过于简单，求解效率和准确性还需要进一步提高。文献［9］提出了一种在云计算环境中结合遗传算法和蚁群算法的资源调度算法，该算法利用遗传算子的快速全局收敛性生成一个初始信息素分布，然后利用双向收敛蚁群算法反复迭代求解，从而提高算法的效率;但存在的问题是算法的迭代步骤过于频繁复杂，增大了空间计算量。文献［10］设计了一种基于改进蚁群优化算法的云计算资源调度优化模型，利用蚁群优化算法得到的路径作为云计算资源调度目标函数的最优解，仿真实验说明该算法具有很好的效果;但存在的问题是实验中仅仅与传统的蚁群算法、粒子群算法相比，并没有针对一些新的改进的算法进行对比，同时实验中云计算相关指标太少，不能完全说明所提算法在其他指标方面的优越性。文献［11］提出了一种基于贪心算法的云计算资源调度策略，建立了云计算环境下资源调度算法的贪心模型，以最小执行时间和满意度为目标，构建资源调度方案;但存在的问题是贪心算法自身存在着一定的缺陷，因此在云计算的资源调度中的效果并不是非常满意。文献［12］提出一种基于时间成本负载加强型的蚁群优化(Time，Cost and Load Balance-Enhanced ACO，TCLB-EACO)优化算法，通过创新地改进信息素和启发信息提高了算法效率;但存在的问题是没有与其他的智能算法进行比较，实验效果相对单一。文献［13］从绿色云计算角度出发，提出了机器启动时间的虚拟机策略，并通过资源延迟感知的实时任务调度(Startup Time Aware Real Scheduling，STARS)算法来进行调度资源，实验说明该算法在时效性、节能和资源利用率方面都具有比较好的效果。文献［14］提出将萤火虫算法用来寻找云计算中的目标资源中的最佳调度策略，仿真实验说明提高了云计算资源分配效率;但存在的问题是萤火虫算法自身存在收敛快等缺点并没有得到解决，实验仅仅与基本算法进行对比。文献［15］提出将改进的蚁群算法用于负载均衡的云计算资源调度中，仿真实验说明该算法能够有效地降低执行成本，满足资源负载均衡;但存在的问题是没有考虑用户的服务质量(Quality of Service，QoS)要求。文献［16］提出一种基于生产函数的云服务提供商收益最大化同时兼顾用户满意度的资源调度算法，通过与基于博弈的效用优化算法进行比较，仿真结果表明该调度算法具有更好的性能;但存在问题是生产函数具有一定的局限性，无法很好地适应云计算下的动态变换特点。文献［17］提出基于禁忌搜索的云计算平台下服务资源均衡调度方法，依据云计算调度系统的结构特点对云计算环境下的资源均衡资源调度问题进行形式化描述，将混沌理论和粒子群理论相结合得到资源调度和资源均衡度的目标函数，完成对云计算资源调度，获得了比较好的效果;但存在的问题是禁忌算法自身算法效率低，对云计算资源调度的效果会具有一定的影响，影响调度效率。文献［18］提出了一种考虑时间成本约束条件的蚁群优化算法，不仅能使任务处理时间较短，执行费用较低，且能使系统负载相对均衡，资源利用率高;但存在的问题是仅仅是与其他改进的蚁群算法相比，没有与更多的智能算法进行比较，存在一定的不足。

针对以上云计算资源调度存在的问题，本文首先描述建立QoS的云计算中的资源分配模型，其次，提出基于蚁群优化蛙跳算法(ACO-Shuffled Frog Leading Algorithm，ACOSFLA)的融合算法运用到云计算资源调度中，最后仿真实验表明融合后的算法能够有效地提高云计算的资源调度效率。

1 基于QoS的云计算资源分配模型

传统的调度算法以资源使用效率为第一目标，算法自身的适应性不好，局限性大。面向商业服务的云计算必须提供具有高效、可靠和公平的资源为这些云端用户服务，并以满足云用户的最大化需求为宗旨。在云计算资源调度中，针对大量资源被调用的请求，首先需要检测资源各个性能指标，计算各个资源当前的占用率和负载情况，寻找更加适合的资源来执行相应的任务，有效地提高资源的利用率。本文提出了基于QoS的云计算模型，构造具有完成时间、费用、可用性和安全性四个指标的效用函数来衡量云计算下的资源效果。

为了进一步研究具有针对性，本文采用文献［19］的资源调度中的任务和资源进行抽象化处理，建立由m个用户和n个资源组成的调度模型，设R表示所有资源集合，即R={r1，r2，…，rn}，其中:ri表示第 i个资源 ri={ri(1)，ri(2)，…，ri(t)}，t为不同的属性。本文选取t的值为4，表示时间、费用、可用性和安全性四个属性。用户的集合为U={u1，u2，…，um}，其中m表示的用户个数，假设一个用户ux在某一个时刻提交的任务为tsj，因此第k个任务可以表示为tsjk={tsjk(1)，tsjk(2)，…，tsjk(t)}。在云计算环境中，用户ux针对某一个资源的不同维度特征属性的QoS为:qij={qij(1)，qij(2)，…，qij(t)}，其中qij(k)表示用户j对ri的第k个属性对应的QoS。用户uj对应资源ri的第k个特征属性用户的效用表示为θij(qij(k))，因此本文设定的基于QoS的目标优化效用函数为:

任务tsj完成时间反映了该资源rj具备完成对应任务tsj的能力，在规定时间内完成，其值为1，否则就为0，其效用函数如下:

云计算服务具有比较高的性价比，设b为用户uj对于任务tsj的预算费用，设c为用户uj对于任务tsj的实际费用。如果超过预算费用，效用的值为0，效用函数如下:

云计算中的可用性反映了用户提交服务请求后，能够成功返回处理的概率，可用性越高，说明用户满意度越大，设定可用性为a，e为常数，随着a逐渐增大，用户的QoS提高幅度越大，效用呈指数式增长，表达式如下:

系统安全性是关系到用户对于QoS性能指标反馈的关键，在Qos中使用监测异常数值大小来表示系统安全性，设定s1、s2表示不同的安全层次安全界限，效用表达式如下:

2 基于改进的蚁群和蛙跳融合算法

2.1 改进的蚁群算法

蚁群优化(ACO)算法是一种模拟真实蚂蚁群体觅食行为的仿生学优化算法，它具有正反馈、分布式和启发式的搜索特点，在解决复杂的优化问题方面取得了比较好的效果，其本质是使用信息素来作为种群中的个体的交流的介质，其计算式如下:

2.1.1 信息素更新

传统的蚁群算法存在的主要缺陷是信息素的值依赖于问题的规模，因此，本文针对信息素进行改进，把蚁群算法的信息素更新过程分为两个阶段，并将信息素的值限定在特定的区间中。第一个阶段是顺序更新阶段，使用前n个迭代上的最优方案来更新路径上的信息素;第二个阶段是当前迭代达到最优解，全局最优路径上的信息素才能够被更新。更新公式如下:

当cf＜t(t为［0，1］内的数)时，使用前m个解序列来更新路径上的信息素;否则，就执行当前迭代的最优解来更新信息素。

2.1.2 设置经验反馈因子

针对信息素的改进主要考虑启发信息对于路径的影响，这使得蚂蚁在算法的迭代初期容易选择最短的路径，而没有考虑被选取为解的路径的组合对最终路径长度的影响，从而导致了搜索具有盲目性的问题，通过研究发现一些短的解元素所在的路径的整体长度往往很大，导致算法最终收敛到局部最优而不是全局最优。为了能够有效地避免在算法的初始阶段就失去原本具有最优解的可能性，需要在概率选择中增加另一个权重——经验反馈因子w来考虑选取的路径对于搜索过程的长期影响。在初始阶段中，当解元素倾向引导蚂蚁寻找短路径时，就会被赋予较高的权重;反之，当解元素可能会引导蚂蚁走向较长的路径时，就应该减少元素的权重，这样就能够让蚂蚁的搜索初期选择不同的路径，增加了多条路径选择的多样性，避免算法陷入局部最优解。反馈因子如下:

式中:cmin和cmax分别表示两个点之间的路径长度的最小值和最大值;cmid代表两者的平均值;c(a)表示路径的长度;A(i，j)表示路径(i，j)的蚂蚁的集合。

2.2 蛙跳算法

蛙跳算法(SFLA)是一种启发式优化算法，它通过执行启发式函数而执行启发式搜索，从而获得全局最优解，其思想是首先将蛙群分解为不同数目的子群，其次在子群中按照一定的策略进行搜索，最后再进行全局交换。

1)子群划分。

设置全部的青蛙有M个，子群数目为k，子群内的候选解的个数为 n。xi=(xi1，xi2，…，xiD) 表示第 i个候选解，其中 D表示候选解的维数。

2)子群内部搜索。

在子群搜索的过程中获得的候选解如果是最差的，需要对其进行更新，反之，则需要使用此时的候选解替换继续执行搜索。

3)全局信息交换。

当所有子群完成内部搜索之后，将所有的子群再次进行重新划分并在群内进行搜索，直到满足找到最优最优解的时候，结束条件结束。

2.2.1 局部优化

使用差分进化算法进行局部更新主要是随机选取一个目标的个体进行更新，而且这个子群的更新对象还是子群中的最差个体，并且在整个优化过程中更新策略并不是一成不变的。为了能够达到算法在进化前期提高种群的多样性和后期加快算法的收敛的优化效果，采用变异方式对其进行优化。

1)变异操作。

在算法的前期中，为了保持种群的多样性，提高全局搜索能力，对子群中的最差个体按照式(13)进行更新，随机选择三个个体，其中一个个体作为目标个体，其他两个个体用来更新移动的步长，采用rand差分算子。

其中:Xr1为目标个体;Xr2和Xr3为随机选取的其他两个个体;X'w为产生的新个体;F1∈(0，1)。

为了有助于收敛到最优点，用子群中最好的个体作为目标个体，引入差分算子best变异，更新策略如下:

式中:Xr2和Xr3为随机选取的其他两个个体;X'w为产生的新个体;Xb为子群最优个体;F2∈(0，1)，且F1+F2=1。

2)选择操作。

将进行一次迭代后将产生的新个体X'w与子群最差个体Xw进行适应度评价，根据自然法则，选择适应值更好的个体进入到下一代种群，如式(15)所示:

3)交叉操作。

为了能够进一步提供算法的局部搜索能力，保持种群的多样性，引入交叉操作进行了改进，更新策略如下:

2.2.2 全局优化

设所有青蛙子群的个数为m，每个子群内的最优青蛙个体分别为:Pb(1)，Pb(2)，…Pb(m)，全局最优解为 Pg，在Pb(1)和Pb(m)中随机选择两个个体作为父代，再结合Pg进行交叉，按照下式生成后代:

式中:r1+r2+r3=1 且r1，r2，r3∈(0，1)。r1，r2，r3的大小决定了父代个体之间交叉域的大小，在青蛙种群中采用精英保留策略，淘汰较差的个体，但是由于Pb表示各个子群中的内部最优个体，因此会导致陷入局部最优。所以在不同的子群最优个体之间进行交叉操作，能够避免陷入局部最优，从而达到全局最优。

2.3 算法步骤

首先，将蚁群算法的个体与云计算资源调度方案进行对应，其次，采用改进的蚁群算法得到的解作为蛙跳算法初始种群个体进行进一步优化，最后得到最优的个体即最佳的调度方案。其算法步骤如下:

步骤1 将蚁群算法中的个体与云计算中的资源调度方案进行一一对应。

步骤2 初始化，设置最大迭代次数、蚁群算法相关参数初始值、蛙跳算法参数初始值。

步骤3 构建蚂蚁路径，将选中的路径对应到蚂蚁的禁忌表中，直到所有蚂蚁都完成一次遍历，按照式(12)改进概率转移规则选取下一个元素。

步骤4 将蚂蚁通过路径得到的解作为蛙跳算法的初始蛙群个数，并按照式(13)～(17)的相关操作对蛙跳算法进行改进。

步骤5 按照式(9)、(10)对信息素进行更新。

步骤6 算法终止，找到最优个蚂蚁个体即最佳的云计算资源调度方案。

3 仿真实验与分析

为了进一步说明本文算法在云计算中的效果，将本文算法与其他算法通过Cloudsim仿真平台对比资源调度的效果。本文算法所需要的主要参数如表1所示，设定任务数量一定，资源数目为［5，100］，对比的指标为在时间、成本、可用性和安全性。

实验内容将本文算法ACO-SFLA与基本蚁群(ACO)算法、基本蛙跳算法(SFLA)、改进的粒子群(Improved Particle Swarm Optimizaiton，IPSO) 算法［20］、改进的人工蜂群算法(Improved Artifical Bee Colony algorithm，IABC)［21］进行对比，5种算法在资源数目逐渐增大的情况下的不同性能对比如图1所示。

图1 不同算法在不同资源下的性能对比Fig.1 Performance comparison of different algorithms under different resources

由图1(a)可以看出，本文算法曲线在下降过程中比较平缓，且完成时间优于其他4种算法，表明本文算法与其他算法相比能够有效地节约完成时间;从图1(b)中可以看出，5种算法的成本伴随着资源数目的增大而逐渐降低，本文算法消耗的成本优于其他4种算法;图1(c)中描述了5种算法的用户满意度调查都比较满意，本文算法满意度稍微低于其他4种算法，这说明本文算法在执行时间和成本方面给云客户带来了较好的用户体验;图1(d)的结果表明了5种算法在资源调度的过程中都具有比较好的安全性，算法之间相差不大，且算法的异常数值的峰值都比较小，而本文算法的峰值相对小一些。综合以上分析得出本文算法能够较好地解决对云计算资源调度的问题，产生更好的优化策略。