改进的精英保护策略遗传算法及其在十杆桁架优化设计中的应用

摘要:本文针对标准遗传算法存在早熟的问题，从两个方面进行了改进，首先采用了精英保护策略和自适应的交叉和变异算子，其次结合结构优化中的力学准则按照内力变化进行变异操作。最后将改进的精英策略遗传算法应用于十杆桁架结构，并同标准遗传算法相比较，结果表明改进的遗传算法是可行、有效的，而且收敛速度更快。

维普资讯

第 2卷第 1 4期20 0 8年 2月

结

构

工

程

师

Vo . 4,No 1 12 . Fb 08 e .2 0

S r cu a n i e r t trl u E gn e s

改进的精英保护策略遗传算法及其在十杆桁架优化设计中的应用孟超尹久仁童宏贻(湘潭大学土木工程与力学学院,湘潭 4 l0 ) 115

摘

要

本文针对标准遗传算法存在早熟的问题,两个方面进行了改进,从首先采用了精英保护策略和

自适应的交叉和变异算子,次结合结构优化中的力学准则按照内力变化进行变异操作.最后将改进其

的精英策略遗传算法应用于十杆桁架结构,同标准遗传算法相比较,并结果表明改进的遗传算法是可行,效的,有而且收敛速度更快 .关键词遗传算法,结构优化

I p o e iit S l c i n GA nd I s Ap ia i n m r v d Elt ee to s a t pl to ci n Tr s n Te— u s Op i i a i n De i n tm z to sgME NG h o YI irn T C a N Jue ONG Ho g i n y( ii E gn ei n e h n sC l g f i g nU ies y X a g n4 0, hn ) C v n ie r g a d M c a i o eeo a t nvri, int 1 5 C ia l n c l X n a t a l 1

A src T v r m epe tr o s pegn t l rh ( G, h a ua n fcec a b ta t ooec et rma e f i l eei a oi m S A) tec l l ige i yw si o h u m c g t c t i n m—p o e s t e flo n wo wa s Fisl eiit s lci n a d s r-da t d c o s v r a d mu a in o e a o r v d a h olwi g t y . rty, l s e e t n e a p e r s o e n t t p r tr t o f o

we e a o t d e o d y,i i e wih me h n c rtro h a e a re u t to o s me g n si h o r d p e .S c n l n ln t c a i sc i i n t e p p rc rid o tmu ain t o e e n c r— em o o c o d n o v rai n fi tr lf r e F n l s me a c r i g t a i t s o ne na o c . i a l o y,t e i r v d eiits l ci n GA s a pl d t h h mp o e lts ee to wa p i o t e e

tn—r s pt z t n d sg a d wa o a e t GA,t e fa i iiy a d r la i t fmo iid GA n e t s o i ai e in, n s c mp r d wih S u mi o h e sb lt n ei bl y o d fe i adt e s a c i g e f in y we e i r v d r m a k b y. h e r h n fi e c r mp o e e r a l c Ke ywo d g n t l o i m,sr cu a p i iai n rs e e i ag rt c h t t r lo t g t u m o

( )采用动态自适应技术,进化过程中调 3在

1概

述

整算法控制参数和编码粒度;

() 4采用非标准的遗传操作算子; 自遗传算法的完整结构和理论被系统地提出以来,多学者一直致力于推动遗传算法的发展,众 对编码方式,制参数的确定,择方式和交叉机控选理等进行了深入的研究,入了动态策略和自适引 ( )采用并行遗传算法 . 5

针对基本遗传算法存在早熟的问题,本文将在最优保护遗传算法的基础上引进一种自适应遗传算子来

改进算法搜索精度和效率,合力学准则并针结对结构最轻设计问题提出一种加快收敛的方法 .

应策略以改善遗传算法的性能,提出了各种变形的遗传算法( G, V A)其基本途径概括起来有下面几个方面: ( )改变遗传算法的组成成分或使用技术, 1 如选用优化控制,适合问题特性的编码技术等;( )采用混合遗传算法; 2收稿日期: 0 7— 8—1 20 0 3

