《机械优化设计第三章课件.ppt》由会员分享,可在线阅读,更多相关《机械优化设计第三章课件.ppt(42页珍藏版)》请在三一办公上搜索。
1、,第三章 一维搜索方法,一维搜索:对于单个变量(一维问题)的直接探索(搜索 或寻查)。,多维问题的数值迭代法,每步为一维搜索,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,单峰区间:函数在该区间只有一个极值点。,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,确定搜索区间的外推法(进退法/成功失败法):,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,确定搜索区间的外推法的基本步骤:,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,确定搜索区间的外推法的基本步骤:,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,确定搜索区
2、间的外推法的程序流程图:,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,例:,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,一维搜索的基本原理: 通过外推法,我们可以确定一个包含一元函数极值点的搜索区间,为了进一步找到极小点,我们需要不断的缩小搜索区间,消去不可能包含极小点的区间,使区间在缩小的过程中逐步向极小点靠拢,最后缩小到极小点附近一个极小的领域内。 这个时候,如果我们规定一个足够小的正数,称为收敛精度。则当区间长度达到足够小,即 取该区间的中点 作为极值点,这才能完成整个一维搜索 。,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,区间消去
3、原理:不断缩小区间所用的原理。 包括:1)直接法:直接比较试选点的函数值; 2)间接法:利用函数导数值的变化信息。,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,直接法,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,直接法,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,间接法,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,区间缩短率:,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,一维搜索方法的分类: 试探法:它是按照某种给定的规律来确定区间内插入点的位置的。插入点位置的确定是为了使区间缩短的更快,而不管函数值的分
4、布规律。它包括:黄金分割法(0.618法)、裴波纳契(Fibonacci)法等。 插值法(函数逼近法):这种方法是根据某点处的某些信息(如函数值、一阶导数、二阶导数等)来构造一个差值函数来逼近原来的函数,用插值函数的极小点作为区间的插入点。它包括:二次差值法、三次插值法等。,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法(0.618法):,基本原理: 通过比较单峰区间内两个内分点的函数值,不断舍弃单峰区间的左端或者右端的一部分,使区间按照固定区间缩短率(=0.618)逐步缩短,直到极小点所在的区间缩短到给定的误差范围内,而得到近似最优解。,第三章 一维搜索方法,第三节 一维搜索的试
5、探法,黄金分割法(0.618法):,黄金分割法的内分点的选取原则:每次区间缩短都取相等的区间缩短率(),同时插入点距离两个端点有对称性。,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法(0.618法):计算步骤:,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法(0.618法):计算步骤:,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法(0.618法):计算步骤:,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法(0.618法):程序框图:,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法(0.618法):例:,第三章 一维搜索方法,第三节
6、 一维搜索的试探法,斐波那契法: 和黄金分割法相似,都是在搜索区间内对称的取点,通过比较两点函数值逐步缩小初始单峰区间来搜索出满意的极小点x*。 与黄金分割法不同的是:黄金分割法每次迭代式按照同一区间缩短率=0.618来缩短区间,而斐波那契法每次迭代的区间缩短率是不同的,它是按斐波那契数列Fn产生的分数序列为缩短率来缩短区间的。,,,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法:,,,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法:,,,区间缩短率用相邻两数的前一数与后一数之比产生,如计算五个点的函数值(即迭代四次,每次区间缩短率分别为,第三章 一维搜索方法,第三节
7、一维搜索的试探法,斐波那契法:,,,推广到计算n个点的函数值,经过n-1次迭代所获得的区间总缩短率为,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法的特点:,,,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法的迭代步骤:,,,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法的迭代步骤:,,,第三章 一维搜索方法,第四节 一维搜索的插值方法,插值法(函数逼近法): 我们就可以根据几个试验点的函数值,利用插值方法建立函数的某种近似表达式,进而求得函数的极小值,并用它作为原函数极小点的近似值。这种方法称为插值法,或函数逼近法 。 牛顿法(切线法):利用一点的函数值,
8、一阶导数值和二阶导数值来构造此二次函数。 抛物线法(二次插值法):利用三点的函数值形成一个抛物线来构造二次函数 。,,,第三章 一维搜索方法,第四节 一维搜索的插值方法,牛顿法(切线法):用切线代替弧逐渐逼近函数极值的一种方法。,,,第三章 一维搜索方法,第四节 一维搜索的插值方法,牛顿法的计算步骤:,,,第三章 一维搜索方法,第四节 一维搜索的插值方法,,,牛顿法的缺点: 1)每一次迭代都要计算函数的二阶导数,增加了计算工作量; 2)对初始点的要求较高,如果选不好,可能使数列发散或收敛到一个不是极小点的点上。,第三章 一维搜索方法,第四节 一维搜索的插值方法,,,第三章 一维搜索方法,第四节
9、 一维搜索的插值方法,二次插值法(抛物线法):,,,基本思想: 在给定的单峰区间a,b内,利用函数上的三个点来构造一个二次插值函数p(),以近似地表达原目标函数f(),并求这个插值函数的极小点近似作为原目标函数的极小点。它是以目标函数的二次插值函数的极小点作为新的中间插入点,进行区间缩小的一维搜索方法。,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,缩小搜索区间: 用插值函数p()的极小点p作为原目标函数的极小点*的近似解,通常不能满足给定的迭代精度要求,所以需要多次缩短搜索区间,使p的点列中的各点依次逐步逼近*。,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,缩小搜索区间:,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,缩小搜索区间:,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,计算步骤:,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,计算步骤:,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法(抛物线法):,,,