公共政策执行的性质
鲁东大学
毕 业 设 计 （论 文）
设计（论文）题目：一种求解非线性优化问题的混合遗传算法
姓 名 苗婷 院 系 数学与信息学院 专 业 数学与应用数学 年 级 学 号 2001E110222 指导教师 周莉
2005年 6 月 1日
一种求解非线性优化问题的混合遗传算法
苗婷
数学与信息学院数学与应用数学专业2001级数本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 optimal 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 nonlinear optimal method.
[Key words] real code ；Rosenbrock algorithm; hybrid genetic algorithm.
目录
1 引言 . ............................................................................................................................................................... 1 2 求解非线性优化问题的混合遗传算法 . ....................................................................................................... 1 2.1 旋转方向法 . ............................................................................................................................................ 1 2.2 混合遗传算法 . ........................................................................................................................................ 4 3 混合遗传算法的收敛性分析 . ....................................................................................................................... 6 4 实例分析 . ....................................................................................................................................................... 7 5 参数说明 . ....................................................................................................................................................... 9 结论 . ................................................................................................................................................................. 9 致谢 . ................................................................................................................................................................. 9 参考文献 . ............................................................................................................................................................. 9 附录 . ............................................................................................................................................................... 10
1 引言
求解非线性优化问题的方法很多，有一维搜索法，共轭梯度法，牛顿型方法等．但这些方法都要求非线性函数可微，或至少连续，有一定的局限性．因此，寻找一种求解不可微非线性函数优化问题的算法是非常必要的．旋转方向法是一种局部直接寻优的确定性方法，该方法简单, 不需要目标函数可微，对于变量数目较少的无约束最优化问题，是一种程序简单而又比较有效的方法．本文就是将旋转方向法加入实码遗传算法进化过程中，将遗传算法每次演化所产生的最优秀个体选作被学习对象，让其作为旋转方向法的初值，经过探测移动和旋转方向的学习，把学习后的个体加入到实码遗传算法每次演化所产生的群体中，并去掉最差的个体，以保持原来群体的规模, 这样得到新的父代群体. 重新对父代群体进行评价、选择、杂交、变异和学习，如此反复演化．为了使收敛速度更快，并得到全局解，本文在算法中加入了“加速循环”这一步骤．达到了预期的效果．
2 求解非线性优化问题的混合遗传算法
不失一般性，设不可微非线性函数的优化问题为如下的最小化问题：
min f (x ) , s.t a (j)≤x (j ) ≤b (j ) (j=1,2, , n) (1)
其中，x ={x (j ) , j =1,2, , n }为优化变量集，[a (j ) , b (j)]为x (j ) 的变化区间，n 为优化变量数目，f (x ) 为非线性目标函数．
2.1 旋转方向法
为了能让旋转方向法应用于有约束的上述优化问题，本文对其进行了改进．
旋转方向法步骤如下：
步一 选取初始数据．选取初始点X 0，初始单位正交方向组d 1, d 2, , d n （可取
00
d 1, d 2, , d n 为坐标轴方向e 1, e 2, e n ）给定初始步长σ0=(σ10, σ2, , σn ) >0收缩因子
α∈(0, 1) ，放大因子β>1，允许误差ε>0，令k =0．
步二 确定参考点．取参考点Z =X k 并令pre[j]=0 , cur[j]=0 ,finish[j ]=0 （j =1, 2, , n ）其中pre 用来记录前一轮循环中每个方向的探测结果，cur 用来记录本次循环中每个方向的探测结果。finish 用来记录每一个方向是否出现了“成功，失败”，1表示探测成功或出现了“成功，失败”，0表示探测失败或没出现“成功，失败”．
步三 进行轴向探测．令j =1，依次沿j =1, 2, , n ．n 个方向进行探测如下：
k k
作Z +σk j d (j ) 若 (Z +σj d (j ) ) j
k
若 (Z +σk j d (j ) ) j >b (j ) 则令(Z +σj d (j ) ) j =b (j ) k
其中(Z +σk j d (j ) ) j 表示Z +σj d (j ) 的第j 个分量
k k k
j]=1． 若 f (Z +σk 转j d (j ) )
k
步四，否则令σk j =-α σj ，cur[j]=0，若pre[j]=1令finish[j]=1 转步四，
步四 检验探测次数．若j
步五 检验步长大小．若对一切j =1, 2, , n ．有σk j
步六 判断探测是否结束．若对一切j =1, 2, , n ．有finish[j]=1，转步七，否则转
步三．
步七 检查是否满足终止条件．令X k +1
=Z ，若X k +1-X k
步八 进行轴向旋转．令p 1=(a 1, a 2, , a n ) T , u =sign (a 1) , w =p 1+e 1 u
σ=
1
, 对j =2, 3, , n ．令p j =e j -σ a j w ， k =k +1 ，返回步二．其中e j 表示第1+a 1
j 元素是1其余元素是0的ｎ维单位列向量．
下述图1为旋转方向法的流程图．旋转方向法设定的参数由初始单位正交向量
(0) (0)
，收缩因子α∈(0, 1) ，放大因子β>1，允许误e 1, e 2, , e n 初始步长σ0=σ1(0) , σ2, , σn
差ε>0．
2.2 混合遗传算法
混合遗传算法包括如下九步：
步一 编码．这里采用实数编码，即利用如下变换
x (j ) =a (j ) +y (j ) (b (j ) -a (j ) ) （2） ( j =1,2, , n) 把初始变化范围为a (j ) b (j ) 区间上的第j 个优化变量x (j ) 对应到[0 1]区间上随机数y (j ) ．
步二 初始父代个体的生成．随机生成m 组n 个[0 1]区间上的均匀随机数，作为m 个初始父代群体y (j , i ) (j=1,2, , n , i =1,2, , m) ．
步三 父代个体的适应能力评价．把第i 个个体代入式(1)，得到相应的优化准则
f (i ) ．f (i ) 越小，其适应函数F (i ) =
[]
1
就越大．则该个体的适应能力就越强． 2
f (i ) +1
步四 父代个体的选择．把已有的父代个体按优化准则值f (i ) ，从小到大排序，称排序后最前面的几个个体为优秀个体，构造函数p (i ) =
F (i )
∑F (i )
i =1
m
，从这些父代个体中，以
概率p (i ) 选择第i 个个体，共选择m-p 个个体，为增加混合遗传算法进行持续全局优化搜索能力，这里把最优秀的ｐ个父体直接加进子代群体中，进行移民操作后, 得到m 个子代
y 1(j , i ) j =1,2, , n ； i =1,2, , m .
步五 父代个体的杂交．按概率p (i ) 随机选择一对父代个体y (j , i 1), y (j , i 2) 作为双亲，并以杂交概率p c 进行算术杂交，产生一个子代个体y 2(j , i ) j =1, 2, , n i =1, 2, , m ．
步六 父代个体的自适应变异．在混合遗传算法中父代个体y (j , i ) 的适应度数值越小，其选择概率p (i ) 越小，则对该个体进行变异的概率p m (i ) 应越大，因此遗传算法的操作是，采用自适应变异的概率p m (i ) =1-p (i ) 来代替y (j , i ) ，从而得到子代
y 3(j , i ) j =1, 2, , n
i =1, 2, , m ，即y 3(j , i ) ＝u (j ) ，u m
步七 排序，由步四至步六得到3m 个子代个体，按其适应度函数值从大到小进行排序，取排在最前面的ｍ个子代个体作为新的群体，以保持原有群体的规模．
步八 演化迭代．用步七产生的最优秀的第一个个体，作为初值．调用旋转方向法子
程序，并利用旋转方向法得到最优解替代步七排序后得到第ｍ个个体．这样得到新的父代群体，转步三．重新对父代群体进行评价，选择，杂交，变异和学习，如此反复演化．
步九：加速循环．用上面步一至步八第一次演化迭代所产生的一组前s 个优秀个体，这一子群体所对应的变量变化区间，作为新的初始变化区间，混合遗传算法转步一，如此加速循环，优秀个体的变化区间逐步调整和收缩，与最优解的距离将越来越近，直到最有个体的目标函数值小于某一定值或算法进行到预定循环次数，结束整个算法运行，把当前群体中最优秀个体指定为混合遗传算法的结果．
此算法克服了遗传算法进行全局搜索，但收敛速度慢，旋转方向法善长微调，但常会陷入局部最优的缺陷．能较大概率快速搜索到全局最优解．
3 混合遗传算法的收敛性分析
混合遗传算法先是利用实码遗传算法每次演化所产生的最优秀个体作为初值，经过探测移动和旋转方向的学习，再利用旋转方向法搜索得到的局部最优解作为优秀个体加入演化迭代中，从而得到新的优秀个体群来调整搜索范围的. 混合遗传算法的全局优化是精确的. 在n 个优化变量的问题和加速循环q 次的情况下，优秀个体包围最优点的概率p op 为
(1-(1-0. 5n ) s ) q ，参见表1. 混合遗传算法是较大概率全局收敛的. 为了平衡群体规模和算法的收敛速度之间的矛盾，混合遗传算法取s =80.
表1 混合遗传算法优秀个体包围最优点的概率p op
表1中p op 取值的精确度为10-14.
定理 在收缩区间比小于常数α，α
证 设混合遗传算法的第t 代的搜索空间为
I t ={(x 1, x 2, , x n ) |a (j t ) ≤x j ≤b (j t ) j =1,2, , n } t=1,2,
由算法的过程知I 1⊇I 2⊇ ⊇I t ⊇I t +1⊇ t =1,2,
即 [a (j 1) , b (j 1) ]⊇[a (j 2) , b (j 2) ]⊇ ⊇[a (j t ) , b (j t ) ]⊇ t=1,2, ; j =1,2, , n 对于任意的正整数t ，闭区间[a (j t ) , b (j t ) ]显然是一个完备距离空间.
作映射 T j =
b (j t +1) -a (j t +1) b (j t ) -a (j t )
(x -a (j t ) ) +a (j t +1) x ∈[a (j t ) , b (j t ) ]
则 T j [a (j t +1) , b (j t +1) ]⊆[a (j t ) , b (j t ) ] 所以T j 是[a (j t ) , b (j t ) ]到自身的映射. 又因为对于∀x ' , x ' ' ∈[a (j t ) , b (j t ) ]，有
|T -T |=
' j ' ' j
b (j t +1) -a (j t +1) b (j t ) -a (j t )
|x ' -x ' ' |
由于收缩区间比小于常数α，α
b (j t +1) -a (j t +1) b
(t ) j
-a
(t ) j
(t +1) (t +1) 1b j -a j
+1) 取 β=((t )
2b j -a (j t )
则 0
得 |T j ' -T j ' ' |
故T j 为[a (j t ) , b (j t ) ]上的一个压缩映照，根据巴拿赫不动点原理，存在唯一的ξj ∈[a (j t ) , b (j t ) ]. 则存在唯一的一个向量γ∈I t t =1,2,
所以混合遗传算法在收缩区间比小于常数α，α
m =200, s =80时这一条件以较大概率满足）是收敛的. (证毕)
4 实例分析
23
求min f (x ) =4 (x1-5) 2+(x 2-6) 2+sin x 3
2≤x 1≤3
s.t 3≤x 2≤6
4≤x 3≤7
取不同的参数得到的最优解, 最优值, 新的区间, 所用时间如：表2．（最后区间下界和最后上界是指：变量x 1, x 2, x 3的新的变化区间如表中的第一条记录x 1, x 2, x 3新的变化范围为：
4. 7. 97≤x 1≤5. 0000, 5. 6739≤x 2≤6. 0000, 4. 4415≤x 3≤6. 4961）(程序见附录中1-1程序)
用文献[4]求解上述例题的的结果如：表3（程序见附录中1-2程序）
由表2和表3可知：在参数样本规模、被选择的优秀父代个体数、杂交概率、算术杂
交系数和循环次数相同的条件下，无论是从最优解还是程序运行所用时间方面来看，本论文的算法都优于文献[4]的算法．
5 参数说明
对于不同的问题样本规模取200；被选择的优秀父代个体数取80；杂交概率取[0.5,0.8] 区间上的数；算术杂交系数取（0,1）区间上的数；循环次数取7．能以较大概率快速求出全局最优解．对于变量个数超过10的问题的求解，样本规模取500, 被选择的优秀父代个体数取200，运算出的结果较理想．
结论
本文提出了一种求解非线性优化问题的方法——混合遗传算法，该算法简单实用，对优化问题无需连续性、可微性的要求，能以较大概率搜索到全局最优解，是解决约优化问题的一种有效方法. 仿真实例表明，在求解精度、收敛速度等方面，该算法均能取得令人满意的结果.
致谢
感谢周莉老师在百忙中给予本文的指导，以及对我本人的鼓励与支持．同时感谢鲁东大学数学与信息学院的全体老师在四年的大学生活给与我的关怀与教导．
参考文献
[1] 玄光男，程润伟著．遗传算法与工程优化． 北京：清华大学出版社，2004 [2] 李敏强，林丹等著．遗传算法的基本理论与应用．北京：科学出版社，2002 [3] 粟塔山，彭伟杰等著．最优化计算原理与算法程序设计．湖南：国防科技大学出版社，2001
[4] 杨晓华等著．解非线性优化问题的混合加速遗传算法．北京师范大学学报第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 tic
a=[2 3 4]' b=[8 6 7]' pt=0.5 m=200 n=3 t=-0.5 q=0; p=100 A=[];
B=rand(n,m);
A=a*ones(1,m)+diag(b-a)*B; while q
f(i)=fun(A(:,i)); end g=[]; G=[]; for i=1:m
for j=i+1:m if f(i)>f(j) g=f(i); f(i)=f(j); f(j)=g; G=A(:,i); A(:,i)=A(:,j); A(:,j)=G; end
end end
AA=[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)); end
AAA=[A(:,1:m-floor(m*pt)),D]; F=[]; for i=1:m
F(i)=1/(f(i)^2+1); end
for i=1:m
pm(i)=F(i)/(1-sum(F)); if rand
A(:,i)=a+diag(b-a)*rand(n,1); end end
E=[AA,AAA,A]; for i=1:3*m
f(i)=fun(E(:,i)) end for i=1:3*m
for j=i+1:3*m if f(i)>f(j) g=f(i); f(i)=f(j); f(j)=g; G=E(:,i); E(:,i)=E(:,j); E(:,j)=G; end end end
A=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 zc>500 t=7; end
for i=1:n
if fun(z+w(i).*e(:,i))
if (zz(j)>=a(j))&&(zz(j)
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))
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 break; end
if norm(z-x)
while norm(z-x)>0.0001&&t==0 zc=zc+1; if zc>500 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=0
while t==0 zc=zc+1; if zc>500 t=7; end
for i=1:n
if fun(z+w(i).*e(:,i))
if (zz(j)>=a(j))&&(zz(j)
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))
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 break; end
if norm(z-x)
A(:,m)=x; for i=1:n
a(i)=min(A(i,:)) b(i)=max(A(i,:)) end end end
fun(A(:,1)) end A(:,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 tic
a=[2 3 4]' b=[8 6 7]' pt=0.5 m=200 n=3 t=-0.5 q=0; p=100 A=[];
B=rand(n,m);
A=a*ones(1,m)+diag(b-a)*B; while q
f(i)=fun(A(:,i)); end g=[]; G=[]; for i=1:m
for j=i+1:m if f(i)>f(j) g=f(i); f(i)=f(j); f(j)=g; G=A(:,i); A(:,i)=A(:,j); A(:,j)=G; end end end
AA=[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)); end
AAA=[A(:,1:m-floor(m*pt)),D]; F=[]; for i=1:m
F(i)=1/(f(i)^2+1); end
for i=1:m
pm(i)=F(i)/(1-sum(F)); if rand
A(:,i)=a+diag(b-a)*rand(n,1); end end
E=[AA,AAA,A]; for i=1:3*m
f(i)=fun(E(:,i)) end
for i=1:3*m
for j=i+1:3*m if f(i)>f(j) g=f(i); f(i)=f(j); f(j)=g; G=E(:,i); E(:,i)=E(:,j); E(:,j)=G; end end end
A=E(:,1:m); x=A(:,1); r=0.05; tt=1; v=1;
d=ones(n,1); EE=eye(n); zc=1
while tt==1 zc=zc+1; if zc>500 tt=0; end
y=x; for j=1:n
z=y+d(j).*EE(:,j); yy=[]; for i=1:n
if z(i)
yy(i,1)=a(i,1); end
if z(i)>b(i) yy(i)=b(i); end
if a(i)
if fun(yy)
else
z=y-d(j)*EE(:,j); for i=1:n
if z(i)
yy(i)=a(i);
end
if z(i)>b(i)
yy(i)=b(i);
end
if a(i)
end
if fun(yy)
y=yy;
end
end
end
if fun(y)>fun(x)
d=r*d;
if norm(d)
x=y;
break;
else
tt=1;
continue;
end
else
l=[];
l=(2*y-x);
end
ll=[];
while v==1
for j=1:n
z=l+d(j).*EE(:,j);
for i=1:n
if z(i)
ll(i)=a(i);
end
if z(i)>b(i)
ll(i)=b(i)
end
if z(i)>=a(i)&&b(i)>=z(i) ll(i)=z(i);
end
end
llll=ll'
if fun(llll)
l=llll;
else
z=l-d(j)*EE(:,j); for i=1:n
if z(i)
llll(i)=a(i); end
if z(i)>b(i)
llll(i)=b(i) end
if z(i)>=a(i)&&b(i)>=z(i) llll(i)=z(i); end
end
if fun(llll)
l=llll;
end
end
v=0
end
if fun(l)
x=y;
y=l;
v=1;
else
x=y;
end
d=d*r;
if norm(d)
x=y;
break;
tt=0;
else
tt=1;
end
end
end
A(:,m)=x;
for i=1:n
a(i)=min(A(i,:)) b(i)=max(A(i,:)) end
tt=0
end
fun(A(:,1))
A(:,1)
toc