《0.618法与Fibonacci法》精美课件

1、0.618法与Fibonacci法0.618法与法与Fibonacci法法单谷函数单谷函数(Unimodal Function)-定义定义0.618法与Fibonacci法0.618法与法与Fibonacci法法单谷函数单谷函数-性质性质注：注：通过计算区间通过计算区间,ba内两个不同点的函数值，就可以内两个不同点的函数值，就可以确定一个包含极小点的子区间确定一个包含极小点的子区间. .0.618法与Fibonacci法0.618法与法与Fibonacci法法单谷函数单谷函数-性质性质0.618法与Fibonacci法0.618法与法与Fibonacci法法(3)(1);(2)数数; ;? t

2、如何寻求如何寻求问题的提出问题的提出0.618法与Fibonacci法0.618法与法与Fibonacci法法通过选取试探点使包含极小点的区间不断缩短，通过选取试探点使包含极小点的区间不断缩短，值均接近极小值。值均接近极小值。直到区间长度小到一定程度，此时区间上各点的函数直到区间长度小到一定程度，此时区间上各点的函数0.6180.618法法( (黄金分割法黄金分割法)- )- Golden Section Search 思路思路0.618法与Fibonacci法下面推导黄金分割法的计算公式下面推导黄金分割法的计算公式. .,., kkkkkkkkbabak 且且取取试试探探点点，为为进进一一步

3、步缩缩短短搜搜索索区区间间次次迭迭代代时时，搜搜索索区区间间为为设设第第分两种情况：分两种情况：和和计算计算, )()(kk ,)()(. 1kk 若若情情形形;,11kkkkbaa 则则令令.,11kkkkbba 则则令令？与与如何确定如何确定kk 0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ),)()(. 2kk 若若情情形形 计算公式计算公式0.618法与Fibonacci法. )1(k中中的的位位置置对对称称在在区区间间和和kkk,ba 件：件：要求其满足以下两个条要求其满足以下两个条kakbk ku0.618法与法与Fibonacci

4、法法0.6180.618法法( (黄金分割法黄金分割法) )1(. 121 , )(,k11 kkkkkkkkkababab)()(akkkkkkkkkkabbab )2()3()(1()(akkkkkkkkkkabaab 计算公式计算公式 缩短率缩短率0.618法与Fibonacci法. 1k)2(一一个个新新的的试试探探点点只只增增加加的的试试探探点点，次次迭迭代代中中，保保留留一一个个旧旧为为减减少少计计算算量量，在在第第 0.6180.618法法( (黄金分割法黄金分割法) )情情每次迭代区间长每次迭代区间长度的缩短率相同度的缩短率相同1 1 计算公式计算公式0.618法与Fibona

5、cci法0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) )注：注： 缩短率缩短率 恰为黄金分割数，即它满足恰为黄金分割数，即它满足 .11 几何意义：几何意义：黄金分割数黄金分割数 对对应的点在单位长区间应的点在单位长区间 0,1中的位置相当于其对中的位置相当于其对称点称点 在区间在区间0， 中中的位置的位置(如图如图6.2.2所示所示) -1 ).ab(abb,a1-N111NNNNN的长度次迭代后的搜索区间第注注 计算公式计算公式0.618法与Fibonacci法0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄

6、金分割法) ) 算法步骤算法步骤0.618.= =Step3若若, kkab则则停；停； 否则否则转转StepStep. .,2kkba 0.618法与Fibonacci法例例 用黄金分割法求函数用黄金分割法求函数 22 xxxf在区间在区间 3, 1 上的极小点。上的极小点。要求最终区间长度不大于要求最终区间长度不大于原始区间长度的原始区间长度的0.080.08倍倍解解函数函数 xf在区间在区间 3, 1 上为单谷函数，且上为单谷函数，且 32. 008. 013 0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 举例举例0.618法与Fibo

7、nacci法第一次迭代第一次迭代 3, 1 ba ,528. 0382. 0 aba .751. 11 f ,472. 1618. 0 aba .695. 22 f,21ff 缩短后区间为缩短后区间为 .472. 1, 1 第二次迭代第二次迭代 472. 1, 1 ba,21ff 缩短后区间为缩短后区间为 .472. 1,056. 0 .059. 21 f ,056. 0382. 0 aba 0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 举例举例 ,528. 0618. 0 aba .751. 12 f0.618法与Fibonacci法迭代迭

8、代次数次数0.5280.5281.4721.4721.7511.7512.6952.695否否-0.056-0.0560.5280.5282.0592.0591.7511.751否否0.5280.5280.8880.8881.7511.7511.9011.901否否0.3050.3050.5280.5281.7881.7881.7511.751否否0.5280.5280.6650.6651.7511.7511.7771.777否否0.4430.4430.5280.5281.7531.7531.7511.751否否0.5280.5280.5800.5801.7511.7511.7571.757是