2含精英策略的遗传算法自从遗传算法在求解实际问题中获得成功以来,人们就试图对其进行理论分析,以解释其为什

摘要:本文针对标准遗传算法存在早熟的问题，从两个方面进行了改进，首先采用了精英保护策略和自适应的交叉和变异算子，其次结合结构优化中的力学准则按照内力变化进行变异操作。最后将改进的精英策略遗传算法应用于十杆桁架结构，并同标准遗传算法相比较，结果表明改进的遗传算法是可行、有效的，而且收敛速度更快。

维普资讯

·

结构分析· 屏蔽字= 串长度 .

结构工程师第 2卷第 1 4期,,, J J其中,为个体编码 i

么有效 .韩炜…通过对遗传算法进行证明得出 简单遗传算法 ( G是不收敛的, S A)而含精英策略 (也称为最优保护策略 )的遗传算法是全局收敛的.下面将介绍此算法 .2 1目标函数的确定及优化 .

( )从 4 B两个父代个体中产生出两个新 2,的子代个体 4,规则如下: B, ①若=, A在第 i基因座上的基因 O则 个值继承 4的对应基因值, B在第 i个基因座上的 基因值继承 B的对应基因值;②若 Wi, A在第 i基因座上的基因=1则 个

工程中许多实际问题是根据所要求的具体情况来建立起计算模型 .通常目标函数中共有 m 个待确定的变量,一般计算模型如下:ia ri )( ) n x( n f as b ett ( )≤ 0 ( u j c g o i=1 Lm)

值继承 B的对应基因值, B在第 i个基因座上的 基因值继承 4的对应基因值;均匀交叉操作的示例如下:A: x%— -

优化即是在此模型空间中找到一组 (个 ) m参数,使 F为最小 (理想情况下为 0或最大 . ) 2 2算法的主要操作环节 .1 )编码

Af xY Y Y Y Y: Bf xY x, x Y x Y x:

B: yY YYY YY YYY

下面从模式的角度来讨论点杂交算子和均匀

杂交算子的优缺点:() 1由于点式杂交破坏模式的概念小,而从

为了实施交叉和变异操作,一般来说要对已选择出的个体进行编码,编码方案的选择是多种多样的,在很大程度上依赖问题的性质,一般采用二进制编码 . 2 )标准适应度函数的确定

在搜索过程中能以较大的概率保护好的模式,所以它的搜索模式数也较小 .这样,当群体规模较小时,其搜索能力会受到一定的影响 . () 2由于均匀杂交在交换位时并不考虑其所在位置,坏模式的概率较大,而它搜索到一些破从点杂交无法搜索到的模式 .这样,当

群体规模较小时,匀杂交的这些特性使其具有较强的搜索均能力 .

对于含有约束条件最优化问题的适应度函数,遗传算法通常采用罚函数的方法来处理 .对

有约束极小化问题的罚函数通常由解到可行性域的距离或对解的"正"略 (修策即迫使其进入可行域 )确定 .来3 )选择策略的确定

基于上述原因,当群体规模较小时,使用均匀杂交比较合适;当群体规模比较大时,而群体内在的多样性使得算法没有必要搜索更多的模式,这

在用遗传算法求解优化问题中,常采用的通是基于适应度比例的选择策略 .

时采用点式杂交会保护好的模式,从而使算法的 收敛较快 . 对于变异操作,二进制编码的变异算子非常简单,只是以一定的概率 P (异概率 )所选 变将取的个体每一次取反,即若是 1则变成 0若是,;0则变成 1, .

4 )杂交与变异算子对优化参数完成编码后就可以进行杂交和变异操作了,杂交的对象是一对个体中相对应的一

段基因,变异的对象是一个个体中的每一个基因.在二进制编码方案下,交操作有点杂交和杂均匀杂交两种方式 .点式杂交又可以分为单点杂交和多点杂交.单点杂交是随机地在两个父串上选择一个杂交点,后交换这两个父串的对应子然

完成杂交和变异操作后,用解码把二进制利还原成为十进制参数 . 5保护最优个体 )

在[, 问搜索适应度最差的个体, 1N]该个体位置处,上一代的最优个体替换掉目前种群用

