0.618法与Fibonacci法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,0.618法与Fibonacci法,单谷函数(Unimodal Function)-定义,1,0.618法与Fibonacci法,单谷函数-性质,注：,通过计算区间,内两个不同点的函数值，就可以,确定一个包含极小点的子区间.,2,0.618法与Fibonacci法,单谷函数-性质,3,0.618法与Fibonacci法,(3),(1),;,(2),数;,问题的提出,4,0.618法与Fibonacci法,通过选取试探点使包含极小点的区间不断缩短，,值均接近极小值。,直到区间长度小到一定程度，此时区间上各点的函数,0.618法(黄金分割法)-,Golden Section Search,思路,5,下面推导黄金分割法的计算公式.,0.618法与Fibonacci法,0.618法(黄金分割法),计算公式,6,0.618法与Fibonacci法,0.618法(黄金分割法),计算公式,缩短率,7,0.618法(黄金分割法),情,每次迭代区间长,度的缩短率相同,1,计算公式,8,0.618法与Fibonacci法,0.618法(黄金分割法),注：,缩短率 恰为黄金分割数，即它满足,几何意义：,黄金分割数 对应的点在单位长区间,0,1中的位置相当于其对称点 在区间0，中的位置(如图,6.2.2,所示),注,计算公式,9,0.618法与Fibonacci法,0.618法(黄金分割法),算法步骤,0.618.,=,Step3,若,则,停；,否则,转Step.,10,例,用黄金分割法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的0.08倍,解,函数,在区间,上为单谷函数，且,0.618法与Fibonacci法,0.618法(黄金分割法),举例,11,第一次迭代,缩短后区间为,第二次迭代,缩短后区间为,0.618法与Fibonacci法,0.618法(黄金分割法),举例,12,迭代,次数,0.528,1.472,1.751,2.695,否,-0.056,0.528,2.059,1.751,否,0.528,0.888,1.751,1.901,否,0.305,0.528,1.788,1.751,否,0.528,0.665,1.751,1.777,否,0.443,0.528,1.753,1.751,否,0.528,0.580,1.751,1.757,是,13,0.618法与Fibonacci法,Fibonacci法,当事先给定搜索算法的迭代次数,N,时，问按何种规则选取试探点可以使给定的搜索区间长度最快地缩短?,思路,问题的提出,由0.618法的推导过程知：在一般搜索算法的迭代过程中，缩短率满足 且,14,0.618法与Fibonacci法,Fibonacci法,待解决的问题转化,为优化问题：,思路,可以证明，此优化问题的最优解为,其中,F,N-k,为,Fibonacci,数,，即,15,0.618法与Fibonacci法,Fibonacci法,Fibonacci 法迭代公式,=,16,0.618法与Fibonacci法,Fibonacci法,注意事项,(1)迭代次数,n,-1的确定,若原始区间为,要求最终区间长度,则,可确定,n-,1,.,(2),第,n,-1次迭代中两个试点的选取方式,17,Fibonacci法,算法步骤,+,18,Fibonacci法,算法步骤,0.618法与Fibonacci法,19,例,用Fibonacci法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的0.08倍,解,：,函数,在区间,上为下单峰函数，,由,可知,应取,0.618法与Fibonacci法,Fibonacci法,举例,20,第一次迭代,：,缩短后区间为,0.618法与Fibonacci法,Fibonacci法,举例,21,第二次迭代,：,缩短后区间为,0.618法与Fibonacci法,Fibonacci法,举例,22,第三次迭代,：,缩短后区间为,第四次迭代,：,缩短后区间为,0.618法与Fibonacci法,Fibonacci法,举例,23,第五次迭代：,0.618法与Fibonacci法,Fibonacci法,举例,缩短后区间为,0.231,0.5386.,24,Fibonacci方法评价,Fibonacci法的优点,效率最高，有限个试点的情况下，可将,最优点所在的区间缩小到最小,0.618法与Fibonacci法,25,Fibonacci法的缺点,（）搜索前先要计算搜索的步数；,（）每次搜索试点计算的公式不一致,Fibonacci方法评价,0.618法与Fibonacci法,26,0.618法与Fibonacci法,0.618法与Fibonacci法的关系,其他方法：二分法,27,