搜索算法结构教学课件市公开课一等奖百校联赛特等奖课件.pptx
《搜索算法结构教学课件市公开课一等奖百校联赛特等奖课件.pptx》由会员分享,可在线阅读,更多相关《搜索算法结构教学课件市公开课一等奖百校联赛特等奖课件.pptx(66页珍藏版)》请在咨信网上搜索。
1、3.1 3.1 3.1 3.1 搜索算法结构搜索算法结构搜索算法结构搜索算法结构一、下降算法模型一、下降算法模型 考虑(考虑(NP)惯用一个线性搜索方式来求解:迭代中从一惯用一个线性搜索方式来求解:迭代中从一点出发沿点出发沿下降可行方向下降可行方向找一个新、性质有找一个新、性质有改进点。改进点。迭代计算:其中 为第 次迭代搜索方向,为沿 搜索最正确步长因子(通常也称作最正确步长)。min f(x)s.t.xS第三章第三章 惯用一维搜索方法惯用一维搜索方法第1页可行方向:设可行方向:设 S,dRn,d0,若存在若存在 ,使,使 ,称,称d 为为 点可点可行方向。行方向。同时满足上述两个性质方向称
2、同时满足上述两个性质方向称下降可行方向下降可行方向。下降方向下降方向 :设设 S,d Rn,d0,若存在若存在 ,使,使 ,称,称d 为为 在在 点下降方向。点下降方向。第2页l模型算法模型算法线性搜索求线性搜索求 ,新点新点使使x(k+1)S初始初始x(1)S,k=1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件?是否满足停机条件?停停k=k+1yesno531第3页二、二、收敛性收敛性概念概念:考虑(考虑(NP)设迭代算法产生点列设迭代算法产生点列x(k)S.1.理想收敛性:设理想收敛性:设x*S是是g.opt(全局最优解全局最优解).当当x*x(k)或或 x(k
3、)x*,k,满足满足 时,称算法收敛到最优解时,称算法收敛到最优解 x*。min f(x)s.t.xS第4页 因为非线性规划问题复杂性,实用中建立以下收敛因为非线性规划问题复杂性,实用中建立以下收敛性概念性概念:2.实用收敛性:定义解集实用收敛性:定义解集 S*=x|x 含有某种性质含有某种性质 例:例:S*=x|x-g.opt S*=x|x-l.opt S*=x|f(x)=0 S*=x|f(x)(为给定实数阈值为给定实数阈值)第5页2.实用收敛性(续)实用收敛性(续)收敛性:设解集收敛性:设解集S*,x(k)为算法产生点列。为算法产生点列。以下情况之一成立时,称算法收敛:以下情况之一成立时,
4、称算法收敛:1 x(k)S*;2x(k)S*,k,x(k)任意极限点任意极限点x*S*。全局收敛全局收敛:对任意初始点:对任意初始点x(1),算法均收敛。算法均收敛。局部收敛局部收敛:当:当x(1)充分靠近解充分靠近解x*时,算法收敛。时,算法收敛。有限步终止有限步终止第6页三、收敛速度三、收敛速度 设算法产生点列设算法产生点列x(k)收敛到解收敛到解x*,且,且x(k)x*,k,关于算法收敛速度,有关于算法收敛速度,有1.线性收敛:线性收敛:当当k充分大时成立。充分大时成立。2.超线性收敛:超线性收敛:3.二阶收敛:二阶收敛:0,是是 使当使当k充分大时有充分大时有第7页三、收敛速度(续)三
5、、收敛速度(续)定理:设算法点列定理:设算法点列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,利用超线性收敛定义可得结果。利用超线性收敛定义可得结果。该结论导出算法停顿条件可用:该结论导出算法停顿条件可用:第8页四、二次终止性四、二次终止性一个算法用于解正定二次函数无约束极小时,一个算法用于解正定二次函数无约束极小时,有限步迭代可达最优解,则称该算法含有有限步迭代可达最优解,则称该算法含有二二次终止性次终止性。
6、第9页第10页问题描述:问题描述:问题描述:问题描述:已知而且求出了处可行下降方向从出发,沿方向求以下目标函数最优解,或者选取使得:惯用一维搜索算法惯用一维搜索算法惯用一维搜索算法惯用一维搜索算法第11页设其最优解为(叫准确步长因子),所以线性搜索是求解一元函数最优化问题(也叫一维最优化问题或普通地,一维优化问题可描述为:于是得到一个新点:一维搜索)。或解第12页普通地,线性搜索算法分成两个阶段:第一阶段确定包含理想步长因子(或问题最优解)搜索区间;第二阶段采取某种分割技术或插值方法缩小这个区间。第13页 搜索区间确定 黄金分割法(0.618法)二次插值法 Newton法关键点:关键点:单峰函
7、数消去性质、进退算法基本思想、黄金分割单峰函数消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。法基本思想、方法比较。我们主要介绍以下一些搜索方法:我们主要介绍以下一些搜索方法:第14页学习主要性:学习主要性:1、工程实践中有时需要直接使用;工程实践中有时需要直接使用;2、多变量最优化基础,迭代中经常要用到。多变量最优化基础,迭代中经常要用到。方法分类:方法分类:1、直接法:、直接法:迭代过程中只需要计算函数值;迭代过程中只需要计算函数值;2、微分法:、微分法:迭代过程中还需
8、要计算目标函数导数;迭代过程中还需要计算目标函数导数;第15页f(x)xab3.2 搜索区间确定 惯用一维直接法有惯用一维直接法有消去法消去法和和近似法近似法两类。它们都是从某两类。它们都是从某个初始搜索区间出发,利用个初始搜索区间出发,利用单峰函数消去性质单峰函数消去性质,逐步缩小搜,逐步缩小搜索区间,直到满足精度要求为止。索区间,直到满足精度要求为止。3.2.1 单峰函数单峰函数 连续单峰函数连续单峰函数f(x)xab不连续单峰函数不连续单峰函数f(x)xab离散单峰函数离散单峰函数f(x)xa b非单峰函数非单峰函数定义:定义:假如函数假如函数f(x)在区间在区间a,b上只有一个极值点上
9、只有一个极值点,则称则称f(x)为为 a,b上单峰函数。上单峰函数。第16页单峰函数含有一个主要消去性质单峰函数含有一个主要消去性质定理:定理:设设f(x)是区间是区间a,b上一个单峰函数,上一个单峰函数,x*a,b是其极小点,是其极小点,x1 和和x2是是a,b上任意两点,且上任意两点,且ax1 x2b,那么比较,那么比较f(x1)与与f(x2)值后,可得出以下结论:值后,可得出以下结论:f(x)xab(I)消去消去a,x1 x*x1x2f(x)xab(II)消去消去x2,bx*x2x1(II)(II)若若f(x1)f(x2),x*a,x2在单峰函数区间内,计算两个点函数值,比较大小后,就能
10、把在单峰函数区间内,计算两个点函数值,比较大小后,就能把搜索区间缩小。在已缩小区间内,仍含有一个函数值,若再计搜索区间缩小。在已缩小区间内,仍含有一个函数值,若再计算另一点函数值,比较后就可深入缩小搜索区间算另一点函数值,比较后就可深入缩小搜索区间.(I)若若f(x1)f(x2),x*x1,b第17页3.2.2 进退算法进退算法(或称成功或称成功-失败失败法法)怎样确定包含极小点在内初始区间怎样确定包含极小点在内初始区间?(一)(一)基本思想:基本思想:由单峰函数性质可知,函数值在极小点左边严格下降,在右边由单峰函数性质可知,函数值在极小点左边严格下降,在右边严格上升。严格上升。f(x)xab
11、x*x0 x1x2从某个初始点出发,沿函数值下降方向前进,直至发觉函数值从某个初始点出发,沿函数值下降方向前进,直至发觉函数值上升为止。上升为止。由由两边高,中间低三点两边高,中间低三点,可确定极小点所在初始区间。,可确定极小点所在初始区间。第18页(二)(二)算法算法1、选定初始点选定初始点a 和步长和步长h;f(x)x2、计算并比较计算并比较f(a)和和f(a+h);有前进;有前进(1)和后退和后退(2)两种情况:两种情况:(1)前进运算:若前进运算:若f(a)f(a+h),(2)后退运算:若后退运算:若f(a)f(a+h),a a+h 则步长加倍,计算则步长加倍,计算f(a+3h)。若。
12、若f(a+h)f(a+3h),令令 a1=a,a2=a+3h,停顿运算;不然将步长加倍,并重复上述运算。停顿运算;不然将步长加倍,并重复上述运算。a+3hf(x)xaa+ha+7ha1b1a-ha-3ha-7ha1b1 则将步长改为则将步长改为h。计算。计算f(ah),若若f(ah)f(a),令令 a1=ah,a2=a+h,停顿运算;不然将步长加倍,继续后退。停顿运算;不然将步长加倍,继续后退。仅仅找区间!若深入找最仅仅找区间!若深入找最小点,参阅小点,参阅P44!第19页(三三)几点说明几点说明缺点:效率低;缺点:效率低;优点:能够求搜索区间;优点:能够求搜索区间;注意:注意:h 选择要适当
13、,选择要适当,初始步长不能选得太小初始步长不能选得太小;第20页3.3 区间消去法黄金分割法区间消去法黄金分割法 消去法思想:消去法思想:重复使用单峰函数消去性质,不停缩小包含极小点搜索区重复使用单峰函数消去性质,不停缩小包含极小点搜索区间,直到满足精度为止。间,直到满足精度为止。消去法优点:消去法优点:只需计算函数值,通用性强。只需计算函数值,通用性强。消去法设计标准:消去法设计标准:(1)迭代公式简单;()迭代公式简单;(2)消去效率高;)消去效率高;(3)对称:)对称:x1 a=b-x2;(4)保持缩减比:)保持缩减比:=(保留区间长度原保留区间长度原区间长度区间长度)不变。(使每次保留
14、下来节点,不变。(使每次保留下来节点,x1或或 x2,在下一次比较中,在下一次比较中成为一个对应百分比位置节点成为一个对应百分比位置节点)。)。(一)(一)黄金分割黄金分割 xabL LL (1 1)L L取“”,=0.61803398874189 第21页(二)(二)黄金分割法基本思想黄金分割法基本思想 黄金分割主要黄金分割主要消去性质消去性质:x2abL LL (1 1)L Lx1 LL (1 1)L L设设x1,x2 为为a,b 中对称两个黄金分割点,中对称两个黄金分割点,x1为为a,x2黄黄金分割点金分割点x2为为x1,b黄金分割黄金分割点点 在在进进行行区区间间消消去去时时,不不论论
15、是是消消去去a,x1,还还是是消消去去x2,b,留留下下来来区区间间中中还还含含一一个个黄黄金金分分割割点点,只只要要在在对对称称位位置置找找另另一一个个黄黄金金分分割割点点,又又能够进行下一次区间消去。能够进行下一次区间消去。每次消去后,新区间长度是原区间每次消去后,新区间长度是原区间0.618倍,经过倍,经过n次消去后次消去后,保,保留下来留下来区间长度为区间长度为0.618nL,需,需计算函数值次数仅为计算函数值次数仅为n+1。黄金分割比黄金分割比 0.618,所以此法也称为,所以此法也称为0.618法。法。第22页(三)(三)算法算法 开始开始b-x1 x2 a 给定给定a0,b0,a
16、=a0,b=b0,=0.618034x2=a+(b-a),x1=a+bx2f2=f(x2),f1=f(x1)f1 f2是是否否a=x1,x1=x2,f1=f2 x2=a+b-x1,f2=f(x2)否否b=x2,x2=x1,f2=f1 x1=a+b-x2,f1=f(x1)否否x*a,x2x*x1,bx*=x1,f*=f1结束结束是是x*=x2,f*=f2是是abx2x1x1 x2=ab第23页!在迭代过程中,四个点次序一直应该是在迭代过程中,四个点次序一直应该是 ax1 x2 b但在计算第二个分割点时使用但在计算第二个分割点时使用x1=a+bx2 或或 x2=a+b x1,因为舍入误差影因为舍入
17、误差影响,可能破坏响,可能破坏ax1 x2 b这一次序,造成混乱。迭代中必须采取一些办法:这一次序,造成混乱。迭代中必须采取一些办法:(1)终止限终止限 不要取得太小;不要取得太小;(2)使用双精度运算使用双精度运算;(3)经过若干次运算后,转到算法中第经过若干次运算后,转到算法中第3步,步,重新开始。重新开始。(四四)黄金分割法优缺点黄金分割法优缺点 2、缺点:对解析性能好单峰函数,与后面要介绍二次插值法、三次缺点:对解析性能好单峰函数,与后面要介绍二次插值法、三次 插值法及牛顿拉夫森法等比较,计算量较大,收敛要慢。插值法及牛顿拉夫森法等比较,计算量较大,收敛要慢。1、优点:算法简单,效率高
18、,只计算函数值,对函数要求低,稳定性好,优点:算法简单,效率高,只计算函数值,对函数要求低,稳定性好,对多峰函数或强扭曲,甚至不连续,都有效对多峰函数或强扭曲,甚至不连续,都有效;第24页 迭代迭代 序号序号ab比较比较0-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.665例例例例3-23-2对函数对函数对函数对函数 ,当给定搜索区间,当给定搜索区间,当给定搜索区间,当给定搜索区间 时,时,时,时,试用黄金分割法求极小
19、点。试用黄金分割法求极小点。试用黄金分割法求极小点。试用黄金分割法求极小点。第25页f(x)=x2,a=-1.5,b=1;精度10-5 a x1 x2 b-3.6034e-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.
20、618035-1.1922e-005-2.7117e-006 2.9804e-006 1.219e-00525 0.618032 0.618032-1.1922e-005-6.2296e-006-2.7117e-006 2.9804e-00626 0.618038 0.618038x*=-2.7117e-006若用若用0.618效果较差效果较差0.61803第26页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
21、-2.4483e-008 2.5078e-008 9.7933e-00835 0.595145 0.595145-9.7339e-008-4.7778e-008-2.4483e-008 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.18
22、88e-009 2.805e-008 2.5078e-00839 -0.113146 -0.1131461.7832e-009 3.1022e-008-1.1888e-009 2.805e-00840-9.83816 -9.83816x*=-1.1888e-009(不满足精度不满足精度)若用若用0.618效果更差效果更差第27页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-x
23、1)-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-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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 搜索 算法 结构 教学 课件 公开 一等奖 联赛 特等奖
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。