《搜索算法结构》PPT课件.ppt

上传人:牧羊曲112 文档编号:5516797 上传时间:2023-07-16 格式:PPT 页数:66 大小:1.15MB
返回 下载 相关 举报
《搜索算法结构》PPT课件.ppt_第1页
第1页 / 共66页
《搜索算法结构》PPT课件.ppt_第2页
第2页 / 共66页
《搜索算法结构》PPT课件.ppt_第3页
第3页 / 共66页
《搜索算法结构》PPT课件.ppt_第4页
第4页 / 共66页
《搜索算法结构》PPT课件.ppt_第5页
第5页 / 共66页
点击查看更多>>
资源描述

《《搜索算法结构》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《搜索算法结构》PPT课件.ppt(66页珍藏版)》请在三一办公上搜索。

1、3.1 搜索算法结构,一、下降算法模型 考虑(NP)常用一种线性搜索的方式来求解:迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。迭代计算:其中 为第 次迭代的搜索方向,为沿 搜索的最佳步长因子(通常也称作最佳步长)。,第三章 常用的一维搜索方法,可行方向:设 S,dRn,d0,若存在,使,称d 为 点的可行方向。同时满足上述两个性质的方向称下降可行方向。,下降方向:设 S,d Rn,d0,若存在,使,称d 为 在 点的下降方向。,模型算法,线性搜索求,新点使x(k+1)S,yes,no,5,3,1,二、收敛性概念:考虑(NP)设迭代算法产生点列x(k)S.1.理想的收敛性:设x*S

2、是g.opt(全局最优解).当x*x(k)或 x(k)x*,k,满足 时,称算法收敛到最优解 x*。,由于非线性规划问题的复杂性,实用中建立下列收敛性概念:2.实用收敛性:定义解集 S*=x|x 具有某种性质 例:S*=x|x-g.opt S*=x|x-l.opt S*=x|f(x)=0 S*=x|f(x)(为给定的实数阈值),2.实用收敛性(续)收敛性:设解集S*,x(k)为算法产生的点列。下列情况之一成立时,称算法收敛:1x(k)S*;2x(k)S*,k,x(k)的任意极限点x*S*。全局收敛:对任意初始点x(1),算法均收敛。局部收敛:当x(1)充分接近解x*时,算法收敛。,有限步终止,

3、三、收敛速度 设算法产生点列x(k)收敛到解x*,且x(k)x*,k,关于算法的收敛速度,有1.线性收敛:当k充分大时成立。2.超线性收敛:3.二阶收敛:0,是 使当k充分大时有,三、收敛速度(续)定理:设算法点列x(k)超线性收敛于x*,且x(k)x*,k,那么证明:只需注意|x(k+1)x*|-|x(k)x*|x(k+1)x(k)|x(k+1)x*|+|x(k)x*|,除以|x(k)x*|并令k,利用超线性收敛定义可得结果。,该结论导出算法的停止条件可用:,四、二次终结性一个算法用于解正定二次函数的无约束极小时,有限步迭代可达最优解,则称该算法具有二次终结性。,问题描述:,已知,并且求出了

4、,处的可行下降方向,从,出发,,沿方向,求如下目标函数的最优解,,或者选取,使得:,常用的一维搜索算法,设其最优解为,(叫精确步长因子),,所以线性搜索是求解一元函数,的最优化问,题(也叫一维最优化问题或,一般地,一维优化问题可描述为:,于是得到一个新点:,一维搜索)。,或解,一般地,线性搜索算法分成两个阶段:,第一阶段确定包含理想的步长因子,(或问题最优解)的搜索区间;,第二阶段采用某种分割技术或插值,方法缩小这个区间。,搜索区间的确定 黄金分割法(0.618法)二次插值法 Newton法,要点:单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、

5、Newton法基本思想、方法比较。,我们主要介绍如下一些搜索方法:,学习的重要性:,1、工程实践中有时需要直接使用;,2、多变量最优化的基础,迭代中经常要用到。,方法分类:,1、直接法:迭代过程中只需要计算函数值;,2、微分法:迭代过程中还需要计算目标函数的导数;,3.2 搜索区间的确定,常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发,利用单峰函数的消去性质,逐步缩小搜索区间,直到满足精度要求为止。,3.2.1 单峰函数,连续单峰函数,不连续单峰函数,离散单峰函数,非单峰函数,定义:如果函数f(x)在区间a,b上只有一个极值点,则称f(x)为 a,b上的单峰函数。,单峰函

