前言

本文主要介紹了數學建模常用模型遺傳演算法，從原理出發到編程實作再到實體運用，筆者參與過大大小小五次數學建模，個人覺得該優化演算法值得一學，

提示：以下是本篇文章正文內容

一、遺傳演算法由來

遺傳演算法的起源可追溯到20世紀60年代初期，1967年,美國密歇根大學J. Holland教授的學生 Bagley在他的博士論文中首次提出了遺傳演算法這一術語,并討論了遺傳演算法在博弈中的應用,但早期研究缺乏帶有指導性的理論和計算工具的開拓，1975年, J. Holland等提出了對遺傳演算法理論研究極為重要的模式理論,出版了專著《自然系統和人工系統的適配》,在書中系統闡述了遺傳演算法的基本理論和方法,推動了遺傳演算法的發展，20世紀80年代后,遺傳演算法進入興盛發展時期，被廣泛應用于自動控制、生產計劃、影像處理、機器人等研究領域，

二、遺傳演算法定義

遺傳演算法（Genetic Algorithm，GA）最早是由美國的 John holland于20世紀70年代提出,該演算法是根據大自然中生物體進化規律而設計提出的，是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化程序的計算模型，是一種通過模擬自然進化程序搜索最優解的方法，該演算法通過數學的方式,利用計算機仿真運算,將問題的求解程序轉換成類似生物進化中的染色體基因的交叉、變異等程序，在求解較為復雜的組合優化問題時,相對一些常規的優化演算法,通常能夠較快地獲得較好的優化結果，

其主要特點是直接對結構物件進行操作，不存在求導和函式連續性的限定；具有內在的隱并行性和更好的全域尋優能力；采用概率化的尋優方法，不需要確定的規則就能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，

遺傳演算法以一種群體中的所有個體為物件，并利用隨機化技術指導對一個被編碼的引數空間進行高效搜索，其中，選擇、交叉和變異構成了遺傳演算法的遺傳操作；引數編碼、初始群體的設定、適應度函式的設計、遺傳操作設計、控制引數設定五個要素組成了遺傳演算法的核心內容，

三、演算法理解

該演算法本質上是讓我們得到在種群中獲得基因最好的個體，這有點類似我之前的博文介紹梯度上升和梯度下降演算法中獲得最優引數，總的來說就像我們高中時做的求該函式的極大值點，我們往往是運用求導的方式來得到該函式的導函式為0的時候所得到的值，從而代入原方程求出極大值，而這些優化演算法只不過是把函式、求導方式方法用其他東西替換了而已，本質上還是差不多的，

圖為梯度下降：

既然我們把函式曲線理解成一個一個山峰和山谷組成的山脈，那么我們可以設想所得到的每一個解就是一登山者，我們希望這些登山者能夠爬上高峰，所以求最大值的程序就轉化成一個“爬山”的程序，

1. 梯度上升演算法：

我們總是往向著山頂的方向攀爬，當爬到一定角度以后也會駐足停留下觀察自身角度是否是朝著山頂的角度上攀爬（從搜索空間中隨機產生鄰近的點，從中選擇對應解最優的個體，替換原來的個體，不斷重復上述程序，），并且我們需要總是指向攀爬速度最快的方向爬，但是這座山不一定是最高峰，只能達到區域最優解而不是全域，

2. 模擬退火：

