人工神經網路 - 遺傳演算法

自然一直是全人類極大的靈感來源。遺傳演算法 (GA) 是基於自然選擇和遺傳學概念的基於搜尋的演算法。遺傳演算法是更大計算分支（稱為進化計算）的一個子集。

遺傳演算法由John Holland及其在密歇根大學的學生和同事（最著名的是David E. Goldberg）開發，此後已在各種最佳化問題上進行了嘗試，並取得了高度成功。

在遺傳演算法中，我們有一組或一個給定問題的可能解決方案池。然後，這些解決方案會進行重組和變異（就像自然遺傳一樣），產生新的後代，並且該過程會重複幾代。每個個體（或候選解決方案）都會被賦予一個適應度值（基於其目標函式值），並且適應性更強的個體具有更高的交配機會，併產生更多“適應性更強”的個體。這符合達爾文的“適者生存”理論。

透過這種方式，我們不斷“進化”出更好一代的個體或解決方案，直到達到停止標準。

遺傳演算法本質上是隨機的，但它們比隨機區域性搜尋（我們只是嘗試各種隨機解決方案，並跟蹤迄今為止最好的解決方案）要好得多，因為它們也利用歷史資訊。

遺傳演算法的優點

遺傳演算法具有多種優勢，使其廣受歡迎。這些包括：

• 不需要任何導數資訊（許多現實世界的問題可能無法提供）。

• 與傳統方法相比，速度更快，效率更高。

• 具有非常好的並行能力。

• 最佳化連續和離散函式以及多目標問題。

• 提供一系列“良好”的解決方案，而不僅僅是一個解決方案。

• 始終獲得問題的答案，並且隨著時間的推移會變得更好。

• 當搜尋空間非常大並且涉及大量引數時非常有用。

遺傳演算法的侷限性

與任何技術一樣，遺傳演算法也有一些侷限性。這些包括：

• 遺傳演算法不適用於所有問題，特別是那些簡單且可以獲得導數資訊的問題。

• 適應度值被重複計算，這對於某些問題來說可能計算成本很高。

• 由於具有隨機性，因此無法保證解決方案的最優性或質量。

• 如果實現不當，遺傳演算法可能無法收斂到最優解。

遺傳演算法——動機

遺傳演算法能夠“足夠快”地提供“足夠好”的解決方案。這使得遺傳演算法在解決最佳化問題方面具有吸引力。需要遺傳演算法的原因如下：

解決難題

在計算機科學中，有一大類問題是NP難的。這實際上意味著，即使是最強大的計算系統也需要很長時間（甚至數年！）才能解決該問題。在這種情況下，遺傳演算法被證明是提供可用的近似最優解的有效工具，並且所需時間很短。

基於梯度的方法的失敗

傳統的基於微積分的方法的工作原理是從一個隨機點開始，沿著梯度的方向移動，直到到達山頂。對於單峰目標函式（例如線性迴歸中的成本函式），這種技術是有效的並且執行良好。但是，在大多數現實世界的情況中，我們有一個非常複雜的問題，稱為景觀，由許多峰和許多谷組成，這會導致此類方法失敗，因為它們具有固有的傾向停留在區域性最優解，如下圖所示。

快速獲得良好的解決方案

旅行商問題 (TSP) 等一些難題具有路徑查詢和 VLSI 設計等現實世界的應用。現在假設您正在使用 GPS 導航系統，並且計算從起點到目的地的“最佳”路徑需要幾分鐘（甚至幾小時）。在這些現實世界的應用中，延遲是不可接受的，因此需要“足夠好”的解決方案，並且交付“快速”。

如何將遺傳演算法用於最佳化問題？

我們已經知道，最佳化是使設計、情況、資源和系統儘可能有效的一種行為。最佳化過程如下圖所示。

用於最佳化過程的遺傳演算法機制階段

以下是將遺傳演算法用於問題最佳化時的階段。

• 隨機生成初始種群。

• 選擇具有最佳適應度值的初始解。

• 使用突變和交叉運算元重組選定的解。

• 將後代插入種群。

• 現在，如果滿足停止條件，則返回具有最佳適應度值的解。否則，轉到步驟 2。