遺傳演算法如何提前終止

『壹』 遺傳演算法^[1，]

遺傳演算法，又稱基因演算法(Genetic Algorithm，簡稱GA)，也是一種啟發式蒙特卡洛優化演算法。遺傳演算法最早是由Holland(1975)提出，它模擬了生物適者生存、優勝劣汰的進化過程，具有不依賴於初始模型的選擇、不容易陷入局部極小、在反演過程中不用計算偏導數矩陣等優點。遺傳演算法最早由Stoffa和Sen(1991)用於地震波的一維反演，之後在地球物理資料的非線性反演中得到廣泛的應用。GA演算法對模型群體進行追蹤、搜索，即模型狀態通過模型群體傳送，具有比模擬退火法更大、更復雜的「記憶」，潛力更大。

遺傳演算法在反演中的基本思路和過程是:

(1)將生物體看成模型，模型參數看成染色體，有多少個模型的參數就有多少個染色體。對每個模型的參數(染色體)用二進制進行編碼，這個編碼就是基因。

(2)隨機生成一個模型群體(相當於生物的種群)，然後在模型群體中進行繁殖，通過母本的選擇、交換和變異等遺傳操作產生下一代，然後保留較好基因，淘汰較差基因。

(3)通過一代一代的繁殖優勝劣汰的進化過程，最後所剩下的種群基本上都是最優的基因，種群趨於一致。所謂群體「一致」，即群體目標函數的方差或標准差很小，或者群體目標函數的均值接近於極值(可能是極大值或極小值)，從而獲得非線性反演問題所對應的最優解或近似最優解。

下面以一個實例來簡述遺傳演算法的基本過程。

[例1]設m是正整數，且0≤m≤127，求方程φ(m)=m²的極大值。

這個例子極為簡單，只有一個模型參數，因此只有一條染色體，目標函數的極值是極大值(此例子來自阮百堯課件)。遺傳演算法通過以下7個步驟來實現:

(1)模型參數二進制編碼。

每個模型參數就是一條染色體，把十進制的模型參數表示為二進制，這就是基因。首先確定二進制碼的長度(基因的長度):

2^N=[m_max(i)-m_min(i)]/Δm(i) (8.20)

其中:N為第i條染色體基因的長度(也就是第i個模型參數的二進制碼位數);[m_min(i)，m_max(i)]為第i個模型參數的取值范圍;Δm(i)為第i個模型參數的解析度。這樣就把模型參數離散化了，它只能按Δm(i)的整數倍變化。基因的長度按下式計算:

地球物理反演教程

其中:c為實數;N為基因長度，是整數;int[ ]為取整函數。上式表示如果c不是整數，那麼基因長度N就是對c取整後加1，這樣保證最小解析度。

基因的編碼按下式進行:

地球物理反演教程

其中:式(8.22)是編碼公式;k為基因編碼的十進制數，是整數;int[ ]為取整函數。把k轉化為二進制就是基因的編碼。解碼是按照式(8.23)進行的。首先把一個基因的二進制編碼轉化為十進制數k，然後按式(8.23)可以計算出第i個模型參數m(i)的十進制值。

例如:電阻率參數ρ(1)，它的變化范圍為10~5000Ω·m，解析度為2Ω·m，設當前參數ρ(1)=133Ω·m，按式(8.21)計算得

c=11.28482，N=12

所以二進制基因長度為13位。

利用式(8.22)計算基因編碼k的十進制數:

k=int[(133-10)/2]=61

把它轉化為二進制數為:000000111101。所以ρ(1)=133 的二進制基因編碼為:000000111101。

解碼過程就是把二進制基因編碼變為十進制數k後用式(8.23)計算:

ρ(1)=10+61×2=132(Ω·m)

注意:基因編碼並不是直接把電阻率值變為二進制。此外，133這個值在基因里不會出現，因為解析度是2，所以表示為最接近的132。

對於[例1]問題來說，選解析度為1，0~127用二進制編碼需7位。

(2)產生初始模型種群。

生物繁殖進化需要一定數量的生物體種群，因此遺傳演算法開始時需要一定數量的初始模型。為保證基因的多樣性，隨機產生大量的初始模型作為初始種群，按照上面的編碼方式進行編碼。個體在模型空間中應分布均勻，最好是模型空間各代表區域均有成員。初始模型群體大，有利於搜索，但太大會增加計算量。