我們爬山坡的時候突然發現登山指明方向的工具失靈了，不清楚我們需要爬的最高山峰是哪座，導致我們不得不在這這篇山谷不停探索，這是我們可能走向平地或者繼續爬山峰，然后我們試圖爬上山峰后，繼續向全體更高的山峰探索，最后我們逐漸向目標最高的山峰爬去，（這個方法來自金屬熱加工程序的啟發，在金屬熱加工程序中，當金屬的溫度超過它的熔點（Melting Point）時，原子就會激烈地隨機運動，與所有的其它的物理系統相類似，原子的這種運動趨向于尋找其能量的極小狀態，在這個能量的變遷程序中，開始時，溫度非常高， 使得原子具有很高的能量，隨著溫度不斷降低，金屬逐漸冷卻，金屬中的原子的能量就越來越小，最后達到所有可能的最低點，利用模擬退火的時候，讓演算法從較大的跳躍開始，使到它有足夠的“能量”逃離可能“路過”的區域最優解而不至于限制在其中，當它停在全域最優解附近的時候，逐漸的減小跳躍量，以便使其“落腳 ”到全域最優解上，）

3. 遺傳演算法：

這次登山比賽中邀請了很多登山者，我們隨機降落到了這片山脈各處，但是我們并沒有收到具體要爬向哪座山峰只能隨機攀爬，但是每過一段時間舉辦方就將一些還沒有準備爬的和爬的還不夠高的登山者給淘汰掉，隨著比賽的進行將會有越來越多的登山者被淘汰掉，而越是接近山峰的登山者就越有可能獲勝，于是經歷了多天的比賽，剩下的登山者都基本聚集在一個山峰附近，他們交換自己的情報和裝備，一起朝著勝利的方向進行，（ 模擬物競天擇的生物進化程序，通過維護一個潛在解的群體執行了多方向的搜索，并支持這些方向上的資訊構成和交換，是以面為單位的搜索，比以點為單位的搜索，更能發現全域最優解，）

四、遺傳演算法的特點和應用

遺傳演算法是一類可用于復雜系統優化的具有魯棒性的搜索演算法，與傳統的優化演算法相比，具有以下特點：

1. 以決策變數的編碼作為運算物件，

遺傳演算法是使用決策變數的某種形式的編碼作為運算物件，這種對決策變數的編碼處理方式，使得我們在優化計算中可借鑒生物學中染色體和基因等概念，可以模仿自然界中生物的遺傳和進化激勵，也可以很方便地應用遺傳操作算子，

2. 直接以適應度作為搜索資訊，

遺傳演算法僅使用由目標函式值變換來的適應度函式值就可確定進一步的搜索范圍，無需目標函式的導數值等其他輔助資訊，直接利用目標函式值或個體適應度值也可以將搜索范圍集中到適應度較高部分的搜索空間中，從而提高搜索效率，

3. 使用多個點的搜索資訊，具有隱含并行性，

遺傳演算法從由很多個體組成的初始種群開始最優解的搜索程序，而不是從單個個體開始搜索，對初始群體進行的、選擇、交叉、變異等運算，產生出新一代群體，其中包括了許多群體資訊，這些資訊可以避免搜索一些不必要的點，從而避免陷入區域最優，逐步逼近全域最優解，

綜上，由于遺傳演算法的整體搜索策略和優化搜索方式在計算時不依賴于梯度資訊或其他輔助知識，只需要求解影響搜索方向的目標函式和相應的適應度函式，所以遺傳演算法提供了一種求解復雜系統問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于各種領域，包括：

• 函式優化
• 組合優化生產調度問題
• 自動控制
• 機器人學
• 影像處理
• 人工生命
• 遺傳編程
• 機器學習
  

五、演算法實作程序

我們可以從該演算法具體實作步驟結合你想要達到的目的來了解該演算法需要做些什么，

就以爬山比賽為例，如果我們作為爬山比賽的舉辦方，該如何設定合理的：

1.建立表現型和基因型的映射關系

我們需要識別每個登山比賽者的定位，就必須給他們設定相對應的編碼，

2.隨機初始化種群，個體為該種群的數字化編碼

比賽開始，開始隨機投放一批參賽選手降落到山脈地區，

3.解碼獲得個體對應的數值資訊

比賽進行到一段時間開始統計每個參賽選手的進度狀態，

4.用適應性函式對每一個基因個體作一次適應度評估

