一种基于改进樽海鞘算法的云仿真任务调度的研究

贺少婕,杜松泽,卜立平

1(中国科学院 沈阳计算技术研究所,沈阳 110168) 2(中国科学院大学,北京 100049) 3(中南大学 商学院,长沙 410000)

1 引 言

如今处于大数据时代,大数据利用云平台作为媒介,为用户提供大量有价值的信息.本文致力于寻找更有效地方法在提高用户服务质量的同时也保障云平台提供商的利益最大化,而任务调度是实现更好云计算性能的重要部分,任务调度本质上就是在多维的环境下,以求得完成任务的最短完成时间和最小成本[1].在云任务调度优化过程中,一般有两种的优化方案,一种是传统的任务调度算法,包括有最大最小分配算法(MAX-MIN),最小最小分配算法(MIN_MIN),先来先服务算法(FCFS)等等[2],但是都存在负载不均衡的问题,从而导致CPU利用率不高;还有一种是元启发式算法,在本文中主要对元启发式算法展开研究.经过以往的实验,证明元启发式算法在任务调度问题上相对于传统的调度算法更能发挥效用.

元启发式算法大致分为两大类:单解算法和基于群体的算法[3].在前一类中,针对特定函数随机生成单个解,并进行改进,直到获得最佳结果.基于单解的算法往往会陷入局部最优解,那么得到的值就会与最低值产生较大偏差.在后一类中,在可取值的上下范围内随机选择出可行解,并增强解值,直到找到最佳解.基于群体的算法由于在迭代过程中丰富了解的多样性,从而避免了多个局部最优解.与基于单解的算法相比,基于群体的算法会检查大量的搜索空间.因此,在基于群体的算法中,找到全局最优解的概率很高.基于群体的算法相比于单解算法会在更广阔的搜索空间内搜索可行解,所以更容易找到最优解,即更优的任务调度方案[4].

在本文中针对利用元启发式算法在多维环境下得到问题的最优解展开讨论.考虑到在云计算任务调度中,极少的涉及到樽海鞘算法.因此,在云计算中,为了寻找使得任务完成时间短、成本低的云任务调度方案,本文提出了一种改进的樽海鞘算法与云计算任务调度模型相结合的任务调度算法,使用CEC的多个单峰函数、多峰函数和复杂函数做测试,比较算法的性能,并且在 CloudSim上完成任务调度过程的模拟实验,验证了本文算法的高效性.

2 相关工作

Kramer O认为遗传算法(Genetic Algorithm,GA)的基本思想是通过对种群中的个体进行交叉、变异、选择等操作,不断选择更优秀的个体,最终得到最优秀的个体[5].由于交叉和变异过程的随机性,算法往往不能快速收敛到最优值[6].刘峰改进了遗传算法,自提出了一个能双面顾及到时间以及设备的负载均衡的适应度函数,但在适应度函数中没有涉及到对任务的完成成本的优化[7].Sharma M提出Harmony-inspired genetic algorithm(HIGA)[8],结合了遗传算法的探索能力和和声搜索的开发能力,它可以智能地感知局部和全局最优区域,而不会在局部或全局最优区域浪费时间,并提供快速收敛.

粒子群优化算法(PSO)实现简单且有效,善于解决NP-Hard问题的应用程序,如调度问题和任务分配问题.齐平在自己的算法中考虑到了资源失效问题,提出了适应度函数评估任务的调度模型,但没有考虑到任务的完成成本[9].王欣欣考虑到了完成时间和资源的消耗,且未考虑到任务完成成本[10].

蜉蝣优化算法(A mayfly optimization algorithm,MA)将粒子群的个体分为雄性和雌性个体[11].此算法是混合了粒子群算法和遗传算法的优点,根据蜉蝣的求偶行为以及交配行为设计出的算法,在局部寻优问题上有良好的表现[12].

静电放电算法(Electrostatic Discharge Algorithm,ESDA)将多个电子设备作为种群,而电子设备在静电放电的影响下会损坏设备,电子设备的适应度也由个体在搜索空间中的位置决定,在迭代过程中也会找到最高适应度的电子设备位置,获得问题最优解[13].

