（计算机软件与理论专业论文）基于遗传算法的分布式系统中任务调度.pdf

摘要 遗传算法是近年兴起的一种用于解决优化问题的并行寻优算法，已被用于分布 式系统的任务调度中。经研究表明遗传算法比启发式算法有较大的优越性。本文提 出了一利t 用广义遗传算法解决任务调度的方法，具体内容有： 1 设计了任务分布的问题模型，设计了一种新的编码方式，即“一维分离编码” 方式。其中，每个个体由左子串和右子串两部分构成。左子串描述任务分配的情况， 右子串描述任务的调度顺序。左、右子串因任务分配和任务排列的要求不同而执行 不同的杂交和变异操作，使搜索空间扩大到整个解空问上。此外，在任务调度中， 让上一代母体中具有较高适应值的染色体( 即最佳和次佳个体) 直接进入下代参 与进化，而不是通过轮盘赌的形式进入下一代，以加快算法的收敛过程。 2 设计了任务调度问题的数学模型和针对该调度问题的广义遗传算法的马尔可 夫链模型。 3 在单机系统中，利用v c + 十语言搭建了一个模拟局部任务调度的仿真系统l d 。 仿真结果表明，与在这一问题上常采用的二维编码的遗传算法相比，本算法能 得到更好的解；与不采用广义遗传算法而代之以精英策略的遗传算法相比，本算法 具有更快的收敛速度，具有较大的优越性，适合处理定规模的调度问题。 关键词：遗传算法，任务调度，马尔可夫链，广义遗传算法 a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i san e wp a r a l l e lo p t i m i z e da l g o r i t h mw h i c hc a nb eu s e dt os o l v e m a n yk i n d so fn p h a r dp r o b l e m s s o m er e s e a r c h e r sh a v eu s e dg ao ns c h e d u l i n g p r o b l e m sa n dt h i sa l g o r i t h mi st u r n e do u tt ob eb e t t e rt h a nh e u r i s t i ca l g o r i t h m i nt h i s p a p e rw ep u tf o r w a r da na l g o r i t h m t os o l v et a s k s c h e d u l i n gw i t hg e n e r a lg e n e t i c a l g o r i t h m 1 f i r s tw ed e s i g nm a t hm o d e lf o rt h et a s kd i s t r i b u t i o na n dp u tf o r w a r dan e wc o d i n g s c h e m en a m e d “o n ed i m c n s i o nd e c i m a l s e p a r a t e dc o d i n g ”e a c hc h r o m o s o m e i s c o m p o s e do fl e f ts t r i n ga n dr i g h ts t r i n g t h el e f td e s c r i b e st h ed i s t r i b u t i o no ft a s ka n dt h e r i g h td e s c r i b et h ee x e c u t i o ns e q u e n c eo ft a s k t h el e f ta n dr i g h te x e c u t ed i f f e r e n t l y b e c a u s et h ed i f f e r e n c e o ft a s ks c h e d u l i n gw h i c hc a ne x t e n dt h es e a r c ho fo p t i m i z e d a n s w e rt ot h ew h o l es p a c e b e s i d e st h em o r eo p t i m i z e dc h r o m o s o m ed i r e c t l ye n t e rt h e n e x tg e n e r a t i o nc a na c c e l e r a t et h ep r o c e s so fc o n v e r g e n c e 2 s e c o n dw ed e s i g nm a t hm o d e lf o rt h ea l g o r i t h mw ep r o p o s ea n dp r o v e dt h a ti tc a n r e a c ho p t i m i z e da n s w e rw i t hs t a n d a r dg e n e r i ca l g o r i t h ma n dg e n e r a l g e n e r i ca l g o r i t h m 3 t h i r dw eb u i l das i m u l a t e ds y s t e ml dw i t hv c + + s i m u l a t i n gl o c a lt a s ks c h e d u l i n g t h es i m u l a t e dr e s u l t ss h o wt h a to u ra l g o r i t h mo u t p e r f o r m st h ea l g o r i t h mu s i n gt w o d i m e n s i o n sc o d i n ga n dc a np r o d u c em u c hb e t t e rr e s u l t s b e s i d e s ，o u ra l g o r i t h mh a sf a s t e r c o n v e r g e n c es p e e dt h a ne l i t es e l e c tm e t h o d t h e c o n c l u s i o ni st h a to u ra l g o r i t h mi sm u c h b e t t e rt h a no t h e ra l g o r i t h m sa n dc a nb e u s e dt os o l v el a r g es c h e d u l i n gp r o b l e m s k e yw o r d s ：g e n e t i ca l g o r i t h m ，t a s ks c h e d u l i n g ，m a r k o vc h a i n s ，g e n e r a lg e n e t i c a l g o r i t h m 第一章绪论 1 1 引言 第一章绪论 二十世纪九十年代来，随着微型计算机功能的日益强大和高速局域网技术的发 展，分布式系统已成为计算机界中的研究热点。所谓分布式系统，就是通过高速网 络将许多处理机连接起来构成的一个计算机系统。作为网络一体化和并行处理分布 化的产物，分布式系统解决了系统透明性及处理机动态分配等问题，表现出强大的 生命力。 比较普遍的分布式系统的定义是：“分布式系统是一些独立的计算机的集合，但 在用户看来却是一台计算机”l lj 。作为网络一体化和并行处理分布化的产物，分布 式系统解决了系统透明性及处理机动态分配等问题，表现出了强大的生命力。它足 与传统的由单个c p u 、内存、外设和终端组成的集中式系统完全不同的。同时，计 算机结构在设计上产生了明显的变化，即从集中式单一处理机系统结构向“分布式” 数据处理的体系结构发展。分布式计算机系统已成为计算机领域中的研究热点。 在分布式系统中，任务分配问题一直是重要的研究课题之一。任务分配是在分 布式系统环境中，根据一定的调度规则和调度策略，把组成并行程序的一组任务按 照一定的执行时序分配到分布式系统的多个计算机接点上，以期获得较好的执行性 能。在分布式系统中，任务的求解过程大体分为四个步骤【2 j ： 任务分解：指把一个大任务划分为可并行执行的相关的子任务的过程。 任务调度：指将这些子任务分配到各个并行处理机上，并安排处理机上子任 务的执行次序的过程。 并行运算：指这些子任务在被分配的处理机上进行并行运算。 解的合成：指将子任务的运行结果合成为整个大任务的运行结果。 其中任务调度这一步骤对发挥系统的并行计算能力、提高系统吞吐量具有非常 重要的影响。良好的调度算法可以充分运用系统中每个处理机的计算能力，避免有 的处理机没有可执行的任务，而有的处理机待执行的任务排起了长队，致使总任务 的执行时间较长。寻找高效适用的任务调度方法是该研究领域的重要目标。近年来， 为了使分布式系统的性能得以提高，提出了许多分配与调度算法【” 。 1 2 任务分配与调度的常用算法 在对任务调度问题进行分析研究时，通常用有向无回路图f d a g d i r e c t e d 青岛大学硕士学位论文 a c y c l i cg r a p h ) 描述任务之间的约束关系。图中结点代表子任务，边代表子任务问的 依赖关系。由于分布式系统的任务调度问题是n p c 问题【2 】，己知可在多项式时间内 求得最优解的情况只有以下三种【2 】：d a g 是一个树，并行处理机同构且全连接， 忽略通信代价：d a g 是任意形状的图，并行处理机只有两个同构处理机，忽略 通信代价；d a g 图上的结点具有相同的计算代价，f 叫隔排序( i n t e r v a l o r d e r e d ) ，处 理机数目不限，忽略通信代价【3 】o 由于调度问题是n p c 问题，用枚举法耗时过长，难以求得最优解，以往人们常 使用一些启发式算法在多项式时间内找到近似最优解。近似最优解指不能确保是最 优解的解。 最常用的启发式算法是l i s t 调度算法n 在l j s t 调度中，首先给每个任务动态或 静态地分配个优先级，按照优先级将任务排成一列，然后从第一个任务开始，将 每个任务逐个分配到一个能使其开始执行时间最早的处理机。人们研究的焦点即是 如何确定任务的优先级，找到一个最优排列，使所有任务能够尽快完成”1 。启发 式算法在求得的解的质量和求解时间两者之问存在着相互制约：也就是说，以降低 解的最优性为代价，来换取求解时间的缩短。在解决规模较小的调度问题时，求解 的时间尚且可以接受，效果较好，但当问题规模较大时，不是由于时间复杂度较高、 运算的时间过长而导致无法求解，就是在可接受的时间内求到的解与最优解差距太 大【1 3 】。 与传统搜索算法不同，遗传算法采用进化的方式对目标空间进行随机搜索。它 将问题域中的可能解看作是群体的一个个体，并将每一个个体编码成符号串形式， 模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行类似生物遗传 学的操作( 选择，杂交和变异) ，根据预定的目标适应度函数对每个个体进行评价， 根据适者生存和优胜劣汰的进化规则，不断得到更优的群体，同时阻全局并行搜索 方式来搜索群体中的最优个体，求得满足要求的最优解。正是因为遗传算法在解决 大空间、非线性、全局寻优等复杂问题上独特的优越性，遗传算法目前已经在优化、 机器学习等领域得到了广泛的应用。 1 9 9 4 年，e d w i n 首先将遗传算法用于同构多处理机的任务调度【1 3 ，以后又有一 些学者紧随其后，进行了进一步的深入研究”2 “。根据任务调度问题的特点，采用 种二维显式排列的方法来表示d a g 图中的分配和调度情况，即每个处理机上所 有的任务排成一个列表，排列的顺序代表了各子任务的先后执行顺序。通过模拟实 验证明，与传统的l i s t 调度算法相比，遗传算法能在可接受的运算时间内得到更好 的解。 许多中外学者在算法中普遍采用二维编码方式，染色体形式并非基本遗传算法 使用的一维二进制编码，而是由二维类似矩阵的形式表示。这种编码形式虽然直观 第一章绪论 明了，但有很大的局限性。 首先，采用这种编码方式进行杂交运算时，要求杂交后生成的新个体仍然满足 同一处理机上子任务深度值非降的排列顺序，以确保生成的新个体是可行解。因此， 选择d a g 中同一深度值的点作为杂交点执行单点杂交。这样做，无法使搜索子空 问波及整个解空间。因为在同一处理机上，可能存在这样的情况：如果两个子任务 之间没有相互依赖关系，深度值高的子任务排在深度值低的子任务之前也能也是可 行解。当最优解恰好属于这种情况时，这种算法无疑是无论进化多少代都不可能找 到最优解的。虽然此后有很多针对如何定义深度值，来尽可能扩大搜索空间的研究 1 6 , 1 8 , 2 0 - 2 2 】，但这样做并不能保证搜索空间扩大到整个解空问。 其次，任务调度包括两个环节，一个环节是确定把子任务分配到哪一台处理机， 我们称为任务分配；一个环节是确定每一处理机上子任务的执行顺序，我们称为任 务排列。如果用二维矩阵形式编码，在进行杂交和变异时，一个结点位置的改变意 味着任务分配情况和排列情况同时做出了改变。分配与排列实质上是两个分离的过 程，如果同时做出改变，搜索解空间的跳跃跨度较大。 还有一些用于任务调度的遗传算法采用了一维编码方式，个体的形式就是所有 子任务的一个队列【1 5 , 1 7 , 1 9 。解码的方法是：从队列的第一个任务开始，任务逐个被 分配到能使其最早开始执行的处理机。遗传算法的目标是找寻一个最优的队列。由 于这种算法得到的结果只是一个调度序列，不指定任务分配到哪个处理机上，调度 序列对应的解需要像l i s t 算法那样，计算任务分配到哪个处理机上可以最早地获准 执行，所以复杂性较大。在遗传算法中，也就是用来描述个体与解之问映射的适应 值函数复杂性较大。由于在遗传算法的进化过程中，需要多次适应值函数的计算。 适应值函数的复杂度对遗传算法的复杂度有着最直接的影响，所以对适应值函数复 杂度的降低将大大提高算法的性能。 针对这种情况，有学者将l i s t 调度算法与遗传算法结合起来，来加快遗传算法 的收敛速度【1 ，减少计算时问。还有一些研究，对初始种群的选择作了改进，目的 也是加快算法的收敛速度【1 8 , 1 9j 。除了对编码形式进行的研究外，还有一些学者将对 遗传算法本身进行改进后应用于任务调度问题。如共同进化遗传算法1 2 “、混合遗传 算法【1 8 , 2 1 】以及自适应遗传算法在任务调度问题上的应用等等。这些改进的遗传算 法有些是对进化过程进行的改进，有些是对操作算予进行的改进，有些是对控制参 数进行的改进，但编码方式基本上是二维编码或一维编码。 1 3 本文所做的工作 本课题的主要任务是研究遗传算法的机理，探索一种较适合分布式系统任务调 青岛大学硕士学位论文 度的遗传算法，以便寻找全局最优解且具有较快的收敛速度。本课题的研究工作为： 1 建立了任务分布的数学模型，提出了一种新的编码方式，即“一维分离编码” 方式。其中，每个个体由左子串和右子串两部分构成。左子串描述任务分配的情况， 右子串描述任务的调度顺序。左、右子串因任务分f l l n 任务排列的要求不同而执行 不同的杂交和变异操作，使搜索空间扩大到整个解空间上。此外，将广义遗传算法 中的进化思想引入了任务调度中。让上一代母体中具有较高适应值的染色体( 即最 佳和次佳个体) 直接进入下一代参与进化，而不是通过轮盘赌的形式进入下一代。 这样一来，以加快算法的收敛过程。 2 建立了任务调度问题的数学模型和针对该调度问题的广义遗传算法的马尔可 夫链模型。 3 在单机系统中，利用v c 十+ 语言搭建了一个模拟局部任务调度的仿真系统l d 。 通过仿真实验证明，本文提出的编码方式和广义遗传算法与采用二维编码的遗 传算法相比，本算法能得到更好的解。与不采用广义遗传而代之以采用精英策略的 传统遗传算法相比，本算法具有更快的收敛速度。 1 4 内容安排 本文内容安排如下：第一章是绪论；第二章简要介绍分布式系统及其任务调度 问题：第三章讲述遗传算法的有关知识；第四章建立了r 。义遗传算法的数学模型， 证明其全局收敛性；第五章讲述了我们设计的用于任务调度问题的广义遗传算法； 第六章是总结与展望。 第二章分布式系统研究背景 2 1 概述 第二章分布式系统研究背景 分布式系统是二十世纪九十年代以来计算机领域的研究热点之。作为网络一 体化和并行处理分布化的产物，分布式系统解决了系统透明性及处理机动态分配等 问题，表现出了强大的生命力。一个被大家公认的分布式系统的定义是：“分布式系 统是一些独立的计算机的集合，但在用户看来却是一台计算机”【酬。 在硬件结构一h ，尽管所有的分布式系统都是山多个c p u 构成的，但可以用不同 的方法将硬件组织起来，形成不同的系统。按照体系结构划分，当前典型的分布式 系统可分为两种：共享存储多处理机、分布存储多计算机。如果结点间通过共用存 储器中的共享变量实现相互通信，就称为多处理机( m u l t i p r o c e s s o r s ) ；如果结点 问使用消息传递方式来实现相互通信，就称为多计算机( m u l t i c o m d u t e r s ) 1 5 】。 共享存储多处理机属于紧密耦合的分布式系统，采用共享主存通信。一个典型 的共享存储多处理机系统由m 个存储模块、p 个处理器和d 个i t o 通道组成，( 1 1 1 ，p ，d ) 的数日按情况而定。由于处理机与主存之间互连网络带宽有限，所以当处理机数增 多时，访问主存的冲突概率会加大，互连网络会成为系统性能的瓶颈。但由于是单 一地址空间，所以较易于编程。 分布存储多计算机属于松散福合的分布式系统，它的每个处理单元都是一个独 立性较强的节点，系由c p u 、本地存储器、i o 设备和消息传递通信接口所组成。由 于每个计算节点的本地存储器容量较大，所以运算时所需的绝大部分指令和数掘均 可取自本地存储器。当不同计算节点一h 的进程需要通信时，就可通过接口进行消息 交换。在有的松散耦合的多计算机系统中，其计算节点本身就是一台完整的计算机， 这样就演变成了现代的机群系统。这种松散性耦合结构易于扩展，但多地址空f 司却 使编程较困难。 分布式系统与集中式系统相比，有其自身的优点。分布式系统有较高的性能价 格比，它还可能具有任何价位上的大型机都无法达到的性能。随着计算机的发展， 其应用领域越来越广，其中许多应用本身就是分布式的。与集中式系统相比，分布 式系统能更好地处理分布式应用。分布式系统的另一个优点是它有更高的可靠性， 通过将任务交由多个机器共同承担，单个芯= 片的故障只会让一台机器停下来，而其 他的机器将继续工作。剥于一些关键性应用来说，例如控制核反应堆或飞机，使用 分布式系统来达到高可靠性是最主要的考虑因素，并且在负载增加时分布式系统较 集中系统更容易扩展。 青岛大学硕士学位论文 2 2 任务分配与调度问题 在分布式系统中，任务分配与调度是分布式系统中的- - + 重要环节，它对于发 挥各处理单元的作用，从整体上提高系统资源的利用率等具有非常重要的意义。 简单来说，任务分配与调度就是把组成并行程序的一组相关任务或构成工作负 载的一组相关作业，按照一定的执行时序分配到分布式系统的多个处理单元上，并 且安排好每计算节点上任务的执行次序，以期获得较好的系统执行性能。 对于一个任务分配与调度实例1 2 ，一组可并行执行的任务可以用一个有向无回 路图( d a g ，d i r e c t e da c y c l i cg r a p h ) 表示，图中结点代表子任务，边代表子任务 间的依赖关系，如图2 1 所示。 图2 1 六个子任务的d a g 在d a g 中，设g = ( t ，e ) 。其中t 为结点集，每个结点z 对应系统中的个任 务；e 为边集，( 正，t i ) e 表示只有在正执行结束后，将执行结果传递给丁，t 才 能开工。i 称为l 的前趋，l 称为i 的后继。用c ( i ，丁，) 表示i 与r ，间的通信代 价。 分配与调度的目标是通过合理地分配各任务到不同的处理单元上，并且安排好 每一处理单元上任务的执行顺序，而使总任务的执行时间最短。在图2 1 中，如果 用w 。表示正的执行时间，调度的目标是使最后个任务t 6 完成的时间最短。此时， 它的所有前趋任务已全部执行完毕。 近年来，人们对任务分配与调度算法进行了大量研究，设计了很多算法。在设 计算法时，设计者主要考虑了以下几方面的问题【1 7 , 1 8 1 ： 1 任务分配与调度的时机 根据任务分配与调度的时机不同，一般可分为静态调度、动态调度和混合调度。 静态调度是指在并行程序编译时，就决定每个任务分配的处理机及其执行顺序。这 经常用于任务图比较确定的情况下。动态调度是在并行程序运行过程中，根据当前 任务调度及系统执行情况，临时决定每个任务的处理机及其起始执行时刻。动态调 第二章分布式系统研究背景 度主要用于任务图不确定的情况，但不可避免地带来一些额外开销。混合调度是介 于静态调度和动态调度之间的一种调度方法。在编译时先静态调度一部分任务，剩 余部分则采用动态调度方法在系统运行过程中给它们分配处理机。 2 目标的实现要求 从目标的实现上看，分布式系统的任务分配与调度划分为最优调度和次优调度 两类。前者以系统的最优调度为目标，获取系统的最高并行度；后者则追求一种次 优调度，以用户要求的时限为标准，达到较高的并行度。因为任务分配与调度问题 是一个n p c 问题，没有在多项式时间内找到最优解的算法，所以通常采用启发式算 法，以得到问题的近似最优解。 3 紧迫性任务的响应问题 按照调度程序所执行的调度操作是否允许任务抢先执行，可分为抢占式调度和 非抢占式调度。如果一个任务一旦占有一个处理机，那么它就不能被中断执行，而 是必须一直运行完毕后才释放该处理机，这种情形即为非抢占式执行方式。由于抢 占执行方式所引起的环境切换会增加系统开销，所以一般情况下不采用。 4 任务迁移问题 根据任务是否允许迁移执行，任务调度可分为两大类：第一类是非迁移算法。 即当一个进程创建时就已决定好它应在的位置，一旦把它放在某台处理机上，它将 一直在那台处理机上运行直至完成。无论它所在的机器负载有多重，也无论有多少 其它的处理机空闲，它都不能移动。另一类是迁移分配算法，即使一个任务已经开 始运行，它也可以移动。这种迁移策略能更好地平衡负载，但实现起来非常复杂。 目前已经证明，任务分配与调度问题是n p c 问题【2 i ，因此，对于一般情况，人 们不得不采用启发式算法来求得近似最优解。启发式算法是基于直观或知识、经验 构造的算法，这样构造的算法可以在可接受的计算时间内寻找较好的解，但不一定 能保证解的最优性。也就是说，以降低解的精确性为代价，来换取计算h 寸l n j 的缩短。 这就促使人们不断地进行科学研究，设计出比已有算法计算时间复杂度更低、找到 的解更好的算法。 以往的大多数调度算法是基于1 i s t 调度的算法。l i s t 调度的基本思想是按照 结点的属性为每个结点指定优先级，按优先级高低生成一个调度序列。在此基础上 又出现了动态l i s t 调度算法【3 0 2 1 。动态调度算法在每次结点被分配后，都要重新计 算所有未被调度结点的优先级，来重新安排剩余结点的顺序。因此，执行算法需要 三个步骤：确定所有未被调度结点的优先级；选择具有最高优先级的结点进行 调度；将结点分配到使它的启动时间最早的处理机上。 决定优先级的方法有很多 4 , 2 6 】，如h l f ( h i g h e s tl e v e lf i r s t ) 、l p ( l o n g e s t p a t h ) 、l p t ( l o n g e s tp r o c e s s i n gt i m e ) 、c p ( c r i t i c a lp a t h ) 等。 青岛大学硕士学位论文 在静态调度中，并行任务的运行时间、通信关系以及处理单元的拓扑结构已知。 每个任务在执行前己静态地分配给特定的处理单元。而动态调度允许根据在任务执 行过程中进行任务迁移或重新分配。动态调度技术虽然可以取得较好的负载平衡效 果，但开销也很大。所以，如果静态调度技术有较好的负载平衡效果时，应尽量采 用静态调度技术。本文只研究静态调度，因此下面所说的调度均指静态调度。 随着遗传算法、神经网络、模拟退火等现代优化算法研究的逐渐兴起，用遗传 算法解决任务分配问题的研究也在进行，并且显示了强大的优越性 2 3 。 第三章遗传算法 第三章遗传算法 大自然是我们解决各种问题时获得灵感的源泉。几百年来，将生物界所提供的 答案应用于实际问题求解已被证明是一个成功的方法，并且形成一个专门的科学分 支一一仿生学( b i o n i c s ) 。我们知道，自然界所提供的答案是经过漫长的自适应过程一 演化过程而获得的结果。除了演化过程的最终结果，我们也可以利用这一过程本身 去解决一些较为复杂的问题。这样，我们不必非常明确地描述问题的全部特征，只 需要根据自然法则来产生新的更好解。遗传算法正是基于这种思想而发展起来的一 种通用的问题求解方法。 3 i 遗传算法简介 遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示 进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于它 采用种群的方式组织搜索，这使得它可以同时搜索解空间内的多个区域。而且用种 群组织搜索的方式使得遗传算法特别适合大规模并行。在赋予遗传算法自组织、自 适应、自学习等特征的同时，优胜劣汰的自然选择和简单的遗传操作使遗传算法具 有不受其搜索空间限制性条件( 如可微、连续、单峰等) 的约束及不需要其它辅助信 息f 如导数) 的特点。这些崭新的特点使得遗传算法不仅能获得较高的搜索效率而且 具有简单、易于操作和通用的特性，而这些特性正是遗传算法越来越受到人们青睐 的主要原因之一。 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 研究的历史比较短。2 0 世纪6 0 年代末期到 7 0 年代初期，主要由美国m i c h i g a n 大学的j o h nh o l l a n d 与其同事、学生们研究形成 了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模 拟生物进化的机制来构造人工系统的模型 3 4 ，”l 。随后经过3 0 余年的发展，取得了丰 硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热湖，计 算智能已成为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗 传算法受到广泛的关注。从1 9 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗传 算法会议，到1 9 9 7 年5 月i e e e 的( ( t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) 创刊， 遗传算法的研究渐趋成熟。目前，遗传算法已被成功应用在机器学习、过程控制、 经济预测、工程优化等领域。 遗传算法的基本思想模拟了自然界的生物进化过程。通常认为达尔文的自然选 择学说揭示了生物进化的内在规律，“适者生存，不适者被淘汰”是自然选择的中心 青岛大学硕士学位论文 思想。遗传算法用适应值来刻画个体适应环境的程度，适应值越高的个体越能适应 环境，生存下来的机率越大。生存下来的个体再经过配偶选择，繁殖出下一代。同 时，在繁殖的过程中某些细胞的基因会发生突变。那些导致生存能力提高的突变所 产生的新的基因片断，会经过很多代的进化逐步传给群体中的多数个体。这样，自 然界从群体中选出了优良的个体，并把他们的优点遗传给下一代。从总体上看，新 的一代适应自然界的能力得到了提高，群体得到了进化。现代细胞学和遗传学的研 究表明，遗传物质的主要载体是染色体，杂交和变异发生在作为生物体结构编码的 染色体上。表3 1 所示为生物遗传中的基本概念与遗传算法中的作用的对应表。 表3 1 生物遗传中的基本概念与遗传算法中的作用的对应表 生物遗传概念遗传算法中的作用 个体 染色体 基因 适应性 种群 杂交 变异 解 解的编码 编码中的某一分量 适应值函数的值 一组解，种群规模决定解的个数 通过杂交算子产生一组新解的过程 编码的某一分量发生变化的过程 3 2 标准遗传算法( s g a ) 通常称h o l l a n d 提出的遗传算法为标准遗传算法( s g a ，s t a n d a r dg e n e t i c a l g o r i t h m ) ，其流程图如下图所示： 图3 1s g a 流程图 算法描述如下： s t e p l ：生成初始种群。 s t e p 2 ：若满足终止条件转s t e p 5 。 s t e p 3 ：，0 ri = 1t o 种群规模d o 3 - 1 ：按照一定的杂交方法和杂交概率进行杂交。 3 2 ：按照一定的变异方法和变异概率进行变异。 第三章遗传算法 s t e p 4 ：计算个体适应值，按适应值进行选择产生新的下代种群 转s t e p 2 。 s t e p 5 ：将进化终止时种群中的最优个体作为最终解。 s t e p 6 ：结束。 算法执行时，先从由所有个体组成的个体空间中随机抽取一定数量的个体作为 初始种群，然后通过相继使用杂交、变异、选择三个遗传算子对初始群体进行操作， 形成新一代的种群。如此反复进化，直至满足终止条件。最后一代中适应值最大的 个体即是通过遗传算法计算出的最终解。标准遗传算法采用轮盘赌选择方法、随机 配对和单点杂交，同时，种群中允许相同个体存在。 例：设种群规模为4 ，算法在筇n 代结束，则如图3 2 所示，第n 代中适应值 函数最大的个体1 1 1 1 即是所得解。 初始种群第l 代第州 图3 2 一个遗传算法求解实例 需要说明的是：由于遗传算法是由选择、杂交、变异算子组成的循环往复的进 化过程，以往的研究有些规定一代从选择算子开始，有些规定从杂交算子开始，我 们选择后者。 3 3 遗传算法的主要参数 在遗传算法的实现过程中，主要涉及五个要素：编码方案、初始种群的设定、 适应值函数、遗传算子的设计和控制参数的设定。 1 编码方案 在编码方面，s g a 采用二进制0 , 1 编码方式，将问题的一个解表示成一个长度 为l 的二进制串，作为一个个体，l 称为链长。 青岛大学硕士学位论文 采用二进制编码的优点在于编码、解码操作简单，交叉、变异等遗传操作便于 实现。但缺点在于： ( 1 ) 相邻整数的二进制编码可能具有较大的h a m m i n g 距离。例如1 5 和1 6 的二 进制表示为0 1 1 1 1 和1 0 0 0 0 ，算法要从1 5 改进到1 6 必需改变所有的位，这将降低遗 传算子的搜索效率。二进制编码的这一缺点有时称为h a m m i n g 悬崖( h a m m i n g c l i f e s ) 。 ( 2 ) 二进制编码时，一般要先给出求解精度以确定串长，而精度确定后，就很 难在算法执行过程中进行调整，从而使算法缺乏微调( f i n e t u n i n g ) 的功能。若在算法 一开始就选取较高的精度，那么串长就很大，这样也将降低算法的效率。 ( 3 ) 在求解高维化问题时，二进制编码串将非常之长。从而使得算法的搜索效率 降低。 以上缺点使其不便于反映所求问题的特定知识。对于一些连贯函数的优化问题， 由于遗传算法的随机特性而使得其局部搜索能力较差，当链长较小时，可能达不到 精度要求；而链长较大时，虽然能提高精度，但却会使算法的搜索空问急剧扩大。 后来许多学者对遗传算法的编码方式进行了改进。 2 初始种群的设定 产生初始种群的方法通常有两种。一种是完全随机的方法产生，适合于对问题 的解无任何先验知识的情况；另一种是由某些先验知识转变为必须满足的一组要求， 然后在满足这些要求的解中随机选取样本。在任务调度问题中，产生初始种群的方 法即属于后者。 3 适应值函数 适应值函数的选取直接影响到遗传算法的收敛速度以及能否找到最优解，因为 遗传算法在进化搜索中基本不利用外部信息，仅以适应值函数为依据，利用种群中 每个个体的适应值来进行搜索。适应值函数设计要满足许多条件，如单值、连续、 非负、最大化等。因为适应值函数的复杂度是遗传算法复杂性的主要组成部分，所 以适应值函数的设计应尽可能简单，使计算的时间复杂度最小。 自然界中，个体的适应值即是它繁殖的能力，它将直接关系到其后代的数量。 在演化计算中，适应函数是用来区分群体中个体好坏的标准，是算法演化过程的驱 动力，是进行自然选择的唯一依据。改变种群内部结构的操作皆通过适应值加以控 制。 遗传算法中度量适应性的方法有很多种。可以用目标函数的形式给出，也可用 目标函数变换的方式来定义。在协同演化( c o e v o l u t i o n ) 时，适应值则通常由某一对 策与群体中相佐的对策进行抗衡的获利确定。个体在种群中的存活量和繁殖量也可 1 2 第三章遗传算法 以作为适应值的一种量，这种度量方式在人工生命的研究中使用。 下面是我们设计遗传算法时经常用到的两种适应性度量及其调节方法。 1 ) 原始适应函数 原始适应函数是问题求解目标的直接表示，通常采用问题的目标函数作为个体 的适应性度量。而对于很多非数值优化问题，我们也可以将其转化成求某个目标函 数的极值问题，如设计和训练神经网络时，我们可将网络的实际输出与期望输出之 差的平方和，作为问题的目标函数，则原问题成为寻找一个网络使该目标函数达到 最小。对于一个问题，定义原始适应函数的方法可能不止一种，选择时要尽量反映 问题本身整体的特性，而不能只追求片面的目标，这一点对用遗传算法求解非数值 问题时，尤为重要，而且往往也是较困难的。 2 ) 标准适应函数 因为原始适应函数反映问题的最初求解目标。因此会出现两种情形，一是极小 情形即原始适应值越小个体性能越好；另一种是极大化情形即原始适应值越大个体 性能越好。但是遗传算法中的某些选择策略( 如基于适应值比例的选择策略) 则要求 适应函数是非负的，而且适应值越大表明个体的性能越好。这时常常需要将原始适 应函数作一个适当的变换以转化成标准的度量方式，即皆化为极大化情形，并且适 应值非负。 目前，我们在设计遗传算法时，群体的规模一般都在几十至几百之间，与实际 物种的规模相差甚远。因此，个体繁殖数量的调节在遗传算法中就显得比较重要了。 如果群体中出现了超级个体，即该个体的适应值大大超过群体的平均适应值，则按 照适应值比例进行选择时，该个体很快就会在群体中占有绝对的比例。从而导致算 法较早地收敛到一个局部最优点，这种现象称为过早收敛( p r e m a t u r ec o n v e r g e n c e ) 。 又如在搜索过程的后期，虽然群体中存在足够的多样性，但群体的平均适应值可能 会接近群体的最优适应值。在这种情况下，群体中实际上己不存在竞争，从而搜索 目标也难以得到改善，这种现象我们称之为停滞现象( s t a g n a t i o n ) 基于上述原因，改变算法性能的方法之一是对适应值进行调节，即通过变换改 变原适应值问的比例关系，常用的比例变换有线性变换及指数函数变换等。 4 遗传算子的设计 遗传算法的进化依靠三个算子的操作：选择、杂交和变异。 ( 1 ) 选择算子 从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择的目的是为了从当 前群体中选出优良的个体，使他们有机会作为父代繁殖下一代子孙。判断个体优良 与否的标准是他们的适应值。如s g a 采用的轮盘赌选择法以及精英选择策略等【2 。 一童璺查堂塑圭堂垡笙兰 ( 2 ) 杂交算子 在自然界生物进化过程中起核心作用的是生物遗传基因的重组加上少量的变 异，因此，遗传算法中超核心怍用的是遗传操作中的杂交算子。杂交是遗传算法获 取新优良个体的最重要手段。所谓杂交是指把两个父代个体的部分结构加以替换重 组而生成新个体的操作。 s g a 采用的是单点杂交，分两步进行：首先对配对库( 经选择操作后形成的父 代群体) 中的个体进行随机配对；其次，在配对个体中随机设定个杂交点，配对 个体按杂交概率彼此交换杂交点后的部分信启、。如下图所示： 皴 圈 图3 1 单点杂交示意图 常见的杂交方式除单点杂交外还有多点杂交、均匀杂交等。 多点杂交是随机选择多个杂交点，在杂交点之间的基因问续地相互交换，产生 两个新的后代。多点杂交的思想源于控制个体特定行为的染色体表示信息的部分无 须包含于邻近的子串，多点杂交的破坏性可以促进解空间的搜索，避免过早收敛。 下图所示是两点杂交的示意图： 图3 2 单点杂交示意图 单点杂交和多点杂交的定义使得个体在杂交点处分成片段。 ( 3 ) 变异算子 变异是一个重要的遗传机制。如果没有变异，遗传过程经常收敛到局部最优解。 变异可以把搜索空间扩大到整个解空间。变异本身是一种局部随机搜索，它与选择、 杂交算子结合在一起，保证了遗传算法的有效性，使遗传算法具有全局搜索能力， 保持了种群的多样性，防止早熟。 5 控制参数的设定 耋 第三章遗传算法 遗传算法中的控制参数包括种群规模、进化终止条件、杂交概率和变异概率等。 这些参数对遗传算法的性能都有很重要的影响。一般来况，种群规模较大时可以同 时处理更多的解，因而容易找到最优解，其缺点是增加了每次迭代的时间。种群规 模一般选择2 0 1 0 0 间的偶数。 进化终止条件常常选择以下三种中的任一种： ( 1 ) 种群中个体的最大适应值超过预先设定值； ( 2 ) 种群中个体的平均适应值超过预先设定值； ( 3 ) 进化代数超过预先设定值。 杂交概率决定了杂交操作的频率。杂交频率越高，收敛速度越快，因此一般选 取较大的杂交概率，但太高的概率也可能导致过早收敛，所以一般选择在0 4 - 0 9 之问。变异概率的选取一般受种群规模、染色体链长等因素的影响，若选取高的变 异概率，虽然增加了样本模式的多样性，但可能会退化为随机搜索，一般选择在 0 0 5 0 2 之间。 这些参数都需要根据经验人为地设定。对于具体问题，衡量参数设置恰当与否， 要依据多次运行的收敛情况和解的质量来判断。如果调整参数难以有效地提高遗传 算法的性能，则往往需要借助剥遗传算法本身的改进。改进的手段可以是多方面的， 如适应值动态调整、引入自适应杂交概率和变异概率等。 3 4 广义遗传算法 1 9 9 8 年，董聪在大自然探索 2 2 】一刊上发表了文章“广义遗传算法”。该文 以m o r g a n 的基因理论及e l d r i d g e 与g o u l d 的间断平稳理论为依据，在融合了m a y r 的边缘物种形成理论和b e r t a l a n f f y 一般系统理论的基础上，对s g a 进行了改进，并 将其定义为广义遗传算法。广义遗传算法摈弃了传统遗传算法普遍采用的遍历搜索 策略，采用的是定向演化模式。它与标准遗传算法的区别主要体现在进化程序上。 在经典遗传算法的演化过程中，使用新的群体替换掉整个群体，即用后代替换 掉所有的父体。这样将可能使得某些优良的父体所具有的优良基因结构得不到繁殖， 而且由于杂交和变异算子的作用可能会破坏掉某些优质父体而产生较差的后代。考 虑经典遗传算法的这一缺点，文献【2 4 】中提出了稳态遗传算法的策略。其基本思想是： 在每一个演化代，通过遗传操作产生的新个体只替换掉当前群体中一部分较差的个 体，选择替换个体可以采用基于局部竞争的随机选取的方法，使得适应值越差的个 体被选择到的概率越大。这样，当前群体中的最优解将肯定被保留到下一代群体， 而另外一些较优的个体也能以较大的概率被保留。选择方法决定了所构造的遗传算 法是否收敛以及收敛点的特性。从自然界我们受到启示：遗传和变异的结果使一些个 青岛大学硕士学位论文 体的适应能力得以改善，而另外一些个体的适应能力则逐渐劣化。除此之外，相似 个休的生存会受到较强的相互抑制。因此，自然选择必将劣化的个体及相似个体中 的较弱者淘汰出局，能够进入下一轮生存竞争的是后代中的优胜者和父辈中的优良 者。从数学的角度讲，允许父辈中的优良者进入下一轮的竞争环境确保了最优解的 迭代稳定性，而将相似个体中的较弱者淘汰出局避免了重复繁衍和近亲杂交，使解 群在解空间的覆盖域扩大，增强了搜寻全局最优解的能力。 经典遗传算法是单种群进行演化且群体规模不进行变化，另外在演化过程中以 新种群替换掉整个群体，这一部分我们将讨论遗传算法在群体策略方面的变化。在 单种群演化中，处于初始化及控制参数的选取所带来的影响，很难达到群体多样性 与选择压力之间的有效平衡。这时算法或者出现过早收敛现象或者频繁地在非有效 区域进行搜索而导致搜索效率过低。解决该问题的一个办法便是实行多种群演化， 每个种群具有不同的初始化值和控制参数，还可以采取不同的选择策略以控制选择 压力，从而产生自己的最优模式。在各种群的演化过程中，一个种群内的个体可以 据某较小的概率迁移到另一种群，而且这种迁移不必在每一个演化代都进行，可以 问隔一定的代数，这样可使得各种群的最优模式有一定的生存期限，由于最优模式 可以从一个种群迁移到另一个种群，如果它在另一种群内也占有优势，则它将会在 种群内占有统治地位。这样，各种群最终都在某一最优领域内进行搜索以使算法收 敛到全局最优解，通过最优个体在群体问进行传播将使我们更容易控制群体的多样 性以达到选择压力之间的有效平衡。 简单来说，基本遗传算法的进化程序为： o 双亲选择一杂交一变异一生存选择一下一代种群 而广义遗传算法的进化程序为： 双亲选择一杂交一一家四口一四分之二生存选择一变异一一家四口一四分 之二生存选择一下一代种群 这里涉及三种选择方式：双亲选择、生存选择和四分之二生存选择，这三种选 择方式的区别如下： 双亲选择是不放回随机选择。也就是说，在种群中，首先以等概率随机选择出 两个个体组成需要进行杂交的母体，下一次再从剩余的个体中随机选择两个需要进 行杂交的母体，以此类推，直至所有个体都被选完。如果设种群规模为偶数n ，则 需选择n 2 次，形成n 2 对需要杂交的母体。 生存选择是一种概率选择方式。指对于变