受到生物進化論的啟發，遺傳演算法的出現為解決全域性最佳化問題提供了全新的思路和路徑，它基於生物遺傳和進化機制，結合

自適應的機率最佳化演算法

，使得我們能夠在全域性範圍內找尋最優解。對於解決現實中的一系列非凸函式問題有較好的表現，作為目前較為經典並且常見的機器智慧演算法，GA不僅可以簡化模型求解具體問題的複雜度，而且具有求解的通用性，使得其應用越來越廣泛。

生物進化觀點

：試想一下高中生物學習的進化論，在一個由多個

個體

組成的

種群

當中，

染色體

作為DNA的載體，是重要的遺傳資訊載體。而對於每個個體而言，其染色體都來源於其父親和母親（我們統稱為父代）。考慮長時間的生物進化過程，父代向子代傳遞遺傳資訊的過程當中，會發生染色體的

複製，交叉，變異等現象

，根據達爾文提出的“優勝劣汰”進化規則，最終會產生一群更適應環境的個體。遺傳演算法作為一種自調節的全域性搜尋最優解的演算法，模仿了生物的進化過程，模擬自然選擇和遺傳中的“複製”、“交叉”、“變異”等現象。從代表問題可能潛在所有解集的一個初始化種群（該種群又是由經過基因編碼的一定數量的個體組成）開始，對種群進行反覆的“複製”、“交叉”、“變異”等操作，估計每個個體的適應值，根據“適者生存”的進化規則，獲取本次進化過程中，該種群內最靠近最優解的個體，不斷的進行上述操作，最終將末代種群中的最優個體解碼獲得滿足要求的最優解。

數學觀點

：實際問題的解決過程中，我們會發現很多問題均是非凸的，也即是說往往在全域性範圍之內會出現許多的區域性最優解，那麼如何在全域性的範圍內找到全域性最優解便是最佳化問題的一個重要的問題，遺傳演算法便可以巧妙地解決該問題，它不需要內在複雜的機理，我們可將其當做一個黑箱，不斷尋找潛在的解，透過一定的準則自適應的尋找全域性最優解，在求解較為複雜的組合最佳化問題時，相對一些常規的最佳化演算法，通常能夠較快地獲得較好的最佳化結果。

首先，我們將生物進化概念與遺傳演算法進行類比，從我個人的理解思路來講，我建議大家在理解遺傳演算法的過程中充分類比生物的進化過程：

圖1 生物進化與遺傳演算法的關係對照

1。 自適應函式：

遺傳演算法的適應度函式是用來判斷群體中的個體的優劣程度的指標（越靠近最優解更優），一般的，它是根據所求問題的目標函式來進行評估的。所以我們可以將個體在目標函式的值視作自適應值。某個體的自適應值越大，那麼其被遺傳到下一代的機率就越大，所以自適應度函式的選擇將直接影響到遺傳演算法收斂的速度以及能否找到全域性最優解。

2。 染色體的編碼與解碼：

為了在計算機中進行演算法解的搜尋，我們需要將解所在空間對映到基因型的空間，這樣計算機才能有效的進行識別，解碼則反之，是從基因型到解所在區間的對映。一般地，我們採用二進位制方式來進行編碼，它採用一個二進位制的字串來表徵解（

包含0或1，即可視為染色體上的基因

）在精度允許的前提條件下，二進位制編碼可以將區間內的無窮多個點用間隔足夠小的有限個點來代替。在編碼的過程當中，我們需要確定解的區間以及需要表示的解的精度：

初始種群的各個個體的基因可以用均勻分佈的隨機數產生，例如要在區間

內尋找最優解，那麼此時染色體的編碼長度，及x的精度要求就至關重要了，假設需要編碼的染色體長度為n，要求達到的精度維小數點後m位，那麼染色體編碼長度和精度之間有如下關係：

在相關精度要求之下，根據上述不等式就可以確定染色體的編碼長度n，進而實現對自變數

的編碼：

在求解個體的自適應函式值時，便需要對染色體編碼進行解碼（decode），對於一個長度為n的二進位制字串，解碼後的

值為：

其中的

為個體的二進位制編碼第k位（從右往左）上的編碼數字（0或1），在上述的編碼（encode）和解碼（decode）定義便實現瞭解空間和基因空間元素之間的轉化。在實際的應用中，二進位制也會存在一些問題，比如

為

時，二進位制編碼為01111和10000，在二進位制格式下，兩數的轉化就需要改變所有位，那麼在後續的交叉和變異操作中就會存在缺陷，所以在有的情況下會採用格雷碼或其他的編碼方式，文章指路：

Bat特白：格雷碼

在本文中，我們仍然採取二進位制的編碼和解碼方式。

3。 選擇操作

輪盤賭

：

遺傳演算法的本質就是模擬生物進化“適者生存”的過程，而個體的適應度值就是評價個體“適應”程度的指標，考慮有N個個體的種群，每個個體有自己的自適應函式值

，定義該個體被選中的機率

，那麼個體的適應值越大其被選中的機率也就越大，在程式設計的過程當中，我們採用輪盤賭來實現該操作。所謂輪盤賭，想一想你去超市購物滿金額之後的轉轉盤抽獎環節，輪盤可以被分為不相等的幾部分扇形區域，指標落在面積更大的區域機率越大，同理，我們可以考慮

前i個體適應度值的和：

例如，此時有5個個體，我們知道了其自適應度值

，那麼我們可以透過計算第i個個體的前i個適應度之和

，最終得到輪盤賭的各區域分界值：

輪盤賭

注：累積適應度值即為上面定義的

，累積機率就是在

的基礎之上除以全體適應度值之和：也就是

