ToSolvetheGridWorkflowSchedulingProblemBasedontheEntropyofChaosGeneticAlgorithm谢泉XIEQuan曰邹杰ZOUJie（福州大学数学与计算机学院，福州350800）（SchoolofMathematicsandComputerScience，FuzhouUniversity，Fuzhou350800，China）
Abstract:Themainideasofthegriddevelopmentisusingcomputingresourceseffectivewhichdistributedinallovertheworld.Ingridenvironment,theworkisdescribedbymanyinterdependenttasks,sotheworkflowschedulingwillmeetenormouschallenges.Thisarticleputsforwardanimprovedchaosgeneticalgorithmtosolvetheproblemofschedulingoptimizationintheworkflowapplication.Itusestheconceptofentropydynamicallyadjustcrossoverandmutationprobabilitytooptimizethetraditionalgeneticalgorithm,andfinallytheexperimentalresultsshowstheeffectivenessofthealgorithm.关键词院网格计算；工作流调度；混沌遗传算法；熵Keywords:gridworkfolw；workflowscheduling；chaos-geneticalgorithms；entropy中图分类号院TP393文献标识码院A文章编号院1006-4311（2014）01-0194-030引言网格工作流调度问题不同于一般的任务调度，在调度时不仅要考虑为任务选择一个最佳资源，还要考虑各个任务之间的时序与因果关系等一系列的约束条件，以及协调各个任务的执行来达到最终的目标，这种调度集中于多元化相互依存的管理任务的执行及映射[1]。网格工作流调度问题中，在既定的工艺流程下，每一个任务有不同的服务器或机器可供选择，它们完成时间不同，且一个服务器上可能同时有不同的任务需要执行，它类似于柔性流水车间调度问题，相比于传统车间调度问题它更加复杂，大大增加了调度的灵活性，更符合生产的实际情况[2，3]。在现代制造业中，它具有很强的代表性，可以广泛应用于精密仪器生产，化工，制药等流程工业中。
一般来说，在分布式服务上映射任务的问题属于NP难题。尽管工作流调度可以进行穷举搜索，但复杂的求解方法不仅效率低下而且很难得到问题的最优解。本文为解决动态网格环境下的工作流调度问题，拟采用一种鲁棒性较强的全局寻优算法———遗传算法[4]。遗传算法的优点是实际操作简单，搜索能力强，易于并行化，但其缺点是具有局限性，容易产生收敛停滞和易陷入局部极值点的问题[5]。
因此本文在传统遗传算法的基础上，引入混沌系统，并利用信息熵的概念动态调整交叉和变异概率，从而提高了算法的准确性及效率。
1工作流调度问题描述网格结构可以利用工作流简化成简洁的结构模型[6]，以便在研究问题时能够从繁琐的网格结构中得到一种有利于调度研究的模型。一个工作流的运行过程通常可以利用有向图模型（DAG）来建模。设定工作流调度问题为：淤定义一组有限的任务集Ti（i=1，2，…，n）和一组有向连接任务（Ti,Tj）的弧的表单，其中任务Tj是Ti的子任务，父任务执行完毕后子才能开始执行子任务。定义C为完成全部作业任务的成本预算，D为最后一项作业任务完成的截止期限。于定义一组能够执行任务Ti的服务集Sji（i=1，2，…，n，j=1，2，…，mi，mi约m），m为可用服务器的总数。
其中每个任务只能由一个服务器来执行。盂定义服务器Sji执行任务Ti的时间为Tji，费用为Cji，工作流调度问题即是将每一个任务Ti映射到合适的服务Sji上。
2混沌遗传算法设计混沌是一种在确定性系统中不定期而又长期的行为，其对初始条件十分敏感，且与杂乱的随机系统具有明显的差异。混沌系统的随机性实际上是受到约束的，对于空间具有很强的遍历性，这种模式更符合生物的进化。与原有的随机搜索相比，混沌系统的遍历性能够在全局范围内进行无重复搜索，减少搜索的盲目性及随机性[7]，进而提高搜索的效率。以下是改进的混沌遗传算法的具体实现过程。
2.1编码对于网格环境下的工作流调度问题，用传统的基于工序的编码方法将无法得到最终的解，因为其不仅简单的对所有任务的执行进行合理的排序，更为重要的是为每一个任务的执行分配一个合理的服务器，使得最终的结果满足用户的需求。
图1中的染色体表示工作流调度的一个可行解，其由两部分组成，第一部分为任务的编码，第二部分为服务分配的编码，它的总长度等于调度问题的任务总数。
2.2种群初始化及适应度函数在生成初始种群时，本文利用混沌系统来取代原有的随机生成方式。具体做法
本文使用了J.Yu和R.Buyya[5]的数据集进行测试，主要参数为：种群规模为10，交叉概率和变异概率见2.4节，迭代次数为100，数据集连续运行5次取最优结果。得到的实验结果如图4。
除以用户预算的结果。从图中可以看出在较低预算下两种算法表现的都不能令人满意，然而随着用户给定的预算的增加，两个算法的结果都符合用户的需求，但混沌遗传算法（CGA）在每一级预算下的表现都优于TGA。
由实验结果可知，本文所设计的混沌遗传算法在基于用户需求的约束下，表现出的结果优于传统的遗传算法。
4结束语针对动态网格环境下工作流调度的特点，本文设计了一种带熵的混沌遗传算法，此算法将混沌机制取代原有算法中的完全随机方式生成初始种群，并利用信息熵的公式动态改变交叉、遗传概率，这样既有效地克服了遗传算法的易早熟收敛等缺陷，又能提高搜索最优解的效率。实验测试结果表明本文所提出的算法更优于传统的遗传算法。
参考文献院[1]李金忠,夏洁武,曾劲涛等.网格工作流调度算法研究综述[J].计算机应用研究,2009,26(8):2916-2820.[2]李超,朱巧明,李培峰等.一个网格服务工作流的动态调度算法[J].计算机应用研究,2008,25(11):3285-3287.[3]田国忠,于炯,侯勇等.基于资源状态可靠度的网格工作流调度算法[J].计算机工程与应用,2008,44(18):115-118.[4]WannapornTeekeng,AritThammano.ModifiedGeneticAlgorithmforFlexibleJob-ShopSchedulingProblems[J].ProcediaComputerScience,2012,12:122-128.[5]J.YuandR.Buyya.SchedulingScientificWorkflowApplicationswithDeadlineandBudgetConstraintsusingGeneticAlgorithms[J].ScientificProgramming,2006,14:217-230.[6]ShayanShahand,StephenJ.Turner,WentongCai,etal.AdynamicWebserviceschedulinganddeploymentframeworkfordata-intensiveGridworkflows[J].ProcediaComputerScience,2010(1):593-602.[7]谭跃,谭冠,叶勇,伍雪冬.具有混沌局部搜索策略的双种群遗传算法[J].计算机应用研究,2011,28(2):469-471.[8]李功波.基于工作流的网格制造调度算法研究[D].华南理工大学硕士学位论文,2010:9-56.
客服QQ：30444492琼网文【2021】1550-113号
增值电信业务经营许可证：琼B2-20210322
出版物经营许可证：新出发龙华出字第(2021)009号
广播电视节目制作经营许可证：(琼)字第00779号
版权所有 ©2002-2024 期刊网(www.qikanchina.com) 琼ICP备2021005105号
