第15组网格计算课程

NP遗传算法由于具有良好的全局搜索能力，在处理任务调度算法时比传统调度算法更具优越（，取最优空间。绪随着的不断发展,信息量的不断增加,遇到的各种计算问题越来越复杂,计算规大的超级计算机的价格也其进入普通的应用领域。因此,迫切地需要寻找一种计算能力Internet或其它高速网络将遍布世界各个角落、能力千差万别的计算资源连接在一起,形成 第二章网格系统与任务调网格系Grid[]己经成为一种利用互网或将地理上泛分布的态的和异构的源互联起来实现资源生于20世纪90年代期的它借于电力网PwerGrid)概念,的目的期望能网格体系一起的方式和方法,另外,网格体系结构还清晰的描述网格系统由哪些组成部分结合在一起沙漏结构(Five-levelsandglassArchitecture),第二个是以IBM为代表的工业界影响下,考虑到Web技术的发展与影响后,Foster等结合WebService和五层沙漏结构开放网和HP共同web服务资源框架(webserviceResourceFramework,WSRF)。下面重点OGSA。点就是简单,它侧重于对网格的定性的描述而不是对具体协议进行定义,易于从整体上进行API和SDK1示。1层都定义了协议,以提供对相关服务的,这些服务包括资源管理、数据存取和资源发现包括和诊断服务、服务、协同分配和调度等,它们说明不同资源集合之间是如何相的。资源层协议考虑的完全是单个的局部资源,因此忽略了全局状态和分布资源集合的连接层:基本功能是实现安全便利地通信。它定义了通信和认证协议,这种协议是基于传统的TCP/IP协议和标准的安全协议,这些协议是针对于网格的网络处理定义供资源的接口,同时提供查询机制(发现资源的结构和状态等信息)、控务质量的资五层沙漏结构之所以形成如沙漏,是由各部分协议的数量分布不均匀引起的,考虑到核心的移植、升的方便性,部分的议数量相比较少,对于其部分既要能够实现上层各协议向协议映射,又现协向下层其各种协的映射按定义,协议的数量不能太多,这样协议就形成了协议层次结构中的一个瓶颈,资源层和连OGSA是GlobalGridForum的重要标准建议,是目前也是最有的一种网格体22OGSAOGSA,OGSA各种资源、计算资源、程序、数据库和网络等等,这里的服务是指具有特定功能的网络webservice,该服务提供了一组接口,这些接口的定义明确并且遵守特定的惯例,解决OGSA的目的就是要将网格的一些功能,更确切地说是Globus的一些功能融合到WebService网格的特其它专有网格上的现有软硬件资源,支持广域环境上计算、、数据、知识资源和信息的成计算、等的功能,其中资源共享是一种集中资源的;源的拥有者对该资源具有别的管理权限,网格应该允许资源拥有者对它的资源有自主网格任务调效的网格任务执行环境,将网格任务调度到异构的网格处理机资源上执行,获得最优或接近般来说性能和效率是评价调度系统的两个基本特征,随着网格系统的应用越来越普及,执行任务调度系统是网格系统的重要组成部分,它主要是根据不同的任务信息,采用适当的资源的不同需求和网格系统本身存在的异构性和动态性,使得任务调度变得极其复杂,任务PC3不断增加的情况下,网格系统的任务调度必须具有可扩展性,以不会导致降低网格系统的性能。4性,所以任务调度必须适应网格的动态性,从可利用的资源中选取最佳资源为用户提供应用服务。OLB:opportunistic。LoadBalancing,它随机选择任务到下一个可用的资源上;4)Max-min:Min-inMin-mi:在该算法中,每个任务在各个资源上的完成时间都事先给出,在所有任务中选择完成时间最小的任务分配给相应的资源,然后将新分配的任务移除,直到所有任务都分GA:遗传算法用来搜索大容量的解空间,它对一个给定问题的群进行操作;7)Greedy:Min-minMax-min根据以往的实验数据表明[7],OLB、UDA、Max-min、SA和Tabu算法在通常情况下调度的性能不是很好。Min-min、GA也在10%以内。GA的性能比Min-min要稍好几个百分点。在这三个算法中,Min-min的搜索速度最快,GA第三章、基本遗传算基本遗传算法的描3t→0TN步骤二：计算适应度，以适应度评价。步骤三：通过适应度进行选择。步骤五：变异操作3以上是目标函数到适应度的基本转换方法，但以上变换方法对某些问题收敛过快，3①随机采样；②确定采样；③混合采样；随机采样随机采样中最有名的就是Holland赌采样，赌选择的基本思想就是个其中，𝑓𝑘为𝑘的适应度，𝑝𝑜𝑝_𝑠𝑖𝑧𝑒为群体规模。𝑝𝑘越大，被选为下一代的概遗传算法通过交叉操作使信息在中间得以传递交叉操作的好坏直接影响了遗传算①单点交叉；②均匀交叉；③算数交叉；单点交叉𝑎𝑎1𝑎2𝑎𝑛]𝑏=[𝑏1𝑏2𝑏𝑛]𝑖位发生交叉，则生成后①基本位变异；②均匀变异；③变异基本位变异该变异是以一定的概率𝑝𝑚随机的指定中的某一位或是某几位上的进行变0110.如下所示：A:10101101（黑斜体的0为变异点，变异后的A1:10111101.𝑝𝑚的大小在一定程度上决定了群体局部搜索能力和收敛性能，局部搜索能力和收遗传参数设遗传算法的参数主要有编码长度𝑙,群体规模𝑀,交叉率𝑝𝑐和变异率𝑝𝑚,终止𝑇等。遗传算法参数的选取对遗传算法性能影响很大，所以选择合适的运行参数是𝑙群体规模表示群体中所含的数量：当群体规模选取较大时有利于增加群体多样20~100。0.4~0.99。另外比较好的方法就是利用自适应的方法选取交叉率，第三章将𝑝𝑚：变异操作是为了使遗传算法跳出局部搜索，扩大搜索范围，较大的变是0.0001~0.1。第四章基于遗传算法的网格资源调1]P好地实现任务的合理分配及资源的有效利用,从而保证网格中各部件的协同工作,为用户提本文问题描𝑖𝑗𝐶𝑖𝑗=4+sin(𝑖−𝑗)+2cos(𝑖+𝑗3cos(1𝑗)。现进行网格资源调度，要求消耗的总成本尽解决方（100029=512，210=1024，所以需要10位二进制编码。将1000个网格资源分配给500个任务，假设产生𝑀个染（

1 2 3 MA分层-共享函数遗𝐹′=𝑎𝐹+𝐹′变换后的最大适应度𝐹′𝑚𝑎𝑥等于变换前平均适应度的整数倍,即𝐹′𝑚𝑎𝑥=𝑐∙𝑐1.2-2.0𝑎和𝑏数法[8]。共享函数是度量两个之间相似度的法，可记为𝑆(𝑑(𝑋,𝑌)),其中𝑑(𝑋,𝑌)表示𝑋与𝑌之间的某种关系（例如距离。当两个相似度越大时，共享函数越δ是预先指定的小生境半径。共享度是与群体中其他共享程度的一种度量，一般为与其他之间的共享函数值之和，用𝑆𝑋表示：𝑆𝑋=∑𝑝𝑜𝑝_𝑠𝑖𝑧𝑒𝑆(𝑑(𝑋, 𝑭=𝒇/其中𝑓是目标函数，适应度大的将被保留下来作为下一代种群B.本文目标函第𝑘个完成所有任务所消耗总成本为（父代第𝑘个的完成所有任务的处理能力（母代分别将父代母代作为两个初始种群，计算各个的适应度值𝐹′和母代（（（𝑁×𝑛(𝑁≥2𝑛≥2)个样本，然后把这群样本分为𝑁个子种群，即每个子种群中包含𝑛个，然后在每个子种群中单独运行各自的遗传算法，记录为𝐺𝐴𝑖(𝑖=1,2𝑛)。为了增加多样性，在每个子种群的遗传算法中可以设置不中，其中𝐴[𝑖]𝑖层的平均适应度。𝑘(1≤𝑖𝑗≤𝑁1≤𝑘≤𝑛1)处交叉，𝑅[𝑖,𝑎1,𝑎2𝑎𝑘𝑏𝑘+1𝑏𝑛]和𝑅[𝑗,𝑏1,𝑏2𝑏𝑘𝑎𝑘+1𝑎𝑛]。其中𝑎𝑘和𝑏𝑘分别表示子种群中的以变异率𝑝𝑚随机生成新的子群体替换掉种群中随机选中的4叉变异，产生新作为下一代新种群部分。本文中我们选择用赌法来选择新种群适应度大的被保留下来作为下一代种群部分，适应度小的进行交叉变异（选出较优组成下一代种群部分）第𝑘个被选入新一代种群的概率为′𝑝(𝑋) ∑ ∑

选用赌方式选择适应度值高的直接生成下一代种群的部分,其过程可用以在［0,1］内产生一个均匀分布的随机数𝑟若𝑟≤𝑞1,则𝑋1被选中若𝑞𝑘−1<𝑟≤𝑞𝑘(2≤k≤M),则𝑋𝑘被选中。其中的𝑞𝑖称为𝑋𝑖(𝑖=1,2,…𝐿)的积累概率,其计算为:𝑞𝑖=

针对本文所解决方案，并没有一开始就将两个目标合成单目标进行遗传算法，优（。当最优的适应度和群体适应度不再上升时，终止算法。选取种群中最优所表示的调度方案，进行资源的调度。算法流13.1.12产生初始任务调度种群:根据两个目标函数各自随机生成一个初始任务调度群𝑷𝟐4获得最终目标（两个目标合成单个目标）𝑓𝑘′(𝑖𝑗)=𝑓𝑘(𝑗)⁄𝑓𝑘(𝑖

断遗传和计算适应度大小（采用4.2.2和4.2.4提到的方法，获得最优解。群中最优所表示的调度方案，进行资源的调度。5布式系统己取得了很多成就,但目前的资源调度技术在网格环境中仍存在很多问题,主要是们会，在以后的科研工作中开辟新思路！参考文 Search，Optimization Learning[R].Reading，MA:AddisonWesley.1989.HollandJH.AdpationinNaturalandArtifieialsystems[M].CmabridgeMA:MIT，，等.基于序值编码的最优保存