基于混合萤火虫遗传算法的云计算中的任务调度优化

孟庆岩， 王晶晶

(烟台黄金职业学院 1.信息工程系; 2.机电工程系， 山东 烟台 265401)

0 引言

云计算是一种新兴的计算模式，根据按需付费策略，用户可以从共享资源池中获得所需资源[1]。云计算的优势主要来自虚拟化技术，即通过虚拟机(VM)工具分配资源。云计算有许多优点，如可扩展性、弹性、廉价、无需预先投资和按需自助服务访问、灵活性等。云服务提供商提供的计算资源通过任务调度算法分配给最终用户，其目标是将资源优化分配给广大用户，同时实现负载平衡。

云计算是一门新兴的技术，因此在云计算中任务调度领域有着广泛的研究。任务调度问题近年来涌现了许多启发式算法，本文提出了一种混合萤火虫遗传启发式算法来优化云计算中的资源分配和任务调度。

遗传算法属于进化算法的一类，受到自然选择过程和进化论的启发。遗传算法的主要优点包括：它能够处理嘈杂或随机的目标函数、全局搜索能力、对解决方案集或染色体进行不同类型编码的能力等。对于具有多个局部最优值的问题，遗传算法是首选的。

萤火虫算法受到文件行为的影响，算法的优势在于其自动细分问题的能力和处理方式的约束能力[2]。这两个优点结合在一起，使搜索空间的探索和开发非常平衡，从而产生了最佳结果。

因此，遗传算法和萤火虫算法都被单独证明是功能强大的元启发式算法，并且它们的混合算法的集成优势更加显著。本文利用以上优点，提出了一种混合萤火虫遗传算法，其目标是优化分配资源，最大程度地减少云环境中任务的总执行时间。

1 算法比较

在云计算中使用可分割负载调度应用程序，目的是减少任务的执行时间[3]。例如实时应用程序使用亚马逊Web服务环境进行了测试，在该服务上调度和部署数据管理模型。与传统的数据库管理系统相比，数据分析任务、决策支持系统和数据集市等各种任务在云环境中表现更好。云计算系统建模算法的仿真工具包使用CloudSim仿真软件[4]。该工具包支持数据中心、虚拟机和资源配置策略等建模实体。同时，使用边界多端口条件下可分任务调度的带宽感知任务调度(BATS)算法[5]。

针对CloudSim模拟器对算法进行评估，并将BATS算法与基于公平的任务调度算法进行比较，发现BATS具有更好的性能。另外基于小仓位值规则粒子群优化算法(PSO)用于云计算环境下的任务调度[6-7]。比较PSO算法与嵌入了交叉和变异算子的PSO算法，我们会发现PSO算法比其他两个算法收敛更快。基于截止期和预算分布的成本-时间优化(DBD-CTO)调度算法，具有实现最小执行成本和管理期限的双重目标[8]。一种基于蚁群优化算法(ACO-LB)的负载均衡算法来解决云计算中虚拟机的负载不平衡问题，能够适应动态云计算环境，以缩短任务完成时间为目标。利用CloudSim工具对ACO-LB算法进行了仿真，形成一种改进的遗传算法用于任务调度，证明本文所提出的算法比单独使用三种启发式算法产生更好的结果[9-11]。

对各种算法的调查表明，元启发式算法最适合用于调度相关的优化问题。该调查有助于为提出混合萤火虫遗传算法解决任务调度问题提供坚实的支持背景。

2 混合萤火虫遗传算法

该算法是优化的萤火虫算法和遗传算法的混合算法。混合的目标是通过将算法的组织分为两个阶段来实现，第一阶段通过萤火虫优化算法完成，第二阶段通过遗传算法完成，如图1所示。

图1 萤火虫遗传算法体系结构

第一个阶段是将任务映射到一个萤火虫种群，然后根据启发式逻辑对结果进行优化放置，得到一组基本结果。任务的放置取决于目标函数，目标函数旨在降低任务的执行成本。第二阶段从萤火虫中选取最终结果，并将这些结果初始化为遗传算法的染色体基本群体。由于基本结果已经通过精确算法进行了微调，因此遗传算法仅寻找执行精确算法后剩下的最高级最优解。因此，萤火虫优化和遗传算法的混合算法比单独使用的每种算法都能产生更好的结果。

2.1 萤火虫算法方法

