優(yōu)化算法之手推遺傳算法（Genetic Algorithm）的詳細步驟圖解

來源：DeepHub IMBA

遺傳算法可以做什么？

遺傳算法是元啟發(fā)式算法之一。它有與達爾文理論（1859 年發(fā)表）的自然演化相似的機制。如果你問我什么是元啟發(fā)式算法，我們最好談談啟發(fā)式算法的區(qū)別。
啟發(fā)式和元啟發(fā)式都是優(yōu)化的主要子領域，它們都是用迭代方法尋找一組解的過程。啟發(fā)式算法是一種局部搜索方法，它只能處理特定的問題，不能用于廣義問題。而元啟發(fā)式是一個全局搜索解決方案，該方法可以用于一般性問題，但是遺傳算法在許多問題中還是被視為黑盒。
那么，遺傳算法能做什么呢?和其他優(yōu)化算法一樣，它會根據(jù)目標函數(shù)、約束條件和初始解給我們一組解。

最優(yōu)局部解與最優(yōu)全局解

遺傳算法是如何工作的?

遺傳算法有5個主要任務，直到找到最終的解決方案。它們?nèi)缦隆?/span>

• 初始化

• 適應度函數(shù)計算

• 選擇

• 交叉

• 突變

定以我們的問題

我們將使用以下等式作為遺傳算法的示例。它有 5 個變量和約束，其中 X1、X2、X3、X4 和 X5 是非負整數(shù)且小于 10（0、1、2、4、5、6、7、8、9）。使用遺傳算法，我們將嘗試找到 X1、X2、X3、X4 和 X5 的最優(yōu)解。

將上面的方程轉化為目標函數(shù)。遺傳算法將嘗試最小化以下函數(shù)以獲得 X1、X2、X3、X4 和 X5 的解決方案。


由于目標函數(shù)中有 5 個變量，因此染色體將由 5 個基因組成，如下所示。

初始化

在初始化時，確定每一代的染色體數(shù)。在這種情況下，染色體的數(shù)量是 5。因此，每個染色體有 5 個基因，在整個種群中總共有 25 個基因。使用 0 到 9 之間的隨機數(shù)生成基因。

在算法中：一條染色體由幾個基因組成。一組染色體稱為種群

下圖是第一代的染色體。

適應度函數(shù)計算

它也被稱為評估。在這一步中，評估先前初始化中的染色體。對于上面示例，使用以下的計算方式。
這是第一代種群中的第一個染色體。

將 X1、X2、X3、X4 和 X5 代入目標函數(shù)，得到 53。


適應度函數(shù)是 1 除以誤差，其中誤差為 (1 + f(x))。


下面公式中加 1 是為了避免零問題


這些步驟也適用于其他染色體。

選擇

輪盤****法是遺傳算法中的一種隨機選擇方法。這就像****場里的輪盤****。它有一個固定點，并且輪子旋轉直到輪子上的一個區(qū)域到達固定點的前面。

在遺傳算法的背景下，具有較高適應度值的染色體將更有可能在輪盤****中被選中。

首先，計算 5 條染色體的總適應度值。

總計 =