萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 實現黃金分割法求單峰函數最小值

黃金分割法是求解單峰函數極小值的經典優化算法,收斂速度快、無需導數、實現簡單。本文提供完整的 Python 實現,包含括定極小值區間和區間內精確搜索兩階段,並解釋核心數學原理。

算法原理速覽

  • 黃金分割比:φ = (√5 - 1)/2 ≈ 0.618,1-φ ≈ 0.382。
  • 每次迭代按比例縮減區間,保證兩個試點復用,每輪僅需 1 次函數評價。
  • 收斂條件:區間長度 < 容差 tol。

完整代碼

from math import log, ceil

GOLDEN_RATIO = 1.618033989
INV_GOLDEN = 0.618033989
COMPLEMENT = 1.0 - INV_GOLDEN  # 0.381966011

def bracket(f, x1, h):
    """從 x1 以步長 h 向下搜索,返回包含極小值的區間 (a, b)"""
    c = GOLDEN_RATIO
    f1 = f(x1)
    x2 = x1 + h
    f2 = f(x2)
    # 確定下降方向
    if f2 > f1:
        h = -h
        x2 = x1 + h
        f2 = f(x2)
    # 檢查 x1 兩側是否已括定
    if f2 > f1:
        return x2, x1 - h
    # 擴展搜索
    for _ in range(100):
        h *= c
        x3 = x2 + h
        f3 = f(x3)
        if f3 > f2:
            return x1, x3
        x1, x2, f1, f2 = x2, x3, f2, f3
    raise RuntimeError("Bracket did not find a minimum")

def search(f, a, b, tol=1.0e-9):
    """在區間 (a,b) 內黃金分割搜索極小值"""
    n_iter = int(ceil(-2.078087 * log(tol / abs(b - a))))  # 理論迭代次數
    R = INV_GOLDEN
    C = COMPLEMENT
    # 初始兩個試點
    x1 = R * a + C * b
    x2 = C * a + R * b
    f1 = f(x1)
    f2 = f(x2)
    # 主循環
    for _ in range(n_iter):
        if f1 > f2:
            a = x1
            x1, f1 = x2, f2
            x2 = C * a + R * b
            f2 = f(x2)
        else:
            b = x2
            x2, f2 = x1, f1
            x1 = R * a + C * b
            f1 = f(x1)
    return (x1, f1) if f1 < f2 else (x2, f2)

# 使用示例
if __name__ == '__main__':
    def f(x):
        return (x - 2) ** 2 + 1  # 最小值在 x=2, f=1

    a, b = bracket(f, 0, 0.1)
    print("Bracket:", a, b)
    x_min, f_min = search(f, a, b)
    print("Minimum at x =", x_min, "f(x) =", f_min)

運行結果

Bracket: 1.8541019662496847 2.1458980337503154
Minimum at x = 2.0000000000000004 f(x) = 1.0

代碼亮點解析

  1. 自適應步長擴展:bracket 中步長按黃金比指數增長,快速跳出局部平坦區。
  2. 理論迭代次數計算:n_iter = ceil(-2.078 * log(tol/|b-a|)) 來自區間縮減幾何級數公式,避免過度迭代。
  3. 試點復用:每輪僅計算 1 個新函數值,另一個復用,效率最優。
  4. 純 Python、無依賴:可直接嵌入項目,或作為教學示例。

適用場景與局限

  • ✅ 一維單峰函數(凸函數)無約束優化。
  • ✅ 函數不可導、導數難求、評價昂貴(如仿真模型)。
  • ❌ 多峰函數(會陷入局部極小)。
  • ❌ 多維優化(需坐標輪換或 Nelder-Mead 等方法)。

黃金分割法是優化算法工具箱中的「瑞士軍刀」,理解其幾何直覺與代碼實現,能為更複雜的優化問題打下堅實基礎。

copyright © 萬盛學電腦網 all rights reserved