先来先服务调度算法(FCFS)主要是从“公平”的角度考虑,按照任务的先后顺序进行调度.缺点在于排在后面的短作业的带权周转时间很大,对短任务的用户体验感不强[14,15].短作业优先(SJF)算法[16]是选择一个执行时间最短的作业为其服务.但是又完全不考虑各个作业的等待时间,因此导致了对长作业不友好的问题,甚至还会造成饥饿问题.

樽海鞘算法(Salp Swarm Algorithm,SSA)利用了这种生物的活动规律,将群体分为了两个群体,分别是领导者和跟随者,领导者是位于食物链前端的樽海鞘,而其余樽海鞘则被视为追随者[17].正如这些樽海鞘的名字所暗示的,领袖引导种群,追随者互相跟随直接或间接的领袖.本文就是基于该算法做出优化并应用在云仿真平台的任务调度系统中.

3 算法模型

3.1 Tent混沌映射

在生成初始化种群阶段,Tent映射生成的个体在搜索空间中分布较为均匀,且本身结构简单,易于实现,避免了随机生成初始种群的不确定性.

3.2 领导者个体更新

将种群中1/5的个体作为领导者,作为樽海鞘链的头部.领导者的个体根据食物的位置进行改变.

(1)

(2)

(3)

其中,j表示问题的维度,xj表示领导者樽海鞘的第j个维度,Fj表示第j维度的全局最优位置,即食物的位置,r1随着算法迭代逐渐减小,t表示当前迭代次数,T表示最大迭代次数,r2、r3是(0,1)之间的随机数,w在0～1.5之间波动.ubj和lbj是第j维度的最大和最小限度值.

3.3 跟随者个体更新

跟随者根据领导者的位置做更新.

(4)

(5)

(6)

其中,N表示种群中的个体数,C1为0～2之间的随机数,xj表示领导者,xi表示当前个体,t是当前迭代次数,T是最大迭代次数,r1表示0～1之间的随机数.

3.4 群体反向学习

使用反向学习策略去搜索更多的位置,增加种群多样性.

(7)

3.5 算法描述

LSA算法的整体流程如下:

Step1.输入样本的数目N,迭代次数Iter,可行解的上限值ub和下限值lb,基准函数fobj,问题维度dim;

Step2.利用Tent混沌映射的方式生成初始种群,便于之后做迭代优化;

Step3.根据给定基准函数计算每个个体的适应度值;

Step4.根据公式(1)更新领导者粒子;

Step5.追随者个体根据公式(4)更新;

Step6.根据公式(7)寻找追随者的反向位置,对比寻找更优秀的个体进行替补;

Step7.选择新的种群加入下一次迭代当中,直到迭代次数完成,选出最优解;

Step8.如果迭代到最后一次,输出最优的适应度函数值,否则,执行Step 7.

算法流程图如图1所示.

图1 算法流程图Fig.1 Algorithm flow chart

4 CEC标准函数集

表1中显示出各函数的设置维度以及搜索空间各个解的最高限度和最低限度.

表1 标准函数集Table 1 Standard set of functions

5 运行结果

在本节展示使用LSA算法以及其他经典算法在测试集上运行所得的测试结果并进行分析.

5.1 CEC 2014运行结果

对于CEC2014测试集函数[18],以下展示出结果图.对PSO,ESDA,MA,SSA,LSA等算法分别进行了测试,如图2～图5所示,从图中可以看出LSA在搜索阶段以及开发阶段具有优越性,寻优结果更好.LSA的收敛速度较其他算法的性能快,且结果也比其他的算法更接近于最优值.

图2 F3测试Fig.2 F3 test result

图3 F4测试Fig.3 F4 test result

图4 F9测试Fig.4 F9 test result

图5 F15测试Fig.5 F15 test result

