遗传算法及其在机械工程中的应用

《遗传算法及其在机械工程中的应用》由会员分享，可在线阅读，更多相关《遗传算法及其在机械工程中的应用（7页珍藏版）》请在金锄头文库上搜索。

1、第16卷 第1期机 械 科 学 与 技 术Vol . 16 No. 11997年 1月M ECHAN ICAL SC IENCE AND TECHNOLOGYJan 1997张学良遗传算法及其在机械工程中的应用张学良 黄玉美(西安理工大学 西安 710048)摘 要 介绍了遗传算法的基本原理、 基本特点及对简单遗传算法的一些改进,简介了其在机械工程中的应用成果,并对其研究前景进行了展望。关键词 遗传算法 优化算法 机械工程中图号 TH122引 言 优化算法和程序是是当今计算机时代科学和工程问题研究中最重要的工具之一。 一个好 的优化算法应具备两个基本特征(设以求全局最大主峰为例):一是要找到主

2、峰而不是众多的次峰;二是爬峰速度要快。 此外,它还应具有通用性,最好能 用于 “黑箱” 问题的寻优。 最简单和万能的算法有两种,即穷举法和蒙特卡罗法1。 这两种基本方法在寻优过程中只 认当前最优值而丢弃其余,造成了大量的信息浪费。 针对这一问题的处理,人们发展了各种各样的优化算法,其中大多是以对目标函数性质等的先验知识为前提的,因而使算法变得复杂而 且增加了应用中的局限性。 如能有一种优化算法既可保留上述两种基本算法的简单和通用特 征,而又有高的寻优准确度和效率,显然是人们梦寐以求的。 遗传算法(GA)为此开辟了一条诱 人的道路。1 遗传算法的基本原理GA是基于自然选择和遗传机制,在计算机上模

3、拟生物进化机制的搜索寻优算法。 在自然 界的演化过程中,生物体通过遗传(传宗接代、 后代和双亲非常相象)、 变异(后代与双亲又不完 全相象)来适应外界环境,一代又一代地优胜劣汰、 繁衍进化。GA模拟了上述进化现象,它把 搜索空间(所求问题的解的隶属空间)映射为遗传空间,即把每一个可能的解编码为一个向量(二进制或十进制数字串或字符串),称为一个染色体或个体,向量的每个元素称为基因,所有 染色体组成群体或种群,并按预定的目标函数(或某种评价指标)对每个染色体进行评价,据其 结果给出一个适应度值。 算法开始时先随机地产生一些染色体(所求问题的候选解),计算其适 应度,据适应度大小对诸染色体进行选择、

4、 交叉、 变异等遗传操作,剔除适应度低(性能不佳)的 染色体,留下适应度高(性能优良)的染色体,从而得到新的群体。 由于新群体的成员是上一代 群体的优秀者,继承了上一代的优良性能,因而明显优于上一代。GA就通过这样反复地操作,收稿日期: 1996 05 24向着更优解的方向进化,直到满足某种预定的优化收敛指标。GA是一个重复的搜索过程,但这一过程并不简单地重复搜索,而是一个带着 “记忆” 的搜 索,算法本身使搜索不会向一个低的区域进化。GA就是靠着自身的这种 “导向”,不断地产生 新的个体,不断的淘汰劣的个体,从而进化到较高阶段或者说趋于收敛。2 遗传算法的基本算子和数学基础2. 1 GA的基

5、本算子GA具有三个基本算子,即选择、 交叉和变异。 (1) 选择(selection)算子选择用以模拟生物界去劣存优的自然选择现象。 它从旧种群中选择出适应性强(适应度 高)的某些染色体,放入匹配集,为通过染色体交叉和变异产生新群体作准备。 选择只能从旧种 群中选择出优秀者,但不能创造出新的染色体。(2) 交叉(Crossover)算子交叉用以模拟生物进化过程中的繁殖杂交现象,它通过两个染色体的交叉组合来产生新 的染色体,即匹配集里任选两个染色体(又称为双亲),随机地选择一个交叉点,通过交换双亲 染色体交叉点右边的部分,从而得到两个新的染色体(后代)。 交叉操作能够创造新的染色体, 从而允许测