串.多点杂交则是一次产生多个杂交点,后间然断交换父串的对应子串 .

中位于处最差的个体 .这样遗传算法就完成了一

单点交叉示意:A: 0 110 111 — 4: 0 110 111 1 1 0 1 I 1 0 1B: 『一日: 『 00 0 1 1 100 1 1 O 0 0 1 110 0 0 0

代的进化,到了一个新的种群 .针对新种群,得 重复上面的过程,即计算目标函数,确定相对适应度,择,选……直至满足收敛条件,可以得到需就

均匀交叉的主要操作过程如下: ( )随机产生一个与个体编码串长度等长的 1

要的结果 .

收敛的判断标准为

摘要:本文针对标准遗传算法存在早熟的问题，从两个方面进行了改进，首先采用了精英保护策略和自适应的交叉和变异算子，其次结合结构优化中的力学准则按照内力变化进行变异操作。最后将改进的精英策略遗传算法应用于十杆桁架结构，并同标准遗传算法相比较，结果表明改进的遗传算法是可行、有效的，而且收敛速度更快。

维普资讯

Sr cu a n ie r 12 No 1 tu trlE gn esVo. 4, .

'占≤

() 1

这里,占为一个事先给定的,常小的正数,非 其含义是在平均意义上实测曲线和理论曲线之间的差异允许值 .计算收敛的原则是所优化的参数既能

满足精度要求,要控制计算时间 .针对本又

式中,为群体中量大的适应度值; 厂为每代群 a体的平均适应度值;厂为要交叉的两个个体中较大的适应度值;要变异个体的适应度值;,/为 ck为惩罚系数 (数 )它的取值应视约束条件的重常,要性而定 .

文具体实例,收敛标准为连续 5代计算结果相差 o值小于 0 1且全部约束条件都满足时,明已收 .,说敛可停止运算 .

这里,定 m~m设 取 (, )间的值,可 01区就以对交叉和变异概率进行自适应调整 .其中,当

个体的适应度值高于群体平均适应值时,采用式 () 2和式( ) 3进行计算, m应取较小值, m和 以不超过050, .;宜当个体的适应度值低于群体平均适应值时,用式 ( )式 (进行计算,采 3和 5) m,和 m应取较大值, 以不小于 05为宜 . . 当适应度值低于平均适应度值时,明该个说体是性能不好的个体,它就采用较大的交叉率对和变异率;如果适应度值高于平均适应度值,明说该个体性能优良,对它就根据其适应度值取相应的交叉率和变异率 .可以看出,当适应度越接近最大适应度值时,叉率和变异率越小;交当适应度等于最大适应度值时,叉率和变异率的值为零 .交 这种调整方法对于群体处于进化后期比较合适, 但对于进化初期不利,为进化初期群体中的较因优个体几乎处于一种不发生变化的状态,此时而的优良个体不一定是优化的全局最优解,容易这使进化走向局部最优解的可能性增加 .为此,可以进一步地改进,群体中最大适应度值的个体使的交叉率和变异率不为零,分别提高 P以和 P ,这就相应地提高了群体中表现优良的个体的交叉率和变异率,得它们不会处于一种近似停滞不使

3改进的精英策略遗传算法遗传算法的参数中交叉概率 P和变异概率 P的选择是影响遗传算法行为和性能的关键所在,接影响算法的收敛性 .P直越大,个体产新

生的速度就越快;然而, P过大,遗传模式被破坏的可能性也越大,得具有高适应度的个体结构使很快就会被破坏 .但是,果 P过小,使搜索如 会过程缓熳,以致停滞不前 .对于变异概率 P如 ,

果P过小,就不易产生新的个体结构;如果 P 取值过大,那么遗传算法就变成了纯粹的随即搜索算法 .针对不同的优化问题,要反复试验来需确定 P和 P, 这是

一件繁琐的工作,而且很难找到适应于每个问题的最佳值 . 本文针对这个问题引进一种自适应遗传算子, P使和 P能够随适应度自动改变 .当种群各个体适应度趋于一致或者趋于局部最优时,使P和P 增加;当群体适应度比较分散时,而使

