遗传算法求解约束非线性规划及Matlab 实现

1、文库下载 免费文档下载/本文档下载自文库下载网，内容可能不完整，您可以点击以下网址继续阅读或下载：/doc/aacd0374a417866fb84a8ee4.html遗传算法求解约束非线性规划及Matlab实现非线性规划第21卷第1期2005年2月大学数学COLLEGEMATHEMATICSVol.21,.1Feb.2005遗传算法求解约束非线性规划及Matlab实现倪金林(合肥工业大学理学院应用数学系,合肥230009)摘要对于约束非线性规划问题,传统的方法:、.用新兴的遗传算法来解决约束非线

2、性规划,.,有的过于复杂.,提出了一种解决.;交叉;变异A文章编号167221454(2005)01200912051引言约束非线性规划问题是运筹学中的一个重要分支,现实生活中许多实际问题都不能表达为容易解决的线性模型,如地下水调整系统和地下水污染来源识别问题中就不可避免非线性规划问题.解决约束非线性问题的方法也很多.一般方法,如可行方向法,惩罚函数法1都计算复杂且精度不高.遗传算法是一个新兴的方法,1975年Holland在他的著作AdaptationinNaturalandArtificalSystems中首次提出遗传算法,很快就用遗传算法来解决非线性最优问题.而用遗传算法解决非线性等式与

3、不等式约束最优化问题的核心问题是如何满足约束问题.如今用遗传算法解决非线性等式与不等式约束最优化有几种满足约束的策略:拒绝策略、改进策略、算子策略和惩罚策略2.前三种策略不会产生不可行解,无法考虑可行域外的解,对于约束严的问题不可行解在种群中占的比例很大,因此将搜索限制在可行域内就很难找到可行解.惩罚策略不拒绝每代中的不可行解,其中一些个体可能提供关于最优解的更有用的信息,通过对不可行解的惩罚来将约束问题转换为无约束问题,任何对约束的违反都要在目标函数中添加惩罚项.因此,允许在搜索空间里的不可行域中进行搜索能实现更快更好的最终解.惩罚函数就是在遗传搜索中考虑不可行解的技术,给不可行解根据具体情

4、况给予惩罚.如何设计一个好的惩罚函数就是关键.设计惩罚函数没有一般的指导性原则.Homaifar,Qi和Lai方法构造的惩罚函数简单,但不够精确.Joines和Houck设计的惩罚函数对参数太敏感.本文在两个定义基础上构造一个新的惩罚函数,并用两个例子说明/doc/aacd0374a417866fb84a8ee4.html该方法是有效可行的.2遗传算法遗传算法是一种从适者生存概念和自然中抽象出来的基因运算,是基于自然选择机制和自然基因的相对较新的联合搜索方法.基因算法与其他的最优化方法相比有4点不同:1)遗传算法运算的是解集的编码,而不是解集本

5、身.收稿日期2004201225基金项目安徽省重点教学研究项目(2001011)92大学数学第21卷2)遗传算法的搜索始于解的一种群,而不是单个解.3)遗传算法用的是目标函数本身,而不使用目标函数和约束函数的导数.4)遗传算法采用概率的,而不是确定的状态转移规则.遗传算法第一次是由Holland提出,自从提出以后,由于遗传算法不同于传统的最优化方法,有其灵活性和易变性.在基本的遗传算法中,许多文学中的变异,选择,交叉,平行计算被改进发展来加速方法的收敛和方法的有效性4.遗传操作主要有三种:1)选择算子(Selection/reproduction):选择算子从群体中按某一概率成对选择个体,某个

