一點前奏

第一次聽說遺傳演算法是在高三晚上放學回家的路上，同行的小夥伴問我：你知道遺傳演算法麼？我自然沒聽說過，於是追問細節。

“聽說遺傳演算法能夠自我迭代，讓他本身系統內的東西進行優勝劣汰的自然選擇，把好的保留下來，次一點的東西就排除掉。是不是特別像人工智慧的那種感覺？”

這麼高階的麼？那時候我就對這個演算法產生了一點興趣，畢竟一個演算法是如何做到自我判斷什麼是好什麼是壞。

因為如此，在我接觸到程式設計以後，我終於有能力去深入研究一下遺傳演算法了。最後覺得，其實這個演算法也沒有當初想得那麼玄乎。

當初年輕不懂事時，對未知的事物有著天然的好奇，自然會把遺傳演算法想的無限大，甚至認為可以自我淘汰不好的程式碼，學習優秀的程式碼等。

其實現在再看過來，遺傳演算法的本質始終沒變，依舊是優勝劣汰，選出最優秀的個體。只不過它的作用被我規劃成了“求一個系統/模型的最優解”。

遺傳演算法簡介

顧名思義，學過高中生物的都應該可以理解“遺傳”是什麼，染色體變異、染色體交叉等術語應該也能夠大概知道是什麼意思。其實遺傳演算法主要就是模擬這一個過程。

不過我也不是專業搞生物的，高中的知識細節部分我早都忘光了，因此拋開其他的，接下來我用我的理解來定義一下遺傳演算法的過程。

遺傳演算法四個基礎概念

遺傳演算法中，一個基本單位為“個體”，一個種群（系統）中擁有好多個體。每個個體攜帶兩個內容：染色體與適應度。

為了形象起見，我們可以把一個個體比喻成一頭羊，一堆羊聚集在一起就成了一個種群。每一隻羊長的（肥瘦程度）都不同，有的很肥，有的很瘦。我們作為一個牧場的牧場主，**最終目的是養出最肥的羊**。而我們的羊比較奇葩，每天都會產仔，並且產完仔就會死去，令我們牧場羊的數量保持在一個確定的數量上。

為了逼迫羊們越來越肥，我們每天殺死最瘦的羊，然後越肥的羊就越有機率交配生孩子，生出的孩子有可能變肥，也有可能變瘦。這樣長此以往下去，我們羊群的羊將會越來越肥，而我們也達到了我們的目的。

所以簡單的總結一下，上面每一頭羊都是一個“個體”，整個牧場就是一個種群。每一頭羊有“**決定**肥瘦程度的染色體”與“肥瘦程度”。這個肥瘦程度就是我們要說的遺傳演算法的“適應度”。每一天我們將其稱之為迭代一次，也就是換一批新羊。

或者用生物上的話來說，每一頭羊都有染色體，染色體決定了他們表現出來的性狀是怎樣的。所以說，染色體決定了每一頭羊的肥瘦程度。

因此我們建立以下對應關係：

整個牧場 -> 一個種群

一頭羊->一個個體

某頭羊決定肥瘦程度的染色體->該個體的染色體

肥瘦程度->適應度

明確了上面四個基礎概念以後，我們就可以引出他們之間的相互關係。

種群中包含了若干個個體，每個個體都擁有兩個屬性：染色體與適應度。每一次迭代中，種群中的個體數量不變。

染色體

其實需要細講的主要還是染色體。

染色體是遺傳演算法與“被求最優解模型”直接相關之處。通常來說一個模型想要求最優解，那麼就肯定會存在變數，透過控制變數的值讓模型的最終值達到最優。

所以在這裡，模型中所有變數就構成了一條染色體。其中每一個變數稱之為染色體上的一個基因。

比如說我們這裡有一個多元函式

f=f(x, y)

，這個函式擁有最大值$

f_{max}

，但是對應的最大值點

(x_{max}, y_{max})

我們並不知道，用通常方法也十分難求出來，所以我們可以利用遺傳演算法來簡單求解一下。所以就將染色體設定為兩個節點（基因），第一個節點為

x

，第二個節點為

y

。

這是對於一個個體來說的，也就是對於單個個體，他的染色體值我可以寫成一個向量為

chrom = [x, y]

適應度

那麼得到了染色體，模型的最優解如何評價呢？就是利用適應度來尋找最優解。

每個個體的適應度就相當於這個模型在“這個染色體的變數的值下的解”。也就是說這個個體的染色體值為