，該例中N取5，顯然，個體的適應度值越大，其累計機率就越大，最終輪盤賭操作就按照累計機率為依據，隨機產生一個0到1之間的隨機數，假設是0。3，那麼0。3恰好在累計機率［0。1322，0。3244］之間，那麼該輪選擇就選擇出區間的右端點代表的個體3，反覆進行該操作，最終選擇出子代種群。

精英選擇

在每一代的選擇過程中會產生一個適應度最高的個體，那麼在每一代的選擇過程中，可以將本代的最優個體保留，傳給下一代，這樣的選擇方式我們稱為精英選擇，其目的是更好的使我們的結果收斂，儘快的找到全域性最優解。

4. 交叉運算元(crossover)

遺傳交叉運算元發生在兩條染色體之間，是遺傳演算法中常見的遺傳操作，交叉操作將種群內個體隨機配對，對每一個染色體隨機產生一個交叉點（單點交叉，當然也可以是多點交叉，程式設計時會稍微增加難度，我們現階段只考慮單點交叉），以某一機率交換其交叉點之後的染色體。交叉機率越大，那麼可以使得各代的交叉越充分，同時個體重中的優良個體也有可能遭到破壞，所以合適的選擇交叉機率才會起到較好的作用，一般的交叉機率在［0。4， 0。99］之間。在後續的程式設計中，我們選取相隔一個個體的兩染色體進行交叉操作。

5. 變異運算元(mutation)

遺傳變異操作就是選取種群中某一個體，以一定的機率隨機的改變染色體中某

一個或多個

基因的值，由於之前的操作當中已經將染色體進行二進位制編碼，那麼此時改變基因的值就是二進位制的取反操作，一般的變異機率為［0。0001， 0。1］之間。變異演算法是對遺傳演算法的改進，對交叉過程中可能丟失的某些遺傳基因進行修復和補充，也可以防止遺傳演算法較快的收斂到區域性最優解。和交叉機率相似，不合適的變異機率也會對演算法的收斂性以及最終的最優解取值產生較大的影響，當變異機率較小時，解的穩定性較高，但是很容易陷入區域性最優解，並且難以跳出區域性最優解的區間；但是如果變異機率較大，可以使得解空間具有多樣性，從區域性最優解跳出來，最終找到全域性最優解，所以在設計程式的時候應該較好的選取變異機率。

當然對於上述的各操作，其方法都不唯一。比如選擇操作中除了輪盤賭演算法，還有隨機遍列取樣等方法，交叉和變異操作中也有多點操作，洗牌交叉等等多種方式，在本文中我們都挑取較為簡單並且容易理解的操作方式。上述的5點知識即為遺傳演算法中的核心，我將以流程圖的形式來說明遺傳演算法的步驟。

遺傳演算法的操作步驟：

確定適應度函式的取值範圍，確立精度及染色體編碼長度。

初始化操作：染色體編碼，確立種群數量，交叉、變異機率等。

初始化種群：隨機生成第一代種群。

利用適應度函式評價種群，判斷是否滿足停止條件，若是則停止，輸出最優解；否則繼續進行操作。

對種群進行選擇、交叉、變異操作，得到下一代種群，回到第4步。

遺傳演算法流程圖

最終演算法可以得到獲得：1。 最佳適應值的個體染色體編碼，透過解碼操作獲取自變數所對應的值；2。 最佳適應度值，也就是演算法找到的全域性最優解；3。 取得最優解的迭代次數（進化到第幾代），遺傳演算法作為一個自搜尋全域性最優解的方法在許多領域的應用都極其的廣泛，當我們解決的問題較為複雜，常常都無法獲取其最優解的情況不妨可以用遺傳演算法嘗試一下，接下來，我們以一個一元函式的最優值問題來運用遺傳演算法：

例：求解函式

在［-1， 2。5］上的最大值

首先，我們嘗試用matlab畫出該函式的影象：可以看出，該函式是非凸的，在區域性區域有許多的區域性最優解，利用matlab的指令我們可以知道該函式的最大值為5。9008，其對應的x值大概在2。4左右，接下來我們用遺傳演算法來求解該問題。

在我的程式設計中：我選取的種群的個體數量為80，染色體長度為15，最大進化代數為60，交叉機率和變異機率分別為0。6和0。01，在選擇過程中運用了精英選擇方式。

讓我們來看看最終的結果：

Best performed individual（chromosome）： 1 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1

Corresponding fitness value：5。9008

Corresponding variable value：2。4017

The time of evolution th get the best：14

在經過了13次迭代，到第14代的時候就找到了最優解5。9008，其對應個體染色體經過解碼即為自變數的取值，為2。4017。需要注意的是，遺傳演算法是一種機率最佳化演算法，所以其每一次的結果可能會不一樣，但是我們如何評價我們建立的模型的好壞，如何確定我們選取的各引數值較為合理呢？此時我們可以看看每一代種群的最大適應值，和個體的平均適應度值：

可以看到，演算法在第14代找到了全域性最優解，每一代種群的平均適應度函式值在前20次進化中在迅速的增大，並且在第30代左右趨於平緩，在第40代之後，種群的最大及平均適應度值都非常平緩了，此時我們就可以說明該演算法已經收斂，我們的引數設定較為合理。

這就是遺傳演算法的基本思路和基本步驟的一個介紹。。。這部分程式碼比較長，下一篇文章中，我將結合github上的程式碼結合自己對該演算法的理解寫一個總結，祝大家學習愉快。

https：//

github。com/yanshengjia/

artificial-intelligence/tree/master/genetic-algorithm-for-functional-maximum-problem/matlab-ga

Kezard：遺傳演算法2 matlab程式設計實現（GA2——- Programming for Matlab）

參考書目：

數學建模與數學實驗（第四版）高等教育出版社，趙靜，但琦。