6、试产生于搜索空间中的新点,它体现了自然界中信息交换的思想。(3) 变异(M utation)算子选择和交叉实现了GA的大范围搜索过程,而变异的目的在于增强GA搜索最优解的能 力。 变异用以模拟很小的概率随机地改变遗传基因的值。 若只有选择和交叉,而没有变异操作,则无法在初始基因组合以外的空间进行搜索,从而 使进化过程的早期就陷入局部解而中止进化过程,使解的质量受到很大限制。 通过变异操作, 可确保群体中遗传基因类型的多样性,以使搜索能在尽可能大的空间中进行,避免丢失在搜索 中有用的遗传信息而陷入局部解,从而获得质量较高的优化解。2. 2 GA的数学基础GA并不复杂,但却具有强大的信息处理能力。

7、Holland提出的图式定理在一定程度上对 此作了解释,从而奠定了GA的数学基础。 根据图式定理,在GA运算过程中,经过复制(即选 择)、 交叉和变异操作后,在第t= 1代中所包含的图式H的数量为m(H,t= 1)m(H,t) (f(H)?FA V) 1 -Pc(H)?(L-1) -O(H)Pm(1)式中,m(H,t)、m(H,t+ 1)为图式H在第t代、 第t+ 1代种群中的数量;f(H)为包含图式H 的染色体的平均适应度;FA V为种群中所有染色体的平均适应度;Pc为交叉概率;Pm为变异 概率;(H)为图式H的长度;OH为图式H的确定参数,又称图式H的阶;L为染色体长度。 图式定理是GA的

8、数学基础,上式说明了高适应度值、 长度短、 阶数低的图式在后代中至 少以指数增长包含该图式H的串的数目。3 遗传算法的实现 考虑如下优化问题:F=f(x,y,z),x,y,z 8, FR(2) 其中,x、y、z是自变量,可以是数值,也可以是符号。 每一组(xi,yi,xi)8 构成问题的一个解。84机 械 科 学 与 技 术第15卷所以 8 可看成问题所有可能解构成的解空间。F是实数域R上的一个实数,是解的优劣程度 或适应性的一种度量。f为解空间(x,y,z)8 到实数域R上的一个映射,要求有定义。 优化目标是寻找一个解(xo,yo,zo)8,满足F=f(xo,yo,zo) = max8f(x

9、,y,z)(3)这里假定求最大值(也可以求最小值)。 利用GA求解上述优化问题,其具体实现如下。3. 1 问题编码 在参数优化问题中,通常将各参数(即自变量x,y,z)用二制编码(也有用十进制编码的),构成子串,再将子串拼接成长串即基因码链。 研究表明,不同的串长,不同的码制,会对问题求 解的精度和算法收敛时间有很大影响。3. 2 初始个体选取(产生祖先)GA的初始个体选取,一般采用随机的方法产生,这有地能够代表一般性,从而实现全范 围(全局)搜索。3. 3 初始群体规模的确定 初始群体的规模即指群体中包含的个体数目N。 个体的多少将直接响GA的有效性。 个体 太少,GA搜索效果会很差,或者根

10、本找不到问题的解。 因为,太少的个体(即太小的群体)不能 提供足够多的采样点,从而减小了个体的多样性。 相反,若群体中包含个体太多,会增加计算 量,使搜索收敛时间增长。 研究结果,一般群体规模控制在N= 30200个体之间较为合适。3. 4 选择适应度函数,评价个体优劣 适应度函数用于评价各个体的性能优劣,指导GA搜索优化。 对于上述函数的优化问题, 可真接将函数本身作为适应度函数,即:F=f(x,y,z)。 某个体(xi,yi,zi)所对应的适应度Fi 越大,则表明其质量越好;反之则差。3. 5 交叉概率Pc的确定 作为GA的最显著特点之一,它的搜索过程是以一定概率Pc控制着交叉操作的频率,

11、Pc 太大,会使高适应度值的个体很快被破感激掉;Pc太小,搜索易停止不前。 一般Pc取0. 60. 9 间的值。3. 6 变异概率Pm的确定 变异是增强个体多样性的另一个因素,它可以有效地防止搜索在成熟前收敛;保证GA搜 索到空间的每 一区域。 变异是以一定概率Pm的方式随机产生的。Pm太小,不易产生的个体;Pm太大,又会使GA变成随机搜索,故一般取Pm为0. 0010. 01之间的值。3. 7 交叉断点和变异断点的确定二者均以随机的方式产生。3. 8 GA的终止判据的确定 目前,确定GA终止条件的主要判据有以下几种:(1) 判断GA进化是否到了预定的最大代数;(2) 判断GA是否已找到某个较

