算法最佳化

算法最佳化

算法(Algorithm)是指解題方案的準確而完整的描述,是一系列解決問題的清晰指令,算法代表著用系統的方法描述解決問題的策略機制。算法最佳化是指對算法的有關性能進行最佳化,如時間複雜度、空間複雜度、正確性、健壯性。由於算法套用情景變化很大,算法最佳化可以使算法具有更好泛化能力。

簡介

算法最佳化是指對算法的有關性能進行最佳化,如時間複雜度、空間複雜度、正確性、健壯性。大數據時代到來,算法要處理數據的數量級也越來越大以及處理問題的場景千變萬化。為了增強算法的處理問題的能力,對算法進行最佳化是必不可少的。算法最佳化一般是對算法結構和收斂性進行最佳化。

算法的基本特徵

一個算法應該具有以下五個重要的特徵:

有窮性(Finiteness)

算法的有窮性是指算法必須能在執行有限個步驟之後終止;

確切性(Definiteness)

算法的每一步驟必須有確切的定義;

輸入項(Input)

一個算法有0個或多個輸入,以刻畫運算對象的初始情況,所謂0個輸入是指算法本身定出了初始條件;

輸出項(Output)

一個算法有一個或多個輸出,以反映對輸入數據加工後的結果。沒有輸出的算法是毫無意義的;

可行性(Effectiveness)

算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步,即每個計算步都可以在有限時間內完成(也稱之為有效性)。

算法常見評定標準

同一問題可用不同算法解決,而一個算法的質量優劣將影響到算法乃至程式的效率。算法分析的目的在於選擇合適算法和改進算法。一個算法的評價主要從時間複雜度和空間複雜度來考慮。

時間複雜度

算法的時間複雜度是指執行算法所需要的計算工作量。一般來說,計算機算法是問題規模n 的函式f(n),算法的時間複雜度也因此記做。

T(n)=Ο(f(n))

因此,問題的規模n 越大,算法執行的時間的增長率與f(n) 的增長率正相關,稱作漸進時間複雜度(Asymptotic Time Complexity)。

空間複雜度

算法的空間複雜度是指算法需要消耗的記憶體空間。其計算和表示方法與時間複雜度類似,一般都用複雜度的漸近性來表示。同時間複雜度相比,空間複雜度的分析要簡單得多。

正確性

算法的正確性是評價一個算法優劣的最重要的標準。

可讀性

算法的可讀性是指一個算法可供人們閱讀的容易程度。

健壯性

健壯性是指一個算法對不合理數據輸入的反應能力和處理能力,也稱為容錯性 。

泛化能力

泛化能力(generalization ability)是指機器學習算法對新鮮樣本的適應能力。學習的目的是學到隱含在數據對背後的規律,對具有同一規律的學習集以外的數據,經過訓練的網路也能給出合適的輸出,該能力稱為泛化能力。通常期望經訓練樣本訓練的網路具有較強的泛化能力,也就是對新輸入給出合理回響的能力。應當指出並非訓練的次數越多越能得到正確的輸入輸出映射關係。網路的性能主要用它的泛化能力來衡量。

常見算法最佳化方法

隨機搜尋

隨機搜尋(random search)是利用隨機數求極小點而求得函式近似的最優解的方法。

變數允許的變化區間,不斷隨機地而不是有傾向性產生隨機點,並計算其約束函式和目標函式的值,對滿足約束條件的點,逐個比較其目標函式的值,將壞的點拋棄,保留好的點,最後便得到最優解的近似解。這種方法是建立在機率論的基礎上,所取隨機點越多,則得到最優解的機率也就越大。由於大多數電腦程式庫中有隨機數發生器,所以套用這種方法是很方便的。但是其計算精度較差、效率較低。隨機搜尋一般用於粗選或普查。常用的方法有隨機跳躍法,隨機走步法等。

梯度下降法

梯度下降法是一個最最佳化算法,通常也稱為最速下降法。最速下降法是求解無約束最佳化問題最簡單和最古老的方法之一,雖然現在已經不具有實用性,但是許多有效算法都是以它為基礎進行改進和修正而得到的。最速下降法是用負梯度方向為搜尋方向的,最速下降法越接近目標值,步長越小,前進越慢。

遺傳算法

遺傳算法也是受自然科學的啟發。這類算法的運行過程是先隨機生成一組解,稱之為種群。在最佳化過程中的每一步,算法會計算整個種群的成本函式,從而得到一個有關題解的排序,在對題解排序之後,一個新的種群----稱之為下一代就被創建出來了。首先,我們將當前種群中位於最頂端的題解加入其所在的新種群中,稱之為精英選拔法。新種群中的餘下部分是由修改最優解後形成的全新解組成。

常用的有兩種修改題解的方法。其中一種稱為變異,其做法是對一個既有解進行微小的、簡單的、隨機的改變;修改題解的另一種方法稱為交叉或配對,這種方法是選取最優解種的兩個解,然後將它們按某種方式進行組合。爾後,這一過程會一直重複進行,知道達到指定的疊代次數,或者連續經過數代後題解都沒有改善時停止。

模擬退火法

模擬退火法是受物理學領域啟發而來的一種最佳化算法。退火是指將合金加熱後再慢慢冷卻的過程。模擬退火也是從一個隨機解開始,然後朝著某個方向變化。算法最為關鍵的部分在於,如果新的解成本值更低,那么新的解則會替代當前當前解,和爬山法類似,不過,如果成本只更高的話,這個解仍然有可能替代當前解。模擬退火算法之所有管用,不僅因為它總是會接受一個更優的解,而且還因為它在退火過程的開始階段會接受表現比較差的解。隨著退火過程的不斷進行,算法越來越不可接受較差的解。

相關詞條

熱門詞條

聯絡我們