全局调度主要目标是在满足任务执行顺序的前提下,根据任务的特点将任务算子放到最适合其运行的节点上去执行。目前,主要有集中式分布式分层模型种主要的调度方式,集中式调度有个中央调度模块,更具设定的调度算法进行计算后将任务算子分发给节点运行。分布式调度模型中每个计算节点各自为政,维护自身的负载,不同节点间通过通信进行数据交换由协同工作方式进行任务分配,通过接收周围节点的工作状态把任务从负荷重的节点转移到相对空闲的节点。分层模型下,计算节点先被分为几个簇,由簇头节点充当中心调度模块的角色,把收到的任务分配给簇内节点执行。为了简化应用环境避免节点频繁信息交换以及维护问题,本文的算法在集中式调度模型的基础上构建。现有全局任务调度算法分布式系统集群的全局任务调度算法相对复杂,在调度时涉及致性可行性等众多问题,般是在应用具体需求的限制下寻找切实可行,而未必是绝对最优解,在此出现的许多研究成果很多都是基于图论排队论运筹学多目标规划遗传学理论等近似技术或者启发性的方法。总体上可以分为静态和动态两个大类型,前者在任务执行之前已经按照事先约定的规则进行了划分,静态任务调度仅仅是根据调度表中的分配规则进行全局任务分配,缺乏自适应性,在简单系统中配合集中式的分布架构能实现很好的效果,但是,在稍微复杂的网络环境下难以根据数据流变化调节分配规则。由此,动态调度被广泛应用于分布式流计算系统中,同单节点调度类似,全局动态调度同样依据图中对任务关系的描述,在对任务作出粒度分析后进行调度。下面简单介绍两类任务调度算法基于图论的算法基于图论的算法是目前应用比较广泛的算法,其比较适合计算机集群的拓扑特点,利用了分网络中的最小截概念网络图,中存在连通目的节点源节点的边,则,均有各自的基于权的函数,若去除条边,则网络图变为非联通图,这些边的集合便是截集。基于图论的算法首先构造分图,而任务的分配效率用截集的权表示,最小截集即是最优任务。基于规划的策略规划是基于目标函数的优化方法,能反应出问题的应用场景,算法首先将特定情形下的需求抽象成量化的数学表达式,通过限制条件求目标函数极值得到可行的规划方案。这种方法的有点是可以更加真实的概括需求。遗传算法概述遗传算法是根据生物进化论中适者生存的观点推演而来的随机化搜索算法,其思想源于达尔文的自然学则学说,最先由教授于上世纪十年代中期提出,后经过不断的演变优化,目前在各个领域都有广泛的应用,以后成立了国际遗传算法学会,其召开的和会议为遗传算法界权威的国际会议,对遗传算法的不对发展做出了卓越的贡献。其基本思想比较简单,借鉴生物学中遗传变异杂交等繁衍后代的方式,在自然选择的作用下,更适应环境的个体的优秀基因才得以保留,优秀个体则能培育跟符合自然环境约束的个体,在此处的自然选择可以抽象成实际问题中的约束条件,比如全局任务调度中的最优化约束。这个过程可以这样理解遗传算法通过直接对格式良好的对象进行操作,通过概率化的方法,对初始数据算法中算法中称作初始种群演化出的后代,后代也可理解为备选方案,算法保留其中更符合约束条件的方案,舍弃效果不佳的,然后通过杂交变异等手段改变备选方案中的些属性得到新的备选方案,接着再进行自然选择操作,选择其中相对更加符合约束条件的因子继续生成新的后代。每次生成后代,不能得到最优解但都更加的接近最优解,如此代代的繁衍,直到最后得到可以接受的解。遗传算法是基于对现实事物的数学抽象,转化为遗传问题中的相关概念后求解。遗传编码这里的编码相当于生物的序列,在生物体中,代表了生物的各项生命体征特点,其来自于父母的遗传,与父母的类似而不相同,因为在生育下代的时候会发生变异导致遗传不是单纯的复制父体母体的。同样在利用遗传算法解决问题之前,我们首先要对问题进行抽象,在理解问题需求的基础上,给出合理的编码,这里的编码相当于问题的序列,个结果的编码代表了解的特点,同时决定了问题在搜索空间中的基因型转化为解空间表现型的解码方法。所以,遗传编码的选择十分关键,必须具有充分的表达性,能反应问题的特点,编码同样也会影响到变异交叉等算子的计算方法。遗传算法的整个过程就是模拟生物种群繁衍的过程,不过算法模拟的更加细化,直接通过染色体来评判个体是否适应环境,也就是通过新生个体的编码是否更加符合适应度函数来判断个结果是否更加接近理想中的解。若没有则通过选择操作,选择由现有的遗传编码中更优秀通过杂交来生成新的编码,以完成接近理想解的目的。因此,遗传算法不是直接对问题进行求解的种算法,必须先对问题进行抽象,将问题空间的解变量转换为遗传空间,由定结构的组成染色体,这个过程就是遗传编码的过程。适应度函数遗传算法不断向最优解靠近的选择过程是由适应度函数控制的,它负责对染色体进行评价,染色体的适应度函数的值决定了个体的适应程度。按照优胜劣汰的原则,让新生的个体按照适应函数值不断增加的方向发展,由于这个特点,适应函数设计时应当充分反映问题的特点,使得靠近最优解的方向与适应度函数值增加的方向保持致。同时,为了方便比较,适应度函数的值应当为非负数,若有些情况下会得出负值,应当设置定的转化方式是的其能转化为正数。若问题目标函数本身具有适应函数的特点,则可以将待求解的目标函数转化为适应度函数其设计规律可以有作如下的总结最值问题最大值式最小值式指数函数转化指数化目标函数,从而建立其与适应函数的联系式适应度函数的衡量标准也要根据不同的情况而定,特别要注意保持个体的多样性,防止收敛过快等情况的产生。特别是在种群规模不是很大的情况下,有时会出现个别适应函数值特别高的个体,则该个体被选中的概率高于其他个体,经过几次选择之后,种群中剩下的基本都是具有高适应函数值个体的后代了,该现象直接导致种群收敛在局部个点,使其他个体失去了公平竞争的机会。以上现象又称为选择压力,在设计时要特别注意避免收敛过快,尽力照顾到个体的公平性,选择的随机性,是的遗传朝有利于搜索最佳答案的方向发展。基因选择与交叉变异选择交叉变异是定义在遗传编码上的系列运算操作。其中选择是推动遗传过程向答案逼近的最直接的推动力,同时也是者中最为关键的操作,如果选择压力过大,则算法过早收敛,搜索的空间被缩小至个局部范围内,若选择压力太小,则遗传算法很难在相对较少的迭代次数内找到符合条件的解,使得计算过程变得缓慢。通常情况下,初期般设置选择压力较小,保证种群的多样性,使得很多个体都有均等的机会,后期压力变大,提高优秀个体脱颖而出的机会。交叉运算是对遗传编码重新组合的过程,初始种群通过交叉产生新的使得搜索空间变大,其运算过程与编码的选择有关,般有进制编码和浮点编码两种方式。以进制编码为例,交叉操作般是从父代中选取两个染色体,然后再对双亲对应的交叉点处的因子相互交换产生新的个体。而交叉点的选择又可以细分为单点交叉多点交叉均匀交叉。以多点交叉为例,在随机产生个交叉点后,可以没有重复随机的完成选择操作,在交叉点间相互交换产生后代,假设现在有两个作为双亲的染色体双亲双亲若随机产生的交叉点位置为则子个体为后代后代最后是变异操作,变异是染色体自身些发生改变的种方式,如同生物学中的概念样。遗传算法中对于变异算子,同样般有进制编码和浮点数编码两种情形。变异算子的主要贡献是提供初始种群中没有的,或者重新得到在选择过程中已经丢失的,扩大解的搜索空间。整个后代生成的过程如图所示综上所述,算法设计的重点是准确的描述适应函数,即如何描述自然选择的标准,若选择的标准制定不当则会带来诸如收敛于局部收敛过快等问题,其基本形式可以进步定义成如下的函数形式式其中表示个体编码方法表示个体的适应度评价函数表示初试种群大小表示群体大小表示选择算子表示交叉算子表示变异算子表示遗传终止运算条件。其具体运算步可以作如下的概括交叉变异父代后代新种群图遗传算法后代产生过程初始化,设置进化代数计数器,设置最大迭代次数,确定合适的编码方案,将解空间与编码空间对应。随机生成个个体作为初始群体根据问题的需求规则确定适应度函数选择遗传算子,设定运行参数,随机生成个个体作为初始群体根据个体的染色体编码,计算种群中个体的适应度,作为选择的依据选择中适应度较好的个体作为父代产生新的子个体对整个种群的适应度进行评价,若达到要求则结束算法,否则重复第步遗传算法在全局调度中的设计自适应算法概述在全局任务调度员领域,存在个共识,即在目前的通信模型下,如何把图中的任务分配到各个计算节点上处理的任务调度问题属于问题。单纯按照业务需求的特性削减调度规模,无法避免其性,般的思路是采用些高效率的搜索算法对全局调度进行优化,因为最优解对于调度的整个过程来说意义不是那么重要,若寻找解这个过程本身占去太多资源的话是不符合运算效率最大化的思路的,所以对于全局任务调度般偏向于采用高效的近似搜索算法。启发式的调度算法通过限制简化任务模型降低调度设计的复杂度,使得求解过程所花费的时间在个可以接受的范围内,并通过挑选评价的迭代过程向最优解靠近。虽然启发式的方法不能找到最优的解,但是般都能在更小的时间复杂度内找到更加接近最优的方案。遗传编码的设计主要讲述在故障诊断平台的应用背景下,对于全局任务调度首先要考虑的是任务之间的依赖性数据集的依赖性不同计算节点计算能力