為保證演算法收斂，在初始模型群體中，有時候應增加各位都為0和都為1的成員。遺傳演算法就是在這個初始模型種群的基礎上進行繁殖，進化求解的。

對於[例1]問題來說，模型空間是0~127個數字，這樣初始種群最多具有128個個體。為了簡單，隨機選擇4個個體作為初始種群。初始種群的編碼、目標函數值見表8.1。

表8.1 初始種群編碼表

(3)模型選擇。

為了生成新一代模型，需要選擇較優的個體進行配對。生物進化按照自然選擇、優勝劣汰的准則進行。對應地，遺傳演算法按照一定的准則來選擇母本(兩個)，然後進行配對繁殖下一代模型，這個選擇稱為模型選擇。模型配對最基本的方法是隨機采樣，用各模型的目標函數值對所有模型目標函數的平均值的比值定義繁殖概率，即

地球物理反演教程

其中:p(m_i)為繁殖概率;φ(m_i)為第i個模型的目標函數;φ_AVG為目標函數的平均值。對於極小化問題來說，規定目標函數值高於平均值的不傳代;對於極大化問題來說，反之即可。

就[例1]來說，要求目標函數取極大值，所以規定目標函數小於平均值的模型不傳代，大於它的可以傳代。對第一代，為了防止基因丟失，可先不捨去繁殖概率小的模型，讓它與概率大的模型配對。如:本例中70與56配對，101與15配對產生子代，見表8.2。

表8.2 基因交換表

(4)基因交換。

將配對的兩個親本模型的部分染色體相互交換，其中交換點可隨機選擇，形成兩個新的子代(見表8.2)。兩個染色體遺傳基因的交換過程是遺傳演算法的「繁殖」過程，是母本的重組過程。

為了使染色體的基因交換比較徹底，Stoffa等人提出了一個交換概率p_x來控制選擇操作的效果。如果p_x的值較小，那麼交換點的位置就比較靠低位，這時的交換操作基本是低位交換，交換前後模型的染色體變化不是太大。如果p_x的值較大，那麼交換點的位置就比較靠高位，此時的交換操作可以在較大的染色體空間進行，交換前後模型數值變化可以很大。

在[例1]中:15、101和56、70作為母本通過交換繁殖出子代5、6、111、120。所選擇的基因交換位置見表8.2。有下劃線的，是要交換的基因位置。

(5)更新。

母本模型和子本模型如何選擇保留一定數量作為新的母本，就是模型更新。不同的策略會導致不同的結果。一般而言，若產生的新一代模型較好，則選擇新一代模型而淘汰上一代模型。否則，則必須根據一定的更新概率p_u來選擇上一代模型來取代新一代中某些較劣的模型。

經過更新以後，繁殖時對子代再進行優勝劣汰的選擇。對於極大值問題，大於目標函數平均值的子代可以繁殖，小於目標函數平均值的子代不能繁殖。由於新的種群能繁殖的個體數量減小了，所以要多繁殖幾次，維持種群個體的數量保持平衡。

在[例1]中，子代較好，所以完全淘汰上一代模型，完全用子代作為新的母本。選擇子代目標函數最大的兩個模型進行繁殖，分別是111、120。

(6)基因變異。

在新的配對好的母本中，按一定比例隨機選擇模型進行變異，變異操作就是模擬自然界中的環境因素，就是按比較小的變異概率p_m將染色體某位或某幾位的基因發生突變(即將0變為1或將1變為0)。

變異操作的作用是使原來的模型發生某些變化，從而成為新的個體。這樣可使群體增加多樣性。變異操作在遺傳演算法中也起著至關重要的作用。實際上，由於搜索空間的性質和初始模型群體的優劣，遺傳演算法搜索過程中往往會出現所謂的「早熟收斂」現象，即在進化過程中早期陷入局部解而中止進化。採用合適的變異策略可提高群體中個體的多樣性，從而防止這種現象的出現，有助於模型跳出局部極值。表8.3為[例1]的基因變異繁殖表。

