《0.618法与Fibonacci法【上课课堂】》由会员分享，可在线阅读，更多相关《0.618法与Fibonacci法【上课课堂】（27页珍藏版）》请在金锄头文库上搜索。
1、0.618法与法与Fibonacci法法单谷函数单谷函数(Unimodal Function)-定义定义1课堂节课0.618法与法与Fibonacci法法单谷函数单谷函数-性质性质注：注：通过计算区间通过计算区间内两个不同点的函数值，就可以内两个不同点的函数值，就可以确定一个包含极小点的子区间确定一个包含极小点的子区间. .2课堂节课0.618法与法与Fibonacci法法单谷函数单谷函数-性质性质3课堂节课0.618法与法与Fibonacci法法(3)(1);(2)数数; ;问题的提出问题的提出4课堂节课0.618法与法与Fibonacci法法通过选取试探点使包含极小点的区间不断缩短，通过选
2、取试探点使包含极小点的区间不断缩短，值均接近极小值。值均接近极小值。直到区间长度小到一定程度，此时区间上各点的函数直到区间长度小到一定程度，此时区间上各点的函数0.6180.618法法( (黄金分割法黄金分割法)- )- Golden Section Search 思路思路5课堂节课下面推导黄金分割法的计算公式下面推导黄金分割法的计算公式. .0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 计算公式计算公式6课堂节课0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 计算公式计算公式 缩短率缩短率7
3、课堂节课0.6180.618法法( (黄金分割法黄金分割法) )情情每次迭代区间长每次迭代区间长度的缩短率相同度的缩短率相同1 1 计算公式计算公式8课堂节课0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) )注：注： 缩短率缩短率 恰为黄金分割数，即它满足恰为黄金分割数，即它满足几何意义：几何意义：黄金分割数黄金分割数 对对应的点在单位长区间应的点在单位长区间 0,1中的位置相当于其对中的位置相当于其对称点称点 在区间在区间0， 中中的位置的位置(如图如图6.2.2所示所示)注注 计算公式计算公式9课堂节课0.618法与法与Fibonacci法法0
4、.6180.618法法( (黄金分割法黄金分割法) ) 算法步骤算法步骤0.618.= =Step3若若则则停；停； 否则否则转转StepStep. .10课堂节课例例 用黄金分割法求函数用黄金分割法求函数在区间在区间上的极小点。上的极小点。要求最终区间长度不大于要求最终区间长度不大于原始区间长度的原始区间长度的0.080.08倍倍解解函数函数在区间在区间上为单谷函数，且上为单谷函数，且0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 举例举例11课堂节课第一次迭代第一次迭代缩短后区间为缩短后区间为第二次迭代第二次迭代缩短后区间为缩短后区间为0.
5、618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 举例举例12课堂节课迭代迭代次数次数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.7
6、531.7531.7511.751否否0.5280.5280.5800.5801.7511.7511.7571.757是是13课堂节课0.618法与法与Fibonacci法法Fibonacci法法当事先给定搜索算法的迭代次数当事先给定搜索算法的迭代次数N时，问按何种规则选取时，问按何种规则选取试探点可以使给定的搜索区间长度最快地缩短试探点可以使给定的搜索区间长度最快地缩短?思路思路问题的提出问题的提出 由由0.6180.618法的推导过程知：在一般搜索算法的迭代过程法的推导过程知：在一般搜索算法的迭代过程中，缩短率满足中，缩短率满足 且且 14课堂节课0.618法与法与Fibonacci法法F
7、ibonacci法法待解决的问题转化待解决的问题转化为优化问题：为优化问题：思路思路可以证明，此优化问题的最优解为可以证明，此优化问题的最优解为 其中其中 FN-k 为为Fibonacci数数，即，即 15课堂节课0.618法与法与Fibonacci法法Fibonacci法法Fibonacci 法迭代公式法迭代公式=16课堂节课0.618法与法与Fibonacci法法Fibonacci法法注意事项注意事项(1) 迭代次数迭代次数n-1的确定的确定若原始区间为若原始区间为要求最终区间长度要求最终区间长度则则可确定可确定n-n-1 1. .(2) (2) 第第n n-1-1次迭代中两个试点的选取方
8、式次迭代中两个试点的选取方式17课堂节课Fibonacci法法算法步骤算法步骤+18课堂节课Fibonacci法法算法步骤算法步骤0.618法与法与Fibonacci法法19课堂节课例例 用用FibonacciFibonacci法求函数法求函数在区间在区间上的极小点。上的极小点。要求最终区间长度不大于要求最终区间长度不大于原始区间长度的原始区间长度的0.080.08倍倍解解： 函数函数在区间在区间上为下单峰函数，上为下单峰函数，由由可知可知应取应取0.618法与法与Fibonacci法法Fibonacci法法举例举例20课堂节课第一次迭代第一次迭代：缩短后区间为缩短后区间为0.618法与法与F
9、ibonacci法法Fibonacci法法举例举例21课堂节课第二次迭代第二次迭代：缩短后区间为缩短后区间为0.618法与法与Fibonacci法法Fibonacci法法举例举例22课堂节课第三次迭代第三次迭代：缩短后区间为缩短后区间为第四次迭代第四次迭代：缩短后区间为缩短后区间为0.618法与法与Fibonacci法法Fibonacci法法举例举例23课堂节课第五次迭代：第五次迭代：0.618法与法与Fibonacci法法Fibonacci法法举例举例缩短后区间为缩短后区间为0.231, 0.5386.24课堂节课Fibonacci方法评价方法评价FibonacciFibonacci法的优点法的优点 效率最高，有限个试点的情况下，可将效率最高，有限个试点的情况下，可将最优点所在最优点所在的区间缩小到最小的区间缩小到最小0.618法与法与Fibonacci法法25课堂节课FibonacciFibonacci法的缺点法的缺点（）搜索前先要计算搜索的步数；（）搜索前先要计算搜索的步数；（）每次搜索试点计算的公式不一致（）每次搜索试点计算的公式不一致Fibonacci方法评价方法评价0.618法与法与Fibonacci法法26课堂节课0.618法与法与Fibonacci法法0.618法与法与Fibonacci法的关系法的关系其他方法：二分法其他方法：二分法27课堂节课