6、体x被选择的概率Pi与其适应度值成正比.最通常的实现方法是轮盘赌(roulettewheel)模型.21交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率Pc进行交叉,生成两个新的个体,交叉位置是随机的.其中Pc是一个系统参数.31变异算子(Mutation):变异算子将新个体的基因链的各位按概率(0,1编码)来说即是取反.h证明了一般的遗传算法不一定收敛,).,或者叫满意解.从数,而计算过程是一个有限自动机,因此通过遗传算法程序求得的解总是一个近似解.近似解与问题真正的最优解的差是一个统计意义下的量,也就是说每次程序运行得到的解的质量可能是有较大的差别的.遗传算法一般采

7、用二进制编码与实数编码.3惩罚函数的改进及Matlab实现现在定义点x与可行域/doc/aacd0374a417866fb84a8ee4.html之间的距离d(x,Q)及非可行点可行度FD(x),在这两个定义的基础上提出了一种新的惩罚函数.一般形式的约束非线性规划问题为maxf(x)=f(x1,x2,xn)s.t.xQ=xEn|gi(x)0,i=1,2,m1;hj(x)=0,j=1,2,m2.定义d(x,Q)=max0,gmax(x),hmax(x),其中gmax(x)=maxgi(x),i=1,2,m1,hmax(x)=max|hj(x)|,

8、j=1,2,m25,d(x,Q)是点x与可行域Q之间为点超出约束的最大值,且反映了点x与可行域Q的关系.若d(x,Q)=0,则xQ;若d(x,Q)0,则x|Q.d(x,Q)越大,表明x离可行域Q越远.定义m1FD(x)=i(x) j(x)m2m1 m2,其中1,gi(x)0,1,hj(x)=0,i(x)=1-,gmax(x)0FD(x)也反映了x与可行域之间的关系.如果FD(x)=1,则xQ,若FD(x)=0,即gi(x)=gmax(x),i=1,2,m1;hj(x)=hmax(x),j=1,2,m2,则点完全不属于可行域.如果0x|Q(记FD(x)为FD),且FD越大,突破约束越小.由上面的

