（计算机应用技术专业论文）基于精英dna遗传算法的网格资源调度.pdf

摘要网格计算，这一新兴的i t 技术是继w e b 技术和i n t e r n e t 之后又一次重大的技术变革。它使得人们可以比以往任何时候都可以更加经济方便的使用高性能的网格资源，如存储能力，计算速度，等等。然而，由于网格资源种类繁多，相互异构，地理位置分布十分广泛，拥有者( 组织) 不同，管理策略各异且本身状态不断发生动态变化，传统的资源管理和调度策略在新的网格环境中己经难以适用。目前，设计一种新的适合网格环境的资源管理系统及相应的调度技术已经成为一个重要的研究方向。文章首先简述了一下网格计算，遗传算法的理论研究，并分析了用遗传算法解决网格资源调度问题的优缺点和可行性。然后，提出了基于精英d n a 遗传算法的网格资源调度策略。文章定义评价度高的d n a 为精英d n a ，改进后的算法，对精英d n a 加以保护，并且让其发挥更多的作用。该策略通过改进后，引进混合交叉算子，单体遗传算子，和逐次逼近的策略，让调度策略有更好的收敛性，能够较快的找到最优解。最后，文章给出了系统的运行流程，算法的核心思想。用n e t 平台实现了网格资源调度系统，通过实验分析，证明了改进后的算法具有很好的效果。关键词：网格资源调度遗传算法混合交叉择优保存a b s t r a c tt r a d i t i o n a lr e s o u r c es c h e d u l i n ga l g o r i t h m ，i ng r i de n v i r o n m e n t ，e x i s ts o m ed e f e c t s ，f o re x a m p l ei tc a nn o tw e l lm e e tt h eq u a l i t yr e q u i r e m e n t sa n dc a nn o tg e tt h eo p t i m a ls o l u t i o n t h i sa r t i c l eg i v e sa nn e wr e s o u r c es c h e d u l i n gm e t h o db a s e do ni m p r o v e dg e n e t i ca l g o r i t h m i ta c h i e v e s 鲥dr e s o u r c es c h e d u l i n gb yu s i n gr e a ln u m b e re n c o d i n ga n da c t i v i t i e sp o i n tc r o s s o v e r e x p e r i m e n t ss h o wt h a tg e n e t i ca l g o r i t h mc a nr e d u c ee x e c u t i n gt i m ea n dt a s kc o m p l e t i o nt i m e ，a n df u r t h e ri m p r o v et h es c a l a b i l i t yo fr e s o u r c es c h e d u l i n gm o d e l t h i sa l g o r i t h mh a ss t a b i l i t ya n dh i g he f f i c i e n c yi ng r i de n v i r o n m e n t g r i dc o m p u t i n gc o r eo ft h ep r o b l e mi st h a tm o s tg r i dr e s o u r c es c h e d u l i n g ，g d dr e s o u r c es c h e d u l i n go b je c t i v ei st h r o u g ht h er a t i o n a la l l o c a t i o no fr e s o u r c e st od i f f e r e n tt r e a t m e n tu n i t ，l e a v i n gt h ei m p l e m e n t a t i o no ft h eg e n e r a lt a s ko fo p t i m a la c c o r d i n gt ot h eu s e r sr e q u i r e m e n t s ，s or e s o u r c e ss c h e d u l i n gf o rg r i dr e s o u r c eu t i l i z a t i o ni sv e r yi m p o r t a n t g r i dr e s o u r c es c h e d u l i n gp r o b l e mi sa nn pp r o b l e m ，a n dg e n e t i ca l g o r i t h m st os o l v en ph a sb e e ns h o w nt ob ea ne f f e c t i v ea l g o r i t h mf o rt h ep r o b l e m t h i sp a p e rd e s c r i b e st h eb i o l o g i c a l p r i n c i p l e so fg e n e t i ca l g o r i t h m s ，c h a r a c t e r i s t i c s ，a n db a s i co p e r a t i o n ，t h ea d v a n t a g e so fs c h e d u l i n gp r o b l e m sa n dt h e i rs o l u t i o n sa l eg i v e nb a s i co p e r a t i o nm e t h o dc o d e d n aw a sp r o p o s e db a s e do ng e n e t i ca l g o r i t h me l i t eg d dr e s o u r c es c h e d u l i n gs t r a t e g y b yi m p r o v i n gt h ep o l i c y ，t h ei n t r o d u c t i o no fh y b r i dc r o s s o v e ro p e r a t o r ，s i n g l eg e n e t i co p e r a t o ra n ds u c c e s s i v ea p p r o x i m a t i o no ft h es t r a t e g ys ot h a tab e t t e rs c h e d u l i n gs t r a t e g yo fc o n v e r g e n c e ，c a nq u i c k l yf i n dt h eo p t i m a ls o l u t i o n t h ea r t i c l ef i r s tb r i e f l yl o o ka tg d dc o m p u t i n g ，g e n e t i ca l g o r i t h mt h e o r y ，a n di ia n a l y s i so ft h eg e n e t i ca l g o r i t h mt os o l v et h ep r o b l e mo fg r i dr e s o u r c es c h e d u l i n ga d v a n t a g e s ，d i s a d v a n t a g e sa n df e a s i b i l i t y s e c o n d l y ，t h ea r t i c l et ot h eb a s i ci d e ao fg e n e t i ca l g o r i t h mb a s e do nt h ec o m m o ng e n e t i ca l g o r i t h mw a si m p r o v e d g r i dr e s o u r c e ss c h e d u l i n gp r o b l e mf o rt h em o d e la n a l y s i s i m p r o v e dg e n e t i ca l g o r i t h mt os o l v et h ep r o b l e mo fg d dr e s o u r c es c h e d u l i n g a tl a s t ，t h ea r t i c l es h o w st h es y s t e mr u n n i n gp r o c e s s e s ，a l g o r i t h m s ，a n dt h ec o r ei d e a n e tp l a t f o r m 、) ，i t hag d dr e s o u r c es c h e d u l i n gs y s t e m ，t h r o u g he x p e r i m e n t a la n a l y s i sp r o v e dt h a tt h ei m p r o v e da l g o r i t h mh a sag o o de f f e c t k e y w o r d sg r i dr e s o u r c es c h e d u l i n gg e n e t i ca l g o r i t h mm e s sc r o s ss e l e c t i o no ft h eb e s tp r e s e r v e di第一章绪论目录l1 1j ；i 言11 2 国内外研究现状。l1 1 1 网格计算的研究现状。11 1 2 资源调度的研究现状21 1 3 遗传算法的研究现状41 3 本文的研究内容和组织结构。6第二章遗传算法2 1 遗传算法基本概念72 2 遗传算法的主要特点92 3 遗传算法的基本实现方法1 02 3 1 编码与解码1 02 3 2 适应度函数1 12 3 3 遗传操作ll2 4 遗传算法的数学模型1 2第三章网格资源调度。1 53 1 网格计算1 53 1 1 网格概述153 1 2 网格的特点1 53 1 3 网格体系结构l63 2 网格资源调度2 03 2 1 网格资源调度原理2 l3 2 2 网格资源调度的分类2 23 2 3 常用网格资源调度算法2 4第四章基于精英d i o , 的网格调度算法2 64 1 算法的可行性2 64 2 基于遗传算法资源调度的数学模型2 74 2 1 交叉算子2 84 2 2 评价函数2 84 2 3 选择算子2 94 2 4 变异算子3 04 3 基于精英遗传算法解决网格资源调度问题3 14 3 1 实数编码3l4 3 2 混合交叉算子3 24 3 3 单个体遗传3 34 3 4 分层式调度3 34 3 5 并发式调度。3 44 3 6 逐次逼近的选择策略3 5第五章系统仿真。5 1 系统平台介绍3 75 2 算法设计3 75 2 1 核心算法总流程3 75 2 2 先来先服务( f c f s ) 方式3 95 2 3 实时性和批调度4 05 2 4 精英遗传核心算法4 05 2 5 资源调度模型4 35 3 系统功能演示4 65 3 1 资源注册4 75 3 2 资源管理4 85 3 3 资源调度。4 9第六章试验分析实验一实验二实验三实验四结束语致谢。资源固定，任务固定，分析评价值5 2资源固定，任务变化，分析成功率5 3任务固定，资源变化，分析成功率5 4普通遗传算法对比5 4攻读硕士期间研究成果参考文献个人简介5 85 9第一章绪论1 1 引言第一章绪论网格的概念和技术都是很新的内容，在1 9 9 8 年，k e s s e l m a 和f o s t e m 第一次提出。在此之前，大范围的使用分布式资源，被称为元计算( m e t a c o m p u t i n g ) 。虽然如此，无论网格技术是从什么时候开始的，相对于一般的分布式计算来说，网格是非常新颖的内容，构成其基础结构的实际焦点和核心组成部分仍处在研究之中，还没有被确定。总体上来说，网格是由一个仔细配置的基础结构发展而来的，该结构支持有限数量的在美国国家中心之间的高新能硬件应用。对我们今天的目标而言，可以被看作无缝和动态的虚拟环境。网格资源调度是网格技术的核心，而其中的资源分配方法和策略对网格资源管理质量和效率起着重要的作用。如何在网格资源的海量信息中快速发现合适的资源，探索更有效的资源搜索分配机制与技术己经是信息产业，乃至整个计算机产业最关键的研究领域之一。未来网格环境下的资源将比今天的网络环境下更加复杂、更加多样，如果能够探索出更加先进高效的资源分配机制和技术，必将产生巨大经济效益和社会效益。本文以基于生物进化的遗传算法为策略，引入逐次逼近的选择策略和混合交叉算子，为网格资源管理提出一种调度算法，试验证明，有较好的效果。1 2 国内外研究现状1 1 1 网格计算的研究现状目前，网格技术已经从美国和欧洲向世界各个地方推广，各个国家都开始重视网格技术，纷纷开展网格建设，投入大量的人力物力进行网格研究与基础设备的建设。英国累计投资超过一亿英镑，建设国家网格；美国投入大量资金用于网格技术基础研究，至今经费已经超过五亿美元：于此同时，欧盟也不惜重金，建设欧洲数据网格和欧洲网格；亚洲的中国，韩国，日本，马来西亚等国也开始了网格建设和研发工作。目前，美国军方正在实施“全球信息网格”计划，预计于2 0 2 0 年完成。作为这个计划的一部分，美国海军陆战队已经启动了一个将耗资1 6 0 亿美元，这个历经8 年的项目，包括系统的研制、建设、维护和升级等多方面的工作。南京信息工程大学硕士学位论文网格技术为许多行业的具有挑战性的问题提供了一种新的有效方法，这些问题可以在新的计算平台上能够较好的完成和实现。各种科研机构和商业机构已经开始意识到网格的重要性，并在网格技术研究上投入了很多的资源，导致了网格研究不断升温和互相攀比。这种大家齐拥而上的局面，对网格技术的健康发展并无好处。为了将有限的资源投入到庞大的网格系统中去，各类研究机构和商业机构进行有效的协作，是非常必要的。令人欣慰的是，全球的网格论坛、国家网格论坛、地区网格论坛、网格协作组织纷纷出现，这些机构，用来协调成员之间的关系，开发相关标准和协议。全球最大的网格联盟一全球网格论坛已经成为事实上的网格标准制定与发布机构。如今，我国的网格技术研究已列入“8 6 3 计划”。“网格战略研讨会”在北京举行，会议上，网格应用领域的专家和网格研究领域的专家就网格技术方面的问题进行了讨论。很多应用领域对网格都提出了新的需求。专家们就网格的发展、应用、参与国际活动等方面的问题进行了全面的讨论。专家们一致认为，网格的研究、开发和应用将是未来的一个重要方向。目前我国的“8 6 3 计划”已经投入各种资源，用来支持网格研究工作。1 1 2 资源调度的研究现状资源调度系统主要包括两个部分：资源仓库和应用软件。其中资源仓库是组建整体系统的基础，而应用软件是向用户提供访问资源仓库的接口。资源调度策略则是应用软件的核心和关键，它直接关系到网格系统整体性能。目前，网格系统中常用的资源调度算法如下：随机调度法这种调度算法有两种使用方式：第一种，用户给出所需资源详细的属性指标，然后资源调度软件从资源仓库中随机选择资源；第二种，用户给出所需资源的整体要求，根据预先设定的量化算法把整体目标向单个资源的目标转换，再由计算机利用第一种方法从资源库中选择满足条件的资源。显然，第一种方式等同于人工选择资源，对用户来说，使用复杂，难以使用。相对于第一种方式，第二种方式较为方便，它也是资源调度中常用的选择策略，它的核心思想是：量化资源调度目标，然后根据每个资源的约束条件，利用随机选择函数从资源库中选择一个资源放入已选资源；不断重复上述过程，直到找到所有满足条件的资源或没有找到满足要求资源为止，流程图如1 1 所示：2第一章绪论匿嘭净囵0震萼挚璧蒸懑荔。爨化整俸垄景数缓荔自l 赫- 一，。；貂蠡缮l缀晦粤选簪毒唾懑上寥粥”叠法结紊霉缓锄虢虢氲话南? i ? ，毒赫黝徽图1 1 随机选取法该算法的关键是量化整体参数。实际应用中，这种算法的程序比较容易实现，但其缺点是具有很大的不确定性，因此，在网格海量资源的环境下，调度成功率低。针对这些缺点，进行了很多的改进，如使用近似匹配策略，但是仍然不能解决在约束条件较多情况下的调度问题，资源调度往往以失败而告终。回溯试探调度法回溯试探调度法，是一种基于搜索策略的条件广度优先或深度优先算法，是随机选取算法的一种改进型。该算法实质是利用随机选取法产生的每一状态类型，并记录下来，当搜索失败时，释放上次成功调度记录的状态，然后再根据策略变换一种新的状态类型进行试探，通过多次的回溯试探，直至找到符合条件的资源集合。该类型算法是建立在随机抽取算法的基础上，只是在抽取策略中增加了验证过程，通过验证所选择资源是否满足系统给定的目标条件来判断是否选择该资源，当发现目前没有任何资源满足要求而调度过程又没有完成时，则采用回溯方法，重新计算。从理论上来看，这种调度算法可以遍历每一种可能的状态组合。但实际上，当资源量比较大时，可能的组合数将会很大。为解决该问题，回溯法组卷通常在在预先设定的调度模式基础上，和随机数组卷算法一起使用，当生成的资源不能通过验证时，则回溯，通过修改调度模式，重新调度，具体流程图如下：3南京信息工程大学硕士学位论文图1 2 回溯试探法由算法流程图可以看出，回溯调度法在本质上也属于随机算法，但是与其不同的是，回溯法是建立在预定的调度模式的基础上。这样就产生两个个问题：一是调度模型较少或不符合环境的话，需要多次回溯，成功率较低，计算时间较长，具有不确定性；二是因为模式是回溯法的基础，不可避免的会造成负载不均衡。在实际应用中，还发现该算法结构复杂，运行时占用内存大。遗传调度算法这也是目前常用的调度算法。遗传算法是一种高效而通用的的随机化搜索算法，它能从调度的整体目标上进行搜索；通过模拟自然界的交叉和变异不断优化群体中的样本，提高单个样本的适应值，不停的向最优解逼近，算法不依赖外部参数，只以适应度作为遗传操作的迭代条件，从而使算法收敛到全局最优解。本文以遗传算法为基础，对普通的遗传算法加以改进，提出一种基于精英d n a 遗传算法的资源调度方案。1 1 3 遗传算法的研究现状遗传算法，是根据生物进化原理，模拟适者生存，优胜劣汰的规律，演变而来的应用广泛的、通用的一种进化搜索方法。它以生物进化原理及基因理论为依据，通过模拟生物进化规则，进过选择、遗传、变异等算子，实现个体适应度逐渐的提高。使个体逐渐逼近最优值。遗传算法的实质就是把自然界有机体优胜劣汰的适者生存、自然选择的进化规则4第一章绪论与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。遗传算法的研究起源于2 0 世纪6 0 年代初期，最开始的研究，以自然系统的计算机模拟为主，鲜明的特点是缺乏理论指导和没有明确的目标和计算工具。但是，仍然产生很多珍贵的研究成果，尤其以f r a s e r 的模拟研究最出名。1 9 6 2 年他提出了自然遗传算法的一些思想，但是，他还没有意识到，自然遗传算法可以转化为人工遗传算法。直到2 0 世纪7 0 年代中期，h o l l a n d 和d e j o n g 创造性的提出了人工遗传算法的方法和理论。其中，h o l l a n d 在1 9 7 5 年出版的专著自然系统和人工系统的适配首次提到了人工遗传算法思想，并系统地论述了遗传算法的基本方法和理论。该著作还指出对遗传算法的理论研究发展具有深远意义的模式理论，该理论首次确认结构重组遗传操作对于获得隐并行性的重要性。同年，d e j o n g 发表重要论文遗传自适应系统到的行为分析，他把他的实验与h o l l a n d 的模式理论结合起来，将选择、交叉和变异操作进一步完善、使之系统化，并提出了诸如代沟等改进的遗传操作技术。d e j o n g 所作的研究工作被看作是遗传算法发展过程中的一个里程碑。进入8 0 年代，遗传算法迎来了兴盛的发展时期，在理论研究方面和实际应用方面都获得了很多成果，研究内容也开始有了新的动向：一是优化搜索方法的研究，二是学习系统的遗传算法的研究，三是生物进化与遗传算法的研究，四是遗传算法的并行分布处理，五是人工生命和遗传算法的研究。5南京信息工程大学硕士学位论文1 3 本文的研究内容和组织结构本书共分7 章第一章分析了本文的研究背景网格以及网格调度的研究现状遗传算法的国内外研究现状。阐述了本文的主要工作，以及文章组织结构。第二章阐述了遗传算法的基本概念，简述了遗传算法的主要特性，给出了遗传算法的数学模型，和实现方法。第三章简述了网格计算的概念，网格的特点，以及网格的体系结构。介绍了著名的网格中间件g l o b u s 调度。介绍了网格资源调度的原理，分别阐述了集中式调度，分布式调度和分层式调度的优缺点。给出了常用的网格资源调度算法，并比较了各种算法的适应条件。第四章提出一种基于精英d n a 的网格调度算法，分析算法的可行性，给出了改进算法的思想。提出了逐步逼近的遗传算子，混合交叉的交叉策略和一种可以分层式并行计算的方法。第五章给出了系统整体设计，提供了整个资源调度算法的流程图，以及核心代码，并给予了解释工作。演示了系统的运行效果。第六章系统模拟了网格资源环境，并在此环境下进行了调度，通过实验数据，证明了算法的各种性能，和其他算法进行了比较。第七章总结篇，总结了研究的成果，并分析了存在的不足，以及以后的改进方案。6第二章遗传算法第二章遗传算法遗传算法，是美国m i c h i g a n 大学的h o l l a n d 教授于上世纪6 0 年代第一次提出的。1 9 7 5年，h o l l a n d 出版了经典著作 a d a p t a t i o ni nn a t u r ea n da r t i f i c i a ls y s t e m ) ) ，该著作详细的阐述了遗传算法理论，为其发展奠定了理论基础。此后，遗传算法引起了国内外学者的重视。1 9 8 3 年，g o l d b e r g 首次将遗传算法用于实际的工程项目一一煤气管道的优化，打开了遗传算法应用研究的新篇章。自1 9 8 5 年以来，国际上召开了多次关于遗传算法的学术会议和研讨会，国际遗传算法学会组织召开的i c g a ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m s )会议和f o g a ( w o r ks h o po nf o u n d a t i o ng e n e t i ca l g o r i t h m s ) 会议，为研究和应用遗传算法提供了交流的机会和平台。9 0 年代，迎来了遗传算法发展的高潮。目前，遗传算法己被成功地应用于工业、经济管理、交通运输、工业设计等不同领域，解决了许多问题。遗传算法理论研究内容主要有分析遗传算法的编码策略、算法收敛性、遗传算法参数的选择、搜索效率的数学基础、遗传操作策略及其性能研究、遗传算法的结构研究、与其它算法的综合比较研究等。比起理论研究，遗传算法的应用研究更为丰富，己渗透到多种学科。遗传算法的应用按其方式可分为三大部分：基于遗传的优化编程、基于遗传的优化计算、基于遗传的机器学习，分别简称为遗传编程( g e n e t i cp r o g r a m m i n g ) ，遗传计算( g e n e t i cc o m p u t a t i o n ) ，遗传学习( g e n e t i cl e a r n i n g ) 。控制领域是近年来遗传算法应用的活跃领域。m u r d o c k 等用遗传算法分析了控制系统的鲁棒稳定问题。m i c h a l e w i e ，用浮点数编码的遗传算法研究了离散时间最优控制问题。p o t t e r 等运用遗传算法研究了数字p i d 控制器的调节。f r e e m a n 等用遗传算法精调模糊逻辑控制器。p a r k 等研究了一种新的基于遗传的模糊推理系统，用于产生优化参数集，获得了良好的性能。c a r l o s 研究了一种处理多目标、多约束条件问题的遗传算法，展示了多目标遗传算法优化技术在控制系统设计方面的优势。k r i s t i n s s o n 和d u m a t ，通过用遗传算法寻找零极点，研究连续和离散的系统的参数辨识问题。黄炯讨论了遗传算法在线辨识的实现问题，研究结果表明遗传算法能在线辨识时滞系统并收敛到全局最优。由于遗传算法有天然的增强式学习能力，因此在系统辨识、非模型控制系统设计以及模糊控制器设计等方面的研究将会更为深入。2 1 遗传算法基本概念遗传算法是模拟自然环境中生物的遗传和进化过程，形成的一种人工自适应全局概率7南京信息工程大学硕士学位论文搜索算法。它根据达尔文“优胜劣汰、适者生存”的理论和孟德尔遗传变异思想，通过模拟生物遗传，交叉，变异等算子，进而开发出的一种多目标、多个体，同时进化的搜索策略，是建立在自然选择概念和进化过程思想基础上的一种随机优化方法。遗传算法，通过维持一群个体组成的种群p ( t ) ( t 表示遗传代数) 。每一个体都代表问题的一个潜在解。每一个体都用一个评价标准得到其适应环境的程度值。通过种群不断的进化，达到较好的总体评价值。在每一代，遗传算法使用交换和变异等遗传算子，对个体进行重新排列组合，获得一个新的种群，评价度高的个体，其生存及参与下一轮交换操作的可能性也越大。伴随着算法的进行，个体优良的特性就逐渐得以保留，并加以组合，从而能够产生出更佳的个体。通过不断地迭代，种群的个体适应度值，不断地逼近目标值。这一过程类似于达尔文的随机变异和自然选择的进化模型，好的基因被不断地继承下来，坏的基因被逐渐淘汰。新一代个体中包含着上一代个体的大量信息，新一代的个体不断在总体特征上胜过旧的一代，从而使整个群体向前进化发展。对于遗传算法，也就是不断地逼近最优解。遗传算法中参考了生物遗传学上的一些基本术语和概念，但又与传统生物学意义有所不同，具体说明如下：染色体( c h r o m o s o m e ) ，遗传主要的载体，它是遗传基因的集合，在使用遗传算法时需要把每一个染色体看成为问题的一个解。基因( g e n e ) ，问题的解由基因组成，为生物性状遗传物质的结构和功能的基本单位。个体( i n d i v i d u a l ) ，染色体是带有特征的实体称个体，个体代表了问题的一个解，种群就是问题的解的集合。种群( p o p u l a t i o n ) ，染色体带有特征的个体的集合称为之种群，又称群体或集团，该集团的个体数量称为群体的大t b ；适应度( f i t n e s s ) ，个体对其所在环境的适应程度，称为适应度。在遗传算法中，根据制定的评价标准，每个解x 对应于一个适应值。该数值越大，则表明对个体环境的适应度越好，所以可以用个体的适应函数来衡量它对环境的适应度。选择( s e l e c t i o n ) ，以评价值为参考，用一定的概率，从群体中选择若干个体的操作称为选择，也称作复制或再生( r e d u c t i o n ) 。交叉( c r o s s o v e r ) ，两个染色体互相交换彼此成分，组成新的个体的操作称为交叉又称为重组或交换。生物体的繁衍就是通过染色体的交叉完成的。变异( m u t a t i o n ) ，遗传因子按一定的概率改变自身性状称的操作，称之为变异。编码( e n c o d i n g ) ，从表现型到遗传子型的映射称为编码。解码( d e c o d i n g ) ，从遗传子型到表现型的映射称为解码又称译码，在上述概念中选8第二章遗传算法择、交叉及突然变异对于实现遗传算法是十分重要的。2 2 遗传算法的主要特点( 1 ) 对参数的编码进行操作，而非对参数本身。遗传算法，将参数看成d n a ，通过将参数编码。然后打散他们，重新组合，生成新的解。通常的编码方式有二进制编码和实数编码。通常的算法与之有本质的不同，通常的算法将参数看成一个固定的值，参与到运算。( 2 ) 是从许多点开始并行计算，而非局限于一点。遗传算法开始，需要随机生成一些解，然后评价函数计算出这些解得满足程度，通过这些解的重新排列组合，形成新的更符合条件的解。这些解是共同的运算，他们的地位是同等的重要。( 3 ) 通过目标函数来计算适配值，而不需要其他推导，从而对问题的依赖性较小。目标函数又叫评价函数，他是遗传算法里最重要的算子，它评价了一个基因优劣程度，决定了基因能不能参与下一代的遗传和变异，一个评价函数的好坏，直接关系到遗传算法的优劣程度。( 4 ) 搜索规则是由概率决定的，而非确定性。评价值较高的解，会以较高的概率参与下一代的遗传和变异，将优秀的基因保存到一下代。相反，评价度低的解，则很有可能遭受淘汰。这里只是以概率而论的，当然也有可能，评价度较高的基因，他也会遭受淘汰。这样充分模拟了自然界中的生物遗传。保证了物种的多样性，防止算法的局部收敛。( 5 ) 在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索。( 6 ) 对于待优化的函数无任何限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，甚至可以是神经网络的隐函数，是一种通用的算法。( 7 ) 具有并行计算的特点，可通过大规模并行计算来提高计算性能。遗传算法不是对针对问题，按过程求解，他是对问题的解排列组合的一种特殊算法。遗传算法要对大量的解，进行迭代优化，而这个过程是可以同时进行的，并且计算过程之间的耦合性较小。( 8 ) 适合解决复杂问题。不论什么问题都可以用遗传算法解决，它是一个通用性的算法，遗传算法通过模拟生物学的遗传议论，优胜劣汰，透通过不停的迭代，筛选出最优解。它的这种特性，决定了9南京信息工程大学硕士学位论文遗传算法，尤其适合大规模运算，遗传算法在解决n p 难问题上，更能体现出其优越性。( 9 ) 计算简单，功能强。遗传算法是一个通用性的算法，从理论上讲，它可以解决任何问题。只需要给出合适的评价函数，然后通过迭代算法，就可以不停的逼近最优解。2 3 遗传算法的基本实现方法2 3 1 编码与解码编码是设计遗传算法的一个关键步骤，也是遗传算法应用时要解决的首要问题。编码方法除了决定个体的染色体排列形式之外，它还决定了体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法影响到遗传算子，交叉算子、变异算子等运算方法。编码方法有二进制码、实数编码等。l 、二进制串编码。二进制编码具有以下优点：( 1 ) 二进制编码类似于生物染色体的组成，算法很容易实现，并易于用生物遗传思想来解释。( 2 ) 采用二进制编码时，计算机对二进制数处理的模式最多，也更容易收敛。( 3 ) 采用二进制算法，实现遗传算法，必须实现遗传和变异等算子。二进制是计算机最容易处理的编码方式，二进制编码使算法非常容易实现。( 4 ) 众所周知，计算机是采用二进制编码的，对操作二进制数据，计算机有更为强大的能力，也提供很多可用的函数。尽管如此，在求解连续优化问题时，二进制编码又存在以下缺点：( 1 ) 相邻整数的二进制编码可能具有较大的海明( n a m m i n g ) 距离。例如1 6 和1 5 的二进制表示为1 0 0 0 和0 0 1 1 1 1 ，如果算法要从1 5 改进到1 6 ，则必须改变所有的位。这将降低遗传算子的搜索效率。二进制编码的这一缺陷，常被我们称之为海明悬崖( h a m m i n gc l i f f s ) 。( 2 ) - - 进制编码，一般要先确定计算精度。然后给出求解的精度以确定串长，一旦指定了精度，就很难在算法执行过程中再进行调整。从而使算法缺乏微调的功能。如果算法开始就选取较高的精度，那么串长就很大，这样也将降低算法的效率。( 3 ) 求解多重约束性问题时，二进制编码串可能非常长，并且具有可变长度，难以把握，制定统一的计算方法，给程序带来了一定的难度，同时也使算法的搜索效率降低。2 、实数编码在问题的变量是实向量的情况下，可以直接采用实编码方式，这样解决了二进制编码1 0第二章遗传算法在实向量环境下的不足。实数编码，既是采用十进制编码。实数编码通常在解决高维约束性问题或者复杂优化问题时具有较好的效果。试验表明，大部分的数值优化问题，通过引入一些专门设计的遗传算子，实数编码要比二进制编码算法的具有更高效率。由于实数编码是最贴近现实，也容易引入相关领域的知识，再加入启发式信息，增加其搜索能力，所以它被越来越广泛的接受。当然，除了上述两种编码方式，还有其它的编码方式：比如符号编码，我们不再一一详述。解码是编码的逆运算，就是根据所选择的编码方式把寻找到的最优串转化成实际物理量。2 3 2 适应度函数在遗传算法中，适应度高的个体将以较大概率遗传到下一代的，而适应度较低的个体遗传到下一代的概率就相对小一些。个体适应度的大小决定着该个体被遗传到下一代群体中的概率，度量个体适应度的标准称为评价函数。通过评价函数来计算每个染色体的优劣程度，他体现了自然进化中的“优胜劣汰”规则。对于优化问题，适应度函数就是目标函数。对于网格资源调度而言，满足调度任务的程度，就是适应度函数。以最小的代价满足任务的需求的调度方案，他的适应度最高。评价函数能够有效地计算出每个染色体与问题最优解染色体之间的差距。若一个染色体与问题的最优染色体之间的差距较小，则该个体的评价值就高，否则就较低。适应度函数的取值大小与求解问题对象有很大关系。2 3 3 遗传操作一般来说。遗传算法主要模拟三种遗传算子：选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 。选择操作也称之为复$ 1 ( r e p r o d u c t i o n ) 操作，最简单而又最常用的选择方法有，轮盘赌选择法( r o u l e t t ew h e e ls e l e c t i o n ) 。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为1 1 ，其中个体i 的适应度为m ，则i 被选择的概率1 m ，为选择算法。显然，概率反映了个体i 的适应度在整个群体的个体适应度总和中所占的比例个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个【o ，1 】之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。交叉操作的简单方式是将被选择的两个个体，经过重新组合后，形成新的两个个体的南京信息工程大学硕士学位论文1 ) 单点交叉( s i n g l e - p o i n tc r o s s o v e r ) ；2 ) 多点交叉( m u l t i p l e - p o i n tc r o s s o v e r ) ；5 ) 缩小代理交叉( c r o s s o v e rw i t hr e d u c e ds u r r o g a t e ) 。变异( m u t a t i o n ) 操作时模拟生物进化中染色体上某位发生突变的现象，从而改变染色体的结构和物理性状。在遗传算法中，变异算子通过按变异概率p 随机反转某位的二进制字符值来实现。对于给定的染色体位串s = 以1 a t ，具体如下：m m 七一誊卸越，变异在做作用于个体位串的等位基因上，由于变异概率比较小，再实施过程中一些个体可能根本不发生一次变异，造成大量的资源浪费。因此，在实际的g a 过程中，往往采用变通的操作，先计算个体变异发生的概率，然后再实现基因层次上的变异，一般包括以计算个体发生变异的概率。计算发生变异的个体上基因突变的概率。2 4 遗传算法的数学模型s g a 首先生成一定规模的初始种群，接着个体以一定的概率进行交叉、变异，实现个体结构重组。再按预设的评价函数选择复制优秀个体组成新一代种群，循环该过程，直到找到满足条件的最优解。其算法如下：1 2第二章遗传算法( 1 ) 群体编码；( 2 ) 初始化群体；( 3 ) 计算群体中个体适应度；( 4 ) 进行选择、交叉和变异操作；( 5 ) 计算新个体的适应度值；( 6 ) 判断是否满足退出循环的条件，若找到满足条件的解或达到最大循环次数则结束循环；否则转向( 4 ) 继续循环。按以上流程分析，基本遗传算法可定义为一个8 元组：s g a = ( c ，e ，p 0 ，m ，r ，w ) 。其中c 为个体的编码方法；e 为个体适应度评价函数；p 0 为初始群体；m 为群体大小：为选择算子；r 为交叉算子；v 为变异算子。定义1 ：个体的评价函数e xi = e ( x f )定义2 ：个体的选择概率定义3 ：个体累计概率fp a xf = a ，1 = l式2 2式2 3式2 4对每对染色体产生一个【o ，1 】的随机数r ，若尸f - 1 r p a x ，x 7 得以遗传到下一代。交叉策略( 0 0 0 0 0 0 1 1 1 1 1 1 )交叉( 0 0 0 0 0 0 1 0 1 0 1 0 )图2 1 交叉策略将一个个体，看作一个二进制的字符串，然后在该字符串的中间位置，从中断开，断开后的小个体，两两结合，形成新的个体。交叉算子，输入两个个体，输出两个个体，他1 3南京信息工程大学硕士学位论文是两个个体重新排列组合的运算。变异策略匝( 1 0 1 0 1 01010)i 一l ( 1 0 1 0 1 00口010)图2 2 变异策略将一个个体，看作一个二进制的字符串，然后在该字符串的某个位置，由0 变成1 ，或者由1 变成0 ，变异算子输入单个个体，输出也是单个个体，变异策略是改变字符串局部位置值的运算。1 4第三章网格资源调度3 1 网格计算第三章网格资源调度3 1 1 网格概述网格计算即分布式计算，是一门计算机科学。它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终结果。最近的分布式计算项目已经被用于使用世界各地成千上万志愿者的计算机的闲置计算能力，通过因特网，您可以分析来自外太空的电讯号，寻找隐蔽的黑洞，并探索可能存在的外星智慧生命；您可以寻找超过1 0 0 0 万位数字的梅森质数；您也可以寻找并发现对抗艾滋病毒更为有效的药物。用以完成需要惊人的计算量的庞大项目。网格把用通信手段连接起来的资源无缝集成为一个整体，他给用户提供了一种基于国际互联网的新型计算平台，在这个平台上对客户的请求和提供资源的能力之间进行合理的匹配，为用户选择合适的资源，为之服务，可实现广域范围内的资源共享。网格把分布的资源集中起来，使之成为一个性能强大的超级计算机，提供计算资源，存储资源，数据资源，信息资源，知识资源，专家资源，设备资源的全面共享。资源共享是网格的根本特征，消除资源孤岛是网格的奋斗目标。3 1 2 网格的特点作为一种新出现的重要的基础设施，网格与其他系统相比，有很多特点，主要包括以下几个方面：虚拟性：网格中的资源和用户都要经过抽象，把实际的用户和资源虚拟化为网格用户和网格资源。网格用户使用标准、开放、通用的协议和界面，可以访问网格中的各种资源，但实际的用户和物理资源是相互不可见的，资源对外提供的只是一个虚拟化的接口。共享性：网格中的各种资源都能够被共享使用，网格是一个提供资源共享的场所。网格中的多个用户不仅能够共同使用网格中的一个资源，网格中的一个用户也可以同时使用多个网格资源。这里的共享的含义是非常广泛的，不仅指一个地方的计算机可以用来完成其它地方的任务，还可以指中间结果，数据库，专业模型库，以及人才资源等各方面的内容。1 5南京信息工程大学硕士学位论文集成性：网格把地理位置上分布的各种资源集成在一起，成为一个有机的整体，协调分散在不同的地理位置的资源使用者。用户不仅可以使用单个资源提供功能，而且能够联合使用多个资源的合成功能。网格可以集成来自不同管理域，不同管理平台面，具有不同能力的资源。协商性：网络支持资源的协商使用，资源请求者和资源提供者可以通过协商得到不同质量的服务，满足不同的实际需求。通过协商，请求者和提供者之间还可以建立专用的服务接口，提供突出个性的服务。请求者可以指定系统响应时间、数据带宽、资源可用性、安全性等各种要求、得到非平凡的服务质量。使得整体系统能提供的功能大于其各个组成部分的功能之和。自治性与管理的多重性：网格上的资源首先是属于某一个组织或者个人的，因此网格资源的拥有者对该资源具有最高级别的管理权限和自主的管理能力，这就是网格的自治性。管理的多重性是指资源不仅可以被拥有者自管理，也必须接受网格的统一管理，网格刁能实现共享和互操作，使网格资源作为一个整体为更多的用户提供方便的服务。3 1 3 网格体系结构网格的体系结构有很多种，目前比较重要的有两个，一个是i f o s t e r 提出的以协议为中心的五层沙漏结构，另一个是i b m 公司与g l o b u s 于2 0 0 2 年共同推出了以服务为中心开放网格服务结构o g s a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 。五层沙漏结构沙漏的含义是因为各层次协议的数量和作用都是不同的。而其核心的协议，是要能够实现上层各种协议向核心协议的映射，同时实现核心协议向下层其它各种协议的映射，核心协议是通用协议，它在所有支持网格计算的地点都应该得到支持，所以，核心协议的数量不能太多，这样，核心协议形成了协议层结构中的一个瓶颈1 6第三章网格资源调度工具与应用应用屡篡汇聚屡鬻耆的| | 瓷源层与连接层溅辫弋构造层图3 1 五层沙漏结构网格的各个协议层形成一个“沙漏”结构，底层是构造层f f a b r i c ) ，包含了网格用户想要分享和获得的网格的各种资源，包括计算资源、存储资源、数据资源、以及各种设备。网格体系拚潋l感掰堪ii秘：疑堪iii1r赣游毖lii1ri连接堪lii曰网络孙泌体系结构图3 2 网格体系结构构造层上面包括连接层( c o n n e c t i v i t y ) 和资源层( r e s o u r c e )