进行多次实验,如图2～图5所示,显示出在F3、F4、F9和F15函数中,在一定的迭代次数下,通过对比找到更优解,然后根据更优解的位置在周围加强搜索的深度以及反向位置寻找跳出局部最优陷阱,增强搜索的广度,LSA算法相比于其他算法能收敛到更优值,收敛性好,稳定性强,以F4单峰函数为例,在1000次的迭代次数内,LSA算法得到的函数最优值更低,且收敛速度最快,是ESDA算法的最优值的10-6倍,相比于其他算法也表现优越.从表2中可以看出,使用多个测试函数,在多个函数中LSA算法表现最好.在多峰函数和复杂函数方面,LSA在寻优过程中也更好的跳出局部最优,找到性能更好的位置.

表2 对比测试显示结果Table 2 Compare the results shown by the test

5.2 收敛性分析

LSA算法基于领导者和追随者分别进行更新,根据公式(1),领导者的位置由r3决定根据哪一种方式进行更新,步调由控制因子w进行控制,随着迭代次数的增加向最优值位置逼近,逐渐收敛,追随者跟着收敛,最终收敛到最优值.

6 应用验证

CloudSim是一种云计算中做任务调度研究中经常使用的一种仿真软件,模拟了云计算中虚拟化技术,还提供了资源的监测以及主机到虚拟机的映射.

云计算中的资源包括处理器,存储器,网络等都是按需使用的,按使用量计费的,且云计算同时需要向多个用户提供服务,所以要考虑到每个用户的响应时间,同时,也要考虑到服务所需的成本.因此本课题提出LSA对云计算中任务调度策略进行改进,以最大限度地提高云计算效率.

任务调度需要考虑所有子任务完成所需要的时间和成本.假设已知每个任务的任务长度,每个任务在每个虚拟机的处理速度,网络宽带的宽度以及每单位的计算资源所需要的成本,以下是设计的适应度函数.

(8)

Ftime=Max(Timetrans[i][dcid]+Timeexec[i][dcid])

(9)

Timetrans[i][dcid]=cloudlength(i)/bw

(10)

Timeexec[i][dcid]=cloudlength(i)/mips(dcid)

(11)

fitness=α×Fcost+β×Ftime

(12)

其中,dcid是虚拟机的编号,Timetrans是将任务i发送到虚拟机上dcid需要的时间,Timeexec是将任务i在虚拟机上dcid执行完成需要的时间,cost是每个单位的任务资源在虚拟机上运行的成本,α+β=1,控制时间和成本的影响比例.Fcost是运行所有任务所需要的成本,Ftime是完成所有任务所需要的时间.表3是使用多种经典算法在CloudSim上的模拟结果.

表3 多种任务调度算法在CloudSim上模拟验证结果Table 3 Multiple task scheduling algorithms simulate and verify the results on CloudSim

使用的对比算法有FCFS 算法,粒子群算法(PSO),模拟退火粒子群算法(SAPSO),自适应权重粒子群算法(SAWPSO),以及本文改进的樽海鞘算法(LSA).分别在任务数量为50、100、200、400的情况下,虚拟机数量为20、20、20、40,其他条件不变的情况下做对比.实验证明,在任务数量相同的情况下,以任务的执行时间和成本为任务指标,LSA分配的方案完成的时间更少且成本更低,大大的提高了解决问题的效率.

7 结论与展望

为了降低云计算中任务调度完成时间和成本,并且为了保证种群多样性,避免收敛过快等问题,本文优化了樽海鞘算法,并将其应用于任务调度中.针对空间搜索和寻优能力不足的问题,提出了LSA算法,该算法使用群体反向学习的策略扩大搜索空间,跳出局部最优化,改良了樽海鞘算法中更新粒子的方式,提高寻优能力,提高搜索的深度与广度.将任务的完成时间和成本作为性能指标,对任务调度过程中,优化任务分配给虚拟机的分配方案,实现了合理的任务调度,缩短了任务的执行时间和降低了执行成本.

未来的工作中可以研究如何在规模更大的任务数量下优化任务调度问题的解决方案,在成本、时间和资源等多维度上考虑任务的分配方案.