欢迎访问一起赢论文辅导网
博士论文
当前位置:首页 > 博士论文
基于萤火虫算法和动态优先级的多Qos云工作流调度
来源:一起赢论文网     日期:2018-09-10     浏览数:2161     【 字体:

 计算机集成制造系统 第23卷的计算节点上。刘晓等[3-4]构建了一种吞吐量一致性模型来评估工作流应用中任务按时完成的概率,同时可对局部吞吐量约束条件进行分配,从而有效减少时间开销。以上两种调度策略的主要目的是优化完成时间。关于在截止时间约束下优化工作流费用问题,ByuByun等[5]针对云计算环境提出分区平衡 间规 (Partitioned Balanced Time Scheduling,PBTS)算法,该算法将工作流截止期划分为多个时间段,并 (Balanced Time Schedu-ling,BTS)算法[6]为每个时间段计算工作流需要的最 量,但 型。HENDRIK 等[7]提出一种服务器数量约束 (ServerCount Bound,SCB)算法,在服从截止时间约束的同 时,寻 用。SAEID等[8]提出一种带有期限分布的IaaS云部分关键 (IaaS Cloud Partial Critical Paths withDeadline Distribution,IC-PCPD2)算 法[8],首 初始化关键路径上任务的截止时间,采用递归的方法依次求取其他路径上任务的截止时间,然后循环求取偏序关键路径,在截止时间约束下将偏序关键路径的任务放置到最便宜的虚拟机实例上,直到工作流中的所有任务分配完毕。现有的工作流调度算法主要从时间和费用两方面进行研究,但这些算法都没有考虑可靠性,均假设任务执行过程和数据传输过程没有中断、不会失败,但在实际系统中,资源和网络的不可用都会对工作流的执行造成负面影响[9]。因此,本文在考虑工作流的完成时间和执行费用的基础上,将工作流执行的可靠性也作为一个服务质量(Quality of Service,QoS)约束考虑在内,针对时间和可靠性双重约束下费用最小化的云工作流调度问题,使用随机搜索算法实现云工作流的调度。在具体实现中,将萤火虫算法(Firefly Algorithm,FA)[10]作为基本思路,提出一系列改进措施,以解决时间和可靠性双重约束的云工作流调度问题。相比于其他智能搜索算法,FA 具有简单易懂、参数少和易实现等特点。然而,传统 FA 的解空间属于连续的实数域,而云工作流优化调度的解空间属于离散的整数域空间。为了使面向连续问题的 FA 适用于求解云工作流优化调度问题,本文对其进行改进、使其离散化,并结合云工作流调度问题重新定义了 FA 中的距离、位置、亮度和萤火虫的移动方式,采用动态优先级方式确定任务的执行顺序,从而提高算法的寻优能力。1 工作流和云资源描述1.1 工作流工作流由一系列任务和任务间具有依赖关系的数据组成[11],一般通过有限 环图(Directed Acy-clic Graph,DAG)描述,图中的节点表示任务,边表示任务间的依赖关系。工作流可 {T,E,D}。 中:T={t1,t2,…,ti,…,tN}表示一系列任务的集合,N 表示任务个数,tentry表示开始任务,即没有父节点的任务,texit表示结束任务,即没有子节点的任务;E 为有向边的集合,E={(ti,tj)|ti,tj∈T},(ti,tj)表示任务ti和tj之间的依赖关系,任务ti是任务tj的前驱任务,任务tj是任务ti的后继任务。任务ti的直接前驱任务集合为pre(ti),直接后继任务集合为succ(ti);D={dti,tj|ti∈T,tj∈T}为任务ti和tj间传输数据量的大小,表示两个任务之间的通信开销,当任务ti和任务tj调度在同一虚拟机上时通信开销忽略不计。1.2 云资源假设云服务提供商可提供不同租赁价格与配置的虚拟机资源来执行工作流任务,这些资源可表示为VM ={vm1,vm2,…,vmM},其中 M 表示虚拟机的个数。对于每一个虚拟机vmm,vmcm表示虚拟机的计算能力即每秒处理的指令数,vmfm表示虚拟机的失败率,vmpm表示虚拟机的单位时间租赁费用。2 问题描述设一个云工作流包括 N 个任务,云服务商提供了 M 个虚拟机。云工作流调度问题实际上是建立N 个任务和 M 个虚拟机间的映射关系。本文的主要目标是寻找一种调度方案,以满足用户要求的完成时间和可靠性双重约束,同时使云资源租赁成本最低。下面分别介绍完成时间、费用和可靠性的计算方式。2.1 完成时间假设任务ti被分配 到虚拟机vmti上执 行。由于受工作流结构的约束,任务ti必须在其前驱任务执行完毕 后,将 数 据 传 输 到 任 务ti所 在 的 虚 拟 机vmti上才可以执行。若此时虚拟机vmti上还有其他未完成的任务,则任务ti必须等待虚拟机vmti其他694 郑宏升 等:基于萤火虫算法和动态优先级的多 QoS云工作流调度任务执行完成后才能开始执行,因此任务ti的开始时间为ST(ti,vmti)= max{tavaili,AvaiTime(vmti)}tavaili= maxtj∈pre(ti){EFT(tj,vmtj)+CT(ti,tj,vmti,vmtj)}。 (1)式中,假设任务ti的前驱任务tj调度到虚拟机vmtj上,EFT(tj,vmtj)表示任务tj的完成时间,数据从ti 传输给tj的时间CT(ti,tj,vmti,vmtj)可用dti,tj/B(vmti,vmtj)计算。其中:AvaiTime(vmti)表示虚拟机执行完ti之前的任务后空闲下来的时间,tavaili表示任务ti的所有前驱任务都已经执行完毕并且将数据都传输到ti上的时间,B(vmti,vmtj)表示虚拟机vmti与vmtj之间的带宽。任务ti的完成时间为FT(ti,vmti)=ST(ti,vmti)+ET(ti,vmti)。 (2)式中,任务ti在虚拟机vmti上的执行时间ET(ti,vmti)=w(ti)/vmcti,w(ti)为任务ti的指令数,从第一个任务开始执行到最后一个任务结束的时间段称为整个工作流的完成时间,因此工作流的完成时间makespan = maxi∈(1,N){FT(ti,vmti)}。 (3)2.2 费用对于虚拟机vmm,tsi和t ei分别为虚拟机vmm上第一个与最后一个被执行的任务,ST(tsi,vmm)为tsi的最早开始时间,FT(tei,vmm)为tei的完成时间,则vmm 的费用cost(vmi)= !FT(tei,vmm)-ST(tsi,vmm)"×vmpi。(4)因此,整个工作流的费用等于所有虚拟机的费用之和,即cost=∑Mm=1cost(vmm)。 (5)2.3 可靠性工作流的可靠性是所有任务都执行成功的可能性,即每个资源上任务执行成功的可能性和任务之间传输路径上传输成功的可能性之和。假设系统的调度方案表示为S:T×R→{0,1},矩阵S 表示工作流中所有任务到所有虚拟机资源的有效映射,若其中的元素Si,m值为1,则表示任务ti被调度到虚拟机vmm上执行。根据文献[12-13],虚 拟 机vmm在时间段t 内的可靠性为e-vmfm·t,则虚拟机vmm在传输时间段t内 将 数 据 传 输 到 虚 拟 机 vmn的 可 靠 性 为e-tf(vmm,vmn)·t,其中tf(vmm,vmn)表 示 虚 拟 机vmm与vmn之间的传输失败率。在调度方案S 中,虚拟机vmm上所有任务的执行时间ET(vmm)=∑Ni=1si,mET(ti,vmm), (6)则虚拟机vmm的可靠性P(vmm)=e-f(vmm)·ET(vmm)。 (7)同理可得数据在虚拟机vmm和vmn间的传输时间CT(vmm,vmn)=∑Ni=1∑j≠isi,msj,nCT(ti,tj,vmm,vmn),(8)则虚拟机vmm和vmn间的传输可靠性为TP(vmm,vmn)=e-tf(vmm,vmn)·CT(vmm,vmn)。 (9)综上所述,可得整个工作流的可靠性即流程成功执行的可能性reliability =∏Mm=1P(vmm)∏Mm=1∏n≠mTP(vmm,vmn)。(10)2.4 调度目标本文研究的调度问题描述如下:min cost。s.t. maskspan≤Deadline;reliability ≥ MinReliability。 (11)式中:Deadline表示用户预先确定的工作流截止时间,MinReliablity 表示用户要求的最低可靠性。3 基于萤火虫算法和动态优先级的云工作流调度3.1 标准萤火虫算法FA 是一种智能搜索算法,它 将搜索及 优化过程模拟成萤火虫之间相互吸引和位置迭代更新的过程,从而将求解最优值的问题看作为寻找最亮萤火虫的问题,搜索过程即为位置好的萤火虫不断取代位置不好的萤火虫的过程。发光亮的萤火虫会吸引发光弱的萤火虫向它移动,发光越亮表示萤火虫的位置越好,最亮萤火虫表示函数的最优解。萤火虫之间的吸引度只与发光强度和距离有关,发光强的萤火虫会吸引周围发光弱的萤火虫,但是其吸引度随距离的增大而逐渐减小。定义1 萤火虫i对萤火虫j 的吸引度为βi,j =β0e-γr2ij。 (12)式中:β0为最大吸引度,即在光源处的吸引度;γ 为695计算机集成制造系统 第23卷光吸收系数,一般取值0~1,其值越大,表明被空气介质吸收的荧光越多,被接收到的亮度越小,吸引度越小;rij为萤火虫之间的距离,用笛卡尔距离表示,距离越远,吸引度越小。定义2 萤火虫i被萤火虫j 吸引而向其移动的位置更新由式(13)计算:xi(t+1)=xi(t)+βij(xj(t)-xi(t))+α(random()-0.5)。 (13)式中:t为迭代次数,xi和xj为萤火虫i和j 所在的空间位置;βij为萤火虫i 和j 间的吸引度大小;α 为步长因子,一般取[0,2]区间内的数。3.2 适用于云工作流调度的萤火虫算法标准 FA 的解空间属于连续的实数域空间,云工作流调度的解空间属于离散的整数域空间。为了使面向连续问题的 FA 能适用于求解云工作流调度优化问题,本文对标准 FA 进行改进,提出适用于云工作流调度问题的萤火虫算法云工作流调度问题的萤火 虫 算 法 (Cloud Workflow Firefly Algorithm,CWFA)。(1)位置编码对萤火虫的位置进行重新编码,使重新编码后的位置都代表一种调度方案,即任务和虚拟机之间的映射关系。假设萤火虫的个数为c,工作流中任务的个数 为 N,可 用 来 进 行 调 度 的 虚 拟 机 个 数 为M,则第i个萤火虫的位置可用一个 N 维向量xi=(xi,1,xi,2,…,xi,j,…,xi,N)表示,其中 xi,j ∈(1,2,…,M)。一个萤火虫的位置向量表示一种可行的调度方案,该位置向量中的每一个元素表示了流程中的一个任务由哪个虚拟机调度执行。(2)适应度函数为了体现费用为目标、时间和可靠性为约束的特点,本文定义某一种调度方案S 的适应度函数f(S)=1-min_costS.cost, S.makespan ≤ Deadline and S.reliablity ≥ MinReliablity;MinReliablityS.reliablity+1-min_costS.cost, S.makespan ≤ Deadline and S.reliablity < MinReliablity;1-min_costS.cost+S.makespaneDeadline, S.makespan > Deadline and S.reliablity ≥ MinReliablity;1-min_costS.cost+S.makespaneDeadline+MinReliablityS.reliablity, S.makespan > Deadline and S.reliablity ≤ MinReliablity烅烄烆。(14)式中:min_cost表示流程执行的最低费用,MinRe-aliability 表示用户要求的最低可靠性,Deadline表示截止时间。当调度方案 S 不满足时间或可靠性约束时,用S.makespane/Deadline,MinRealiabili-ty/S.reliability 对时间和可靠性进行惩罚;当调度方案S 满足所有约束时,用1-min_cost/S.cost限制费用的取值范围。(3)萤火虫距离定义两只萤火虫之间的距离(即两种调度方案的距离)rij =∑nk=1(l(xi,k ≠xj,k))槡2。 (15)式中l(·)为指示函数,当参数为真时函数值为1,否则为0(l(true)=1,l(false)=0)。(4)萤火虫位置更新若萤火虫i的周围有比其更亮的萤火虫,则该萤火虫向比它亮的萤火虫移动。假定比它亮的萤火虫为j,移动时根据吸引度的大小进行位置更新,定义如下位置更新公式:xi,k(t+1)=xj,k(t),βi,j >θ;xi,k(t),βi,j ≤θ烅烄烆。(16)式中βi,j表示萤火虫i 对萤火虫j 的吸引度。吸引度作为一个概率,用来决定xi是否从xj继承某个解维度。在判定前,随 机得到 0~1 范围内 的取值θ,当吸引度大于θ时,xi从xj处继承某个解维度的值,否则保留原始的值。若萤火虫i的周围没有比其更亮的萤火虫,则萤火虫i为最优萤火虫,其移动方式与普通萤火虫并不同,本文定义了最优萤火虫的位置更新规则,命名为“最优调整规则”,该规则的核心思想为:在不满足时间约束的情况下,优先满足截止时间,因为整个工作流的完成时间取决于最终完成时间最大的虚拟机,所以减少这个虚拟机的最终完成时间,理论上能减少整个工作流的完成时间;在满足截止时间的情况下则随机移动。3.3 CWFA算法流程3.3.1 动态优先级现有的大部分云工作流调度算法在确定任务执6966;修订日期:2016-09-13。Received 26Feb.2016;accepted 13Sep.2016.基金项目:国家自然科学基金资助项目(61472112)。Foundation item:Project supported by the National Natural Science Foundation,China(No.61472112).基于萤火虫算法和动态优先级的多 QoS云工作流调度郑宏升,俞东进+ ,张 蕾(杭州电子科技大学 计算机学院,浙江 杭州 310018)摘 要:为了提高用户的满意程度、降低运营成本,考虑时间、费用和可靠性3个重要的服务质量因素,针对时间和可靠性双重约束下费用最小化的云工作流调度问题,提出基于萤火虫算法和动态优先级的最优调度方案。结合云工作流调度问题的特点,重新定义了萤火虫算法中的位置、距离以及位置更新方式,同时对于每一种调度方案,采用动态优先级算法确定任务顺序,以减少工作流完成时间。在 WorkflowSim 平台上进行模拟调度仿真实验,证明了该方法在收敛速度和最优值方面均优于传统的云工作流调度算法。关键词:云工作流;调度;可靠性;动态优先级;服务质量;萤火虫算法中图分类号:TP311   文献标识码:AMulti-QoS Cloud Workflow Scheduling Based on Firefly Algorithm and Dynamic PrioritiesZHENG Hongsheng,YU Dongjin+,ZHANG Lei(School of Computer,Hangzhou Dianzi University,Hangzhou 310018,China)Abstract:To improve the user satisfactory and reduce the operating costs,three important attributes of Quality ofService(QoS)which included time,costs and reliability were taken into account.To solve the scheduling problemof cloud workflow with minimized cost and constrains between time and reliability,an optimal scheduling approachbased on firefly algorithm and dynamic priorities was proposed.The position,distance and updating mode of posi-tion in firefly algorithm were redefined and the priorities were dynamically set for task order to reduce the overallcompletion time.The experimental results conducted on WorkflowSim demonstrated that the proposed approach wassuperior to the traditional cloud workflow scheduling algorithm with regard to both the convergence speed and theobtained optimal value.Keywords:cloud workflow;scheduling;reliability;dynamic priority;quality of service;firefly algorithm0 引言近年来,随着云计算技术的迅猛发展,越来越多的组织将传统的业务过程与应 用迁移到云计算环境。云工作流调度指将相互之间具有依赖关系的工作流任务映射到虚拟机资源上执行的过程,它决定了工作流实例执行的成败和执行效率的高低[1]。一般说来,云工作流调度问题 是一个 NP-hard问题,对于用户给定的工作流实例,调度过程存在较大的改进和优化空间。目前国内外学者在工作流优化调度方面做了许多有价值的研究工作。关于优 化 工作流完 成时间(makespan)问题,Shishir等[2]针对单工作流应用,提出一种针对异构资源的工作流调度经典算法———异构最早完成时间(Heterogeneous Earliest FinishTime,HEFT),该算法根据任务的平均执行时间和通信时间计算出一个优先级,在任务分配时选择具有最大优先级的任务,并将其调度到完成时间最小 郑宏升 等:基于萤火虫算法和动态优先级的多 QoS云工作流调度行顺序时采用静态优先级的方式,如 HEFT 算法。这种方法使用任务平均执行时间,只要计算一次便可确定优先级。然而在实际中,当分配方案确定时,任务的执行时间根据其被具体分配到的虚拟机进行计算。因此,可以根据实际分配方案动态调整任务的优先级,称之为动态优先级。该方法的主要思想是每次在可执行任务列表中找到完成时间最早的任务分配高优先级,具体算法如算法1所示。这里用变量entityNum 表示每个任务还有多少父任务未确定优先级,用变量idx 表示优先级(idx 越小优先级越高),用vmTaskList表示每个虚拟机中的可执行任务列表。算法的具体执 行 过 程 如 下:① 将 起 始 任 务 添加到 对 应 的 虚 拟 机 可 执 行 列 表 中 (vmTaskList,第5~6行),初 始 化entityNum 为 每 个 任 务 对 应的父任务个数(第8行);② 遍 历 每 个 虚 拟 机 的 可执行列表,计 算 可 执 行 任 务 的 完 成 时 间 (第 12~15行);③在所 有 可 执 行 任 务 中 找 到 完 成 时 间 最早的任务ttask_sel(第16~18行);④为ttask_sel分配优先级,删除对应虚拟 机 中 可 执 行 任 务 列 表 中 的 该任务(第19~21行);⑤ 更 新ttask_sel所 有 子 任 务 在entityNum 中的状态,若变为可 执 行 任 务,则 添 加到对应虚 拟 机 的 可 执 行 列 表 中 (第 22~25 行 );⑥重复步骤②~⑤,直 到 每 个 虚 拟 机 都 没 有 可 执行的任务。算法1 动态优先级算法。输入:M //任务与资源的映射关系,M(ti)表示任务ti分配到的虚拟机。输出:rank(ti),1≤i≤N //任务优先级。01:idx=0; //动态02:entityNum(Task→parentNum)←  //该任务还有多少父任务未分配优先级03:vmTaskList(VM→Tasks)←   //虚拟机中可以开始执行的任务04:for each task ti05: if tihas not parents then06:   vmTaskList.get(vmMi).add(ti)07:  else08:   entityNum.get(ti)←ti 的父任务数09:while vmTaskList.isNotEmpty()do  //还有虚拟机有任务要分配10: min_end←∞11: task_sel←null12: for each resource vmjin vmTaskList13:  Tasksj← vmTaskList.get(vmj)14:  for each task tiin Tasksj15:   runtime← 根据式(2)计算得到任务的完成时间;16:   if runtime<min_end17:    min_end← runtime18:    task_sel←i19: res_sel←M(task_sel)20: vmTaskList.get(res_sel).remove()21: rank(task_sel)=idx++22: for each task tiin succ(task_sel)23:  entityNum.get(ti)--24:  if entityNum.get(ti)==025:   vmTaskList.get(vmMi).add(ti)26:return rank3.3.2 算法流程算法2给出了基于 CWFA 的云工作流调度算法的伪代码实现方案。算法的输入为任 务列 表和虚拟机列表,输出为最优适应度值bestFitness和最优分配方案bestDop。算法执行主要分为以下几个步骤:(1)初始化算法基本参数。设置萤火虫的数目v、光吸收系数γ、最大迭代数itMax、步长因子α,对应算法2中的第1~2行。(2)生成初始萤火虫种群。随机生成萤火虫位置,根据式(14)计算适应度函数值作为萤火虫的亮度。设置最 优 适应 度 值bestFitness 为 初 始 萤 火 虫中的最优适应度值、最优分配方案bestDop 为相应的萤火虫位置,对应算法2中的第3~6行。(3)萤火虫 的 移 动。 在 一 只 萤 火 虫i的 搜 索范围内,找 到 所 有 比 它 亮 的 萤 火 虫 并 放 到 集 合Niti={niti,1,niti,2,…,niti,ni}中,其 中:ni表 示 集合中萤火虫的 个 数,niti,j表 示 萤 火 虫 的 编 号。 遍历集 合 Niti,萤 火 虫i被 萤 火 虫 niti,j吸 引 而 向niti,j移 动,1≤j≤ni。 根 据 式 (12)计 算 萤 火 虫niti,j对萤火虫i的 吸 引 度,根 据 式 (13)进 行 位 置更新。若周围没有 比 它 更 亮 的 萤 火 虫 (Niti为 空集),则该只萤火虫为最 优 萤 火 虫 ;若 对 应 的 调 度方案没有满足时间 约 束,则 在 最 终 完 成 时 间 最 大的虚拟机上挑选出 运 行 时 间 最 短 的 任 务 ,将 其 分配到最终完成时间 最 小 的 虚 拟 机 上 ,优 先 满 足 时间约束。 若 满 足 截 止 时 间,则 随 机 移 动,对 应 代码的10~13行。(4)更新亮度。更新萤火虫位置后,重新计算适应度值,若 适 应 度 值 大 于bestFitness,则 设 置best-Fitness为该适应度值,并更新bestDop,对应算法2中的第14~17行。697计算机集成制造系统 第23卷(5)当前迭代次数it=it+1,若it<itMax,则转步骤(3)。(6)输出最优适应度值bestFitness和最优分配方案bestDop。算法2 云工作流调度算法(CWFA)。输入:T={t1,t2,…,ti,…,tn}//任务列表; VM ={vm1,vm2,…,vmm}//虚拟机列表。输出:bestFitness,bestDop//最优适应度值,最优分配方案。01: 初始化:萤火虫数v、最大迭代次数itMax、光吸收系数γ02: 最大吸引度βo、步长因子α.03: 萤火虫位置空间dpos←n*v的矩阵;04: 萤火虫亮度空间fvalue←n维向量;05: [dpos,fvalue]←initValue();06: bestFitness,bestDop←fvalue[i]=max{dops[i]},dpos[k]07: for it=1to itMax do08:  for i=1to v do09:  萤火虫集合 Nit←选择更亮的萤火虫10:  if Nit≠ do11:   根据式(12)更新吸引度β,根据式(13)更新dpos[i]12:  else13:   根据“最优调整规则”进行位置更新   //该萤火虫为最亮萤火虫14:  update fvalue[i]15:   if fvalue[i]<bestFitness do16:    bestFitness=fvalue[i]17:    bestDop=dops[i]18:return bestDop4 实验分析4.1 实验配置实验使用 WorkflowGenertor[14]生成任务数为50,100,200和300的激光干涉引力波天文台(La-ser Interferometer Gravitational wave Observato-ry,LIGO)应用的工作流模型。LIGO 是一个通过分析压缩双星系统(如中子星和黑洞)获取到的数据来探测引力波的天体物理学应用。LIGO 中生成的任务同质化程度较低,其基本结构如图1所示。所有 实 验 基 于 以 下 环 境:处 理 器 为 Intel(R)Core(TM)i5-2450M,2.5 GHz;4 GB 内 存;Windows 764位操作系统。假设有一个数据中心,其有10个虚拟机,每个虚拟机的计算速度在500~1 500MIPS之间随机选取,虚拟机之间的带宽是一个500Mbps~1.5Gbps之间的随机数。假设虚拟机的失败率和虚拟机之间的传输失败率符合均匀分布,其取值范围为10-3/h~10-4/h[15]。虚拟机的收费模拟亚马逊的收费模式,即虚拟机速度越快、费用越高。生成的虚拟机具体配置如表1所示,其中虚拟机之间的传输数据带宽按照双方最小的带宽计算。表1 不同类型虚拟机实例参数设置编号计算速度/MIPS带宽/Mbps单价/($·h-1)失败率/(×10-4·h-1)1  1 419  777  4.26  5.902  515  961  1.54  6.203  1 055  538  3.17  4.094  1 421  1 004  4.26  3.455  1 083  1 435  3.25  3.106  510  1 433  1.53  4.217  1 474  1 438  4.42  8.908  551  1 264  1.65  8.159  1 399  721  4.20  2.9810  825  724  2.47  6.45实验需要用户给出一个截止时间和可靠性约束,这两个取值要求在合理范围之内。本文选取的截止时间依据 HEFT 算法的实验结果设置,即将截止时间设置为 HEFT 算法的1.15倍。选取的可靠性约束要大于一个最低可靠性,这个最低可靠性是将所有任务都分配到可靠性最差的虚拟机上时流程执行的可靠性。完成时间和可靠性约束的取值如表2所示。698 郑宏升 等:基于萤火虫算法和动态优先级的多 QoS云工作流调度表2 完成时间和可靠性约束实例类型 完成时间约束 可靠性约束LIGO-50  2 600  0.65LIGO-100  4 600  0.63LIGO-200  15 000  0.54LIGO-300  27 000  0.504.2 参数分析本文有萤火虫数目v和步长因子α两个重要参数。经过实验分析,步长因子对实验结果几乎没有影响,因此下面只分析萤火虫数目对算法目标值的影响。实验分析了任务数为50,100,200,300共4种LIGO 工作流模型下,参数v 在 25~100范围内对算法目标值的影响。对于每种参数组合,运行 CW-FA 100次,选取平均适应度值来分析萤火虫数目v对算法结果的影响,如表3所示。从表3可以看出,在选定数据集的情况下,随着萤火虫数目的增加,适应度值越来越好。这是因为萤火虫数目的增加会扩大解的搜索范围,使得到更优解的概率增加。从表3也可以看出,随着萤火虫数目的增加,满足约束的解的个数也随之增加。表3 参数v在不同数据集下对适应度值的影响适应度值 25  50  75  100LIGO-50  1.504  1.339  1.211  1.108LIGO-100  1.463  1.287  1.000  0.859LIGO-200  0.264  0.216  0.212  0.199LIGO-300  0.143  0.104  0.090  0.0854.3 结果对比4.3.1 与标准萤火虫算法对比经过实验分析得到了模型参数取值:萤火虫个数v=50,步 长 因 子α=1。 此 外,取 迭 代 次 数 为100。在实验中,首先对算法收敛次数进行比较。在任务数为50,100,200,300 时,CWFA 和标 准萤火虫算法(FA)所得调度方案的适应度值变化情况如图2所示。从图2可以看出,CWFA 在不同任务数情况下得出的最优调度方案的适应度值均比标准萤火虫低。在任务数为50~100时,CWFA 在迭代次数较少时就已经找到了近似最优解,说明本文算法可以较快地寻找到较优的调度方案。同时在不同任务数下,可以发现 CWFA 生成的调度方案的适应度值均比标准 FA 低。699计算机集成制造系统 第23卷在任务数为50,100,200,300时,两种算法的最优调度方案费用值比较如图3所示。从图3可以看出,随着任务量从50增长至300,CWFA 生成的调度方案费用值均较低,并且其调度方案费用值与标准 FA 的差值越来越大。说明 CWFA 更加适用于任务数较多的情况,这是因为在任务数较多的情况下,CWFA 可以在较大范围内搜索,体现了算法全局搜索能力的优势。4.3.2 与 GA,S-CLPSO 算法对比下面 将 CWFA 与 遗 传 算 法 (Genetic Algo-rithm,GA)、基于集合的全面学习的离散粒子群优化 (discrete version of Comprehensive LearningParticle Swarm Optimizer based on set-based par-ticle swarm optimization,S-CLPSO)算法两种随机搜索算法进行对比,这两种算法都考虑了时间、费用和可靠性3种约束。(1)GA 文献[16]提出一种费用为约束、完工时间最小且任务执行失败率最低的 GA,用来解决云工作流调度问题。实验设定:初始种群100,迭代次数100,交叉概率0.5,变异概率0.01。(2)S-CLPSO 该方法将 PSO 算法离散化,用于求解云工作流调度问题,并允许用户自定义不同类型的 QoS 约 束[17]。其 中 S-CLPSO 有 惯 性 权 重w、学习因子c1和c23个重要参数。根据实验得到较优的参数:w=0.8;学习因子c1=1,c2=1。表4给出 了 不 同 任 务 数 的 LIGO 工 作 流 模 型下,3种算法在本文实验环境下运行 100次得出的调度方案各个指标的平均值。表4 不同任务数下3种算法的最优调度结果对比调度结果CWFA  GA  S-CLPSO费用 完成时间 可靠性 费用 完成时间 可靠性 费用 完成时间 可靠性LIGO-50  88  2 579  0.63  103  2 534  0.67  101  2 436  0.67LIGO-100  168  4 505  0.64  194  4 576  0.66  187  4 662  0.66LIGO-200  342  7 914  0.62  388  8 854  0.61  375  10 934  0.61LIGO-300  517  12 536  0.61  569  16 058  0.61  553  18 342  0.56在费用优化方面(如 图 4a),随 着 任 务 量 从 50增 长 至 300,3 种 算 法 的 费 用 均 越 来 越 高,但 是CWFA 生成的调度方 案 费 用 值 均 最 低。S-CLPSO和 GA 的费 用 随 着 任 务 数 的 增 多 远 高 于 CWFA。在完成 时 间 方 面 (如 图 4b),当 任 务 数 为 50 时,CWFA 的完工时间高于 S-CLPSO 和 GA。但随着任务数的 增 加,CWFA 调 度 结 果 的 完 成 时 间 均 明显优于其他算法,这是因为 CWFA 采 用 动 态 优 先级调整任务之间的执行顺序,使得完成时间更短。5 结束语本文针对时间和可靠性双重约束下费用最小化的云工作流调度问题,提出基于 FA 和动态优先级的最优调度方案搜索方法。重新定义了 FA 中的位置、距离和位置更新方式,同时对每一种调度方案,采取动态优先级确定任务顺序。通过仿真实验结果证明了本文所提算法在费用和完工时间方面不但均优于传统 FA,而且优于 GA 和S-CLPSO 算法。790

[返回]
上一篇:面向二进制程序的空指针解引用错误的检测方法
下一篇:基于凸多面体抽象域的自适应强化学习技术研究