表8.3 基因變異繁殖表

在[例1]中，用111、120分別繁殖兩次，形成4個子代，維持種群數量平衡。隨機選擇120進行變異，變異的位數也是隨機的。這里把它的第2位進行變異，即從1變為0，繁殖後形成子代為:70、110、121、127。可以看出新的子代比初始種群要好得多，其中甚至已經出現了最優解。如果對於地球物理的極小值問題，我們可以預先設置一個擬合精度，只要在種群中出現一個達到擬合精度的模型就可以終止反演了。

(7)收斂。

重復(3)~(6)的步驟，模型群體經多次選擇、交換、更新、變異後，種群個體數量大小不變，模型目標函數平均值趨於穩定，最後聚集在模型空間中一個小范圍內，則找到了全局極值對應的解，使目標函數最大或最小的模型就是全局最優模型。

對於具有多解性的地球物理反演問題來說，通過這一步有可能找到滿足擬合精度的多個模型，對於實際反演解釋、推斷具有較高的指導意義。

遺傳演算法中的各種概率包括交換概率px、變異概率p_m以及更新概率p_u，這些參數的選擇與設定目前尚無統一的理論指導，多數都視具體問題而定。Stoffa等(1991)的研究表明，適中的交換概率(p_x≈0.6)、較小的變異概率(p_m≈0.01)和較大的更新概率(p_u≈0.9)，遺傳演算法的性能較優。

與模擬退火反演演算法相同，遺傳演算法與傳統的線性反演方法相比，該方法具有:不依賴初始模型的選擇、能尋找全局最小點而不陷入局部極小、在反演過程中不用計算雅克比偏導數矩陣等優點。另外，遺傳演算法具有並行性，隨著並行計算和集群式計算機技術的發展，該演算法將會得到越來越廣泛的研究與應用。

但是遺傳演算法作為類蒙特卡洛演算法同樣需要進行大量的正演計算，種群個體數量越大，繁衍代數越多，則計算量越大。所以和前面的最小二乘法相比，速度不是它的優勢。

『貳』 基因遺傳演算法的終止條件一般是適應度數值小於0.()

基因遺傳演算法的終止條件一般是適應度數值小於0。是對的。

遺傳演算法便基於達爾文的進化論，模擬了自然選擇，物競天擇、適者生存，通過N代的遺傳、變異、交叉、復制，進化出問題的最優解。

『叄』 遺傳演算法原理簡介

遺傳演算法（Genetic Algorithm, GA）是一種進化計算（Evolutionary Computing）演算法，屬於人工智慧技術的一部分。遺傳演算法最早是由John Holland和他的學生發明並改進的，源於對達芬奇物種進化理論的模仿。在物種進化過程中，為了適應環境，好的基因得到保留，不好的基因被淘汰，這樣經過很多代基因的變化，物種的基因就是當前自然環境下適應度最好的基因。該演算法被廣泛應用於優化和搜索中，用於尋求最優解（或最優解的近似），其最主要的步驟包括交叉（crossover）和突變（mutation）。

所有的生物體都由細胞組成，每個細胞中都包含了同樣的染色體（chromosome）。染色體由一串DNA組成，我們可以簡單地把一個生物個體表示為一條染色體。每條染色體上都包含著基因，而基因又是由多個DNA組成的。每個基因都控制著個體某個性狀的表達，例如眼睛的顏色、眼皮的單雙等。在物種繁衍的過程中，首先發生交叉，來自於父母的染色體經過分裂和重組，形成後代的染色體。之後，後代有一定概率發生基因突變，即染色體上某個位置處的基因以一定概率發生變化。之後，對每一代都重復進行交叉和突變兩個步驟。對於每一個後代，我們可以通過一定的方式測量其適應度。適應度越好的個體，在下一次交叉中被選中的概率越大，它的基因越容易傳給下一代。這樣，後代的適應度就會越來越好，直到收斂到一個穩定值。

在優化問題中，可行解總是有很多個，我們希望尋找一個最優解，它相對於其他可行解來說具有更好的適應度（即目標函數值更大或更小）。每個可行解就是一個「生物個體」，可以表示為狀態空間中的一個點和適應度。每個解都是一個經過編碼的序列，已二進制編碼為例，每個解都是一個二進制序列。這樣每個染色體就是一個二進制序列。遺傳演算法從從一組可行解開始，稱為population，從population中隨機選擇染色體進行交叉產生下一代。這一做法的基於下一代的適應度會好於上一代。遺傳演算法的過程如下：

