優化a演算法
㈠ 多目標優化演算法
多目標優化演算法如下:
一、多目標進化演算法(MOEA)
1、MOEA通過對種群X(t)執行選擇、交叉和變異等操作產生下一代種群X(t+1)。
2、在每一代進化過程中 ,首先將種群X(t)中的所有非劣解個體都復制到外部集A(t)中。
2、智能優化演算法:包括進化演算法(簡稱EA)、粒子群演算法(簡稱PSO)等。
兩者的區別:傳統優化技術一般每次能得到Pareo解集中的一個,而用智能演算法來求解,可以得到更多的Pareto解,這些解構成了一個最優解集,稱為Pareto最優解(任一個目標函數值的提高都必須以犧牲其他目標函數值為代價的解集)。
㈡ A*演算法的好處
其實A*演算法也是一種最好優先的演算法
只不過要加上一些約束條件罷了。由於在一些問題求解時,我們希望能夠求解出狀態空間搜索的最短路徑,也就是用最快的方法求解問題,A*就是干這種事情的!
我們先下個定義,如果一個估價函數可以找出最短的路徑,我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為:
f'(n) = g'(n) + h'(n)
這里,f'(n)是估價函數,g'(n)是起點到節點n的最短路徑值,h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的,所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n),但 g(n)>=g'(n)才可(大多數情況下都是滿足的,可以不用考慮),h(n)代替h'(n),但h(n)<=h'(n)才可(這一點特別的重要)。可以證明應用這樣的估價函數是可以找到最短路徑的,也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。
舉一個例子,其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數,h(n)=0,這種h(n)肯定小於h'(n),所以由前述可知廣度優先演算法是一種可採納的。實際也是。當然它是一種最臭的A*演算法。
再說一個問題,就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件,如果信息越多或約束條件越多則排除的節點就越多,估價函數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了,誰叫它的h(n)=0,一點啟發信息都沒有。但在游戲開發中由於實時性的問題,h(n)的信息越多,它的計算量就越大,耗費的時間就越多。就應該適當的減小h(n)的信息,即減小約束條件。但演算法的准確性就差了,這里就有一個平衡的問題。
㈢ 機器學習中有哪些重要的優化演算法
梯度下降是非常常用的優化演算法。作為機器學習的基礎知識,這是一個必須要掌握的演算法。藉助本文,讓我們來一起詳細了解一下這個演算法。
前言
本文的代碼可以到我的Github上獲取:
https://github.com/paulQuei/gradient_descent
本文的演算法示例通過Python語言實現,在實現中使用到了numpy和matplotlib。如果你不熟悉這兩個工具,請自行在網上搜索教程。
關於優化
大多數學習演算法都涉及某種形式的優化。優化指的是改變x以最小化或者最大化某個函數的任務。
我們通常以最小化指代大多數最優化問題。最大化可經由最小化來實現。
我們把要最小化或最大化的函數成為目標函數(objective function)或准則(criterion)。
我們通常使用一個上標*表示最小化或最大化函數的x值,記做這樣:
[x^* = arg; min; f(x)]
優化本身是一個非常大的話題。如果有興趣,可以通過《數值優化》和《運籌學》的書籍進行學習。
模型與假設函數
所有的模型都是錯誤的,但其中有些是有用的。– George Edward Pelham Box
模型是我們對要分析的數據的一種假設,它是為解決某個具體問題從老洞數據中學習到的,因此它是機器學習最核心的概念。
針對一個問題,通常有大量的模型可以選擇。
本文不會深入討論這方面的內容,關於各種模型請參閱機器學習的相關書籍。本文僅以最簡單的線性模型為基礎來討論梯度下降演算法。
這里我們先介紹一下在監督學習(supervised learning)中常見的三個符號:
m,描述訓練樣本的數量
x,描述輸入變數或特徵
y,描述輸出變數或者叫目標值
- 請注意,一個樣本笑或可能有很多的特徵,因此x和y通常是一個向量。不過在剛開始學習的時候,為了便於理解,你可以暫時理解為這就是一個具體的數值。
- 代價函數也叫損失函數。
- 不同的模型可能會用不同的損失函數。例如,logistic回歸的假設函數是這樣的:。其代價函數是這樣的:
對於一個函數,怎麼確定下行的方向?
每一步該往前走多遠?
有沒有可能停留在半山腰的平台上?
- 這里的下標i表示第i個參數。 上標k指的是第k步的計算結果,而非k次方。在能夠理解的基礎上,下文的公式中將省略上標k。
收斂是指函數的變化率很小。具體選擇多少合適需要根據具體的項目來確定。在演示項目中我們可以選擇0.01或者0.001這樣的值。不同的值將影響演算法的迭代次數,因為在梯度下降的最後,我們會越來越接近平坦的地方,這個時候函數的變化率也越來越小。如果選擇一個很小的值,將可能導致演算法迭代次數暴增。
公式中的 稱作步長,也稱作學習率(learning rate)。它決定了每一步往前走多遠,關於這個值我們會在下文中詳細講解。你可以暫時人為它是一個類似0.01或0.001的固定值。
在具體的項目,我們不會讓演算法無休止的運行下去,所以通常會設置一個迭代次數的最大上限。
我們隨機選擇了 都為10作為起點
設置最多迭代1000次
收斂的范圍設為0.001
學習步長設為0.01
如果樣本數量較小(例如小於等於2000),選擇BGD即可。
如果樣本數量很大,選擇 來進行MBGD,例如:64,128,256,512。
- 《深度學習》一書中是這樣描述的:「與其說是科學,這更像是一門藝術,我們應該謹慎地參考關於這個問題的大部分指導。」。
對於凸函數或者凹函數來說,不存在局部極值的問題。其局部極值一定是全局極值。
最近的一些研究表明,某些局部極值並沒有想像中的那麼糟糕,它們已經非常的接近全局極值所帶來的結果了。
Wikipeida: Gradient descent
Sebastian Ruder: An overview of gradient descent optimization algorithms
吳恩達:機器學習
吳恩達:深度學習
Peter Flach:機器學習
李宏毅 - ML Lecture 3-1: Gradient Descent
PDF: 李宏毅 - Gradient Descent
Intro to optimization in deep learning: Gradient Descent
Intro to optimization in deep learning: Momentum, RMSProp and Adam
Stochastic Gradient Descent – Mini-batch and more
劉建平Pinard - 梯度下降(Gradient Descent)小結
多元函數的偏導數、方向導數、梯度以及微分之間的關系思考
[Machine Learning] 梯度下降法的三種形式BGD、SGD以及MBGD
- 作者:阿Paul https://paul.pub/gradient-descent/
訓練集會包含很多的樣本,我們用 表示其中第i個樣本。
x是數據樣本的特徵,y是其目標值。例如,在預測房價的模型中,x是房子的各種信息,例如:面積,樓層,位置等等,y是房子的價格。在圖像識別的任務中,x是圖形的所有像素點數據,y是圖像中包含的目標對象。
我們是希望尋找一個函數,將x映射到y,這個函數要足夠的好,以至於能夠預測對應的y。由於歷史原因,這個函數叫做假設函數(hypothesis function)。
學習的過程如下圖所示。即:首先根據已有的數據(稱之為訓練集)訓練我們的演算法模型,然後根據模型的假設函數來進行新數據的預測。
線性模型(linear model)正如其名稱那樣:是希望通過一個直線的形式來描述模式。線性模型的假設函數如下所示:
[h_{ heta}(x) = heta_{0} + heta_{1} * x]
這個公式對於大家來說應該都是非常簡單的。如果把它繪制出來,其實就是一條直線。
下圖是一個具體的例子,即: 的圖形:
在實際的機器學習工程中碰含伍,你會擁有大量的數據。這些數據會來自於某個數據源。它們存儲在csv文件中,或者以其他的形式打包。
但是本文作為演示使用,我們通過一些簡單的代碼自動生成了需要的數據。為了便於計算,演示的數據量也很小。
import numpy as np
max_x = 10
data_size = 10
theta_0 = 5
theta_1 = 2
def get_data:
x = np.linspace(1, max_x, data_size)
noise = np.random.normal(0, 0.2, len(x))
y = theta_0 + theta_1 * x + noise
return x, y
這段代碼很簡單,我們生成了x范圍是 [1, 10] 整數的10條數據。對應的y是以線性模型的形式計算得到,其函數是:。現實中的數據常常受到各種因素的干擾,所以對於y我們故意加上了一些高斯雜訊。因此最終的y值為比原先會有輕微的偏離。
最後我們的數據如下所示:
x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [6.66, 9.11, 11.08, 12.67, 15.12, 16.76, 18.75, 21.35, 22.77, 24.56]
我們可以把這10條數據繪制出來這樣就有一個直觀的了解了,如下圖所示:
雖然演示用的數據是我們通過公式計算得到的。但在實際的工程中,模型的參數是需要我們通過數據學習到的。所以下文我們假設我們不知道這里線性模式的兩個參數是什麼,而是通過演算法的形式求得。
最後再跟已知的參數進行對比以驗證我們的演算法是否正確。
有了上面的數據,我們可以嘗試畫一條直線來描述我們的模型。
例如,像下面這樣畫一條水平的直線:
很顯然,這條水平線離數據太遠了,非常的不匹配。
那我們可以再畫一條斜線。
我們初次畫的斜線可能也不貼切,它可能像下面這樣:
最後我們通過不斷嘗試,找到了最終最合適的那條,如下所示:
梯度下降演算法的計算過程,就和這種本能式的試探是類似的,它就是不停的迭代,一步步的接近最終的結果。
代價函數
上面我們嘗試了幾次通過一條直線來擬合(fitting)已有的數據。
二維平面上的一條直線可以通過兩個參數唯一的確定,兩個參數的確定也即模型的確定。那如何描述模型與數據的擬合程度呢?答案就是代價函數。
代價函數(cost function)描述了學習到的模型與實際結果的偏差程度。以上面的三幅圖為例,最後一幅圖中的紅線相比第一條水平的綠線,其偏離程度(代價)應該是更小的。
很顯然,我們希望我們的假設函數與數據盡可能的貼近,也就是說:希望代價函數的結果盡可能的小。這就涉及到結果的優化,而梯度下降就是尋找最小值的方法之一。
對於每一個樣本,假設函數會依據計算出一個估算值,我們常常用來表示。即 。
很自然的,我們會想到,通過下面這個公式來描述我們的模型與實際值的偏差程度:
[(h_ heta(x^i) - y^i)^2 = (widehat{y}^{i} - y^i)^2 = ( heta_{0} + heta_{1} * x^{i} - y^{i})^2]
請注意, 是實際數據的值, 是我們的模型的估算值。前者對應了上圖中的離散點的y坐標,後者對應了離散點在直線上投影點的y坐標。
每一條數據都會存在一個偏差值,而代價函數就是對所有樣本的偏差求平均值,其計算公式如下所示:
[L( heta) = frac {1}{m} sum_{i=1}^{m}(h_ heta(x^i) - y^i)^2 = frac {1}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i})^2]
當損失函數的結果越小,則意味著通過我們的假設函數估算出的結果與真實值越接近。這也就是為什麼我們要最小化損失函數的原因。
藉助上面這個公式,我們可以寫一個函數來實現代價函數:
def cost_function(x, y, t0, t1):
cost_sum = 0
for i in range(len(x)):
cost_item = np.power(t0 + t1 * x[i] - y[i], 2)
cost_sum += cost_item
return cost_sum / len(x)
這個函數的代碼應該不用多做解釋,它就是根據上面的完成計算。
我們可以嘗試選取不同的 和 組合來計算代價函數的值,然後將結果繪制出來:
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
theta_0 = 5
theta_1 = 2
def draw_cost(x, y):
fig = plt.figure(figsize=(10, 8))
ax = fig.gca(projection='3d')
scatter_count = 100
radius = 1
t0_range = np.linspace(theta_0 - radius, theta_0 + radius, scatter_count)
t1_range = np.linspace(theta_1 - radius, theta_1 + radius, scatter_count)
cost = np.zeros((len(t0_range), len(t1_range)))
for a in range(len(t0_range)):
for b in range(len(t1_range)):
cost[a][b] = cost_function(x, y, t0_range[a], t1_range[b])
t0, t1 = np.meshgrid(t0_range, t1_range)
ax.set_xlabel('theta_0')
ax.set_ylabel('theta_1')
ax.plot_surface(t0, t1, cost, cmap=cm.hsv)
在這段代碼中,我們對 和 各自指定了一個范圍進行100次的采樣,然後以不同的 組合對來計算代價函數的值。
如果我們將所有點的代價函數值繪制出來,其結果如下圖所示:
從這個圖形中我們可以看出,當 越接近 [5, 2]時其結果(偏差)越小。相反,離得越遠,結果越大。
直觀解釋
從上面這幅圖中我們可以看出,代價函數在不同的位置結果大小不同。
從三維的角度來看,這就和地面的高低起伏一樣。最高的地方就好像是山頂。
而我們的目標就是:從任意一點作為起點,能夠快速尋找到一條路徑並以此到達圖形最低點(代價值最小)的位置。
而梯度下降的演算法過程就和我們從山頂想要快速下山的做法是一樣的。
在生活中,我們很自然會想到沿著最陡峭的路往下行是下山速度最快的。如下面這幅圖所示:
針對這幅圖,細心的讀者可能很快就會有很多的疑問,例如:
這些問題也就是本文接下來要討論的內容。
演算法描述
梯度下降演算法最開始的一點就是需要確定下降的方向,即:梯度。
我們常常用 來表示梯度。
對於一個二維空間的曲線來說,梯度就是其切線的方向。如下圖所示:
而對於更高維空間的函數來說,梯度由所有變數的偏導數決定。
其表達式如下所示:
[ abla f({ heta}) = ( frac{partial f({ heta})}{partial heta_1} , frac{partial f({ heta})}{partial heta_2} , ... , frac{partial f({ heta})}{partial heta_n} )]
在機器學習中,我們主要是用梯度下降演算法來最小化代價函數,記做:
[ heta ^* = arg min L( heta)]
其中,L是代價函數,是參數。
梯度下降演算法的主體邏輯很簡單,就是沿著梯度的方向一直下降,直到參數收斂為止。
記做:
[ heta ^{k + 1}_i = heta^{k}_i - lambda abla f( heta^{k})]
這里有幾點需要說明:
線性回歸的梯度下降
有了上面的知識,我們可以回到線性模型代價函數的梯度下降演算法實現了。
首先,根據代價函數我們可以得到梯度向量如下:
[ abla f({ heta}) = (frac{partial L( heta)}{ partial heta_{0}}, frac{ partial L( heta)}{ partial heta_{1}}) = (frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) , frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i})]
接著,將每個偏導數帶入迭代的公式中,得到:
[ heta_{0} := heta_{0} - lambda frac{partial L( heta_{0})}{ partial heta_{0}} = heta_{0} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) heta_{1} := heta_{1} - lambda frac{partial L( heta_{1})}{ partial heta_{1}} = heta_{1} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i}]
由此就可以通過代碼實現我們的梯度下降演算法了,演算法邏輯並不復雜:
learning_rate = 0.01
def gradient_descent(x, y):
t0 = 10
t1 = 10
delta = 0.001
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
t0_ = t0 - 2 * learning_rate * sum1 / len(x)
t1_ = t1 - 2 * learning_rate * sum2 / len(x)
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1
這段代碼說明如下:
如果我們將演算法迭代過程中求得的線性模式繪制出來,可以得到下面這幅動態圖:
最後演算法得到的結果如下:
Times: 657, gradient: [5.196562662718697, 1.952931052920264]
Times: 658, gradient: [5.195558390180733, 1.9530753071808193]
Times: 659, gradient: [5.194558335124868, 1.9532189556399233]
Times: 660, gradient: [5.193562479839619, 1.9533620008416623]
Gradient descent finish
從輸出中可以看出,演算法迭代了660次就收斂了。這時的結果[5.193562479839619, 1.9533620008416623],這已經比較接近目標值 [5, 2]了。如果需要更高的精度,可以將delta的值調的更小,當然,此時會需要更多的迭代次數。
高維擴展
雖然我們舉的例子是二維的,但是對於更高維的情況也是類似的。同樣是根據迭代的公式進行運算即可:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=1}^{m}(h_ heta(x^{k})-y^k)x_i^k]
這里的下標i表示第i個參數,上標k表示第k個數據。
梯度下降家族BGD
在上面的內容中我們看到,演算法的每一次迭代都需要把所有樣本進行遍歷處理。這種做法稱為之Batch Gradient Descent,簡稱BGD。作為演示示例只有10條數據,這是沒有問題的。
但在實際的項目中,數據集的數量可能是幾百萬幾千萬條,這時候每一步迭代的計算量就會非常的大了。
於是就有了下面兩個變種。
SGD
Stochastic Gradient Descent,簡稱SGD,這種演算法是每次從樣本集中僅僅選擇一個樣本來進行計算。很顯然,這樣做演算法在每一步的計算量一下就少了很多。
其演算法公式如下:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - lambda(h_ heta(x^k)-y^k)x_i^k]
當然,減少演算法計算量也是有代價的,那就是:演算法結果會強依賴於隨機取到的數據情況,這可能會導致演算法的最終結果不太令人滿意。
MBGD
以上兩種做法其實是兩個極端,一個是每次用到了所有數據,另一個是每次只用一個數據。
我們自然就會想到兩者取其中的方法:每次選擇一小部分數據進行迭代。這樣既避免了數據集過大導致每次迭代計算量過大的問題,也避免了單個數據對演算法的影響。
這種演算法稱之為Mini-batch Gradient Descent,簡稱MBGD。
其演算法公式如下:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=a}^{a + b}(h_ heta(x^k)-y^k)x_i^k]
當然,我們可以認為SGD是Mini-batch為1的特例。
針對上面提到的演算法變種,該如何選擇呢?
下面是Andrew Ng給出的建議:
下表是 Optimization for Deep Learning 中對三種演算法的對比
方法准確性更新速度內存佔用在線學習BGD好慢高否SGD好(with annealing)快低是MBGD好中等中等是
演算法優化
式7是演算法的基本形式,在這個基礎上有很多人進行了更多的研究。接下來我們介紹幾種梯度下降演算法的優化方法。
Momentum
Momentum是動量的意思。這個演算法的思想就是藉助了動力學的模型:每次演算法的迭代會使用到上一次的速度作為依據。
演算法的公式如下:
[v^t = gamma v^{t - 1} + lambda abla f( heta) heta = heta - v_t]
對比式7可以看出,這個演算法的主要區別就是引入了,並且,每個時刻的受前一個時刻的影響。
從形式上看,動量演算法引入了變數 v 充當速度角色——它代表參數在參數空間移動的方向和速率。速度被設為負梯度的指數衰減平均。名稱動量來自物理類比,根據牛頓運動定律,負梯度是移動參數空間中粒子的力。動量在物理學上定義為質量乘以速度。在動量學習演算法中,我們假設是單位質量,因此速度向量 v 也可以看作是粒子的動量。
對於可以取值0,而是一個常量,設為0.9是一個比較好的選擇。
下圖是momentum演算法的效果對比:
對原來的演算法稍加修改就可以增加動量效果:
def gradient_descent_with_momentum(x, y):
t0 = 10
t1 = 10
delta = 0.001
v0 = 0
v1 = 0
gamma = 0.9
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
v0 = gamma * v0 + 2 * learning_rate * sum1 / len(x)
v1 = gamma * v1 + 2 * learning_rate * sum2 / len(x)
t0_ = t0 - v0
t1_ = t1 - v1
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1
以下是該演算法的輸出:
Times: 125, gradient: [4.955453758569991, 2.000005017897775]
Times: 126, gradient: [4.955309381126545, 1.9956928964532015]
Times: 127, gradient: [4.9542964317327005, 1.9855674828684156]
Times: 128, gradient: [4.9536358220657, 1.9781180992510465]
Times: 129, gradient: [4.95412496254411, 1.9788858350530971]
Gradient descent finish
從結果可以看出,改進的演算法只用了129次迭代就收斂了。速度比原來660次快了很多。
同樣的,我們可以把演算法計算的過程做成動態圖:
對比原始的演算法過程可以看出,改進演算法最大的區別是:在尋找目標值時會在最終結果上下跳動,但是越往後跳動的幅度越小,這也就是動量所產生的效果。
Learning Rate 優化
至此,你可能還是好奇該如何設定學習率的值。
事實上,這個值的選取需要一定的經驗或者反復嘗試才能確定。
關鍵在於,這個值的選取不能過大也不能過小。
如果這個值過小,會導致每一次迭代的步長很小,其結果就是演算法需要迭代非常多的次數。
那麼,如果這個值過大會怎麼樣呢?其結果就是:演算法可能在結果的周圍來回震盪,卻落不到目標的點上。下面這幅圖描述了這個現象:
事實上,學習率的取值未必一定要是一個常數,關於這個值的設定有很多的研究。
下面是比較常見的一些改進演算法。
AdaGrad
AdaGrad是Adaptive Gradient的簡寫,該演算法會為每個參數設定不同的學習率。它使用歷史梯度的平方和作為基礎來進行計算。
其演算法公式如下:
[ heta_i = heta_i - frac{lambda}{sqrt{G_t + epsilon}} abla f( heta)]
對比式7,這里的改動就在於分號下面的根號。
根號中有兩個符號,第二個符號比較好理解,它就是為了避免除0而人為引入的一個很小的常數,例如可以設為:0.001。
第一個符號的表達式展開如下:
[G_t = sum_{i = 1}^{t} abla f( heta){i} abla f( heta){i}^{T}]
這個值其實是歷史中每次梯度的平方的累加和。
AdaGrad演算法能夠在訓練中自動的對learning rate進行調整,對於出現頻率較低參數採用較大的學習率;相反,對於出現頻率較高的參數採用較小的學習率。因此,Adagrad非常適合處理稀疏數據。
但該演算法的缺點是它可能導致學習率非常小以至於演算法收斂非常的慢。
關於這個演算法的直觀解釋可以看李宏毅教授的視頻課程:ML Lecture 3-1: Gradient Descent。
RMSProp
RMS是Root Mean Square的簡寫。RMSProp是AI教父Geoff Hinton提出的一種自適應學習率方法。AdaGrad會累加之前所有的梯度平方,而RMSProp僅僅是計算對應的平均值,因此可緩解Adagrad演算法學習率下降較快的問題。
該演算法的公式如下:
[E[ abla f( heta_{i})^2]^{t} = gamma E[ abla f( heta_{i})^2]^{t - 1} + (1-gamma)( abla f( heta_{i})^{t})^{2} heta_i = heta_i - frac{lambda}{sqrt{E[g^2]^{t+1} + epsilon}} abla f( heta_{i})]
類似的,是為了避免除0而引入。 是衰退參數,通常設為0.9。
這里的 是t時刻梯度平方的平均值。
Adam
Adam是Adaptive Moment Estimation的簡寫。它利用梯度的一階矩估計和二階矩估計動態調整每個參數的學習率。
Adam的優點主要在於經過偏置校正後,每一次迭代學習率都有個確定范圍,使得參數比較平穩。
該演算法公式如下:
[m^{t} = eta_{1} m^{t-1} + (1-eta_{1}) abla f( heta) v^{t} = eta_{2} v^{t-1} + (1-eta_{2}) abla f( heta)^2 widehat{m}^{t} = frac{m^{t}}{1 - eta^{t}_1} widehat{v}^{t} = frac{v^{t}}{1 - eta^{t}_2} heta = heta - frac{lambda}{sqrt{widehat{v}^{t}} + epsilon}widehat{m}^{t}]
,分別是對梯度的一階矩估計和二階矩估計。, 是對,的校正,這樣可以近似為對期望的無偏估計。
Adam演算法的提出者建議 默認值為0.9,默認值為0.999,默認值為 。
在實際應用中 ,Adam較為常用,它可以比較快地得到一個預估結果。
優化小結
這里我們列舉了幾種優化演算法。它們很難說哪種最好,不同的演算法適合於不同的場景。在實際的工程中,可能需要逐個嘗試一下才能確定選擇哪一個,這個過程也是目前現階段AI項目要經歷的工序之一。
實際上,該方面的研究遠不止於此,如果有興趣,可以繼續閱讀 《Sebastian Ruder: An overview of gradient descent optimization algorithms》 這篇論文或者 Optimization for Deep Learning 這個Slides進行更多的研究。
由於篇幅所限,這里不再繼續展開了。
演算法限制
梯度下降演算法存在一定的限制。首先,它要求函數必須是可微分的,對於不可微的函數,無法使用這種方法。
除此之外,在某些情況下,使用梯度下降演算法在接近極值點的時候可能收斂速度很慢,或者產生Z字形的震盪。這一點需要通過調整學習率來迴避。
另外,梯度下降還會遇到下面兩類問題。
局部最小值
局部最小值(Local Minima)指的是,我們找到的最小值僅僅是一個區域內的最小值,而並非全局的。由於演算法的起點是隨意取的,以下面這個圖形為例,我們很容易落到局部最小值的點裡面。
這就是好像你從上頂往下走,你第一次走到的平台未必是山腳,它有可能只是半山腰的一個平台的而已。
演算法的起點決定了演算法收斂的速度以及是否會落到局部最小值上。
壞消息是,目前似乎沒有特別好的方法來確定選取那個點作為起點是比較好的,這就有一點看運氣的成分了。多次嘗試不同的隨機點或許是一個比較好的方法,這也就是為什麼做演算法的優化這項工作是特別消耗時間的了。
但好消息是:
鞍點
除了Local Minima,在梯度下降的過程中,還有可能遇到另外一種情況,即:鞍點(Saddle Point)。鞍點指的是我們找到點某個點確實是梯度為0,但它卻不是函數的極值,它的周圍既有比它小的值,也有比它大的值。這就好像馬鞍一樣。
如下圖所示:
多類隨機函數表現出以下性質:在低維空間中,局部極值很普遍。但在高維空間中,局部極值比較少見,而鞍點則很常見。
不過對於鞍點,可以通過數學方法Hessian矩陣來確定。關於這點,這里就不再展開了,有興趣的讀者可以以這里提供的幾個鏈接繼續探索。
參考資料與推薦讀物
㈣ A*演算法如何改進
十萬火急:此改進的模糊C-此函數實現遺傳演算法,用於模糊C-均值聚類 %% A=farm(:,Ser(1)); B=farm(:,Ser(2)); P0=unidrnd(M-1); a=[
㈤ A*演算法優化
A演算法是游戲中路徑搜索的常見演算法。Dijkstra是最短路徑的經典演算法,A演算法的思路基本上和Dijkstra演算法一致,在Dijkstra演算法的基礎上增加了啟發函數,也就是:
f(n) = g(n) + h(n)
其中,n是路徑上某一點,g(n)是從出發點到該點的cost,h(n)是關於該點的啟發函數,通常是對從該點到目標花費的一個估計,例如到目標的直線距離或者曼哈頓距離。 A演算法每次選擇f(n)最小的點,然後更新所有g(n)。
如果你明白Dijkstra演算法,那麼在這里h(n) = 0 的話,A演算法就和Dijkstra演算法一樣了。
本文不詳細講解A演算法,需要詳細了解A演算法的具體過程的,參見以下兩篇文章:
理解A*演算法的具體過程
A*演算法詳解
A*演算法優化的關鍵在於h(n)的選擇。 一個啟發函數h(n)被稱為admissible的,是指h(n)的估計,不會超過節點N到目標的實際花費。
如果h(x)滿足以下條件,h(x)被稱為單調的(monotone, or consistent)。 對於任意一條邊(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是(x,y)的長度
如果滿足這個條件,就意味著沒有任何節點需要被處理多次,也就是說,在Dijkstra演算法中,新加入一個節點會導致已添加節點中cost降低的情況不會存在,也就不需要去更新已添加節點(稱為close set)。
如果一個啟發函數是單調的,那麼該啟發函數一定是admissible的。如果該啟發函數是admissible的,那麼可以證明A*在同類演算法中搜尋到最短的路徑。
問題出在這里:如果我們更在意的是搜索的時間空間花費,而不是最優結果,那麼A*演算法就有優化空間。所以我們放鬆要求,修改我們的啟發函數,使得我們搜尋到的路徑不會比最佳路徑差太多,就是優化演算法,稱為ε-admissible演算法。
有多種ε-admissible演算法,在此只舉例最簡單直接的一種: 加權A*(靜態加權)演算法。
假如ha(n)是一個admissible的啟發函數,我們選取新的啟發函數hw(n) = ε ha(n),其中ε>1 作為啟發函數。就可以在某種程度上進行優化。 下圖1是使用ha(n)作為啟發式演算法,下圖2是使用hw(n)作為啟發式演算法,其中ε取5.
圖1:ha(x)作為啟發演算法
圖2:hn(x)作為啟發演算法
可以看出,ha(n)可以找到最小路徑,但是多了許多無用的搜索;而hw(n)找到的不是最優路徑,但是減少了大量無用搜索。
其他的優化演算法思路類似都是在於啟發函數的選擇。詳見參考文獻。
參考文獻:
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic
㈥ IA優化演算法是什麼
IA優化演算法指的是免疫演算法是模仿生物免疫機制,結合基因的進化機理,人工構造出的一種新型智能優化演算法。它具有一般免疫系統的特徵,採用群體搜索策略,通過迭代計算,最終以較大的概率得到問題的最優解。
相比較於其他演算法,免疫演算法利用自身產生多樣性和維持機制的特點,保證了種群的多樣性,克服了一般尋優過程(特別是多峰值的尋優過程)中不可避免的「早熟」問題,可以求得全局最優解。免疫演算法具有自適應性、隨機性、並行性、全局收斂性、種群多樣性等優點。
免疫演算法主要模塊:
抗原識別與初始抗體產生。根據待優化問題的特點設計合適的抗體編碼規則,並在此編碼規則下利用問題的先驗知識產生初始抗體種群。
抗體評價。對抗體的質量進行評價,評價准則主要為抗體親和度和個體濃度,評價得出的優質抗體將進行進化免疫操作,劣質抗體將會被更新。
免疫操作。利用免疫選擇、克隆、變異、克隆抑制、種群刷新等運算元模擬生物免疫應答中的各種免疫操作,形成基於生物免疫系統克隆選擇原理的進化規則和方法,實現對各種最優化問題的尋優搜索。
㈦ A*演算法介紹
姓名:車文揚 學號:16020199006
【嵌牛導讀】:A*演算法的逐步詳解
【嵌牛鼻子】:啟發式演算法
【嵌牛提問】:A*演算法的原理是什麼?
【嵌牛正文】:
A*演算法
路徑規劃是指的是機器人的最優路徑規劃問題,即依據某個或某些優化准則(如工作代價最小、行走路徑最短、行走時間最短等),在工作空間中找到一個從起始狀態到目標狀態能避開障礙物的最優路徑。機器人的路徑規劃應用場景極豐富,最常見如游戲中NPC及控制角色的位置移動,網路地圖等導航問題,小到家庭掃地機器人、無人機大到各公司正爭相開拓的無人駕駛汽車等。
目前路徑規劃演算法分為:
A*演算法原理:
在計算機科學中,A*演算法作為Dijkstra演算法的擴展,因其高效性而被廣泛應用於尋路及圖的遍歷,如星際爭霸等游戲中就大量使用。在理解演算法前,我們需要知道幾個概念:
搜索區域(The Search Area):圖中的搜索區域被劃分為了簡單的二維數組,數組每個元素對應一個小方格,當然我們也可以將區域等分成是五角星,矩形等,通常將一個單位的中心點稱之為搜索區域節點(Node)。
開放列表(Open List):我們將路徑規劃過程中待檢測的節點存放於Open List中,而已檢測過的格子則存放於Close List中。
父節點(parent):在路徑規劃中用於回溯的節點,開發時可考慮為雙向鏈表結構中的父結點指針。
路徑排序(Path Sorting):具體往哪個節點移動由以下公式確定:F(n) = G + H 。G代表的是從初始位置A沿著已生成的路徑到指定待檢測格子的移動開銷。H指定待測格子到目標節點B的估計移動開銷。
啟發函數(Heuristics Function):H為啟發函數,也被認為是一種試探,由於在找到唯一路徑前,我們不確定在前面會出現什麼障礙物,因此用了一種計算H的演算法,具體根據實際場景決定。在我們簡化的模型中,H採用的是傳統的曼哈頓距離(Manhattan Distance),也就是橫縱向走的距離之和。
如下圖所示,綠色方塊為機器人起始位置A,紅色方塊為目標位置B,藍色為障礙物。
我們把要搜尋的區域劃分成了正方形的格子。這是尋路的第一步,簡化搜索區域。這個特殊的方法把我們的搜索區域簡化為了2 維數組。數組的每一項代表一個格子,它的狀態就是可走(walkalbe)或不可走(unwalkable) 。現用A*演算法尋找出一條自A到B的最短路徑,每個方格的邊長為10,即垂直水平方向移動開銷為10。因此沿對角移動開銷約等於14。具體步驟如下:
從起點 A 開始,把它加入到一個由方格組成的open list(開放列表) 中,這個open list像是一個購物清單。Open list里的格子是可能會是沿途經過的,也有可能不經過。因此可以將其看成一個待檢查的列表。查看與A相鄰的8個方格 ,把其中可走的 (walkable) 或可到達的(reachable) 方格加入到open list中。並把起點 A 設置為這些方格的父節點 (parent node) 。然後把 A 從open list中移除,加入到close list(封閉列表) 中,close list中的每個方格都是不需要再關注的。
如下圖所示,深綠色的方格為起點A,它的外框是亮藍色,表示該方格被加入到了close list 。與它相鄰的黑色方格是需要被檢查的,他們的外框是亮綠色。每個黑方格都有一個灰色的指針指向他們的父節點A。
下一步,我們需要從open list中選一個與起點A相鄰的方格。但是到底選擇哪個方格好呢?選F值最小的那個。我們看看下圖中的一些方格。在標有字母的方格中G = 10 。這是因為水平方向從起點到那裡只有一個方格的距離。與起點直接相鄰的上方,下方,左方的方格的G 值都是10 ,對角線的方格G 值都是14 。H值通過估算起點到終點( 紅色方格) 的Manhattan 距離得到,僅作橫向和縱向移動,並且忽略沿途的障礙。使用這種方式,起點右邊的方格到終點有3 個方格的距離,因此H = 30 。這個方格上方的方格到終點有4 個方格的距離( 注意只計算橫向和縱向距離) ,因此H = 40 。
比較open list中節點的F值後,發現起點A右側節點的F=40,值最小。選作當前處理節點,並將這個點從Open List刪除,移到Close List中。
對這個節點周圍的8個格子進行判斷,若是不可通過(比如牆,水,或是其他非法地形)或已經在Close List中,則忽略。否則執行以下步驟:
若當前處理節點的相鄰格子已經在Open List中,則檢查這條路徑是否更優,即計算經由當前處理節點到達那個方格是否具有更小的 G值。如果沒有,不做任何操作。相反,如果G值更小,則把那個方格的父節點設為當前處理節點 ( 我們選中的方格 ) ,然後重新計算那個方格的 F 值和 G 值。
若當前處理節點的相鄰格子不在Open List中,那麼把它加入,並將它的父節點設置為該節點。
按照上述規則我們繼續搜索,選擇起點右邊的方格作為當前處理節點。它的外框用藍線打亮,被放入了close list 中。然後我們檢查與它相鄰的方格。它右側的3個方格是牆壁,我們忽略。它左邊的方格是起點,在close list 中,我們也忽略。其他4個相鄰的方格均在open list 中,我們需要檢查經由當前節點到達那裡的路徑是否更好。我們看看上面的方格,它現在的G值為14 ,如果經由當前方格到達那裡,G值將會為20( 其中10為從起點到達當前方格的G值,此外還要加上從當前方格縱向移動到上面方格的G值10) ,因此這不是最優的路徑。看圖就會明白直接從起點沿對角線移動到那個方格比先橫向移動再縱向移動要好。
當把4個已經在open list 中的相鄰方格都檢查後,沒有發現經由當前節點的更好路徑,因此不做任何改變。接下來要選擇下一個待處理的節點。因此再次遍歷open list ,現在open list中只有7 個方格了,我們需要選擇F值最小的那個。這次有兩個方格的F值都是54,選哪個呢?沒什麼關系。從速度上考慮,選擇最後加入open list 的方格更快。因此選擇起點右下方的方格,如下圖所示。
接下來把起點右下角F值為54的方格作為當前處理節點,檢查其相鄰的方格。我們發現它右邊是牆(牆下面的一格也忽略掉,假定牆角不能直接穿越),忽略之。這樣還剩下 5 個相鄰的方格。當前方格下面的 2 個方格還沒有加入 open list ,所以把它們加入,同時把當前方格設為他們的父親。在剩下的 3 個方格中,有 2 個已經在 close list 中 ( 一個是起點,一個是當前方格上面的方格,外框被加亮的 ) ,我們忽略它們。最後一個方格,也就是當前方格左邊的方格,檢查經由當前方格到達那裡是否具有更小的 G 值。沒有,因此我們准備從 open list 中選擇下一個待處理的方格。
不斷重復這個過程,直到把終點也加入到了open list 中,此時如下圖所示。注意在起點下方2 格處的方格的父親已經與前面不同了。之前它的G值是28並且指向它右上方的方格。現在它的G 值為20 ,並且指向它正上方的方格。這是由於在尋路過程中的某處使用新路徑時G值更小,因此父節點被重新設置,G和F值被重新計算。
那麼我們怎樣得到實際路徑呢?很簡單,如下圖所示,從終點開始,沿著箭頭向父節點移動,直至回到起點,這就是你的路徑。
A*演算法總結:
1. 把起點加入 open list 。
2. 重復如下過程:
a. 遍歷open list ,查找F值最小的節點,把它作為當前要處理的節點,然後移到close list中
b. 對當前方格的 8 個相鄰方格一一進行檢查,如果它是不可抵達的或者它在close list中,忽略它。否則,做如下操作:
□ 如果它不在open list中,把它加入open list,並且把當前方格設置為它的父親
□ 如果它已經在open list中,檢查這條路徑 ( 即經由當前方格到達它那裡 ) 是否更近。如果更近,把它的父親設置為當前方格,並重新計算它的G和F值。如果你的open list是按F值排序的話,改變後你可能需要重新排序。
c. 遇到下面情況停止搜索:
□ 把終點加入到了 open list 中,此時路徑已經找到了,或者
□ 查找終點失敗,並且open list 是空的,此時沒有路徑。
3. 從終點開始,每個方格沿著父節點移動直至起點,形成路徑。
㈧ 如何利用矩陣對a*演算法進行優化
如果A確實能完全存入一級緩存,那麼把B按列分塊,一塊一塊乘就行了.
一般來講矩陣乘法並不是像你說的那樣做的,而要把A,B,C都分塊,對於每一級存貯器而言,應該至少分成5個部分來管理.比如說,A的某一塊常駐於這一級存貯,然後餘下的部分分為四塊:
(1)上一步已經運算完成的C塊——寫入低一級存貯
(2)下一步將參與運算的B塊——從低一級存貯讀入
(3),(4)正在參與運算的B和C塊
然後對於這一級存貯器上的小矩陣塊運算C=AB仍然按照同樣的管理方式遞交給上一級存貯來計算.一般來講A塊選得略小一點,具體的分配方式取決於運算和I/O的速度,盡量保持計算單元忙碌.
㈨ 優化演算法筆記(一)優化演算法的介紹
(以下描述,均不是學術用語,僅供大家快樂的閱讀)
我們常見常用的演算法有排序演算法,字元串遍歷演算法,尋路演算法等。這些演算法都是為了解決特定的問題而被提出。
演算法本質是一種按照固定步驟執行的過程。
優化演算法也是這樣一種過程,是一種根據概率按照固定步驟尋求問題的最優解的過程。與常見的排序演算法、尋路演算法不同的是,優化演算法不具備等冪性,是一種 概率演算法 。演算法不斷的 迭代 執行同一步驟直到結束,其流程如下圖。
等冪性即 對於同樣的輸入,輸出是相同的 。
比如圖1,對於給定的魚和給定的熊掌,我們在相同的條件下一定可以知道它們誰更重,當然,相同的條件是指魚和熊掌處於相同的重力作用下,且不用考慮水分流失的影響。在這些給定的條件下,我們(無論是誰)都將得出相同的結論,魚更重或者熊掌更重。我們可以認為,秤是一個等冪性的演算法(工具)。
現在把問題變一變,問魚與熊掌你更愛哪個,那麼現在,這個問題,每個人的答案可能不會一樣,魚與熊掌各有所愛。說明喜愛這個演算法不是一個等冪性演算法。當然你可能會問,哪個更重,和更喜歡哪個這兩個問題一個是客觀問題,一個是主觀問題,主觀問題沒有確切的答案的。當我們處理主觀問題時,也會將其轉換成客觀問題,比如給喜歡魚和喜歡熊掌的程度打個分,再去尋求答案,畢竟計算機沒有感情,只認0和1(量子計算機我不認識你)。
說完了等冪性,再來說什麼是概率演算法。簡單來說就是看臉、看人品、看運氣的演算法。
有一場考試,考試的內容全部取自課本,同時老師根據自己的經驗給同學們劃了重點,但是因為試卷並不是該老師所出,也會有考試內容不在重點之內,老師估計試卷中至少80%內容都在重點中。學霸和學渣參加了考試,學霸為了考滿分所以無視重點,學渣為了pass,因此只看了重點。這樣做的結果一定是score(學霸)>=score(學渣)。
當重點跟上圖一樣的時候,所有的內容都是重點的時候,學霸和學渣的學習策略變成了相同的策略,則score(學霸)=score(學渣)。但同時,學渣也要付出跟學霸相同的努力去學習這些內容,學渣心裡苦啊。
當課本如下圖時
學霸?學霸人呢,哪去了快來學習啊,不是說學習一時爽,一直學習一直爽嗎,快來啊,還等什麼。
這時,如果重點內容遠少於書本內容時,學渣的學習策略有了優勢——花費的時間和精力較少。但是同時,學渣的分數也是一個未知數,可能得到80分也可能拿到100分,分數完全取決於重點內容與題目的契合度,契合度越高,分數越高。對學渣來說,自己具體能考多少分無法由自己決定,但是好在能夠知道大概的分數范圍。
學霸的學習策略是一種遍歷性演算法,他會遍歷、通讀全部內容,以保證滿分。
學渣的學習策略則是一種概率演算法,他只會遍歷、學習重點內容,但至於這些重點是不是真重點他也不知道。
與遍歷演算法相比,概率演算法的結果具有不確定性,可能很好,也可能很差,但是會消耗更少的資源,比如時間(人生),空間(記憶)。概率演算法的最大優點就是 花費較少的代價來獲取最高的收益 ,在現實中體現於節省時間,使用很少的時間得到一個不與最優解相差較多的結果。
「莊子:吾生也有涯,而知也無涯;以有涯隨無涯,殆矣。」的意思是:人生是有限的,但知識是無限的(沒有邊界的),用有限的人生追求無限的知識,是必然失敗的。
生活中概率演算法(思想)的應用其實比較廣泛,只是我們很少去注意罷了。關於概率演算法還衍生出了一些有趣的理論,比如墨菲定律和倖存者偏差,此處不再詳述。
上面說到,優化演算法就是不停的執行同樣的策略、步驟直到結束。為什麼要這樣呢?因為優化演算法是一種概率演算法,執行一次操作就得到最優結果幾乎是不可能的,重復多次取得最優的概率也會增大。
栗子又來了,要從1-10這10個數中取出一個大於9的數,只取1次,達到要求的概率為10%,取2次,達到要求的概率為19%。
可以看出取到第10次時,達到要求的概率幾乎65%,取到100次時,達到要求的概率能接近100%。優化演算法就是這樣簡單粗暴的來求解問題的嗎?非也,這並不是一個恰當的例子,因為每次取數的操作之間是相互獨立的,第2次取數的結果不受第1次取數結果的影響,假設前99次都沒達到要求,那麼再取一次達到要求的概率跟取一次達到要求的概率相同。
優化演算法中,後一次的計算會依賴前一次的結果,以保證後一次的結果不會差於前一次的結果。這就不得不談到馬爾可夫鏈了。
由鐵組成的鏈叫做鐵鏈,同理可得,馬爾可夫鏈就是馬爾可夫組成的鏈。
言歸正傳, 馬爾可夫鏈(Markov Chain, MC) ,描述的是 狀態轉移的過程中,當前狀態轉移的概率只取決於上一步的狀態,與其他步的狀態無關 。簡單來說就是當前的結果只受上一步的結果的影響。每當我看到馬爾可夫鏈時,我都會陷入沉思,生活中、或者歷史中有太多太多與馬爾可夫鏈相似的東西。西歐封建等級制度中「附庸的附庸不是我的附庸」與「昨天的努力決定今天的生活,今天的努力決定明天的生活」,你的下一份工作的工資大多由你當前的工資決定,這些都與馬爾可夫鏈有異曲同工之處。
還是從1-10這10個數中取出一個大於9的數的這個例子。基於馬爾可夫鏈的概率演算法在取數時需要使當前取的數不小於上一次取的數。比如上次取到了3,那麼下次只能在3-10這幾個數中取,這樣一來,達到目標的概率應該會顯著提升。還是用數據說話。
取1次達到要求的概率仍然是
取2次內達到要求的概率為
取3次內達到要求的概率為
取4次內……太麻煩了算了不算了
可以看出基於馬爾可夫鏈來取數時,3次內能達到要求的概率與不用馬爾可夫鏈時取6次的概率相當。說明基於馬爾可夫鏈的概率演算法求解效率明顯高於隨機概率演算法。那為什麼不將所有的演算法都基於馬爾可夫鏈呢?原因一,其實現方式不是那麼簡單,例子中我們規定了取數的規則是復合馬爾可夫鏈的,而在其他問題中我們需要建立適當的復合馬爾科夫鏈的模型才能使用。原因二,並不是所有的問題都符合馬爾科夫鏈條件,比如原子內電子出現的位置,女朋友為什麼會生(lou)氣,彩票號碼的規律等,建立模型必須與問題有相似之處才能較好的解決問題。
介紹完了優化演算法,再來討論討論優化演算法的使用場景。
前面說了優化演算法是一種概率演算法,無法保證一定能得到最優解,故如果要求結果必須是確定、穩定的值,則無法使用優化演算法求解。
例1,求城市a與城市b間的最短路線。如果結果用來修建高速、高鐵,那麼其結果必定是唯一確定的值,因為修路寸土寸金,必須選取最優解使花費最少。但如果結果是用來趕路,那麼即使沒有選到最優的路線,我們可能也不會有太大的損失。
例2,求城市a與城市b間的最短路線,即使有兩條路徑,路徑1和路徑2,它們從a到b的距離相同,我們也可以得出這兩條路徑均為滿足條件的解。現在將問題改一下,求城市a到城市b耗時最少的線路。現在我們無法馬上得出確切的答案,因為最短的線路可能並不是最快的路線,還需要考慮到天氣,交通路況等因素,該問題的結果是一個動態的結果,不同的時間不同的天氣我們很可能得出不同的結果。
現實生產、生活中,也有不少的場景使用的優化演算法。例如我們的使用的美圖軟體,停車場車牌識別,人臉識別等,其底層參數可能使用了優化演算法來加速參數計算,其參數的細微差別對結果的影響不太大,需要較快的得出誤差范圍內的參數即可;電商的推薦系統等也使用了優化演算法來加速參數的訓練和收斂,我們會發現每次刷新時,推給我們的商品都有幾個會發生變化,而且隨著我們對商品的瀏覽,系統推給我們的商品也會發生變化,其結果是動態變化的;打車軟體的訂單系統,會根據司機和客人的位置,區域等來派發司機給客人,不同的區域,不同的路況,派發的司機也是動態變化的。
綜上我們可以大致總結一下推薦、不推薦使用優化演算法的場景的特點。
前面說過,優化演算法處理的問題都是客觀的問題,如果遇到主觀的問題,比如「我孰與城北徐公美」,我們需要將這個問題進行量化而轉換成客觀的問題,如身高——「修八尺有餘」,「外貌——形貌昳麗」,自信度——「明日徐公來,孰視之,自以為不如;窺鏡而自視,又弗如遠甚」,轉化成客觀問題後我們可以得到各個解的分數,通過比較分數,我們就能知道如何取捨如何優化。這個轉化過程叫做問題的建模過程,建立的問題模型實際上是一個函數,這個函數對優化演算法來說是一個黑盒函數,即不需要知道其內部實現只需要給出輸入,得到輸出。
在優化演算法中這個黑盒函數叫做 適應度函數 , 優化演算法的求解過程就是尋找適應度函數最優解的過程 ,使用優化演算法時我們最大的挑戰就是如何將抽象的問題建立成具體的模型,一旦合適的模型建立完成,我們就可以愉快的使用優化演算法來求解問題啦。(「合適」二字談何容易)
優化演算法的大致介紹到此結束,後面我們會依次介紹常見、經典的優化演算法,並探究其參數對演算法性能的影響。
——2019.06.20
[目錄]
[下一篇 優化演算法筆記(二)優化演算法的分類]