（计算机软件与理论专业论文）基于遗传算法的网格任务调度研究(1).pdf

摘要 网格作为计算机领域的研究热点之一，近年来受到了广泛的关注。网格中的任 务调度，对发挥系统的并行性能和保持负载平衡具有举足轻重的作用。如何快速而 有效地实现多机系统内的全局任务调度，无论在理论研究还是实际应用中都有十分 重大的意义。已有文献证明，由于网格的复杂多变和任务的层出不穷，网格中的任 务调度属于n p 完全问题，很难用传统的搜索办法在多项式时间内找到最优解。由 此人们想到利用现代启发式算法来解决网格中的任务调度问题。 遗传算法是近年兴起的一种用于解决优化问题的启发式算法，被广泛用于解决 各类n p 问题和任务调度问题，并有仿真实验证明，在处理调度问题时，遗传算法 与传统调度算法相比具有较大的优越性。但是经典遗传算法本身也存在一定的缺陷， 实时性较差，存在运行随机性和不稳定性，因而吸引了大批学者致力于改进遗传算 法的探索和研究中。 在本文中，首先对经典遗传算法，广义遗传算法和并行广义遗传算法进行了数 学分析，得到：广义遗传算法比经典遗传算法有更好的收敛性和全局寻优能力；并 行广义遗传算法比广义遗传算法有更高的运行效率，更适合在有多处理机的网格系 统中处理分布式任务的调度问题。我们提出的任务调度算法以并行广义遗传算法为 基础，根据参考文献 4 的研究，本算法采用统一二进制编码。考虑到生物界不变的 规律：父代强壮，子嗣必然强壮，我们对广义遗传算法又做了进一步的扩展：利用 问题的领域知识，把握最优解在问题空间中的分布，再在这个分布范围内随机设定 初始群体，也可以利用其它的寻优算法，生成一些近优解，组成初始群体。丽从算 法本身而言，则可以通过过量生成初始个体，从中挑选优势个体的方式构成初始群 体。通过这样方式生成的初始种群，必然会在今后的进化过程中占据优势，能够更 快的收敛到全局最优解，提高任务调度器的实时性。本文在第五章中对此也进行了 实验对比，对比结果表明优秀的初始种群的收敛速率更快，算法的全局寻优能力更 强。 同时我们利用m a t l a b 的d i s t r i b u t e dc o m p u t i n g l - 具箱对并行广义遗传算法进行了 仿真。虽然由于试验环境所限，试验结果与数学推导公式略有偏颇，但仍旧可以证 明并行广义遗传算法比广义遗传算法有更高的运行效率和实际应用价值。 硕士研究生车晓雪( 计算机软件与理论) 指导教师许日滨教授 关键词：遗传算法；广义遗传算法；并行广义遗传算法；网格；任务调 度 a b s 。i r a c 1 1 r e c e n t l y ，g r i dh a sb e e nw i d e l yp a y i n ga t t e n t i o n , w h i c h i sc o n s i d e r e da sah o tt o p i ci nt h e r e s e a r c ho fc o m p u t e rs c i e n c e t h ej o bs c h e d u l i n gs y s t e mp l a y sa l li m p o r t a n tr o l ei n o p t i m i z i n gg n dp a r a l l e lp e r f o r m a n c ea n dm a i n t a i n i n gi t sl o a db a l a n c e t h e r ei sag r e a t s i g n i f i c a n c ei ns c h e d u l i n gt a s k sg r o s sd i f f e r e n tp r o c e s s o r se f f e c t i v e l ya n de f f i c i e n t l y w i t h i nt h ew h o l e 酾ds y s t e m ，b o t hf o rt h e o r e t i c a lr e s e a r c ha n dp r a c t i c a la p p l i c a t i o n i t h a sb e e np r o v e dt h a tt h eg r i dj o bs c h e d u l i n gi san p - c o m p l e t ep r o b l e m , a n di ti sh a r dt o f i n da no p t i m a ls o l u t i o ni np o l y n o m i a lt i m eb yu s i n gt r a d i t i o n a ls e a r c h i n gm e t h o d s o t h em o d e r nh e u r i s t i e sa l g o r i t h mi si n v o l v e d g e n e t i ca l g o r i t h mi san e wk i n do fm o d e r nh e t w i s t i e sa l g o r i t h m , w h i e hi so f t e nu s e dt o s o l v ed i f f e r e n tk i n d so fn p c o m p l e t ep r o b l e m sa n dc o m p l e xj o bs c h e d u l i n gp r o b l e m s s o m es i m u l a t i o ne x p e r i m e n t sh a v ec o n f i r m e dt h a tg e n e t i ca l g o r i t h mi sb e t t e rt h a n c l a s s i c a ls c h e d u l i n ga l g o r i t h m s b u tt h ec l a s s i cg e n e t i ca l g o r i t h ma l s oh a ss o m ed e f e c t s ， s u c ha sp o o rr e a lt i m ep e r f o r m a n c ea n di n s t a b i l i t y s om a n ya c a d e m i c i a n sc o m m i t t e d t h e m s e l v e st os t u d yg e n e t i ca l g o r i t h m s i nt h i sp a p e r , f i r s t l ym a r k o vm o d e li su s e dt oa n a l y s i sc l a s s i cg e n e t i ca l g o r i t h m ，e x t e n d e d g e n e t i ca l g o r i t h ma n dp a r a l l e l e x t e n d e dg e n e d ca l g o r i t h m t h ee x t e n d e dg e n e t i c a l g o r i t h mi sp r o v e dt h a ti ti sb e t t e rt h a nc l a s s i cg e n e t i ca l g o r i t h ma tp e r f o r m a n c e ；t h e p a r a l l e le x t e n d e dg e n e t i ca l g o r i t h mh a sh i g h e re f f i c i e n c yt h a ne x t e n d e dg e n e t i ca l g o r i t h m a n di ti sm o r ep r o f i t a b l et ob ea p p l i e di n 班dj o bs c h e d u l i n g t h e nt h i sa l g o r i t h mt h a t m e n t i o n e di nt h i sp a p e ri su s e dt os o l v eg r i dt a s ks c h e d u l i n gp r o b l e m t h i sa l g o r i t h mi s b a s e do ne x t e n d e dg e n e t i ca l g o r i t h m , u s i n gb i n a r yc o d i n ga c c o r d i n gt ob i b l i o g r a p h y1 4 t h e r ei sar u l ei nb i o l o g y , w h i c hi si ft h ep a r e n t sa r es t r o n g ，t h e nt h e i ro f f s p r i n gm u s tb e s t r o n ge i t h e r s of i r s ts o m eo p t i m a li n d i v i d u a l sa r eg e n e r a t e db ya n a l y s i n gc u r r e b tg r i d s c h e d u l i n gi n f o r m a t i o n , o ru s es o m eo t h e rc l a s s i cs e a r c ha l g o r i t h m s t of i n dm a n yo p t i m a l i n d i v i d u a l s ，a n dt h e nt h o s eo p t i m a li n d i v i d u a l sa g eg r o u p e dt oi n i t i a lp o p u l a t i o n g e n e t i c a l g o r i t h mw i t hs u c hi n i t i a l i z a t i o np o p u l a t i o nm u s th a v eb e t t e rp e r f o r m a n c et h a nn o r m a l g e n e t i ca l g o r i t h m h lt h ef i f t hc h a p t e r , a ne m u l a t o ri sb u i l t ；t h ee x p e r i m e n tr e s u l ts h o w e d t h a tt h ep o p u l a t i o nw i t hg o o di n d i v i d u a l sw i l lg e tt h ec o n v e r g e n c ef a s t e r f u r t h e r m o r em a f l a bd i s t r i b u t e dc o m p u t i n gt o o l b o xi su s e dt or u nap a r a l l e le x t e n d e d g e n e t i ca l g o r i t h m a l t h o u g ht h ee x p e r i m e n tr e s u l th a ss o m e t h i n gd i f f e r e n t f r o mo u r m a t h e m a t i c a la n a l y s i n gr e s u l t ，i ta l s oc a np r o v et h a tt h ep a r a l l e le x t e n d e dg e n e t i c a l g o r i t h mi sm o r ev a l u a b l ea n de f f i c i e n tt h a nc l a s s i cg e n e t i ca l g o r i t k m ，e x t e n d e dg e n e t i c a l g o r i t h m p o s t g r a d u a t es t u d e n t ：c h ex i a o x u e ( c o m p u t e r s o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f x uy u e b i n k e yw a r d s ：g e n e t i ca l g o r i t h m ，e x t e n d e dg e n e t i ca l g o r i t h m ，p a r a l l e le x t e n d e d g e n e t i ca l g o r i t h m ，g r i d ，j o bs c h e d u l i n g 学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已 属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：车磁座 日期：2 0 0 7 年0 5 1 7 日 5 2 青岛大学硕士学位论文 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后 发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为青岛 大学。 本学位论文属于： 保密口，在 年解密后适用于本声明。 不保密n o ( 请在以上方框内打“4 ”) 论文作者签名：孽影眵 日期： 2 0 0 t5 月1 7 日 导师签名： 落k7 之 日期孤侮角偌 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 5 3 青岛大学硕士学位论文 第一章绪论 自从e n i a c 诞生以来的半个多世纪中，计算机系统取得了惊人的发展。这是计算 技术和应用技术之间相互作用的结果：一方面，计算技术的提高，为应用技术提供了 一个十分坚实的舞台，使之在众多学科领域中得到了迅速发展：另一方面，不断扩大 和深入的应用技术又对计算技术提出了更高的要求，激励着人们对计算技术的潜力进 行更深入地开发和利用州。特别是进入九十年代以来，一些大型软件的运行，对计算 技术提出越来越高的要求，研制高处理速度和大存储容量的计算机系统刻不容缓。然 而，仅仅依靠提高集成电路密度是很难满足要求的。这是因为芯片的散热、延时、甚 至量子效应等工程因素的限制，以及光速这个不可逾越的障碍，使得通过提高时钟主 频来提高系统处理能力的方式，效果越来越低，并行性的开发和利用己逐渐成为优化 系统性能的主要手段。多处理机任务调度问题作为并行计算中的关键问题，自然也得 到人们越来越多的重视闭。 1 1 多处理机任务调度研究现状 软硬件技术的发展激发了研究人员对并行分布式系统的兴趣。分布式操作系统和 著行进程管理是并行分布式系统中豹关键闯题，而其中的重要任务就是用可行的技 术，将应用程序有效、合理地分配到多个处理器上运行。因此，多处理机任务调度问 题可以简单表述为：如何将进程( 们) 分布( 调度) 到处理单元上以满足某些性能要求，如 运行时间最小化，通信延时最小化，资源利用率最大化等等。个任务管理系统，追 求的是高吞吐率，高资源利用率，总运行时间短，平均等待时间小，具有较好的公平 性和优先级策略。但是，一般说来，一种调度策略不可能同时达到以上目标，追求高 吞吐率可能意味着平均等待时间的增大，而追求小的平均等待时间往往降低系统的吞 吐率。因此，一个合理的任务管理系统应提供多种调度策略，使用户能够从实际应用 需要出发，选取合适的调度策略。常见的经典作业调度策略有： ( 1 ) 先来先服务( f i f o ) ；f i f o 是最简单也是最明显的调度策略。所有的作业根据 进入排队的顺序开始执行。当队列中的下一个作业不能得到资源开始执行时，f i f o 策 路不会去尝试队列中后面的作业。f i f o 最大的优点是易于高效实现，丽且能够保证系 统的公平性，作业的执行顺序是可以预见的。但是它牺牲了系统的吞吐率和利用率， 特别是当作业队列的下一个作业需要大数目的节点时，会出现大量空闲的机器时间间 隔，造成系统资源的极大浪费【羽。 第一章绪论 ( 2 ) 最先适应( f f ，f i r s tf i t ) ：f f 调度策略根据作业到达作业队列的顺序扫描作业 队列中的作业，执行第一个系统资源能满足其资源需求的作业。与f i f o 相比，它不会 由于一个资源需求大的作业被阻塞而影响其作业队列中后续作业的执行。也就是说， 不管系统能否满足排在作业队列头的作业的资源需求，只要作业队列中存在作业其资 源需求系统能够满足，系统将不会停止启动执行新的作业。很明显，f f 调度策略能够 极大地提高系统的吞吐率。但是，其缺点也是明显的，那就是资源需求小的作业延迟 了资源需求大的作业，使其可能长时间得不到执行，从而产生饥饿现象，不能保证公 平性，从而增加系统的平均等待时间。另外，作业的执行顺序具有不可预见性【s 】。 d ) 最优适应( b e s t f i t ) ：b e s t f i t 调度策略扫描整个作业队列，从中选取当前系统 能满足的资源要求展大的作业投入运行。与f f 一样，它不会由于一个资源需求大的作 业被阻塞而影响其作业队列后面的作业得以执行。显然，b e s t f i t 调度策略更能提高系 统的吞吐率，但是，它也不能消除饥饿现象，不能保证公平性，作业的执行顺序也具 有不可预见性f 1 6 】。 ( 4 ) 贪心算法( g r e e d y ) ：g r e e d y 调度策略扫描整个作业队列，并将各个作业进行 组合，从中选取当前系统能满足的资源要求最大的作业组投入运行。g r e e d y 与b e s t f i t 一样，它不会由于一个资源需求大的作业被阻塞而影响其作业队列后面的作业得以执 行。而且，它比b e s t f i t 更能提高系统的吞吐率，但是，它仍然不能消除饥饿现象，不 能保证公平性，作业的执行顺序更具有不可预见性f 9 】。 ( 5 ) 优先级策略( p r i o d t y ) ：优先级调度策略是一种比较通用的策略。首先，系统 根据各种不同的参数( 用户优先级、作业类型等) 计算出作业的优先级，然后根据优先 级对作业进行排列，生成作业队列，系统根据作业队列来逐一考虑是否运行该作业。 优先级策略的使用最好地体现了系统的公平性。优先级策略还可以和其他策略结合使 用，例如f f , b a e k f i l l 等。当优先级策路单独使用时，严格按照作业的优先级来选取作 业，会产生与f l f o 一样的问题，即当高优先级作业的资源要求不能得到满足时，低优 先级作业也都将被阻塞，即使系统能够满足其资源要求。这样，会导致系统资源空 闲，系统不能满负荷运行，降低系统的利用率和吞吐率。而且，低优先级作业会长时 间得不到运行，产生饥饿现象。当优先级策略和其他调度策略结合使用时，将会具有 其他调度策略的一些特征。满足不同系统的调度需要1 9 】。 ( 6 ) 预约策略( r e s e r v a t i o n ) ：为了解决在f f ，b e s t f i t ，g r e e d y 等作业调度策略中 的资源要求大的作业长时间不能得到运行的现象，对于长时间不能运行的作业，可以 采取预约的策略，即当一个作业在队列中等待的时间超过一定的值，对它所需要的资 源进行预约，即这些资源中的一部分成为可用时，不再分配给其它的作业，一直到预 2 青岛大学硕士学位论文 约的所有资源都已得到满足时，将该作业投入运行。预约策略对于调度并行作业和串 行作业混合的作业队列显得尤其重要。由于并行作业需要较多的c p u 资源，它要等到几 个c p u 同时空闲时才能运行。如果系统中有很多串行作业，当有少数c p u 空闲时，它也 不能被执行，而此时空闲的c p u 很容易被其它串行作业或需要c p u 数目少的并行作业所 使用。这样，只要系统一直存在串行作业，该并行作业就有可能得不到运行。通过预 约策略，就可以解决这个问题。预约策略虽然解决了饥饿现象，但它导致了少量的资 源空闲时间，牺牲系统资源的利用率，降低了系统的吞吐率唧。 “) 填装策略( b a c k f i l l i n g ) ：装填策略的运用，解决了预约策略中的资源浪费。 所谓装填策略，就是充分利用预约策略中由于预约产生的时间空隙，避免系统资源的 浪费。通过计算预约形成的时间间隔，从作业队列中选取合适的作业插入到这段时间 段内运行，而不影响预约作业的按时运行，从而有效利用了系统资源，提高系统的利 用率和吞吐率。在装填策略中，如何选取合适的作业以填补预约形成的时间间隔，也是 一个重要的调度问题。一般有以下3 种策略来选取作业【7 】： f f ：扫描作业队列，选取第一个能在该时间段完成的作业进行填充。 b e s t f i t ：扫描作业队列，在所有作业中选取运行时间小于而且最接近该时段 的作业进行填充。 g r e e d y ：扫描作业队列。并将所有在作业进行组合，从中选取总运行时间小于 且最接近该时间段的作业组进行填充。 装填策略还可以与优先级策略结合使用，即系统首先根据作业的优先级进行调 度，当优先级高的作业资源要求不能得到满足时，预约其所要求的资源，然后采用装 填技术，减少资源的浪费。但是，装填策略需要事先知道作业的运行时间，才能为预 约形成的时间间隔进行填补，这使该策略的实现有了一定的困难。 前人研究表明，上述七种调度策略中，最先适应、最佳适应和贪心调度策略能够 提高系统的吞吐率，但是不能保证公平性。而先来先服务、优先级策略和预约调度策 略能够保证系统的公平性，但是降低了系统的吞吐率。填装策略在保证系统公平性的 同时，又能提高系统的吞吐率，是当前研究的比较多的经典作业调度策略之一【9 】。 1 2 网格的出现 随着多机系统的发展，分布式系统、网络开始步入我们的生活。人们在享受网络 带来的通信便利的同时，不禁又想到了可否进一步实现资源的共享，满足人们进行大 规模计算的需求，于是网格便应运而生。目前对网格还没有一个非常精确的定义，国 外媒体常用：“下一代因特网”、“i n t e r n e t 2 ”、“下一代w e b ”来称呼网格的相 3 第一章绪论 关技术。中国工程院院士李国杰认为“1 ：“网格是继传统因特网、w e b 之后的第三个大 浪潮，可称为第三代因特网应用。简单地讲，传统因特网实现了计算机硬件的连通； w e b 实现了网页的连通；而网格试图实现互联网上所有资源的全面连通。”可见网格 的目地是把整个因特网无缝的整合在一起，实现资源的高度共享，为用户提供一个虚 拟平台，实现传统计算机难以实现的复杂科学计算、大规模的数据服务和网络信息服 务，达到计算资源、存储资源、信息资源、知识资源等的全面共享，从根本上消除信 息孤岛和资源孤岛。 可以这样做一个形象的比喻：如果把网格比喻成一盘围棋，那么每一台参与网格 计算的节点就相当于一个棋子，棋盘上纵横交错的线条对应于现实世界的网络。在网 格上做计算，就像下围棋一样，不是靠单个棋子来完成的，而是所有棋子相互配合共 同作用的结果。 可以说网格是多处理机系统发展的结果，是一种特殊的分布式系统。网格中的任 务调度是网格研究的核心问题。在保证每一网格结点能够按时完成本地任务的前提 f ，如何实现系统任务的合理分配是网格任务调度研究的重点。由于网格资源复杂多 变，而提交到网格中的任务也是多种多样的。从而导致了网格任务调度极其复杂，是 典型的n p 完全问题，具体证明见参考文献“1 。基于这样的复杂性，如果继续采用传统 的任务调度策略，很难在多项式时间内得到任务的最优解，由此我们想到了现代启发 式算法。 1 3 遗传算法在任务调度中的发展 遗传算法起源子对自然界进化过程的计算机模拟，它惊人地将算法的简单性和解 决复杂问题的高效性有机地结合起来了。自1 9 7 5 年以来，遗传算法在理论研究和应用 研究上都取得了长足的进展。最近十年内，则更是发展得如火如荼。 作为个解决组合优化问题的有效方法，遗传算法被应用于多处理机任务调度问 题中是十分自然的。关于这方面的尝试，可以追述到二十世纪八十年代末。而e s h h o u 在1 9 9 4 年i e e e t r a n s a c t i o n o n p a r a l l e la n d d i s t r i b u t e ds y s t e m s 上发表的论文：“a g e n e t i ca l g o r i t h mf o rm u l t i p r o c e s s o rs c h e d u l i n g ”是一个重要标志。而同期刊在1 9 9 9 年的第八期，又刊登了相同主题的两篇论文，更表明了人们对于这个问题的重视【4 】。 像其它任务调度算法一样，遗传任务调度算法也是种类繁多，结构各异。不仅染 色体的编码设计各异，而且选择、杂交和变异操作也存在很大差异，而且算法的结果 和性能也都有明显的不同，有时甚至会有截然相反的结论。这些遗传调度算法可以按 图1 1 的方法进行分类。 4 青岛大学硕士学位论文 基于遗传算法的多处理机任务调度 经典遗传算法ji 扩展遗传算法 动态多处理机任务调度静态多处理机任务调度 异构多处理机系统 il 同构多处理机系统 图1 1 基于遗传算法的任务调度研究现状 由上图可知遗传算法不仅可以应用于静态多机系统的任务调度，也可以用于动态 多机系统的任务调度；即可用于同构系统的任务调度，又可用异构系统中的任务调 度。可见遗传算法在任务调度领域的发展前景还是之分广阔的。 目前基于遗传算法的任务调度研究多集中于非二进制的染色体编码方式，和如何 将调度领域的知识溶入算法当中，而忽略了遗传算法本身的一些特性。由此我们不禁 想到了自然界丰富多彩的动物都是由最简单的d n a 、r n a 演化出来的，那么我们为什么 不能用简单的二进制编码来实现复杂系统中的任务调度呢? 而且从软件工程的角度讲 统一的二迸制编码将会使算法有更高的可重用性，便于遗传算法的复用和推广。在参 考文献”1 中有关于二进制编码的染色体具有最大的“模式数一一信息位比”且满足最 小字符集编码原则的详细证明，这里不再多述。 作为一种启发式算法，遗传算法有很好的全局搜索能力，但是根据能量守恒定 理，一方面的增强必然是以一方面的削弱为代价的。因此，和经典调度算法相比，遗 传算法的实时性要差很多。诚然经典调度算法很难在一个复杂多变的环境里寻找到任 务的最优调度，但遗传算法却是以实时性的代价去换取最优解的，这是我们所不愿意 看到的。由此，参考文献【1 0 】提出了一种新的自适应的遗传算法，该算法在系统轻负 载时，采用填装策略；在系统重负载时，采用遗传算法。因为在系统轻负载时，由于 有大量的空闲资源，若仍旧采用本身运行时间较长的广义遗传算法，则会使更多的资 源处于等待状态，降低系统的资源利用率。而此时若采用填装算法，虽然通过填装策 5 第一章绪论 略得到的调度未必是全局最优调度，但是由于算法的实时性强，会大大缩短资源和任 务的等待时间。从宏观上来看在轻负载时，采用填装策略不但可以提高资源利用率， 而且任务从到达到完成的时间未必会大于按照遗传算法去调度所需要的时间。在系统 重负载时，虽然遗传算法本身的执行时间不会变小，但由于此时大量资源处于工作状 态，即便立即将任务提交到网格结点，也只能提交到等待队列，无法占有资源。因此 当大量资源处于工作状态时，可以将任务提交的时间接后，先采用遗传算法搜索最优 解，然后再提交。通过对比实验发现在系统负载大于某一临界值时，采用遗传算法比 填装策略能得到更好的资有利用率；在系统负载小于某一临界值时，采用遗传算法会 降低系统资源利用率。 1 4 本文的研究内容 本文通过深入研究遗传算法机理，探索到一种更适合网格任务调度的遗传算法a 该算法具有较快的收敛速度和优秀的全局寻优能力，无论从生物学角度还是软件工程 角度，都具有很高的理论价值和应用价值。 本文对标准遗传算法，广义遗传算法和并行广义遗传算法进行了数学分析，得 到：广义遗传算法比标准遗传算法有更好的收敛性和全局寻优能力；并行广义遗传算 法比广义遗传算法有更高的运行效率，更适合在有多处理机的网格系统中用于处理分 布式任务的调度闯题。文中提出的任务调度算法采用统一的二进制编码，并以广义遗 传算法为基础。考虑到生物界不变的规律：父代强壮，子嗣可能会强壮的特点，我们 对广义遗传算法做了进一步的扩展：利用问题的领域知识，把握最优解在问题空间中 的分布，再在这个分布范围内随机设定初始群体( 也可以利用其它的寻优算法) ，生 成一些近优解，组成初始群体。从算法本身而言，可过量生成初始个体，从中挑选优 势个体构成初始群体。通过这样方式生成的初始种群，将会在今后的进化过程中占据 优势，能更快地收敛到全局最优解，提高任务调度器的实时性。本文在第五章中对此 也进行了实验对比，对比结果表明优秀的初始种群的收敛速率更快，算法的全局寻优 能力更强。 同时利用m a t l a b 的d i s t r i b u t e dc o m p 砸n g 工具包对并行广义遗传算法进行了仿真。 首先我们将两台计算机通过网线连接在一起，利用m a t l a b 的分布式工具箱将这两台机 器设置成一个分布式系统。其中一台机器设置为c l i e n t ，具有可以自动分派任务和收集 计算结果的功能，类似j o bm a n a g e r ；同时该机器也有分布式计算的功能，可以接受任 务，进行计算。另一台机器设置为普通的w o r k e r , ，可以接受j o bm a n a g e r 分配的任务进 6 青岛大学硕士学位论文 行分布式计算。虽然由于试验环境所限与数学推导公式略有偏颇，但仿真实验结果仍 旧可以证明并行广义遗传算法比广义遗传算法有更高的运行效率和实际应用价值。 7 第二章遗传算法 第二章遗传算法 自达尔文的物种起源面世以来，物竟天择的生物进化观念已经为人们所普遍 接受。神奇的大自然通过简单的d n a 、r n a 演变出了千变万化的生物界，这不禁令 所有人都扼腕叹奇。随着科学的发展，复杂系统中的问题求解成为人们进一步探索世 界的瓶颈，人们在这方面的成就在完美的自然进化之前显得相形见绌。随之人们想到 了能否把“物竞天择，适者生存”的生物进化概念溶入到科学计算中呢? 于是遗传算 法也就应运而生了。 2 1 遗传算法 遗传算法就是希望通过模仿自然界的进化过程，找到一种在复杂系统中求解问题 的有效方法。遗传算法是一个概率算法。它首先产生问题的一组候选解作为初始种 群。然后将初始种群作为父代，通过杂交、变异等遗传操作，产生新的群体( 子代) 。 再根据适应度评价的结果，对个体进行筛选，实现优胜劣汰。最后依据终止条件决定 是否继续进化过程。遗传算法利用进化操作的随机性，保证了解群完全覆盖解空间， 同时通过杂交、选择和变异等操作，使之收敛于最优解。表3 1 生动的将各种生物进 化概念和遗传算子对应了起来f ”。 表2 1 遗传算子对应表 生物遗传概念遗传算子 个体解 染色体解的编码 基因编码中的某一分量 适应能力适应值函数 种群 一组解，种群舰模决定解的个数 杂交 通过杂交算子产生一组新解的过程 变异编码的某一分量发生变化的过程 由于传统的线性数值方法在面对复杂的工程问题，尤其那些包括噪声干扰的动态 随机非线性系统时显得无能为力，因而遗传算法成为近二十年内发展最为迅速的计算 机研究问题之一。它首次触及了原先被认为超出计算机求解能力以外的领域，如快速 的药物设计，供应链管理问题，战场中的快速战术分析等。更激动人心的是，将来它 8 青岛大学硕士学位论文 也许会成就人类人工智能的梦想：使计算机能够自我学习，并成为任何一个领域的专 家f 】。 通常我们称上世纪六十年代由j o h n h o l l a n d 在用计算机模拟自然进化时提出的遗 传算法为经典遗传算法( s g a , s t a n d a r dg e n e t i ca l g o r i t h m ) ，其基本流程如图2 1 所示： 图2 1 经典遗传算法流程图 上图清晰地展示了经典遗传算法的流程。可以看出遗传算法源于自然规则，与传统的 优化算法相比有十分显著的特点： l 、遗传算法以决策变量的编码作为运算对象。 2 、遗传算法直接以适应值作为搜索信息，无需导数等其它辅助信息。 3 、遗传算法使用多个点的搜索信息，具有隐含并行性。 4 、遗传算法使用概率搜索技术，而非确定性规则。 9 第二章遗传算法 2 2 广义遗传算法 1 9 9 8 年，董聪在大自然探索上发表了文章“广义遗传算法”。该文以 m o r g a n 的基因理论及e l d f i d g e 与g o u l d 的间断平稳理论为依据，在融合了m a y r 的边 缘物种形成理论和b e r t a l a n f f f y 一般系统理论的基础上，对s g a 进行了改进，并将其定 义为“广义遗传算法”。广义遗传算法摈弃了传统遗传算法普遍采用的遍历搜索策 略，采用的是定向演化模式。它与基本遗传算法的区别主要体现在进化程序上。简单 来说，基本遗传算法的进化程序为： 双亲选择一杂交一变异一生存选择一下一代种群 而广义遗传算法的进化程序为17 l ： 双亲选择一杂交一家四口一四分之二生存选择 一变异一一家四口一四分之二生存选择一下一代种群 这里涉及三种选择方式：双亲选择、生存选择和四分之二生存选择，这三种选择 方式的区别如下： 双亲选择是不放回随机选择。也就是说，在种群中，首先以等概率随机选择出两 个个体组成需要进行杂交的母本，下一次再从剩余的个体中随机选择两个需要进行杂 交的母本，以此类推，直至所有个体都被选完。如果设种群规模为偶数，则需选择 n 2 次，形成n 2 对需要杂交的母本。双亲选择确保了每个父代在子代中均有繁衍的 机会【5 1 。 生存选择是一种概率选择方式，体现了适者生存的原则。指对于变异后形成的临 时种群，采用“轮盘赌”的选择方式，由适应值的大小决定哪些个体被保留，哪些被 淘汰，哪些个体被重复选中【那。( 有关轮盘赌的执行方式请参见有关文献) 四分之二生存选择是从四个个体中选择前两个适应值较大的个体，抛弃剩余两个 适应值较小的个体。在杂交和变异过程中，加入四分之二生存选择，使父代和子代进 行竞争，并让其中的优良者进入下一轮的竞争环境。此举措保证了算法的迭代稳定 性，并使其具备了实现局部最优化的功能【5 l 。 广义遗传算法可以进一步描述为：从当前种群中进行双亲选择，选出的母体进行 杂交，在母体和杂交后产生的两个新个体中进行四分之二生存选择，保留两个适应值 较大的个体，丢弃两个适应值较小的个体。保留下来的两个体进行变异后，仍然与变 异后产生的两个新个体一起进行四分之二生存选择。如此反复进行n 2 次，直至形成 下一代种群。 l o 青岛大学硕士学位论文 除此之外，广义遗传算法中的杂交和变异也与基本遗传算法中的略有不同。在基 本遗传算法中，杂交和变异都按照拟定的概率进行，而在广义遗传算法中，由于父代 一定会参与竞争，因此杂交的概率恒为l 。 与经典遗传算法相比，广义遗传算法具有鲜明的特征【5 】： l 、选择细分为双亲选择和生存选择两种。 2 、在进化过程的每一次循环中，杂交操作为一必然事件而非或然事件。 3 、杂交和变异产生的新个体被选中是一非均匀随机事件，其概率依赖于上一次该 染色体发生改变的后果，采用奖优罚劣的策略。 4 、进化过程其实可描述为渐近和骤变两个阶段。渐近阶段主要通过杂交和选择的 协同作用逼近局部最优解；骤变阶段主要通过变异和选择的协同作用实现局部 最优状态的定向迁移，使下一次循环可在更好的起点上开始。 2 3 粗粒度并行遗传算法 上述基本遗传算法和广义遗传算法归根结底都属于串行遗传算法，主要用于解决 传统搜索算法难以解决的非线性优化问题。在解决这类n p 优化问题时，往往需要大规 模的计算，因而整个进化过程是非常缓慢的【1 1 】。因此人们想到了能否在多台处理机上 同时运行遗传算法以提高运行效率，由此并行遗传算法 o ， z ，- f ) o ，则有 p k 。= ，i k = o = p 蜀+ 。= ，i 蜀= 口 3 - ( 2 ) 成立，称 x k ，k = o 1 ) 为齐次的马尔可夫链，记作 曩町= p x * 。= i x 。= 磅 1 4 青岛大学硕士学位论文 3 ( 2 ) 式表示从状态i 转移到状态，的概率与册和，无关。即无论质点在何时处于 状态i ，只要由i 出发，经刀个单位时间转移到，的概率都相同a 齐次马尔可夫链的一 步转移概率所组成的矩阵为： ，= p o op o j p l op l la ： p 中的元素n 满足条件： 岛o ：乃 显见齐次马尔可夫链的一步转移矩阵满足随机矩阵的条件，属于随机矩阵韵范 畴。 定义3 4 ( 本原随机矩阵) 若随机矩阵p ，存在七l 。使得尸 o 即对于任意i d e s ， 均有露 o ，则称p 为本原随机矩阵。 定义3 5 设 文。， = 0 ，l ，) 为有限齐次马尔可夫链，露为| i 步转移概率。若存在七 1 。使 o ，称状态i 可达状态工记f 叶，若有f 呻，和，_ f 同时成立，称i 与， 互通，记作i 付，。 定义3 6 对于马尔可夫链的状态i ，正整数集 弗l ；力 o ) 的最大公因子碣称为状 态i 的周期。若珥 l ，称状态f 为周期的；若巧= l ，称状态i 为非周期的。 定理3 1 若i 竹j ，则i 与，有相同的周期。 证明：二f 付_ ， 3 l l ，刀l ，使得巧。 o ，劣 0 巧“彤x 哆 o ，垆町才 o 1 5 第三章遗传算法的数学模型及收敛性分析 设4 ，t 分别为，与，的周期，则，+ 栉可被z 和q 整除，且拳 o 艺“”钔矽巧却巧o o 从而“+ 疗+ z ) 可被z 整除 又。o o u + 功可被d ，整除 + z 可被d ，整除 同理可得：t 可被z 整除 ：d 。= d 1 定理3 2 若马尔可夫链是不可约的，即所有状态之间互通，且存在， 使乃 o ， 则此链是非周期的，其转移概率矩阵为本原随机矩阵。 证明：+ ? 巴 0 7 矿= 1 又由于所有状态之间互通，由定理3 1 得：该马氏链中所有状态的周期都为1 。v i ，j ，都有i 争_ ， 二j ，使得舻 o ，彬 o 巧嘞2 守乞巴巴 o 巧+ 和”矽+ 匕易x x 乞 o 取o - - m a x + ；i , j 册，则后o 时，秽 o 该马氏链的转移概率矩阵为本原随机矩阵 定义3 7 一个定义在状态空间s 上的概率分布，= i 。，i ：，i ，一) 称为马尔可夫链的 平稳分布，如果，。= 1 ，且有： 1 6 青岛大学硕士学位论文 ，= ，= f 。，：， 冬：季：；： = o 。只i + f2 b ，+ ) ，( fl 毋2 + f2 最2 + ) ，( fl 弓，+ f2 昱，+ ) ，) e p i i = i ，只 眶s 平稳分布也称马氏链的不变概率测度，对于一个平稳分布f = p 。，i ：，f ，一，有这 样的性质： ，r = 石p = ，r p 2 嚣石p 3 = = 7 r p ” 马尔可夫链 文。，k = o ，l ，) 的平稳分布f = f 。，f2 ，) 存在这样的性质： l i r a 力= t i m p x ( n ) = j ) = f f ，也就是说经过长时间转移后，马氏链各状态的概率 h 帽。口埘 趋于稳定，f = 和，i ：，f ) 即是该链的极限分布。 定理3 3 如果，是本原随机矩阵，则存在一个平稳分布，r ，使对任意，有 一目= 矿o - 证明：由本原随机矩阵的定义可知，对于本原随机矩阵，有疗 o 。 当胪l 时，见g o ，i , j e i m ，( n ) = r a i n 硝表示在珂次转移后在，列中最 小的一个元素。设m 研) = m 聱考表示在，1 次转移后在，列中最大的一个元素。因 为v f 都有： 矽) - 肌砖。只。m s ( n 一1 ) = - 0 1 ) j e jk e l 包括j 列中使得力为最小的i 在内，因此可得：m j ( n ) 1m j ( n 一1 ) ，表明每列的最 小值随着，的增加而增大。同理v f ： 砖= m ( n - i 既鸠。一1 ) ；鸠。一1 ) j ，i e ， 鸩( 帕哆伽一1 ) ，即每列的最大值随着一的增加而减少由于鸩( 功和一o o 都 是有界序列，因此当刀一。时，都有极限值。 1 7 第三章遗传算法的数学模型及收敛性分析 现证明嫩哆( 功= 。l i r a m j ( n ) 设s 为无限小正实数，当i = i o 时，经