6、数具有一个重要的消去性质,定理:设f(x)是区间a,b上的一个单峰函数,x*a,b是其极小点,x1 和x2是a,b上的任意两点,且ax1 x2b,那么比较f(x1)与f(x2)的值后,可得出如下结论:,(I)消去a,x1,(II)消去x2,b,(II)若f(x1)f(x2),x*a,x2,在单峰函数的区间内,计算两个点的函数值,比较大小后,就能把搜索区间缩小。在已缩小的区间内,仍含有一个函数值,若再计算另一点的函数值,比较后就可进一步缩小搜索区间.,(I)若f(x1)f(x2),x*x1,b,3.2.2 进退算法(或称成功-失败法),如何确定包含极小点在内的初始区间?,(一)基本思想:,由单峰

7、函数的性质可知,函数值在极小点左边严格下降,在右边严格上升。,从某个初始点出发,沿函数值下降的方向前进,直至发现函数值上升为止。由两边高,中间低的三点,可确定极小点所在的初始区间。,(二)算法,1、选定初始点a 和步长h;,2、计算并比较f(a)和f(a+h);有前进(1)和后退(2)两种情况:,则步长加倍,计算f(a+3h)。若f(a+h)f(a+3h),令 a1=a,a2=a+3h,停止运算;否则将步长加倍,并重复上述运算。,则将步长改为h。计算f(ah),若f(ah)f(a),令 a1=ah,a2=a+h,停止运算;否则将步长加倍,继续后退。,仅仅找区间!若进一步找最小点,参阅P44!,

8、(三)几点说明缺点:效率低;优点:可以求搜索区间;注意:h 选择要适当,初始步长不能选得太小;,3.3 区间消去法黄金分割法,消去法的思想:反复使用单峰函数的消去性质,不断缩小包含极小点的搜索区间,直到满足精度为止。,消去法的优点:只需计算函数值,通用性强。,消去法的设计原则:(1)迭代公式简单;(2)消去效率高;(3)对称:x1 a=b-x2;(4)保持缩减比:=(保留的区间长度原区间长度)不变。(使每次保留下来的节点,x1或 x2,在下一次的比较中成为一个相应比例位置的节点)。,(一)黄金分割,取“”,=0.618,(二)黄金分割法的基本思想,黄金分割重要的消去性质:,设x1,x2 为a,

9、b 中对称的两个黄金分割点,,x1为a,x2的黄金分割点,x2为x1,b的黄金分割点,在进行区间消去时,不管是消去a,x1,还是消去x2,b,留下来的区间中还含一个黄金分割点,只要在对称位置找另一个黄金分割点,又可以进行下一次区间消去。,每次消去后,新区间的长度是原区间的0.618倍,经过n次消去后,保留下来的区间长度为0.618nL,需计算函数值的次数仅为n+1。,黄金分割比 0.618,所以此法也称为0.618法。,(三)算法,开始,x*a,x2,x*x1,b,!在迭代过程中,四个点的顺序始终应该是 ax1 x2 b,但在计算第二个分割点时使用x1=a+bx2 或 x2=a+b x1,由于

10、舍入误差的影响,可能破坏ax1 x2 b这一顺序,导致混乱。迭代中必须采取一些措施:,(1)终止限不要取得太小;,(2)使用双精度运算;,(3)经过若干次运算后,转到算法中的第3步,重新开始。,(四)黄金分割法的优缺点,2、缺点:对解析性能好的单峰函数,与后面要介绍的二次插值法、三次 插值法及牛顿拉夫森法等比较,计算量较大,收敛要慢。,1、优点:算法简单,效率高,只计算函数值,对函数要求低,稳定性好,对多峰函数或强扭曲的,甚至不连续的,都有效;,例3-2对函数,当给定搜索区间 时,试用黄金分割法求极小点。,f(x)=x2,a=-1.5,b=1;精度10-5,a x1 x2 b-3.6034e-