終止條件可以是達到了最大迭代次數，或者是前後連續幾代的最優染色體的適應度差值小於一個閾值。以上演算法描述也許還不夠直觀，我們舉例說明。假設解可以用二進制編碼表示，則每個染色體都是一個二進制序列。假設序列長度為16，則每個染色體都是一個16位的二進制序列：

首先，我們隨機生成一個population，假設population size為20，則有20個長度為16的二進制序列。計算每個染色體的適應度，然後選取兩個染色體進行交叉，如下圖所示。下圖在第6為上將染色體斷開再重組，斷開的位置是可以隨機選擇的。當然，斷裂位置也可以不止一個。可以根據具體問題選擇具體的交叉方式來提升演算法性能。

之後，隨機選取後代染色體上某個基因發生基因突變，突變的位置是隨機選取的。並且，基因突變並不是在每個後代上都會發生，只是有一定的概率。對於二進制編碼，基因突變的方式是按位取反：

上述例子是關於二進制編碼的，像求解一元函數在某個區間內的最大最小值就可以使用二進制編碼。例如，求解函數f(x)=x+sin(3x)+cos(3x)在區間[0,6]內的最小值。假設我們需要最小值點x保留4位小數，那麼求解區間被離散成60000個數。因為2 {15}<60000<2 {16}，所以，需要16位二進制數來表示這60000個可能的解。其中0x0000表示0，0x0001表示0.0001，以此類推。針對這個例子，文末給出了demo code．

然而，在排序問題中無法使用二進制編碼，應該採用排列編碼（permutation encoding）。例如有下面兩個染色體：

交叉：隨機選取一個交叉點，從該出將兩個染色體斷開。染色體A的前部分組成後代1的前部分，然後掃描染色體B，如果出現了後代1中不包含的基因，則將其順序加入後代1中。同理，染色體B的前部分組成了後代2的前部分，掃描染色體A獲得後代2的後部分。注意，交叉的方式多種多樣，此處只是舉出其中一種方式。

( 1 5 3 2 6 | 4 7 9 8) + ( 8 5 6 7 2 | 3 1 4 9) => ( 1 5 3 2 6 8 7 4 9) + ( 8 5 6 7 2 1 3 4 9)

突變：對於一個染色體，隨機選中兩個基因互換位置。例如第3個基因和倒數第2個基因互換：

(1 5 3 2 6 8 7 4 9) => (1 5 4 2 6 8 7 3 9)

此外還有值編碼（value encoding）和樹編碼（tree encoding）等，具體例子可以參考這個鏈接： http://obitko.com/tutorials/genetic-algorithms/encoding.php

在實際的遺傳演算法中，往往會保留上一代中的少數幾個精英（elite），即將上一代population中適應度最好的幾個染色體加入到後代的poulation中，同時去除後代population中適應度最差的幾個染色體。通過這個策略，如果在某次迭代中產生了最優解，則最優解能夠一直保留到迭代結束。

用GA求函數最小值的demo code： https://github.com/JiaxYau/GA_test

參考資料 ：

[1] Introction to Genetic Algorithm, http://obitko.com/tutorials/genetic-algorithms/index.php

[2] Holland J H. Adaption in natural and artificial systems

『肆』 遺傳演算法怎麼判斷何時為最優解

適應度越大，解越優。
判斷是否已得到近似全局最優解的方法就是遺傳演算法的終止條件。 在最大迭代次數范圍內可以選擇下列條件之一作為終止條件：
1. 最大適應度值和平均適應度值變化不大、趨於穩定；
2. 相鄰GAP代種群的距離小於可接受值，參考「蔣勇，李宏.改進NSGA—II終止判斷准則[J].計算機模擬.2009. Vol.26 No.2」

『伍』 遺傳演算法怎麼回事

遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳演算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。對於一個求函數最大值的優化問題(求函數最小值也類同)，一般可以描述為下列數學規劃模型: 遺傳演算法式中為決策變數，為目標函數式，式2-2、2-3為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。遺傳演算法的基本運算過程如下:a)初始化:設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。b)個體評價:計算群體P(t)中各個個體的適應度。c)選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。d)交叉運算；將交叉運算元作用於群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳演算法中起核心作用的就是交叉運算元。e)變異運算:將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t 1)。f)終止條件判斷:若tT,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算

『陸』 遺傳演算法

優化的演算法有很多種，從最基本的梯度下降法到現在的一些啟發式演算法，如遺傳演算法(GA)，差分演化演算法(DE)，粒子群演算法(PSO)和人工蜂群演算法(ABC)。

舉一個例子，遺傳演算法和梯度下降：

梯度下降和遺傳演算法都是優化演算法，而梯度下降只是其中最基礎的那一個，它依靠梯度與方向導數的關系計算出最優值。遺傳演算法則是優化演算法中的啟發式演算法中的一種，啟發式演算法的意思就是先需要提供至少一個初始可行解，然後在預定義的搜索空間高效搜索用以迭代地改進解，最後得到一個次優解或者滿意解。遺傳演算法則是基於群體的啟發式演算法。

遺傳演算法和梯度下降的區別是：

1.梯度下降使用誤差函數決定梯度下降的方向，遺傳演算法使用目標函數評估個體的適應度
2.梯度下降是有每一步都是基於學習率下降的並且大部分情況下都是朝著優化方向迭代更新，容易達到局部最優解出不來；而遺傳演算法是使用選擇、交叉和變異因子迭代更新的，可以有效跳出局部最優解
3.遺傳演算法的值可以用二進制編碼表示，也可以直接實數表示

遺傳演算法如何使用它的內在構造來算出 α 和 β ：

主要講一下選擇、交叉和變異這一部分：
1.選擇運算:將選擇運算元作用於群體。選擇的目的是把優秀（適應值高）的個體直接遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

2.交叉運算：將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。交叉運算元是將種群中的個體兩兩分組，按一定概率和方式交換部分基因的操作。將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。例如：（根據概率選取50個個體，兩兩配對，交換x,y，比如之前兩個是(x1,y1),(x2,y2)，之後變成了（x1,y2）,(x2,y1)）

3.變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。（x2可能變為x2+δ，y1變為y1+δ）
種群P(t)經過選擇、交叉、變異運算之後得到下一代種群P(t+1)。

遺傳演算法就是通過對大量的數據個體使用選擇、交叉和變異方式來進化，尋找適合問題的最優解或者滿意解。

遺傳演算法參數的用處和設置：

1.編碼選擇：通常使用二進制編碼和浮點數編碼，二進制適合精度要求不高、特徵較少的情況。浮點數適合精度高、特徵多的情況
2.種群：種群由個體組成，個體中的每個數字都代表一個特徵，種群個體數量通常設置在40-60之間；迭代次數通常看情況定若計算時間較長可以在100內，否則1000以內都可以。
3.選擇因子：通常有輪盤賭選擇和錦標賽選擇，輪盤賭博的特點是收斂速度較快，但優勢個體會迅速繁殖，導致種群缺乏多樣性。錦標賽選擇的特點是群多樣性較為豐富，同時保證了被選個體較優。
4.交叉因子：交叉方法有單點交叉和兩點交叉等等，通常用兩點交叉。交叉概率則選擇在0.7-0.9。概率越低收斂越慢時間越長。交叉操作能夠組合出新的個體，在串空間進行有效搜索，同時降低對種群有效模式的破壞概率。
5.變異因子：變異也有變異的方法和概率。方法有均勻變異和高斯變異等等；概率也可以設置成0.1。變異操作可以改善遺傳演算法的局部搜索能力，豐富種群多樣性。
6.終止條件：1、完成了預先給定的進化代數；2、種群中的最優個體在連續若干代沒有改進或平均適應度在連續若干代基本沒有改進；3、所求問題最優值小於給定的閾值.

『柒』 遺傳演算法的基本原理