通過舉辦方邀請的專家進行評分，爬的最高的登山者得分最高，

5.選擇階段的理念就是選出最適合的個體，讓它們將基因傳遞給下一代，

每隔一段時間，淘汰一批得分不理想的選手，

6.交叉運算時遺傳演算法中最重要的階段，對于每一對即將結合的父體，演算法在基因中隨機選擇一個交叉點交換它們的某些基因，產生新的基因組合，期望將有益基因組合在一起，

其余的登山選手互相交換資訊和裝備，

7.在形成的新后代中，它們的一些基因會以較低的隨機概率出現變異，也就是說字串中的一些位元會發生變動，

可能資訊和裝備產生了某些變化導致爬山的方向發生改變，

8.如果種群出現了收斂（不再生成和之前幾代有巨大差異的后代），遺傳演算法就會終止，

比賽接近尾聲，余下的登山者幾乎都在目標山頂的附近，

以上就是整個遺傳演算法的流程，

通常認為遺傳演算法有5個階段：

• 初始種群
• 適應度函式
• 選擇運算
• 交叉運算
• 變異運算

遺傳演算法的偽代碼可以寫為：

1. 起始
2. 形成初始種群
3. 計算適應度
4. 重復
5. 選擇運算
6. 交叉運算
7. 變異運算
8. 計算適應度
9. 直到種群出現收斂
10. 終止

六、具體實作方法

基本遺傳演算法（SGA）由編碼、適應度函式、遺傳算子（選擇、交叉、變異）及運行引陣列成，

1.編碼與解碼

實作遺傳演算法的第一步就是明確對求解問題的編碼和解碼方式，

對于函式優化問題，一般有兩種編碼方式，各具優缺點

• 實數編碼：直接用實數表示基因，容易理解且不需要解碼程序，但容易過早收斂，從而陷入區域最優，例如坐標（1,2），（2,3），
• 二進制編碼：穩定性高，種群多樣性大，但需要的存盤空間大，需要解碼且難以理解，如：1110001010111

• 浮點編碼法：適用于在遺傳演算法中表示范圍較大的數，適用于精度要求較高的遺傳演算法，改善了遺傳演算法的計算復雜性，提高了運算交率，但存盤空間大，解碼且難以理解，如：1.2-3.2-5.3-7.2-1.4-9.7

• 符號編碼法：符合有意義積術塊編碼原則，便于在遺傳演算法中利用所求解問題的專門知識，便于遺傳演算法與相關近似演算法之間的混合使用，

在上面介紹了一系列編碼方式以后，那么，如何利用上面的編碼來為我們的袋鼠染色體編碼呢？首先我們要明確一點：編碼無非就是建立從基因型到表現型的映射關系，這里的表現型可以理解為個體特征（比如身高、體重、裝備等等），

那么，在此問題下，我們關心的個體特征就是：登山者的位置坐標（因為我們要把高低低的登山者給淘汰掉），我們關心的始終是登山者在哪里，并且只要知道了登山者的位置坐標（位置坐標就是相應的染色體編碼，可以通過解碼得出），我們就可以：

1. 在地圖上找到相應的位置坐標，算出高度，（相當于通過自變數求得適應函式的值）然后判讀該不該淘汰該登山者，
2. 可以知道交換情報和裝備（染色體交叉和變異）后登山者新的位置坐標，

以我們的目標函式 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 為例，（該例子轉載為知乎）

假如設定求解的精度為小數點后4位，可以將x的解空間劃分為 (9-0)×(1e+4)=90000個等分，

2^16<90000<2^17，需要17位二進制數來表示這些解，換句話說，一個解的編碼就是一個17位的二進制串，

一開始，這些二進制串是隨機生成的，一個這樣的二進制串代表一條染色體串，這里染色體串的長度為17，

對于任何一條這樣的染色體chromosome，如何將它復原(解碼)到[0,9]這個區間中的數值呢？

