（计算机应用技术专业论文）基于自适应遗传算法的服务工作流调度问题的研究.pdf

论文摘要 随着互联网普及和计算机技术的发展，作为下一代分布式计算平台，网格计 算越来越得到人们的重视。网格计算中的一个重要问题工作流调度就是一个 很有应用前景的技术。工作流调度问题把用户提交的任务分为若干个存在互相依 赖关系的子任务，要求工作流管理系统( w 舢s ) 为工作流的所有子任务分配一个 服务器，根据用户的喜好最大化某种需求。工作流调度最大的挑战在于在较短的 时间内，要为用户随机给定的任务集合分配服务器。不但这些服务器的性质会动 态地变化，而且服务器本身也属于不同的系统管理者所有。 本文提出了一种混合自适应遗传算法，用来解决网格环境的工作流调度问 题，在最大化某种用户喜好的同时还要求调度满足用户提出的约束条件，比如费 用、完成期限等。本文首先简单介绍网格环境的工作流和遗传算法。接着根据用 户的三种主要需求建立数学模型，设计相应的适应度函数。然后介绍自适应的遗 传算法，算法通过聚类分析提炼出若然干变量，把这些变量融入模糊逻辑的思想 指导遗传算法控制参数的更新。同时算法还加入了并行算子，减少算法的计算时 间。另外，增加了染色体的寿命属性，使得染色体在后期能通过重调整算子，实 现优胜劣汰。最后，通过实验验证了本文提出的自适应遗传算法在求解工作流调 度问题上的效率。 关键字：自适应，网格，工作流，遗传算法，模糊系统，并行 a b s t r a c t w i t ht h ep o p u l a r i t yo fi n t e m e ta n dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , 鲥d c o m p u t i n g ，a st h en e x tg e n e r a t i o nc o m p u t i n gp l a t f o r m s ，h a sr e c e i v e dc o n s i d e r a b l e a t t e n t i o n w o r k f l o ws c h e d u l i n g ，o n ei m p o r t a n tp r o b l e mo ng r i dc o m p u t i n g ，i sa p r o m i s i n gt e c h n o l o g y w o r k f l o ws c h e d u l i n gp r o b l e mr e q u i r ew o r k f l o wm a n a g e m e n t s y s t e mt oa s s i g ne a c ht a s ki nw o r k f l o wt oas e r v i c eo fg s p , a n dm a x i m i z et h eu s e r s p r e f e r e n c e s o n eg r e a t e s tc h a l l e n g e i nw o r k f l o ws c h e d u l i n gi st op r o v i d eu s e r sas e to f s e r v i c e sf o rar a n d o md i s t r i b u t i o nt a s ks e t n o to n l yt h es e to fs e r v i c e sw i l lb e d y n a m i c a l l yc h a n g e d ，b u t a l s ot h e s e r v i c e s 锄eb e l o n gt od i f f e r e n t s y s t e m a d m i n i s t r a t i o n i nt h i sp a p e r , ah y b r i da d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) i sp r o p o s e dt os o l v e w o r k f l o ws c h e d u l i n gp r o b l e mi ng r i de n v i r o n m e n t t h ea g am a x i m i z eu s e r s p r e f e r e n c ea n dr e q u i r et h es c h e d u l i n gt om e e tw i t hs c h e d u l i n gp r o p o s e db yu s e r , s u c h a sc o s t ，d e a d l i n ea n ds oo n i nt h i sp a p e r , w ef i r s ti n t r o d u c ew o r k f l o wi n 班d e n v i r o n m e n t ，a n dg e n e t i ca l g o r i t h m s e c o n d l y , w eb u i l dm a t h e m a t i cm o d u l e sa b o u t w o r k f l o w t h i r d l y , a nh y b r i da d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) i sr e s e a r c h e d ，t h e a l g o r i t h mu s ev a r i a b l e s ，e x t r a c t e df r o mc l u s t e ra n a l y s i sa l g o r i t h m , t og u i d ef u z z y s y s t e mt ot r a i nc o n t r o lp a r a m e t e r si na g a t h ea l g o r i t h mh a sa l s oj o i n e dp a r a l l e l o p e r a t o r , t or e d u c et h ec o m p u t i n gt i m e i na d d i t i o n , a t t r i b u t i o no fl i f e t i m ea n d r e a s s i g n m e n to p e r a t o ra r ei n t r o d u c e di na g a ，t oa c h i v es u r v i v a lo ff i t t e s ti nt h el a s t g e n e r a t i o n s a tt h ee n do ft h i sp a p e r , r e s u l t so fe x p e r i m e n t sc o n f i r mt h ee f f e c t i v e n e s s o fp r o p o s e da l g o r i t h m k e yw o r d s ：a d a p t i v e ，g r i p ，w o r k f l o w , g e n e t i ca l g o r i t h m , f u z z ys y s t e m , p a r a l l e l 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体己经发表或撰写过的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：官兆 日期：2 0 f o 钻月3f 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即： 学校有权保留学位论文并向国家主管部门或其指定机构送交论 文的电子版和纸质版，有权将学位论文用于非赢利目的的少量复 制并允许论文进入学校图书馆、院系资料室被查阅，有权将学位 论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。保密的学位论文在解密后使用本规定。 学位论文作者签名：渤匕 日期：列哞岁月3i e l x斗2 午明年 名 叫 签 币 羽 师 期 导 日 中山人学硕士学位论文 1 1 引言 1 绪论 网格计算的概念自从上世纪九十年代被人们提出以来，一直被认为是下一代 分布式并行计算平台的核心技术。网格计算通过若干计算或电子设备组成的网络 ( 一般指互联网) 来共享强大的计算能力和数据存储能力，它能协调，分配和组 合分散在管理区域内多种硬件资源，这些资源包括计算机，工作站，网络设备， 数据存储设备，科学仪器等等。通过灵活地调度互联网上的多个计算资源，人们 能解决很多巨型机才能解决的复杂问题，极大地节省了购买高端硬件的开销。目 前网格计算已经在很多商业和科研邻域取得广泛的运用，国外一些i t 巨头都已 经开始研究网格计算的解决方案，比如i b m ，o r a c l e ，s u n ，h p 等 1 - 5 。在网 格中，我们把一系列任务按某个特定的顺序用计算设备处理，以达到预定目的问 题称为工作流。工作流中的任务集合通常用一个有向无环图表示，图中的每 个节点表示一个任务，图的弧表示任务之间的先序关系。工作流是一个n p 难问 题，它要求我们为了完成客户提交的所有任务，在一个服务器的集合中选择合适 的计算设备 1 。传统的方法仅仅单一地考虑最小化完成任务的时间或最小化计 算的开销，但是现实生活中，我们的客户不仅要求在规定时间内完成计算任务， 还要求开销尽量小，安全性尽量高等等。我们需要综合客户的所有要求，并提出 新的基于综合性指标和用户约束的调度算法。 在求解工作流调度问题上，遗传算法一直是一个有效而容易实现的方法，但 是以往的遗传算法往往收敛较慢，容易陷入局部最优解。虽然也有很多改进算法 取得了不错的效果，但是它们往往没有考虑用户的多种需求。本论文首先根据用 户的三种主要需求设计相应数学模型，然后提出一种新的自适应遗传算法，综合 了模糊系统指导下的交叉、变异参数的更新，染色体根据寿命的重调整，以及并 行计算等思想，致力于解决群体中利用( e x p l o i t a t i o n ) 能力和探索( e x p l o r a t i o n ) 不能同时提高的矛盾。通过分别求解函数优化问题和工作流调度问题的实验，证 明了本文提出的自适应遗传算法取得的效果。 第1 页 中山人学硕士学化论文 1 2 选题背景 近来，网格计算技术已经升级为开放式的网格服务架构( 0 g s a ) ，它引入 了互联网服务到互通性的网格模型里【1 】，首先，o g s a 允许网格市场的不同的 网格服务供应者( g s p s ) 提供计算资源，调度问题变为给每个任务匹配一个网格 服务提供者( g s p s ) ，由他提供的一个服务实例( 可以是某个计算机，处理器， 存储设备等) ；第二，除了时间长度( m a k e s p a n ) ，客户要求的服务质量( q o s ) 还可 能包含计算的开销( c o s t ) 可以是使用某个实例需要付的服务费，以及可靠性 ( r e l i a b i l i t y ) ，安全性( s e c u r i t y ) 等等。 论文 1 】 2 】提出的综合考虑3 种服务指标一一m a k e s p 趴，c o s t ，r e l i a b i l i t y 的工 作流模型更符合实际生活，尤其是论文 1 使用专门为工作流而设计的7 种启发 式公式来优化蚁群算法，取得了不错的效果。当然，以上两篇论文考虑的工作流 模仍然是基于每个g s p s 或服务器实例最多只能为一个任务服务的假设，并没有 考虑到服务器可以在不同的时间解决不同的任务，以减少不必要的开销，当然如 果考虑处理器的复用情况，问题将会更加复杂，随着前面解决任务使用服务器的 不同，后面可以使用的g s p s 也就会不同了，这也是本论文的努力方向。 本论文主要应用的算法是遗传算法 6 ，它是计算智能领域一个举足轻重的 分支，其思想源于生物科学的进化理论和遗传变异理论，是通过模仿自然界的进 化活动，设计出能够有效解决优化问题的系统方法。国内外有很多论文 1 3 】- 2 0 】 也作过求解工作流的工作，这些论文使用遗传算法，模拟人工退火，粒子群算法 等元启发式算法对问题取得了一定的改进，但它们没有加入足够启发式信息以优 化所用的算法，一般花去太多的计算时间，而且结果仍然不够优化，此外它们也 没有考虑对用户多种需求的综合。 遗传算法来源于生物科学的两个重要理论自然进化和生物遗传。这两个 理论为h o l l a n d 研究人工自适应系统提供了宝贵的思想源泉。在前人运用计算机 进行生物模拟的基础上，h o l l a n d 发现了自然界的生物遗传进化系统同人工自适 应系统的相似性，成功地建立遗传算法的模型，并对遗传算法搜索的有效性进行 了理论证8 y j 2 3 - 2 5 】。 此后人们在遗传算法的理论研究，特别是收敛性方面做了很多的工作 2 6 】 【2 9 ，从理论上初步证明了遗传算法求解n p 问题的有效性。此外，遗传算法被 第2 页 中山人学硕士学位论文 广泛地运用于很多的领域，并取得了不错的效果 7 】， 3 0 3 4 。 虽然遗传算法是一种比较“老”的元启发式算法，但是在今天它仍然有着勃 勃生机，很多人致力于它的研究。遗传算法因为计算速度快，鲁棒性，可扩展性， 并行性等优点受到人们的重视，其中如何通过利用每次迭代的一些计算结果加快 收敛速度，成了一个热门的研究方向 6 。论文 7 使用了基于聚类信息的模糊集 函数来优化交叉和变异算子，一定程度上改进了遗传算法。模糊集是z a d e h 8 】 提出来的，它用模糊的0 到1 的数来表示一个物体在是否在一个集合里面，而不 是传统的是或者非。论文 9 】- 1 2 使用这种思想，提出了使用基于模糊集的归属 函数( m e m b e rf u n c t i o n ) 来表示算法当前的运行状况这些函数以当前需要优 化的参数作为输入比如论文 7 】提出遗传算法可以分为四个阶段的思想，然 后根据不同的阶段选择不同的归属函数，用计算出的结果来优化参数。论文 9 】- 1 2 】都在一定程度上改进了原有的算法，也从实际上证明了模糊集的思想移植到 元启发式算法，特别是遗传算法上的成功。 1 3 主要工作 本文主要研究网格环境下的工作流调度问题，考虑在用户给定的主要目标和 约束条件下，给工作流的所有任务调配合适的服务器，以最优化用户的目标。 第一，考虑用户的三种主要需求( 费用、完成时间和安全性) ，建立了三种 数学模型。三种模型分别以其中一种需求为优化目标，其它两种为约束条件。这 种包含目标和约束的工作流更加符合现实的情况。 第二，把基于聚类和模糊集的遗传算法，用在了离散优化问题工作流调 度上。 第三，改进了论文【7 提出的算法，使之适合工作流问题。增加了并行算法 子，使得算法的计算时间减少一半。增加了染色体根据寿命进行优胜劣汰的重调 整算子，使得算法在后期的探索能力不被过分地降低，甚至有所提高。 1 4 研究意义 在为网格环境下的工作流调度服务器的时候，服务器具有动态变化、资源跨 区域等性质，不利于人们在较短的时间内给出一个即符合用户需求，又最优化用 第3 页 中山人学硕士学位论文 户目标的调度方案。使用鲁棒性强的概率性算法，能极大地节省时间，得出一个 符合要求的结果。 本文提出的混合自适应遗传算法在以有的基于聚类的遗传算法的基础上有 所改进，使之能适应网格工作流问题的特殊性，并能通过并行化减少算法的计算 时间，提高对已有解的利用，从而在较短时间内达到预期的调度效果。 1 5 论文结构 第2 章介绍网格环境下的工作流，根据用户主要需求的不同，建立相应的数 学模型。 第3 章简要介绍了遗传算法。介绍了遗传算法的基本思想、基本流程和各种 常用算子。 第4 章介绍了混合自适应遗传算法，综合了k 聚类和模糊系统指导下的参数 控制，主仆关系模型下的并行算子和根据染色体寿命的重调整算子等三种主要思 想。 第5 章实验部分。用本文提出的自适应遗传算法求解函数优化和工作流问 题，通过模拟实验寻找合适的混合自适应遗传算法的参数，并比较不同遗传算法 的求解不同优化模型的工作流问题上的优劣。 第6 章论文总结和未来的展望。 第4 页 中山大学硕士学位论文 2 1 网格工作流概述 2 网格工作流 网格计算( g r i dc o m p u t i n g ) 是通过利用网络中大量可用的异构网格服务提 供者( g r i ds e r v i c ep r o v i d e r ) ，通常包括p c 机，工作站，数据库，网络硬盘，数 据源，计算节点等) 完成大型的计算任务的方法。可以说网格计算的兴起和互联 网的发展是密切相关的，当前i b m ，o r i o l e 等国际大公司已经开始提供网格计算 的商业服务。除了计算网格的应用开发，管理和调度网格资源内的计算设备用于 求解实际问题也是一个复杂的任务。网格计算通过综合网络( 通常是互联网) 的 各种资源，灵活地调度可用资源，从而能求解非常复杂的问题，而工作流就是网 格计算应用的一个很好的例子。 工作流 3 7 】( w o r k f l o w 是对工作流程及其各操作步骤之间业务规则的抽象、 概括、描述。工作流建模，即将工作流程中的工作如何前后组织在一起的逻辑和 规则在计算机中以恰当的模型进行表示并计算。工作流要解决的主要问题是：为 实现某个业务目标，在多个参与者之间，利用计算机，按某种预定规则自动传递 文档、信息或者任务。可以说工作流最早起源于商业领域的办公自动化，早在上 世纪7 0 年代工作流的概念就已经被人们提出，然而直到9 0 年代，随着计算机技 术的发展和互联网的普及，工作流才逐渐走进人们的视野。如今工作流在商业， 电信，医药卫生，物理学，生物学等领域都取得了广泛的应用 3 7 】。 网格计算的架构图如图2 1 所示，它反映了网格计算的基本原理，首先由g s p ( g r i ds e r v e i c ep r o v i d e r ) 提供服务的索引到服务字典，然后用户才能查找并使 用服务，而且用户通过资源供应商和g s p 进行连接 3 8 1 1 3 9 。可以说g s p 具体包 含哪些服务，g s p 的具体调度策略等等对于用户都是透明的，他仅仅关心g s p 提供的那些服务，以及g s p 提供服务的质量和价钱。当用户提交的任务可以划 分成若干相互有依赖关系的子任务，而且这些子任务一定要被不同类型的服务器 ( 本文的服务器指的是提供服务的设备，包含网格中的任何可用资源) 所执行， 那么我们称这个任务为工作流。 第5 页 中山人学硕士学位论文 g s pg s pg s p 图2 1 网格计算的工作架构 如图2 1 ，用户提出的单个任务需求最后会被划给g s p 的一个具体的服务实 例( s e r v i c e s e r v i c ei n s t a n c e ) 解决，而如果用户提出的任务是可以分成一组互不 相包含又相互有依赖关系的任务集合，也就是一组工作流任务，那么资源供应商 所作的工作还包含了工作流的调度。同时由于工作流需要的服务往往是动态变化 的，即使相同的工作流问题，对于确定性的算法也难以求得满意的答案。 工作流最先的起源之一来源于计算机科学的支持类基础性研究 4 0 。虽然己 存在的科学工作流系统能解决诸如工作流创建、计划和执行等问题，但是深度的 科学研究需要我们提供更加易用的工作流创建工具，开始高级的自动化工具，提 供鲁棒性强的工作流执行，管理动态的工作流等等，这些工作都需要强大的工作 流服务调度算法的支撑。 所谓工作流调度，就是在把工作流的每个子任务都分配一个g s p 的服务。 根据论文【3 5 】，工作流调度是一个n p 难问题，很多论文尝试过用传统算法解决 这个问题，但是能解决的问题规模毕竟有限，而且计算速度较慢，难以应用到实 际的大规模问题中去。因此本文尝试用遗传算法求解这个问题，为了更好地解释 工作流，我们先尝试对问题进行简单的数学建模。 第6 页 中山人学硕士学位论文 2 2 网格工作流的数学模型 图2 2 工作流实例e - e c o n o m i c 工作流可以模拟成一个有向无环图( d a g ) ：g = ( 聊) 3 5 。点的集合 v = 石，互，z ) 表示工作流中的任务，有向边的集合么= 臃，巧矿) 表 示任务之间的依赖关系。若 a 则称任务巧是任务乃的父塞，任务乃 是任务霉的弦王。如图2 2 ，互是正和互的父亲，而弓是五和互的孩子。工作流 的有向边的包含了任务完成的先后次序，如果 彳，则只有巧完成后， 乃才能被执行。如图2 2 ，互必须在瓦和五前完成，而弓的执行必须放在在互 和正完成之后。一个任务的先庄任釜是它的父亲任务或它的父亲任务经过有限次 迭代得到的父亲任务，一个任务的后庄任釜是它的父亲任务或它的父亲任务经过 有限次迭代得到的父亲任务。如图2 2 ，正的后序任务为五和五，而互的后序任 务是乃和写。这表示如果要执行互，必需在完成任务五和互之后。而任务乃和 乃被执行的必要条件是已完成互。互的前驱任务集合p r e c ( t 5 ) = 五，互) ，后继 任务集合s u c c ( 互) = 乃，巧) 。为了方面地计算工作流的开始和结束时间，在工 作流的任务中，再添加两个虚拟的任务e 和z ，它们的执行不需要时间和费用， 仅仅起到起始和结束的标示作用。e - e c o n o m i c 工作流增加两个虚拟任务后的有向 图，如图2 3 所示。今后本文所有的工作流都默认增加了虚拟的起始任务z 和结 束任务z 。 第7 页 中山大学硕士学位论文 图2 3 增加开始和结束节点后的工作沉实例e - e c o n o m i c 根据工作流的定义和有向无环图的性质，我们得到以下定义： 定义l ：一个任务只能在它的所有先序任务完成后才能被执行。 定义2 ：一个标准工作流内的任务必须都执行而且仅仅执行一次。 定义3 ：每个任务必须在某个时间段分配给一个可以执行该任务的服务实 例。 定义4 ：每个g s p 在一个时间段内最多只能提供一类服务。 对于n 个任务的工作流，我们任务互的可用服务区域为墨= s ；，s ；，一，) ， 其中- - 1 ，疗。假设工作流的用户仅仅关心三个指标：费用( c o s t ) ，时间( t i m e ) 安全性( r e l i a b i l i t y ) 。则我们设定第f 个任务可用的第，个服务实例有四个 变量 s l g ，c ，s ? f ，s i 厂) ，掣g 表示g s p 的i d ( 在整个网格中唯一) ， s l c 表示任务f 执行的费用，4 t 表示任务i 执行的时间，r 表示任务i 执行 的安全性。 假定用户在提交任务的时候还给出了费用等三个指标的预期：预算 ( b u d g e t ) ，最晚完成期限( d e a d l i n e ) ，可靠性( a v a i l a b i l i t y ) 。我们的调度结果 必须满足这些预期的要求。 假设工作流的一个调度为x = “，而，吒) ，x c o s t 为调度x 的费用， x t i m e 为调度x 的完成时间，z r e l i a b i l i t y 为调度x 的可靠性。 第8 页 中山大学硕士学位论文 x c o s t = 带c i = 1 x t i m e = 疋的最晚结束时间 ( 2 1 ) ( 2 2 ) x r e l i a b i l i t y = m i n 妒，( 2 3 ) 一l 、一一， i - - 1 下面根据公式( 2 1 ) - ( 2 3 ) 建立网格工作流的数学模型 摆血：如果用户最关心的是费用，用户要求费用最小化的同时需要 d e a d l i n e ，a v a i l a b i l i t y 满足约束条件， m i nx 。c o s t ix t i m e d e a d l i n e 譬f b u d g e t & & t i m e d e a d l i n e 。 i o 5 d e a d l i n e t i m e + o 5 + 以矿c o s t d e a d l i n g ( 3 3 ) 加鲫2 1 + c o s t m i n 7 d 细，r e ，渤f f j 纱，矿c o s t b u d g e t & & t i m e s d e a d l i n p 【0 5 ( b u d g e t c o s t + d e a d l i n e t i m e ) + t r ，o t h e r w i s e 其中仃= r e _ i nt o t a lr e f i a b i l i t y m a xt o t a lr e l i a b i l i t y ，m i n t o t a l r e l i a b i l i t y 第1 3 页 中山人学硕士学位论文 表示网格中可用的安全性最小的服务的安全性指标，对应的 m a x t o t a l r e l i a b i l i t y 表示网格中最大的安全性指标。 3 5 选择算子 增加选择算子是遗传算法区别于其他智能算法的因素之一。选择算子要求每 一次在父辈染色体中根据某种规则，选择若干染色体作为新一代染色体( 可以重 复选择同一个父辈染色体) ，参与后面的交配和变异过程。选择算子的基本思想 是适应度越高的染色体，越有可能被保留到后代的种群中；反之，适应度越低的 染色体，越有可能被淘汰，失去繁殖后代的机会。这点和自然界的“优胜劣汰” 法则是一致的。 人们针对不同的问题提出了很多不同选择算法( 选择算子) ，这些选择算子 思想上主要分为概率性选择方法、线性队列选择方法和局部选择方法，它们各有 利弊。 ( 1 ) 局部选择 局部选择算法的基本思想是从父代染色体中选择继续繁殖的时候，每次选择 子代染色体的时候，都在一个邻域( 邻域包含的染色体的规模小于整个种群) 内 选择一个适应度最高的染色体。针对不同的领域的拓扑结构，或者邻域的规模， 可以都与同一个种群每次可以选择的染色体也会有区别。如图3 2 ，描述了一维 拓扑结构下的局部选择，选择池的大小分别为r = 3 ，r = 5 。在一维拓扑结构的时 候，一般把染色体按照下标看作一个环形结构，即第1 号染色体的左邻居为第 p o p号染色体，右邻居为第2号染色体，其他的以此类推。图32中判定第isize 个染色体的后代时，如果r = 3 ，在第i 号染色体和a ，b 之间选择适应度最大的； 如果r - - 5 ，在第i 号染色体和a 、b 、c 、d 之间选择适应度最大的。 r = 5 图3 2 局部选择的拓扑结构( 1 维) 第1 4 页 “3 中山大学硕士学位论文 图3 3 局部选择的拓扑结构( 2 维) 如图3 3 所示，局部选择如果是2 维结构拓扑，那么第f 号染色体的邻居除 了它的左右邻居a 、b ，还包括上下邻居c 、d 。对f 号染色体进行选择的时候， 要在第i 号染色体和a 、b 、c 、d 中选择适应度最大者作为子代染色体。 ( 2 ) 随机选择 随机选择( s t o c h a s t i cs e l e c t i o n ) 是g o l d b e r g 于1 9 8 9 年提出的 4 3 】，又叫轮 盘赌选择算法( r o u l e r ew h e e ls e l e c t i o n ) 。轮盘赌是基于概率的随机选择。 轮盘赌的过程大致如下 6 ： 计算每个染色体v f 的适应值p z ( v ) 求群体的总适应值尸 f ：y e v a l ( v , ) f = l ( 3 4 ) 求每个染色体的选择概率只，i = l ，2 ，, p o p _ s i z e 只= 了e v a l ( v i ) ( 3 5 ) 求每个染色体的积累概率q 明9 2 c i2 p i f 兰l ( 3 6 ) 对轮盘转动p 叩泷次，每次随机产生一个介于0 到1 之间的随机数p ，如 果p c 1 ，那么本次选择1 号染色体，否贝 。，、4 4 ，- 足q p l 的区间，本次选 择的是第计1 号染色体，其中i - - - 1 ，2 ，, p o p _ _ s i z e 。 第1 5 页 中山火学硕士学位论文 ( 3 ) 线性排序选择 线性排序选择也属于随机选择的范畴，它是有g r e f e n s t e t t e 和b a k e r 于1 9 8 9 年提出来的【4 3 】。线性排序选择定义染色体x 被选择的次数为t s r ： t s r ( x ) ：m i n + ( m a x m i 咒) r a n k ，( x ) ( 3 7 ) v 如公式( 3 7 ) ，t s p ( x ) 是染色体x 被选择作为子代的次数( 不一定是整数) ， 其中l m a x 2 ，m i n + m a x = 2 。r a r e ( x ) 为种群中按照适应度低到高排序时， 染色体x 所在的位置。根据r s r ( x ) = n ，使用和轮盘赌相似的方法，可以计 算出新一代的种群。 以上三种选择方法是最常用、最有鲁棒性的方法，论文 4 3 通过模拟实验， 对这三种选择算子的基因位( a l l e l e s ) 多样性，基因型多样性( 即染色体之间的 差异) ，近亲交配程度，鲁棒性( 这里的鲁棒性指算法在1 0 0 0 代以内求出最优解 的概率) 进行了分析，得出结论：对于上述四个指标，局部选择算法最好，轮盘 赌次之，线性排序最差。在算法初期，局部选择能有效地避免最差的一些染色体 的干扰，及时地淘汰掉这些染色体，从而提高算法的收敛速度。在算法后期，局 部选择能维持算法的多样性，减少陷入局部最优解的可能。但是轮盘赌选择的优 势在于全局地把握所有求过的染色体的情况，所有染色体都有机会( 虽然机会不 一样) 繁殖后代。而且，轮盘赌选择可以改进的空间较大，比如可以引入染色体 寿命的概念，这些方法都将极大地提高算法的效率。鉴于此，本文将采用的是轮 盘赌的选择算子。 3 6 交叉算子 交叉( c r o s s o v e r ) 通过概率性算法选择部分染色体两两交配，能最大限度地 提高对已有解信息的利用( e x p l o i t a t i o n ) 能力。算法对种群的每个染色体产生一 个 o ，1 】区间的浮点数，如果， p x 则参与交配，否则染色体直接被复制到下一 代。参与交配的染色体被两两配对，一般是按照被选择参与交配的顺序配对，比 如1 号对2 号，3 号对4 号，以此类推。交配的方法会根据具体优化的问题而有 很大的区别。 交配采用单点交叉，随机产生一个交叉的位置k ( k 是介于2 和n 1 间的整 第1 6 页 中山人学硕士学位论文 数) ，然后沿着这个位置把原来的染色体分成两部分，两个染色体依照前后的组 合生成新的两个染色体。比如两个染色体口= ( q ，a 2 ，t 2 k ，口m ，口- l ，口) 和 b = ( 岛，b e ，瓯，反书6 ，) ，交叉位置为k ，那么交叉后新的染色体为： 口= ( q ，口2 ，- l 6 - l ，“) b = ( 岛，b e ，反，口 + l ，a n - 1 口) 交叉操作能提高g a 利用( e x p l o i t a t i o n ) 己知解的能力，因为两个染色体通 过交叉能有效地利用它们已有的解空间内的基因片段，产生解空间内比较优秀的 新个体。两个三维染色体交配的解空间的拓扑结构如图3 4 所示，两个父代染色 体墨= 五，x 2 ，x 3 ) 和冯= y l ，y 2 ，y 3 ) 用图3 4 中黑色的点表示，它们交叉 后产生的解有可能是它们本身，也可能在其它6 个白色的点所在位置，但是交叉 产生的新的染色体的位置最多也只能在这个长方体的八个端点上，而且新的染色 体对必须是在这个长方体上、一个斜对角线的两个端点，如五和五、五和五 都是一对。 1x 4 图3 4 三维染色体交叉的解空间的拓扑结构 可以说控制交叉算子的关键参数是a ，每一代群体中交叉的染色体个数为 取木p o ps i z e 个，交叉的值一般取 0 4 ，0 9 9 之间，a 一般设得较大。如果a 过小 的话，算法对已有解的利用能力就会极低，导致种群适应度进化较慢，即算法收 敛过慢。在后面的章节将会讨论根据群体的状态动态调整a 的策略，以更好地 利用己有信息，提高算法的收敛速度。 第1 7 页 中山人学硕士学位论文 3 7 变异算子 变异算子( m u t a t eo p e r a t o r ) 保证了算法的探索能力( e x p l o r a t i o n ) ，让算法 向新的解空间搜索，避免算法陷入局部最优解。其中过早陷入局部最优解又称为 早熟。变异算子的控制参数为砌，算子对种群每个染色体的每个基因位都产生 一个【o ，1 】区间的浮点数，如果， 砌，则