最优化——线搜索-斐波那契数列法

150 阅读 0 评论 99 点赞

我是靠谱客的博主小巧白羊，这篇文章主要介绍最优化——线搜索-斐波那契数列法，现在分享给大家，希望可以做个参考。

斐波那契数列法

斐波那契数列法与二分法相比没有太大的区别，只是nuk与lambdak的更新方式不一样，如下。
在这里插入图片描述

其中F为斐波那契数列，k为迭代次数，n为数组大小。

Python代码：

复制代码

def FibonacciArray(size):
    fibonacciArray = [1,1]
    for i in range(2,size):
        fibonacciArray.append(fibonacciArray[i-1] + fibonacciArray[i-2])
    return fibonacciArray

fibonacciArray = FibonacciArray(50)
def FibonacciMethod(a0, b0,):
    epsilon = 0.0001
    ak = a0
    bk = b0
    k = 0
    n = len(fibonacciArray) - 1
    while True:
        if bk -ak < epsilon:
            xstar = (bk + ak) / 2
            fstar = calFx(xstar)
            return xstar, fstar
        else:
            k = k + 1
            lambdaK = ak + (fibonacciArray[n - k - 1] / fibonacciArray[n - k + 1]) * (bk - ak)
            muK= ak + (fibonacciArray[n - k] / fibonacciArray[n - k + 1]) * (bk - ak)
            fLambdaK = calFx(lambdaK)
            fMuK = calFx(muK)
            if fLambdaK > fMuK:
                ak = lambdaK
                continue
            else:
                bk = muK
                continue
xstar, fstar = FibonacciMethod(-3,5)
print("FibonacciMethod xstar is %s" % xstar)
print("FibonacciMethod fstar is %s" % fstar)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def FibonacciArray(size):
    fibonacciArray = [1,1]
    for i in range(2,size):
        fibonacciArray.append(fibonacciArray[i-1] + fibonacciArray[i-2])
    return fibonacciArray

fibonacciArray = FibonacciArray(50)
def FibonacciMethod(a0, b0,):
    epsilon = 0.0001
    ak = a0
    bk = b0
    k = 0
    n = len(fibonacciArray) - 1
    while True:
        if bk -ak < epsilon:
            xstar = (bk + ak) / 2
            fstar = calFx(xstar)
            return xstar, fstar
        else:
            k = k + 1
            lambdaK = ak + (fibonacciArray[n - k - 1] / fibonacciArray[n - k + 1]) * (bk - ak)
            muK= ak + (fibonacciArray[n - k] / fibonacciArray[n - k + 1]) * (bk - ak)
            fLambdaK = calFx(lambdaK)
            fMuK = calFx(muK)
            if fLambdaK > fMuK:
                ak = lambdaK
                continue
            else:
                bk = muK
                continue
xstar, fstar = FibonacciMethod(-3,5)
print("FibonacciMethod xstar is %s" % xstar)
print("FibonacciMethod fstar is %s" % fstar)