（应用数学专业论文）遗传算法在三次设计中的应用.pdf

声明 r 8 78 6 0 7 本人郑重声明：本论文的所有研究工作都是在导师一王兵团教授的悉 心指导下，由本人独立创作完成论文中所引用的已知结论均可参见相应文 献，参考文献已在文章的最后列出特别，未经作者本人许可，任何擅自更 改、抄袭或剽窃本论文之内容的行为，都将承担相应的学术和法律责任。 曼虫鞋垡笙立_ 一3 o n l yc a ni tg r e a t l yr e d u c et h ee x p e r i m e n tt i m e sa r l dc o m p u t a t i o n ，b u t “s o t h eg o a lo p t i m u mo b t a i n e db yg e n e t i ca i g o r i t h mi 8b e t t e rt h a nt h a to f c o n v e n t i o n a lt i a n k o um e t h o d g ac a na l s ob ea p p l i e dt ot h et h r e es t a g e d e s i g no fe x p e r i m e n ti t e mi fc o m b i n i n gw i t hr e g r e s s i o ne x p e r i m e td e s i g n o ra r t 访c i a ln e u r a jn e t w o r k b a s e do nm a s t e r i n gt h es i m p l eg a ，e x p l o r e t h ee s s e n c eo ft h ed e s i g no fo p t i m i z a t i o na l g o r i t h m ，a n dt h e na p p l yt h e d e s i g no fe x p e r i m e n t o r t h o g o n a ld e 8 i g na n d8 y m m e t r i c a ld e s i g nt ot h e c r e a t i o no fg a sp r i m a r yp o p u l a t i o n ，8 t r u c t l l r eg aw i 七hn e wf o m ；s e e k c h em a t h e m a t i c a lp r o g r a mo fs i m p l og e n e t i ca l g o r i 七h m ，a n da l s op r e s e n t t h ep r o g r a mo ft h i 88 p e c i a lt h r e cs t a g ed e s i g n k e y w o r d s ： g e n e t i ca 1 9 0 r i t h m ；t h r e es t a g ed e s i g n ；o r t h o g o n a ld e _ 响；n ；s y m m e t r i c “d e s i g n ；m a t h e m a t i c a 第一章遗传算法简介及其应用现状 5 1 1 编码：最优化问题的解有两种常用表示方法一一二进制向量或浮点 向量用二进制编码的染色体用来表示决策变量的真实值，向量的长度由求 解问题要求的精度决定在求解复杂优化问题时，二进制向量表示结构解码 及解码均比较麻烦，而浮点向量则可表示一个长度与解向量相同的染色体 12初始化：随机产生个初始染色体(整数为种群数目)，或采用 以下方法初始化；根据事先给出的解集酽中的一个内点，记为，定义一 个足够大的数m，在形中，随机选择一个方向d，如果+md满足约 束，则将+md作为一个染色体，否则置m为o和m之间的一个随 机数，直到+md可行为止重复以上过程，直至产生个初始染色体h ，k ， 1 3 评价函数：评价函数e u 甜( y ) 是对种群中的染色体y 设定一个概 率，使该染色体被选择的可能性与其适应度成比例，可通过轮盘赌法，适应 度大的染色体被选择的机会更大在染色体，中，根据一定序 的关系，使染色体由好到坏进行重新排序设参数(0，1)，定义基于序号 的评价函数：e u 越( k ) = a ( 1 一a ) ”1 ，i = l ，2 ，； 1 4 选择算子：选择是用来确定重组或交叉个体，以及被选个体将产 轮盘赌选择过程以旋转赌轮次为基础，每次旋转都为新种群选择一 个染色体赌轮按每个染色体的适应度选择染色体，选择过程的一般步骤为： ( 1 ) 对每个染色体，计算累积概率吼= ：；1 段； (2)从区间中(0，1)产生一个随机数r； ( 3 ) 若吼一l r g ，则选择第t 个染色体k ( 1 ts ) ； ( 4 ) 重复( 2 ) 和( 3 ) 次，得到个复制的染色体吖，吃，一，嵋 笪二主垫堡簦鎏笪坌丛基堡旦塑些 6 1 5 交叉算子：基因重组是结合来自父代交配种群中的信息产生新的 个体按照编码表示法的不同，有实值重组( 包括离散重组、中间重组、线 性重组和扩展线性重组等) 和二进制交叉( 包括单点交叉、多点交叉、均匀 交叉、洗牌交叉和缩小代理交叉等) 定义参数只作为交叉操作的概率，种群中有期望值为p c 个染色体 进行交叉操作为确定交叉操作的父代，对 = 1 到，在 o ，1 】中产生随机 数r ，如果r p c ，选择k 作为父代对选择的父代( w ，彰) 进行交叉操作 产生新的染色体x 和y ：x = c k + ( 1 一c ) 巧，y = ( 1 一c ) k 。+ c 巧， 式中c 为开区间( 0 ，1 ) 中的一个随机数用交叉操作产生新的染色体x 和 y 代替原种群中的染色体蟛和彰 1 6 变异算子：定义参数尸k 作为遗传系统中的变异概率，种群中有 f k 个染色体进行变异操作首先类似于交叉操作，产生变异的父代对 进行变异的父代染色体矿，按关系x = y + m d 进行变异，产生新的染色 体x ，式中d 为舒中随机选择的变异方向；m 为初始化过程定义的一个 足够大的数如果x 不行，将们置为【o ，m 之间的一个随机数，重新用上 式计算，直到x 可行为止用变异产生的染色体x 代替原种群中的染色体 y 。父代种群经过选择、交叉和变异，得到子代种群 1 7 收敛条件；遗传算法的优化准则依据问题的不同，它有相应的确定 方式，如采用以下准则作为判断收敛条件： o 种群中个体的最大适应度超过预先设定值； o 种群中个体的平均适应度超过预先设定值； o 世代数超过预先设定值 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数( f i t n e 8 8 f u n c t i o n ) 为依据一般地，适应度函数是由目标函数变换而成的，基本的适 应度函数有以下几种； 箜二童垫堡差鎏笪金丛基堡旦垫鉴 l u 外的位而进行保护 基于生物免疫性的免疫算子，能明显抑制进化过程中的退化现象，减轻 g a 后期的波动，提高搜索效率和收敛速度有人提出的s r m ( s e l f - r e p r o d u c t i o n ) 算子增强了种群的多样性，c m ( c r o s s o v ea n dm u t a t i o n ) 算子促进了有利变 异的增加，使算法大大节省了存贮空间和运行时间采用“尺度收缩”策略 的混沌变异算子能明显的改善群体平均适应值，提高算法的性能，是解决优 化问题的有效方法 控制参数 控制参数一般有群体大小、交换概率、变异概率等，这些参数对遗传算 法性能影响较大在标准的遗传算法中多采用经验估计，这样会影响算法的 全局最优性和收敛性目前许多学者意识到这些参数应该随着遗传进化而 自适应变化，d a v i s 提出自适应算子概率方法，张良 x 笪二主垫堡苎鎏笪坌丛基堡旦塑些 1 1 进行设计，得到了便于理解的模糊集和模糊规则 用小波分析中的多尺度分析对g a 中的染色体进行多尺度分解，这样 分解后的染色体的长度变短，从而基因交换、变异等遗传操作更为彻底，有 效的克服了基因丢失引起的早熟问题小生境技术不仅能够保证群体中解 的多样性，而且具有很强的引导进化能力小生境技术的引入，提高了g a 处理多峰函数优化问题的能力 将模拟退火过程引入遗传算法，在优选交叉和变异个体的过程中加入 一定的“扰动”，以达到保持种群内位串的多样性和位串之间的竞争机制， 克服了算法易陷于极小点的问题，使得搜索沿着全局最优方向进行 以多点突变操作为主的广义遗传算法，实现了局部最优状态相互闯的 转移，使算法获得全局最优而面向对象遗传算法改变了在传统的g a 中各 个函数之间只有参数的传递而无代码的继承性的状况，从概念上提高了软件 的可重用性，用户可以更方便的设计和实现自己的编码方案和遗传算子变 异基遗传算法，采用变异算子进行局部优化搜索，并利用随机初始化技术使 算法在局部搜索能力提高的同时仍有可能寻找到全局最优解 第二章试验设计简介 在生产和科研中，为研制新产品，改革生产工艺，寻找优良的生产条件， 需要做许多多因素的试验对不同因素的所有可能的水平组合做试验，叫做 全面试验当因素较多时，虽然理论上仍可进行全面试验，但实际中会遇到 很多问题例如，生产化工产品，需要提高收益，认为反应温度的高低、加 碱量的多少、催化剂种类等多种因素都是造成收益不稳的主要原因根据以 往经验，温度有三个水平，加碱量有三个水平，催化剂有三个水平如果做 全面试验，则需3 3 = 2 7 次如果6 个因素，5 个试验水平，全面试验的次 数是5 6 = 1 5 6 2 5 次对于这样一些问题，设计全面试验往往耗时、费力因 此，要设计多因素试验方案，就得选择合理的试验设计方法，使之既能减少 试验次数，又能收到较好的效果 试验设计是统计数学的一个重要分支，是二十世纪初由生物统计学家 费歇尔( r o n a l df j s h e r ，英国人) 首创的他从实践和理论上发展、丰富了统 计数学，将试验设计方法应用于农业、生物学和遗传学等方面，取得了丰硕 成果三、四十年代，英、美、苏等国继续对试验设计方法进行研究 试验设计方法主要讨论如何合理安排试验以及如何分析试验所得的数 据等，例如，在工厂为了提高产品的产量，提高某有效成分的回收率，改善 产品的质量而进行的改变原料配比和工程条件的试验；为掌握作物取得最 高产量和提高产品质量所需要的栽培条件而进行的品种对比试验、旌肥方 法对比试验、农药效果对比试验等这些试验的目的都是要弄清楚试验过程 中自变量对于因变量的影响的大小和趋势，有时还要寻找其最佳条件 试验设计方法常用的术语和符号定义如下： 1 试验指标：是试验研究过程的因变量，常为试验结果特征的量 2 因素：指作为试验研究过程的自变量，常常是造成试验指标按某种 第二章实验设计简介 规律发生变化的那些原因如某些试验中的成分、温度等常用a 、b 、x 等 符号表示 3 水平；指试验中因素所处的具体状态或情况，又称为等级。如温度 用a 表示，则用下标1 、2 、3 、表示因素的不同水平，分别记为山、a 。、 a 3 、。可见，有的因素的水平是由数量决定，有的因素的水平是由特定的 质( 品种，名牌，产地等) 来决定 正交设计和均匀设计是目前最流行的两种试验设计的方法，它们各有 所长，相互补充，给使用者提供了更多的选择 2 1 均匀设计和正交设计简介 四十年代初问世的“正交试验法”是研究与处理多因素试验的一种科学 有效的方法，它用正交表安排多因素试验。正交试验法从农业生产中逐步推 广到各工业生产领域中去，取得了显著的经济效益。它在西方发达国家的广 泛应用，对促进其经济的发展起到了很好的作用特别需要指出的是：日本 在二次大战后，工业生产飞速发展的原因之一，就是在各工业领域里普遍推 广、应用正交试验设计技术正交试验法在我国6 0 年代开始使用，7 0 年代 在工农业生产中得到推广应用 正交试验设计包括两部分内容：第一，是怎样安排试验；第二，是怎样 分析试验结果这一方法具有这样的特点：完成试验要求所需的实验次数 少数据点的分布很均匀可用相应的极差分析方法、方差分析方法、 回归分析方法等对试验结果进行分析，引出许多有价值的结论。因此日益受 到科学工作者的重视，在实践中获得了广泛的应用 正交试验法利用排列整齐的表一一正交表来对试验进行整体设计、综 合比较、统计分析，实现通过少数的试验次数找到较好的生产条件，以达到 最高生产工艺效果正交表能够在因素变化范围内均衡抽样，使每次试验都 1 3 第二章实验设计简介 具有较强的代表性，而且正交表具备均衡分散和整齐可比性等特点，往往使 得试验能够较好或更好地达到目的 正交表是一系列规格化的表格，每个表格都有一个记号，如l 9 ( 3 4 ) 等， 其中l 表示正交表，9 是正交表的行数，表示需要做的试验次数4 是正交 表的列数，表示最多可以安排的因素的个数3 是因素水平数，表示此表可 以安排三水平的试验常用的有两水平的上8 ( 2 7 ) 、l 4 ( 2 3 ) ，三水平的l 9 ( 3 4 ) 、 l 。，( 3 ”) ，还有四水平、五水平的l 1 6 ( 4 5 ) 、l 2 5 ( 5 8 ) 等，另外还有水平不等的， 如上8 ( 4 3 4 ) 、工1 8 ( 2 3 7 ) 等正交表的特点如下： ( a ) 每列中数字出现的次数相同； ( b ) 表中任意两列数字的搭配是均衡的这种均衡性是一般正交表构造 的特点，它使得根据正交表安排的试验，其试验结果具有很好的可比性，易 于进行统计分析正交设计的直观分析可以给出试验指标y 随每个因素的 水平变化的规律 均匀设计则是舍弃“整齐可比”特性，而让试验点在试验范围内充分咄目 匀分散”，即单纯从均匀性考虑的试验方法它可以估计回归模型中涉及因 素的主效应和交互效应，适用于多因素多水平试验，它所使用的均匀设计 表在选用时有较多的灵活性例如，一项试验若每个因素取4 个水平，用 l ，o ( 4 5 ) 来安排，只需作1 6 次试验，若取5 水平，则需用l 2 5 ( 5 6 ) 表又如在 一项试验中，原计划用均匀设计u 矗( 1 3 5 ) 来安排五个因素，每个因素有1 3 个水平后来由于某种需要，每个因素改为1 4 个水平，这时可用u 矗( 1 4 5 ) 来安排，试验次数只需增加一次均匀设计的试验次数随水平增加有“连续 性”，而称正交设计有“跳跃性” 2 2三次设计简介 三次设计方法是2 0 世纪7 0 年代日本田口玄一博士创立的其基本思想 1 4 第二章实验设计简介 是将正交试验、信噪比、质量损失函数、正交多项式回归等概念和方法应用 到新产品、新工艺的设计与开发中去田口方法既适用于产品设计、科学试 验、技术革新、工艺改革等开发性领域，也适用于质量评价和质量改进等方 面它是一种注重技术与经济相结合，以求取得高质量、低费用，达到提高 经济效益的优化设计方法此法一经提出，就在日本的电子、化工、冶金、 汽车和纺织等行业广泛应用此后，很快传入美国、欧洲和我国吼 田口试验设计有如下特点： 1 是一种分部设计法，可用较少的组合评估较多的试验因素； 2 其因素数可达3 1 个，水平数可达5 个，可进行混合水平的设计； 3 它的试验阵列正交，可独立评估因素影响； 4 它将信噪比s n ( 通信电子领域的测量指标) 的概念导入设计中； 5 它可分为静态设计和动态设计两种，又可分成试验性项目的三次设 计和可计算性项目的三次设计 田口设计与均匀设计的比较： 均匀实验设计是一种新兴的试验设计方法，是我国统计学家方开泰和中 科院院士王元首创的，是处理多因素多水平试验设计的一种好方法。其特点 是用较少的试验次数完成复杂的试验设计其试验次数等于最大水平数，而 不是与实验水平数呈平方关系，试验次数仅与需要考察的因素数有关均匀 设计的操作流程如下： 1 先选出试验的关键因素，并确定各因素的取值范围及水平； 2 根据“均匀设计”选出适当的“试验表”； 3 按照表格规定的顺序做试验； 4 用电脑分析数据，算出该试验的数学模型、优化条件及优化结果 田口设计与均匀设计是目前比较流行的两种试验设计的方法，它们各 有所长，相互补充 1 5 第三章遗传算法在三次设计中的应用 田口博士认为，无论设计一个新产品还是一种新工艺，都可以分三个 阶段进行：第一阶段一一系统设计，提出初始设计方案；第二阶段一一参数 设计，探求参数的最佳搭配，提高产品性能的稳定性；第三阶段一一容差设 计，对关键件给以合适的容差范围田口方法在我国机械、电子、化工、光 学等行业都得到了应用，充分体现了田口方法的先进性、可行性和有效性。 三次设计的基本方法与步骤： 系统设计( 第一次设计) ：即功能设计，是指技术人员利用专业知识与 技术，对某性能的产品的整个系统结构进行的设计例如：化工生产过程选 择什么样的原材料和工艺路线、采用什么加工工艺等系统设计的质量取决 于专业技术的高低系统设计是整个设计的基础，它为选择需要考察的因素 和待定的水平提供了依据 参数设计； 三次设计的核心是参数设计，其目的是求出参数水平的最 优组合，使产品有稳定的性能它和一般的因子设计不同之处在于把误差因 素引进了设计中参数设计是一种非线性设计，它运用正交试验、方差分析 等方法来研究各种参数组合与输出特性之间的关系，以便找 x 第三章遗传算法在三次设计中的应用 3 1 遗传算法在气体换向装置的三次设计中的应用 三次设计的核心是参数设计，它在系统设计的基础上，决定这些系统中 各参数值的最优水平及最佳组合，尽量减少各种干扰的影响，使产品输出特 性波动小田口方法用两个正交表来安排试验，可控因素被安排在内侧正交 表上( 称为内表) ，而误差因素被安排在外侧正交表上( 称为外表) 设内表、 外表分别用正交表k ( r 5 ) 与三。) 表示，为了对内表上每一号试验( 水 平组合) 作出噪音影响分析，需要安排一张外表，总共需要n 张外表，要做 = m n 次试验，还要根据所得数据计算信噪比和灵敏度，再进行方差分 析因此田口方法的试验次数和计算量是非常巨大的。 1 9 9 9 年卢贤巨等【把均匀设计应用到三次设计中，即将内表与外表中 的正交表改换成均匀设计表，可以减少很多试验次数下面我们通过一个实 例来说明三次设计的具体方法与步骤，并给出遗传算法在两个实例的三次 设计中的应用 遗传算法( g e n e t i ca 1 9 0 r i t h m 简称g a ) 是模拟自然选择和基因遗传理 论的一种随机搜索算法它仿效生物进化与遗传规律，从某一种群( 初 始可行解集) 出发，利用遗传算子( 复制、杂交、变异) 一代代优胜劣汰，最 后找出最优解 三次设计实例解决的具体方法、步骤 i ) 系统设计 某厂生产与制造的气动换向装置要达到如下特性指标： ( 1 ) 带动9 0 0 n 左右的负载在一定的阻力作用下完成6 个转换动作，且 动作可靠、到位冲击力小、体积小、重量轻； ( 2 ) 在1 秒内完成最长距离的换向动作； ( 3 ) 在一定的压缩空气作用下，气耗量尽可能少 通过分析，认为在6 个转换动作中，最长的转换动作是关键，因此，设 1 8 第三章遗传算法在三次设计中的应用 计最长转换动作的基本结构，建立了力学模型( 如图311 ) 运动方程为 厂= 一 = 、( 昔a 2 b 一2 f ) g 9 ( 1 ) 式中各参数表示意义如下： ；换向末速度，望目特性值； a 换向活塞直径，待选参数； b ：汽缸内气压，待选参数； c ：换向行程，待选参数； f ：换向阻力( 取7 5 0 士2 0 n ) ； ：系统重力( 取9 0 0 士5 0 ) ； 9 ：重力加速度( 9 = 9 8 0 0 m m s 2 ) ； 本设计以换向末速度y 为所考虑的系统输出特性，目标特性值“o 9 6 0 m m s ，输出特性值y 是可计算的，式( 1 ) 是系统设计公式。 i i ) 参数设计 待选参数a 、b 、e 为可控因素，参数设计的具体步骤如下： ( 1 ) 可控因素水平表，如表3 1 1 所示 1 9 复三主重焦差鎏垄三盗选盐生塑堕旦 2 u 因素及水平a n n m l口f m p 0 1a f m m l 1 2 222 5 2 22 42 65 6 32 63 06 0 图3 1 1 可控因素水平表 这是3 因素3 水平的试验，且不考虑交互作用，因此可用正交表_ l 。( 3 4 ) 安排试验。安排可控因素的表称为内表，相应的设计称为内设计。本题的内 表为l 9 ( 3 4 ) ，内设计的试验结果见下页表31 2 。 因素 abge 叩( d b ) 试验号 234 llll5 5 7 9 2221 6 6 4 313332 12 5 4 1231 5 5 1 0 2 3 1 2 03 9 3l22 3 1 8 31321 8 8 9 821 32 2 3 2 0 32l 2 4 5 1 m 1 3 4 3 4 63 9 9 75 1 0 75 0 4 7t = 1 6 8 2 6 m 5 9 0 85 9 3 55 6 6 85 8 7 1 s r = 2 6 3 1 4 j 6 5 7 26 8 9 46 0 5 35 0 0 8 8 7 0 61 4 5 21 5 0 81 5 8 r 2 2 2 6 2 8 9 79 4 68 6 3 表3 1 2 试验方案与结果表 笪三童垂焦笠鲨垄三盗丛盐! 堕堕旦 2 1 ( 2 ) 误差因素水平表 在本题中，换向活塞直径、汽缸内气压、换向行程均有误差，把这些误 差因素分别记作爿、b 、e 。，以与可控因素a 、b 、g 相区别。另外，换向 阻力和系统重力也是误差因素，分别记作f 、。误差因素47 、b7 、e 的 水平确定与内表有关，其确定方法是：设内表中某号试验的a 、b 、g 的条 件为a ：、b ：、q ，按三级品计算，假定它们的变化范围分别为鸽土o 1 、 b ：士o2 、q 士o 2 ，误差因素f 、的水平确定与内表无关，是由系统设 计确定的：f = 7 5 0 土2 0 、= 9 0 0 士5 0 误差因素水平表如表3 13 所示 因素及水平4 f m m lb f 彳p 0 1e f m m lf 。( n 、n 。( n 、 la ：一0 1 b 2 一o2q o2 7 3 08 5 0 2a ：日： q 7 5 09 0 0 3a ：+ 0 1 玩+ o 2暖+ o 2 7 7 09 5 0 表3 1 3 误差因素水平表 以内表2 中第l 号试验条件为例，如= 2 2 、b ：= 2 2 、晓= 5 2 ，相应 的误差因素水平表见表3 1 4 因有9 号试验，共有9 张误差因素水平表。 因素及水平 a b a f 7 n j 12 192 05 187 3 08 5 0 22 20225 2 07 5 09 0 0 32 2 12 4 5 227 7 0 9 5 0 表3 1 4 误差因素水平表 ( 3 ) 外设计 安排误差因素的正交表称为外表，相应设计称为外设计。本题选用正交 表厶8 ( 2 3 7 ) 作为外表按系统设计公式( 1 ) 对每张外表计算各号试验下 第三章遗传算法在三次设计中的应用 的输出特性值。例如，内表中第1 号试验的外表如表3 1 5 所示。 l 2 f a 7 13 f b7 1 4 f g 15 r f7 16 r 7 1789 1 llll1lli1 6 7 2112222222 9 9 3ll3333 3 33 8 0 4 l2l122 3 31 0 8 5122 2 33l l2 6 7 6l 2 331122 4 1 4 713 12 13 2 3 2 0 0 8l3 23 2 1 3 l3 3 6 9 l331 3 2124 1 2 1 0 21 133 2 210 1 1212l13323 8 2 1 2213221134 3 0 1 32 2 1 2 3l32o 1 4222 3 l2 133 4 8 1 5223123214 1 0 1 6231323121 3 6 1 7232131232 9 7 1 8233212314 6 5 表3 1 5 内表第1 号试验的外表表 由表3 1 5 第1 号试验知，各误差因素均取水平1 ，从表3 1 4 中查出相 应值为 a ：= 2 1 9 ，b ；= 2 o ，暖一5 18 ，f = 7 3 0 ，7 = 8 5 0 代入公式( 1 ) ，得 可=、( ；2 1 9 2 地。一2 7 3 0 ) 5 1 - 8 9 8 0 0 8 5 0 笪三主垫堡簦鲎查三达亟：! 土主盟堕旦 2 3 仿此可以算出其它各号试验的y 值，计算结果记入表31 5 的最后一列 中，由于表3 15 的第1 0 号、第1 3 号试验用公式( 1 ) 计算时，根号出现负 值，失去意义，所以假定一o 。 对于内表中各号试验的外表所计算的输出特性值共有9 1 8 = 1 6 2 个， 利用它们可以算出内表每号试验的信噪比，其结果记在表3 1 2 最后一列。然 后进行内表的统计分析得到最优工艺条件a 3 8 3 g 1 ，其输出特性值g = 9 9 7 。 文献【7 j 把均匀设计方法引入三次设计中，它把内、外表的正交表改换成 均匀设计表后可以大大减少试验次数，例如，上面的例题中，把内表岛( 3 4 ) 和外表l 1 8 ( 2 3 7 ) 分别换成砜( 9 6 ) 和“2 ( 1 2 “) 使试验次数减少为9 1 2 = 1 0 8 次 遗传算法在三次设计中的应用 回到上面讨论的气体换向装置的三次设计问题，其系统设计完全不变。 因参数设计是三次设计的核心，我们仅需应用遗传算法解答这个核心问题。 先把方程( 1 ) 中各因素4 、b 、g 、f 、对应改换成z l 、z 2 、z 3 、z 4 、z 5 ，于 是方程( 1 ) 、表31 1 、表3 1 3 可以表示成一个多元函数的优化问题： 厂i 一 可一 ( 。i jz 2 ，z 3 ，z 4 ，z 5 ) = 、( 詈z z 2 2 2 4 ) 茁3 9 z 5 v 其中，z l 2 1 9 ，2 6 1 ，z 2 2 o ，32 ，z 3 1 5 1 8 ，6 0 2 ，z 4 7 3 0 ，7 5 0 ，7 7 0 ) ， z 5 8 5 0 ，9 0 0 ，9 5 0 ) 本题是一个望目特性的三次设计，即要求函数= ( 。，z 。，z t ，z s ) 在定义域内的值环绕目标值9 6 0 为好。 传统的三次设计( 田口方法) 已作了介绍，它实际上是一个组合优化问 题。为节省试验次数和计算量，正交设计对多因素的试验一般只取2 水平和 3 水平。我们应用遗传算法就可以突破这种局限，各因素的水平可根据对应 因素的取值域的大小和需要增加到多水平。下面对本问题进行编码时就可 以看到这一点。 笪兰童垂堡差鎏垄三盗选盐主堕生旦 2 7 电阻r 1 ( n )r 2 ) 场( q ) 风( n ) 水平1 5 0 02 4 0 02 22 7 0 水平2 1 0 0 03 6 0 02 83 6 0 水平3 1 5 0 04 8 0 03 44 5 0 表3 2 1可控因素水平表 图3 2 1稳流器示意图 选用正交表l 9 ( 3 4 ) ，可以得到9 个不同的水平组合，参看表322 ：根据 电学原理，电流的输出为 r l k 。 ( 凰+ 2 凰) k 。 2 面再面丽一可旷 笪三主垂生薹鎏垄三盗选盐生堕生塑 2 9 从以上的分析结果可知，最佳的各可控因素水平组合的电流输出为 r l k 。( 兄3 + 2 r 4 ) k 。 9 一面再丽一面霜丁一 1 5 0 0 1 8( 3 4 + 2 3 6 0 ) 3 6 0 ( 1 5 0 0 + 2 4 0 0 ) 3 4 2 3 4 3 6 0 = 1 8 20 6 此结果比较接近目标值1 8 0 m a ，对应各个电阻值分别为 尺l = 1 5 0 0 q ，r 2 = 2 4 0 0 q ，兄3 = 3 4 q 、r 4 = 3 6 0 n 、k 。= 0 7 和k 。= 1 8 。 遗传算法在此例中的应用 类似地，根据遗传算法的基本内容与步骤，本问题的求解过程如下： 辜编码 根据各因素( 自变量) 定义域的不同特点，可以采用自然数编码方式， 具体做法为： r - ，r z ，风、r 4 、和k 。的取值为离散数值j o ，1 ，2 ，字符串长 m = 1 ，= 1 ，2 ，6 ，故变量( r l ，r 2 ，冗3 ，r 4 ，k 。，k 。) 的字符串总长 例如，( 1 5 0 0 ，2 4 0 0 ，2 8 ，4 5 0 ，o 7 ，1 8 ) 对应编码为( 2 ，o ，1 ，2 ，l ，1 ) 的一个染色体。 奉初始化种群 采用随机方法生成初始种群，种群的大小可以任意选定，此题取= 7 ，用随机方法生成= 7 的个体作为初始种群。 毒选取适应值函数 本题目标函数和适应值函数取为 ， ) = j g 一1 8 。j j 石淼一生璺等一1 8 。| = m i n 第三章遗传算法在三次设计中的应用 遗传操作 1 ) 复制：本题选用最小适应度个体代替最大适应度个体的方法 2 ) 杂交：本题选取交换概率为p c 一0 8 ，采用单点交换法。对于字符串 总长工= 6 的上述编码，具体交换做法为：首先产生l 到一l 之间的一个 随机整数t ，然后将两个交换的字符串x ，和尥从第1 个字符后的所有字 符进行交换。 3 ) 变异：变量兄，、嘞、兄3 、r 4 、k 。和k 。对应的染色体基因位值 的 变异用2 一i 代替的方式 按照上述求解过程，对随机生成的初始种群( 一7 ) 进行遗传操作， 取p c o8 ，p 竹。= 0 0 5 ，迭代7 次得到本题的较优解= 1 7 96 9 6 ，其对应 参数组合为：冗l = 1 5 0 0 n ，兄2 = 2 4 0 0 n ，岛一2 2 n 、凰= 3 6 0 n 、k 。= 0 8 和 k 。= 1 9 。 根据上述两个实例结果分析，可得以下结论： 1 遗传算法用于三次设计，简洁明了，省去了田口方法中的正交试验 设计、信噪比等繁琐的试验与计算。计算结果表明：初始种群用正交设计表 已有的1 8 组( 7 组) 数据更好一些，这是因为正交试验数据分布比较均匀 些；而随机生成初始种群的优点是可以完全脱离正交设计，更具通用性。 2 对于试验性项目的三次设计，由于产品的输出特性值与各因素间没 有确定的函数关系，因而遗传算法中的适应值函数较难定义。笔者建议先进 行正交回归设计或均匀设计，求出输出挣 生值与各因素( 参数) 之间的近 似数学表达式，用来定义适应值函数。 3 本文应用遗传算法讨论的两个参数设计问题，所得的最优水平 x 第四章遗传算法的其他简单探讨研究 虽然g a 在许多优化问题中都有成功的应用，但其本身也存在一些不 足例如局部搜索能力差、存在未成熟收敛和随机漫游等现象，从而导致算 法的收敛性能差，需要很长时间才能找到最优解，这些不足阻碍了遗传算法 的推广应用。如何改善遗传算法，使其更好地应用于实际问题的解决中，是 许多学者一直探索的一个课题。 4 1 正交均匀设计在遗传算法中的应用 针对简单遗传算法初始种群生成的随机性，可试将试验设计的优化设 计方法引入遗传算法，从编码开始，优化初始种群的选取。 1 g a 的基本编码简介 ( 1 ) 二进制编码：h 0 1 l a n d 在运用模式定理分析编码机制时，建议使用二 进制编码，但它不能直接反映问题的固有结构且精度不高，个体长度大，占 用计算机内存多； ( 2 ) g r a y 编码：将二进制编码通过一个变换进行转换得到的编码，其目 的就是克服h a m m i n g 悬崖的缺点； ( 3 ) 动态编码( d y n a m i ce n c o d i n g ) ：是当算法收敛到某局部最优时增加搜 索的精度，在全局最优点附近可以进行更精确的搜索，增加精度的办法是在 保证串长不变的前提下减小搜索区域； ( 4 ) 实数编码：对于问题的变量是实向量的情形，用这种编码方式，可以 直接在解的表现型上进行遗传操作，从而便于引入与问题领域相关的启发 式信息以增加算法的搜索能力； ( 5 ) 当问题的表示是树( n e e ) 或图( g r 印h ) 时，还可使用结构式编码。 第四章遗传算法的其他简单探讨研究 不管我们选用哪种编码方式，最初种群的选取还是具有随机性，而进化 结果和需进化代数直接取决于初始种群。所以我们有必要研究如何选取相 对“优势”的初始种群 2 正交试验设计在g a 编码中的应用一初始种群的正交生成 在解决优化问题之前，没有全局最优解的任何信息。为顺利找到它，使 种群在“可行域”内分布均匀，这样有利于保证种群中含较丰富的模式。将 正交试验设计方法应用于二进制编码中的思路有如下几种： ( 1 ) 针对二进制编码( o 一1 编码) 的特点，将编码视为构造2 水平的实 验设计方案，列数作为染色体长度的刻画；行数视为种群的容量的刻画首 先根据实际问题的需要，确定要描述问题所需“个体”的长度f ，视之为正交 表的列数；所进行正交试验的次数作为初始种群选取的个体数目一一群体 容量。其中二进制编码中的0 或1 分别取代正交表中的2 或l 如正交表 l 8 ( 2 7 ) ( 见表42 1 ) 1234567 11111111 21112222 31221122 4122221l 52l2l212 6 2 12 2121 7221112l 8 2212112 表4 ，2 1 正交表l 8 ( 2 7 ) 可用来描述需要二进制编码长为7 的某个问题以三8 ( 2 7 ) 作为参照 根据上述的思路，可以得到如下8 个个体： 3 2 第四章遗传算法的其他简单探讨研究 s 1 = 1 1 1 1 1 1 l ；s 2 = 1 1 1 0 0 0 0 ；s 3 = 1 0 0 1 1 0 0 ；s 4 = 1 0 0 0 0 1 1 ； s 5 = 0 1 0 1 0 1 0 ；s 6 = 0 1 0 0 1 0 1 ；s 7 = 0 0 1 1 1 0 1 ；s 8 = 0 0 1 0 1 1 0 。 同上法，可先利用h a d a m a r d 矩阵法构造形如l 2 t ( 2 2 。1 ) 的2 水平正 交表，然后得到初始种群 ( 2 ) 对种群容量和染色体长度不满足关系n = z + l 的种群来说，同样 可借助构造相应的正交表来生成如：借助正交拉丁方来构造以素数为水平 数的正交表( 如l 9 ( 3 4 ) ，l z s ( 5 6 ) ) ，生成初始种群。以染色体长度2 = 4 且种 群容量n = 9 为例，初始种群选取思路如下： 查询对应的正交表l 9 ( 3 4 ) ，结果如表42 2 忆12 34 111l1 2l2 22 31333 42 1 23 522 3 l 62312 73132 83213 93321 表422 正交表三9 ( 3 4 ) 由于二进制编码的特殊性，如何将上表中的“3 ”替换为“o ”或“1 ” 成为关键。借助计算机随机生成一个值( “o ”或“l ”) ，替换“3 ”，且同时将 所有的“2 ”换作“0 ”，直至生成9 个不同的个体。 ( 3 ) 一般地，将每一维变量看作是一个因素，根据可行域的大小、维数以 及要求的求解精度，选择合适的正交表来安排生成初始种群。如果可行域比 较大，可将其划分为若干个子空间，各子空间的大小可根据经验随机选择， 第四章遗传算法的其他简单探讨研究 若初始种群按照正交设计的形式生成为 11 1 o0o 1o0 01l 0l0 l01 ool 1l0 同样地，取p c = o 8 ，尸= 0 0 5 ，用同一个程序实现，仅经过3 次迭代 得到最优值，( 6 4 ) = 4 0 9 6 。可见正交设计在此例中有很好的应用效果。 3 均匀设计在g a 编码中的应用一初始种群的“均匀”生成 同上法，将编码视为构造2 水平的实验设计方案，列数作为染色体长度 的刻画；行数视为种群容量的刻画首先根据实际确定要描述问题所需“个 体”的长度，视为均匀设计表的列数；并选取适当的正交试验的次数作为初 始种群选取的个体数目一一群体容量这里值得一提的是：均匀设计表有自 己的使用表，所以可以更加灵活地选取试验次数，也即种群容量可以有更多 的选择余地。 下面给出一种简单的均匀选取初始群体的方法：设字符串由二进制字符 表示，字符串总长度为f c r o m ，对于任给个体z o ，1 ) “”， x 第四章遗传算法的其他简单探讨研究 j ，1 ，l c h r o m 3 ) ， i ，1 ，p o p s i z e ) ； d o o l d p o p 眠l c h r o m 3 + l d l r o m l 十2 】 = r a n d o m i n t e g e r ， o ，2 ) “1 ，p o p s i z e ) ； d o o l d p o p 【 i ) l c h r o m 】= r a n d o m i n t e g e r ， o ，2 ) ， i ，1 ，p o p 8 i z e ) ： m a t r i x f b r m 【。l d p o p 至此得到初始种群具体形态 x o l d p o p = 工h b l e o ， p o p s i z e ) ；x = 7 工h b l e o ， p o p s i z e ) ， 5 ) n e w c h r o m = t l e o ， p o p s i z c ) ， l c h r o m 扎 b c s t 0 = ；b e s t f 0 一 ) ；m a x r u n 8 = 1 溜= 9 8 0 0 ； * 以下给出循环程序 w h i l c _ m o 。r u n ss5 0 0 ，m 馘r u n s + + d o 【 z 眠1 - 、。! ! 二兰! 2 f c 打o m l 一1 d o x m ，2 = 2 o + 0 1 d p o p f i ，1 c h r o m l + 1 o 2 1 1 = 1 c h r o m l + 1 + l c h r o m 3 ： d o “1 ，p 叩s i z e ) “1 ，p o p s i z e ) 州邶”。3 + ( 妻。f d p 。p 【幻”2 n 一器z 3 】= 。3 + ( 。f d p 。p 【i ，州+ 2 “一) * 器 j = z c h + 2 亿l ，p 印s 。z e ) d o x 【 i ，4 】= 7 3 0 + + o l d p o p 口，1 1 + 1 】 2 0 ， i ，1 ，p o p s i z e ) d o x 口，2 = 8 5 0 + o l d p 。p 口，l c h r o m l 】 $ 5 0 ， i ，1 ，p o p s i z e ) 以上给出编码与实码的对应关系 ， o 一，卢一，7 一，“一，q j = a 6 s ( j 2 卢一2 p ) 7 + 9 q 一9 6 0 ； * 给出适应度函数 f o l d p o p = 7 1 a b l c o ， p o p 8 i z e ) 】； 3 7 掣 ，印妇 0 触 + 第而兰墨通胥若荽瑶爵吾斋罂塑覃建 等篓蠹垂嚣 i 登墓i 型i | | 冀毒训地丽蒋涔嫂烈【i ，翁丽鞲圳褂嚣藩赫蠹鐾囊。 i 鞠型j 秘斟削割引蟊曩羹裂鬻t l ? ”葡秘瘘翼籍毯j 熏矧鞲蠹蓍 受霸蓑一h 墅鼙鼹鲤菠；嚣鞠撼黼姗j j 窘j 瓣鞫彰翼 魏孽 缓雳络番 嘲商錾药；，搿税磐痂瓦厕懿迥黑鹫嚣辩；飘黧黼鞭i 蒯鹱疆黎囊嚣蕊鹤 西餮羹瓣撼， d i 洌辣j 搿撼羞；j 燃；裂r ，霉l ，疆。錾靖，嘴氆滔溺塔氆曩澎骡嬲目磊 珏纛黼l 驺趱嚣兹裟。 翼萋俐帑盘辩符嚣；麓冀划善孺辩魏帑致i 湛一“! 弛鲤霎秘糌警； 鞘萋i 0 ”；鼙g 一? l l 。测季女裂技洋群搿凝黯冀鞣n i i g 女# t ；馨弼紧 骜弱萋巍蹇j 鼙i 一h 勺，蠹i j 1 “i 垄；稽一j # 磊，终- “* 藕酣，一g i # 莩 囊；一女n j 霸矗掣雌搿艮田漏蠹登巍硝。妯鞠冀誉勰熊 j 涮阿 x 箜堕主垂堡簦鎏生基笪笪兰竖过堑塞3 9 i o = r a n d o m i n t e g e r ， 1 ，1 出r o m 一1 d o j m o i 】 = j m l i 1 ；j m l i = j m 2