萤火虫算法的理想化规则表现在3个方面。首先萤火虫属于雌雄同体物种，一个萤火虫可以吸引到所有其他的萤火虫[12]。其次，吸引力与它们的亮度成正比，对于任何两个萤火虫，不那么明亮的萤火虫被吸引；同时，吸引力随着萤火虫之间距离的增加而降低。最后，如果某个瞬间没有比它自己更亮的萤火虫，它会随机移动或者不移动位置。

优化问题的解决方案或搜索空间具有无限的候选解决方案，在候选搜索空间中解决方案的编码使结果可视化并有助于进一步的探索。云计算场景中的资源是虚拟机(VM)，并且每个虚拟机都通过其ID或编号来标识。名为Ti的大小为m(子任务总数)的向量表示搜索空间，其中每个索引i的值给出分配给第i个任务的资源号，表示样本候选编码解决方案。萤火虫算法和遗传算法都使用相同的编码策略，因此每个完整文件的长度和染色体的长度是相同的，这就是子任务的总数(m)。

例如，设置3个作业任务(k=3)和3个资源(n=3)。3个作业分别分解为2、4、3个子任务，分别为m1，m2和m3，即子任务(1)=3(m1=2)，子任务(2)=4(m2=4)，子任务(3)=3(m3=3)。因此子任务的总数是m1，m2和m3之和，即9(m=m1+m2+m3=9)。因此，染色体的长度(l)为9。对9个子任务的3种资源的一种可能分配是n1={1,3,5,9}，n2={2,4}，n3={6,7,8}。这种分配在向量T中编码为[1,2,1,2,1,3,3,3,1]，它代表种群中的一个样本或一条染色体。T中的每个条目的值都在1～n范围内，令s为萤火虫种群数。同样，如果考虑一个工作长度为9的10个个体(s=10)的总体，则为10*9的随机值总体矩阵。总的来说，总体矩阵的形式为Xij，其中i范围为[1，s]，j为[1，l]，Xij中的每个条目的值为[1，n]。

目标函数是定义和制定实现优化目标所需基本条件的函数。在本文所提问题中，优化的结果必须是减少所有任务在云计算机环境中的总执行时间，从而提高任务调度性能。因此，目标函数满足所有子任务的总执行时间最小。一个任务的执行时间取决于两个可变的实体，即由虚拟机处理器核心驱动的指令执行速度和每个任务的指令大小或长度。每个资源或虚拟机都有自己的执行速度，以每秒百万条指令(MIPS)为单位，用向量Ri表示，其中i∈[1,n]。每个子任务的长度都是用i∈[1,l]编码的百万个指令条数来表示的。每个任务的执行时间(以秒为单位)是通过任务的长度除以分配给它的虚拟机的速度得到的。每个实体的执行时间或精度函数如式(1)、式(2)。

(1)

(2)

该算法的目标是使式(1)中得到的所有任务的总执行时间最小化，式(2)给出了执行时间的反比关系。一个特定的fi获得的任务执行时间越长，为该i获得的F值就越小。因此，最好的解决方案是找到一个具有最大F的染色体，即最优萤火虫算法为M，如式(3)。

M=maxiFi

(3)

萤火虫的运动流动性基于其对其他萤火虫的吸引力，具有较高亮度的萤火虫让其它萤火虫朝自己移动。为了衡量吸引力，必须计算出萤火虫的亮度。亮度(I)是目标函数对该颜色的直接测量结果，光线I和j之间的吸引力(β)计算如式(4)、式(5)。

βi=Fi*e-γr2

(4)

βj=Fj*e-γr2

(5)

这里γ是光吸收系数，它是一个常数;e是指数常数;r是萤火虫i和j之间的距离。距离表示两个萤火虫对应位不同的数量，类似于汉明距离。该运动的目的是通过将吸引力更强的萤火虫中的主要特征加入吸引力较弱的萤火虫中，从而缩短两个萤火虫之间的距离。

定义目标函数：F(x),x=(x1,x2,…,x1)；生成萤火虫的初始种群Xij(i=1,2,…,m)(j=1,2,…,n)；用F(x)表示光强度I；定义光吸收系数，设置t=>0。当t小于总群数，设置条件i=1∶s(s表示所有萤火虫)，j=1∶i；如果Ij>Ii，吸引力β随着距离e-γr而变化；此时把萤火虫i移向j，评估结果并更新；直至遍历i和j；最后对萤火虫进行排序找出当前最优。