對于本問題，我們可以采用以下公式來解碼：

x = 0 + decimal(chromosome)×(9-0)/(2^17-1)

decimal( ): 將二進制數轉化為十進制數

一般化解碼公式：

f(x), x∈[lower_bound, upper_bound]
x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)

lower_bound: 函式定義域的下限
upper_bound: 函式定義域的上限
chromosome_size: 染色體的長度

通過上述公式，我們就可以成功地將二進制染色體串解碼成[0,9]區間中的十進制實數解，

2.適應度與選擇

1.適應度函式（fitness function）

遺傳演算法中，一個個體(解)的好壞用適應度函式值來評價，在上個問題中，f(x)就是適應度函式，

適應度函式也稱評價函式，是根據目標函式確定的用于區分群體中個體好壞的標準，適應度函式總是非負的，而目標函式可能有正有負，故需要在目標函式與適應度函式之間進行變換，

評價個體適應度的一般程序為：

1. 對個體編碼串進行解碼處理后，可得到個體的表現型，

2. 由個體的表現型可計算出對應個體的目標函式值，

3. 根據最優化問題的型別，由目標函式值按一定的轉換規則求出個體的適應度，

適應度函式是遺傳演算法進化的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定，

2.選擇函式（selection）

我們希望有這樣一個種群，它所包含的個體所對應的函式值都很接近于f(x)在[0,9]上的最大值，但是這個種群一開始可能不那么優秀，因為個體的染色體串是隨機生成的，

如何讓種群變得優秀呢？不斷的進化，

每一次進化都盡可能保留種群中的優秀個體，淘汰掉不理想的個體，并且在優秀個體之間進行染色體交叉，有些個體還可能出現變異，種群的每一次進化，都會產生一個最優個體，種群所有世代的最優個體，可能就是函式f(x)最大值對應的定義域中的點，如果種群無休止地進化，那總能找到最好的解，但實際上，我們的時間有限，通常在得到一個看上去不錯的解時，便終止了進化，

對于給定的種群，如何賦予它進化的能力呢？

• 首先是選擇(selection)
  • 選擇操作是從前代種群中選擇***多對***較優個體，一對較優個體稱之為一對父母，讓父母們將它們的基因傳遞到下一代，直到下一代個體數量達到種群數量上限
  • 在選擇操作前，將種群中個體按照適應度從小到大進行排列
  • 采用輪盤賭選擇方法（當然還有很多別的選擇方法），各個個體被選中的概率與其適應度函式值大小成正比
  • 輪盤賭選擇方法具有隨機性，在選擇的程序中可能會丟掉較好的個體，所以可以使用精英機制，將前代最優個體直接選擇

下面介紹幾種常用的選擇算子：（選擇算子）

1. 輪盤賭選擇（Roulette Wheel Selection）：是一種回放式隨機采樣方法，每個個體進入下一代的概率等于它的適應度值與整個種群中個體適應度值和的比例，選擇誤差較大，

2. 隨機競爭選擇（Stochastic Tournament）：每次按輪盤賭選擇一對個體，然后讓這兩個個體進行競爭，適應度高的被選中，如此反復，直到選滿為止，

3. 最佳保留選擇：首先按輪盤賭選擇方法執行遺傳演算法的選擇操作，然后將當前群體中適應度最高的個體結構完整地復制到下一代群體中，

4. 無回放隨機選擇（也叫期望值選擇Excepted Value Selection）：根據每個個體在下一代群體中的生存期望來進行隨機選擇運算，方法如下:

   （1） 計算群體中每個個體在下一代群體中的生存期望數目N，

   （2） 若某一個體被選中參與交叉運算，則它在下一代中的生存期望數目減去0.5，若某一個體未 被選中參與交叉運算，則它在下一代中的生存期望數目減去1.0，

   （3） 隨著選擇程序的進行，若某一個體的生存期望數目小于0時，則該個體就不再有機會被選中，

