智能优化算法作业

1、一、优化算法及其应用1.简介共轭梯度法（Conjugate Gradient）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。 2.算法原理共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。设二次函

2、数为，其中为常数，为维列向量，为对称正定矩阵，用共轭梯度法求的极小点：共轭梯度法探索的第一步是沿负梯度方向。即点按方向找到，然后沿着与上一次探索方向相共轭的方向进行探索直达到最小点。令。上式的意义就是以原来的负梯度的一部分即，加上新的负梯度，构造。在上式中的选择，应使维欧氏空间中的两个非零向量与关于矩阵共轭。即因，故有若令二式相减，得设在第次迭代中代入上式，得式中为第次迭代的最优步长。由式和式，得将式和式代入上式，得因为是一正交系，故有或故上式可简化为得用一维探索最优化方法确定，即求或用解析法，使求得。或由式，得即又由于进行一维最优化搜索，故有由上两式可求得如此，即可得到共轭梯度法的一组计算公

3、式为3.算法步骤用共轭梯度法求无约束多维极值问题的算法步骤如下：（1） 给定初始点，及精度；（2） 若，停止，极小值点为，否则转步骤（3）；（3） 取，且置；（4） 用一维搜索法求，使得，令，转步骤5；（5） 若，停止，极小值点为，否则转步骤（6）；（6） 若，令，转步骤（3），否则转步骤（7）；（7） 令，置，转步骤（4）。4.算法的MATLAB实现在MATLAB中编程实现的共轭梯度法函数为：功能：用共轭梯度法求解多维函数的极值。调用格式：其中，：目标函数； ：初始点； ：自变量向量； ：目标函数取最小值时的自变量值； ：目标函数的最小值。共轭梯度法的MATLAB程序代码如下：functio

4、n x,minf=minGETD(f,x0,var,eps)%目标函数:f;%初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x;%目标函数的最小值:minf;format long;if nargin=3 eps=1.0e-6;endx0=transpose(x0);n=length(var);syms l;gradf=jacobian(f,var); %梯度方向v0=Funval(gradf,var,x0);p=-transpose(v0);k=0;while 1 v=Funval(gradf,var,x0); tol=norm(v); if tol=eps x=x0;

5、 break; end y=x0+l*p; yf=Funval(f,var,y); a,b=minJT(yf,0,0.1); xm=minHJ(yf,a,b); x1=x0+xm*p; vk=Funval(gradf,var,x1); tol=norm(vk); if tolt s=-fi; if count=0 s=-fi; else s=s1; end x=x+a*s; f=subs(f,xi,yi,x); f1=diff(f); f1=solve(f1); if f1=0 ai=double(f1); else break x,f=subs(f,xi,yi,x),count end x=

6、subs(x,a,ai); f=xi-xi2+2*xi*yi+yi2; fxi=diff(f,xi); fyi=diff(f,yi); fxi=subs(fxi,xi,yi,x); fyi=subs(fyi,xi,yi,x); fii=fxi,fyi; d=(fxi2+fyi2)/(fx2+fy2); s1=-fii+d*s; count=count+1; fx=fxi; fy=fyi;endx,f=subs(f,xi,yi,x),count输入：conjugate_grad_2d(0,0,0.0001)结果：x = 0.24998825499785 -0.24999998741273f =

7、0.12499999986176count = 10ans = 0.12499999986176例2试用共轭梯度法求解目标函数的极小值。设初始点。解：原函数的梯度为第一次探索的方向：由式，得由此得求点处的梯度为由式求：第二次探索的方向：由式求探索步长为：由此得gademo 方式2step 1 编写目标函数gademo1eval1.mfunction sol, val = gaDemo1Eval(sol,options)x=sol(1);val = x + 10*sin(5*x)+7*cos(4*x);step 2 生成初始种群，大小为10initPop=initializega(10,0, 9

8、,gademo1eval1,1e-6,1);step 325次遗传迭代 x, endPop,bpop,trace = ga(0 9,gademo1eval1,initPop,.1e-6 1 1,maxGenTerm,25,.normGeomSelect,0.08,.arithXover,2,.nonUnifMutation,2, 25 ,3)% Output Arguments:% x- the best solution found during the course of therun% endPop - the final population % bPop - a trace of t

9、he best population(解的变化)% traceInfo- a matrix of best and means of the ga for each generation(种群平均值的变化)% Input Arguments:% bounds - a matrix of upper and lower boundson the variables% evalFN- the name of the evaluation .m function% evalOps - options to pass to the evaluation function (NULL)% startPo

10、p - a matrix of solutions that can be initialized%from initialize.m% opts - epsilon, prob_ops ,display change required to consider two solutions different, prob_ops 0 if you want to apply the%genetic operators probabilisticly to each solution, 1 if you are supplying a deterministic number of operato

11、rapplications and display is 1 to outputprogress 0 forquiet. (1e-6 1 0)% termFN- name of the .m termination function (maxGenTerm)% termOps- options string to be passed to the terminationfunction(100).% selectFN - name of the .m selection function(normGeomSelect)% selectOpts - options string to be pa

12、ssed to select after%select(pop,#,opts) (0.08)% xOverFNS - a string containing blank seperated names of Xover.m files (arithXover heuristicXover simpleXover) % xOverOps - A matrix of options to pass to Xover.m files with the first column being the number of that xOver to perform similiarly for mutation (2 0;2 3;2 0)% mutFNs - a string containing blank seperated names of mutation.m files (boundaryMutation multiNonUnifMutation .% nonUn