机械优化设计第三章课件.ppt

《机械优化设计第三章课件.ppt》由会员分享，可在线阅读，更多相关《机械优化设计第三章课件.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 一维搜索方法一维搜索 一维搜索：对于单个变量（一维问题）的直接探索（搜索 或寻查）。多维问题的数值迭代法每步为一维搜索1）解析法：2）数值解法的基本思想：确定*所在的搜索区间，然后根据区间消去原理不断缩小区间，从而获得*的数值近似解。第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理单峰区间：单峰区间：函数在该区间只有一个极值点。“高低高”第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理确定搜索区间的外推法 确定搜索区间的外推法（进退法/成功失败法）：“高低高”第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理确定搜索区间的外推法 确定搜索区间的外推法的基本步

2、骤：第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理确定搜索区间的外推法 确定搜索区间的外推法的基本步骤：第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理确定搜索区间的外推法 确定搜索区间的外推法的程序流程图：第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理例：第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理一维搜索的基本原理：通过外推法，我们可以确定一个包含一元函数极值点的搜索区间，为了进一步找到极小点，我们需要不断的缩小搜索区间，消去不可能包含极小点的区间，使区间在缩小的过程中逐步向极小点靠拢，最后缩小到极小点附近一个极小的领域内。这个时候，如果我们

3、规定一个足够小的正数，称为收敛精度。则当区间长度达到足够小，即 取该区间的中点 作为极值点，这才能完成整个一维搜索。第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理区间消去原理 区间消去原理：不断缩小区间所用的原理。包括：1）直接法：直接比较试选点的函数值；2）间接法：利用函数导数值的变化信息。第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理直接法第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理直接法第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理间接法0 00第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理区间缩短率：第三章 一维搜索方法第二

4、节 搜索区间的确定与区间消去法原理一维搜索方法的分类：试探法 试探法：它是按照某种给定的规律来确定区间内插入点的位置的。插入点位置的确定是为了使区间缩短的更快，而不管函数值的分布规律。它包括：黄金分割法（0.618法）、裴波纳契（Fibonacci）法等。插值法 插值法（函数逼近法 函数逼近法）：这种方法是根据某点处的某些信息（如函数值、一阶导数、二阶导数等）来构造一个差值函数来逼近原来的函数，用插值函数的极小点作为区间的插入点。它包括：二次差值法、三次插值法等。第三章 一维搜索方法第三节 一维搜索的试探法黄金分割法（0.618法）：基本原理：基本原理：通过比较单峰区间内两个内分点的函数值，不

5、断舍弃单峰区间的左端或者右端的一部分，使区间按照固定区间缩短率（=0.618）逐步缩短，直到极小点所在的区间缩短到给定的误差范围内，而得到近似最优解。第三章 一维搜索方法第三节 一维搜索的试探法黄金分割法（0.618法）：黄金分割法的内分点的选取原则：黄金分割法的内分点的选取原则：每次区间缩短都取相等的区间缩短率（），同时插入点距离两个端点有对称性。第三章 一维搜索方法第三节 一维搜索的试探法黄金分割法（0.618法）：计算步骤：计算步骤：第三章 一维搜索方法第三节 一维搜索的试探法黄金分割法（0.618法）：计算步骤：计算步骤：第三章 一维搜索方法第三节 一维搜索的试探法黄金分割法（0.61

6、8法）：计算步骤：计算步骤：第三章 一维搜索方法第三节 一维搜索的试探法黄金分割法（0.618法）：程序框图：程序框图：第三章 一维搜索方法第三节 一维搜索的试探法黄金分割法（0.618法）：例：例：第三章 一维搜索方法第三节 一维搜索的试探法斐波那契法：和黄金分割法相似，都是在搜索区间内对称的取点，通过比较两点函数值逐步缩小初始单峰区间来搜索出满意的极小点x*。与黄金分割法不同的是：黄金分割法每次迭代式按照同一区间缩短率=0.618来缩短区间，而斐波那契法每次迭代的区间缩短率是不同的，它是按斐波那契数列Fn产生的分数序列为缩短率来缩短区间的。，第三章 一维搜索方法第三节 一维搜索的试探法斐波

7、那契法：，斐波那契数：凡是满足递推关系而产生的正数序列Fn，就称为斐波那契数。n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Fn 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 第三章 一维搜索方法第三节 一维搜索的试探法斐波那契法：，n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Fn 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 区间缩短率用相邻两数的前一数与后一数之比产生，如计算五个点的函数值（即迭代四次，每次区间缩短率分别为第三章 一维搜索方法第三节 一维

8、搜索的试探法斐波那契法：，n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Fn 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 推广到计算n个点的函数值，经过n-1次迭代所获得的区间总缩短率为第三章 一维搜索方法第三节 一维搜索的试探法斐波那契法的特点：，第三章 一维搜索方法第三节 一维搜索的试探法斐波那契法的迭代步骤：，第三章 一维搜索方法第三节 一维搜索的试探法斐波那契法的迭代步骤：，第三章 一维搜索方法第四节 一维搜索的插值方法插值法（函数逼近法）：我们就可以根据几个试验点的函数值，利用插值方法建立函数的某种近似表达式，进而

9、求得函数的极小值，并用它作为原函数极小点的近似值。这种方法称为插值法，或函数逼近法。牛顿法（切线法）：牛顿法（切线法）：利用一点的函数值，一阶导数值和二阶导数值来构造此二次函数。抛物线法（二次插值法）：抛物线法（二次插值法）：利用三点的函数值形成一个抛物线来构造二次函数。，第三章 一维搜索方法第四节 一维搜索的插值方法牛顿法（切线法）：用切线代替弧逐渐逼近函数极值的一种方法。，牛顿法的迭代公式 牛顿法的迭代公式:第三章 一维搜索方法第四节 一维搜索的插值方法牛顿法的计算步骤：，第三章 一维搜索方法第四节 一维搜索的插值方法，牛顿法的缺点 牛顿法的缺点：1）每一次迭代都要计算函数的二阶导数，增加

10、了计算工作量；2）对初始点的要求较高，如果选不好，可能使数列发散或收敛到一个不是极小点的点上。第三章 一维搜索方法第四节 一维搜索的插值方法，第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，基本思想：基本思想：在给定的单峰区间a,b内，利用函数上的三个点来构造一个二次插值函数p()，以近似地表达原目标函数f()，并求这个插值函数的极小点近似作为原目标函数的极小点。它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索方法。第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，第三章 一维搜索方法第四节 一维搜索的插值方法二次插值

11、法（抛物线法）：，缩小搜索区间：缩小搜索区间：用插值函数 用插值函数p(p()的极小点 的极小点 p p作为原目标函数的极小点 作为原目标函数的极小点*的近似解，通常不能满足给定的迭代精度要求，所以需 的近似解，通常不能满足给定的迭代精度要求，所以需要多次缩短搜索区间，使 要多次缩短搜索区间，使 p p的点列中的各点依次逐步逼 的点列中的各点依次逐步逼近 近*。第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，缩小搜索区间：缩小搜索区间：第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，缩小搜索区间：缩小搜索区间：第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，计算步骤：计算步骤：第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，计算步骤：计算步骤：第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，第三章 一维搜索方法第四节 一维搜索的插值方法二次插值法（抛物线法）：，