A. 遺傳演算法-總結
最近在做遺傳演算法的項目，簡單記錄一下。
遺傳演算法是模擬自然界生物進化機制的一種演算法，在尋優過程中有用的保留無用的去除。包括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
B. 遺傳演算法
參考文獻： 知乎 遺傳演算法 編碼解碼知識
實現遺傳演算法的第一步就是明確對求解問題的編碼和解碼方式。對於函數優化問題，一般有兩種編碼方式，各具優缺點
實數編碼：直接用實數表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優
二進制編碼：穩定性高，種群多樣性大，但需要的存儲空間大，需要解碼且難以理解
對於求解函數最大值問題，我選擇的是二進制編碼。
以我們的目標函數 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]這個區間中的數值呢？
對於本問題，我們可以採用以下公式來解碼：
decimal( ): 將二進制數轉化為十進制數
一般化解碼公式：
lower_bound: 函數定義域的下限
upper_bound: 函數定義域的上限
chromosome_size: 染色體的長度
通過上述公式，我們就可以成功地將二進制染色體串解碼成[0,9]區間中的十進制實數解。
染色體，就是指由 DNA 組成的聚合體，DNA 上的每個基因都編碼了一個獨特的性狀，比如，頭發或者眼睛的顏色
可以將他看作是一個優化問題，它可以嘗試找出某些輸入，憑借這些輸入我們便可以得到最佳的輸出值或者是結果
遺傳演算法要點：
1.初始化
初始化候選全體，隨機初始化
2.查找適應函數
3.選擇：物競天擇，適者生存
先選擇能量強的個體，然後再進行隨機選擇，選出適應度雖然小，但是倖存下來的個體
4.交叉：
5.變異：根據需要進行選擇
C. python遺傳演算法如何提升收斂速度
python遺傳鄭緩州演算法採用交叉演算法提升收斂速度法。根據查喊蔽詢相關公開信息顯示交哪櫻叉演算法是一種提升速度的方法，但是加快速度會導致收斂質量的下降。
D. 遺傳演算法出來的結果不穩定
有兩種可能：1.有多種組合等於X，因此組合有多種
2.你的遺傳演算法容易局部收斂
對於2解決辦法：增加判斷，當種群最優染色體一直不變持續N代，重新初始化一個種群，或者往種群中注入新的隨機染色體來跳出局部收斂區域。
對補充的回答：
遺傳演算法本身就是一種智能尋優的隨機演算法，搜索過程中存在隨機性，在具有多個最優解的情況下，很難每次都尋優到同一組參數組合，因為每次的搜索路徑是不同的。
如果樓主真是尋求最後結果一樣的效果的話，可以先得到一組最優組合數字集合S，按從小到大排列處理後變為S'(n1,n2...ni)
然後搜索過程中的某組數字集合Q的目標函數
既滿足：
相加的和最接近X，
還要滿足：
1.數字個數=i
2.臨時將Q從小達到排列，各個位置上的元素和S'的元素最接近
這樣可能會增加很多計算時間，但理論上是可以每次都得到S
E. 遺傳演算法<sup>[1，]</sup>
遺傳演算法，又稱基因演算法(Genetic Algorithm，簡稱GA)，也是一種啟發式蒙特卡洛優化演算法。遺傳演算法最早是由Holland(1975)提出，它模擬了生物適者生存、優勝劣汰的進化過程，具有不依賴於初始模型的選擇、不容易陷入局部極小、在反演過程中不用計算偏導數矩陣等優點。遺傳演算法最早由Stoffa和Sen(1991)用於地震波的一維反演，之後在地球物理資料的非線性反演中得到廣泛的應用。GA演算法對模型群體進行追蹤、搜索，即模型狀態通過模型群體傳送，具有比模擬退火法更大、更復雜的「記憶」，潛力更大。
遺傳演算法在反演中的基本思路和過程是:
(1)將生物體看成模型，模型參數看成染色體，有多少個模型的參數就有多少個染色體。對每個模型的參數(染色體)用二進制進行編碼，這個編碼就是基因。
(2)隨機生成一個模型群體(相當於生物的種群)，然後在模型群體中進行繁殖，通過母本的選擇、交換和變異等遺傳操作產生下一代，然後保留較好基因，淘汰較差基因。
(3)通過一代一代的繁殖優勝劣汰的進化過程，最後所剩下的種群基本上都是最優的基因，種群趨於一致。所謂群體「一致」，即群體目標函數的方差或標准差很小，或者群體目標函數的均值接近於極值(可能是極大值或極小值)，從而獲得非線性反演問題所對應的最優解或近似最優解。
下面以一個實例來簡述遺傳演算法的基本過程。
[例1]設m是正整數，且0≤m≤127，求方程φ(m)=m2的極大值。
這個例子極為簡單，只有一個模型參數，因此只有一條染色體，目標函數的極值是極大值(此例子來自阮百堯課件)。遺傳演算法通過以下7個步驟來實現:
(1)模型參數二進制編碼。
每個模型參數就是一條染色體，把十進制的模型參數表示為二進制，這就是基因。首先確定二進制碼的長度(基因的長度):
2N=[mmax(i)-mmin(i)]/Δm(i) (8.20)
其中:N為第i條染色體基因的長度(也就是第i個模型參數的二進制碼位數);[mmin(i)，mmax(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(mi)為繁殖概率;φ(mi)為第i個模型的目標函數;φAVG為目標函數的平均值。對於極小化問題來說，規定目標函數值高於平均值的不傳代;對於極大化問題來說，反之即可。
就[例1]來說，要求目標函數取極大值，所以規定目標函數小於平均值的模型不傳代，大於它的可以傳代。對第一代，為了防止基因丟失，可先不捨去繁殖概率小的模型，讓它與概率大的模型配對。如:本例中70與56配對，101與15配對產生子代，見表8.2。
表8.2 基因交換表
(4)基因交換。
將配對的兩個親本模型的部分染色體相互交換，其中交換點可隨機選擇，形成兩個新的子代(見表8.2)。兩個染色體遺傳基因的交換過程是遺傳演算法的「繁殖」過程，是母本的重組過程。
為了使染色體的基因交換比較徹底，Stoffa等人提出了一個交換概率px來控制選擇操作的效果。如果px的值較小，那麼交換點的位置就比較靠低位，這時的交換操作基本是低位交換，交換前後模型的染色體變化不是太大。如果px的值較大，那麼交換點的位置就比較靠高位，此時的交換操作可以在較大的染色體空間進行，交換前後模型數值變化可以很大。
在[例1]中:15、101和56、70作為母本通過交換繁殖出子代5、6、111、120。所選擇的基因交換位置見表8.2。有下劃線的，是要交換的基因位置。
(5)更新。
母本模型和子本模型如何選擇保留一定數量作為新的母本，就是模型更新。不同的策略會導致不同的結果。一般而言，若產生的新一代模型較好，則選擇新一代模型而淘汰上一代模型。否則，則必須根據一定的更新概率pu來選擇上一代模型來取代新一代中某些較劣的模型。
經過更新以後，繁殖時對子代再進行優勝劣汰的選擇。對於極大值問題，大於目標函數平均值的子代可以繁殖，小於目標函數平均值的子代不能繁殖。由於新的種群能繁殖的個體數量減小了，所以要多繁殖幾次，維持種群個體的數量保持平衡。
在[例1]中，子代較好，所以完全淘汰上一代模型，完全用子代作為新的母本。選擇子代目標函數最大的兩個模型進行繁殖，分別是111、120。
(6)基因變異。
在新的配對好的母本中，按一定比例隨機選擇模型進行變異，變異操作就是模擬自然界中的環境因素，就是按比較小的變異概率pm將染色體某位或某幾位的基因發生突變(即將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、變異概率pm以及更新概率pu，這些參數的選擇與設定目前尚無統一的理論指導，多數都視具體問題而定。Stoffa等(1991)的研究表明，適中的交換概率(px≈0.6)、較小的變異概率(pm≈0.01)和較大的更新概率(pu≈0.9)，遺傳演算法的性能較優。
與模擬退火反演演算法相同，遺傳演算法與傳統的線性反演方法相比，該方法具有:不依賴初始模型的選擇、能尋找全局最小點而不陷入局部極小、在反演過程中不用計算雅克比偏導數矩陣等優點。另外，遺傳演算法具有並行性，隨著並行計算和集群式計算機技術的發展，該演算法將會得到越來越廣泛的研究與應用。
但是遺傳演算法作為類蒙特卡洛演算法同樣需要進行大量的正演計算，種群個體數量越大，繁衍代數越多，則計算量越大。所以和前面的最小二乘法相比，速度不是它的優勢。