最佳化

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

最佳化粵拼zeoi3 gaai1 faa3英文optimization),全名數學最佳化mathematical optimization),係應用數學嘅一個分支,研究點樣喺特定情況下將一個特定嘅函數輸出或者變數有咁大得咁大(最大化)或者有咁細得咁細(最小化)。

方法[編輯]

爬山演算法[編輯]

內文:爬山演算法

爬山演算法(hill climbing)係一種常用嚟做最佳化嘅演算法:想像一個統計模型,有兩個參數,,而家用某個指標 量度個統計模型嘅表現,而呢個指標係數值愈細代表個模型愈理想嘅,例如係個模型嘅犯錯率(睇下圖)。家陣 經已有咗數值,所以個模型喺上圖入面有個座標位置,而個爬山演算法可以喺每一步噉做:

  1. 加減 嘅數值嚟改變個模型,即係個模型有 4()個前進方向;
  2. 計四個數值 ,當中 係移去第 個方向會得到嘅 值;
  3. 按「揀 值最小化嘅方向」呢條法則嚟改變 嘅數值;
  4. 重複,直至結束條件達到為止。

如果順利,個模型嘅 值會慢慢變到愈嚟愈細(接近理想數值),不過原則上,呢個最後嘅答案值唔保證會係理想數值-可能喺睇到嘅空間外有更低嘅可能 值,但呢個演算法唔會能夠保證將個模型帶到去嗰個數值-所以係一個近似演算法[1]。多個兩個參數嘅情況可以用同一道理想像。

爬山演算法嘅圖解;X 軸同 Y 軸係個模型嗰兩個參數,Z 軸(上下)表示一個量度模型表現嘅指標;演算法嘅目標係要將 最小化。

梯度下降法[編輯]

內文:梯度下降法

梯度下降法(gradient descent)係另一種常用嚟做最佳化嘅演算法。梯度下降法同爬山演算法相似,分別在於梯度下降法用嘅係斜率:喺每一步當中,一個梯度下降法啲參數移去邊一面唔係最決於邊一面嘅 數值低啲,而係取決於邊一面嘅 值嘅斜率高啲,諗住如果某一面嘅 數值跌得快,移去過一面就會最快噉令 數值下降[2]梯度上升法(gradient ascent)係指用同樣嘅手法搵最大值。以下係用 Python 寫嘅一段梯度下降法碼:

next_x = 6  # We start the search at x=6
gamma = 0.01  # Step size multiplier
precision = 0.00001  # Desired precision of result
max_iters = 10000  # Maximum number of iterations

# Derivative function
def df(x):
    return 4 * x ** 3 - 9 * x ** 2


for _ in range(max_iters):
    current_x = next_x
    next_x = current_x - gamma * df(current_x) # 睇吓個斜率係點。

    step = next_x - current_x
    if abs(step) <= precision:
        break

print("Minimum at ", next_x)

# The output for the above will be something like
# "Minimum at 2.2499646074278457"

模擬退火[編輯]

內文:模擬退火

模擬退火(simulated annealing):爬山演算法嘅一個變種;喺每步當中,最簡單嘅模擬退火演算法會考慮周圍嘅可能 值嘅 值,foreach 呢啲 值,將佢個 ±s,當中 s 係一個隨機俾嘅數值(溫度值),然後個演算法會再按邊個 嘅(±s 後) 數值比較接近理想數值,決定參數要變成邊個可能 值-噉做嘅話,個演算法唔會咁易企喺一個地區性最細或者地區性最大嗰度唔郁,但因為 比較近理想數值嘅 會比較大機會被選中,所以經過好多步之後,個演算法最後得出嗰個 值好有可能會係 值理想嘅[3]。一段用模擬退火嘅虛擬碼如下[4]

 Input:
   ProblemSize,
   iteration, // 重複幾多次
   max_temp, // 最大溫度值
 Output:
   S_best // 最佳嘅參數值
 
 Initialize:
   S_current = CreateInitialSolution(ProblemSize); // 將現時參數值設做隨機數值。
   S_best = S_current; // 暫時當最佳參數值係現時數值。
 
 for (i = 1 to iteration)
   S_i = CreateNeighborSolution(S_current); // 搵 S_current 周圍嘅參數值。
   current_temp = CalculateTemperature(i, max_temp); //「現時溫度」由 i 同 max_temp 話事。
   if Cost(S_i) < Cost(S_current) // 如果 S_i 嘅指標值靚過 S_current 嘅...
     S_current = S_i;
     if Cost(S_i) < Cost(S_best) // 如果 S_i 嘅指標值靚過 S_best 嘅...
       S_best = S_i;
     end
   else if (Exp[((Cost(S_current) - Cost(S_i)) / current_temp]) > rand()
   // 當中 rand() 係一個隨機產生嘅數值;隨住 current_temp 變細,呢個 elseif 發生嘅機會率會愈嚟愈細。
     S_current = S_i;
 end
 
 return S_best; // 最後就將 S_best 俾出嚟做輸出。
模擬退火嘅一個示範;Y 軸係需要最大化嗰個指標,X 軸係參數,隨住溫度值慢慢下降,參數值漸趨穩定。幅圖有好多地區性最大,所以用單純嘅爬山演算法好可能會搞唔掂。

睇埋[編輯]

參攷文獻[編輯]

  1. Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 111-114.
  2. Hill Climbing Algorithms (and gradient descent variants) IRL.
  3. Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680.
  4. Simulated Annealing 互聯網檔案館歸檔,歸檔日期2019年10月30號,.. Clever Algorithms: Nature-Inspired Programming Recipes.

出面網頁[編輯]

  • "Decision Tree for Optimization Software". Links to optimization source codes
  • "Global optimization".
  • "EE364a: Convex Optimization I". Course from Stanford University.
  • Varoquaux, Gaël. "Mathematical Optimization: Finding Minima of Functions".