遺傳演算法通常的實現方式，就是用程序來模擬生物種群進化的過程。對於一個求最優解的問題，我們可以把一定數量的候選解（稱為個體）抽象地表示為染色體，使種群向更好的解來進化。大家知道，使用演算法解決問題的時候，解通常都是用數據或者字元串等表示的，而這個數據或字元串對應到生物中就是某個個體的「染色體」。進化從完全隨機個體的種群開始，之後一代一代發生。在每一代中評價其在整個種群的適應度，從當前種群中隨機地選擇多個個體（基於它們的適應度），通過自然選擇和突變產生新的種群，該種群在演算法的下一次迭代中成為當前種群。其具體的計算步驟如下：
編碼：將問題空間轉換為遺傳空間；
生成初始種群：隨機生成P個染色體；
種群適應度計算：按照確定的適應度函數，計算各個染色體的適應度；
選擇：根據染色體適應度，按照選擇運算元進行染色體的選擇；
交叉：按照交叉概率對被選擇的染色體進行交叉操作，形成下一代種群；
突變：按照突變概率對下一代種群中的個體進行突變操作；
返回第3步繼續迭代，直到滿足終止條件。

『捌』 遺傳演算法的運算過程

遺傳操作是模擬生物基因遺傳的做法。在遺傳演算法中，通過編碼組成初始群體後，遺傳操作的任務就是對群體的個體按照它們對環境適應度(適應度評估)施加一定的操作，從而實現優勝劣汰的進化過程。從優化搜索的角度而言，遺傳操作可使問題的解，一代又一代地優化，並逼近最優解。
遺傳操作包括以下三個基本遺傳運算元(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。這三個遺傳運算元有如下特點：
個體遺傳運算元的操作都是在隨機擾動情況下進行的。因此，群體中個體向最優解遷移的規則是隨機的。需要強調的是，這種隨機化操作和傳統的隨機搜索方法是有區別的。遺傳操作進行的高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。
遺傳操作的效果和上述三個遺傳運算元所取的操作概率，編碼方法，群體大小，初始群體以及適應度函數的設定密切相關。 從群體中選擇優勝的個體，淘汰劣質個體的操作叫選擇。選擇運算元有時又稱為再生運算元(reproction operator)。選擇的目的是把優化的個體(或解)直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的，目前常用的選擇運算元有以下幾種：適應度比例方法、隨機遍歷抽樣法、局部選擇法。
其中輪盤賭選擇法 （roulette wheel selection）是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應度值成比例。設群體大小為n，其中個體i的適應度為，則i 被選擇的概率，為遺傳演算法
顯然，概率反映了個體i的適應度在整個群體的個體適應度總和中所佔的比例。個體適應度越大。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率後，為了選擇交配個體，需要進行多輪選擇。每一輪產生一個[0，1]之間均勻隨機數，將該隨機數作為選擇指針來確定被選個體。個體被選後，可隨機地組成交配對，以供後面的交叉操作。 在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳演算法中起核心作用的是遺傳操作的交叉運算元。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳演算法的搜索能力得以飛躍提高。
交叉運算元根據交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。根據編碼表示方法的不同，可以有以下的演算法：
a)實值重組（real valued recombination）
1)離散重組（discrete recombination）
2)中間重組（intermediate recombination）
3)線性重組（linear recombination）
4)擴展線性重組（extended linear recombination）。
b)二進制交叉（binary valued crossover）
1)單點交叉（single-point crossover）
2)多點交叉（multiple-point crossover）
3)均勻交叉（uniform crossover）
4)洗牌交叉（shuffle crossover）
5)縮小代理交叉（crossover with reced surrogate）。
最常用的交叉運算元為單點交叉(one-point crossover)。具體操作是:在個體串中隨機設定一個交叉點，實行交叉時，該點前或後的兩個個體的部分結構進行互換，並生成兩個新個體。下面給出了單點交叉的一個例子：
個體A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新個體
個體B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新個體 變異運算元的基本內容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同，可以有以下的演算法：
a)實值變異
b)二進制變異。
一般來說，變異運算元操作的基本步驟如下：
a)對群中所有個體以事先設定的變異概率判斷是否進行變異
b)對進行變異的個體隨機選擇變異位進行變異。
遺傳演算法引入變異的目的有兩個:一是使遺傳演算法具有局部的隨機搜索能力。當遺傳演算法通過交叉運算元已接近最優解鄰域時，利用變異運算元的這種局部隨機搜索能力可以加速向最優解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優解的積木塊會因變異而遭到破壞。二是使遺傳演算法可維持群體多樣性，以防止出現未成熟收斂現象。此時收斂概率應取較大值。
遺傳演算法中，交叉運算元因其全局搜索能力而作為主要運算元，變異運算元因其局部搜索能力而作為輔助運算元。遺傳演算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當群體在進化中陷於搜索空間中某個超平面而僅靠交叉不能擺脫時，通過變異操作可有助於這種擺脫。所謂相互競爭，是指當通過交叉已形成所期望的積木塊時，變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作，是目前遺傳演算法的一個重要研究內容。
基本變異運算元是指對群體中的個體碼串隨機挑選一個或多個基因座並對這些基因座的基因值做變動(以變異概率P.做變動)，(0，1)二值碼串中的基本變異操作如下：
基因位下方標有*號的基因發生變異。
變異率的選取一般受種群大小、染色體長度等因素的影響，通常選取很小的值，一般取0.001－0.1。 當最優個體的適應度達到給定的閾值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，演算法終止。預設的代數一般設置為100-500代。