11、005 2.9804e-006 2.7093e-005 6.6107e-00522 0.618034 0.618034(x1-a)/(x2-a)(b-x2)/(b-x1)-3.6034e-005-1.1922e-005 2.9804e-006 2.7093e-00523 0.618034 0.618034-1.1922e-005 2.9804e-006 1.219e-005 2.7093e-00524 0.618035 0.618035-1.1922e-005-2.7117e-006 2.9804e-006 1.219e-00525 0.618032 0.618032-1.1922e-005-

12、6.2296e-006-2.7117e-006 2.9804e-00626 0.618038 0.618038x*=-2.7117e-006,若用0.618效果较差,0.61803,f(x)=x2,a=-1.5,b=1;精度10-10,a x1 x2 b-2.1976e-007-9.7339e-008-2.4483e-008 9.7933e-00834 0.626902 0.626902-9.7339e-008-2.4483e-008 2.5078e-008 9.7933e-00835 0.595145 0.595145-9.7339e-008-4.7778e-008-2.4483e-008

13、2.5078e-00836 0.680264 0.680264-4.7778e-008-2.4483e-008 1.7832e-009 2.5078e-00837 0.470017 0.470017-2.4483e-008 1.7832e-009-1.1888e-009 2.5078e-00838 1.12758 1.12758(x1-a)/(x2-a)(b-x2)/(b-x1)1.7832e-009-1.1888e-009 2.805e-008 2.5078e-00839-0.113146-0.1131461.7832e-009 3.1022e-008-1.1888e-009 2.805e-

14、008-9.83816-9.83816x*=-1.1888e-009(不满足精度),若用0.618效果更差,f(x)=x2,a=-1.5,b=1;精度10-10重新开始,a x1 x2 b-7.8811e-010 1.9703e-010 8.0587e-010 1.791e-00944 0.618034 0.618034(x1-a)/(x2-a)(b-x2)/(b-x1)-7.8811e-010-1.7926e-010 1.9703e-010 8.0587e-01045 0.618034 0.618034-7.8811e-010-4.1182e-010-1.7926e-010 1.9703e-

15、01046 0.618034 0.618034-4.1182e-010-1.7926e-010-3.5532e-011 1.9703e-01047 0.618034 0.618034-1.7926e-010-3.5532e-011 5.3298e-011 1.9703e-01048 0.618034 0.618034-1.7926e-010-9.0432e-011-3.5532e-011 5.3298e-01149 0.618034 0.618034-9.0432e-011-3.5532e-011-1.6019e-012 5.3298e-01150 0.618034 0.618034x*=-1

16、.6019e-012(满足要求),设 f(x)在 a,b上可微,且当导数为零时是解。取 x=(a+b)/2,那么 f(x)=0 时,x 为最小点,x=x*;f(x)0 时,x 在上升段,x*x,去掉a,x.(自己画算法框图),3.4 二分法,a,b缩小,当区间a,b的长度充分小时,或者当 充分小时,即可将a,b的中点取做极小点的近似点,这时有估计:,我们知道,在极小点,处,,,且,时,,递减,即,,而当,,函数递增,即,若找到一个区间a,b,满足性质,。,,则,a,b内必有,的极小点,,且,,为找此,,,取,,若,,,则在,中有极小点,这时,用,作为新的区间a,b,继续这个过程,逐步将区间,假

17、设 f(x)是具有极小点的单峰函数,,则必存在区间a,b,使f(a)0。,由f(x)的连续性可知,必有x*(a,b),使f(x)=0,优点:计算量较少,总能找到最优点,缺点:要计算导数值,收敛速度较慢,收敛速度为一阶,其中区间a,b的确定,一般可采用“进退法”。,3.5 多项式近似法二次插值法,(一)基本思想,对形式复杂的函数,数学运算时不方便,复杂函数 f(x),极小点x*,函数近似,最优点也应近似,一次多项式二次多项式三次多项式,?如何构造符合要求的多项式?,(二)二次插值多项式近似法(抛物线法)的基本原理,设目标函数 f(x)在三点x1 x2 x3 上的函数值分别为f 1,f2,f3,相

