（运筹学与控制论专业论文）一种求解资源受限项目调度问题的混合遗传算法.pdf

中文摘要 资源受限的项目调度问题广泛存在于建筑工程、软件开发、飞机及轮船制造 等单件或小批量生产方式的企业中。在理论上，该问题属于n p - h a r d 问题，一直 吸引着国内外众多学者的研究和关注，提出了许多求解该问题的优化算法，概括 起来可分为精确算法和启发式算法。由于精确算法的求解时间呈指数增长，无法 处理大规模问题。相反，启发式算法在计算大规模的问题时能在合适的时间里得 出令人满意的计算结果，尤其是启发式算法中的遗传算法，作为种全局优化搜 索算法，因其简单易用，对很多优化问题能够得到令人满意的解，已在科学研究 和工程最优化领域中得到广泛应用。 本文提出一种新的遗传算法，该算法的编码方式为工序优先权数的拓扑排 序，解码方式采用了串行调度产生方案。算法的进化过程如下： 1 采用新的选择策略，使得每代中的优良个体的基因编码不会因为交叉操作 和变异操作所破坏。 2 本文采用了峰交叉算子f 4 0 】，使得算法在搜索迭代过程中对个体的优良“基 因片段”进行保护，不会因为交叉和变异操作算子所破坏。 3 在变异操作中，采用把少量随机产生的新个体直接加入种群中，代替个体 中单个基因发生变异，保持种群个体的多样性。 4 在每代种群的开始，采用向前向后排序搜索算法对种群个体进行局部搜 索，极大的提高了算法的搜索质量。 选用标准数据库p s p l i b 中的1 5 6 0 个例子对该算法进行测试，数值试验结果 表明该算法是有效的。 关键词。遗传算法拓扑排序精英解选择峰交叉 a bs t r a c t t h ea p p l i c a t i o n so fr e s o u r c e c o n s t r a i n e dp r o j e c ts c h e d u l i n gp r o b l e m ( r c p s p ) c a l lb ef o u n di nc o n s t r u c t i o n , s o f t w a r ed e v e l o p m e n t ，a i r c r a f ta n ds h i pm a n u f a c t u r i n g a n do t h e ro l l e p i e c eo rs t r ol lb a t c hp r o d u c ti o no ft h ee n t e r p r i s e i nt h e o r y ，t h ep r o b l e m i sn p - h a r dp r o b l e ma n dh a sa t t r a c t e dm a n ys c h o l a r sb o t ha th o m ea n da b r o a d t h e r e a r ean u m b e ro fo p t i m i z a t i o na l g o r i t h m sf o rs o l v i n gt h ep r o b l e m , w h i c hc a nb e g r o u p e di n we x a c ta l g o r i t h m sa n dh e u r i s ti ca l g o ri t h m s s i n c et h ec o m p u t a t i o nt i m eo f e x a c ta l g o r i t h m sg r o w se x p o n e n t i a l l y ，t h e ya r er i o tu s e dt od e a lw i t hl a r g e - s c a l e p r o b l e m s o n t h e c o n t r a r y , t h eh e u r i s t i ca l g o r i t h mf o rd e a l i n gw i t hl a r g e s c a l e p r o b l e mc a nd r a was a t i s f a c t o r yr e s u l ta tt h ef i g h tt i m e ，e s p e c i a l l yt h em e t a h e u r i s t i c s g e m t i ca l g o r i t h m , a sag l o b a lo p t i m i z a t i o ns e a r c ha l g o r i t h m , c a nf i n das a t i s f a c t o r y s o l u t i o nf o rm a n yo p t i m i z a t i o np r o b l e m s i th a sb e e nw i d e l yu s e da ts c i e n t i f i c r e s e a r c ha n de n g i n e e ri n gf i el d t h i sp a p e rp r e s e n t san e wg e n e t i ca l g o r i t h mf o rt h er c p s pw i t hat o p o b g i c a l o r d e rr e p r e s e n t a t i o n d e c o d i n gm e t h o d sh a v ea d o p t e das e r i a lp r o g r a ms c h e d u l i n g t h ee v o l u t i o no fg e n e t i ca l g o r i t h mi sa sf o i b w s ： 1 an e ws e l e c t i o ns t r a t e g yi se m p l o y e dt om a k et h eg e n ee n c o di n go ft h eg o o d i n d i v i du a le a c hg e n e r a t i o nn o tb ed a m a g e db yc r o s sa n dm u t a t i o no p e m t i o r t 2 t h ep e a kc r o s s o v e ro p e r a t o ri s d e s i g n e d ，w h i c hw i l lp r o t e c tt h ef m e g e n e f r a g m e n t s ”o fi n d i v i d u a l sf r o md a m a g i n gb yc r o s s o v e ra n dm u t a t i o no p e r a t o r si nt h e s e a r c hp r o c e s s 3 i nt h em u t a t i o np r o c e s s ，w ep u tas m a l ln u m b e ro fr a n d o m l yg e n e r a t e dn e w i n d i v i du a l s i n t o t h e p o p u l a t i o nd i r e c t l y , i n s t e a d o fi n d i v i du a lm u t a t i o ni nt h e o c c u r r e n c eo f as i n g l eg e n et om ai n t ai nt h ed i v e r s i t yo fi n d i v i du a lp o p u l a t i o n 4 int h e b e g i n n i n g o fe a c h g e n e r a t i o np o p u l a t i o n t h e f o r w a r d - b a c k w a r d s c h e d u l i n gm e t h o d si s u s e da sab c a ls e a r c hp r o c e d u r e ，w h i c hg r e a t l yi m p r o v e dt h e q u a l i t yo ft h es e a r c ha l g o ri t h m t h ep e r f o r m a n c ee v a l u a t i o nd o n e0 1 1t h e15 6 0b e n c h r m r ki n s t a n c e ss h o w st h a t o u ra l g o ri t h mi se f f e c t i v e k e y w o r d s ：g e n e t i ca l g o r i t h m s ；t o p o l o g i c ai o r d e r ；c h o i c eo fe l i t es o l u t i o n s p e a kc r o s s o v e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁洼盘堂或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者弛张嘎u 签字吼吖年6 月日 学位论文版权使用授权书 本学位论文作者完全了解 丕盗盘茔 有关保留、使用学位论文的规定。特 授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并 采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家 有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：i 长咯重导师签名：至宏 签字隰咔月日 签字吼加，年6 月一日 1 1 遗传算法简介 第一章绪论 遗传算法( g e n e t i ca l g o r i t h m , g a s ) 是模拟生物在自然环境中的遗传和进化过 程而形成的一种自适应全局搜索算法。它最早是由美国m i c h i g a n 大学的h o l l a n d 教授提出，起源于6 0 年代对自然和人工自适应系统的研究【t 】。h o l l a n d 创建的遗 传算法是利用某种编码技术作用于所谓的染色体的二进制数串，其基本思想是模 拟由这些串组成的群体的进化过程。遗传算法通过有组织但是随机的交换来重新 组合那些适应性好的串，在每一代中，利用上一代编码中适应性好的片段来产生 一个新的串的群体；作为额外添加，偶尔也要在编码中尝试用新的位和段来替换 原来的部分。它可以利用已有的信息来搜索那些有希望改善解的质量的串结构。 遗传算法通过作用于染色体上的基因，寻求好的染色体来求解问题。与自然 界相似，遗传算法对求解问题的本身一无所知，它需要的仅是对算法所产生的每 个染色体进行评价，并基于适应值的大小来选择染色体，使得适应值大的染色体 比适应值小的染色体有更多的繁殖机会。遗传算法通过模拟达尔文“优胜劣汰、 适者生存”的原理及利好的结构；通过模拟孟德尔遗传变异理论在迭代过程中保 持已有的结构，同时寻找更好的结构。 7 0 年代d e j o n g 基于遗传算法的思想在计算机上进行了大量的纯数值函数优 化计算实验【2 】。在一系列研究工作的基础上，8 0 年代由g o i d b e r g 进行归纳总结， 形成了遗传算法的基础框架【3 】。 随着经济、科技和社会的不断发展，人们遇到的各种问题越来越复杂，迫 切的需要寻找一种更好的求解方法。遗传算法作为一种有效的全局搜索方法，从 产生至今不断的扩展应用领域，比如工程设计、制造业、人工智能、计算机科学、 生物工程、自动控制、社会科学、商业和金融等，同时应用实践也促进了遗传算 法的不断地发展和完善。 1 2 资源受限的项目调度问题 资源受限的项目调度问题( r c p s p ) 是典型的组合优化问题【4 j ，广泛地存在 于建筑工程、机械制造、计算机系统安装、大型设备的修理以及电视台、广播电 台的调度等项目中有着广泛的应用，在理论上，它是一个富有挑战性的n p - h a r d 问题【5 6 1 ，其基本内容可描述为：在一个( 或多个) 项目中，包含着很多相互关联( 满 足紧前关系) 的工作，每项工作的完成需要一定数量的资源并有一定的工期，在 项目的每一个阶段都可能有多个工作竞争同种有限的资源，问题是如何分配这 些资源才能实现最优的管理目标? 这些目标可能是：项目的工期最短，项目拖期 最少，项目拖期惩罚最小，项目的净收益最大等。 1 3 本文所做的工作及安排 本文研究了的是遗传算法求解资源受限项目调度问题并在参考了大量现有 的算法的基础上，设计了求解r c p s p 问题的新的遗传算法。用标准问题集p s p l i b 中的1 5 6 0 例子进行了数值试验，并与文献中的结果进行比较，试验结果表明我们 所提出的算法是有效的。本文的框架安排如下： 第二章是遗传算法的基本原理的介绍，包括遗传算法的基本术语、基本操作、 算法的收敛性和应用，其中介绍了一些重要的定义和定理。 第三章介绍了资源受限的项目调度问题，主要介绍了r c p s p 问题和研究现 状，对现有的算法做了重点叙述，尤其是启发式算法中的智能优化算法。 第四章是本文的重点，分两部分，第一部分详细地介绍了新遗传算法的特点， 从编码方式、选择操作、峰交叉操作和变异操作以及整个流程；第二部分是数值 计算和实验分析。 第五章是结束语，全文的总结。 第二章遗传算法的基本原理 电子计算机问世以来，生物模拟便构成了计算机科学的一个组成部分。其目 的之一便是从研究生物系统出发，探索产生基本认知行为的微观机理，然后设计 具有生物智能的机器或模拟系统以解决复杂问题。如遗传算法、神经网络和细胞 自动机等都是从不同角度模拟生物系统而发展起来的研究方向。 遗传算法( g e n e t i ca l g o r i t h m , g a s ) 是一种模拟自然界生物进化过程的全局随 机搜索算法，由美国m i c h i g a n 大学的h o l l a n d 教授于6 0 年代首先提出。它将计 算机科学与进化论的思想结合起来，依据达尔文“优胜劣汰，适者生存”的原则， 通过模拟自然界中生物群体由低级到高级，由简单到复杂的生物进化过程，最终 逐渐逼近问题的最优解或准最优解。遗传算法作为一种有效的全局搜索方法，因 具有较好的普遍适用性、易扩充性和有很高的并行性等优点而得到广泛的应用。 2 1 遗传算法的基本术语 由于遗传算法研究与应用尚在不断发展中，有关术语的应用尚未完全取得统 一。为了在下面研究中做到准确、清晰、规范地描述，本文中采用的术语及其含 义解释如下： 个体( i n d i v i d u a l ) ：g a 所处理的基本对象、结构。 群体( p o p u h t b n ) ：个体的集合。 位串( b i ts t r i n g ) ：个体的表示形式。对应于遗传学中的染色体。 基因( g e m ) ：位串中的元素，表示不同的特征。对应于生物学中的遗传物 质单位，以d n a 序列形式把遗传信息译成编码。 基因型( 寥t y p e ) ：也称遗传型，指用基因组定义遗传特征和表现。对应 于g a 中的位串。 表现型( p i l e n o t y p e ) ：生物体的基因型在特定环境下的表现特性。对应于g a 中的位串解码后的参数。 基因位( 1 0 c u s ) ：某一基因在染色体中的位置。 等位基因( a l l e l e ) ：表示基因的特征值，即相同基因位的基因取值。 适应值( f i t n e s s ) ：某一个体对于环境的适应程度，或者在环境压力下的生存 能力，取决于遗传特性。 复制或选择( r e p r o d u c t i o no rs e l e c t i o n ) ：在有限资源空间上的排他性竞争。 交叉或重组( c r o s s o v e ro rr e c o m b i n a t i o n ) ：一级位串或者染色体上对应基因 段的交换。 变异( m u t a t i o n ) ：位串或染色体水平上的基因变化，可以遗传给子代个体。 遗传( h e r e d i t y ) ：父代个体通过有性方式向子代个体的特征传递过程。 编码( c o d i n g ) ：把问题空间中的参数转换成遗传空间中的个体卸从表现 型到基因型的转换。 解码( d e c o d i n g ) ：编码的相反操作。即从基因型到表现型的转换。 2 2 遗传算法的基本操作 遗传算法悬一群体体型操作，该操作以群体中的所有个体为对象。选择 ( 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 ) 是遗传算法的三个主要操作 算子它们构成了所谓的遗传操作，使避传算法具有了其它传统方法所没有的特 性。遗传算法的基本流程如下圉所示： 工 图2 - l 遗传算法基本流程图 遗传算法是包含如下些要素的集合体：( ”参数编码( 2 ) 初始群体的设 定( 3 ) 适应值函数的设计( 4 ) 遗传操作设计( 5 ) 控制参数的设定( 主要是 指群体大小和使用遗传操作的交叉概率、变异概率等) ，( 6 ) 算法终止法剐的确 定。这六个要素构成了遗传算法的核心内容。 2 2 1 参数编码 按照遗传算法的工作流程，隶解时必须在目标问题实际表示翔遗传算法的染 色体间建立联系，即确定编码和解码运算。 由于遗传算法计算的鲁棒性，它对编码的要求并不苛刻。实际上，大多数问 题都采用h o l l a n d 建议的二进制编码设计，因为它最为实用并符合d ej o n g 的编 码原理 2 , 1 9 , 2 0 。然而，在很多情况下，编码形式也就决定了交叉操作，编码问题 往往被称作编码一交叉问题。因此，作为遗传算法流程中第一步的编码技术是一 个值得认真研究的问题，很多专家提出了各种编码方法。 非二进制编码中具有代表性的是十进制编码方案 2 1 1 和实数编码方案 3 1 。在 采用g a 求解b p 类问题时【3 22 1 ，用序列编码更为合理、自然。由此可见非二进 制编码往往结合问题的具体形式，一方面可简化编码解码过程，另一方面可以在 遗传操作中采用非传统操作算子，或者与其它搜索算法相结合。 2 2 2 初始化群体 遗传算法是群体性的操作，因此必须具备一个由若干初始解构成的初始群 体。初始群体中的个体一般是随机产生的。群体规模n 越大，群体中个体的多样 性越高，g a 搜索的质量可以得到改进，但是计算量也随之增加：群体规模太小， 则可能产生早熟收敛。因此群体规模不宜太大也不宜太小。在不具有关于问题解 空间的先验知识的情况下，很难判定最优解的数量及其在可行解空间中的分布情 况。因此我们往往希望在问题解空间均匀采样，随机生成一定数目的个体( 为群 体规模的2 倍) ，然后从中挑出较好的个体构成初始群体。 2 2 3 适应值函数 遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则，必 须对个体位串的适应性进行评价。因此，适应函数( f i t n e s sf u n c t i o n ) 就构成了 个体的生存环境。根据个体的适应值，就可决定它在此环境下的生存能力。一般 来说，好的染色体位串结构具有比较高的适应函数值，即可以获得较高的评价， 具有较强的生存能力。 由于适应值是群体中个体生存机会选择的惟一确定性指标，所以适应函数的 形式直接决定着群体的进化行为。为了能够直接将适应函数与群体中的个体优劣 度量相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大 越好。 目前遗传算法中常用的适应值函数有以下几种：按比例的适应值分配；基于 排序的适应值分配；等机会变换；非单调适应值变换。需要注意的是，只有对整 个群体的目标函数，才能计算出经过变换后的适应值，对单个个体计算适应值是 没有意义的。 茸z ”自 m * h 日n自j b ”“ 臣亘固 互困 臣亘圈 至丑 l； 厂忑而司厂磊磊i ； 图2 2 计算适应值躅 2 2 4 遗传算子 标准遗传算法的操作算子一般都包括选择、交叉、变异三种基本形式，它们 构成了遗传算法具备强大搜索能力的棱心。 ( i ) 选择( 复制) 选择即从当前群体中选择适应值高的个体以形成下一代群体的过程。发展各 种选择算子的目的是为了避免基因缺失。提高全局收敛性和效率。目前常用的 选择有：适应值比倒选择、排序进择、联赛选择、稳态选择、随机遍历选择和精 英选择策略扭i 。 只是从当前群体中选择较好的个体形成交配池，其本身并投有产生新的个 体。 ( 2 ) 交叉( 重组) g a 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的 优良基园遗传给下一代个体，井生成包古更多基因结构的新个体。交叉操作一般 分为以下三个步骤；首先从交配池中随机选出要变配的一对个体，然后根据位串 长度l ，在要交配的一对个体中分别随机选取【1 z 一1 j 的一个或多个整数k 作为 交叉位置：最后根据交叉概率实施交叉操作相互交换交叉位置中的内容，从而 形成新的一对个体。 采用二进制编码、实数编码和自然数编码所用的交叉策略不一样，目前通常 使用的遗传算子包括适用于二进制编码的一点交叉、两点交叉、多点交叉、一致 交叉；适用于自然数编码的部分匹配交叉、顺序交叉、圈交叉和启发式交叉和适 用于实数编码的算术交叉等。 ( 3 ) 蔓 在群体进化的整个过程中，交叉操作是主要的基因重组和群体更选的手段 变异操作的作用是第二位的，仅仅充当背景性的角色。但变异却是不可或缺的。 当交叉算子产生的后代的适应值不再比前辈好又未达到最优解，就会产生成熟前 收敛或早熟收敛，发生这种情况的根源是发生了有效基因缺失，这时，为了克服 这种情况，只有信赖于变异。一方面，变异算子可以使群体进化过程中丢失的等 位基因信息得以恢复，以保持群体中的个体差异性，防止发生成熟前收敛；另一 方面，当群体规模较大时，在交叉操作基础上引入适度的变异，也能够提高遗传 算法的局部搜索效率。 变异操作模拟自然界生物体进化中的突变现象，从而改变染色体的结构和物 理性状。常规变异的效果是不明显又很慢的，目前发展的主要变异算子有：基于 二进制编码的常规位变异、有效基因变异、自适应有效基因变异、概率自调整变 异和基于实数编码的均匀变异、非均匀变异、零变异等。 另外，许多高级遗传算子得到了研究，如显性算子、倒位算子、分离和易位 牌子、增加和缺失算子以及迁移算子等。这些遗传算子来源于群体遗传学，目前 应用尚少，机理及其表现有待进一步的深入研究。 2 2 5 控制参数和选择 在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。主要 参数包括群体规模刀，交叉概率，以及变异概率。许多学者进行了大量实验 研究，给出了最优参数建议( d ej o n 9 1 2 】，g r e f e n s t e t t e l 2 3 】，s c h a f f e r t 2 4 1 ) 。 ( 1 ) 群体规模尼：大群体含有较多模式，为遗传算法提供了足够的模式采 样容量，可以改进g a 搜索的质量，防止成熟前收敛。但大群体增加了个体适应 性评价的计算量，从而使收敛速度降低。一般情况下专家建议n = 2 0 - 2 0 0 。 ( 2 ) 交叉概率历：交叉概率控制着交叉算子的应用频率，交叉概率越高， 群体中新结构的引入越快，已获得的优良基因结构的丢失速度也相应升高，而交 叉概率太低则可能导致搜索阻滞，一般取= o 6 0 1 0 0 。 ( 3 ) 变异概率。：变异操作是保持群体多样性的有效手段，变异概率太小， 可能使某些基因位过早丢失的信息无法恢复：而变异概率过高，则遗传搜索将变 成随机搜索，一般取。= 0 0 0 5 0 0 1 。 实际上，上述参数与问题的类型有着直接的关系，不存在一组适用于所有问 题的最佳参数值，在实际问题中应根据需要改变上述参数值以获得最佳结果。 2 2 6 终止循环的条件 由于遗传算法具有较大的随机性，这里根据几条启发式的终止条件 2 5 1 ，给 定参数s 、a 、x 、y 和四种终止条件。 a 计算每代群体中染色体适应值的方差，当方差小于时，可认为算法收敛； b 计算每代群体适应值均值，当均值与最佳染色体适应值的比值大于a 时， 7 可认为算法收敛： c 记录每代最佳染色体，若某染色体连续保持最佳达到x 代，可终止算法。 d 由于计算时间和机器容量都是有限的，代数不能无限长，故迭代次数达到 规定值y 时，可停止计算。 2 3 遗传算法的收敛性 遗传算法的基础理论主要以收敛性分析为主。对算法收敛性的分析主要分为 基于随机过程的研究和机遇模式理论的研究。这里简要给出基于随机过程的收敛 定理。 在遗传算法的进化过程中，种群一代接一代的变化过程作为一个随机过程来 加以考察，并可利用m a r k o v 链来对进化过程进行理论分析，从而得到遗传算法 收敛性方面的重要结论。 这里先定义几个随机过程中的术语。 定义阑1 设随机过程 朋功，力谚只能取可列个值，= ， ，并且满足条 件：对于任意刀及乇，j i ，如果只小0 ) = 石，川1 ) = ，仞) = ) 0 有 眉拟刀+ i ) = ，- 肿，i x ( 0 ) = 矗，x 0 ) = ，l ，z ( 刀) = 厶 = 尸白+ 1 ) = ，。陟仞) = ，。) 则称 川刀) ，n 20 为时间状态离散的m a r k o v 链，简称m a r k o v 链。 定义2 称群以刀) = 1 拟功= 刀 嘲为m a r k o v 连的转移矩阵，记为 异( 功。 易( 功具有下面两条性质：( 1 ) 乃( 功o ；( 2 ) 。易( 所，功0 = l 定义3 对于m a r k o v 链，如果 乞( 惕m + 1 ) = 只坝r e + 1 ) = 1 坝功= 矗= 尸，( 乃 即从状态i 出发转移到状态的转移概率与时间起点所无关，则称这类 m a r k o v 链为其次m a r k o v 链。 定义4 对于其次m a r k o v 连，称乞为一步转移概率，全部乞( 乃所组成 的一个矩阵尸= ( 只) 称为一步转移概率矩阵，或称为随机矩阵。 为了简单起见，我们只对基本遗传算法的收敛性进行分析。基本遗传算法可 描述为一个齐次的m a r k o v 链z = 只力，0 ) ，因为基本遗传算法的选择、交叉、 变异操作都是独立随机进行的，新群体仅与其父代群体及遗传算子有关，而与其 父代群体之前的各代群体无关，即群体无后效性，并且各代群体之间的转移概率 与时间起点无关。 定理【2 7 1 l 基本遗传算法收敛于最优解的概率小于l 。 证明。将群体的各种可能状态分解为包括最优个体的状态厶和不包括最优 个体的状态： = 厶u ( 厶n 厶= ) ( 2 - 1 ) 需要证明尸进入的稳定概率小于l 。 用反证法，假设基本遗传算法能收敛于最优解的概率等于l ，则进入状态 的稳定概率等于0 ，即 l i m 眉z = 0 ( 2 - 2 ) 在某些遗传算法的进化过程中，群体从某一状态，经过选择交叉和变异算 子的连续作用而转变为状态。这三种遗传算子的转移概率分别是易，f ， ，他们可分别构成相应的随机矩阵j = s , ) ，f = 巳) a s = ) ，则遗传算 法的群体状态变换矩阵为：刀= 剃= ，：，) 。 由于量c 都是随机矩阵，并且= 彤) ( 1 一以) 1 - 州力( 俄刀为状 态，和状态之间的海明距离) ，容易得证厶 0 ，即彳是正定的。 在，时刻，群体是状态的概率e ( 力为： e ( ，) = 尸( o ) 衫 ( ，= o ，l ，2 ，。) ( 2 3 ) 由齐次m a r k o v 链的性质可知，尸( ，) 的稳定概率的分布和初始概率分布无 关，即有 乡( ) = 尸( o o ) 乃 0 ( 2 - 4 ) 注意到上式中的状态i ，即也可能是中的一个状态，从而可知 l i l l l 只尸厶) 0 ( 2 - 5 ) 上式与式( 2 - 2 ) 的假设相矛盾，从而定理得证。 显然，对于这种收敛于最优解的概率小于l 的基本遗传算法，其应用可靠性 就值得怀疑。从理论上来说，仍希望遗传算法能够保证收敛于最优解，这就需要 对基本遗传算法进行改进，如果使用精英保留的策略就可以达到这个要求。 定理2t z s ) 用精英保留的策略的遗传算法能收敛于最优解的概率为l 证明i 考察这样所组成的个体集合，( ，) = ( “力，只力) ，其中硝，) 是当前群体 中适应值最高的个体。这一个体集合的状态转移规则是： ( 1 ) 根据定理l 中的状态转移矩阵尼由爿力产生只，+ 1 ) 。 ( 2 ) 彳，+ 1 ) 是从上一代群体中和本代群体中挑选出的一个具有最大适应值 的个体，即4 ，+ 1 ) = m a x 钡，) ，4 ( , 4 0 是群体只，+ 1 ) 中适应值最高的个体) ，这 样所构造出的随机过程，( ，) ，0 仍然是一个齐次m a r k o v 链，即有 ，( 力= 尸( 0 _ ) ( ) 7 假设个体集合状态中包括有最优解的状态为厶，则该随机过程的状态转移概 率为： 0(vie厶夥so)(2-6) 劈= 0 ( v ，夥萑i o ) ( 2 - 7 ) 即从任何状态向含有最优解的状态转移的概率大于0 ，而从含有最优解的状 态向不含最优解的状态转移的概率等于0 。此时，对于v i e 厶夥诺厶，下式都成 立： 一o ( _ o o ) ( 2 - 8 ) 矿( o o ) = o ( j az o ) ( 2 9 ) 即个体集合收敛于不含有最优解的状态的概率为0 。换言之，算法总能以概 率1 搜索到最优解。 2 4 遗传算法的基本特性 ( 1 ) 自组织、自适应性【2 9 】：应用遗传算法求解问题时，在编码方案、适应 值函数及遗传算子确定后，算法将利用进化过程中获得的信息进行组织搜索。基 于自然的选择策略为：适者生存。因此适应值大的个体具有较高的生存概率，再 通过交叉和基因突变等遗传操作，就可能产生更适应环境的后代。遗传算法的这 种自组织、自适应特征，使它具有能根据进化过程中解的变化来自动发现解空间 的特性和规律的能力。 ( 2 ) 并行性1 3 0 ：遗传算法的本质并行性表现在两个方面：一是遗传计算是 内在并行的，即其可让一定数量的计算机各自进行独立群体的遗传计算，等运算 结束后才进行通信比较，选取最优个体：二是遗传算法的内含并行性。由于遗传 算法采用群体的方式组织搜索，因而可同时搜索解空间的多个区域，并相互交流 信息。使用这种搜索方式，虽然每次只执行与群体规模成比例的计算，但本 质上己进行了玖) 次有效搜索，这就使遗传算法能以较少的计算获得较大的收 益。 ( 3 ) 过程性：遗传计算通过自然选择和遗传操作等自组织行为来增强群体 的适应性。在这个过程中，算法本身无法判断个体处在解空间的位置，因此需要 人为干预( 即事先确定终止准则) 才能终止。 ( 4 ) 多解性：遗传算法的另一基本特征是采用群体的方式组织搜索。它从 多个点出发，通过这些点的内部结构的调整和重组来形成新的点，因而每次都将 提供多个近似解。 ( 5 ) 不确定性：遗传算法的不确定性是伴随其随机性而来的。遗传算法的 主要步骤都含有随机因素。从而在算法的进化过程中，事件发生与否带有很大的 不确定性。 ( 6 ) 非定向性：自然选择和生殖过程这种非定向机制是遗传算法的关键。 它没有确定的迭代方程，而是用调整群体内部结构的方法来增强其对环境的适应 性，以使得问题得到解决。 ( 7 ) 内在学习性：遗传算法的个体学习方式是通过改变个体的基因结构来 提高自己的适应值。 ( 8 ) 统计性：遗传计算的群体方式决定它是一个统计过程。在每一代，都 要进行统计，以确定个体的优劣并推动进化的进行。 ( 9 ) 稳健性：由于遗传算法利用个体的适应值推动群体的进化，而不管求 解问题本身的结构特性，因而在用遗传算法求解不同问题时，只需要设计相应的 适应值函数，而无须修改算法的其它部分。同时，因为遗传算法具有自适应性， 算法在效率和利益之间的权衡使得它能适用于不同的环境并取得较好的效果。 ( 1 0 ) 整体优化性：遗传算法能同时在解空间的多个区域内进行搜索，并且 能以较大的概率跳出局部最优，以找出全局最优解。 2 5 遗传算法的应用 遗传算法提供了一种求解系统优化问题的通用框架p ”，它不依赖于问题的 具体领域，对问题的种类有很强的适应性，所以广泛应用于很多学科。遗传算法 的应用领域主要有： ( 1 ) 函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用 算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函 数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数， 有单峰函数也有多峰函数等，人们用这些几何特性各异的函数来评价遗传算法的 性能。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较 难求解，遗传算法却可以方便地得到较好的结果。 ( 2 ) 组合优化 随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时在目前的计 算机上用枚举法很难或者甚至不可能得到其精确最优解。对于这类复杂问题，人 们己意识到应把精力放在寻求其满意解上，而遗传算法则是寻求这种满意解的最 佳工具之一。实践证明，遗传算法对于组合优化中的n p 完全问题非常有效。例 如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形分划问题等方 面得到成功的应用。 ( 3 ) 生产调度问题 生产调度问题在许多情况下所建立起来的数学模型难以精确求解，即使经过 一些简化之后可以进行求解，也会因简化太多而使得求解结果与实际相差甚远。 因此，目前在现实生产中也主要靠一些经验进行调度。遗传算法已成为解决复杂 调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、 任务分配等方面遗传算法都得到了有效的应用。 ( 4 ) 自动控制 在自动控制领域中许多与优化相关的问题需要求解，遗传算法的应用日益增 加，并显示了良好的效果。例如用遗传算法进行航空控制系统的优化、基于遗传 算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工 神经网络的结构优化设计和权值学习，都显示出了遗传算法在这些领域中应用的 可能性。 ( 5 ) 机器人智能控制 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于 对人工自适应系统的研究，所以机器人智能控制理所当然地成为遗传算法的一个 重要应用领域。例如遗传算法已经在移动机器人路径规划、关节机器人运动轨迹 规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究 和应用。 ( 6 ) 图像处理和模式识别 图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程 中，如扫描、特征提取、图像分割等不可避免地会产生一些误差，这些误差会影 响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的 重要要求。遗传算法在图像处理中的优化计算方面是完全胜任的。目前已在图像 恢复、图像边缘特征提取、几何形状识别等方面得到了应用。 ( 7 ) 人工生命 人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特有行为 的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与 遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要 理论基础。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、 学习模型、行为模型等方面显示了初步的应用能力。可以预见，遗传算法在人工 生命及复杂自适应系统的模拟与设计、复杂系统突现性理论研究中，将得到更为 深入的发展。 ( 8 ) 遗传程序设计 k o m 发展了遗传程序设计的概念，他使用了以l i s p 语言所表示的编码方法， 基于对一种树型结构所进行的遗传操作自动生成计算机程序。虽然遗传程序设计 的理论尚未成熟，应用也有一些限制。但它已有一些成功的应用。g a 在早期就 曾应用于囚徒困境问题分析。近年来，商业、金融领域已经成为遗传算法应用热 点。遗传算法与现代计算机强大的运算能力相结合，使金融交易中瞬息万变的诸 多因素能够为人所理解并能加以利用，使交易者更多地依赖于计算机的速度。目 前己经有许多基于遗传算法的软件包应用于金融系统和股票投资分析。 ( 9 ) 机器学习 学习能力是高级自适应系统所应具备的能力之。基于遗传算法的机器学 习，特别是分类器系统，在许多领域得到了应用。例如，遗传算法被用于模糊控 制规则的学习，利用遗传算法学习隶属度函数，从而更好地改进模糊系统的性能。 基于遗传算法的机器学习可用于调整人工神经网络的连接权，也可用于神经网络 结构的优化设计。分类器系统在多机器人路径规划系统中得到了成功的应用。 第三章资源受限的项目调度问题( r c p s p ) 3 1r c p s p 问题的描述 资源受限的项目调度问题( r c p s p ) 是典型的组合优化问题，其基本内容可 描述为：对于给定的刀项具有优先顺序的活动= 1 ，2 ，刀和所种可更新资源，每 种资源的可用量为局，后= l ，2 ，m ，一项活动的执行过程需要花费矿个时间 单位，在这段时间内，资源后的一个常量被占用，每一个活动有一个紧前关 系集合名和一个紧后关系集合t 。事实上，只需定义紧前关系集合或紧后关系 集合就足够了，因为，e 母，如果，z ，那么我们说 ( i 先gj ) ， 从而活动不能在，结束之前开始。除此之外，如果， 且 ，则也有， 。在每个新的调度阶段，选择乞中优先权最大的工 作( 如果有多个工作具有相同的优先权，则选择编号最小的工作) 加入绣，并 指定该工作的开始时间为满足紧前关系约束和资源约束的最早可行时间。记 s t 为工作的开始执行时刻，历为根据方法计算得到的工作的,pertcpm 最晚开 初始化：刀：= 1 ，绣： l ，蹈= o ； w h i l e i 绣i 0 的大小改变偏好的大小。 s c h i r m e r 3 5 1 对b r s 和r b r s 算法进行了改进，提出了标准化带有偏好的随 机采样算法( n o r m a l i z e db r s ，简称n b r s ) 和修正的基于后悔值得随机采样算 法( m o d i f i e dr b r s ，简称m r b r s ) ，这两种算法避免了在计算9 ( ) 时的不稳定 性，使得9 ( ) 更能反映工作的优先权。该文作者通过对计划生成方案( s s s ， p s s ) 、随机采样算法( n b r s 、m r b r s ) 、优先规则( m i n s l k 、l f t 、l s t 等) 和样本规模z 及参数a 的多种组合的实验j 证明了该算法的有效性，分析了算法 求得的解答最优性和参数的关系。 由于r c p s p 属于n p h a r d 问题，没有一种启发式算法能对所有的问题实例 都能求出令人满意的解，只能根据问题实例的特点来选择相应的算法。s c h i r m e r 提出了一种基于案例推理的自适应算法，基本思想是将r c p s p 的问题实例根据 其特征参数n c 、r f 和r s 划分成不同的类，针对每一类的实例问题在求解时选 择相应的控制策略，以得到较好的解。算法具有学习能力，可以根据新的问题实 例求解结果修正原来的控制策略，也可以增加新的控制策略。该文作者通过大量 的实验，给出了r s p s p 类的划分方法及其对应的控制策略。 ( 3 ) 智能优化算法 近年来，模拟退火( s i m u l a t e da n n e a l i n g ，简称s a ) 、禁忌搜索( t a b us e a r c h ， 简称t s ) 和遗传算法( g e n e t i ca l g o r i