P和P .减少 .同时,于适应值高于群体平均对

适应值的个体,对应于较低的 P和 P, 使该解得以保护进入下一代;而低于平均适应值的个体,结合个体违反约束的情况给与相对较高的 P和P使该解被淘汰掉 .因此,,自适应的 P和 P

前的状态 .为了保证每一代的优良个体不被破坏,采用精英策略,使它们直接复制到下一代中. 经过上述改进, . P P和计算表达式如下:P= P— :—.—

能够提供相对某个解的最佳 P和 P .通过自 适应遗传算子使算法在保持群体多样性的同时,保证遗传算法的收敛性 . 通过对精英策略遗传算法中的 P和 P 按上述思想进行改进,得算法中的 P使和 P按如下公式进行自适应调整: 厂P.

:——::: !:: !—:

, () ≥ 6() 7

P=P 2 1+ )厂< ( c一

≠ Jnx l a

Ja g v

/() 9

P: P 1 1+ ) f< ( c() 2 () 3() 40. 01 0 .

式中, P,=0 6,P2=0 3 . . .,P,:0 0,P 2: .5 m 当P>0 9时, . .;>0 1 P . P=0 9 P .时: 01 ..与经典自适应交叉和变异算子相比,本文对

=m ( 2 1+k)厂<厂 c a/

经典自适应算子做了如下变动:在经典自适应算子中厂< a和f< a时,厂 f 其交叉和变异率取定值

P=m ( 4 1+k) cf<f a

() 5

摘要:本文针对标准遗传算法存在早熟的问题，从两个方面进行了改进，首先采用了精英保护策略和自适应的交叉和变异算子，其次结合结构优化中的力学准则按照内力变化进行变异操作。最后将改进的精英策略遗传算法应用于十杆桁架结构，并同标准遗传算法相比较，结果表明改进的遗传算法是可行、有效的，而且收敛速度更快。

维普资讯

·

结构分析·

结构工程师第 2卷第 1 4期图中, L=914m各杆截面积 (~ ) 4 m, .的下限

P和 P本文根据此时个体违反约束的程度对 ,其乘以一个系数 ( ( )式 ( ),其也能自式 7和 8 )使 适应调节,如果个体违反约束越严重,其交叉和变异率也越大 .通过将上述的交叉和变异算子引入

均为 06 5c .4 m .杆件离散变量集为{ .4 6 0 6 51,1. 3 6. 5 6, 1 9, 9. 5,2 8 9 5 5, 41 2. 1 35 5.,

3 2 8, 2. 5

4 93, 51 1 1. .6 3, 7 0.9 9 5, 6.7 4,1 9. 7, 1 . 7 0 6 7 41

前面介绍的最优保护遗传算法,就形成了本文改进的精英策略遗传算法.

95 148 8 1706,0 . (位为 c . 3, 5 .3, 8 .9 200}单 m )1

4用于结构最轻设计的改进遗传算法加快收敛策略通过前面对基本遗传算法引进精英保护策略和自适应交叉,变异算子,使得算法收敛性能得到大大改善 .在结构优化设计中,了进一步加快为算法的收敛速度

,文结合结构优化方法中力学本准则对遗传算法中的变异这一操作做一下改进 . 我们以结构的最轻设计为例,般来说此时一的目标函数是设计变量的递增函数 .按照力学准则,最优设计的结果中,在最小设计变量对应的杆件应该是在所有杆件中所受的内力最小而且应力

:『 )P P1 .

图 1十杆平面桁架不意图 Fi 1 S th o e tus g. kec ftn—r s

目标函数为