18、应的二次插值多项式为 P2(x)=a0a1x+a2x2,令P2(x)和f(x)在三点上的函数值相等,三个待定系数,P2(x)的平稳点是 P2(x)a1+2a2x=0 的解,(二)二次插值多项式近似法(抛物线法)的基本原理,设目标函数 f(x)在三点x1 x2 x3 上的函数值分别为f 1,f2,f3,相应的二次插值多项式为 P2(x)=a0a1x+a2x2,三个待定系数,P2(x)的平稳点是 P2(x)a1+2a2x=0 的解,简化计算,其他插值公式参阅P51-52(2)-(4)!三点二次插值公式最常用.,!迭代过程要点!,若任意取x1 x2 x3 三个点,,则求出的x*可能位于给定区间之外或

19、误差太大,最初的三个点x1 x2 x3 应构成一个两边高,中间低的“极小化框架”,即满足f1f2,f3f2,且两个等号不同时成立,极小化框架可由进退算法求得,在完成一次计算后,得到近似x*,,要进行搜索区间的收缩,然后在新区间中重新构造三点组成的“极小化框架”,有两种方法,终止准则:采用目标函数值的相对误差或绝对误差来判断,前进成功,极小化框架 x1 x2 x3,前进失败,x1,x2,极小化框架 x3 x2 x1,后退,h0,2h0,4h0,h0,h0,2h0,4h0,(三)进退算法(用于求“极小化框架”或初始搜索区间),(四)逐次二次插值近似法的算法,初始点x1,h0,精度1,溢出下限2,步

20、长缩短率m,二次插值法的优点:收敛速度较快,约为1.32阶,缺点:对强扭曲或多峰的,收敛慢,甚至会失败,故要求函数具有较好 的解析性能,(五)二次插值法与黄金分割法的结合,2)用二次插值法逼近极小点相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式:,xp*0.555,fp=0.292,例 3-3用二次插值法求函数f(x)=3x3-4x+2的极小点,给定 x0=0,h=1,=0.2。,解 1)确定初始区间初始区间a,b=0,2,另有一中间点x2=1。,在新区间,相邻三点的函数值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.x

21、p*0.607,fp=0.243由于fpx2,新区间a,b=x2,b=0.555,1|x2-xp*|=|0.555-0.607|=0.0520.2,迭代终止。xp*0.607,f*=0.243,由于fp0.2,应继续迭代。,此例黄金分割法需要5次收缩区间,例,例 3-4用二次插值法求 的极值点。初始搜索区间,。,图,解:取x2点为区间x1,x3的中点,,计算x1,x2,x3 3点处的函数值f1=19,f2=-96.9375,f3=124。可见函数值满足“高低高”形态。以x1,x2,x3为插值点构造二次曲线,求第一次近似的二次曲线p(x)的极小值点,由公式得。,比较函数值可知这种情况应消去左边区

22、段.然后用 作为x1,x2,x3新3点,重新构造二次曲线p(x),如此反复计算,直到 为止。整个迭代过程的计算结果列于表2-2.从表中可见,经7次迭代后,终止迭代。故最优点,0.618法,11次迭代,x*=3.9968;f*=-155.9996高精度时差异更大!,要求计算导数的插值法,若目标函数f(x)可导,可通过解f(x)0求平稳点,进而求出极值点。对高度非线性函数,要用逐次逼近求平稳点。,一、Newton法,要求目标函数f(x)在搜索区间内具有二阶连续导数,且已知f(x)和f(x)的表达式。,(一)基本思想,采用迭代法求(x)=0的根,xk+1,xk+2,(xk)=(xk)/(xk1xk)

23、,xk+1=xk(xk)/(xk),用于求(x)f(x)0的根,xK+1=xkf(xk)/f”(xk),0,一点二次插值-切线法,牛顿法程序流程:,例题 用Newton法求解 初始点取 x0=1。(迭代三次),解:f(x)的一阶和二阶导函数为,迭代公式为 xK+1=xkf(xk)/f”(xk),第一次迭代:x0=1,f(x0)12,f”(x0)36 x11(12)/361.33,第二次迭代:x1=1.33,f(x1)3.73,f”(x1)17.6 x21.33(3.73)/17.61.54,(本例精确解为 x*),第三次迭代:x2=1.54,f(x2)0.5865,f”(x2)12.76 x3

