遺傳演算法簡單介紹與MATLAB實現（一）

02-08

一點前奏

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

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

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

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

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

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

遺傳演算法簡介

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

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

遺傳演算法四個基礎概念

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

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

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

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

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

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

整個牧場 -> 一個種群
一頭羊->一個個體
某頭羊決定肥瘦程度的染色體->該個體的染色體
肥瘦程度->適應度

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

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

染色體

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

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

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

比如說我們這裡有一個多元函數 $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 = egin{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}=xleft[1pm randleft(1-dfrac{f}{f_{best}} ight)^2 ight]$

可以得到新的染色體節點值 $x_{new}$ .其中,正負號隨機決定，代表著當前染色體節點值應該變大還是變小。

這個式子代表著，當 $f$ 越趨近於 $f_{best}$ 時， $left(1-frac{f}{f_{best}} ight)^2$ 就趨近於0，說明對原 $x$ 的改變越小（變化量幾乎為0）；當 $f$ 遠離 $f_{best}$ 時， $left(1-frac{f}{f_{best}} ight)^2$ 越趨近於1，說明對原 $x$ 的改變越大。