（管理科学与工程专业论文）遗传算法与正交设计的结合及应用.pdf

中圈科学拉术 擘硎f ? 沦空 遗竹算法0 雕宓 ； f 的纳台及成用 摘要 ? 遗传算法是基于进化论的原理发展起来的一种广为应用的、商效的随机搜 索与优化算法。遗传算法从一组随机生成的个体组成的种群开始，经过选择、 交叉、变异等遗传操作对问题的解空间进行高效的随机搜索。遗传算法具有简 单、通用、鲁棒性强等特点，适用于对复杂问题的求解，特别是柔性制造系统 领域中存在的能力扩张等大规模整数混合规划问题。 正交设计是试验设计方法中最优的设计方法之一。采用正交设计可以通过 少量的试验点获取尽可能多的信息。旋转正交法是在正交设计基础上提出的特 别针对整数规划问题的一种求解方法。旋转正交法通过正交设计对问题的求解 空问进行正交取样，并引入极差思想，通过极差比较在不同的正交子空间之间 进行旋转，以较快的速度搜索整个解空间。? 旋转正交法与遗传算法结合的算法通过旋转正交法快速提取解空间中的优 异个体，并将其添加到遗传算法的种群中，参与遗传运算。采用这样的处理将 个子空间的最优试验个体的遗传信息添加到种群中，加快遗传算法的搜索速度。 通过向种群中添加各个不同子空间的优异个体，可以迫使遗传算法不局限于某 个子空间搜索从而避免出现未成熟收敛现象。本文提出的算法在应用表面封装 技术的印刷配线板的能力扩张规划中获得良好的应用。 关键字：遗传算法，正交设计，旋转正交法 闽科学技术人学颁i j 地立遗f i ： 盘与爪交墩计的站旮及j 配川 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 saw e l l - u s e da n dh i g he f f i c i e n c yr a n d o m l ys e a r c h i n g m e t h o dt h a tb a s e do ne v o l u t i o n a r yt h e o r y f r o mar a n d o m l yp r o d u c e dp o p u l a t i o n ， g e n e t i ca l g o r i t h ms e a r c h e st h ef i e l de f f i c i e n t l yt h r o u g hg e n e t i co p e r a t i o n ss u c h a s s e l e c t ，c r o s s o v e ra n dm u t a t i o n s i m p l i c i t y ，g e n e r a l i z a t i o na n ds t r o n gr o b u s t n e s sa r e c h a r a c t e r so fg a g ai sw e l lf i t t e dt os o m ev e r yc o m p l e xq u e s t i o n s ，s u c ha si a r g e s c a l e i n t e g e r - m i x e dp r o g r a m m i n gp r o b l e m w h i c hw & s g i v e n o u ti nf l e x i b l e m a n u f a c t u r i n gs y s t e mc a p a c i t yd e s i g n o r t h o g o n a ld e s i g ni so n eo f t h eo p t i m a le x p e r i m e n t a ld e s i g n s u s i n go r t h o g o n a l d e s i g nt o s e l e c te x p e r i m e n tp o i n t sc a r lo b t a i np a r a m e t e r s i n f o r m a t i o nt h r o u 曲l e s s e x p e r i m e n t s r o t a t i n go n h o g o n a lm e t h o dr r o r 0s a m p l e st h ef i e l db yo r t h o g o n a l d e s i g n ，t h e nc o m p a r e s e a c hf a c t o r s e f f e c t b yt h eo r d e r , r o mr o t a t e sa m o n g d i f f e r e n to r t h o g o n a ls u bf i e l d sa n ds e a r c h e sf o rt h eb e s ts o l u t i o n t h en e w a l g o r i t h mc o m b i n e sg a a n dr o m t o g e t h e r r o m g au s e sr o m t o s e l e c tt h eb e s ti n d i v i d u a lf r o ms a m p l i n gp o i n t s t h e na d d st h eb e s to n ei n t ot h e p o p u l a t i o no f g a b a s e do nt h eg e n e t i cm e c h a n i s mo fo a ，t h eg e n e t i ci n f o r m a t i o no f b e s ti n d i v i d u a lo fe a c ho r t h o g o n a ls u bf i e l do b t a i n e db yr o mc a nb eu s e dt o a c c e l e r a t et h es e a r c h i n gs p e e do f g a a d d i n g b e s ti n d i v i d u a l si n t ot h ep o p u l a t i o nc a l l p r e v e n tg a f r o mi m m a t u r ec o n v e r g e n c e r o m g ai sw e l la p p l i e di nt h ec a p a c i t y e x p a n s i o n o fp r i n t e dc i r c u i tb o a r d m a n u f a c t u r i n g w h i c hu s e ss u r f a c em o u n t t e c h n o l o g y k e y w o r d s ：g e n e t i ca l g o r i t h m ，o r t h o g o n a ld e s i g n ，r o t a t i n go r t h o g o n a lm e t h o d 4 q i 田科学拙术j ：学倒【l j 论义 遗伯算法l = i 形受敬计的蚰驶心j 第一章绪论 在工业工程的研究与实践中，一些问题特别是制造系统中的许多最优化问 题如柔性制造系统的能力规划等，具有非常复杂的性质。这类问题采用传统 的优化方法很难解决这一类问题，但是随着遗传算法( g a - - - g e n e t i ca l g o r i t h m ) 的提出，人们找到求解这类问题的一种有效的算法。 遗传算法是由美国m i c h i g a n 大学的j h o l l a n d 教授在2 0 世纪6 0 年代初期 提出其数学框架于6 0 年代中期完成。遗传算法的内涵哲理是启迪于自然界生 物从低级、简单，到高级、复杂直至人类这样漫长而复杂的进化过程，借鉴 于达尔文的物竞天演、优胜劣汰、适者生存的自然选择和自然进化的机理，通 过在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过 程以获得最优解其本质是一种求解问题的高效并行全局搜索算法。由于遗传 算法的整体搜索策略和优化计算时不依赖于梯度信息，所以遗传算法具有广泛 的应用范围，特别适合处理高度复杂的非线性问题。 遗传算法的两大主要特点是群体搜索策略和群体中个体之间的信息相互交 换，它实际是模拟由个体组成的群体的整体学习过程，其中每个个体表示给定 问题空间的一个解点。遗传算法从任一初始的群体出发，通过随机选择( 使群体 中优秀的个体有更多的机会传给下一代) 、交叉( 体现自然界中群体内个体之间 的信息交换) 和变异( 在群体中引入新的变种确保群体中信息的多样性) 等遗 传操作，使群体一代一代地进化到搜索空间越来越好的区域，直至抵达最优解 点。 正交设计是一种已经被证明的有效的试验设计方法。正交设计是利用正交 表来安排具有均衡搭配特性的试验计划。所谓均衡搭配原则是指：每一个因子 的各水平出现的次数相同：每两个因子的各水平搭配出现的次数相同。正交设 计强调“均衡性”，即对每一个因素的渚水平一视同仁，体现了设计的一维和二 维边缘的投影均匀性。通过正交设计方法设计试验方案，选取相应的试验点 可以达到通过少量的试验获得尽可能多的信息的效果。在正交设计的基础上 旋转n j 交法是借鉴限交设计的原理，利用爪交拉丁方的思想，对烂个墩值空间 进行全面的覆盖，同时揪掘函数特征，利用“极差”的思想，别m 交拉丁方进 巾珊科学挫术大学埘i j i = 史遗 算 击限交l i 计的缃台度脚，i j 行变换从而不断更新试验点，以至达到最优点或次优点。 本文提出的旋转正交遗传算法( r o m g a ) 将正交法与遗传算法结合起来 具体算法如下：通过正交设计对问题的解空间进行选择，提取试验点，获得关 于最优点的遗传信息，然后添加到遗传中群中通过遗传算法对获得的信息进行 遗传操作，求得最优解或次优解。 本文共分六章，第一章绪论，对文章内容进行简单介绍。第二章主要介绍 遗传算法。包括遗传算法的结构、遗传算法的基本要素、遗传算法的基本原理 等。第三章是阐述旋转正交法的思想，第四章是旋转正交法与遗传算法的结合， 提出结合算法r o m s g a ，并进行算法的有效性实证。第五章将r o m s g a 应 用到柔性生产系统的能力规划问题中，求解大规模整数混合规划问题。第六章 总结全文。 中i 目 ： 学救术人学瑚i ：论立 i l ! i 彝垃如竹：受改汁的蚰敬成用 第二章遗传算法 遗传算法( g e n e t i ca 1 9 0 r j c h m g a ) 是一类借鉴生物界自然选择和自然 遗传机制的随机化搜索算法，由美 m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首 先提出。 遗传算法将生命的遗传机制和生物界的适者生存引入到科学计算中，模仿 自然界生物进化过程，其独特之处在于群体搜索策略和群体中个体之间的信息 交换，搜索不依赖于梯度信息。因为生物在进化过程中所要解决的生存问题具 有高度非线性、随机性、复杂性等特点，而生物的进化很好地解决了这一问题； 所以遗传算法为解决高度复杂的实际问题提供了一条新途径。 遗传算法的主要特点是简单通用、鲁棒性强适用于并行分布处理。它尤 其适用于处理传统搜索方法难于解决的复杂和非线性问题，如组合优化问题。 在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索 的组合爆炸。遗传算法能在搜索过程中自动获取和积累有关搜索空间的知识， 并自适应地控制搜索过程，从而得到最优解或准最优解。遗传算法可以广泛用 于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。是2 1 世纪 有关智能计算中的关键技术之一。 2 1 遗传算法的结构 遗传算法的常用形式是g o l d b e r g 提出的。和传统的搜索算法不同，遗传算 法从一组随机产生的初始解，称为“种群( p o p u l a t i o n ) ”，开始搜索过程。种群 中的每个个体是问题的一个解称为“染色体( c h r o m o s o m e ) ”，染色体是一串 符号如二进制字符串。种群中的染色体在后续的迭代中不断进化，称为遗传。 在进化过程的每一代中采用“适值( f i t n e s s ) ”来测量染色体的好坏。前一代染 色体通过选择( s e l e c t ) 、交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 等遗传操作生成生成 的下一代染色体，称为“后代( o f f s p r i n g ) ”。在新一代染色体形成的过程中 根据适应值的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。 经过若干代遗传演化之后算法可能收敛于最好的染色体，即可能是问题的最 优解或次优解。 中圈科学技术太孕硝j j 舱文遗伯算法与正空 ! 汁的绋台发戌胴 遗传算法的基本流程如图2 _ 1 所示： 图2 】遗传算法的基本流程 从图2 1 可见，遗传算法是一种群体性操作，该操作以群体中的所有个体 为对象。选择、交叉和变异是3 个主要的遗传操作算子，它们共同构成了遗传 操作( g e n e t i co p e r a t i o n ) ，使遗传算法具有了其他传统算法所没有的特性。 2 2 遗传算法的基本要素 遗传算法包含了如下5 个基本因素：参数编码、初始群体的确定、适应度 函数的设计、遗传操作设计、控制参数设定。 2 - 2 1 参数编码 遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体越加结构 重组处理从而不断搜索出群体中个体问的相似性，并形成优化积木块以逐渐 逼近最优解。因此遗传算法不能直接处理问题空间的参数，必须将它们转换 成遗传空问的基因按一定结构组成的染色体或个体这一转换操作就是编码 ( c o d i n g ) 。编码实现表现型到基因型的转换与编码相对的是译码( d e c o d i n g ) - 它实现从基因型到表现型的转换。 中田科学技术人掌例l j 论文造f 算蹯与j f ；= 交鼬计的纳台及戍，盱 编码评估规范和编码原理： 评估编码策略常采用以下3 个规范： ( 1 ) 完备性：问题空阃中的所有点( 候选解) 都能作为遗传算法空间中的 点( 染色体) 表现。 ( 2 ) 健全性：遗传算法空间的染色体能对应所有问题空间中的候选解。 ( 3 ) 非冗余性：染色体和候选解一一对应。 d e j o n g 的编码原理： ( 1 ) 有意义积木块编码原则：所定编码应当易于生成与所求问题相关的短 距和低阶的积木块。 ( 2 ) 最小字符编码规则：所定编码应采用最小字符集以使问题得到自然的 表示或描述。 现在已经提出的编码方案有：一维染色体编码、多参数映射编码、可变染 色体长度编码、树结构编码等。本文提出的算法采用的编码方式为一维染色体 编码种的二值编码。 一维染色体编码：指搜索空间的参数转换到遗传空间后，其相应的基因呈 一维排列构成染色体。在一维染色体编码中最常用的符号集是二值符号集 0 ， il ，基于此符号集的个体表现为二值码串，这种编码方式称为二值编码。 二值编码是目前遗传算法中常用的编码方法，二值编码具有如下特点： ( 1 ) 简单易行； ( 2 ) 符合最小字符集编码原则： ( 3 ) 便于用模式定理进行分析。 但是二值编码存在一定的缺点，特别是它不能直接反映出所求问题的本身 结构特征，很难满足有意义积木块编码原则。 2 2 2 群体设定 在遗传算法处理流程中，继编码设计之后的任务是初始群体的设定，并以 此为起点一代代进化直到按某种进化停止规则中止进化过程。在群体设定中的 关键因素是群体规模的设定，即群体中个体数目的设定。在群体设定中需要考 9 中冈科学投术人学碗j ：论文遗佟算弦与i e 兜戳纠纳台z 乏成用 虑两个因素：初始群体的设定、进化过程中各代( 或群体) 的规模如何维持 ( 1 ) 初始群体的设定 一般遗传算法中初始群体中的个体是随机产生的，其设定采用以下策略： a 根据问题固有知识，设法把握最优解所占空间在整个问题空间的分布范 围然后在此范围中设定初始群体。 b 先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中， 这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。 ( 2 ) 群体多样性 群体规模的设定受遗传操作中选择操作的影响很大。根据遗传算法的模式 定理，若群体规模为m ，则遗传操作可从这m 个个体中生成和检测m m 个模 式，并在此基础上不断性形成和优化积木块，直到达到最优解。m 越太，遗传 操作所处理的模式就越多，生成有意义的积木块并逐渐进化为最优解的机会就 越高，即群体规模越太，陷入局部最优解的危险就越小；但是群体规模太太会 带来若干弊病：一是群体规模直接影响计算效率，二是进行选择的过程中，一 般采用与适应度成比例的方法，群体中个体非常大时。少量适应度很高的个体 会被选择而生存，但大多数个体会被淘汰，这影响配对库的形成。另一方面， 群体规模太小，会使遗传算法的搜索空间分布范围有限，搜索可能停止在未成 熟阶段引起未成熟收敛即群体规模不能太小。 2 2 3 适应度函数 遗传算法使用目标函数即适应度函数作为依据，其不受连续可微的约束且 定义域可以为任意集合，唯一要求是针对输入能够计算出可以比较的非负结果。 在具体应用中，由于适应度函数的设计和遗传操作中的选择直接有关，所以适 应度函数的设计要结合求解问题的本身要求而定。 已经采用的适应度函数有以下几种方法： ( 1 ) 目标函数映射成适应度函数：在遗传算法中，适应度函数要进行比较 排序并在此基础上计算选择概率这要求适应度函数的值取正值。因 此在实际计算中，将目标函数映射成求最大值形式且函数值非负的必 要。一般可以采用的映射方式如下： o 中田奉 学技术人学脚i j ：论文地 = 纰与难交1 矬i f 的绨放成f j c z ，= 孑”“一g 工 当占“) _ c 。 其他情况 其中的c 。存在多种选择方式： a 个合适的输入值； b 迄今为止进化过程中g ( x ) 的最大值或当前群体中g ( x ) 的最大值； c 前k 代中g ( 工) 的最大值。 ( 2 ) 适应度函数定标。 在遗传算法的实际应用过程中，可能会出现两种不利的情况：一是未成熟收 敛，即在遗传进化的早期超常个体的出现导致这些个体在群体中占有较大比例； 二是随机漫游，即群体的平均适应度已接近最佳个体适应度，此时个体间竞争 力减弱，最佳个体和其他太多数个体在选择过程中有几乎相等的选择机会，从 而使有目标的优化过程趋向无目标的随机优化过程。 为了避免出现这两种情况，人们对适应度进行缩放调整适应度函数定 标。主要定标方式有以下几种：线性定标、o 截断、乘幂标等。 线性定标：设原适应度函数为，定标后的适应度函数为厂，则线性定标 可采用下式表示厂= 矿+ 6 。系数a 、b 可以有多种途径进行设定但需要满足 两个条件： 1 ) 原适应度函数平均值要等于定标后的适应度平均值； 2 ) 定标后的适应度函数的最大值厂二要等于原适应度函数平均值厂所指 定的倍数即厂。= c , u t t * 厂。其中c 。是为得到所期待的最有群体 个体的复制数对于个体数目在5 0 - 1 0 0 之间的群体- c 。可在1 2 2 0 之日j 取值。 ( 3 ) 惩 目函数法 这种适应度函数的表达方法主要针对有约束问题的求解。在用遗传算法对 有约束问题求解的过程中，需要考虑每一代种群中的个体是否满足约束条件。 惩罚函数法的目的就是设法对个体违背约束条件的情况给与惩罚，并将惩罚体 翔抖学技术大学倒j ：论文j 笕 0 算法与试受垃汁的站台z 乏艘j f j 现在适应度函数设计中，把一个约束优化问胚转换为一个附带考虑代价或惩罚 的非约束优化问题。 惩罚函数一般分为两类：定量惩罚、变量惩罚。对于复杂问题变量惩罚 比定量惩 有效。 2 2 4 遗传操作 在遗传箅法中，通过编码确定初始群体后，遗传操作对群体中的个体按照 其对环境的适应度施加一定的操作，从而实现优胜劣汰的进化过程。遗传操作 事模拟生物基因遗传的操作，从优化搜索的角度而言。遗传操作可以使问题的 解，一代又一代地优化，并逼近最优解。 遗传操作包括三个基本遗传算子：选择( 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 24 1 选择算子 选择是从群体中选择优胜的个体，淘汰劣质个体的操作。选择的目的是把 优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。 遗传算法的基本原理就是达尔文的自然选择原理，选择是遗传算法的推动 力。选择压力是一个内含的准则，压力过大搜索就会过早停止；压力过小搜索 又会不必要的缓慢。选择压力一般遵循的规则是在算法的初级阶段采用低的选 择压力扩展搜索空问，在算法的终止阶段采用较高的选择压力寻找最好的解域， 将遗传搜索引向展优解。 选择操作包括三个基本方面： ( 1 ) 采样空间； ( 2 ) 采样机理； ( 3 ) 选择概率。 2 中田科学投术人学例j ：论文笼f 算谯0 0 难受墩计的鲥f 台敷皿朋 采样空问 采样空问由两个因素来确定：大小和成分( 双亲或后代) 。采样空问分为两 种：规则的采样空问、扩大的采样空间。令p o p _ s i z e 为种群大小，o f f _ s i z e 为 每代产生的个体数。规则的采样空问的大小为p o ps i z e ，含有所有后代和部分 双亲；扩大的采样空间的大小为p o p s i z e + o 吣i z e ，包括所有双亲和后代。 ( 1 ) 规则采样空间 h o l l a n d 提出的原始的遗传算法中，后代旦产生就替代双亲，即整代替 代。d ej o n g 提出了群替代策略：后代一产生，就选一个父代死去，死去 的父代是和该后代最相似的，相似性通过简单的位与位相同的数量进行 测量。m i c h a l e w i c z 则详细描述了后代直接替代双亲，下代由转轮选择生 成的简单遗传算法。 ( 2 ) 扩大的采样空间 在扩大的采样空间进行选择时，双亲和后代有同样的生存机会。典型的 选择方式是( t a - - ) 选择：“个父代和 个后代竞争生存最后选出最 好的u 个父代和后代构成下一代的双亲。另一种策略是( ， ) 选择： 选择u 个最好的后代作为下一代双亲( p ) 。这两种选择策略都可以 通过概率方式在扩大的采样空间实现。这两种策略的优点在于可以用增 加交叉率和变异率的方法改进遗传算法的效能。 采样机理 采样机理是指如何从采样空间中选择染色体的理论，有如下三种选择方法： 随机采样、确定采样、混合采样。 ( 1 ) 随机采样 b a k e r 指出。随机采样的特点是在选择阶段根据生存概率来确定每个 染色体的实际繁殖数。选择阶段由两部分构成：确定染色体的期望 值：将期望值转换成后代数。这类方法中最著名的是h o l l a n d 的正比 选择或转轮选择，其基本思想是每个染色体的选择概率正比与它的 适应度值。 ( 2 ) 确定采样 确定采样是从采样空问中选择p o p _ s i z e 个最好的染色体( u + x ) 卜田科学技术人学倒1 ： 仑史 造 算珐q 正受致计的绌台及成，盱 选择和( “， ) 选择都属于这种方法。截断恐择和阻塞恐择也属 于确定采样它们将所有染色体按适值大小排序后，选择最好的作 为繁殖的双亲。截断选择定义了一个闳值t ，每代选择t 的最好染 色傩，每个染色体产生10 0 t 个后代。阻塞选择等价于截断选择它 让选出的p o p _ s i z e s 个最好染色体每个产生s 个后代。 ( 3 ) 混合采样 混合采样同时具有随机和确定采样的特征。典型的采样方法是 g o l d b e r g 等提出的竞赛选择：随机地选出一组染色体，从中选出最 好的一个进行繁殖，每组的染色体数称为竞赛人数。w e t z e l 提出的 随机竞赛选择按照一般方法计算选择概率，用转轮法选出成对的染 色体，然后将适值高的染色体加入到新种群，直到种群充满为止。 b r i n d l e 提出的保留随机采样为每个染色体分配其期望值的整数部分 个样本，然后所有染色体再按照其期望值的分数部分来竞争种群中 的空缺。 采样概率 较简单的采样概率的确定方法是正比选择法，即选择概率正比与染色体的 适值，但这种方法存在一定的缺陷，如在较早的代中一些超级染色体会霸占选 择过程，而在较晚的代中种群集中在起，染色体的竞争减弱。 标定法和排序法可以解决正比选择法带来的问题。标定法将原目标函数映 射为某个实数值，然后用这些实数值来确定每个染色体的生存概率。排序法则 忽略实际目标函数值，而采用染色体的顺序来替代生存概率。 标定法已经成为广为接受的方法，已经提出的标定方法可以分为以下两类： 静态标定、动态标定。其中动态标定可以尽一步分为两类：标定参数按照每代 中适值的分布情况自动调整，以保持恒定的选择压力；标定参数随代数的增加 而自动增加以相应的增加选择压力。 与采样概率有关的适应度函数定标在前面已经提到过，除了线性定标、动 态线性定标、o 截断和幂率标定以外，还包括对数标定、窗1 ：3 技术、j 下规化、 b o l t z m a n n 选择和排序等标定方法。针对本文所处理的实际问题，下面主要介绍 n j 规化定标方法。 【上鲤盟堂丝查叁堂堡! ：堡垒丝! ! 簦些生堑塞丝生业堂堂丝些旦 正规化定标是c h e n g 和g e n b 同抛出的一和，动态定标技术，对于极大化问 题，它采用如下形式：厂：= 燃： 对于极小化问胚，可取序z f m 。a x _ = - - l f + + ，r 。 在表达式中厂和厂分别为当前种群中最好和最坏的原始适值，是一个小 的正实数，通常限制在( 0 ，1 ) 开区间内。采用这种转换具有双重目的：防止 方程中分母为0 ；使适值正比选择改为纯随机选择成为可能。 针对不同的采样空间，采用不同的采样机理和选择概率，人们已经提出大 量的选择算子。常用的选择算子有以下几种： a 适应度比例方法( 赌轮或蒙特卡罗选择) 最基本最常用的选择方法，个体的选择概率与其适应度成比例。 b 最佳个体保存方法( e l i t i s tm o d e l ) 该方法是将群体中适应度最高的个体不进行配对交叉而直接复制到下 代。这种方法的优点是进化过程中某一代的最优个体可以不被交叉和变异破坏， 但是局部最优个体的遗传基因可能会急速增加使进化限于局部解。所以这种方 法适用于单峰性质的搜索空间寻优，而不是多峰性质的空间寻优。 c 期望值方法( e x p e c t e d v a l u em o d e l ) 期望值方法的思想如下： 1 ) 计算群体中每个个体在下一代生存的期望数目： m = f 。| 1 = l t n 2 ) 若某个体被选中并要参与配对和交叉，则它在下一代中的生存数目减 去0 5 ；若不参与配对和交叉，则该个体的生存期望数目减1 。 3 ) 在2 ) 的两种情况中若一个个体的期望值小于零时，则该个体不参与 选择。 d 排序选择方法( r a n k b a s e dm o d e l ) 排序选择方法是指在计算每个个体的适应度后，根据适应皮大小顺序对群 体中个体排序，然后按照事先设计好的概率表按顺序分配给个体作为各自的 选择概率。 p 阐科学拙术人学瑚j ：抡立遗 ，l ：j 杰- j ij l 蹙墩计的纳2 乏i ! y l l j ei 陕赛选择方法( t o u r n a m e n ts e l e c t i o nm o d e l ) 该方法的操作思想是：从群体中任意选择一定数目的个体( 联赛规模) ，其 中适应废最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的 个体数达到预先设定的数目为止。 f 排挤方法( c r o w d i n g m o d e l ) d e j o n g 提出的排挤选择方法是新生成的子代将替代或排挤相似的旧父代个 体，提高群体的多样性。 这几种选择方法对遗传算法的在线和离线性能的影响均各不相同，在具体 问题的处理过程中应根据问题求解特点采用较适合的方法或结合使用。 2 2 4 2 交叉算子 遗传算法中起核心作用的操作是交叉操作，交叉操作是指把两个父代个体 的部分结构加以替换重组而生成新个体的操作。任何交叉算子的设计必须考虑 如下两点：一是任何交叉算子需满足交叉算子的评估规则，即交叉算子必须保 证前一代中优秀个体的性状能在后一代的新个体中尽可能得到遗传和继承：二 是交叉算子和编码设计需要协调操作。 对于二值编码，各种交叉算子都包括两个基本内容：是从由选择操作形 成的配对库中，对个体随机配对并按预先设定的交叉概率来决定每对是否需要 进行交叉操作；二是设定配对个体的交叉点，并对这些点前后的配对个体的部分 结构( 或基因) 进行相互交换。 基本的交叉算子( 对二值编码) 有如下几种： a 一点交叉：在个体串中随机设定一个交叉点实行交叉时。该点前或后 的两个个体的部分结构进行互换并生成两个新个体。 b 二点交叉：设置两个交叉点其余与一点交叉类似。 c 多点交叉：此法较少采用，因为多点交叉不能有效的保存重要的模式。 d 一致交叉、部分匹配交叉、顺序交叉、周期交叉等。 对于实数编码或其他形式的编码，除了上述的交叉方法以外，还有相应的 其他交叉方式，如基于方向的交叉。这种交叉方法采用目标函数值来确定遗传 搜索的方向一运算按下面的公式由双亲x ，和x ：产生一个后代x ： i | 田“学技术太学俐士论文遗f e 算址与芷交l ； 十的纳台段膛加 x = ，( x 2 - x ) + x 2 ，式中，是0 与1 之问的随机数。 2 2 4 3 变异算子 变异算子是对群体中的个体串的某些基因座上的基因值作变动。变异算予 的基本步骤如下：一在群体中所有个体的码串范围内随机的确定基因座；二是 以事先设定的概率对基因座的基因值进行变异。 引入变异算子的目的为：一是使遗传算法具有局部随机搜索能力，当遗传 算法通过交叉算子己接近最优解邻域时，利用变异算子的局部随机搜索能力可 以加速向最优解收敛；二是使遗传算法可维持群体多样性，以防止出现未成熟 收敛。 变异算子有以下几种： a 基本变异算子： 对群体中的个体码串随机挑选一个或多个基因座并对这些基因座作变动。 b 逆转算子： 此算子是变异算子的一种特殊形式，其基本操作是在个体串中随机挑选二 个逆转点，然后将两个逆转点间的基因值以逆转概率逆向排序。 c 自适应变异算子： 该算子与基本变异算子的操作内容类似，唯一不同的是变异概率不是固定 不变而是随群体中个体的多样性程度而自适应调节，通常根据交叉所得两个新 个体的海明距离进行变化。 d 动态变异( 非均匀变异) ： 由j a n i l o w 和m i c h a l e w i c z 提出，目的是提高精度、增加细调能力。对于父 亲x ，若元素x 被选出作变异，则后代为x = i x l 一，溉，x 】- 其中溉是按 如下两种可麓选得的： x = x + ( ，x ：x 女) 或x = x i a ( t ，乩一x ：) 工? ，矗l 通常为变量溉的上下界，一般可由约束域确定：函数a ( t ，y ) 返回 ( o ，j 】| j 的一个值，使得( ，力随t 增加而趋于0 ( t 是代数) t 函数的这个性质 1 7 中旧科学技术人学鲥i ：诧尘 迪f - 算 上与i = 交1 5 计的站台及戊用 使得初始迭代时，搜索均匀分布在整个空倒，丽到后期则分斫，在局部范围内。 ( ，y ) 表达，眵式如下：( ，y ) 2 y 。，。( 1 一手) ，其中，r 是【。，l 】f 吲的随莉l 数；丁 是最大代数；b 是确定不均匀度的参数。该运算可能产生不可行的后代，可以 采取减少随机数r 的方法来解决。 e 基于方向的变异： 由g e n 和l i u 提出。连续可微函数，的t a y l o r 展开为 ，( x + 兰厂( z ) + ( 夥 + 融力) 。血，j e r “。 式中，0 口l ；v f ( x ) 为函数厂在点x 的梯度；缸是尺“中的摄动a 在遗传算 法计算过程中，对适应度函数的数学性质要求不高，可以按如下公式计算近似 梯度的第f 个分量： 鱼2 二垡_ 兰苎j 鼍上立生二删，z ，是一个小的实数。令d 为 “工 上式计算的近似梯度，变异后的后代即为x = x + r d ，r 是随机的非负实数。 在有方向的变异运算中，可以随机选择一个方向。特别是当染色体靠近边 界的时候，按梯度给出的方向容易都指向边界造成拥挤，在这种情况下应采用 随机方向替代给定的方向。 2 2 5 收敛性 遗传算法通过对遗传操作的恰当设计和运行，可以实现兼顾全局搜索和局 部搜索的均衡搜索，但是标准遗传算法的全局收敛性理论分析尚未解决。对于 遗传算法计算过程出现的未成熟收敛，已经进行了相当的研究并提出了一些解 决方案。 未成熟收敛主要有以下表现：一是群体中所有个体都陷入同极值而停止 进化；二是接近最优解的个体总是被淘汰进化过程不收敛。产生未成熟收敛 的因素具体表现如下： a 在进化韧始阶段，生成了具有很高适应度的个体； 巾闺科学技术人学倒j j 地卫：遗仲算躔j 蚵：交啦计的纳台及心朋 b 在基于适应度比例的选择下，其他个体被淘汰，犬部分个体与x 一致； c 相同的两个个体进行交叉，从而未能生成新个体； d 通过变异或逆转所生成的个体适应度高但数量少，所以被淘汰的概率很 大： e 群体中的大部分个体都处于与x 一致的状态。 对于未成熟收敛现象，已经有的经验和对策主要有以下几点： ( 1 ) 提高变异概率：在进化初始阶段可以加强遗传算法的随机搜索能力： ( 2 ) 调整选择概率：把选择概率本身作为个体进行优化即所谓元o a ； ( 3 ) 合适定标：适应度定标： ( 4 ) 维持群体中个体的多样性： a 增加群体规模，但需考虑计算量增加因素： b 实旄局部化：将群体分成若干子群体，每个群体独立的进行选择操作， 可以使由于出现不适当个体而产生未成熟收敛的现象局部化： c 实施单一化：把相同的个体单一化，即不允许群体中若干相同个体的出 现； d 增大配对个体距离：配对选择一般是随机进行的，其中缺少对个体问相 似度的判断，有可能使交叉结果未能产生新个体，作为改进，可用海明距离测 度来判断配对个体的相似度，并由此决定配对与否。 标准遗传算法的收敛性 对于标准遗传算法的收敛性，研究表明标准遗传算法并不保证全局最优收 敛，但是在一定的约束条件下可以实现收敛。相关的定理和定义如下： 标准遗传算法可被描述成一个马尔可夫链：状态空间s = b ”= b 7 ”，其 中n 表示群体大小，f 表示染色体串的长度。 群体中各基因( 个体中的位) 由于遗传算子引起的概率变化由变换矩阵 j d 描述。p 可以表示为随机矩阵c ，s 的乘积，c 为交叉算子引起的变化， ，为变异算子的作用，s 表示为选择算子的作用。 定理2 _ 1 如果变异概率p 。( o ，1 ) 一交叉概率为p 。【o ，l 】，同时采用比例 小i 日h 学拔_ 苯) 哿：觋l ：论文 地他# 珐旦j i 彬空敬汁的鲐古发j 圳f 选抒法( 按个体适应度占群体适应度的比例进行复 ；! j ) ，则标准遗传算法的变化 矩阵，是基本的。 定理2 _ 2 标准遗传算法( 参数同定理2 】) 不能收敛至全局最优值。 定理2 3 具有定理2 1 所示参数， 最终能够收敛到全局最佳值。 定理2 - 4 具有定理2 1 所示参数， 可收敛于全局最优解。 且在选择后保留当前最优值的遗传算法 且在选择前保留当前最优解的遗传算法 由此可见标准遗传算法( 符合定理2 1 的参数设置) 在任意初始化，任 意交叉算子( 简单或复杂) 以及任意适应度函数下，均不能收敛到全局最优解， 而通过改进标准遗传算法即在选择作用前( 或后) 保留当前最优解，则能保 证收敛至全局最优解。 2 3 遗传算法的基本原理和优点 2 3 1 遗传算法的基本原理 已经提出的遗传算法的基本原理和理论包括模式定理、积木块假设、最小 骗问题、隐并行性等。 2 3 1 1 模式定理 模式( s c h e m a ) ：描述字符串集的模板该字符串集中的串在某些位置上存在相 似性。如基于三值字符串 0 1 ，+ 所产生的能描述具有某些结构相似性的0 ， 1 字符串集的字符串即为模式。 模式的阶：模式中确定位置的个数称为该模式的模式阶。 模式的定义距：模式中第一个确定位置和最后一个确定位置之间的距离称为该 模式的定义距。 模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及 平均适应度高于群体平均适应度的模式在予代中将得以指数级增长。 统汁确定理论中的双角子机问题表明：要获得最优的可性解，则必须保证 较优解的样本数呈指数级增长。模式定理保证较优模式的样本数呈指数级增长 i i 【日科学技术人学倾i ? 论文 遗f 算法0 砒型改计的蚺啬z 乏 j ( ，h 从而给出了遗传算法的理论基础。 2 3 1 2 积木块假设 积木块：具有低阶、短定义距以及高适应度的模式称为积木块。 积木块假设：积木块在遗传算子的作用下，相互结合，能够生成高阶、长距、 高平均适应度的模式，可最终生成全局最优解。 积木块假设没有得到证明，但是已经有大量的实践证据支持这一假设。从2 0 年前b a g l e y 和r o s e n b e r g 的两篇开创性的文章到最近大量的遗传算法应用实例 都表明，积木块假设在平滑多峰问题、带干扰多峰问题以及组合优化问题等领 域均取得成功。b e t h k e 采用w a l s h 函数和一种巧妙的模式变换，提出一种采用 w a l s h 系数计算模式平均适应度的有效分析方法，这种方法可以在一些特定的 适应度函数和编码方式下，可以判定积木块通过相互组合是否会产生最优解或 接近晟优解。h o l l a n d 把b e t h k e 的方法推广到当群体非均匀分布的模式平均适 应度分析上。 2 3 1 3 隐并行性 h o l l a n d 和g o l d b e r g 指出遗传算法有效处理的模式个数为o ( n 3 ) ，即尽管遗 传算法实际上只对n 个串个体进行运算，但却隐含处理了o ( n 3 ) 个模式，这个 性质就是隐并行性。 隐并行性性质表明：尽管具有高阶、长定义距的模式在交叉算子和变异算 子作用下遭到破坏，遗传算法在处理相对小数目的串时，仍然隐含地处理了大 量的模式。 2 3 2 遗传算法的优点 主要有以下三点： ( 1 ) 遗传算法对所求解的优化问题没有太多的数学要求。由于算法的进化 性特点在解的搜索过程中不需要考虑解问题的内在性质，遗传算法可以处理 任意形式的目标函数和约束，不论是线性还是非线性，离散还是连续，甚至混 合的搜索空问。编码操作使得遗传算法可直接对结构对象进行操作如集合、 叶i 田h 学拙术人学硎j ：论文 遗仲髯_ 盘与花交墩计的站台及础，日 序列、矩阵、树、图、链和袭等各种一线或二维甚至三维结构形式的对象，这 一特点，使得遗传算法具有广泛的应用领域。 ( 2 ) 进化算子的各态历经性使得遗传算法能够非常有效的进行概率意义下 的全局搜索，而传统的优化方法则是通过临近点比较而移向较好点从而达到 收敛的局部搜索过程。这种方法在问题具有凸性时才能找到全局最优解。遗传 算法是采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进 行评估。更形象地说遗传算法是并行地爬多个峰。这一特点使遗传算法具有 较好的全局搜索性能，减少了陷于局部优解的风险。同时，这使遗传算法本身 也十分易于并行化。 ( 3 ) 遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独 立的启发式，保证算法的有效性。 卜旧 ： 学技术人学彤i j 论文避 0 算法与玳受挫计的铺台厦脚用 第三章正交设计和旋转正交法 3 1 正交设计 正交试验设计 正交试验设计是一种研究多因子试验问题的重要的数学方法，它主要使用 正交表这一工具来进行整体设计、综合比较、统计分析，具体的讲就是使用正 交表从所有可能搭配中选择若干必需的试验，然后采用统计方法对试验结果进 行综台处理，获得关于问题的重要信息。 3 1 1 定义 正交设计的定义( 均衡搭配原则) ：符合下列两个条件的设计为正交设计 ( 1 ) 每一个园子的各水平出现的次数相同； ( 2 ) 每两个因子的各水平搭配出现的次数相同。 正交设计阵的定义： 矩阵a 叫做正交设计阵，如果a 满足以下条件： ( 1 ) 对任何j - l ，2 ，m ，在五。，五：，兄。，这几个数中，1 ，2 ， s ，出现的次数一样多( 各y ，2 n t s ，次) - ( 2 ) 对任何j # k ， 在( 五圹五。) ，( 旯：，旯：+ ) ，( a 矿旯。) 这n 对数中( 1 ， 1 ) - ( i ，2 ) ，( 1 ，j t ) ，- ( s ，- 1 ) ，- ( s ，n ) 出现的次数一 样多( 各y 。= 刀，s ，s 1 次) 。 正交设计阵对应的设计即为正交设计。其中元素五。表示正交设计中第f 次 试验第j 个因子的水平，第j 个因子的水平值集合为 l ，2 ，3 ，s 1 试 验总次数为n 。 正交设计的优点在于在