9、是 ba , 1f2f ab 3,1 472.1 ,1 472. 1 ,056. 0 888. 0 ,056. 0 888. 0 ,305. 0 665. 0 ,305. 0 665. 0 ,443. 0 554.02/665.0443.0* x0.618法与Fibonacci法0.618法与法与Fibonacci法法Fibonacci法法当事先给定搜索算法的迭代次数当事先给定搜索算法的迭代次数N时，问按何种规则选取时，问按何种规则选取试探点可以使给定的搜索区间长度最快地缩短试探点可以使给定的搜索区间长度最快地缩短?思路思路问题的提出问题的提出).ab(abb,a1-N618. 0111NNN

10、NN 的的长长度度次次迭迭代代后后的的搜搜索索区区间间法法知知：经经由由 由由0.6180.618法的推导过程知：在一般搜索算法的迭代过程法的推导过程知：在一般搜索算法的迭代过程中，缩短率满足中，缩短率满足 且且 . 121k).ab(abb,a1-N11121NNNN N 的的长长度度次次迭迭代代后后的的搜搜索索区区间间又又知知：经经0.618法与Fibonacci法0.618法与法与Fibonacci法法Fibonacci法法待解决的问题转化待解决的问题转化为优化问题：为优化问题：思路思路. 1,.,2 , 1, 121 , 2,.,2 , 1,1 .min1121 NkNktskkkkN

11、 可以证明，此优化问题的最优解为可以证明，此优化问题的最优解为 , 1,.,2 , 1,1 NkFFkNkNk 其中其中 FN-k 为为Fibonacci数数，即，即 ,.2 , 1, 11110iFFFFFiii0.618法与Fibonacci法0.618法与法与Fibonacci法法Fibonacci法法Fibonacci 法迭代公式法迭代公式=0.618法与Fibonacci法0.618法与法与Fibonacci法法Fibonacci法法注意事项注意事项(1) 迭代次数迭代次数n-1的确定的确定若原始区间为若原始区间为 ,ba要求最终区间长度要求最终区间长度, ) 0( nnab则则,)

12、(1)()(132211121 abFabFFFFFFabFFabnnnnnnn可确定可确定n-n-1 1. . b-aFn 即即，(2) (2) 第第n n-1-1次迭代中两个试点的选取方式次迭代中两个试点的选取方式.0,21111为为辨辨别别常常数数其其中中 nnnnnnba 1111111 . 0,2/ nnnnnnnnabba 或或0.618法与Fibonacci法Fibonacci法法算法步骤算法步骤1 k ,k +0.618法与Fibonacci法Fibonacci法法算法步骤算法步骤0.618法与法与Fibonacci法法 1111111 . 0,2/ nnnnnnnnabba

13、或或0.618法与Fibonacci法例例 用用FibonacciFibonacci法求函数法求函数 22 xxxf在区间在区间 3, 1 上的极小点。上的极小点。要求最终区间长度不大于要求最终区间长度不大于原始区间长度的原始区间长度的0.080.08倍倍解解： 函数函数 xf在区间在区间 3, 1 上为下单峰函数，上为下单峰函数， 32. 008. 013 由由,5 .1208. 0/1 nF可知可知n应取应取 .136 F0.618法与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第一次迭代第一次迭代： 3, 1 ba abFFa 64 4135

14、1 538. 0 462. 14138165 abFFa 675. 2,751. 121 ff,21ff 缩短后区间为缩短后区间为 462. 1, 1 0.618法与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第二次迭代第二次迭代： 462. 1, 1 ba538. 0 751. 12 f 077. 01462. 1153 FF 083. 21 f,21ff 缩短后区间为缩短后区间为 462. 1,077. 0 0.618法与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第三次迭代第三次迭代： 462.

15、1,077. 0 ba538. 0 751. 11 f 846. 0077. 0462. 1077. 043 FF 870. 12 f,21ff 缩短后区间为缩短后区间为 846. 0,077. 0 第四次迭代第四次迭代： 846. 0,077. 0 ba538. 0 751. 12 f 231. 0077. 0846. 0077. 031 FF 822. 11 f,21ff 缩短后区间为缩短后区间为 846. 0,231. 00.618法与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第五次迭代：第五次迭代：0.618法与法与Fibonacci法法

16、Fibonacci法法举例举例 846. 0,231. 0 ba75148. 1,5385. 0)846. 0231. 0(2/11 f 5386. 0001. 0 8148. 12 f,21ff 缩短后区间为缩短后区间为0.231, 0.5386.0.618法与Fibonacci法Fibonacci方法评价方法评价FibonacciFibonacci法的优点法的优点 效率最高，有限个试点的情况下，可将效率最高，有限个试点的情况下，可将最优点所在最优点所在的区间缩小到最小的区间缩小到最小0.618法与法与Fibonacci法法0.618法与Fibonacci法FibonacciFibonacci法的缺点法的缺点（）搜索前先要计算搜索的步数；（）搜索前先要计算搜索的步数；（）每次搜索试点计算的公式不一致（）每次搜索试点计算的公式不一致Fibonacci方法评价方法评价0.618法与法与Fibonacci法法0.61