智能理论与技术

1、智能理论与技术智能理论与技术杨启文杨启文 薛云灿薛云灿课程纲要l传统最优化技术传统最优化技术无约束最优化方法（无约束最优化方法（9 9学时）学时）有约束最优化方法（自学，有约束最优化方法（自学，3 3学时）学时）l智能优化计算智能优化计算进化计算进化计算（1515学时）学时）模糊逻辑模糊逻辑（9 9学时）学时）人工神经网络人工神经网络（1818学时）学时）最优化技术的重要性2优化问题求 的极小值 |34|)(2xxxf034)(2xxxf1求解问题求 的根 132xf(x)132xf(x)一个求解可以问题转变为一个优化问题传统最优化方法优化模型的一般形式优化模型的一般形式lopt. f ( x

2、i, yj, k )ls.t. gh ( xi, yj, k ) , 0l h = 1,2, ,ml其中：其中： xi 为决策变量（可控制）为决策变量（可控制） yj 为已知参数为已知参数 k 为随机因素为随机因素 f 为目标函数为目标函数 gh 为约束条件为约束条件传统最优化方法无约束最优化方法无约束最优化方法非梯度搜索非梯度搜索l概述概述x2x1o (k)s(k)s(k)x(k+1)x(k)x*f(x(k)f(x(k+1)x(k+1)=x(k)+ (k)s(k)迭代公式迭代公式在优化设计的在优化设计的迭代运算中，迭代运算中，在搜索方向在搜索方向s(k)上寻求最优步上寻求最优步长长 (k)

3、的方法的方法称一维搜索法。称一维搜索法。传统最优化方法无约束最优化方法无约束最优化方法直接搜索直接搜索l概述概述l基本方法基本方法1、黄金分割法（、黄金分割法（0.618法）法）2、二次插值法（抛物线法）、二次插值法（抛物线法）3、单纯形算法、单纯形算法5.1 黄金分割法 黄金分割法适用于黄金分割法适用于a,b区间上的任何单峰函数区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。甚至可以不连续。因此，这种方法的适应面相当广。一、黄金分割法的原理一、黄金分割法的原理 在搜索区间在搜索区间a

4、,b内适当插入两点内适当插入两点x1,x2 ，并计，并计算其函数值。算其函数值。 x1,x2 将区间分为三段，通过比较函数将区间分为三段，通过比较函数值的大小，删除其中的一段，使搜索区间缩短。然值的大小，删除其中的一段，使搜索区间缩短。然后再在保留下来的区间上作同样处理，如此迭代下后再在保留下来的区间上作同样处理，如此迭代下去，使搜索区间无限缩小，从而得到极小点的近似去，使搜索区间无限缩小，从而得到极小点的近似值。值。5.1 黄金分割法（图5.1.1）5.1 黄金分割法l 插入点插入点x1,x2的位置相对于区间的位置相对于区间a,b两端两端点有对称性要求，点有对称性要求，除对称性要求外，还要求

5、除对称性要求外，还要求每次迭代区间长度缩短的比率是相同的。设每次迭代区间长度缩短的比率是相同的。设原区间长度为原区间长度为l如图所示，保留区间长度为如图所示，保留区间长度为l ，区间缩短率为区间缩短率为 。进行第二次缩短时，新点。进行第二次缩短时，新点为为x3 ,设设y1f(x3)则新区间为则新区间为a,x1为保持相同为保持相同的区间缩短率，的区间缩短率，5.1 黄金分割法（图5.1.1）5.1 黄金分割法 应有（应有（1- ）/ = 故：故：1- = 2 2 + -1=0由此可得：由此可得： =0.618黄金分割法可使相邻两次搜索区间都具有黄金分割法可使相邻两次搜索区间都具有相同的缩短率相同

6、的缩短率0.618。x1=a+ 0.382(b-a)x2=a+ 0.618(b-a)b-x2=x1-ax2-x1= (b-a)列题：min f(x)=2x2-x-1 初始区间a1,b1=-1,1,精度l 0.16kakbk kukf( k)f( uk)1-11-0.236 0.236-0.653 -1.1252 -0.23610.2360.528-1.125 -0.9703 -0.236 0.5280.0560.236-1.050 -1.1254 0.0560.5280.2360.348-1.125 -1.1065 0.0560.3480.1680.236-1.112-1.1256 0.168

7、0.3480.2360.279-1.125 -1.1237 0.1680.2795.1 黄金分割法l二、黄金分割法的搜索过程二、黄金分割法的搜索过程 1、给出初始搜索区间、给出初始搜索区间a,b及收敛精度及收敛精度 。 2、按坐标点计算公式计算，并计算相应的、按坐标点计算公式计算，并计算相应的函数值函数值,取出较大点取出较大点 3、用这个较大点做为区间的一端、用这个较大点做为区间的一端,另一端不另一端不变来缩短搜索区间变来缩短搜索区间 4、检查是否满足收敛条件、检查是否满足收敛条件 5、若满足收敛条件，则取最后两点的平均、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。值作为极小点的近

8、似解。5.2 二次插值法一、插值法概念一、插值法概念 假定我们给定的问题是在某一确定区间假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置，但是没有函数表内寻求函数的极小点的位置，但是没有函数表达式，只有若干试验点处的函数值。我们可以达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作近的低次插值多项式，用该多项式的最优解作为原函数最优解的近似解，这种方法是用低次为原函数最优解的近似解，这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近插值多项式逐步逼近原目标函数的极小点的

9、近似求解方法，称为插值方法或函数逼近法。似求解方法，称为插值方法或函数逼近法。5.2 二次插值法二、插值法与试探法的异同点二、插值法与试探法的异同点 相同点：相同点：都是利用区间消去法原理都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小将初始搜索区间不断缩短，从而求得极小点的数值近似解。点的数值近似解。5.2 二次插值法不同点：不同点：试验点位置的确定方法不同。在试探法试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的，中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。例如：黄金分割法是并未考虑函数值的分布。例如：黄金分割法是按照等比例按照等比例0.

10、618缩短率确定的。而在插值法中，缩短率确定的。而在插值法中，试验点的位置是按函数值近似分布的极小点确试验点的位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值进行大定的。试探法仅仅利用了试验点函数值进行大小的比较，而插值法还要利用函数值本身或其小的比较，而插值法还要利用函数值本身或其导数信息。所以，当函数具有较好的解析性质导数信息。所以，当函数具有较好的解析性质时，插值方法比试探方法效果更好。时，插值方法比试探方法效果更好。5.2 二次插值法三、二次插值法的概念三、二次插值法的概念 利用原目标函数上的三个插值点，利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式

11、的构成一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步最优解作为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值逼近原目标函数的极小点，称为二次插值方法或抛物线法。方法或抛物线法。p1p(x)p3f(x)f1x1=ap2f2x2x*xp*f3x3=b5.2 二次插值法 四、二次插值函数的构成四、二次插值函数的构成 过函数曲线上的三点过函数曲线上的三点p1(x1 , f 1)、 p2(x2 , f 2)、 p3(x3 , f 3) 作作二次插值多项式二次插值多项式 p(x)=ax2+bx+c 它应满足条件它应满足条件 p(x1)=ax12+bx1+c 1=f 1

12、 p(x2)=ax22+bx2+c = f 2 p(x3)=ax32+bx3+c = f 3 5.2 二次插值法l解方程组，得待定系数解方程组，得待定系数a、b、c分别分别为为)()()()()(133221321213132xxxxxxfxxfxxfxxa)()()()()(133221322212212312322xxxxxxfxxfxxfxxb)()()()()(133221321122313113223xxxxxxfxxxxfxxxxfxxxxc5.2 二次插值法 令插值函数令插值函数p(x)的一阶导数为的一阶导数为0，即，即 p (x)=2ax+b=0 得得p(x)极小点为极小点为

13、xp* = b / 2 a 代入代入a、b得得321213132322212212312322*)()()()()()(21fxxfxxfxxfxxfxxfxxxp5.2 二次插值法l令l则13131xxffc32112122)/()(xxcxxffc)2131(21*ccxxxp5.2 二次插值法若若c2=0， 则则 即即 说明三个插值点位于同一条直线上，因此说说明三个插值点位于同一条直线上，因此说明区间已经很小，插值点非常接近，故可将明区间已经很小，插值点非常接近，故可将x2、y2输出作为最优解。输出作为最优解。0)/()(32112122xxcxxffc131311212xxffcxxf

14、f5.2 二次插值法 五、区间的缩短五、区间的缩短 为求得满足收敛精度要求的最优点，往为求得满足收敛精度要求的最优点，往往需要多次进行插值计算，搜索区间不断缩往需要多次进行插值计算，搜索区间不断缩短，使短，使xp*不断逼近原函数的极小点不断逼近原函数的极小点x*。 第一次区间缩短的方法是，计算第一次区间缩短的方法是，计算xp*点的点的函数值函数值fp*，比较，比较fp*与与f2，取其中较小者所对应，取其中较小者所对应的点作为新的的点作为新的x2，以此点的左右两邻点作为，以此点的左右两邻点作为新的新的x1和和x3，得到缩短后的新区间，得到缩短后的新区间x1，x3，如图所示。如图所示。xp*x2f

15、2f3x*x1=ax3=b5.2 二次插值法l以后，根据以后，根据fp*相对于相对于x2的位置，并比较的位置，并比较fp*与与 f2 ，区间的缩短可以分为以下四种情况。区间的缩短可以分为以下四种情况。xp*xp*xp*xp*x2x2x2x2x3=bx3=bx1=ax1=a5.2 二次插值法入口入口xp*x2?f2*fp*?f2fh?xs=xf-b(xf-xh), fsfsfh?单纯形为hflsglfrfg?xs=xf+b(xf-xh) sglfrfl?rglxe=xf+a(xf-xh), fefefr?glerglnnnnyyyyyn图5.3.2 单纯形算法框图传统最优化方法无约束最优化方法无

16、约束最优化方法l概述概述l基本方法基本方法l 1. 最优梯度法最优梯度法l 2. 共轭梯度法共轭梯度法l 3. 牛顿法与阻尼牛顿法牛顿法与阻尼牛顿法 梯度搜索梯度搜索梯度与hesse阵称为f在点x处的梯度最优梯度法 优化设计是追求目标函数值最小，因此，自然可以设优化设计是追求目标函数值最小，因此，自然可以设想从某点出发，其搜索方向取该点的负梯度方向，使函数值想从某点出发，其搜索方向取该点的负梯度方向，使函数值在该点附近下降最快。这种方法也称为最优梯度法。在该点附近下降最快。这种方法也称为最优梯度法。一、基本原理一、基本原理梯度法的迭代公式为：梯度法的迭代公式为： x(k+1)=x(k)- (k

17、)g(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 此式表明，相邻的此式表明，相邻的两个迭代点的梯度是

18、彼两个迭代点的梯度是彼此正交的。也即在梯度此正交的。也即在梯度的迭代过程中，相邻的的迭代过程中，相邻的搜索方向相互垂直。梯搜索方向相互垂直。梯度法向极小点的逼近路度法向极小点的逼近路径是锯齿形路线，越接径是锯齿形路线，越接近极小点，锯齿越细，近极小点，锯齿越细，前进速度越慢。前进速度越慢。最优梯度法二、迭代终止条件二、迭代终止条件 采用梯度准则：采用梯度准则： | g(k) | 三、迭代步骤三、迭代步骤（1）任选初始迭代点）任选初始迭代点x(0)，选收敛精度，选收敛精度 。（2）确定）确定x(k)点的梯度（开始点的梯度（开始k=0)（3）判断是否满足终止条件）判断是否满足终止条件| g(k)

19、| ？若满足输出若满足输出最优解，结束计算。否则转下步。最优解，结束计算。否则转下步。（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)。nyl最优梯度法解下题： mi

20、n f(x)=2x12+x22 初点x(2) =(1,1)t , =1/10l先求出函数的梯度：g(k) =4x1 2x2l第一次迭代:求出-g(1),并运算是否满足终止条件l不满足终止条件后,沿-g(1)做一维搜索，求出 (1)l利用x()=x()- ()g()，得-g()后跳到第一步 共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。称作共轭梯度法。一、共轭梯度法的搜索方向一、共轭梯度法的搜索方向 共轭梯度法的搜索方向采用梯度

21、法基础上的共轭共轭梯度法的搜索方向采用梯度法基础上的共轭方向，如图所示，目标函数方向，如图所示，目标函数f(x)在迭代点在迭代点xk+1处的处的负梯度为负梯度为- f(xk+1)，该方向与前，该方向与前一搜索方向一搜索方向sk互为正交，在此互为正交，在此基础上构造一种具有较高收敛基础上构造一种具有较高收敛速度的算法，该算法的搜索方速度的算法，该算法的搜索方向要满足以下两个条件：向要满足以下两个条件： （1）以）以xk+1点出发的搜索方点出发的搜索方向向 sk+1是是- f(xk+1)与与sk的线性的线性组合。即组合。即xkx*xk+1- f(xk+1)sk+1sk sk+1 = - f(xk+

22、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；否则进行下一步。；否则进行下一步。21)()

23、(kkkxfxf （5）检查搜索次数，若）检查搜索次数，若k=n，则令，则令x0=xk+1，转（，转（2），），否则，进行下一步。否则，进行下一步。 （6）构造新的共轭方向）构造新的共轭方向 sk+1 = - f(xk+1) + ksk 令令k=k+1，转（，转（3）21)()(kkkxfxf四、共轭梯度法流程图四、共轭梯度法流程图入口入口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)yn给定：给定： x(0)， k n ？x0=xk+1nysk

24、+1 = - f(xk+1) + kskk=k+1 牛顿法是求无约束最优解的牛顿法是求无约束最优解的一种古典解析算法。牛顿法可以一种古典解析算法。牛顿法可以分为原始牛顿法和阻尼牛顿法两分为原始牛顿法和阻尼牛顿法两种。实际中应用较多的是阻尼牛种。实际中应用较多的是阻尼牛顿法。顿法。一、原始牛顿法的基本思想一、原始牛顿法的基本思想 在第在第k次迭代的迭代点次迭代的迭代点xk邻域内，用一个二次函邻域内，用一个二次函数去近似代替原目标函数数去近似代替原目标函数f(x)，然后求出该二次函数，然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点，依的极小点作为对原目标函数求优的下一个迭代点，依次类

25、推，通过多次重复迭代，是迭代点逐步逼近原目次类推，通过多次重复迭代，是迭代点逐步逼近原目标函数的极小点。标函数的极小点。如图所示。如图所示。f(x) 1(x) 0(x)x0 x1x2x*二、原始牛顿法的迭代公式二、原始牛顿法的迭代公式 设目标函数设目标函数f(x)具有连续的一、二阶导数，具有连续的一、二阶导数，在在x(k)点邻域内取点邻域内取f(x)的二次泰勒多项式作近似式，的二次泰勒多项式作近似式，即即取逼近函数取逼近函数 (x)为为设设xk+1为为 (x)极小点，根据极值的必要条件，应极小点，根据极值的必要条件，应有有 (xk)=0，即，即 f(xk)+ g(xk) x=0 又又 x= x

26、k+1 - xk 得得 xk+1 = xk- g(xk)-1 f(xk) 即牛顿法迭代公式，方向即牛顿法迭代公式，方向- g(xk)-1 f(xk)称为称为牛顿方向牛顿方向xxgxxxfxfxfkttkk)(21)()()(xxgxxxfxfxkttkk)(21)()()(一、对原始牛顿法的改进一、对原始牛顿法的改进 为解决原始牛顿法的不足，加入搜索步长为解决原始牛顿法的不足，加入搜索步长 (k)因此，因此，迭代公式变为：迭代公式变为： xk+1 = xk - (k)g(xk)-1 f(xk) 二、阻尼牛顿法的迭代步骤二、阻尼牛顿法的迭代步骤 （1）给定初始点和收敛精度）给定初始点和收敛精度

27、（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）检查收敛精度，若）检查收敛精度，若| xk+1- xk |则则x*=xk+1，停止，否则，停止，否则 k=k+1，返回（，返回（2）继续）继续三、阻尼牛顿法的特点三、阻尼牛顿法的特点 优点：优点：由于阻尼

28、牛顿法每次迭代都在牛顿方由于阻尼牛顿法每次迭代都在牛顿方向进行一维搜索，避免了迭代后函数值上升的现向进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有苛刻的要求。点的选择没有苛刻的要求。 缺点：缺点： 1、对目标函数要求苛刻，要求函数具有、对目标函数要求苛刻，要求函数具有连续的一、二阶导数；为保证函数的稳定下降，连续的一、二阶导数；为保证函数的稳定下降，海赛矩阵必须正定；为求逆阵要求海赛矩阵非奇海赛矩阵必须正定；为求逆阵要求海赛矩阵非奇异。异。 2、计算复杂且计算量大，存储量大、计算复杂且计算量大，存储量大222141)1 ()(xxxxxf20)() 1 (xf20)() 1 (xf牛顿方向为:02)()()1(1)1(2)1(xfxfd从x(1)出发,沿d(1)作一维搜索.得116)()(4) 1 () 1 (dxf从x(1)出发,沿d(1)作一维搜索.得116)()(4)1()1(dxf0064)( 13显然,用阻尼牛顿法不能产生新点.原因在于hessian矩阵非正定. 变尺度法也称拟牛顿法，它是基于牛顿法的思想变尺度法也称拟牛顿法，它是基于牛顿法的思想而