w ) 1+ (:[ 2++ 3 4+ 5+ 6+√ 2 ( 8+ 7+ 9+ o] 1 ) sbet o .[] u jc t≤ U j≤ l J uXi∈ S

接近容许应力的杆件.在遗传算法中,这个设计变量对应与个体染色体串的一段基因,以为了所在进化过程中反应这种思想,文作者在算法中本增加了如下操作:在选择操作后,对个体解码计算出结构各杆内力,过比较得出最小内力杆件;通然后在变异操作时将此杆件对应变量的基因用本个

式中,为各杆件在力作用下的应力,]为各 [ 杆杆件容许应力,, u为桁架 J点在力作用下的位节移,u为容许位移,为杆件离散变量集 .[] s根据上面的优化模型,文用 MA L B编写本 TA

体所有变量值中最小处的基因替代 .为了是说明此操作,现举例如下:设结构有 3假

了上述问题的改进遗传算法程序,通过了调试 .并 在初始参数 N= 0, 0 3,= .8下得到 6 P: .6 P 0 0表1 十杆平面桁架优化结果杆件截面积/m c

个设计变量(,,, )选取一个体o1, 11 2 3

(横线优化结果,表 1见 .T b e 1 Op i z t n r s l o e -r s a l t mi a i e u t ft n tu s o

上部为染色体串,下面为对应的变量 )这个体表示,变量的值为离散集中第 4011个元素;的值 ( ) 为离散集中第 3010个元素;的值为离散集中 ( ) 第 711 ) ( 个元素,<< .通过分析最小内 0 力对应的杆件为杆 3所以其对应的变量处的一,段基因应被最小变量处的基因替换, 110-即 -+ 01, 0变异后的个体为 011010010 .

杆件号

连续变量文献[ 2]方法文献[] 3方法0. 4 6 5

离散变量未改进遗传算法0. 4 6 6 51

本文改进方法1 9 55 . 3

1

(. 4 )6 5

23 4 5

1 6. 5 78 0 8. 7 1 0. 5 9 1 71 2. 0 65 .4 1 17 . 4

16 5 6 .17 4 0 . 1 5. 7 7 1 0 3. 3 (. 4 )6 51 1 2. 4 8

1 70 5 8 .91 19 5 4 .3 2 0. 0 0 6. 1 4 5 1 955 . 3 1 .3 41 9 5

1 7. 9 8 0 59 7 4 6. 7 1 4. 3 5 8 8 19 55 . 3 19 55 . 3 1 19 5 4 .3

5算

例

6 7

十杆平面桁架 ( 1有 6个节点,0个设计图 ) 1变量,

料是铝 .E=6 6 aP=2 5 .8材 890MP, 710 6N/m .全部杆件的许用应力为,

8 91 ( )

8 .2 17 0 6 5 . 48 . 1 0 9

8 3 2. 7 06 5 .49 .2 1 7

51 6 3 .1 0. 4 6 6 5 11 7. 9 8 0 5

5 . 28 1 61 1 93 . 551 1. 3 4 9 5

±124MP, 2 7 . a在

结构重量 2) 7 . 2 1 . 2 4 . (8 8 7 25 57 67 4 5注:量单位为 N.重

2 8 . 28 2 6

号和 4号节点作用有向下的 44 8 N的集中 4 .9k力,动节点向下方向的位移允许值为 5 . m,可 0 8m

表 1中文献[]文献[]用的是连续变 2和 3使

摘要:本文针对标准遗传算法存在早熟的问题，从两个方面进行了改进，首先采用了精英保护策略和自适应的交叉和变异算子，其次结合结构优化中的力学准则按照内力变化进行变异操作。最后将改进的精英策略遗传算法应用于十杆桁架结构，并同标准遗传算法相比较，结果表明改进的遗传算法是可行、有效的，而且收敛速度更快。

维普资讯

Sr cua n ie r Vo. 4. . t trlE gn es 12 No 1 u

. 4. 3

Sr cua ayi t trlAn lss u

量,其基本思想都是采用基于力学准则和优化准则的方法,得出连续变量的结果,后对结果进先然行调整 .比较表中的数据,用没有改进的遗传采

遗传算法具有如下优点:( )编程简单,算过程仅涉及目标函数和 1计

算法得出的结果与本文改进后的方法得到的结果相差为 ( 67 4 5— 2 8 ./ 28 2 6= 2 4 . 28 2 6) 2 8 .

约束条件的分析比较,二进制与十进制的转换,约束条件不需要用设计变量的显示表示 . () 2算法搜索精度和效率较高,所得结果可充分满足结构的各种约束条件 .

1.%,文献[ 69与 2]所得到的结果相差为( 67 4 5—2 7 . ) 2 7 . 2 4 . 08 8 7/ 08 8 7=2%,文献 8与

[]得到结果相差为 (674 5—2 1 . ) 3所 2 4 . 2557/2 1. 25 5 7=1 .% .而本文方法所得的结果与文 88

献[]所得到的结果相差为 ( 2 8 .— 2 2 26 82 7 . ) 2 7 . 08 87/08 87=96,文献[]得到 .%与 3所的结果相差为 ( 28 2 6— 25 5 7/ 25 5 7= 2 8 . 2 1 . ) 2 1 .

16 .显然本文改进后的方法在搜索效率上要 .%优于未改进的遗传算法 .

通过将上表中数据应用结构计算软件 S P00进行校核, A 20所得各杆件的应力都小于规定限值.但得出的最大竖向位移,\咖[] 17文献 为6 . 2 63 3 3 2 2 2 2

2 4 6 8 10 10 10 6 10 0 O O O O 0 2 4 1 0 8 2 o

进化代数

图 2十杆桁架质量减小过程图 Fi. M a s rdu i r c s ft e tn—r s g2 s e cng p o e s o h e tu s

m文献[] 61 n,文方法为5 .7m m, 3为5 .3m '本 l 07 m,与问题给定的最大节点竖向位移是5 . m相比, 08m 文献[]出2 .%,献[]出05 .显然文 2超 16文 3超 .%

参考文献[i]韩炜. 一种全局一局部优化算法及其在桩基承载

献[] 2与文献[] 3由于将连续变量调整离散化,使其位移约束失效,使得结果成为不可行解.而采用本文方法得到的解则在可行域之内.

力反演中的应用[ . D]北京:中国地震

局工程力学研究所,0 0 20.

从本例十杆桁架结构重量减小过程( )图2来看,文改进后的遗传算法进化到 5时的优化本 0代结果便达到了未改进基本遗传算法的最优结果,而且收敛过程快,具有良好的稳定性 .得到的最

[2]李敏强, 寇纪淞,丹, .林等遗传算法的基本理论与应用[ . M]北京:科学出版社,0 2 20 . [3] S h i LA,asi .S m p rx a o ocps cm t F r h B o eapoi t ncn et m i f t c rl ytei[] IA J 17,2 2: o s ut a snhs J .A A ,9 4 1 ( ) r r u s1 4— 02 9 2 .

优解的质量也明显好于未改进得基本遗传算法 .

[ 4] D b sM W, e o . A piao fot a t ob N l nR B p l t n o pi ly s ci m i

5结

论

ci r uo td sutrlds n J .A A J re at at e t c a ei[] I A, ti o ma r u g1 7,4 1 ) 3 1 1 . 9 6 1 (0:1— 8 3

由以上算例结果及分析可知,用本文改进采(上接第 2 9页)

3结

论

参考文献[1]黄诚驹. A/ A实用教程[ . C DC M M]北京:电子工业

从目前我国各设计院的实际发展情况来看, 结构设计一般还是使用二维 C AD系统,维工程二

出版社,00 20 .

[ 付永忠 .oi o s0 3 C M w rs用技术精粹 2] Sl w r 2 0/ A ok实 d k[ .京: M]北科学出版社,0 3 20. [ 简诚颖. oMo wok——工程师的设计分析工 3] c s s rs/具[] C D C M与制造业信息化,06 z ) J.A/A 20 ( 1 .『 Sl Wok. sr Sm n a rv i 0 6 . oi 4] oi rs U e ' aul(eio 2 0 ) Sl— d sn dwo k 2 06. r s, 0

图仍然是设计和分析的依据 .当需要对大型复杂结构体系的结构体系进行精细的有限元分析及复杂的施工模拟时,须首先建立复杂结构的三维必实体模型,能实现复杂结构体系的精细有限元才分析及施工过程的数值模拟,同时可以实现结构构件的自动加工过程 .

本文来源：https://www.bwwdw.com/article/0zi1.html