现代设计方法---一维搜索

1、12345x0d0 x1d1x2d2x3d3xkxk+1dk67单谷区间内函数单谷区间内函数可以不连续，也可以不连续，也可以有不可微点可以有不可微点8(1) 如图如图(a)所示，若所示，若x1、x2在在x*的右侧，则必然的右侧，则必然f (x1) f (x2) ，这种情况，这种情况下，可丢掉下，可丢掉(a0,x1)部分，而最小点部分，而最小点x*必在区间必在区间(x1,b0) 内内0a*x1x2xx(a)(a)(xf0b0a0b*x1x2xx)(xf(b)(b)*x1x2xx)(xf(c)(c)(3) 如图如图(c)所示，若所示，若x1、x2在在x*的两侧，的两侧， f (x1)= f (x2

2、) ，则不论丢掉，则不论丢掉 (a0,x1) ，还是，还是(x2,b0)，最小点，最小点x* 必在留下部分内。必在留下部分内。0a0b图图3-1 搜索区间的缩短搜索区间的缩短n平分法：平分法：适于目标函数易求一阶或二阶导数。取具有极小点的适于目标函数易求一阶或二阶导数。取具有极小点的单谷函数单谷函数的探索区间的探索区间 s, e的的中点中点 m作为计算点，并根据函数在作为计算点，并根据函数在 m处处的的一阶导数一阶导数(0或或0 ，递增，则取新区间为，递增，则取新区间为 s(k), m(k)（左边）（左边）)。收缩率约为收缩率约为0.5。n Fibonacci法（分数法）法（分数法）F(1)=

3、 F(2)=1, F(n)= F(n-1)+ F(n-2)(n2)按照上式产生的按照上式产生的Fibonacci数数F(n)，缩短率为，缩短率为 (n)=F(n-1)/F(n) )(ksa)(kma)(kea1)-(3 1xLxxLa1(0)a2(0)as(0)ae(0)0()0()()1()0()0(1)0()0()()1()0()0(2 senneesnnsaaFFaaaaFFaa或如如 f( 2(0) )f( 1(0)，则探索区间，则探索区间 s(0), e(0)缩短为缩短为 s(0), 2(0)如如 f( 2(0) ) f( 1(0)，则探索区间，则探索区间 s(0), e(0)缩短为

4、缩短为 1(0), e(0)114)-(3 618. 0 3)-(3 6180339887. 0251 )23()23( 01 0 ) 13( 222LLx LLxx得两根，取正根：解方程式，即得：由式 斐波纳契数列是斐波纳契数列是1、1、2、3、5、8、13、21、34、55、89、 144、 233 。上述神秘数字的任何两个连续的比率，譬如。上述神秘数字的任何两个连续的比率，譬如55/89 0.618，89/1440.618。相邻两个斐波那契数的比值是随序相邻两个斐波那契数的比值是随序号的增加而逐渐趋于黄金分割比的。号的增加而逐渐趋于黄金分割比的。这组数字十分有趣。这组数字十分有趣。0.6

5、18的倒数是的倒数是1.618。譬如。譬如233/144 1.168。有人研究过向日葵，发现向日葵花有有人研究过向日葵，发现向日葵花有89个花辫，个花辫，55个朝一方，个朝一方，34个朝向另一方。五角星非常美丽，这是因为在五角星中可以找到个朝向另一方。五角星非常美丽，这是因为在五角星中可以找到的所有线段之间的长度关系都是符合黄金分割比的。的所有线段之间的长度关系都是符合黄金分割比的。 1213 因此，只要第二个点取在原始区间的因此，只要第二个点取在原始区间的0.618处，第一点在它对处，第一点在它对称的位置：称的位置：x2=Lx1就能保证无论经过多少次舍去，保留的点始就能保证无论经过多少次舍去

6、，保留的点始终在新区间的终在新区间的0.618处。要进一步缩短区间，在其保留点的对称位处。要进一步缩短区间，在其保留点的对称位置再作一次计算就可以了。而且每次消去时，区间的缩短率置再作一次计算就可以了。而且每次消去时，区间的缩短率E不变，不变，E = = 0.618。因此计算。因此计算n个点以后，总的缩短率为：个点以后，总的缩短率为：7)-(3 1nnE6)-(3 22212xxLxxLx618. 0149)-(3 )(1 ()( 8)-(3 )(000100020001abaxabaxabbx或图图3-2 黄金分割法的取点图黄金分割法的取点图若给定区间缩短的精度若给定区间缩短的精度，黄金分割

7、法的计算方法及，黄金分割法的计算方法及步骤步骤如下：如下：n (1)设初始区间为设初始区间为a0 ，b0，第一次区间缩短要取两个点，如，第一次区间缩短要取两个点，如3-2(b)所示，分别为：所示，分别为：计算计算f (x1)与与f (x2)，并进行比较，并进行比较若若f (x1)f (x2) ，则如图，则如图3-2(c) 若若f (x1) f (x2) ，则如图，则如图3-2(d)10)-(3 )(1 ( , , 1111122101abaxxxxbaa11)-(3 )( , , 1112210111abaxxxbbxa1512)-(3 00abab图图3-3 3-3 黄金分割法程序框图黄金分

8、割法程序框图给定给定,ba)(),(618. 0222xffabax)(),(382. 0111xffabax21ff 否否否否21211,ffxxxa)(),(618. 0222xffabax是是)(),(382. 0111xffabax12122,ffxxxbab是是)()(5 . 0 xffbax止止也可采用迭代次数是否大于或等于也可采用迭代次数是否大于或等于 k k 作终止准则。作终止准则。xab1x2x1f2f1x2xaff1x2xbab1x2xx1f2f例例1 用黄金分割法求函数用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定的极小点，给定a, b=0, 2, =0.2。

9、解：第一次缩小区间： x1=0+0.382 (2-0)=0.764, f1=0.282 x2=0+0.618(2-0)=1.236, f2=2.72 f10.2第二次缩小区间：令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382 (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, 应继续缩小区间 第三次缩小区间：令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618(1.236-0.472)=0.944, f2=0.747由

10、于f10.2, 应继续缩小区间第四次缩小区间：令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382 (0.944-0.472)=0.652, f1=0.223由于f10.2, 应继续缩小区间第五次缩小区间：令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382 (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.18 x2则转则转；若；若x4 x2则转则转。 若若f2f4成立成立，则则x1=x2，x2=x4，f1=f2，f2

11、=f4，区间缩短为区间缩短为x2， x4 ，x3，转；否则转；否则x3=x4，f3=f4，区间缩短为区间缩短为x1， x2 ，x4，转转。)(xf)(111fxP，)(222fxP，4x)(333fxP，)(xfOx)(xP*x3x3f1x1f2x2f)(xP)(111fxP，)(222fxP，4x)(333fxP，)(xfOx)(xf*x3x3f1x1f2x2f2x1x3x27 若若f4f2成立成立，则则x3=x2，x2=x4，f3=f2，f2=f4，区间缩短为区间缩短为x1， x4 ，x2，转；否则转；否则x1=x4，f1=f4，区间缩短为区间缩短为x4， x2 ，x3，转。转。 区间搜索

12、完毕。然后转向计算新的搜索区间区间搜索完毕。然后转向计算新的搜索区间x1， x2 ，x3上插值抛物线的极小点上插值抛物线的极小点x4 。)(xfOx)( xf3x3f1x2x2f*x3x2x)(xfOx)(xf)(xP4x3x3f1x1f2x2f1x*x1f4x28抛物线插值法的计算流程图抛物线插值法的计算流程图a, b=0, 2,2）用二次插值法逼近极小点相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式： 0.555 )()()()()()(213212131323222122123123224fxxfxxfxxfxxfxxfxxx0.2

13、924f由于f4f2, x40.2, 应继续迭代。在新区间，相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1 x4=0.607, f4=0.243 由于f4x2, 新区间a,b=x2, b=0.555, 1 |x2-x4 |=|0.555-0.607|=0.052 f2。比较函数值可知应去掉区间x1, x4，以x4, x2 , x3作为x1, x2 , x3构建新的P(x)05. 00378. 042xx8969.155)(6850.155)(42xfxf9501. 34* xx31323323)-(3 )(2211kkkkxxxx24)-(3 )(21 11kkkxxx3435