2.2 遗传算法方法

经过萤火虫算法的预先迭代，从萤火虫过程中形成的最佳解集作为遗传算法的初始种群。因此，染色体的数量等于萤火虫的数量，同样的编码方法也被复制到了遗传方案编码中。3种主要的遗传算子是选择、交叉和变异，3个算子共同进化种群[13]。遗传算法的适应度函数与萤火虫算法的目标函数相同，萤火虫的符号被染色体互换。由于初始的最优解集已经使用萤火虫算法找到，因此遗传算法具有更快收敛解的优点。

选择是指选择两个父母产生后代的过程，目的是在保持种群大小恒定的状态下复制种群中适应度高的个体[14]。为了生产出更好更适合的后代，选择更好的父母是至关重要的。本文选择了轮盘赌选择算子。

交叉，相互配对的染色体按某种方式相互交换部分基因[15]。在他们的适合度值中，从两个父母中选出更强适应性的染色体。根据达尔文的理论，只有适应度最强的个体才能生存下来。因此，通过基因交换，较弱的染色体被较强的染色体淘汰。本文采用两点交叉策略。

变异的目的是在染色体中产生随机的基因抽动，以引入染色体的多样性[16]。本文使用非均匀变异算子。

经过所需的迭代次数后，从最终的染色体群体中选择最佳或最适合的染色体作为结果，并根据最佳染色体中编码的顺序遵循调度顺序。

遗传算法伪代码，使用与萤火虫算法相同的目标函数，产生染色体群体并初始化交叉和突变率。设置迭代=>0。选择2个解决方案，根据结果改变候选方案，执行交叉算子，实现迭代=>迭代+1，直到达到最大迭代限制。选择出最合适的解决方案，结束。

3 结果分析

在CloudSim中模拟了确定萤火虫遗传混合算法用于任务调度效率的实验。实验可分为3个主要部分，以证明萤火虫遗传混合算法的效率随迭代次数的增加而提高，证明萤火虫遗传混合算法的效率高于常用的先进先出(FIFO)算法。最后，证明了组合的萤火虫遗传混合算法优于单独的遗传算法的效率。

3.1 参数设定

为了验证混合遗传元启发式算法在不同情况下的有效性。萤火虫和遗传算法使用总结的参数进行初始化。如表1所示。

表1 初始化参数

3.2 实验结果分析

在第一种情况下，为了确定迭代和执行时间之间的关系，进行了实验。所有迭代的任务数被固定为20个，而萤火虫和染色体的群体规模被固定为30个。所有情况下，资源或虚拟机的数量固定为5。其余全局参数与表1相同。随着时间段数的增加，执行时间减少。如图2所示。

图2 执行时间与迭代变化的性能分析

从10次迭代开始，迭代次数增加了10倍。对于每种情况，图2中提到的迭代值对应于萤火虫和遗传算法的相同迭代值。

在第二种情况下，实验的目的是建立萤火虫遗传算法优于FIFO算法的优越性。任务数从20开始以20的系数递增，所有情况下资源或虚拟机的数量固定为5。在整个实验中，萤火虫和遗传算法的迭代值都固定在30。总结了实验结果，如图3所示。

图3 FIFO与混合遗传算法的性能分析

显然，随着任务数的增加，萤火虫遗传算法的执行时间依然比FIFO算法要短。

在第三种情况下，该实验旨在证明将萤火虫遗传算法结合在一起的能力，实验情况与方案2相似。任务数从20开始以20的系数递增，所有情况下资源或虚拟机的数量固定为5。两种算法的迭代值固定为30。结果如图4所示。

图4 遗传算法与混合遗传算法的性能分析

混合萤火虫遗传算法在执行越来越多的任务时执行时间更短，这证明它比遗传算法更好。

4 总结

本文提出了一种将萤火虫和遗传两种强大的启发式搜索算法相结合的方法，形成一个组合的元启发式搜索算法。试图探索一种新的混合遗传元启发式算法来解决云计算中的任务调度问题，其目标是使所有任务的执行时间最小，达到近似最优解决方法。仿真结果表明，与FIFO和遗传等常用算法相比，混合萤火虫遗传算法在大搜索空间的动态云环境中具有高效、快速的搜索能力。由于混合萤火虫遗传算法能够快速收敛到近似全局最优解，因此它在云计算环境中有利于资源的优化分配和任务调度。