一种求解非线性优化问题的混合遗传算法

1、鲁东大学毕 业 设 计 （论 文）设计（论文）题目：一种求解非线性优化问题的混合遗传算法姓 名 苗婷 院 系 数学与信息学院 专 业 数学与应用数学 年 级 2001 级 学 号 2001E110222 指导教师 周莉 2005 年 6 月 1 日一种求解非线性优化问题的混合遗传算法苗婷数学与信息学院数学与应用数学专业 2001 级数本 2 班摘要 针对遗传算法善长全局搜索但收敛速度慢，旋转方向法善长微调但常会陷入局部最优的不足，本文提出了一种求解不可微非线性优化问题的方法混合遗传算法，该算法在实码遗传算法进化过程中加入旋转方向法，加快了算法的收敛速度，同时给出了该算法收敛的理论证明，理论分析

2、和实例分析验证了该算法的有效性.关键词 实码；旋转方向法；混合遗传算法Abstract Genetic algorithm is good at global reseaching, but the speed is very slow. Rosenbrock algorithm is good at partial reseaching, but it is difficult to find out the global solution.A method is presented for global solution of indifferentiable nonlinear opti

3、mal problems-A hybrid genetic algorithm.This method adds Rosenbrock algorithm into real code genetic algorithm . This algorithm accelerats convergence -speed.The sametime this text give out convergence theorem.Some theoretial analysis and application indicate that this algorithm is a superior nonlin

4、ear optimal method.Key words real code；Rosenbrock algorithm; hybrid genetic algorithm.目录1 1 引言引言 .12 2 求解非线性优化问题的混合遗传算法求解非线性优化问题的混合遗传算法 .12.1 旋转方向法.12.2 混合遗传算法.43 3 混合遗传算法的收敛性分析混合遗传算法的收敛性分析 .64 4 实例分析实例分析 .75 5 参数说明参数说明 .9结论 .9致谢 .9参考文献参考文献 .9附录 .101 引言求解非线性优化问题的方法很多，有一维搜索法，共轭梯度法，牛顿型方法等但这些方法都要求非线性函数

5、可微，或至少连续，有一定的局限性因此，寻找一种求解不可微非线性函数优化问题的算法是非常必要的旋转方向法是一种局部直接寻优的确定性方法，该方法简单,不需要目标函数可微，对于变量数目较少的无约束最优化问题，是一种程序简单而又比较有效的方法本文就是将旋转方向法加入实码遗传算法进化过程中，将遗传算法每次演化所产生的最优秀个体选作被学习对象，让其作为旋转方向法的初值，经过探测移动和旋转方向的学习，把学习后的个体加入到实码遗传算法每次演化所产生的群体中，并去掉最差的个体，以保持原来群体的规模,这样得到新的父代群体.重新对父代群体进行评价、选择、杂交、变异和学习，如此反复演化为了使收敛速度更快，并得到全局解