『玖』 遺傳演算法-總結

最近在做遺傳演算法的項目，簡單記錄一下。
遺傳演算法是模擬自然界生物進化機制的一種演算法，在尋優過程中有用的保留無用的去除。包括3個基本的遺傳運算元：選擇（selection）、交叉（crossover）和變異（mutation）。遺傳操作的效果與上述3個遺傳運算元所取的操作概率、編碼方法、群體大小、初始群體，以及適應度函數的設定密切相關。
1、種群初始化
popsize 種群大小，一般為20-100，太小會降低群體的多樣性，導致早熟；較大會影響運行效率；迭代次數一般100-500；交叉概率：0.4-0.99，太小會破壞群體的優良模式；變異概率：0.001-0.1，太大搜索趨於隨機。編碼包括實數編碼和二進制編碼，可以參考遺傳演算法的幾個經典問題，TSP、背包問題、車間調度問題。
2、選擇
目的是把優化個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代，我大部分採用了輪盤賭的方法。具體可參考 http://my.oschina.net/u/1412321/blog/192454 輪盤賭方法各個個體的選擇概率和其適應值成比例，個體適應值越大，被選擇的概率也越高，反之亦然。在實際問題中，經常需要最小值作為最優解，有以下幾種方法進行轉換
a、0-1之間的數據，可以用1-該數值，則最小值與最大值互換；
b、 求倒數；
c、求相反數；
以上幾種方法均可以將最大值變為最小值，最小值變為最大值，便於利用輪盤賭選擇最優個體，根據實際情況來確定。
3、交叉
交叉即將兩個父代個體的部分結構加以替換重組而生成新個體的操作，通過交叉，遺傳演算法的搜索能力得以飛躍提高。根據編碼方法的不同，可以有以下的演算法：
a、實值重組
離散重組、中間重組、線性重組、擴展線性重組
b、二進制交叉
單點交叉、多點交叉、均勻交叉、洗牌交叉、縮小代理交叉
4、變異
基本步驟：對群中所有個體以事先設定的變異概率判斷是否進行變異；對進行變異的個體隨機選擇變異位進行變異。根據編碼表示方法的不同，有實值變異和二進制變異
變異的目的：
a、使遺傳演算法具有局部的隨機搜索能力。當遺傳演算法通過交叉運算元已接近最優解鄰域時，利用變異運算元的這種局部搜索能力可以加速向最優解收斂。顯然該情況下變異概率應取較小值，否則接近最優解的積木塊會因為變異遭到破壞。
b、使遺傳演算法可維持多樣性，以防止未成熟收斂現象。此時收斂概率應取較大值。
變異概率一般取0.001-0.1。
5、終止條件
當最優個體的適應度達到給定的閾值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，演算法終止。預設代數一般為100-500。
6、其它
多變數：將多個變數依次連接
多目標：一種方法是轉化為單目標，例如按大小進行排序，根據排序和進行選擇，可以參考 https://blog.csdn.net/paulfeng20171114/article/details/82454310