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