截止时间约束的工作流调度自适应进化方法
|
摘要
工作流是云计算环境下任务的主要表现形式,工作流任务调度问题是一个典型的NPC问题,进化算法在解决这类问题方面具有明显优势。然而,传统的进化算法容易陷入局部最优,造成早熟结果。提出一种考虑截止时间约束条件下的自适应遗传进化方法,采用适应度修正均值来自适应计算交叉概率、变异概率,引入惩罚函数自适应修正适应度,以避免陷入局部最优。在WorkflowSim仿真环境上,选用具有代表性的Montage科学工作流,与5种算法的对比实验结果表明在4种不同截止时间约束下,所提方法的约束满足程度最高,且能够在贴近用户截止时间约束的执行时间下花费更小的成本。
Workflow is the main manifestation of tasks in cloud computing environment. Workflow task scheduling problem is a typical NPC problem. Evolutionary algorithm has obvious advantages in solving such problems. However, the traditional evolutionary algorithm has the problem of being easy to fall into the local optimum and causing premature convergence. In this study, a deadline-constrained adaptive genetic evolutionary approach which calculates the probability of mutation and selection based on the modified mean fitness adaptively is proposed, and a penalty function to update the fitness adaptively to avoid falling into the local optimum is introduced. On the basis of WorkflowSim simulation environment, the representative Montage workflow is selected. Compared with five algorithms, experimental results show that under the constraints of four different deadlines, the proposed method had the best constraint satisfaction rate and smaller costs at execution times closed to user's deadline constraints.
Workflow is the main manifestation of tasks in cloud computing environment. Workflow task scheduling problem is a typical NPC problem. Evolutionary algorithm has obvious advantages in solving such problems. However, the traditional evolutionary algorithm has the problem of being easy to fall into the local optimum and causing premature convergence. In this study, a deadline-constrained adaptive genetic evolutionary approach which calculates the probability of mutation and selection based on the modified mean fitness adaptively is proposed, and a penalty function to update the fitness adaptively to avoid falling into the local optimum is introduced. On the basis of WorkflowSim simulation environment, the representative Montage workflow is selected. Compared with five algorithms, experimental results show that under the constraints of four different deadlines, the proposed method had the best constraint satisfaction rate and smaller costs at execution times closed to user's deadline constraints.
引文
[1]黄冀卓,王湛,马人乐.一种新的求解约束多目标优化问题的遗传算法[J].计算机工程与应用,2006,42(23):47-51.
[2]Rodriguez M A,Buyya R.Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J].IEEE Transactions on Cloud Computing,2014,2(2):222-235.
[3]Vockler J,Juve G,Deelman E,et al.Experiences using cloud computing for a scientific workflow application[C].USA:[s.n.],2011:15-24.
[4]Ostermann S,Iosup A,Yigitbasi N,et al.A performance analysis of ec2 cloud computing services for scientific computing[J].Cloud Computing,2009,34:115-131.
[5]Zhang J,Chung S H,Lo W L.Clustering-based adaptive crossover and mutation probabilities for genetic algorithms[J].IEEE Transactions on Evolutionary Computation,2007,11(3):326-335.
[6]Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems Man & Cybernetics,2002,24(4):656-667.
[7]Tessema B G,Yen G G.A self adaptive penalty function based algorithm for constrained optimization[C].[S.l.]:[s.n.],2006:246-253.
[8]Schad J,Dittrich J,Quiané-Ruiz J A.Runtime measurements in the cloud[J].Proceedings of the Vldb Endowment,2010,3(1/2):460-471.
[9]Wu Z,Ni Z,Gu L,et al.A revised discrete particle swarm optimization for cloud workflow scheduling[C].[S.l.]:[s.n.],2010:184-188.
[10]Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems Man & Cybernetics,2002,24(4):656-667.
[11]Liu L,Zhang M,Buyya R,et al.Deadline-constrained coevolutionary genetic algorithm for scientific workflow scheduling in cloud computing[J].Concurrency and Computation:Practice and Experience,2017,29(5):1-12.
[2]Rodriguez M A,Buyya R.Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J].IEEE Transactions on Cloud Computing,2014,2(2):222-235.
[3]Vockler J,Juve G,Deelman E,et al.Experiences using cloud computing for a scientific workflow application[C].USA:[s.n.],2011:15-24.
[4]Ostermann S,Iosup A,Yigitbasi N,et al.A performance analysis of ec2 cloud computing services for scientific computing[J].Cloud Computing,2009,34:115-131.
[5]Zhang J,Chung S H,Lo W L.Clustering-based adaptive crossover and mutation probabilities for genetic algorithms[J].IEEE Transactions on Evolutionary Computation,2007,11(3):326-335.
[6]Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems Man & Cybernetics,2002,24(4):656-667.
[7]Tessema B G,Yen G G.A self adaptive penalty function based algorithm for constrained optimization[C].[S.l.]:[s.n.],2006:246-253.
[8]Schad J,Dittrich J,Quiané-Ruiz J A.Runtime measurements in the cloud[J].Proceedings of the Vldb Endowment,2010,3(1/2):460-471.
[9]Wu Z,Ni Z,Gu L,et al.A revised discrete particle swarm optimization for cloud workflow scheduling[C].[S.l.]:[s.n.],2010:184-188.
[10]Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems Man & Cybernetics,2002,24(4):656-667.
[11]Liu L,Zhang M,Buyya R,et al.Deadline-constrained coevolutionary genetic algorithm for scientific workflow scheduling in cloud computing[J].Concurrency and Computation:Practice and Experience,2017,29(5):1-12.