5. 確定式選擇：按照一種確定的方式來進行選擇操作，具體操作過程如下：

   （1） 計算群體中各個個體在下一代群體中的期望生存數目N，

   （2） 用N的整數部分確定各個對應個體在下一代群體中的生存數目，

   （3） 用N的小數部分對個體進行降序排列，順序取前M個個體加入到下一代群體中，至此可完全確定出下一代群體中Ｍ個個體，

6. 無回放余數隨機選擇：可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中，因而選擇誤差比較小，

7. 均勻排序：對群體中的所有個體按期適應度大小進行排序，基于這個排序來分配各個個體被選中的概率，

8. 最佳保存策略：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來代替掉本代群體中經過交叉、變異等操作后所產生的適應度最低的個體，

9. 隨機聯賽選擇：每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中，

10. 排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性，

下面以輪盤賭選擇為例給大家講解一下：

假如有５條染色體，他們的適應度分別為５、８、３、７、２，

那么總的適應度為：F = 5 + 8 + 3 + 7 + 2 = 25，

那么各個個體的被選中的概率為：

α1 = ( 5 / 25 ) * 100% = 20%

α2 = ( 8 / 25 ) * 100% = 32%

α3 = ( 3 / 25 ) * 100% = 12%

α4 = ( 7 / 25 ) * 100% = 28%

α5 = ( 2 / 25 ) * 100% = 8%

可以看出，適應性越高的個體被選中的概率就越大，

• 其次是交叉(crossover)
  • 兩個待交叉的不同的染色體(父母)根據交叉概率(cross_rate)按某種方式交換其部分基因
  • 采用單點交叉法，也可以使用其他交叉方法

適用于二進制編碼個體或浮點數編碼個體的交叉算子：

1. 單點交叉（One-point Crossover）：指在個體編碼串中只隨機設定一個交叉點，然后再該點相互交換兩個配對個體的部分染色體，

2. 兩點交叉與多點交叉：

   (1) 兩點交叉（Two-point Crossover）：在個體編碼串中隨機設定了兩個交叉點，然后再進行部分基因交換，

   (2) 多點交叉（Multi-point Crossover）

3. 均勻交叉（也稱一致交叉，Uniform Crossover）：兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新個體，

4. 算術交叉（Arithmetic Crossover）：由兩個個體的線性組合而產生出兩個新的個體，該操作物件一般是由浮點數編碼表示的個體，

對應的二進制交叉：

• 最后是變異(mutation)
  • 染色體按照變異概率(mutate_rate)進行染色體的變異
  • 采用單點變異法，也可以使用其他變異方法

例如下面這串二進制編碼：

101101001011001

經過基因突變后，可能變成以下這串新的編碼：

001101011011001

以下變異算子適用于二進制編碼和浮點數編碼的個體：

• 基本位變異（Simple Mutation）：對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算，

• 均勻變異（Uniform Mutation）：分別用符合某一范圍內均勻分布的亂數，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值，（特別適用于在演算法的初級運行階段）

• 邊界變異（Boundary Mutation）：隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值，特別適用于最優點位于或接近于可行解的邊界時的一類問題，

• 非均勻變異：對原有的基因值做一隨機擾動，以擾動后的結果作為變異后的新基因值，對每個基因座都以相同的概率進行變異運算之后，相當于整個解向量在解空間中作了一次輕微的變動，

• 高斯近似變異：進行變異操作時用符號均值為Ｐ的平均值，方差為P**2的正態分布的一個亂數來替換原有的基因值，

這篇重點介紹原理，下篇將介紹運用Python完成實體操作，

參閱：

百度百科：遺傳演算法

【演算法】超詳細的遺傳演算法(Genetic Algorithm)決議

遺傳演算法詳解（GA）

詳解遺傳演算法

知乎

https://www.zhihu.com/question/23293449/answer/120220974