chrom = [x_1, y_1]

，所以我們把

(x_1, y_1)

帶入到之前的多元函式中，可以得到這個函式的一個解為

f_1 = f(x_1, y_1)

，解

f_1

就是這一條染色體（個體）的適應度。

尋找最優解

對於整個種群，我們假設有

N

個個體，所以對應的，也就有

N

條染色體，

N

個適應度。因此可以寫成以下形式

Chrom = \begin{bmatrix} x_1 & y_1 \\ x_2 & y_2 \\ \dots & \dots \\x_N & x_N \end{bmatrix}

Fitness = [f_1, f_2, \dots, f_N]^{\mathrm{T}}

其中每一行都代表著一個個體。

我們在這裡假設每個個體的染色體的值各不相同，因此適應度（模型的解）也就各不相同。所以我們就可以從中挑出來最大的適應度，它就是在當前情況下的最優解，但不一定是真正的最大值

f_{max}

。

所以接下來的就是開始尋找真正的最大值（最優解）。

遺傳演算法流程

一次迭代包括以下幾個過程：

1。 染色體變異。即改變某個染色體的值；

2。 染色體交叉。任意選擇兩個染色體交換部分基因；

3。 計算適應度。計算每個染色體在當前迭代下對應的適應度。

4。 優勝劣汰。選出最劣適應度的染色體，並將其~~用最優適應度染色體~~替換。

染色體變異

染色體變異作用於每一個個體，目的就是修改當前染色體，從而讓其變得“更好”，也有可能變得“更壞”。

為了能夠讓已經就很優的個體不要貿然的跌下神壇，讓不算特別好的個體突破階級限制進入最優，我們可以做出以下規定：

適應度越優的個體染色體變化範圍越小；

f

適應度越劣的個體染色體變化範圍越大。

這樣子就能夠令整個種群的階級隨時保持流動。

假設某個個體的染色體的某個節點$x$要發生變異，我們現在必須已知：當前迭代下種群中的最優適應度$f_{best}$；當前個體的適應度$f$。

然後我們產生一個隨機數$rand$，就是這個節點的變化值，所以透過公式

x_{new}=x\left[1\pm rand\left(1-\dfrac{f}{f_{best}}\right)^2\right]

可以得到新的染色體節點值

x_{new}

。其中，正負號隨機決定，代表著當前染色體節點值應該變大還是變小。

這個式子代表著，當

f

越趨近於

f_{best}

時，

\left(1-\frac{f}{f_{best}}\right)^2

就趨近於0，說明對原

x

的改變越小（變化量幾乎為0）；當

f

遠離

f_{best}

時，

\left(1-\frac{f}{f_{best}}\right)^2

越趨近於1，說明對原

x

的改變越大。

染色體交叉

染色體交叉比較容易，隨機選擇兩個染色體，在隨機選擇一對節點，相互交換對應的值即可。

比如有兩個個體的染色體為

chrom_m=[x_m, y_m], chrom_n = [x_n, y_n]

，我們選擇將其第一個節點上的兩個節點進行交叉互換，得到新的兩個染色體值為

chrom_m=[x_n, y_m], chrom_n = [x_m, y_n]

。

計算適應度

計算適應度其實就是將每個個體的染色體帶入到模型中進行計算，計算出來其對應的適應度。

優勝劣汰

為了讓我們種群的適應度整體水平上升，我們必須殺死排名最後的那個個體。

殺死之後種群數量就變少了，所以就必須要讓比較優良的個體多生點來把種群數量補回來。在這裡我為了方便，直接把最劣的個體的染色體替換成了最優個體的染色體。

這樣子就是優勝劣汰，略微的把整體適應度水平提升了一點。

小結

以上就是遺傳演算法的大概流程。因為遺傳演算法的實現方法較多，所以這是按照我個人習慣整合成的一個遺傳演算法。一般來說，遺傳演算法的染色體還可以由二進位制表示，優勝劣汰的方法也有其他方法，在這裡我們就不多贅述。

下一章將會引入MATLAB程式碼，引入實際模型來進行一個具體的計算。

對知乎編輯器的吐槽

因為知乎不支援Markdown，所以公式還得一點點全部複製貼上到Tex編輯器中，做無用功。所以讓我對在知乎上同步發表文章不太積極。

在我的CSDN部落格上已經更新完了這個遺傳演算法與MATLAB系列，所以有興趣的朋友們可以直接戳連結轉到我的部落格。