12、优的染色体;(3) 判断各上体的适应度是否已趋于稳定,而不再上升。4 遗传算法的特点94第1期张学良等:遗传算法及其在机械工程中的应用GA具有如下特点 (1) GA处理参数集合的编码,而非处理参数本身。(2) GA对函数f的限制很少,并不要示其连续、 可微。 函数f既可以是数学表达式等显函数,也可以是映射矩阵,甚至神经网络等隐函数,所以GA的应用范围极广。(3) GA同时搜索空间中的许多点,而非单点。 这种多搜索如同一张网罩上 “地形” 上,数量极大的个体同时在很多区域采样,极大地减少了陷入局部的可能性。 (4) GA使用概率规则指导搜索,而不是确定性规则,它可以有效地搜索有噪声的多峰值复杂空

13、间,从中找出期望值高的区域。(5) GA在解空间内进行充分的搜索,但不是盲目的穷举。(6) GA隐含着并行性。 虽然GA仅对每一代N个个体操作,但实际上即处理了大约N3个图式。 以上均为遗传算法的优点,当然GA也存在一些问题,包括群体大小选择,变叉和变异的 概率确定,进化代数的选取等,均无参考的标准,需根据具体问题具体确定,而且GA往往出现 成熟前收敛(过早趋同)或振荡现象等。5 对于简单遗传法的一些改进 针对简单遗传算法(SGA)存在的问题,研究者们提出了各种改进算法这些进基本上体现 在GA实现的方方面面。5. 1 对选择规则的改进SGA中的群体进化方式是针对个体的劣中选优,主要的进化手段是

14、杂交,后代替换双亲, 优良基因结构被杂交破坏的可能性较大,以致延缓群体性能的进化;SGA以适应度作为选种 的选择激励,若群体的适应度变化不大或过大,都会引起选择激励不足或波动,导致进化过程 过早收敛或发生振荡;各代群体中的最优个体未得到保护,劣质后代可能取代优良的双亲。 为 此,对选择规则进行了如下收进。(1) 个体等级为选择的激励的最差个体替换法将群体中各个体按适应度大小排序,并以其序号代表各个体的等级,用各个体的等级作为 选择激励,选取一对双亲,经交叉、 变异等过程繁殖两个后代,随机抛弃一个后代2或抛弃适应 度低的一个后代3,用另一个后代来替换群体中等级最差的一个个体。(2) 杰出个体保护

15、法4对于群体中适应度最高的个体,可直接进入下一代群体中,从而防止最杰出个体由于选择、 交叉与变异的偶然性而被破感激掉。 (3) 扫描窗最小适应度屏障法Fm in,对于本代中凡是Fi 1)到N个体的各同源基因码链作如下变异: 从高位到低位与最优个体用逐码比较,设比较到第n位出现二者不同; 这一同源基因码链的前(n- 1)位不动,而其余部分随机化。 自适应变异2 它是在选定了双亲进行杂交时,先以Hamm ing距离测定其双亲基因码的差异,根据该差异决定基后代的变异率Pm,若双亲的差异愈小,给定的变异率愈尺。 它可当群体中各个个体过 分趋于一致时,使变异的可能性增加,从而提高群体的多样性,增强算法维

16、特搜索的能力,而在 群体的多样性已以很强时,则减少变异率,以免破坏优良个体。6 遗传算法在机械工程中的应用简介由于GA的上述优点,GA在机械工和中的 用异常广泛。 在些仅简在介绍几个实例。 (1) 磨削参数优化7文献7将GA应用于磨削参数优化,从表面粗糙度、 加工误差和磨削诳率三个方面来建 立适应度函数,从而对染色体(磨削能数的编码串)优劣进行综合评价,取得了较好的效果。(2) 工艺设计中的应用8文献8将GA应用于工艺过程设计,为这一非结构化问题优化提供了新的思路,从而淡化了 工艺过程设计和生产计划调度间的界限。 (3) 机床挂轮组的最佳选择9机床挂轮组的选择是一个典型的多极值约束优化问题,至今没有有效的搜索算法,文献9用GA较满意地解决了这一问题。(4) 迟滞非线性系统参数识别本文将GA应用于如下迟滞非线性系统的参数识别。x+z=f(t)(4)z=K x- x zzn- 1-xzn(5)15第1期张学良等:遗传算法及其在机械工程中的应用其中,已知z