24、1.54(0.587)/12.761.586 f(x2)=15.1191,0.618法1,2上11次 x*=1.5795,f*=15.1194,例1:求 min f(x)=arctan t d t 解:f(x)=arctan x,f(x)=1(1+x2)迭代公式:xk+1=xk-(1+xk 2)arctan xk 取 x0=1,计算结果:k xk f(xk)1f(xk)1 1 0.7854 2 2-0.5708-0.5187 1.3258 3 0.1169-0.1164 1.0137 4-0.001095-0.001095 5 7.9631e-010 x4 x*=0 取 x0=2,计算结果如下

25、:2-3.535713.9510-279.3441 1.2202e+005 不收敛!,线性收敛,二次收敛,Ex1:,Ex2:,(二)优缺点,1、优点:收敛速度快;在f(x)=0的单根处,是2阶收敛;在f(x)=0的重根 处,是线性收敛。例,2、缺点:需要求二阶导数,若用数值导数代替,由于舍入误差将影响收敛 速度;收敛性还依赖于初始点及函数性质。,!通常在计算程序中规定最大迭代次数,当次数达到K还不能满足精度时,则认为不收敛,要换一个初始点。,二、二点二次插值,x*,1)割线法基本思想:用割线代替Newton法中的切线,并与区间消去法相结合。,c,P52(3-14),P51(3-12),2)另一

26、个二点二次插值(f(a)f(b)f(b)较割线法稍好,收敛速度都为1.618阶,通过检查区间两端导数来收缩区间新区间两端点的导数值异号,基本思想与二次插值法类似:用四个已知值(如两个点函数值及其导数值)构造一个三次多项式P3(x),用P3(x)的极小点近似目标函数的极小点x*,利用函数在两点的函数值和导数值:,三、三次插值,三次插值法的收敛速度比二次插值法要快,达到2阶收敛速度。,求出:,极值的条件:,极值充分条件为:,将极值点方程带入上式,仅取正号,两种情形(A=0/A0)统一为:,其它形式,二点三次插值法一般流程:,编写程序应用时建议结合教材p55框图编写(嵌入进退法),其更具普适性、鲁棒

27、性。,教材P56-58的 D.S.C.法、Powell法及其组合法是区间搜索与二次插值法的结合!,P59-P64介绍了有理插值、连分式方法属特殊方法,含教材作者的一些研究成果,大家参阅教材,注意其适应条件,必要时课选用.,方法综述,(1)如目标函数能求二阶导数:用Newton法 收敛快,(2)如目标函数能求一阶导数:首先考虑用三次插值法,收敛较快 对分法、收敛速度慢,但可靠 二次插值如割线法也可选择.,(3)只需计算函数值的方法:首先考虑用二次插值法,收敛快 黄金分割法收敛速度较慢,但可靠,作业,一、用黄金分割法求函数f(x)=3x4-4x2+2的极小点,给定 x0=-2,h=1,=0.1(x

28、0=2,h=1,=0.1)。二、ch3 3.1 3.7-9参考课件见http:/-课程教学,解:1)确定初始区间x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1,f2=f(x2)=1由于f1f2,应加大步长继续向前探测。,x3=x0+2h=0+2=2,f3=f(x3)=18由于f2f3,可知初始区间已经找到,即a,b=x1,x2=0,2,2)用黄金分割法缩小区间 第一次缩小区间:x1=0+0.382X(2-0)=0.764,f1=0.282 x2=0+0.618 X(2-0)=1.236,f2=2.72 f10.2,例 3-1用黄金分割法求函数f(x)=3x3-4x+2的极小点,

29、给定 x0=0,h=1,=0.2。,第三次缩小区间:令 x1=x2=0.764,f1=f2=0.282x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f10.2,应继续缩小区间。,第二次缩小区间:令 x2=x1=0.764,f2=f1=0.282x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1f2,故新区间a,b=x1,b=0.472,1.236因为 b-a=1.236-0.472=0.7640.2,应继续缩小区间。,第四次缩小区间:令 x2=x1=0.764,f2=f1=0.282x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f10.2,应继续缩小区间。,第五次缩小区间:令 x2=x1=0.652,f2=f1=0.223x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1f2,故新区间a,b=x1,b=0.584,0.764因为 b-a=0.764-0.584=0.180.2,停止迭代。,极小点与极小值:x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222,返回,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号