智能理论与技术.ppt

《智能理论与技术.ppt》由会员分享，可在线阅读，更多相关《智能理论与技术.ppt（67页珍藏版）》请在三一办公上搜索。

1、智能理论与技术,课程纲要,传统最优化技术无约束最优化方法（9学时）有约束最优化方法（自学，3学时）智能优化计算进化计算（15学时）模糊逻辑（9学时）人工神经网络（18学时）,最优化技术的重要性,2优化问题求 的极小值,1求解问题求 的根,一个求解可以问题转变为一个优化问题,传统最优化方法,优化模型的一般形式,Opt.f(xi,yj,k)s.t.gh(xi,yj,k),0 h=1,2,m其中：xi 为决策变量（可控制）yj 为已知参数 k 为随机因素 f 为目标函数 gh 为约束条件,传统最优化方法无约束最优化方法,非梯度搜索,概述,x2,x1,o,(k)S(k),S(k),x(k+1),x(k

2、),x*,F(x(k),F(x(k+1),x(k+1)=x(k)+(k)s(k),迭代公式,在优化设计的迭代运算中，在搜索方向s(k)上寻求最优步长(k)的方法称一维搜索法。,传统最优化方法无约束最优化方法,直接搜索,概述基本方法1、黄金分割法（0.618法）2、二次插值法（抛物线法）3、单纯形算法,5.1 黄金分割法,黄金分割法适用于a,b区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。一、黄金分割法的原理 在搜索区间a,b内适当插入两点x1,x2，并计算其函数值。x1,x2 将区间分为三段，通过比较函数值的大小，删除其中的一段

3、，使搜索区间缩短。然后再在保留下来的区间上作同样处理，如此迭代下去，使搜索区间无限缩小，从而得到极小点的近似值。,5.1 黄金分割法（图5.1.1）,5.1 黄金分割法,插入点x1,x2的位置相对于区间a,b两端点有对称性要求，除对称性要求外，还要求每次迭代区间长度缩短的比率是相同的。设原区间长度为l如图所示，保留区间长度为l，区间缩短率为。进行第二次缩短时，新点为x3,设y1f(x3)则新区间为a,x1为保持相同的区间缩短率，,5.1 黄金分割法（图5.1.1）,5.1 黄金分割法,应有（1-）/=故：1-=2 2+-1=0由此可得：=0.618黄金分割法可使相邻两次搜索区间都具有相同的缩短

4、率0.618。,x1=a+0.382(b-a),x2=a+0.618(b-a),b-x2=x1-a,x2-x1=(b-a),列题：min f(x)=2x2-x-1 初始区间a1,b1=-1,1,精度L 0.16,5.1 黄金分割法,二、黄金分割法的搜索过程 1、给出初始搜索区间a,b及收敛精度。2、按坐标点计算公式计算，并计算相应的函数值,取出较大点 3、用这个较大点做为区间的一端,另一端不变来缩短搜索区间 4、检查是否满足收敛条件 5、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。,5.2 二次插值法,一、插值法概念 假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置，但是

5、没有函数表达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作为原函数最优解的近似解，这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近似求解方法，称为插值方法或函数逼近法。,5.2 二次插值法,二、插值法与试探法的异同点 相同点：都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。,5.2 二次插值法,不同点：试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。例如：黄金分割法是按照等比例0.618缩短率确定的。而在插值法中，试验点的位置是按函数值近似分

6、布的极小点确定的。试探法仅仅利用了试验点函数值进行大小的比较，而插值法还要利用函数值本身或其导数信息。所以，当函数具有较好的解析性质时，插值方法比试探方法效果更好。,5.2 二次插值法,三、二次插值法的概念 利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值方法或抛物线法。,p1,p(x),p3,f(x),f1,x1=a,p2,f2,x2,x*,xP*,f3,x3=b,5.2 二次插值法,四、二次插值函数的构成 过函数曲线上的三点P1(x1,f 1)、P2(x2,f 2)、P3(x3,f 3)作二次插值多项

7、式 p(x)=Ax2+Bx+C 它应满足条件 p(x1)=Ax12+Bx1+C 1=f 1 p(x2)=Ax22+Bx2+C=f 2 p(x3)=Ax32+Bx3+C=f 3,5.2 二次插值法,解方程组，得待定系数A、B、C分别为,5.2 二次插值法,令插值函数p(x)的一阶导数为0，即 p(x)=2ax+b=0 得p(x)极小点为 xp*=B/2 A 代入A、B得,5.2 二次插值法,令则,5.2 二次插值法,若c2=0，则 即 说明三个插值点位于同一条直线上，因此说明区间已经很小，插值点非常接近，故可将x2、y2输出作为最优解。,5.2 二次插值法,五、区间的缩短 为求得满足收敛精度要求

8、的最优点，往往需要多次进行插值计算，搜索区间不断缩短，使xp*不断逼近原函数的极小点x*。第一次区间缩短的方法是，计算xp*点的函数值fp*，比较fp*与f2，取其中较小者所对应的点作为新的x2，以此点的左右两邻点作为新的x1和x3，得到缩短后的新区间x1，x3，如图所示。,xP*,x2,f2,f3,x*,x1=a,x3=b,5.2 二次插值法,以后，根据fp*相对于x2的位置，并比较fp*与 f2，区间的缩短可以分为以下四种情况。,xP*,xP*,xP*,xP*,x2,x2,x2,x2,x3=b,x3=b,x1=a,x1=a,5.2 二次插值法,入口,xp*x2?,f2*fP*?,f2fP*

9、?,x1 xp*f1 fP*,x3 x2 f3 f2x2 xp*f2 fP*,x1 x2 f1 f2x2 xp*f2 fP*,x3 xp*f3 fP*,出口,Y,Y,N,N,a,b,c,d,Y,N,5.2 二次插值法,六、终止准则 当满足给定精度时，计算终止，并令 x*xP*(k),f*f(x*),5.3.1 单纯形算法概述,单纯形的定义是指设计空间 中有n+1个顶点的几何体。单纯形算法，是利用单纯形的顶点，计算其函数值，按一定的规则进行探测性搜索。如图5.3.1所示，通过对搜索区间单纯形顶点的函数值进行直接比较，可以判断目标函数的变化趋势，确定有利的搜索方向和步长。,5.3.3 单纯形算法步

10、骤一之初始化过程,L,H,R,H,S,F,S,G,5.3.3 单纯形算法步骤一之初始化过程,单纯形算法的核心是在选择新的较好的单纯形顶点的过程，包含有反射、扩展、压缩三种类形的过程。(二维空间为例)1）构造单纯形、计算函数值首先，在平面上去不共线的三点x1,x2和x3，计算各顶点的函数值,构造一个三角形HGL，即二维单纯形。（见图5.3.1）,5.3.3 单纯形算法步骤一之初始化过程,其中，令 H函数值 最大的点，为最差点；L函数值 最小的点，为最好点；G函数值 介于H和L之间的点。,5.3.3 单纯形算法步骤一之初始化过程,L,H,R,H,S,F,S,G,5.3.4 单纯形算法步骤二之反射过

11、程,函数值,说明最差点的反对称方向目标函数会有所改进，可以作为下一步的搜索方向。于是，将H点经过其余两点的中心，做出点的反对称点,即取 式中，a为反射系数，根据经验取a=1。,5.3.4 单纯形算法步骤二之反射过程,下一步，比较三个新顶点的函数值。若有,则用 XR代替XH,构成新的单纯形GRL。,5.3.5 单纯形算法步骤三之扩展过程,若,则说明原反射方向有利，可沿此方向扩展，取式中 为扩展系数，一般取 如果有,表明向前扩展有利，则以XE代替XH得到新的单纯形ELG；如果有，则说明扩展失败，取原来的单纯形RGL。,5.3.6 单纯形算法步骤四之压缩过程,若,则说明原反射方向走的太远，应该进行压

12、缩步骤，先取 其中 令 为压缩系数,一般取若,则用XS代替XH,形成新的单纯形SLG,5.3.6 单纯形算法步骤四之压缩过程,若,则进行收缩.最低点XL不动,其余两点向XL移动一半的距离.令以XL,XG,XH构成新的单纯形,传统最优化方法无约束最优化方法,概述基本方法 1.最优梯度法 2.共轭梯度法 3.牛顿法与阻尼牛顿法,梯度搜索,梯度与HESSE阵,称为f在点x处的梯度,最优梯度法,优化设计是追求目标函数值最小，因此，自然可以设想从某点出发，其搜索方向取该点的负梯度方向，使函数值在该点附近下降最快。这种方法也称为最优梯度法。一、基本原理梯度法的迭代公式为：x(k+1)=x(k)-(k)g(

13、k)其中g(k)是函数F(x)在迭代点x(k)处的梯度f(xk)，(k)一般采用一维搜索的最优步长，即 f(x(k+1)=f(x(k)-(k)g(k)=min f(x(k)-(k)g(k)=min()据一元函数极值条件和多元复合函数求导公式，得()=0 即得(k)的值,由()=-(f(x(k)-(k)g(k)T g(k)=0即（f(x(k+1)T g(k)=0或(g(k+1)Tg(k)=0,此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。,最优梯度法,二、迭代终止条件 采用

14、梯度准则：|g(k)|三、迭代步骤（1）任选初始迭代点x(0)，选收敛精度。（2）确定x(k)点的梯度（开始k=0)（3）判断是否满足终止条件|g(k)|？若满足输出最优解，结束计算。否则转下步。（4）从x(k)点出发，沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点 x(k+1)=x(k)-(k)g(k)，令k=k+1 返回步骤（2）。,最优梯度法,四、梯度法流程图,入口,给定：x(0)，,k=0,|g(k)|？,x*=x(k)f*=f(x(k),出口,x(k)=x(0,计算：g(k),k=k+1,沿g(k)方向一维搜索，求最优步长(k)。,N,Y,最优梯度法解下题：min f(x)

15、=2x12+x22 初点x(2)=(1,1)T,=1/10,先求出函数的梯度：g(k)=,4x1 2x2,第一次迭代:求出-g(1),并运算是否满足终止条件不满足终止条件后,沿-g(1)做一维搜索，求出(1)利用x()=x()-()g()，得-g()后跳到第一步,共轭梯度法,共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。一、共轭梯度法的搜索方向 共轭梯度法的搜索方向采用梯度法基础上的共轭方向，如图所示，目标函数F(x)在迭代点xk+1处的负梯度为-f(xk+1)，该方向与前一搜索方向Sk互为正交，在此基础上构造一种具有较高收

16、敛速度的算法，该算法的搜索方向要满足以下两个条件：（1）以xk+1点出发的搜索方向 Sk+1是-f(xk+1)与Sk的线性组合。即,xk,x*,xk+1,-f(xk+1),Sk+1,Sk,共轭梯度法,Sk+1=-f(xk+1)+kSk（2）以与为基底的子空间中，矢量与相共轭，即满足 Sk+1T G Sk=0二、k的确定 记住三、共轭梯度法的算法（1）选初始点x0和收敛精度。（2）令k=0，计算S0=-f(x0)。（3）沿Sk方向进行一维搜索求(k)，得 x(k+1)=x(k)+(k)S(k)（4）计算 f(xk+1)，若|f(xk+1)|，则终止迭代，取x*=xk+1；否则进行下一步。,共轭梯

17、度法,（5）检查搜索次数，若k=n，则令x0=xk+1，转（2），否则，进行下一步。（6）构造新的共轭方向 Sk+1=-f(xk+1)+kSk 令k=k+1，转（3）,共轭梯度法,四、共轭梯度法流程图,入口,k=0，计算：-f(x0),|f(xk+1)|？,出口,求(k)，x(k+1)=x(k)+(k)S(k),计算：f(xk+1),x*=xk+1f(x*)=f(xk+1),Y,N,给定：x(0)，,k n？,x0=xk+1,N,Y,Sk+1=-f(xk+1)+kSk,K=K+1,牛顿法,牛顿法是求无约束最优解的一种古典解析算法。牛顿法可以分为原始牛顿法和阻尼牛顿法两种。实际中应用较多的是阻尼

18、牛顿法。,原始牛顿法,一、原始牛顿法的基本思想 在第k次迭代的迭代点xk邻域内，用一个二次函数去近似代替原目标函数f(x)，然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点，依次类推，通过多次重复迭代，是迭代点逐步逼近原目标函数的极小点。如图所示。,F(x),1(x),0(x),x0,x1,x2,x*,原始牛顿法,二、原始牛顿法的迭代公式 设目标函数f(x)具有连续的一、二阶导数，在x(k)点邻域内取f(x)的二次泰勒多项式作近似式，即取逼近函数(x)为设xk+1为(x)极小点，根据极值的必要条件，应有(xk)=0，即 f(xk)+G(xk)x=0 又 x=xk+1-xk 得 xk

19、+1=xk-G(xk)-1 f(xk)即牛顿法迭代公式，方向-G(xk)-1 f(xk)称为牛顿方向,阻尼牛顿法,一、对原始牛顿法的改进 为解决原始牛顿法的不足，加入搜索步长(k)因此，迭代公式变为：xk+1=xk-(k)G(xk)-1 f(xk)二、阻尼牛顿法的迭代步骤（1）给定初始点和收敛精度（2）计算 f(xk),若 f(xk)满足收敛条件,则停止计算;否则,计算G(xk)=-2f(xk)-1 f(xk)（3）从x(k)出发,沿G(xk)做一维搜索,求步长(k),使它满足 f(x(k)+(k)d(k)=min f(x(k)+d(k)令 x(k+1)=x(k)+(k)d(k)。（4）检查收

20、敛精度，若|xk+1-xk|则x*=xk+1，停止，否则 k=k+1，返回（2）继续,阻尼牛顿法,三、阻尼牛顿法的特点 优点：由于阻尼牛顿法每次迭代都在牛顿方向进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有苛刻的要求。缺点：1、对目标函数要求苛刻，要求函数具有连续的一、二阶导数；为保证函数的稳定下降，海赛矩阵必须正定；为求逆阵要求海赛矩阵非奇异。2、计算复杂且计算量大，存储量大,取初始点:x(1)=(0,0)T.,min,函数的梯度和hessian矩阵分别为:,牛顿方向为:,从x(1)出发,沿d(1)作一维搜索.得,从x(1)出发,沿d(1)作一

21、维搜索.得,显然,用阻尼牛顿法不能产生新点.原因在于Hessian矩阵非正定.,变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由Davidon于1959年提出又经Fletcher和Powell加以发展和完善的一种变尺度法，故称为DFP变尺度法。拟牛顿法的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵.,DFP变尺度法,1、选定初始点和收敛精度 2、计算初始点处的梯度g1，选取初始对称正定矩阵H1=In。3、计算搜索方向Sk=-Hkgk 4、沿Sk方向一维搜索，求步长(k),使它满足 f(x(k)+(k)d(k)=min f

22、(x(k)+d(k)令 x(k+1)=x(k)+(k)d(k)。5、判断是否满足终止准则，若满足输出最优解，否则转6。6、当迭代n次还未找到极小点，重置Hk为单位矩阵，并以当前点为初始点返回2，否则转7。,DFP变尺度法的步骤,7、计算gk+1=,p(k)=xk+1 xk,q(k)=gk+1-gk.利用计算Hk+1置k=k+1,返回3.,DFP变尺度法的步骤,求 min取初始点及初始矩阵为且梯度为,DFP变尺度法例题,第1次迭代:从x(1)出发作一维搜索,得得x(2)=x(1)+(k)d(1)=,g2=,DFP变尺度法例题,第2次迭代:p(1)=(k)d(1)=q(1)=g2-g1=,利用公式可得H2=,DFP变尺度法例题,令 d(2)=-H2g2=从x(2)出发作一维搜索,得得得x(3)=x(2)+(2)d(2)=,g3=.得最优解为x(3),DFP变尺度法例题,