6、，本文在算法中加入了“加速循环”这一步骤达到了预期的效果2 求解非线性优化问题的混合遗传算法不失一般性，设不可微非线性函数的优化问题为如下的最小化问题： (1) n),1,2,(j as.t , )(min)()(j)jjbxxf其中，为优化变量集，为的变化区间，为优化变量n,1,2,j , )(jxxb , (j)( ja)( jxn数目，为非线性目标函数)(xf2.1 旋转方向法为了能让旋转方向法应用于有约束的上述优化问题，本文对其进行了改进旋转方向法步骤如下：步一 选取初始数据选取初始点，初始单位正交方向组（可取0Xnddd,21为坐标轴方向）给定初始步长收缩因子nddd,21neee,

7、210),(002010n，放大因子，允许误差，令) 1 , 0(100k步二 确定参考点取参考点并令（kXZ 000 ,finishj , curjprej）其中用来记录前一轮循环中每个方向的探测结果，用来记录本次循nj, 2 , 1precur环中每个方向的探测结果。用来记录每一个方向是否出现了“成功，失败” ，1 表finish示探测成功或出现了“成功，失败” ，0 表示探测失败或没出现“成功，失败” 步三 进行轴向探测令，依次沿个方向进行探测如下：1jnj, 2 , 1n作 若则令)( jkjdZ)()() (jjjkjadZ)()() (jjjkjadZ 若则令)()() (jjjk

8、jbdZ)()() (jjjkjbdZ其中表示的第个分量jjkjdZ) ()()( jkjdZj 若令 转)() ()(ZfdZfjkj)( jkjdZZkjkj 1curj步四，否则令，若令转步四，kjkj 0curj1prej1finishj步四 检验探测次数若令返回步三，否则，转步五nj 1 jjcurpre 步五 检验步长大小若对一切有迭代终止nj, 2 , 1kj步六 判断探测是否结束若对一切有，转步七，否则转nj, 2 , 11finishj步三步七 检查是否满足终止条件令，若，则，即为ZXk1kkXX11*kXX最优解，否则转步八步八 进行轴向旋转令,Tnaaap),(211)(

9、1asignu uepw 11,对令， ，返回步二其中表示第111anj, 3 , 2waepjjj 1 kkje元素是 1 其余元素是 0 的维单位列向量j下述图 1 为旋转方向法的流程图旋转方向法设定的参数由初始单位正交向量初始步长，收缩因子，放大因子，允许误neee,21)0()0(2)0(10,n) 1 , 0(1差0 1curj, Z )e (Z Z ) ( ) ()(j)(j(j)j)()()(jjjjjjjjjjjjjjjjjbabbeZeZZbeZa则若则若则若 j=n?j=j+1?)() (ZfeZfjjkXZ j=1初始点，初始正交向量组0 xn),1,2,(j , jje

10、p初始步长，.),(21n1010k=0prej=0,curj=0,finishj=0, n),1,2,(j 0curj jjprej=1?finishj=1否是是否是否 1curj, Z )e (Z Z ) ( ) ()(j)(j(j)j)()()(jjjjjjjjjjjjjjjjjbabbeZeZZbeZa则若则若则若 j=n?j=j+1?)() (ZfeZfjjkXZ j=1初始点，初始正交向量组0 xn),1,2,(j , jjep初始步长，.),(21n1010k=0prej=0,curj=0,finishj=0, n),1,2,(j 0curj jjprej=1?finishj=1

11、否是是否是否 1curj, Z )e (Z Z ) ( ) ()(j)(j(j)j)()()(jjjjjjjjjjjjjjjjjbabbeZeZZbeZa则若则若则若 j=n?j=j+1?)() (ZfeZfjjkXZ j=1初始点，初始正交向量组0 xn),1,2,(j , jjep初始步长，.),(21n1010k=0prej=0,curj=0,finishj=0, n),1,2,(j 0curj jjprej=1?finishj=1否是是否是否 1curj, Z )e (Z Z ) ( ) ()(j)(j(j)j)()()(jjjjjjjjjjjjjjjjjbabbeZeZZbeZa则若

12、则若则若 j=n?j=j+1?)() (ZfeZfjjkXZ j=1初始点，初始正交向量组0 xn),1,2,(j , jjep初始步长，.),(21n1010k=0prej=0,curj=0,finishj=0, n),1,2,(j 0curj jjprej=1?finishj=1否是是否是否 1curj, Z )e (Z Z ) ( ) ()(j)(j(j)j)()()(jjjjjjjjjjjjjjjjjbabbeZeZZbeZa则若则若则若 j=n?j=j+1?)() (ZfeZfjjkXZ j=1初始点，初始正交向量组0 xn),1,2,(j , jjep初始步长，.),(21n101

13、0k=0prej=0,curj=0,finishj=0, n),1,2,(j 0curj jjprej=1?finishj=1否是是否是否 1curj, Z )e (Z Z ) ( ) ()(j)(j(j)j)()()(jjjjjjjjjjjjjjjjjbabbeZeZZbeZa则若则若则若 j=n?j=j+1?)() (ZfeZfjjkXZ j=1初始点，初始正交向量组0 xn),1,2,(j , jjep初始步长，.),(21n1010k=0prej=0,curj=0,finishj=0, n),1,2,(j 0curj jjprej=1?finishj=1否是是否是否 ZXk1kkXX1

14、 11112111111),(, ),(aasignepwaaaXXXXpTnkkkkwaejj pn ,2,3,j j对k=k+1 ZX*对?, 2 , 1jnj 1?finishjn,1,2,j 对 ZX*否是否是否是图 1：旋转方向法的流程图 2.2 混合遗传算法混合遗传算法包括如下九步：步一 编码这里采用实数编码，即利用如下变换 n),1,2,j ( )()()()()()(jjjjjabyax（2）把初始变化范围为区间上的第个优化变量对应到区间上随机数)()( jjbaj)( jx 1 0)( jy步二 初始父代个体的生成随机生成 m 组 n 个区间上的均匀随机数，作为 m 1 0个

15、初始父代群体m),1,2,i ,n ,1,2,(j ),(ijy步三 父代个体的适应能力评价把第 i 个个体代入式(1)，得到相应的优化准则越小，其适应函数就越大则该个体的适应能力就越强)(if)(if1)(1)(2ifiF步四 父代个体的选择把已有的父代个体按优化准则值，从小到大排序，称)(if排序后最前面的几个个体为优秀个体，构造函数，从这些父代个体中，以miiFiFip1)()()(概率选择第 i 个个体，共选择 m-p 个个体，为增加混合遗传算法进行持续全局优化搜)(ip索能力，这里把最优秀的个父体直接加进子代群体中，进行移民操作后,得到个子代m；.n ,1,2,j ),(y1ijm,

16、1,2,i 步五 父代个体的杂交按概率随机选择一对父代个体作为双亲，)(ip),(),(21ijyijy并以杂交概率进行算术杂交，产生一个子代个体cp),(2ijyminj, 2 , 1 , 2 , 1步六 父代个体的自适应变异在混合遗传算法中父代个体的适应度数值越小，),(ijy其选择概率越小，则对该个体进行变异的概率应越大，因此遗传算法的操作是，)(ip)(ipm采用自适应变异的概率来代替，从而得到子代)(1)(ipipm),(ijy),(3ijynj, 2 , 1，即，；，其中，mi, 2 , 1),(3ijy)( ju)(ipumm),(3ijy),(ijy)(ipumm)( ju和均

17、为上的随机数nj, 2 , 1mu 1 , 0步七 排序，由步四至步六得到个子代个体，按其适应度函数值从大到小进行排m3序，取排在最前面的个子代个体作为新的群体，以保持原有群体的规模步八 演化迭代用步七产生的最优秀的第一个个体，作为初值调用旋转方向法子程序，并利用旋转方向法得到最优解替代步七排序后得到第个个体这样得到新的父代群体，转步三重新对父代群体进行评价，选择，杂交，变异和学习，如此反复演化步九：加速循环用上面步一至步八第一次演化迭代所产生的一组前 s 个优秀个体，这一子群体所对应的变量变化区间，作为新的初始变化区间，混合遗传算法转步一，如此加速循环，优秀个体的变化区间逐步调整和收缩，与最

18、优解的距离将越来越近，直到最有个体的目标函数值小于某一定值或算法进行到预定循环次数，结束整个算法运行，把当前群体中最优秀个体指定为混合遗传算法的结果此算法克服了遗传算法进行全局搜索，但收敛速度慢，旋转方向法善长微调，但常会陷入局部最优的缺陷能较大概率快速搜索到全局最优解3 混合遗传算法的收敛性分析个优化变量的问题和加速循环次的情况下，优秀个体包围最优点的概率为nqopp.qsn)5 . 01 (1 (80s表 1 混合遗传算法优秀个体包围最优点的概率opp优秀个体数目s优化变量数目n加速循环次数q opp100370.999 988 885 209 7080370.999 839 412 25

19、8 49803100.999 770 596 835 3650370.991 212 622 530 82表 1 中取值的精确度为.opp1410定理 在收缩区间比小于常数，的条件下，混合遗传算法收敛1证 设混合遗传算法的第 代的搜索空间为t1,2, tn,1,2,j | ),()()(21tjjtjntbxaxxxI由算法的过程知1,2, 121tIIIItt即 n,1,2,j ;1,2, t,)()()2()2()1()1(tjtjjjjjbababa对于任意的正整数 ，闭区间显然是一个完备距离空间.t,)()(tjtjba作映射 , )()()()1()()()()1()1(tjtjtj

20、tjtjtjtjtjjbaxaaxababT则 ,)()()1()1(tjtjtjtjjbabaT所以是到自身的映射.jT,)()(tjtjba又因为对于，有,)()( tjtjbaxx| )()()1()1( xxababTTtjtjtjtjjj由于收缩区间比小于常数，1所以 10)()()1()1(tjtjtjtjabab取 ) 1(21)()()1()1(tjtjtjtjabab则 10得 | xxTTjj故为上的一个压缩映照，根据巴拿赫不动点原理，存在唯一的.jT,)()(tjtjba,)()(tjtjjba则存在唯一的一个向量1,2, tIt所以混合遗传算法在收缩区间比小于常数，的条

21、件下（由表 1 知控制参数1时这一条件以较大概率满足）是收敛的. (证毕)80,200sm4 实例分析求 min2332221sin)6()5(x 4)(xxxf s.t 746332321xxx取不同的参数得到的最优解,最优值,新的区间,所用时间如：表 2 （最后区间下界和最后上界是指：变量的新的变化区间如表中的第一条记录新的变化范围为：321,xxx321,xxx）(程序见附录中 1-1 程序)4961. 64415. 4 ,0000. 66739. 5 ,0000. 597. 7 . 4321xxx表 2 混合遗传算法求解实例的结果样本规模（m） 被选择的优秀父代个体数（ ）s杂交概率c

22、p算术杂交系数（）循环次数（q）最优解（）x最优值(f)最后区间下界（a）最后区间上界（b）所用时间（t）2001000.50.575.00006.00005.9961-0.99994.70975.67394.44155.00006.00006.496127.3790s200800.80.575.00016.00004.9062-1.00004.38144.80714.16795.46886.00006.984726.4980s5002200.50.575.00016.00005.0824-1.00004.88905.99995.08245.00016.00005.0824132.4210s2

23、00500.80.174.99996.00005.8984-0.99754.70035.42404.57305.36406.00016.733028.4610s200500.50.175.00006.00005.4452-0.99993.97843.99744.03066.01006.00006.961626.9480s 用文献4求解上述例题的的结果如：表 3（程序见附录中 1-2 程序）表 3 用文献4求解实例的结果样本规模（m） 被选择的优秀父代个体数( )s杂交概率cp算术杂交系数（）循环次数（q）最优解（）x最优值(f)最后区间下界（a）最后区间上界（b）所用时间（t）2001000.

24、50.574.98095.94325.6182-0.99344.90545.88655.51015.05646.00005.726484.4810s200800.80.574.99886.00004.1039-0.99764.99886.00004.10394.99886.00004.103984.5010s5002200.50.575.05206.00005.9127-0.98504.84565.74305.36265.05206.00005.9127195.3110s200500.80.175.10256.00006.3529-0.95805.10256.00006.09605.10256

25、.00006.352951.0740s200500.50.174.90616.00004.5154-0.93554.87955.96944.27564.90616.00004.515447.5690s由表 2 和表 3 可知：在参数样本规模、被选择的优秀父代个体数、杂交概率、算术杂交系数和循环次数相同的条件下，无论是从最优解还是程序运行所用时间方面来看，本论文的算法都优于文献4的算法5 参数说明对于不同的问题样本规模取 200；被选择的优秀父代个体数取 80；杂交概率取0.5,0.8 区间上的数；算术杂交系数取（0,1）区间上的数；循环次数取 7能以较大概率快速求出全局最优解对于变量个数超过

26、10 的问题的求解，样本规模取 500,被选择的优秀父代个体数取 200，运算出的结果较理想结论 本文提出了一种求解非线性优化问题的方法混合遗传算法，该算法简单实用，对优化问题无需连续性、可微性的要求，能以较大概率搜索到全局最优解，是解决约优化问题的一种有效方法.仿真实例表明，在求解精度、收敛速度等方面，该算法均能取得令人满意的结果.致谢感谢周莉老师在百忙中给予本文的指导，以及对我本人的鼓励与支持同时感谢鲁东大学数学与信息学院的全体老师在四年的大学生活给与我的关怀与教导参考文献1 玄光男，程润伟著遗传算法与工程优化北京：清华大学出版社，20042 李敏强，林丹等著遗传算法的基本理论与应用北京：

27、科学出版社，20023 粟塔山，彭伟杰等著最优化计算原理与算法程序设计湖南：国防科技大学出版社，20014 杨晓华等著解非线性优化问题的混合加速遗传算法北京师范大学学报第 39 卷第 4 期，2003附录1-1 程序目标函数function f=fun(x) f=4*(x(1)-5)2+(x(2)-6)2+sin(x(3)23) n=3 m=5 a=2 3 4 b=3 6 7/求解过程/clc tica=2 3 4 b=8 6 7 pt=0.5 m=200 n=3 t=-0.5q=0;p=100A=;B=rand(n,m);A=a*ones(1,m)+diag(b-a)*B;while qf(

28、j) g=f(i); f(i)=f(j); f(j)=g; G=A(:,i); A(:,i)=A(:,j); A(:,j)=G; endendendAA=A(:,1:p) A(:,1:(m-p);D=;for i=1:floor(m*pt) c=rand(1,m); kk=find(c=max(c); ss=find(c=min(c); D(:,i)=A(:,kk)+t*(A(:,kk)-A(:,ss);endAAA=A(:,1:m-floor(m*pt),D;F=;for i=1:m F(i)=1/(f(i)2+1);endfor i=1:m pm(i)=F(i)/(1-sum(F); if

29、 randf(j) g=f(i); f(i)=f(j); f(j)=g; G=E(:,i); E(:,i)=E(:,j); E(:,j)=G; end endendA=E(:,1:m);bata=1.2;alph=-0.5;w=ones(n,1);pre=zeros(n,1);cur=zeros(n,1);finish=zeros(n,1);x=A(:,1);v=eye(n);z=x;e=v;t=0;zc=1;while t=0 zc=zc+1; if zc500 t=7; end for i=1:n if fun(z+w(i).*e(:,i)=a(j)&(zz(j)=b(j) z(j

30、)=zz(j); end if zz(j)b(j) z(j)=b(j); end end w(i)=w(i)*bata; cur(i)=1; else w(i)=w(i)*alph; cur(i)=0; if pre(i)=1 finish(i)=1; end end end pre=cur; h=1; for j=1:n if abs(w(j)0.0001 l=1; h=l*h else l=0; h=h*l end end if h=1 t=1; for k=1:n if finish(k)=1 r=1; t=t*r; else r=0; t=t*r; end end else x=z b

31、reak; end if norm(z-x)0.0001&t=0 zc=zc+1; if zc500 t=7 end v(:,1)=(z-x)/norm(z-x); d=sign(v(1,1); c=v(:,1)+d*e(:,1); aa=1/(1+abs(v(1,1); for j=2:n v(:,j)=e(:,j)-aa*v(j,1).*c end e=v; pre=zeros(n,1);cur=zeros(n,1);finish=zeros(n,1);z=x;t=0while t=0 zc=zc+1; if zc500 t=7; end for i=1:n if fun(z+w(

32、i).*e(:,i)=a(j)&(zz(j)=b(j) z(j)=zz(j); end if zz(j)b(j) z(j)=b(j); end end w(i)=w(i)*bata; cur(i)=1; else w(i)=w(i)*alph; cur(i)=0; if pre(i)=1 finish(i)=1; end end end cc=cur pre=cur; h=1; for j=1:n if abs(w(j)0.0001 l=1; h=l*h else l=0; h=h*l end end if h=1 t=1; for k=1:n if finish(k)=1 r=1;

33、t=t*r; else r=0; t=t*r; end end else x=z break; end if norm(z-x)0.0001 x=z; break; endendA(:,m)=x;for i=1:n a(i)=min(A(i,:) b(i)=max(A(i,:)endendendfun(A(:,1)endA(:,1)toc /以下是 1-2 程序/目标函数function f=fun(x) f=4*(x(1)-5)2+(x(2)-6)2+sin(x(3)23) n=3 m=5 a=2 3 4 b=3 6 7/求解过程/clc tica=2 3 4 b=8 6 7 pt=0.5 m=200 n=3 t=-0.5q=0;p=100A=;B=rand(n,m);A=a*ones(1,m)+diag(b-a)*B;while qf(j) g=f(i); f(i)=f(j); f(j)=g; G=A(:,i); A(:,i)=A(:,j); A(:,j)=G; endendendAA=A(:,1:p) A(:,1:(m-p);D=;for i=1:floor(m*pt) c=rand(1,m); kk=find(c=max(c); ss=find(c=min(c); D(:,i)=A(:,kk)+t*(A(:,kk)-A(:,ss);endAAA=A