第47卷第3期
2011年2月
.机械
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
学报
JOURNALOFMECHANICALENGINEERING
V01.47NO.3
Feb. 201l
DOI:10.3901/JME.2011.03.141
工程约束优化的自适应罚函数
混合离散差分进化算法木
车林仙1,2程志红1
(1.中国矿业大学机电工程学院徐州221008;
2.泸州职业技术学院机械工程系泸州646005)
摘要:将离散约束优化问题转化为非负整数约束规划问题,开发求解该问题的离散差分进化算法。该算法采用基于混沌映射
的种群初始化、双版本变异和带随机扰动项的取整运算等新策略。针对非线性约束条件,给出惩罚基数的计算方法和连续映
射摹函数的表达式,在此基础上设计处理非线性约束的自适应惩罚因子。提出一种刻画种群多样性的新测度——种群二次平
均基因距离及基于新测度的依概率混沌移民算子。将自适应罚函数法、依概率混沌移民操作与离散差分进化算法有机融合,
构造面向工程约束优化的混合离散差分进化算法。对3个离散约束优化实例进行验证,结果表明,混合算法具有良好的鲁棒
性且优于离散粒子群算法。应用混合算法求解斜齿圆柱齿轮传动优化设计问题,结果优于遗传算法及其改进算法、离散粒子
群算法,目标函数值较遗传算法及其改进算法分别下降41%和10%。
关键词:差分进化算法离散约束优化 自适应罚函数基因距离混沌移民
中图分类号:THl22TPl8
HybridDiscreteDifferentialEvolutionwithaSelf-adaptivePenalty
FunctionforConstrainedEngineeringOptimization
. CHELinxianl,2CHENGZhihon91
(1.SchoolofMechanicalandElectricalEngineering,ChinaUmvemityof
MiningandTechnology,Xuzhou221008;
2.DepartmentofMechanicalEngineering,LuzhouVocationalandTechnicalCollege,Luzhou646005)
Abstract:Theconstraineddisuseoptimization(CDO)istransformedintoanonlinearconstrainednon—negativeinteger
programming(CNIP)whichcallbesolvedbytheproposeddiscretedifferentialevolution(DDE)algorithmthatadoptsseveral
improvementssuchasthechaoticinitializationofapopulation,thedouble-schememutation,andtheintegratingoperatorwith
stochasticperturbation.Aimingatthenonlinearconstraints,thecalculatingapproachesforthebasepenaltyandtheformulaforthe
basefunctionofcontinuousmappingarecarriedout,andself-adaptivepenaltyfactorsbasedonthesenotionsforhandlingconstraints
arepresented.Itisstudiedthatanovelmeasul:e,termedasaquasire-averaginggenedistanceforapopulation,isemployedtodepict
thediversityofthepopulationandchaoticimmigrationoperatorsdependingOnthismeasllreandtheprobabilityareimplementedto
preservethepopulationdiversity.Orientatingconstrainedengineeringoptimizations,itproposesanovelhybridDDE(HDDE)in
whichaself-adaptivemethodandachaoticimmigrationstrategyaredynamicallyincorporatediIItheDDEalgorithmtoimproveits
performance.Furthermore,threebenchmarkfunctionsinCDOfieldsaleutilizedtotestthisHDDEalgorithmandtheresultsshow
thatthenewapproachisrobustandefficient,andismoreoptimalinobjectivefunctionsthanthediscreteparticleswarmoptimization
(DPSO)algorithm.Finally,thisworkalsousestheproposedalgorithmtooptimizethetransmissiondesignofhelicalgearreducers
anditsobjectivevalueisbetterthanthoseobtainedbygeneticalgorithm(GA),improvedGA(IGA),andDPSO,ete.,andhas
decreasedby41%and10%comparedwithGAandIGA.respectively.
Keywords:DifferentialevolutionalgorithmConstraineddiscreteoptimizationSelf-adaptivepenaltyfunctionGenedistance
Chaoticimmigrant
。四川省应用摹础研究
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
资助项目(2008JY0163).20100108收到初
稿,20100823收到修改稿
万方数据
142 机械工程学报 第47卷第3期
0前言
多数工程优化设计问题都属于离散约束优化
问题(Constraineddiscreteoptimization,CDO)。比如
齿轮的齿数与模数、螺纹的螺距与直径、弹簧的圈
数与簧丝直径等参数均为离散变量;而齿宽、板厚
等参数形式上是连续变量,但由于制造精度、设计
规范等工程实践的需要,最终的设计结果仍表现为
离散变量。CDO是
数学
数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划
规划和运筹学中最有意义,
但也是较困难的领域之一。
非线性约束优化的关键是如何处理约束条件
和搜索全局最优解。约束处理技术主要有两类:一
类是基于规则的方法,如DEBtlt在遗传算法(Genetie
algorithm,GA)中应用基于规则的联赛选择方法处
理约束条件,RUNARSSON等[21在进化策略
(Evolutionarystrategy,ES)中应用基于概率的随机排
序方法约束处理技术,这类方法通常较复杂;另一
类是罚函数法,如CHEN等【3。4】将传统罚函数法用
于GA,罗贤海掣5】则构造了适应于GA的综合罚函
数,PARSOPOULOS等【6】在粒子群算法(Particle
swarllloptimization,PSO)中应用非固定多段映射罚
函数法(Non.stationarymulti.stageassignment
penaltyfunctionmethod,NMAPFM)处理约束条件,
HE等[7-8]应用协同进化技术同时优化罚因子和目标
函数值,于颖等⋯oJ提出了基于传统外点罚函数法和
扩展Lagrange乘子外点罚函数法的PSO。YU等【lu
还设计了基于大值惩罚的离散PSO(DiscretePSO
basedonhugevaluepenalty.DPSOHVP),实为拒绝
不可行解的简单约束处理技术。以上罚函数法约束
处理技术仍存在易陷入局部最优的缺陷。另一方
面,STORN掣12J提出的差分进化算法(Differential
evolution,DE)是目前最受关注的全局优化方法之
一,已被成功应用于机器人最优路径规划【l3|、数字
滤波器设计【14J及控制系统设计【l51等诸多工程领域。
同时,研究者还将DE推广到CDO领域,如吴亮红
等Il6J构造了面向实数一整数混合规划问题的实数
一整数混合DE;而AL.ANZI掣171、WANG等[18】
则根据调度问题的特点,设计特定的变异算子,开
发了离散DE(DiscreteDE,DDE)。
面向工程实践的离散进化算法(Discreteevolu-
tionaryalgorithm,DEA)已成为优化领域中一个引人
瞩目的新方向【91。CHEN掣3】应用二进制编码GA
在离散空间内寻优,但求解高维优化问题时染色体
串很长,会降低搜索效率。于颖等【9】针对CDO构造
了带离散惩罚项的PSO,但仍在连续域内寻优;稍
后,她进一步研究了按离散格点索引号寻优的
DPSO【11】,但其大值惩罚技术使得该算法很难获得
全局最优解。本文借鉴YU等【ll】的思想,设计了面
向工程离散优化领域的DDE,并应用基于反馈混沌
化算法【l9】的种群初始化、双版本变异和扩大取整范
围等策略提高种群多样性。针对罚函数约束处理中
难于设置通用惩罚因子的缺陷,提出了免参数设置
的自适应罚函数法(Self-adaptivepenaltyfunction
method,SPFM),其惩罚因子可根据群体的适应度随
进化过程自动调整。研究了评价种群多样性的新测
度——种群二次平均基因距离,当该测度小、种群
多样性差时,对种群实施依概率的混沌移民操作,
使其逃离局部最优区域,以克服早熟收敛。将以上
新策略有机融合,构造了面向工程离散约束优化的
自适应罚函数混合离散差分进化算法(HybridDDE
withaself-adaptivepenaltyfunction,HDDESPF)。最
后,应用3个Benchmark问题和1个工程设计实例
测试了新算法,结果表明该方法的全局优化能力和
计算鲁棒性等均优于文献中报道的离散进化
算法。
1 离散约束优化问题的数学模型
不失一般性,本文考虑最小化CDO
rain厂(x) ’
S.t.x=(xlx2⋯XD)1∈.仃
xd∈厂d={舻’I办=0,1,⋯,na;
x(o)
o),
因此,该问题共有伽l+2m2)个不等式约束。
若记离散变量集合乃所有元素的上标集为昌=
{0,l,⋯,Hd}(d=l,2,⋯,功,则CDO式(1)可转化为
万方数据
2011年2月 车林仙等:工程约束优化的自适应罚函数混合离散差分进化算法 143
非负整数约束规划问题(Constrainednon-negative
integerprogramming,CNIP),其等效解空间为伊
n2.巨d,等效寻优变量为Jf=(,lj2⋯如)T∈p
(妇∈昌,d--1,2,⋯,D)。若Xd为等间隔离散变量,设
其间隔为Axd,下限为Xd,rffm,则舻’飞Inin0心妇;
若勤为非等间隔离散变量,则建立其数据列表,通
过上标号后检索相应的离散值舻’。因此,寻优变
量J『与设计变量x具有一一映射关系,称非负整数
矢量j『为离散优化变量工的编码,记作户P∽;反
之,称X为.,的解码,记作x=e-1(Jf)。
2 自适应罚函数混合离散差分进化
算法
2.1离散差分进化算法
将DE改进为在非负整数空间p内寻优的
DDE,即可求解CNIP。DDE与DE类似,初始化
种群后,仍应用变异、交叉和选择等进化操作生成
新一代种群,只是前者采用整数编码,而后者采用
实数编码。DDE的3个控制参数为种群规模‰。、
缩放因子F和交叉因子P。。进化至第“户l,2,⋯,T,
r为最大进化代数)代的个体为筇’=(J;::{;j⋯(t:
⋯Z岛)T∈矽(扫l,2,⋯,‰);按DE的变异操作
生成变异个体五HD=暖r丑≯⋯露苫’)T,对
之取整得∥件D=(五,’Z:≯1’⋯矗苫D)7;父代个
体筇’与变异个体∥¨D交叉,生成试验个体
露o“’=(殿+1’粥“’⋯歹黪1’)T;个体筇’与片o“’
竞争得新一代个体.,:Hn。本文应用混沌算法生成初
始化种群,并采用双变异策略和带随机扰动项的取
整运算,其基本思想描述如下。
2.1.1混沌初始化种群
文献【l9】研究了一维反馈混沌化Logistic映射
y滑1’=4=∥0(1护)+(4+e4bp(mod1) (2)
式中孝——离散时间序列,釉,1,2,⋯
.∥o)——混沌迭代初值,≯o)∈(o,1)
由于混沌序列式(2)的Lyapunov指数为
4.0704【19】,即其混沌运动强烈,具有良好的遍历性,
因此本文应用反馈混沌化算法生成DDE的初始种
群。DEB[1】应用GA求解约束优化问题时,提出了
联赛选择中的3条规则。
(1)可行解个体总是优于不可行解个体。
(2)对于两个可行解个体,目标函数值越小越
优秀。
(3)对于两个不可行解个体,约束违反度越小
越优秀。
本文应用DEB规则评价混沌序列(个体)优劣。
对于不可行解个体,定义其约束违反度为
工(工)=∑(gf(x))地‘枷 (3)
i=1
fmax{0,毋∽)i=l,2,⋯,ml
⋯。
【lIll《功Ii=ml+l,ml+2,⋯,ml+m2
f1口.rx、<1
r(qA工))212q”一1i(x)>1l二 ■
基于混沌序列的群体生成算法如下。
算法l:混沌群体生成算法。
(1)在(o,1)范围内随机初始化矢量,)-
(一∞谬’⋯鳄’)T,置@。
(2)由式(2)分别迭代生成矢量Y({+1)=
(订纠’y笋“’⋯蟛+1’)T的各维分量,并映射为非负
整数矢量(个体)P‘纠’=(矗纠’硝“’⋯p苫“’)T。其
取整映射为
∥“’=L(1+nd)蟛+1’Jd=l,2,⋯,D (4)
式中,L.J为下取整运算符。
(3)将个体扩1’映射为离散设计变量妒n,即
xpl)-e_1p@1’),再计算其目标函数值(若x伊1’为可
行解)或约束违反度(若工舻1)为不可行解)。
(4)若孝<舌。一1,则乒《斗l,转步骤(2);否则,
执行步骤(5)。
(5)应用DEB规则评价p=-∥n,∥孙,⋯,p‰“’},
并按优劣排序得P=伽“n,p“孙,⋯,P“缸x’}。
按算法l生成‰个混沌序列尸后,从中选择
前面的M砷个优秀个体组成初始种群。根据实践经
验,
建议
关于小区增设电动车充电建议给教师的建议PDF智慧城市建议书pdf给教师的36条建议下载税则修订调整建议表下载
取毒一=(100~300)M,0p。
2.1.2双变异策略
本文采用双变异策略,以此提高种群的多样
性。对于DE/rand/1策略,变异个体五H”的基矢量、
差分矢量由3个互不相同的父代随机个体硝’,Z:’,
殷)组成。DE/rand/1策略未利用任何父代适应度值
信息,有利于保持种群的多样性,其全局搜索能力
强,但收敛速度慢。对于DE/best/2策略,变异个
体五Hu由最优个体础作引导,因而局部搜索能力
强,精度高,收敛速度快,但会加大算法陷入局部
最优点的可能性。因此,生成新一代变异个体五H1)
时,以概率p(∈[O,1】)按DE/rand/1策略执行变异,
而以概率(1叩)按DE/best/2策略执行变异,这样既
能提高算法的收敛速度,又能在一定程度上保持种
群的多样性。进化前期取较小的P,可保持较高的
收敛速度;而在进化后期取较大的P,可以增强全
万方数据
机械工程学报 第47卷第3期
局搜索能力。因此,P随进化代数线性递增较合适。
故本文的变异操作为
矽=怪篇:驾,嚣鬈刀舯抄p
k=-I,2,⋯,Ⅳ脚 (5)
式中,rand()为(0,1)范围内服从均匀分布的随机数,
每次引用采样一次;缩放因子F一般在(O,2】范围内
取值。
2.1.3带随机扰动项的取整运算
在DDE的进化过程中,仅有变异操作后可能
出现小数,因此改进的关键是取整运算。本文定义
的取整运算为
矗∥=%(震+l’)k=-I,2,⋯,‰pd=l,2,⋯,D
(6)
式中,Di“·)为取整算子。
本文不采用传统的下取整,其具体运算法则
如下。
(1)若殁+l’∈【o,%】(扣l,2,⋯,Ⅳ聊;d=l,2,⋯,
肼,则
%(Z7)=
峨jo+刊i o≤删’一嵫刊≤o.1
忱刊+lo凰剃’一LI弘k,+1d’j<1
嵫+1)J+random(0,1)
o.1<强+l’一旧lk,州dJ<0.9
(7)
式中,random(0,1)为在0,l两个数中随机取其一,
每次引用采样一次。
当分量非常接近整数(距离不超过0.1)时,则取
与其最接近的整数;而当o.1%^d:;/=rmt[1,D】
k=-I,2,⋯,‰d=-1,2,⋯,D(9)
式中,‰[1,刎为{1,2,⋯,D)内的随机自然数。
(5)选择操作:对Z”与丘o“’按式(10)进行选
择操作得新一代个体
如+1) f刀o¨’ 咖(e-1(片o+1’))<中(e-1(Zo))
以
lZ‘’ 驴(e-1(露o+1’))≥驴(e-1联D))
扣1,2,⋯,Ⅳ脚 (10)
(6)更新最优个体:新一代群体中适应度最小
的个体为当前的最优个体_,-best(t+l’,即
I嚣’=argrain删舻(e。1(第“’))}磐(11)
,t
(7)终止检验:如果满足终止准则,则输出结
果并停止;否则,t=t+l,转步骤(3)。
2.2非线性约束的自适应罚函数处理
根据NMAPFMt61,可将CDO式(1)转化为如下
的无约束优化问题
roan少(x)=厂(x)+万u’五(x)(12)
式中,万‘%(D为惩罚项,万∽为随迭代代数t(t=l,2,⋯,
r)动态调整的惩罚力度,石∽为惩罚因子,其表达
式分别为
∥力=tC (13)
以扩大寻优范围。
(2)若五省’引o,%】(扣l,2,⋯,‰;庐1,2,⋯,式中
研,则
嘣Z口’)--Lrand()(1+naJ(8)
2.1.4离散差分进化算法的流程
根据上述分析,本文的新型DDE采用混沌初
始化种群、双变异算子及带随机扰动项取整算子等
策略,其基本流程描述如下。
算法2:DDE。
(1)设置控制参数:‰p,只风,P,To
(2)初始化种群:应用算法l初始化种群,通
过计算适应度多(矿1(Z∞))(烈·)的计算方法见第2.2
r,h+’,|2
‘(x)=E(吼(x))7‘嘶‘。"目(吼(x))(14)
i=l
卜惩罚强度指数,间.5~1.5
吠·卜分段映射函数
在实际应用中,须根据具体问题设置分段映射
函数战·),且优化结果对其值比较敏感。若函数值
过大,将导致过度约束,难以搜索到全局最优解:
反之,函数值过小,将起不到应有的约束作用,最
后收敛于违反约束的不可行解。为此,本文提出如
下的改进分段映射函数
口(z户,7(z)Z" (15)
式中 r自变量,z>O
∥——与原目标函数进化至第t代时的数量
万方数据
2011年2月 车林仙等:工程约束优化的自适应罚函数混合离散差分进化算法 145
级相当的惩罚基数,≯o>o
,7(·)——分段映射基函数
本文将第(f-1)代个体适应度绝对值的均值作为
≯r),即
产古笠I痧(e-I(∥))lt=l∥2”,T(16)
1’popk=l
在算法1生成的Ⅳ脚个初始个体中,若有不可
行解,亦须应用式(12)计算其适应度,本文将初始
个体原目标函数绝对值的均值作为≯∞,即
|o)-古笠肛1皑))l(17)
‘’pop‘2I
借鉴文献[6】设计分段函数的方法,将分段映射
基函数定义为
刁(z)=
1 z∈(0,0.001)
2 z∈[0.001,0.020)
5 z∈[0.02,0.10)
10 z∈[0.1,1.0)
20z∈[1,+oo)
通过大量试验发现,按上述方法设置分段映射
函数式(15)时能获得较好惩罚效果。因为约束问题
的优化解大多位于可行域的边界上,利用与原目标
函数值相当数量级的惩罚基数,有利于保留约束违
反度较小的不可行解,以便引导群体在可行域边界
区域搜索。为增强基函数的通用性和平’滑.性,进一
步将其拟合为单调递增连续函数
矛(z)=l+lb(1000z+1)2 (18)
式中,A为修正指数,2--1.5---,3.0。
分段映射基函数玎(·)3t其拟合函数牙(·)(取扛
1.5)的曲线如图l所示。由图l可知,两者的惩罚
力度相当,但后者更平滑。
图1分段映射基函数曲线及其拟合曲线
将式(18)代入式(15),再代入式(14),可得自适
应惩罚因子
矗(x):z(f)葛(gi(x))舭))×
{1+lb[10000(qf(x))+lr)t=l,2,⋯,T(19)
若应用NMAPFM,对于不同优化问题,须经
反复测试后才能设置合适的分段函数值;而应用本
文提出的SPFM,惩罚因子厶∽中的惩罚基数≯o
可随进化过程自适应调整,有效克服了前者的
不足。
2.3基于种群多样性测度评价的混沌移民策略
在进化后期,大量个体聚集在最优个体的附近
区域,此时个体间的差异很小,导致随机生成的差
分矢量趋近于0,使得新一代试验个体与该区域内
的父代个体差异很小。若该最优个体为一局部极值
点,则个体很难逃离其约束范围,直至种群整体汇
聚于该局部极值点上,因而引起算法早熟收敛。为
了改善算法的全局搜索能力,在进化后期必须避免
种群整体趋同,采用特定策略增加算法的多样性。
下面给出一种刻画种群多样性的新测度。
定义1:第t代种群中,称个体刀’与最优个体
艘.间的规范化Euclidian距离
O'kt)=
k=-I,2,⋯,^‰ (20)
为个体相对于最优个体的规范化拟基因距离,简称
基因距离。
定义2:第t代种群中,称所有基因距离的算
术平均值
,.Ⅳ"
厅ok÷∑∥ (21)^,‘一一 一 ’ ’
。’pop
k=l
为种群规范化平均拟基因距离,简称种群平均基因
距离。
定义3:第t代群体中,由基因距离小于种群
平均基因距离的所有个体组成的群体称为近优子
群,记作蹀。称.嘟中所有个体的平均基因距离
%_---(t)2南泛掣 Q2’
为近优子群规范化平均拟基因距离,简称种群二
次平均基因距离。其中,I跳I表示子群.蹀中的个
体数。
计算种群二次平均基因距离础时,未计入离
最优个体垲较远的部分基因距离,因此础可以
较准确地刻画.瑶的汇聚程度,是一种评价种群多
样性的新测度。础越小,种群向比汇聚的程度
越高,种群的多样性越差。若础≤,(,>o,为种群
汇聚程度阈值),种群将高度趋同,经变异操作后很
O
5
O
5
O—H—e释睡姐器工H一}籁懂整求
万方数据
机械工程学报 第47卷第3期
难产生新的个体,种群将停止进化,陷入局部最优
区域。
若种群陷入局部最优区域,则应用混沌算法的
遍历性生成新个体,依概率Pmig取代.咄中的个体,
在增加种群的多样性的情况下,保持原有的进化趋
势,本文称之为依概率的混沌移民操作。
2.4 自适应罚函数混合离散差分进化算法
基于SPFM和种群多样性新测度,将依概率
的混沌移民算子嵌入DDE中,形成了面向工程约
束优化的新型算法~HDDESPF,其基本流程描述
如下。
算法3:HDDESPF。
(1)设置控制参数:‰,F’P∞P,Z‰,£A,,,
pmigo
(2)初始化种群:应用算法1生成初始种群,
应用式(17)计算∥’,再应用式(19)、(12)计算
痧(c-1(Zo’)),并确定初始最优个体恐。置t--0。
(3)、(4)均同算法2。
(5)选择操作:应用式(16)计算≯州),再应用式
(19),(12)计算谚(e-1(矗‘H1’)),对筇’与片‘件1’按式(10)
进行选择操作得新一代个体露“)。
(6)更新最优个体:确定新一代群体中适应度
最小的个体最n,若少(e_1(盛1’))<函(e。1(础。)),则
删’=盛¨,否则j⋯(t+l’=砝。
(7)混沌移民:应用式(20)~(22)计算硝“),
厅‘H1’及o--opI(t+n。若磷1’<,,则按以下1)~3)执行依
概率的混沌移民操作;否则执行步骤(8)。
1)应用算法l生成5M,op个混沌序列(但按适应
度优劣排序)。置扣l,肛=0。
2)若o-(tt)<厅(‘)且rand()印mig,则∥=∥+1,应
用按适应度优劣排序后的第∥个混沌个体p州)取代
个体Z“n,即Z川’节d妁,并更新O(e-1(露“’))。
3)若鼢w如,则k=-k+l,转2):否则,执行步
骤(8)。
(8)终止检验:如果满足终止准则,则输出全
局最优结果I管’并停止;否则,t=t+l,转步骤(3)。
3算法测试与分析
3.1测试问题及参数设置
为了分析HDDESPF的执行性能,本文选择
DPSOHVP与DDESPF(算法3不执行步骤(7)的依概
率混沌移民操作)进行对比测试。试验对象为3个
Benchmark问题,每种算法分别独立运行50次。测
试环境:hltelCorerU2.1.66GHzCPU,2GBRAM,
WinXPOS,Matlab6.5编程。
例l:多项式约束优化问题【s】
minfl(x)=(西一10)2+5(x2—12)2+
霹+3(x4-11)2+1喈+7《+
霹一4x6x7一lOx6—8.b
约束条件为一lO≤柳≤10且而为整数(卢1,2,⋯,7)
gl(x)=一127+2xa2+3x24+x3+4《+5x5≤0
gE(x)=-282+7而+3x2+lOx2+.h一.x5≤0
&(x)=一196+23x1+《+69一8x7≤0
颤(工)=4彳+《一3x_1x2+29+5x6一llx7≤0
可接受最优值歹≯700。若.厂血忝厶,则视算法成
功求得最优解(下同)。由于文献[8】是将该函数作为
连续Benchmark问题进行测试的,因此第3.2节中
的分析仅涉及HDDESPF,DDESPF和DPSOHVP,
不与文献[8]比较。
例2:压力容器结构优化设计问题【7.1l】。压力容
器结构设计问题为典型CDO问题,设计变量分别
是:壳的厚度d。G1),两端帽的厚度疏阮),内径R∞),
容器中间圆柱部分的长度£似)。其中,xl,X2是离
散变量,取0.0625的整数倍(
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
冷轧钢板的有效
厚度);X3,x4是连续变量,但实际应用中X3,X4也应
圆整,取整数。该问题的数学模型如下
min五(x)=0.6224xax3x4+1.778lx2《+
3.166lx2x4+19.84x,12x3
约束条件为(自变量单位与文献【7】相同)
0.0625≤Xl,X2≤6.1875 10≤毛,黾≤200
&(x)=-x1+0.0193x3≤0
92(x)=一而+0.00954x3≤0
93(x)=-缸gx,一≯4《+129600。≤o
94(X)=x4—240≤0
可接受最优值丘=6075(由于x4≤200,故寻优时
无须考虑约束条件94∽)。
例3 Himielblau约束优化问题[8,11】
minL(x)=5.3578547《+o.8356891jcl黾+
37.293239xa一40792141
约束条件为
78≤一≤10233≤x2≤4527≤jc3,x4,X5≤45
10≤gl(x)≤92
{20≤92(x)≤llo
【20≤93(x)≤25
万方数据
2011年2月 车林仙等:工程约束优化的自适应罚函数混合离散差分进化算法 147
式中 gl(x)=85.334407+0.005658X2X5+
0.0006262xlx4—0.0022053x3x5
92(x)=80.51249+0.0071317屯%+
0.0029955xax2+0.00218l3#
93(x)=9.300961+0.0047026x3x5+
0.0012547xax3+O.0019085.,qx4
《卢1,2,⋯,5)为整数,可接受的最优值厶=
00512。
HDDESPF的控制参数:M,op=60,F=0.5,
p。----0.5~O.9,p---0.3"--0.8,‰=100^钿,乒1.5,i=2,
,=0.02,Pmig=o.7,r=loo(例l、2)及T=300(例3);
DDESPF除无,外,其余参数均与HDDESPF相同;
DPSOHVP的控制参数见表1,其中,参数口一,‰
及岛ugc的意义见文献[11】。
表1 DPSOHVP的控制参数
参数
种群规模 外循环代数 内循环代数 大惩罚值
尘r脚 !!坠.!亟 !堕
函数tl 100 10 50 107
函数正 60
函数.fi 100
60
100
l护
109
3.2测试结果与分析
例1中,3种算法的最优解均为:,=(2,2,0,4,
0,1,2)1,fmin=700,旷(-7,-258,-156,-9)1。
例2中,DPSO[9J的最优解:x’=(0.8125,0.4375,
44,163)1,‰=6049.91077,旷(0.0367,--0.01774,
一52204.015)r(gl@)违反约束,因此该解实为不可行
解);DPSOHVP[¨】的最优解:f=(0.875,0.4375,45,
144)1,‰。=6136.90599,g=(-o.0065,-0.0082,
一1791.925)1:DDESPF与HDDESPF的最优解均为:
x’=(0.8125,0.4375,42,178)‘,厶i。=6074.99836,
g----(-o.0019,-0.03682,_774.049)1。本文的最优解是
目前用离散进化算法求出的最好结果。文献【1l】应
用枚举法得出的理论最优解:f:(0.8125,0.4375,
41,191)1,缸=6204.02867,g--(-o.0212,-0.04636,
一1369.906)1,显然不是全局最优解。
例3中,DPSOHVPtllj的最优解:x’=(78,33,31,
4l,36)‘.丘i。=-30387.755,g=(91.630610,
98.791596,20.008631)T;DDESPF与HDDESPF的
最优解均为:x’=(8l,33,30,45,36)。.厂mi。=
-30512.450,g=(91.989912,98.955091,
20.005165)1。本文的最优解与文献[1l】应用枚举法
得出的理论最优解一致。
3种算法的计算性能统计结果比较见表2优,^,
磊分别表示最好、最差和平均目标函数值,鼬表示
标准偏差,珞表示成功率,fm表示平均耗时),最优
目标函数值的平均进化曲线对比如图2~4所示(略
去进化初期的部分曲线)。其中,有关DPSOHVP的
统计结果及平均进化曲线,均系作者根据文献[11】
编写程序计算得出的结果(有可能与原文献程序不
同)。例1、2属较简单问题,HDDESPF与DDESPF
的成功率都非常高(几乎为100%),但前者耗时更
长,因此就简单问题而言前者并无优势;而例3为
经典多极值难优化问题,HDDESPF的成功率和鲁
棒性均远优于DDESPF,由于前者在进化后期引入
依概率的混沌移民算子,因而可使群体逃离局部最
优区域并执行深度搜索,较大幅度地提高了获取全
局最优解的几率。与HDDESPF及DDESPF相比,
DPSOHVP的成功率非常低,平均值和标准偏差较
大,鲁棒性较差。
表2 3种算法求解测试问题的统计结果比较
图5为例3中DDESPF某次运行陷入局部最优
区域(早熟收敛)、HDDESPF某次运行逃离局部最优
区域的进化曲线对比。由图5可知,两种算法都快
速收敛并陷入局部最优区域,础亦急剧减小并低
于,。在DDESPF中,础继续减小至稳定值,群
体高度趋同,直至进化结束也未能逃出局部最优区
万方数据
圉2 3种算法求僻舭的最优值平均选化曲
线比较
(b)DPSOHVP
圉3 3种算法求解例2的最优值平均进化曲线比较
一冲虫懈豪嚣淼平均进化曲线比较图4 3种算法求解例3的最优钟粕””
4工程应用实侈IJ
例4:应甩HDDEsPF对二级斜齿圆柱蕾
万方数据
2011年2月 车林仙等:工程约束优化的自适应罚函数混合离散差分进化算法 149
速器进行优化设计。已知原始数据为【4】:高速轴输
入功率P1=6.2kW;高速轴转速,ll-1450r/rain;总
传动比itr=31.5;齿宽系数妒a_0.4;大齿轮为45钢,
正火187~207HB;小齿轮为45钢,调质228"一
255FIB;总工作时间不少于lO年;取第一系列标
准模数。设计减速器使其总体积最小。
设计变量分别是:第1级传动,齿轮的法向模
数仰nI@1)),小齿轮齿数0l(砣)),齿宽(6I∞)),螺旋
角懈‰)),传动比(fIG5));第1I级传动,齿轮的法
向模数(m。IIG6)),小齿轮齿数(z3∞)),齿宽(bHG8)),
螺旋角够II(x9))。其中,Xl,X6是非等间隔离散变量;
娩,新是整数变量;勋,x8是连续变景,但实际应用中
应圆整,取整数;x4,X5,x9是连续变量,但受制造
精度所限,实际应用中取0.0001的整数倍。该问
题的数学模型如下
nfinf(x):!堑蔓羔!!±蔓2+‘
。4cos‘x4
厂 , 、21
兀《划1+f坐1l
L L工5/j
4cos2x9
约束条件为(自变量单位与文献【4]相同)
xa∈{2,2.5,3,4,5}
x6∈{2,2.5,3,4,5,6,8,10}
15≤x2.x7≤50
10≤x3,黾≤40
0.1396≤x4.x9≤0.2168
5.8≤五≤7.0
酏)=78419.774f1-1-单≤o
咖,=鼍竽(·+期一单COSx9≤。魂 \ jl·)/『 。
仅):—2506—.685一薪≤093 0【x)=——一《≤
94(x):丝一《≤094(x)=——一《≤
gs(x)=xax2x5cosx9+2cosx4cosxg(五+50)一
%"s_f1+坐1≤o
96(x)一|round(x2xs)一jc2黾l≤Ez
97(x)刊round(31.5x7/文)一31.5为/甄I≤£
式中,round(·)为四舍五入取整函数,岛为齿数圆
整误差,ez=0.02。
在第1级传动中,大齿轮齿数Z2=X2x5,但圆整
后会引起传动比误差,因此设置约束条件96∽可避
免圆整后第1级传动比误差过大(此处取Ez’O.02是
为了表明本文的优化解可满足高精度约束条件,事
实上工程应用中可放大到e=-=O.5)。同理,岛㈤则可
避免第1I级误差过大。
应用HDDESPF,DDESPF及DPSOHVP3种算
法求解此问题,HDDESPF与DDESPF除弘2500,
k=200Ⅳ蛳外,其余参数均与第3节相同;
DPSOHVP的参数:%。p=150,amx=50,j};雠=100,
Ch。。c_1011。3种算法分别独立运行20次,此问题的
可接受最优值k=1423532mm5。
3种算法的计算性能统计结果比较见表3,最
优目标函数值的平均进化曲线对比如图6所示。由
表3可知,HDDESPF与DDESPF的成功率均较高
且相当,前者因引入混沌移民算予而获得较高的精
度和良好的鲁棒性,即其平均值与全局最优值很接
近且标准偏差很小,但耗时稍长;后者的平均值与
标准偏差明显偏高。相比而言,DPSOHVP的最优
值远逊色于HDDESPF与DDESPF的最差值,且其
标准偏差很大,鲁棒性差。
E
口
奄
耧
旧
避
rrrr
’
罨
瓤
嚼
避
皿
进化代数t/103
(a)tlDDESPF与DDESPF
进化代数t/103
(b}DPSOHVP
图6 3种算法求解斜齿轮优化设计问题的
最优值平均进化曲线比较
本文还对GAl41、DPSOHVP及HDDESPF的最
优解进行了比较分析(表4),结果表明,DPSOHVP
的最优目标函数值比GA差,而HDDESPF的最优
目标函数值比GA下降了约41%。文献[5】应用改
万方数据
机械工程学报 第47卷第3期
进GA求得的最优目标函数值为1583197.7862
mm,(但该文未给出圆整后的设计变量,因此本文未
将该方法的结果列入表4进行比较),HDDESPF的
最优目标函数值比改进GA下降了约10%。GA及
其改进算法都是先将斜齿轮设计问题作为连续约
束优化问题求解,再对设计变量圆整,但受约束条
件限制,圆整后通常会较大幅度增加目标函数值,
很难达到全局最优解。而DDE则是将全部设计参
数作为离散变量寻优,无须再对设计结果圆整,因
此更容易求得全局最优解。本文给出的斜齿轮设
计结果是目前已知满足工程实践的单目标最优离
散解。
表3 3种算法求解斜齿轮优化设计问题的统计结果比较
表4 3种算法求解斜齿轮设计问题所得的最优结果比较
注:·表示文献【4】无此约束条件。
5 结论
(1)面向工程实践,将离散约束优化问题转化
为非负整数约束规划问题,建立相应的数学模型。
设计了求解该问题的离散差分进化算法,并采用基
于混沌映射的种群初始化、双版本变异和带随机扰
动项的取整运算等策略,以增加种群的多样性。
(2)针对现有非线性约束处理技术的不足,提
出惩罚基数和连续映射基函数等新概念,发展了约
束处理的自适应罚函数法。定义了一种刻画种群多
样性的新测度——种群二次平均基因距离,设计了
基于新测度的依概率混沌移民算子。
(3)将自适应罚函数法、依概率混沌移民操作
与离散差分进化算法有机融合,构造面向工程约束
优化问题的混合离散差分进化算法。对3个
Benchmark问题和斜齿圆柱齿轮传动优化设计问题
进行数值验证,结果表明混合算法具有良好的鲁棒
性且优于文献中报道的结果。对于4个难度、维数
不同的问题,除最大进化代数、初始混沌序列个数
外,其余控制参数完全一致,表明该算法通用性较好。
(41由于混沌移民操作会增加计算开销,因此
在种群规模、最大进化代数相同的条件下,
HDDESPF比DDESPF耗时更长。对于复杂问题例
3、4,HDDESPF均优于比较算法,这是符合EA
中“无免费午餐”定理的。HDDESPF在进化后期
存在较多趋同个体,如何减少冗余搜索来降低计算
开销是需要进一步研究的课题,也是本文的后续
工作。
参考文献
【l】DEBK.Anefficientconstrainthandlingmethodfor
geneticalgorithms[J].ComputerMethodsinApplied
MechanicsandEngineering,2000,l86(2-4):3l1-338.
121RUNARSSONTP,YAOXimSearchbiasesin
constrainedevolutionaryoptimization[J].IEEE
TransactionsOnSystems,Man.,andCybernetics,PartC.-
ApplicationsandRedews,2005,35(2):233—243.
【3】CHENXindu,CHENXin,SUNJiaa,eta1.Genetic
algorithmsinSU'UeRLraloptimizationwithmixeddiscrete
designvariables[J].ChineseJournalofMechanical
Engineering,1997,10(1):19—24.
【4】高玉根,王国彪,丁予展.斜齿轮减速器遗传算法的
优化设计川.起重运输机械,2003,10(8):19—21.
GAOYugen,Ⅵ‘ANGGuobiao,DINGYuzhan.Optimal
designofhelicalgearreducerswithgeneticalgorithms叨.
HoistingandConveyingMachinery,2003,lO(8):19-21.
【5】罗贤海,张仁宏,曹坤,等.改进遗传算法及其在齿
轮传动优化设计中的应用【J】.机械设计与研究,2006,
22(2):64-67.
万方数据
2011年2月 车林仙等:工程约束优化的自适应罚函数混合离散差分进化算法 15l
LUOXianhai,ZHANGRenhong,CAOKun,eta1.An
improvedgeneticalgorithmanditsapplicationinoptimi-
zationdesignofthegeartransmissions[J].Machine
DesignandResearch,2006,22(2):64·67.
【6】P久RSOPOULOSKE,VRAHATISMN.Particleswal'm
optimizationmethodforconstrainedoptimization
problems[M]//SINCAKP。VASCAKJ,KVASNICKAV,
eta1.Intelligenttechnologies—theoryandapplications:
Newtrendsinintelligenttechnologies.Amsterdam:lOS
Press,2002:214-220.
【7】HEQie,WANGLing.Aneffectiveco-evolutionary
particleswarnloptimizationforconstrainedengineering
designproblems[J].EngineeringApplicationsof
ArtificialIntelligence,2007,20(1):89—99.
【8】HUANGFuzhuo,WANGLing,HEQie.Aneffective
co-evolutionarydifferentialevolutionforconstrained
optimization[J].AppliedMathematicsandComputation,
2007,18“1):340-356.
【9】于颖,李永生,於孝春.粒子群算法在工程优化设计
中的应用【J】.机械工程学报,2008,4402):226-231.
YUYing,LIYongsheng,YUXiaochun.Applicationof
particleswarmoptimizationintheengineeringoptimi-
zationdesign[Y].ChineseJournalofMechanical
Engineering,2008,44(12):226-231.
【10】于颖,於孝春,李永生.扩展拉格朗日乘子粒子群算
法解决工程优化问题[J】.机械工程学报,2009,45(12):
167.172.
YUY'mg,YUXiaochun,LIYongsheng.Solving
engineeringoptimizationproblemby augmented
Lagrangeparticleswarmoptimization叨.Journalof
MechanicalEngineering,2009,45(12):167—172.
【ll】YUYing,YUXiaochun,LIYongsheng.Noveldiscrete
particle8warffloptimizationbasedonhugevaluepenalty
forsolvingengineeringproblem[J].ChineseJournalof
MechanicalEngineering,2009,22(3):410—418.
[12】STORNR,PRICEK.Differentialevolution—asimpleand
efficientheuristicfor globaloptimizationover
continuousspaces[J].JournalofGlobalOptimization,
1997,11(4):341—359.
【13】AYDINS,TEMELTASH.Fuzzy-differentialevolution
algorithmforplanningtime—optimaltrajectoriesofa
unicyclemobilerobotonapredefinedpath[J].Advanced
Robotics,2004,18(7):725-748.
【14】STORNR.Designingnonstandardfilterswith
differentialevolution【川.IEEESignalProcessing
Magazine,2005,22(1):103—106.
【15】NOBAKHTIA,WANGHong.Asimpleself-adaptive
differentialevolutionalgorithm、析thapplicationonthe
ALSTOMgasifier[j].AppliedSoftComputing,2008,
8(1):350—370.
【16】吴亮红,王耀南,陈正龙.求解混合整数非线性规划
问题的改进差分进化算法【J】.小型微型计算机系统,
2007,28(4):666-669.
WULianghong,WANGYaonan,CHENZhenglong.
Modifieddifferentialevolutionalgorithmformixed-
integernonlinearprogrammingproblems[J].Journalof
ChineseComputerSystems,2007,28(4):6