遺傳配對演算法
Ⅰ 遺傳演算法<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)，遺傳演算法的性能較優。
與模擬退火反演演算法相同，遺傳演算法與傳統的線性反演方法相比，該方法具有:不依賴初始模型的選擇、能尋找全局最小點而不陷入局部極小、在反演過程中不用計算雅克比偏導數矩陣等優點。另外，遺傳演算法具有並行性，隨著並行計算和集群式計算機技術的發展，該演算法將會得到越來越廣泛的研究與應用。
但是遺傳演算法作為類蒙特卡洛演算法同樣需要進行大量的正演計算，種群個體數量越大，繁衍代數越多，則計算量越大。所以和前面的最小二乘法相比，速度不是它的優勢。
Ⅱ 遺傳演算法--GA
遺傳演算法（GA）屬於 人工智慧啟發式演算法 ，啟發式演算法的目標就是 尋找原始問題的最優解 ，該演算法的定義為
人類通過直觀常識和生活經驗，設計出一種以搜索最優解為目的，通過模擬大自然規律的演算法，該演算法在可以在接受的花銷（計算時間和存儲空間）范圍內找到問題實例的一個可行解，且該可行解和真實最優解的誤差一般不可以被估計
當下主要有的啟發式演算法包括 遺傳演算法、退火法，蟻群演算法、人工神經網路等 ，這篇文章主要介紹遺傳演算法
遺傳演算法的基本原理是模擬達爾文進化論 "物競天擇，適者生存" 的自然法則，其核心思想為
（1）將原始問題的參數，抽象為基因編碼
（2）將原始問題的可行解，抽象為基因排列的染色體組合
（3）將原始問題的解集規模，抽象為一定數量染色體組成的種群
（4）尋找可行解的過程，抽象為種群的進化過程（染色體選擇、交叉、變異等）
（5）比較可行解的優劣，抽象為量化比較不同種群對當前環境的適應程度
（6）逼近最優解的過程，抽象為淘汰適應度差的種群，保留適應度高的種群進行下一次進化
（7）問題的最優解，抽象為經過多次進化後，最終生存下來的精英種群
理論上，通過有限次種群進化，生存下來的種群都是 精英染色體 ，是最適合當前環境條件的種群，也就可以無限逼近原始問題的最優解
相關生物學術語：
為了大家更好了解遺傳演算法，在此之前先簡單介紹一下相關生物學術語，大家了解一下即可。
基因型(genotype)：性狀染色體的內部表現；
表現型(phenotype)：染色體決定的性狀的外部表現，或者說，根據基因型形成的個體的外部表現；
進化(evolution)：種群逐漸適應生存環境，品質不斷得到改良。生物的進化是以種群的形式進行的。
適應度(fitness)：度量某個物種對於生存環境的適應程度。
選擇(selection)：以一定的概率從種群中選擇若干個個體。一般，選擇過程是一種基於適應度的優勝劣汰的過程。
復制(reproction)：細胞分裂時，遺傳物質DNA通過復制而轉移到新產生的細胞中，新細胞就繼承了舊細胞的基因。
交叉(crossover)：兩個染色體的某一相同位置處DNA被切斷，前後兩串分別交叉組合形成兩個新的染色體。也稱基因重組或雜交；
變異(mutation)：復制時可能（很小的概率）產生某些復制差錯，變異產生新的染色體，表現出新的性狀。
編碼(coding)：DNA中遺傳信息在一個長鏈上按一定的模式排列。遺傳編碼可看作從表現型到基因型的映射。
解碼(decoding)：基因型到表現型的映射。
個體（indivial）：指染色體帶有特徵的實體；
種群（population）：個體的集合，該集合內個體數稱為種群
大體實現過程
遺傳演算法中每一條染色體，對應著遺傳演算法的一個解決方案，一般我們用適應性函數（fitness function）來衡量這個解決方案的優劣。所以從一個基因組到其解的適應度形成一個映射。 遺傳演算法的實現過程實際上就像自然界的進化過程那樣。
基本遺傳演算法概述
1.[開始]生成n個染色體的隨機群體（適合該問題的解決方案）
2.[適應度]評估群體中每個染色體x的適應度f（x）
3.[新種群]通過重復以下來創建新種群直到新種群完成的步驟
3.1 [選擇]根據種群的適合度選擇兩個親本染色體（更好的適應性，更大的選擇機會）
3.2 [交叉]以交叉概率跨越父母形成新的後代（兒童） ）。如果沒有進行交叉，後代就是父母的確切副本。
3.3 [突變]突變概率突變每個基因座（染色體中的位置）的新後代。
4.[接受]在新種群中放置新後代[替換]使用新生成的種群進一步運行演算法
5.[測試]如果滿足結束條件，則停止並返回當前種群中的最佳解
6。[循環]轉到步驟2
影響GA的因素
從遺傳演算法概述可以看出，交叉和變異是遺傳演算法中最重要的部分。性能主要受這兩個因素的影響。在我們解釋有關交叉和變異的更多信息之前，我們將給出一些有關染色體的信息。
染色體編碼
染色體應該以某種方式包含它所代表的解決方案的信息。最常用的編碼方式是二進制字元串。然後染色體看起來像這樣：
每個染色體由二進制字元串表示。字元串中的每個位都可以表示解決方案的一些特徵。另一種可能性是整個字元串可以表示一個數字 - 這已在基本的GA小程序中使用。當然，還有許多其他的編碼方式。編碼主要取決於解決的問題。例如，可以直接編碼整數或實數，有時對某些排列等進行編碼很有用。
染色體交叉
在我們確定了將使用的編碼之後，我們可以繼續進行交叉操作。 Crossover對來自親本染色體的選定基因進行操作並產生新的後代。最簡單的方法是隨機選擇一些交叉點，並在此點之前從第一個父項復制所有內容，然後在交叉點之後復制另一個父交叉點之後的所有內容。交叉可以說明如下:( |是交叉點）：
還有其他方法可以進行交叉，例如我們可以選擇更多的交叉點。交叉可能非常復雜，主要取決於染色體的編碼。針對特定問題進行的特定交叉可以改善遺傳演算法的性能。
4.染色體突變
在執行交叉之後，發生突變。突變旨在防止群體中的所有解決方案落入解決問題的局部最優中。突變操作隨機改變由交叉引起的後代。在二進制編碼的情況下，我們可以將一些隨機選擇的位從1切換到0或從0切換到1.突變可以如下所示：
突變（以及交叉）技術主要取決於染色體的編碼。例如，當我們編碼排列時，可以將突變作為兩個基因的交換來進行。
GA的參數
1.交叉和突變概率
GA有兩個基本參數 - 交叉概率和變異概率。
交叉概率 ：交叉的頻率。如果沒有交叉，後代就是父母的精確副本。如果存在交叉，則後代由父母染色體的部分組成。如果交叉概率為100％，那麼所有後代都是由交叉產生的。如果它是0％，那麼全新一代都是從舊種群的染色體的精確拷貝製成的（但這並不意味著新一代是相同的！）。交叉是希望新染色體將包含舊染色體的良好部分，因此新染色體將更好。但是，將舊人口的一部分留給下一代是好的。
突變概率 ：染色體部分突變的頻率。如果沒有突變，則在交叉（或直接復制）後立即生成後代而不進行任何更改。如果進行突變，則改變染色體的一個或多個部分。如果突變概率為100％，則整個染色體發生變化，如果是0％，則沒有變化。突變通常會阻止GA陷入局部極端。突變不應該經常發生，因為GA實際上會改變為隨機搜索。
2.其他參數
種群規模 ：種群中有多少染色體（一代）。如果染色體太少，GA幾乎沒有可能進行交叉，只探索了一小部分搜索空間。另一方面，如果染色體太多，GA會減慢。研究表明，經過一定的限制（主要取決於編碼和問題），使用非常大的種群是沒有用的，因為它不能比中等規模的種群更快地解決問題。
3 選擇
正如您從GA概述中已經知道的那樣，從群體中選擇染色體作為交叉的父母。問題是如何選擇這些染色體。根據達爾文的進化論，最好的進化能夠創造出新的後代。選擇最佳染色體的方法有很多種。例如輪盤賭選擇，Boltzman選擇，錦標賽選擇，等級選擇，穩態選擇和其他一些選擇。
1.輪盤賭選擇
父母根據他們的健康狀況選擇。染色體越好，它們被選擇的機會就越多。想像一下輪盤賭輪，人口中的所有染色體都放在那裡。輪盤中截面的大小與每條染色體的適應度函數的值成比例 - 值越大，截面越大。有關示例，請參見下圖。
輪盤賭中放入一塊大理石，並選擇停止的染色體。顯然，具有較大適應值的染色體將被選擇更多次。
該過程可以通過以下演算法來描述。
[Sum]計算總體中所有染色體擬合度的總和 - 總和S.
[Select]從區間（0，S）-r生成隨機數。
[循環]遍歷總體並從0 - 總和中求和。當總和s大於r時，停止並返回您所在的染色體。當然，對於每個群體，步驟1僅執行一次。
2.排名選擇
當健身值之間存在很大差異時，先前的選擇類型會出現問題。例如，如果最佳染色體適應度是所有擬合度總和的90％，那麼其他染色體將很少被選擇的機會。等級選擇首先對群體進行排序，然後每個染色體接收由該等級確定的適合度值。最差的將是健身1，第二個最差的2等等，最好的將具有適應度N（人口中的染色體數量）。您可以在下面的圖片中看到，在更改適應性與排名確定的數字後情況如何變化。
排名前的情況（適合度圖）
排名後的情況（訂單號圖）
現在所有染色體都有機會被選中。然而，這種方法會導致收斂速度變慢，因為最好的染色體與其他染色體的差別不大。
3.穩態選擇
這不是選擇父母的特定方法。這種選擇新種群的主要思想是染色體的很大一部分可以存活到下一代。穩態選擇GA以下列方式工作。在每一代中，選擇一些好的（具有更高適應性）染色體來創建新的後代。然後去除一些不好的（具有較低適合度）染色體並將新的後代放置在它們的位置。其餘人口倖存下來。
4.精英
精英主義的想法已經被引入。當通過交叉和變異創建新的種群時，我們有很大的機會，我們將失去最好的染色體。精英主義是首先將最佳染色體（或少數最佳染色體）復制到新種群的方法的名稱。其餘人口以上述方式構建。精英主義可以迅速提高GA的性能，因為它可以防止丟失最佳找到的解決方案。
交叉(Crossover)和突變 (Mutation)
交叉和變異是GA的兩個基本運算符。 GA的表現非常依賴於它們。運算符的類型和實現取決於編碼以及問題。有多種方法可以執行交叉和變異。在本章中，我們將簡要介紹一些如何執行多個編碼的示例和建議。
1.二進制編碼
交叉
單點交叉 - 選擇一個交叉點，從第一個父項復制從染色體開始到交叉點的二進制字元串，其餘從另一個父項復制
選擇兩點交叉 - 兩個交叉點，從第一個父節點復制從染色體開始到第一個交叉點的二進制字元串，從第一個父節點復制從第一個交叉點到第二個交叉點的部分，其餘的是再次從第一個父級復制
均勻交叉 - 從第一個父項或第二個父項中隨機復制位
算術交叉 - 執行一些算術運算以產生新的後代
突變
位反轉 - 選擇的位被反轉
2.置換編碼
交叉
單點交叉 - 選擇一個交叉點，將排列從第一個父項復制到交叉點，然後掃描另一個父項，如果該數字還沒有在後代中，則添加它注意：還有更多方法如何在交叉點之後產生休息
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)
變異
順序更改 - 選擇並交換兩個數字
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)
3.值編碼
交叉
可以使用來自二進制編碼的所有交叉
變異
添加一個小數字（用於實數值編碼） - 將一個小數字添加到（或減去）所選值
（1.29 5.68 2.86 4.11 5.55）=>（1.29 5.68 2.73 4.22 5.55）
4.樹編碼
交叉
樹交叉 - 在父母雙方中選擇一個交叉點，父母在該點被分割，交換點下面的部分被交換以產生新的後代
變異
更改運算符，數字 - 選定節點已更改
補充:
疑惑點：
初始種群是啥：
利用二進制（一般）表示最終解
例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}
用六位二進制數表示由x，y組成的解，例如：001100 表示x=1，y=4
001100 稱為一條基因序列，表示的是該問題的一種解決 方案
種群是包含多個基因序列（解決方案/個體）的集合
適應度函數是啥，有什麼作用：
適應度函數可以理解成「 游戲 規則」，如果問題較為復雜，需要自定義適應度函數，說明如何區分優秀與不優秀的個體; 如果問題比較簡單，例如上述求最大值的問題，則直接用此函數式作為適應度函數即可。作用：評定個體的優劣程度，從而決定其遺傳機會的大小。
怎麼選擇：
定義「適者生存不適者淘汰」的規則，例如：定義適應度高的被選擇的概率更大
怎麼交叉：
利用循環，遍歷種群中的每個個體，挑選另一個體進行交叉。例如，通過遍歷為基因序列A挑選出B配對，則取A的前半部分，B的後半部分，組合成新的個體（基因序列）C
如何變異：
隨機挑選基因序列上的某一位置，進行0-1互換
建議 GA的參數
如果您決定實施遺傳演算法，本章應該為您提供一些基本建議。這些建議非常籠統。您可能希望嘗試使用自己的GA來解決特定問題，因為沒有一般理論可以幫助您針對任何問題調整GA參數。
建議通常是對GA的經驗研究的結果，這些研究通常僅在二進制編碼上進行。
交叉率
交叉率一般應高，約為80％-95％。 （但是有些結果表明，對於某些問題，交叉率約為60％是最好的。）
突變率
另一方面，突變率應該非常低。最佳利率似乎約為0.5％-1％。
人口規模
可能令人驚訝的是，非常大的人口規模通常不會改善GA的性能（從找到解決方案的速度的意義上說）。良好的人口規模約為20-30，但有時大小為50-100是最好的。一些研究還表明，最佳種群規模取決於編碼字元串（染色體）的大小。這意味著如果你有32位染色體，那麼人口應該高於16位染色體。
選擇
可以使用基本的輪盤賭選擇，但有時排名選擇可以更好。查看有關選擇優缺點的章節。還有一些更復雜的方法可以在GA運行期間更改選擇參數。基本上，這些表現類似於模擬退火。如果您不使用其他方法來保存最佳找到的解決方案，則應確保使用精英主義。您也可以嘗試穩態選擇。
編碼
編碼取決於問題以及問題實例的大小。查看有關編碼的章節以獲取一些建議或查看其他資源。
交叉和變異
運算符取決於所選的編碼和問題。查看有關操作員的章節以獲取一些建議。您還可以查看其他網站。
搜索空間
如果我們正在解決問題，我們通常會尋找一些最好的解決方案。所有可行解決方案的空間（所需解決方案所在的解決方案集）稱為搜索空間（也稱為狀態空間）。搜索空間中的每個點代表一種可能的解決方案。每個可能的解決方案可以通過其對問題的值（或適應度）進行「標記」。通過GA，我們在眾多可能的解決方案中尋找最佳解決方案 - 以搜索空間中的一個點為代表。然後尋找解決方案等於在搜索空間中尋找一些極值（最小值或最大值）。有時可以很好地定義搜索空間，但通常我們只知道搜索空間中的幾個點。在使用遺傳演算法的過程中，隨著進化的進行，尋找解決方案的過程會產生其他點（可能的解決方案）。
問題是搜索可能非常復雜。人們可能不知道在哪裡尋找解決方案或從哪裡開始。有許多方法可用於尋找合適的解決方案，但這些方法不一定能提供最佳解決方案。這些方法中的一些是爬山，禁忌搜索，模擬退火和遺傳演算法。通過這些方法找到的解決方案通常被認為是很好的解決方案，因為通常不可能證明最佳方案。
NP-hard Problems
NP問題是一類無法用「傳統」方式解決的問題。我們可以快速應用許多任務（多項式）演算法。還存在一些無法通過演算法解決的問題。有很多重要問題很難找到解決方案，但是一旦有了解決方案，就很容易檢查解決方案。這一事實導致了NP完全問題。 NP代表非確定性多項式，它意味著可以「猜測」解決方案（通過一些非確定性演算法），然後檢查它。如果我們有一台猜測機器，我們或許可以在合理的時間內找到解決方案。為簡單起見，研究NP完全問題僅限於答案可以是或否的問題。由於存在輸出復雜的任務，因此引入了一類稱為NP難問題的問題。這個類並不像NP完全問題那樣受限。 NP問題的一個特徵是，可以使用一個簡單的演算法，可能是第一眼看到的，可用於找到可用的解決方案。但是這種方法通常提供了許多可能的解決方案 - 只是嘗試所有可能的解決方案是非常緩慢的過程（例如O（2 ^ n））。對於這些類型問題的更大的實例，這種方法根本不可用。今天沒有人知道是否存在一些更快的演算法來提供NP問題的確切答案。對於研究人員來說，發現這樣的演算法仍然是一項重大任務（也許你！:-)）。今天許多人認為這種演算法不存在，因此他們正在尋找替代方法。替代方法的一個例子是遺傳演算法。 NP問題的例子是可滿足性問題，旅行商問題或背包問題。可以獲得NP問題匯編。
參考：
https://www.jianshu.com/p/ae5157c26af9
https://www.jianshu.com/p/b36b520bd187
Ⅲ 遺傳演算法-總結
最近在做遺傳演算法的項目，簡單記錄一下。
遺傳演算法是模擬自然界生物進化機制的一種演算法，在尋優過程中有用的保留無用的去除。包括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
Ⅳ 遺傳演算法的基本原理
遺傳演算法的基本原理和方法
一、編碼
編碼：把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。
解碼（解碼）：遺傳演算法解空間向問題空間的轉換。
二進制編碼的缺點是漢明懸崖（Hamming Cliff），就是在某些相鄰整數的二進制代碼之間有很大的漢明距離，使得遺傳演算法的交叉和突變都難以跨越。
格雷碼（Gray Code）：在相鄰整數之間漢明距離都為1。
（較好）有意義的積木塊編碼規則：所定編碼應當易於生成與所求問題相關的短距和低階的積木塊；最小字元集編碼規則，所定編碼應採用最小字元集以使問題得到自然的表示或描述。
二進制編碼比十進制編碼搜索能力強，但不能保持群體穩定性。
動態參數編碼（Dynamic Paremeter Coding）：為了得到很高的精度，讓遺傳演算法從很粗糙的精度開始收斂，當遺傳演算法找到一個區域後，就將搜索現在在這個區域，重新編碼，重新啟動，重復這一過程，直到達到要求的精度為止。
編碼方法：
1、 二進制編碼方法
缺點：存在著連續函數離散化時的映射誤差。不能直接反映出所求問題的本身結構特徵，不便於開發針對問題的專門知識的遺傳運算運算元，很難滿足積木塊編碼原則
2、 格雷碼編碼：連續的兩個整數所對應的編碼之間僅僅只有一個碼位是不同的，其餘碼位都相同。
3、 浮點數編碼方法：個體的每個基因值用某一范圍內的某個浮點數來表示，個體的編碼長度等於其決策變數的位數。
4、 各參數級聯編碼：對含有多個變數的個體進行編碼的方法。通常將各個參數分別以某種編碼方法進行編碼，然後再將他們的編碼按照一定順序連接在一起就組成了表示全部參數的個體編碼。
5、 多參數交叉編碼：將各個參數中起主要作用的碼位集中在一起，這樣它們就不易於被遺傳運算元破壞掉。
評估編碼的三個規范：完備性、健全性、非冗餘性。
二、選擇
遺傳演算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一種遺傳運算，用來確定重組或交叉個體，以及被選個體將產生多少個子代個體。
常用的選擇運算元：
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個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。
6、無回放余數隨機選擇：可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中，因而選擇誤差比較小。
7、均勻排序：對群體中的所有個體按期適應度大小進行排序，基於這個排序來分配各個個體被選中的概率。
8、最佳保存策略：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來代替掉本代群體中經過交叉、變異等操作後所產生的適應度最低的個體。
9、隨機聯賽選擇：每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中。
10、排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性。
三、交叉
遺傳演算法的交叉操作，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。
適用於二進制編碼個體或浮點數編碼個體的交叉運算元：
1、單點交叉（One－pointCrossover）：指在個體編碼串中只隨機設置一個交叉點，然後再該點相互交換兩個配對個體的部分染色體。
2、兩點交叉與多點交叉：
（1） 兩點交叉（Two－pointCrossover）：在個體編碼串中隨機設置了兩個交叉點，然後再進行部分基因交換。
（2） 多點交叉（Multi－pointCrossover）
3、均勻交叉（也稱一致交叉，UniformCrossover）：兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新個體。
4、算術交叉（ArithmeticCrossover）：由兩個個體的線性組合而產生出兩個新的個體。該操作對象一般是由浮點數編碼表示的個體。
四、變異
遺傳演算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來替換，從而形成以給新的個體。
以下變異運算元適用於二進制編碼和浮點數編碼的個體：
1、基本位變異（SimpleMutation）：對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。
2、均勻變異（UniformMutation）：分別用符合某一范圍內均勻分布的隨機數，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。（特別適用於在演算法的初級運行階段）
3、邊界變異（BoundaryMutation）：隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。
4、非均勻變異：對原有的基因值做一隨機擾動，以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後，相當於整個解向量在解空間中作了一次輕微的變動。
5、高斯近似變異：進行變異操作時用符號均值為P的平均值，方差為P2的正態分布的一個隨機數來替換原有的基因值。
Ⅳ 遺傳演算法是什麼
遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。
遺傳演算法(Genetic Algorithms簡稱GA)是由美國Michigan大學的John Holland教授於20世紀60年代末創建的。它來源於達爾文的進化論和孟德爾、摩根的遺傳學理論，通過模擬生物進化的機制來構造人工系統。遺傳演算法作為一種全局優化方法，提供了一種求解復雜系統優化問題的通用框架，它不依賴於問題的具體領域，對優化函數的要求很低並且對不同種類的問題具有很強的魯棒性，所以廣泛應用於計算機科學、工程技術和社會科學等領域。John Holland教授通過模擬生物進化過程設計了最初的遺傳演算法，我們稱之為標准遺傳演算法。
標准遺傳演算法流程如下：
1）初始化遺傳演算法的群體，包括初始種群的產生以及對個體的編碼。
2）計算種群中每個個體的適應度，個體的適應度反映了其優劣程度。
3）通過選擇操作選出一些個體，這些個體就是母代個體，用來繁殖子代。
4）選出的母代個體兩兩配對，按照一定的交叉概率來進行交叉，產生子代個體。
5）按照一定的變異概率，對產生的子代個體進行變異操作。
6）將完成交叉、變異操作的子代個體，替代種群中某些個體，達到更新種群的目的。
7）再次計算種群的適應度，找出當前的最優個體。
8）判斷是否滿足終止條件，不滿足則返回第3）步繼續迭代，滿足則退出迭代過程，第7）步中得到的當前最優個體，通過解碼，就作為本次演算法的近似最優解。
具體你可以到網路文庫去搜索遺傳演算法相關的論文，很多的。
你也可以參考網路里對遺傳演算法的介紹。
Ⅵ 遺傳演算法
優化的演算法有很多種，從最基本的梯度下降法到現在的一些啟發式演算法，如遺傳演算法(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、所求問題最優值小於給定的閾值.
Ⅶ 遺傳規律中的配子法是怎麼樣一中演算法啊
根據雌雄親本產生的雌雄配子的類型，來推斷子代的基因型（雌雄配子隨機結合）。如親本為AB、BB，則配子分別是A、B和B，如下
配子/組合
A
B
B
AB
BB
Ⅷ 基因遺傳演算法主流
基因遺傳演算法是一種靈感源於達爾文自然進化理論的啟發式搜索演算法 該演算法反映了自然選擇的過程 即最適者被選定繁殖 並產生下一代
自然選擇的過程從選擇群體中最適應環境的個體開始 後代繼承了父母的特性 並且這些特性將添加到下一代中 如果父母具有更好的適應性 那麼它們的後代將更易於存活 迭代地進行該自然選擇的過程 最終 我們將得到由最適應環境的個體組成的一代
這一概念可以被應用於搜索問題中 我們考濾一個問題的諸多解決方案 並從中搜尋出最佳方案
遺傳演算法含以下五步
1.初始化
2.個體評價（計算適應度函數）
3.選擇運算
4.交叉運算
5.變異運算
初始化
該過程從種群的一組個體開始 且每一個體都是待解決問題的一個候選解
個體以一組參數（變數）為特徵 這些特徵被稱為基因 串聯這些基因就可以組成染色體（問題的解）
在遺傳演算法中 單個個體的基因組以字元串的方式呈現 通常我們可以使用二進制（1和0的字元串）編碼 即一個二進制串代表一條染色體串 因此可以說我們將基因串或候選解的特徵編碼在染色體中
個體評價利用適應度函數評估了該個體對環境的適應度（與其它個體徑爭的能力）每一個體都有適應評分 個體被選中進行繁殖的可能性取決於其適應度評分 適應度函數是遺傳演算法進化的驅動力 也是進行自然選擇的唯一標准 它的設計應結合求解問題本身的要求而定
選擇運算的目的是選出適應性最好的個體 並使它們將基因傳到下一代中 基於其適應度評分 我們選擇多對較優個體（父母）適應度高的個體更易被選中繁殖 即將較優父母的基因傳遞到下一代
交叉運算是遺傳演算法中最重要的階段 對每一對配對的父母 基因都存在隨機選中的交叉點
變異運算
在某些形成的新後代中 它們的某些基因可能受到低概率變異因子的作用 這意味著二進制位串中的某些位可能會翻轉
變異運算前後
變異運算可用於保持群內的多樣性 並防止過早收斂
終止
在群體收斂的情況下（群體內不產生與前一代差異較大的後代）該演算法終止 也就是說遺傳演算法提供了一組問題的解
Ⅸ 關於遺傳演算法
遺傳演算法（Genetic Algorithm，簡稱GA）是美國 Michigan大學的 John Golland提出的一種建立在自然選擇和群體遺傳學機理基礎上的隨機、迭代、進化、具有廣泛適用性的搜索方法。現在已被廣泛用於學習、優化、自適應等問題中。圖4-1 給出了 GA搜索過程的直觀描述。圖中曲線對應一個具有復雜搜索空間（多峰空間）的問題。縱坐標表示適應度函數（目標函數），其值越大相應的解越優。橫坐標表示搜索點。顯然，用解析方法求解該目標函數是困難的。採用 GA時，首先隨機挑選若干個搜索點，然後分別從這些搜索點開始並行搜索。在搜索過程中，僅靠適應度來反復指導和執行 GA 搜索。在經過若干代的進化後，搜索點後都具有較高的適應度並接近最優解。
一個簡單GA由復制、雜交和變異三個遺傳運算元組成：
圖4-2 常規遺傳演算法流程圖