《《0.618法与Fibonacci法》精美课件》由会员分享，可在线阅读，更多相关《《0.618法与Fibonacci法》精美课件（28页珍藏版）》请在金锄头文库上搜索。
1、0.618法与法与Fibonacci法法单谷函数单谷函数(Unimodal Function)-定义定义0.618法与Fibonacci法0.618法与法与Fibonacci法法单谷函数单谷函数-性性质质注：注：通过计算区间通过计算区间内两个不同点的函数值，就可以内两个不同点的函数值，就可以确定一个包含极小点的子区间确定一个包含极小点的子区间. .0.618法与Fibonacci法0.618法与法与Fibonacci法法单谷函数单谷函数-性性质质0.618法与Fibonacci法0.618法与法与Fibonacci法法(3)(1);(2)数数; ;问题的提出问题的提出0.618法与Fibona
2、cci法0.618法与法与Fibonacci法法通过选取试探点使包含极小点的区间不断缩短，通过选取试探点使包含极小点的区间不断缩短，值均接近极小值。值均接近极小值。直到区间长度小到一定程度，此时区间上各点的函数直到区间长度小到一定程度，此时区间上各点的函数0.6180.618法法( (黄金分割法黄金分割法)- )- Golden Section Search 思路思路0.618法与Fibonacci法下面推导黄金分割法的计算公式下面推导黄金分割法的计算公式. .0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 计算公式计算公式0.618法与Fib
3、onacci法0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 计算公式计算公式 缩短率缩短率0.618法与Fibonacci法0.6180.618法法( (黄金分割法黄金分割法) )情情每次迭代区间长每次迭代区间长度的缩短率相同度的缩短率相同1 1 计算公式计算公式0.618法与Fibonacci法0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) )注：注： 缩短率缩短率 恰为黄金分割数，即它满足恰为黄金分割数，即它满足几何意义：几何意义：黄金分割数黄金分割数 对对应的点在单位长区间应的点在单位长区间
4、 0,1中的位置相当于其对中的位置相当于其对称点称点 在区间在区间0， 中中的位置的位置(如图如图6.2.2所示所示)注注 计算公式计算公式0.618法与Fibonacci法0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 算法步骤算法步骤0.618.= =Step3若若则则停；停； 否则否则转转StepStep. .0.618法与Fibonacci法例例 用黄金分割法求函数用黄金分割法求函数在区间在区间上的极小点。上的极小点。要求最终区间长度不大于要求最终区间长度不大于原始区间长度的原始区间长度的0.080.08倍倍解解函数函数在区间在区间上为
5、单谷函数，且上为单谷函数，且0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 举例举例0.618法与Fibonacci法第一次迭代第一次迭代缩短后区间为缩短后区间为第二次迭代第二次迭代缩短后区间为缩短后区间为0.618法与法与Fibonacci法法0.6180.618法法( (黄金分割法黄金分割法) ) 举例举例0.618法与Fibonacci法迭代迭代次数次数0.5280.5281.4721.4721.7511.7512.6952.695否否-0.056-0.0560.5280.5282.0592.0591.7511.751否否0.5280.5
6、280.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是是0.618法与Fibonacci法0.618法与法与Fibonacci法法Fibonacci法法当事先给定搜索算法的迭代次数当事先给定搜索算法的迭代次数N时，问按何种规则选取时，问按何种规则选取试
7、探点可以使给定的搜索区间长度最快地缩短试探点可以使给定的搜索区间长度最快地缩短?思路思路问题的提出问题的提出 由由0.6180.618法的推导过程知：在一般搜索算法的迭代过程法的推导过程知：在一般搜索算法的迭代过程中，缩短率满足中，缩短率满足 且且 0.618法与Fibonacci法0.618法与法与Fibonacci法法Fibonacci法法待解决的问题转化待解决的问题转化为优化问题：为优化问题：思路思路可以证明，此优化问题的最优解为可以证明，此优化问题的最优解为 其中其中 FN-k 为为Fibonacci数数，即，即 0.618法与Fibonacci法0.618法与法与Fibonacci法
8、法Fibonacci法法Fibonacci 法迭代公式法迭代公式=0.618法与Fibonacci法0.618法与法与Fibonacci法法Fibonacci法法注意事项注意事项(1) 迭代次数迭代次数n-1的确定的确定若原始区间为若原始区间为要求最终区间长度要求最终区间长度则则可确定可确定n-n-1 1. .(2) (2) 第第n n-1-1次迭代中两个试点的选取方式次迭代中两个试点的选取方式0.618法与Fibonacci法Fibonacci法法算法步骤算法步骤+0.618法与Fibonacci法Fibonacci法法算法步骤算法步骤0.618法与法与Fibonacci法法0.618法与F
9、ibonacci法例例 用用FibonacciFibonacci法求函数法求函数在区间在区间上的极小点。上的极小点。要求最终区间长度不大于要求最终区间长度不大于原始区间长度的原始区间长度的0.080.08倍倍解解： 函数函数在区间在区间上为下单峰函数，上为下单峰函数，由由可知可知应取应取0.618法与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第一次迭代第一次迭代：缩短后区间为缩短后区间为0.618法与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第二次迭代第二次迭代：缩短后区间为缩短后区间为0.618法
10、与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第三次迭代第三次迭代：缩短后区间为缩短后区间为第四次迭代第四次迭代：缩短后区间为缩短后区间为0.618法与法与Fibonacci法法Fibonacci法法举例举例0.618法与Fibonacci法第五次迭代：第五次迭代：0.618法与法与Fibonacci法法Fibonacci法法举例举例缩短后区间为缩短后区间为0.231, 0.5386.0.618法与Fibonacci法Fibonacci方法评价方法评价FibonacciFibonacci法的优点法的优点 效率最高，有限个试点的情况下，可将效率最高，
11、有限个试点的情况下，可将最优点所在最优点所在的区间缩小到最小的区间缩小到最小0.618法与法与Fibonacci法法0.618法与Fibonacci法FibonacciFibonacci法的缺点法的缺点（）搜索前先要计算搜索的步数；（）搜索前先要计算搜索的步数；（）每次搜索试点计算的公式不一致（）每次搜索试点计算的公式不一致Fibonacci方法评价方法评价0.618法与法与Fibonacci法法0.618法与Fibonacci法0.618法与法与Fibonacci法法0.618法与法与Fibonacci法的关系法的关系其他方法：二分法其他方法：二分法0.618法与Fibonacci法此课件下载可自行编辑修改，供参考！此课件下载可自行编辑修改，供参考！感谢你的支持，我们会努力做得更好！感谢你的支持，我们会努力做得更好！