9、两个定义,可构造一个新的惩罚函数来处理x在不可行域的适值函数.第1期倪金林:遗传算法求解约束非线性规划及Matlab实现f(x),xQ,f(x)0,x|Q,f(x)其中p,为参数,满足p1,0.根据不同的情形,选择p,的值.上面的惩罚函数在处理极大化的问题时,若x在可行域之内,等于目标函数值;不在可行域内,根据x突破约束的程度来改变适值,脱离/doc/aacd0374a417866fb84a8ee4.html约)p在p1,0时也越大(d(x,Q) 1/束越大,d(x,Q),1/FD越大,(d(x,Q) 1/(FD (FD )p.在p1,0时恒大

10、于1,所以求得的eval(x)越小于目标函数值.在遗传算法中被选取的概率越小,这也就达到了惩罚的目的.下面通过具体的例子来说明.先计算一个求约束非线性规划最小化问题2例1minF=x31 2x2x3 2x3,2s.t.x21 x2 x3=4,x1-x2 2x32,x1,x2,x30.2,(SQP)方法及新的惩罚函数遗传算法(p=115,=013)表1变量x1x2x3F一般GA算法(=10)0156473165490100000118035一般GA算法(=100)0110983198490100000100264SQP01001641000001000041194e-009新算法01000041

11、0000010000010000精确解010000410000010000010000应用上面的惩罚函数在p=115,=013时,得到的解为x1=010000,x2=410000,x3=010000,f1(x1,x2,x3)=010000,且满足约束条件.上例用新惩罚函数的遗传算法的算法跟踪结果为图1.图1上面的例子说明在解非线性规划问题时,新构造的惩罚函数在遗传算法中可以得到更好的解.新的构造方法对于每代中根据具体的个体重新计算d(x,Q),1/FD,让d(x,Q),1/FD随着迭代进行而一直处于动态变化中.再举一个求最大化最优解的例子.94大学数学第21卷2例2maxf(x)=-2x21

12、2x1x2-2x2 /doc/aacd0374a417866fb84a8ee4.html4x1 6x2,s.t.2x1-x20,x1 5x25,x1,x20.对这个问题,应用可行方向法、惩罚函数法和上面新惩罚函数的遗传算法(p=115,=011)的解对比结果如表2.表2变量x1x2F可行方向法016300187461544惩罚函数法016450186961566基于权重GA0165801868616129Homairfar的GA0162050177011新的算法01658961,x,6130.根据上表说明传统GA差,Homaifar的GA(r1

13、=02),而新的惩罚函数的遗传算法(p=115,=011)的结果6.但是新的惩罚函数的遗传算法比基于权重的遗传算法简单.例2新惩罚函数的遗传算法的算法跟踪结果为图2.因为初始种群是随机产生,每次曲线可能不同,但最后的目标函数基本相同.图2新的惩罚函数的遗传算法应用在上面的两个例子:一个求最大化,一个求最小化得到的最优解比传统的解决约束非线性规划问题的方法、一般的遗传算法得到的结果都好,非常接近实际最优解.通过上述两个例子,参数p在1,6,在0101,015内取值,容易得到比较好的解.由于遗传算法的初始的解是通过随机生成的,所以程序每次运行的结果可能不完全一样,但每次的结果误差都控制在一定的范围

14、之内.可见,新的惩罚函数的遗传算法对于解决约束非线性规划问题是完全可行的,并且得到的结果优于传统的解决约束非线性规划问题的方法:可行方向法,惩罚函数法.比一般的遗传算法也要好.4结论解约束非线性规划问题一直是运筹学的一个难点.对于这个问题,已经有很多常规传统的解法,如可行方向法,惩罚函数法等.但这些方法计算复杂且结果不精确.遗传算法兴起以后,很快就应用到解决约束非线性规划问题.惩罚函数的选取一直是遗传算法的核心.本文根据两种脱离可行域程度函数d(x,Q),FD来构造一种新的惩罚函数对突破可行域的x进行惩罚.d(x,Q/doc/aacd0374a

15、417866fb84a8ee4.html),FD都是随着x的变化而第1期倪金林:遗传算法求解约束非线性规划及Matlab实现95动态地改变,因此能够更好地对每个具体的x进行处理.用两种度量函数d(x,Q),FD联合处理,互相补充,用两个参数调节解,能较好地得到最优解.通过两个实例,应用Matlab进一步论证了这种方法的可操作性.参考文献1运筹学教材编写组.运筹学M.北京:清华大学出版社,2000.180-189.2日玄光男,程润伟.遗传算法与工程设计M.北京:科学出版社,2000.36-38.3日玄光男,程润伟.遗传算法与工程设计M.北京:科学出版社,2000.39-40.4GuanJiaba

16、o,MustafaMAral.ProgressivegeneticalgorithmforsolutionofoptimizationproblemswithnonlinearequalityandinequalityconstraintsJ.AppliedMathematicalModelling,1999,23:324-343.5唐加福,汪定伟,许宝栋,李露.基于评价函数的遗传算法解性规J决策,2000,15(5):573-576.6唐加福,汪定伟.(5):490-493.ThewithNonliearConstraintsProgrammingGeneticAlgorithmandDem

17、onstrationbyMatlabNIJin2lin(HefeiUniversityofTechnology,Hefei230009,China)Abstract:Tooptimizationwithnonlinearconstraintsprogramming,traditionalmethod,suc/doc/aacd0374a417866fb84a8ee4.htmlhasfeasibledirection,penaltyfunction,iscomplicatedandimprecise.Solvingoptimizationwithn

18、onlinearconstraintsprogrammingbygeneticalgorithm,penaltyfunctioniscore.Theformergeneticalgorithmwithpenaltyfunctionisnotperfect,impreciseandcomplicated.Basedontwodefinition,thenewpenaltyfunctionisfound.Throughtnewpenaltyfunction,thearticledevelopsthenewmethodofsolutionofoptimizationwithnonliearconstraintsprogramming.Twoexamplesshowthattheimpr