《一种基于新改进的Price算法的混合遗传算法求解约束优化问题.doc》由会员分享，可在线阅读，更多相关《一种基于新改进的Price算法的混合遗传算法求解约束优化问题.doc（14页珍藏版）》请在三一文库上搜索。
1、一种基于新改进的Price算法的混合遗传算法求解约束优化问题第26卷第2期工程数学学报Vo1.26No.22009年04月CHINESEJOURNALOFENGINEERINGMATHEMATICSApt.2009文章编号:1005-3085(2009)02019109一种基于新改进的Price算法的混合遗传算法求解约束优化问题木李宏,焦永昌,张莉(1.西安电子科技大学理学院,西安710071;2一西安电子科技大学天线与微波国家重点实验室,西安710071)摘要:新改进的Price算法能够求解多峰,多维,以及不可微目标函数的全局优化问题.把新改进的Price算法作为局部搜索算子,并入到实数编码
2、遗传算法中,构成一个混合遗传算法,求解约束优化问题.该混合算法增强了全局寻优能力,提高了函数值的精度,并减少了计算量.通过对l3个约束标准测试函数的仿真实验,并和已有算法的比较,结果表明本文提出的混合遗传算法是有效的.关键词:Price算法:遗传算法;混合遗传算法;全局优化;约束优化分类号:AMS(2000)90C30;90C59中图分类号:TP18文献标识码:A1引言考虑一般的非线性优化问题min,(),=(Xl,?一,)R(1)R表示界约束搜索空间,即=(z1,t1)(k,U)lliU,i=1,2,几).表示可行域,=R()0,J=1,m),其中()0,J=1,m是不等式约束(等式约束可近
3、似转化为不等式约束).若要求n,问题(1)就是约束优化问题.非线性优化问题(1)广泛地存在于科学,工程等实际问题中,对其进行算法研究具有重要的理论和实际意义,因此,受到各领域研究者的普遍关注.求解连续变量的非线性优化问题的方法一般分为确定性方法和随机性方法.与确定性方法相比,随机性方法具有独特的优点:鲁棒性强,适用范围广,具有全局寻优能力,对目标函数的性态无要求.在处理目标函数是非凸,不连续,或不可微,高度非线性的复杂优化问题时,确定性方法有时无能为力,而只能使用随机性方法.近几十年来,各种随机性算法及改进算法【1-9】应运而生,如进化算法f包括遗传算法,进化策略,进化规划等),Price算法
4、,差分进化算法,蚁群算法,粒子群算法等,已成功地用于求解各种优化问题.遗传算法是一种最具代表性的进化算法,在各种问题的求解与应用中展现了其独特的魅力【3,4,5,8】,但在理论和应用上也暴露出诸多不足和缺陷,如对某些复杂问题而言,它易趋于早熟收敛而陷于局部最优解【0,】,另外,也存在收敛速度慢,计算量大等问题【3】.牧稿日期:200%03-27.作者简介:李宏(1972年4月生),男,硕士,讲师.研究方向:进化计算,优化算法与应用,智能信息处理.基金项目:国家自然科学基金f60171045;60374063).192工程数学学报第26卷一些研究表明,在进化算法中并入某些其他知识能极大改善进化算
5、法的性能3,9.特别是将进化算法和局部搜索方法相结合的混合算法已经证明是很有前途的措施【9_Io.本文把一种启发式算法一新改进的Price算法【2】作为局部搜索算子,并入到实数编码遗传算法中,构成一种混合遗传算法,求解约束优化问题.为了测试混合算法的有效性,我们仅使用静态罚函数法来处理约束,对13个标准问题进行了实验,并和其他三种进化算法的结果作了比较,结果表明本文的混合遗传算法是有效的.2新改进的Price算法新改进的Price算法2】是一种求解多峰,多维,以及不可微目标函数的无约束优化问题的高效的启发式算法.文【2】中,考虑下面的无约束全局最小值问题),(2)z,其中f:R一R,是一个超立
6、方体.为了处理工程中一类重要的,但比较困难的全局优化问题,如目标函数的计算很麻烦,而且目标函数的导数无法计算,Brachetti等【1】提出了一种新的求解全局优化问题的Price算法,后来,Jiao等【2】又对该算法进行了改进,使其计算效果更好,并且大幅度减少了计算量.下面给出Jiao等【2】提出的新改进的Price算法的详细步骤.算法1Data:选择正整数m使得mmax(n+1,3,适当小的正数,以及正常数u.Step0:令k=0,用数论方法产生初始种群集S=,其中kD,i=1,m,并且计算f(xki),i=1,m.Step1:求出两点kax和i,以及它们的目标函数值ax和i,使得盛=ax)
7、=maxf(),tn=k)=剃minf()若停止准则ax一盛i<E满足,算法停止;否则,在S中求出第三个最好解i3和其目标函数值.n3=f(xkmi3).Step2:在S中随机选择礼+1个点乞,珐,xk.求出n个点xk,xk的带权值的质心:咤=乞,其中=,=uStep3:令庀=1k八k),求出试验点:吊Jk一(一),f(Xkio),【一CZk(c一乞),>,(),k.kf(Xko),mm,I-f,【第2期李宏等:一种基于新改进的Price算法的混合遗传算法求解约束优化问题和:u.若孟D转Step2,否则,计算,().Step4:若,(),令S+=,k=k+1转Step2.Step5
8、:若i3<,()<ax,令+=SU)一Xax),并令k=k+1转Step1.Step6:若f(x)i3,令雪=SU卜一ax),在雪中,选择三个最好的点(有最,J,的目标函数值)圣f,z:,圣!.,令圣f=(盒f1,l2,圣z),f=(1,!.2,一,岔fn),岔f.:(1,2,仝f.)T,计算盛=,():m,(圣).Step7:计算向量圣=(圣:l,2,奎:),盎k.t,qi=2蔫i)f(ct,【(圣z.一l.)+(z.一奎fi),(童z)+(圣z.一圣lt),(.)J若岔,令k+=并令=+1,转Step1;否则,计算,(童:).若,:)&x,8k+1=:否则,令+=u圣)
9、一ax).令k=k+1转Step1.3实数编码的遗传算法本文采用实数编码,我们用向量X=(X1,Xn)T作为一个个体(或染色体)来表示问题f1)的一个解.3.1初始种群在n维界空间中随机产生pop个服从均匀分布的个体构成初始种群,Pop表示种群规模.3.2适应度函数由于所讨论的问题f1)是最小化问题,为方便起见,设定:适应度越小,结果越好.对等式约束h(x)=0,通过下式,将其转化为不等式约束:I()I一50,其中5=10_.基于精确罚函数法,将不等式约束gj(X)0,J=1,2,m作为罚项,构成如下适应度函数fit(x)=,()+Mmaxgj(x),0),(3)J:1其中M(M>0)是
10、合适的罚参数.3.3交叉算子以杂交概率P随机选取两个父代个体,记为Xl=(Xl1,X12,Xl)T和X2=(X21,X22,X2n)T.则由下式产生后代个体Y:(Y1,Y2,Yn)Tfit(x)fit(x2),fit(xx)>t(2),其中F=diag(71,7),(一1,1)且7t0,i=1,n.3.4变异算子设p是变异概率,到目前为止最好的个体(保留的最好解)为best=(bestl,best)T.对满足JIbestylf1(E1=10一)的每个Y=(Y1,Yn)T,生成一个随机数r(0,1),若r<p,则由下式产生变异后代Z=(Z1,)Tz=best+V?Icl,(5),J2
11、1Z一一12,【/rr+12,-Cl_-,Il194工程数学学报第26卷其中V是对角矩阵:V=diag(bestlyl,best一).IcI=(Ic1I,lc2l,Ic1)T是随机搜索步长,c是服从礼维标准正态分布的随机向量,即:c一(0,1),N(O,1)T.对不满足IIbestyllE1的每个=(yl,)T,生成一个随机数r(0,1),若r<P,则由高斯变异,产生后代=(z1,Zn)T,Z=best+V(6)其中AvN(0,)=(N(0,),N(0,)T,即Av服从均值为0=(0,0)T,方差为=(,)T的佗维正态分布.3.5选择算子为了提高种群多样性,选择算子采取以下策略:在当前种
12、群(父代)及所有后代(杂交产生的后代以及变异产生的后代)个体中,按适应度的升序排列,选择前popN1个个体,再在(或通过预估,在的某子区域)中随机产生1个个体,把这两部分个体合起来作为下一代种群,并且保留每一代产生的最好解.3.6终止规则若算法执行了最大进化代数,则停止,所得最好解作为近似全局最优解.4混合遗传算法新改进的Price算法【2】可以求解目标函数不可微,多峰,多维的无约束全局优化问题,仿真实验表明,该算法不但求出的全局最优解的精度高,而且计算量特别小.本文将新改进的Price算法做了适当的简化修改,并入到我们设计的实数编码的遗传算法中,构成一种新的混合遗传算法,用来求解约束优化问题
13、.该混合算法结合了两种不同算法的优点,加强了算法的全局搜索能力,提高了解的质量,并减少了计算量.下面我们给出混合遗传算法的详细步骤:算法2Step0:(参数)种群规模Pop,杂交概率P.,变异概率P,罚参数M,最大进化代数,两个合适的整数1,2和一个正常数.Step1:(初始化)置k:0,产生初始种群P(k)=,.),并计算每个个体的适应度fit(xki),i=1,Pop.Step2:(杂交)Step2.1:在区间(0,1)上产生随机数rl,同时在区间【1,pop上随机产生两个整数r2和r3且r2r3.若r1<P.,则取父代的两个个体分别为和,由交叉算子(4)产生它们的中间后代Y.Ste
14、p2.2:重复Step2.1Pop次,设产生pop个后代个体,构成一个中间种群集,记为Pc(后)=,),并计算每个个体的适应度fit(yk),i=1,Pop.Step3:(变异)Step3.1:对i=1,Pop,若IIbest一ll1(E1=10_4),则产生一个随机数r(0,1),若r<P,则由变异算子(5),产生中间后代Z.否则,产生一个随机数r(0,1),若r<Pm,则由变异算子(6),产生中间后代Z%.Step3.2:通过Step3.1,设产生Pop个后代个体,构成一个中间种群集,记为:Pm(七):名,z),并计算每个个体的适应度fit(z),i=1,Popm.Step4:
15、(简化的新改进Price算法)第2期李宏等:一种基于新改进的Price算法的混合遗传算法求解约束优化问题195Step4.1:在父代及所有后代个体中,选出p个较好的个体,记为=0,.p,满足:fitkmi=fit(o)fit(ok.p)=fitkmax.Step4.2:在中,随机选择2+l(N2+1<pop)个个体,记为:0,0,0:,求出.k,.k这2个带权重的质心ck:c乞=叫.k,其中=鑫,=南,?Step4.3:令,t=1fit(.),求试验点吊J一(.Z0一吃),如果,托笔fit(.),【Ok.一a(c笔一.),如果,乱笔>fit(oo),其中f1一而fit(oo)-fi
16、t+kw,如果,圪fit(.),【l一鹁,如果似fit(.),和砂=,警.计算,(童).Step4.4:若fit(&)<,托ax,令=u童)一.p);否则,令=.将中的个体从小到大排序,选择适应度最小的个体勃.,然后在序号2-12中随机选择一个个体白,在仝fl=(ll1,圣f12,.,圣fln)T,22=(圣f21,圣f22,f2n)T,岔l3=(l31,l32,z3竹)T,计算:fit():maxfit(2).Step4.5:计算试验向量=(岔1,仝:2,圣:)T=蔫等篆拳1i=1,2,.-,n2i)fit(&ti)fit(&ti)fit(2t.【(圣zi一圣3
17、)+(圣f.t一f2)+(圣z一l23)J计算.,乱().Step4.6:若(宕)tax,令=;否则,令=u:)一ax).Step5:(选择)由选择策略,从中,选出前PopN1个较好个体,再随机抽取1个个体,构成Pop个下一代种群,并保留每一代的最好解.Step6:(判断)若满足停止准则,则停止,输出所保留的最好解作为问题(1)的近似全局最优解.否则,令k=+1,转Step2.5数值仿真结果及比较为了评估本文提出的算法(简记为HGA)的性能,我们测试了文献【6-8】中的l3个标准约束测试函数.详细的情况见文献96-8中附录.本文算法的参数设置如下:种群规模pop=100,杂交概率P=0.8,变
18、异概率P=0.05,两个合适的整数N1=5,2=50和一个正常数,=2.196工程数学学报第26卷采用罚函数法来处理约束条件已被广泛地应用到各种约束优化问题中,一般来说,罚参数的选取比较困难,需要经过反复的试验才能确定.本文采用精确罚函数法,将约束条件放入适应度函数中,对13个标准约束测试函数,我们选取如下的罚参数:对,3,选取M=100;对fl0,选取M=10;对,2,6和,8,选取M=10;对,1和,4,选取M=103:对.7,9和f12,选取M=i02;对,5和fn,选取M=10;对f13,选取M=0.1.最大进化代数,除了,2我们选取N=2000,其余的选取N:1000.对每个函数独立
19、运行15次,记录15次所得最好值,平均值,中间值,最差值,标准差(简记作St.Dev.),平均进化代数(简记作MNG)及适应度的平均计算次数(简记作MNFE),结果见表1和表2.我们把HGA所获得的结果分别与Runarsson等【6】提出的SR,Mezura-Montes等【l提出的SMES,以及Venkatraman等8】提出的GF三种不同的方法作了比较.他们的结果见表1和表2,表中NA表示结果没有给出.表1:对测试函数flf6,HGA与SR,SMES和GF的性能比较第2期李宏等:一种基于新改进的Price算法的混合遗传算法求解约束优化问题197表2:对测试函数f7.f13,HGA与SR,S
20、MES和GF的性能比较由表1和表2可以看出,对13个约束测试函数,HGA能够找到8个函数.,1.厂3,4.,6,8,9,11和f12的最优解,还能够找到其余5个函数的近似最优解.HGA分别与SR,SMES和GF所求得结果的比较:对函数.厂1.r4.,8,fl1和f12,HGA,SR和SMES每次运行都能找到最优解;除了,8和fll外,GF求得的结果比HGA的结果差.对,6,f9,f13这3个函数,HGA所找到的最好值,平均值,中间值及最差值都优于或等于其他三种算法.对函数,2,HGA所找到的最好值优于其他三种算法,但平均值,中间值,最差值差于SR和SMES,好于GF.对函数.厂3,HGA所找到
21、的最好值,平均值和中间值都是最优值,但最差值略差于最优值.对函数.厂5,HGA所找到的结果比SR差,比GF好;HGA所找到的最好值和中间值比SMES好,但平均值和最差值比SMES差.对函数.厂7,HGA所找198工程数学学报第26卷到的结果比SR差,比GF好;HGA所找到的最好值,中间值和最差值比SMES差,平均值比SMES好.对函数fl0,HGA除了最好值比SMES差外,其余的结果都好于其他三种算法.HGA分别与SR,SMES和GF的计算量的比较:HGA除了,2所需的最大进化代数为=2000,适应度的计算次数约为220000外,其余的12个测试函数的最大进化代数为=1000,适应度的计算次数
22、约为110000.而SR的适应度的计算次数为350000,SMES需要的适应度的计算次数为240000,GF需要的适应度的计算次数为50000,表明HGA的计算量比SR和SMES小,比GF的计算量大.对13个测试函数,HGA求出最好解的平均进化代数为17_1644,适应度的平均计算次数为1780-181792.因此,除了函数f12和f13,HGA需要的适应度的平均计算次数少于SR.6结论在进化算法中加入局部搜索方法,如最速下降法,单纯形法,近似算法,插值法等局部优化方法以及与其他的启发式算法相结合,构成的混合进化算法已经被证明是改善进化算法性能的有效方法.本文把新改进的Price算法做了适当的
23、简化修改,合并到实数编码遗传算法中,构成求解约束优化问题的混合遗传算法.该混合方法充分利用两者的优点,有效地改善了算法的全局收敛能力,提高了解的质量和减少了计算量.该算法对目标函数的性质没有要求,适合求解工程实际问题.通过对13个标准约束测试函数的仿真实验,并和已有几种算法做了比较,结果表明本文提出的混合遗传算法是有效的.参考文献:f11BrachettiP,etalAnewversionofthePriceSalgorithmforglobaloptimizationJ】.JournalofGlobalOptimization,199710:165-1842】JiaoYong-Chang,e
24、ta1.AmodificationtothenewversionofthePricesalgorithmforcontinuousglobaloptimizationproblemsJ.JournalofGlobalOptimization,2006,36(4):609-6263】GoldbergDE.GeneticAlgorithmsinSearch,OptimizationandMachineLearningM.Reading,Ma:AddisonWsley,19894】OndrejHrstka,AnnaKucerova.Improvementsofrealcodedgeneticalgo
25、rithmsbasedondifferentialoperatorspreventingprematureconvergenceJ.AdvancesinEngineeringSoftware,2004,35:237-2465】WangHsiao-Fan,wluKuang-yao.HybridgeneticalgorithmforoptimizationproblemswithpermutationpropertyJ1.Computers&OperationsResearch,2004,31:24532471f61RunarssonTPYaoX.Stochasticrankingforc
26、onstrainedevolutionaryoptimization(J1.mEETrans.onEvolutionaryComputation,2000,4(3):284-294【7】Mezura-MontesE,CoelloCAC.AsimplemultimemberedevolutionstrategytosolvecoiLstrainedopti-mizationproblemsJ.IEEETrans.onEvolutionaryComputation,2005,9(1):1-17【8VenkatramanS,YenGG.Agenericameworkforconstrainedopt
27、imizationusinggeneticalgorithmsJ.IEEETrans.onEvolutionaryComputation,2005,9(4):424-435【9】NomanN,IbaH.AcceleratingdifferentialevolutionusinganadaptivelocalsearchJ.IEEETrails.onEvolutionaryComputation,2008,12(1):107-125【10】GoldbergD,VoessnerS.Optimizingglobal-localsearchhybridsC/Proc.GeneticEvo1.Compu
28、t.Conf.(GECCO99),1999:220-228第2期李宏等:一种基于新改进的Price算法的混合遗传算法求解约束优化问题199HybridGeneticAlgorithmBasedontheModificationtotheNewVersionofthePriceSAlgorithmforConstrainedOptimizationProblemsLIHong,JIAOYonchang.,ZHANGLi(1一SchoolofScience,XidianUniversity,Xian710071;2一NationalLaboratoryofAntennasandMicrowaveT
29、echnology,XidianUniversity,Xian710071)Abstract:ThemodificationtothenewversionofthePriceSalgorithmcanfindtheglobalminimumofamultimodal,multivariateandnondiffrentiablefunction.Inthispaper,themodificationtothenewversionofthePriceSalgorithmistakenasalocalsearchoperator,whichiscombinedwiththerealcodedgen
30、eticalgorithm.Thusanewhybridgeneticalgorithmisproposedforconstrainedoptimizationproblems.Thenewapproachiscapableofenhancingtheglobalsearchabilityofthegeneticalgorithm,improvingtheaccuracyoftheminimumfunctionvalue,aswellasreducingthecomputationalburden.Thehybridgeneticalgorithmhasbeentestedon13constrainedbenchmarkproblems.Theresultsobtainedhavebeencomparedwiththoseofotherexistingalgorithms.Simulationresultsshowtheeffectivenessoftheproposedalgorithm.Keywords:thePriceSalgorithm;geneticalgorithm;hybridgeneticalgorithm;globaloptimization;constrainedoptimization