最优化第二讲——一维搜索法（斐波那契法和java实现）

news/2024/7/6 3:14:45

先看一下斐波那契数列

这个很容易理解，就是当前的值等于前两个值的和

斐波那契法的递归结构如下

步骤一：我们首先要知道需要精确到的区间长度，例如要在[1, 10]之间搜索极小值点，希望精确到0.5之间，那么也就是我最后要求得的Ln的长度要小于等于0.5。所以这个时候就能知道经过几轮计算可以达到这个精度，斐波那契数列指的是：Fn=F(n-1)+F(n-2)。上图可知Ln与Fn是有关系的，所以可以求得满足Ln小于等于0.5的Fn，也就知道了可以迭代几轮。

步骤二：求出L2，L2=L1*F(n-1)/F(n)，这个式子可以由上图得到，就是要确定最开始的t1、t2点，然后比较t1、t2点对应的函数值得大小，缩小区间，缩小区间的方法跟通用方法一致，如果t1的函数值f1大于t2的函数值f2，那么区间缩小为[t1, 10]，否则区间缩小为[1, t2]

步骤三：如果区间缩小为[t1, 10]，这个时候t1=t2，而t2的值等于t1在这个区间内的对称值。其实我们可以看到只有第一步需要计算两个点的函数值，其他步都只要计算一个点的函数值就行，因为另外一个点的函数值由上一步遗留下来

代码实现如下

[java] 
   view plain
   copy
    
   
 private static void fibonacci(float start, float end, float eps) {  
           
         float Fn_1, Fn;  
         int n;  
         float L1 = end - start;  
         float Ln = eps;  
         n = 2;  
         Fn = F(n);  
         //求要经过几轮区间长度才可以小于eps  
         while(Fn <= L1 / Ln) {  
             n ++;  
             Fn = F(n);  
         }  
         Fn_1 = F(n - 1);  
           
         float t1, t2, f1, f2;  
         float a = Math.min(start, end);  
         float b = Math.max(start, end);  
           
         t1 = b - (b - a) * Fn_1 / Fn;  
         t2 = a + b - t1;  
         f1 = fun(t1);  
         f2 = fun(t2);  
           
         while(b - a >= Ln) {  
             if(f2 < f1) {  
                 a = t1;  
                 t1 = t2;  
                 t2 = a + b - t1;  
                 f1 = f2;  
                 f2 = fun(t2);  
             } else {  
                 b = t2;  
                 t2 = t1;  
                 t1 = a + b - t2;  
                 f2 = f1;  
                 f1 = fun(t1);  
             }  
         }  
           
         System.out.println((b + a) / 2);  
     }  
       
     private static float F(int n) {  
           
         if(n == 0 || n == 1) return 1;  
         return F(n - 1) + F(n - 2);  
     }  
       
     private static float fun(float x) {  
         return (float) Math.sin(x);  
     }  