遺傳演算法導圖

❶ 遺傳演算法--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

❷ 遺傳演算法

遺傳演算法是從代表問題可能潛在解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因的組合，它決定了個體形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼。初始種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解。在每一代，根據問題域中個體的適應度（fitness）大小挑選（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群自然進化一樣的後生代種群比前代更加適應環境，末代種群中的最優個體經過編碼（decoding），可以作為問題近似最優解。

5.4.1 非線性優化與模型編碼

假定有一組未知參量

x_i（i=1，2，…，M）

構成模型向量m，它的非線性目標函數為Φ（m）。根據先驗知識，對每個未知量都有上下界α_i及b_i，即α_i≤x≤b_i，同時可用間隔d_i把它離散化，使

d_i=（b_i-α_i）/N （5.4.1）

於是，所有允許的模型m將被限制在集

x_i=α_i+jd_i（j=0，1，…，N） （5.4.2）

之內。

通常目標泛函（如經濟學中的成本函數）表示觀測函數與某種期望模型的失擬，因此非線性優化問題即為在上述限制的模型中求使Φ（m）極小的模型。對少數要求擬合最佳的問題，求目標函數的極大與失擬函數求極小是一致的。對於地球物理問題，通常要進行殺重離散化。首先，地球模型一般用連續函數表示，反演時要離散化為參數集才能用於計算。有時，也將未知函數展開成已知基函數的集，用其系數作為離散化的參數集x_i，第二次離散化的需要是因為每一個未知參數在其變化范圍內再次被離散化，以使離散模型空間最終包含著有限個非線性優化可選擇的模型，其個數為

地球物理數據處理教程

其中M為未知參數x_i的個數。由此式可見，K決定於每個參數離散化的間隔d_i及其變化范圍（α_i，b_i），在大多數情況下它們只能靠先驗知識來選擇。

一般而言，優化問題非線性化的程度越高，逐次線性化的方法越不穩定，而對蒙特卡洛法卻沒有影響，因為此法從有限模型空間中隨機地挑選新模型並計算其目標函數 Φ（m）。遺傳演算法與此不同的是同時計算一組模型（開始時是隨機地選擇的），然後把它進行二進制編碼，並通過繁殖、雜交和變異產生一組新模型進一步有限的模型空間搜索。編碼的方法可有多種，下面舉最簡單的例說明之，對於有符號的地球物理參數反演時的編碼方式一般要更復雜些。

假設地球為有三個水平層的層次模型，含層底界面深度h_j（j=1，2，3）及層速度v_j（j=1，2，3）這兩組參數。如某個模型的參數值為（十進制）：

h₁=6，h₂=18，h₃=28，單位為10m

v₁=6，v₂=18，v₃=28，單位為 hm/s

按正常的二進制編碼法它們可分別用以下字元串表示為：

地球物理數據處理教程

為了減少位元組，這種編碼方式改變了慣用的單位制，只是按精度要求（深度為10m，波速為hm/s）來規定參數的碼值，同時也意味著模型空間離散化間距d_i都規格化為一個單位（即10m，或hm/s）。當然，在此編碼的基礎上，還可以寫出多種新的編碼字元串。例如，三參數值的對應位元組順序重排，就可組成以下新的二進制碼串：

地球物理數據處理教程

模型參數的二進制編碼是一種數學上的抽象，通過編碼把具體的非線性問題和生物演化過程聯系了起來，因為這時形成的編碼字元串就相當於一組遺傳基因的密碼。不僅是二進制編碼，十進制編碼也可直接用於遺傳演算法。根據生物系統傳代過程的規律，這些基因信息將在繁殖中傳到下一帶，而下一代將按照「適者生存」的原則決定種屬的發展和消亡，而優化准則或目標函數就起到了決定「適者生存」的作用，即保留失擬較小的新模型，而放棄失擬大的模型。在傳帶過程中用編碼表示的基因部分地交合和變異，即字元串中的一些子串被保留，有的改變，以使傳代的過程向優化的目標演化。總的來說，遺傳演算法可分為三步：繁殖、雜交和變異。其具體實現過程見圖5.8。

圖5.8 遺傳演算法實現過程

5.4.2 遺傳演算法在地震反演中的應用

以地震走時反演為例，根據最小二乘准則使合成記錄與實測數據的擬合差取極小，目標函數可取為

地球物理數據處理教程

式中：T_i，0為觀測資料中提取出的地震走時；T_i，s為合成地震或射線追蹤算出的地震走時；ΔT為所有合成地震走時的平均值；N_A為合成地震數據的個數，它可以少於實測T_i，0的個數，因為在射線追蹤時有陰影區存在，不一定能算出合成數據T_j，0。利用射線追蹤計算走時的方法很多，參見上一章。對於少數幾個波速為常數的水平層，走時反演的參數編碼方法可參照上一節介紹的分別對深度和速度編碼方法，二進制碼的字元串位數1不會太大。要注意的是由深度定出的字元串符合數值由淺到深增大的規律，這一約束條件不應在雜交和傳代過程中破壞。這種不等式的約束（h₁＜h₂＜h₃…）在遺傳演算法中是容易實現的。

對於波場反演，較方便的做法是將地球介質作等間距的劃分。例如，將水平層狀介質細分為100個等厚度的水平層。在上地殼可假定波速小於6400 m/s（相當於解空間的硬約束），而波速空間距為100m/s，則可將波速用100m/s為單位，每層用6位二進制字元串表示波速，地層模型總共用600位二進制字元串表示（l=600）。初始模型可隨機地選取24～192個，然後通過繁殖雜交與變異。雜交概率在0.5～1.0之間，變異概率小於0.01。目標函數（即失擬方程）在頻率域可表示為

地球物理數據處理教程

式中：P₀（ω_k，v_j）為實測地震道的頻譜；ω_k為角頻率；v_j為第j層的波速；P_s（ω_k，v_j）為相應的合成地震道；A（ω_k）為地震儀及檢波器的頻率濾波器，例如，可取

A（ω）=sinC⁴（ω/ω_N） （5.4.6）

式中ω_N為Nyquist頻率，即ω_N=π/Δt，Δt為時間采樣率。參數C為振幅擬合因子，它起到合成與觀測記錄之間幅度上匹配的作用。C的計算常用地震道的包絡函數的平均比值。例如，設E［］為波動信號的包絡函數，可令

地球物理數據處理教程

式中：t_max為包絡極大值的對應時間；J為總層數。包絡函數可通過復數道的模擬取得。

用遺傳演算法作波速反演時失擬最小的模型將一直保存到迭代停止。什麼時候停止傳代還沒有理論上可計算的好辦法，一般要顯示解空間的搜索范圍及局部密度，以此來判斷是否可以停止傳代。值得指出的是，由（5.4.4）和（5.4.5）式給出的目標函數對於有誤差的數據是有問題的，反演的目標不是追求對有誤差數據的完美擬合，而是要求出准確而且解析度最高的解估計。

遺傳演算法在執行中可能出現兩類問題。其一稱為「早熟」問題，即在傳代之初就隨機地選中了比較好的模型，它在傳代中起主導作用，而使其後的計算因散不開而白白浪費。通常，增加Q值可以改善這種情況。另一類問題正相反，即傳相當多代後仍然找不到一個特別好的解估計，即可能有幾百個算出的目標函數值都大同小異。這時，最好修改目標函數的比例因子（即（5.4.5）式的分母），以使繁殖概率P_s的變化范圍加大。

對於高維地震模型的反演，由於參數太多，相應的模型字元串太長，目前用遺傳演算法作反演的計算成本還嫌太高。實際上，為了加快計算，不僅要改進反演技巧和傳代的控制技術，而且還要大幅度提高正演計算的速度，避免對遺傳演算法大量的計算花費在正演合成上。

❸ 遺傳演算法在數學上的應用

應用遺傳演算法搜索邊坡最小安全系數的研究
陸峰 陳祖煜 李素梅
（中國水利水電科學研究院結構材料所）

提 要
本文簡要介紹了滑坡滑裂面搜索問題和遺傳演算法，並試用遺傳進化演算法從邊坡任意形狀滑裂面組合中搜索最有可能的滑裂面，也就是使安全系數最小的滑裂面。作為實例，分析了遺傳演算法在天生橋二級電站首部樞紐進水口右岸滑坡分析中的應用。

關鍵詞 邊坡；安全系數；遺傳演算法；EMU程序。

1．前言

在應用條分法進行邊坡穩定分析的過程中，從可能的滑裂面集合中確定相應最小安全系數的臨界滑裂面是很關鍵的一步。這是一個確定安全系數這個泛函對滑裂面形狀這個自變函數的極小值問題。由於實際情況的復雜性，求這一極小值的解析方法很難付諸實施。從實用角度出發，基於最優化原理發展起來的求邊坡最小安全系數的方法是比較有效而且便於應用。這些方法有"窮舉法"、"黃金分割法"、"鮑威爾法"等，但它們都只能應用於圓弧形滑裂面或圓弧-直線形（改良圓弧法）滑裂面的情形。對於比較符合岩質邊坡的具有多個自由度的折線形滑裂面情形，孫君實用復形法取得較好的效果；陳祖煜提出了單純形法，使最優化方法搜索邊坡最危險滑裂面更加有效，且不會漏掉可能的最小值。單純形法程序已在國內外多家工程、科研和教育單位得到應用，並不斷隨著應用工程案例數量的增加而不斷完善[1]。單純形法使最優化方法應用於岩質邊坡穩定性分析的研究和應用前進了一大步。同為最優化方法，遺傳演算法是最近發展起來的一種仿生尋優演算法。國內外已有一些學者試圖將遺傳演算法應用於搜索安全系數最小的邊坡滑裂面，以期獲得更優的結果。文獻[2]將此演算法應用於基於圓弧滑裂面假定的任意形狀坡面的非均質土坡情況，搜索的目標是使邊坡安全系數最小的圓弧滑裂面圓心和半徑。本文將在文獻[1]和文獻[2]的基礎上，應用遺傳演算法搜索邊坡安全系數最小的任意形狀滑裂面，根據工程實踐經驗，主要是折線組合的滑裂面。 2．遺傳演算法及其應用於岩土工程的基礎

如前所述，搜索邊坡最危險滑裂面問題是安全系數對滑裂面形狀的泛函極值問題。數值方法求解這一問題的主要手段是迭代運算。一般的迭代方法容易陷入局部極小的陷阱而出現"死循環"現象，使迭代無法進行。遺傳演算法很好地克服了這個缺點，是一種全局優化演算法。
生物在漫長的進化過程中，從低等生物一直發展到高等生物，可以說是一個絕妙的優化過程。這是自然環境選擇的結果。人們研究生物進化現象，總結出進化過程包括復制、雜交、變異、競爭和選擇。一些學者從生物遺傳、進化的過程得到啟發，提出了遺傳演算法（GA）。演算法中稱遺傳的生物體為個體（indivial），個體對環境的適應程度用適應值（fitness）表示。適應值取決於個體的染色體（chromosome），在演算法中染色體常用一串數字表示，數字串中的一位對應一個基因（gene）。一定數量的個體組成一個群體（population）。對所有個體進行選擇、交叉和變異等操作，生成新的群體，稱為新一代（new generation）。
遺傳演算法計算程序的流程可以表示如下[3]：
第一步 准備工作
（1）選擇合適的編碼方案，將變數（特徵）轉換為染色體（數字串，串長為m）。通常用二進制編碼。
（2）選擇合適的參數，包括群體大小（個體數M）、交叉概率PC和變異概率Pm。
（3）確定適應值函數f（x）。f（x）應為正值。
第二步 形成一個初始群體（含M個個體）。在邊坡滑裂面搜索問題中，取已分析的可能滑裂面組作為初始群體。
第三步 對每一染色體（串）計算其適應值fi，同時計算群體的總適應值 。
第四步 選擇
計算每一串的選擇概率Pi=fi/F及累計概率 。選擇一般通過模擬旋轉滾花輪（roulette，其上按Pi大小分成大小不等的扇形區）的演算法進行。旋轉M次即可選出M個串來。在計算機上實現的步驟是：產生[0，1]間隨機數r，若r<q1，則第一串v1入選，否則選v2，使滿足qi-1<r<qi（2≤i≤m）。可見適應值大的入選概率大。
第五步 交叉
（1） 對每串產生[0，1]間隨機數，若r>pc，則該串參加交叉操作，如此選出參加交叉的一組後，隨機配對。
（2） 對每一對，產生[1，m]間的隨機數以確定交叉的位置。
第六步 變異
如變異概率為Pm，則可能變異的位數的期望值為Pm ×m×M，每一位以等概率變異。具體為對每一串中的每一位產生[0，1]間的隨機數r，若r<Pm，則該位發生反轉，如對染色體二進制編碼為數字0變為1，1變為0。
如新個體數達到M個，則已形成一個新群體，轉向第三步；否則轉向第四步繼續遺傳操作。直到找到使適應值最大的個體或達到最大進化代數為止。
由於選擇概率是由適應值決定的，即適應值大的染色體入選概率也較大，使選擇起到"擇優汰劣"的作用。交叉使染色體交換信息，結合選擇規則，使優秀信息得以保存，不良信息被遺棄。變異是基因中得某一位發生突變，以達到產生確實有實質性差異的新品種。遺傳演算法雖是一種隨機演算法，但它是有導向的，它所使用的"按概率隨機選擇"方法是在有方向的搜索方法中的一種工具。正是這種獨特的搜索方法，使遺傳演算法自然地避開了其它最優化演算法常遇到的局部最小陷阱。遺傳演算法搜索最優結果的效果在數學上還沒有嚴格的證明，但它的有效性已在許多專業的應用的得到體現。對於岩質邊坡安全系數對滑裂面形狀這樣不可微的泛函極值問題，就目前的科學認識水平來講，遺傳演算法不失為一種可以信賴的方法。 3．用遺傳演算法搜索安全系數最小的邊坡任意形狀滑裂面

在邊坡（尤其是岩質邊坡）最危險滑裂面搜索問題中，滑裂面的實際形狀是很復雜的，起控製作用的是岩體的主要結構面和邊坡的體型。從以往實際工程經驗看，可以總結出岩質邊坡滑裂面在順滑方向上的剖面形狀為折線，由岩體結構面和局部岩土材料的剪切破壞面連接而成。這樣，搜索最危險滑裂面的問題就可以簡化為從折線滑裂面組合中尋優的問題。本文用遺傳進化演算法解決這個問題。
（1） 定義遺傳演算法的目標函數
目標函數定義為邊坡的安全系數，用安全系數的大小表示解的適應值。在邊坡最危險滑裂面搜索問題中，解的安全系數越小，適應性能越好。
（2） 初始群體的確定
根據邊坡的工程地質調查記錄，根據經驗初步擬定出一批滑裂面形狀。如圖1所示，滑裂面由點序列Ai（xi，yi）（i=1，?，N）表示。將點序列AI的坐標（xi，yi）依次排列成x1y1x2y2?xNyN的形式，經二進制編碼形成一條染色體。對於擬定的滑裂面形狀，其對應的安全系數用EMU程序[4]進行計算。
（3） 確定搜索范圍
根據經驗對每個點Ai，確定其坐標（xi，yi）的可能變化范圍。在此范圍內搜索導致最小安全系數的邊坡滑裂面形狀。
（4） 計算
將初始種群的所有擬定滑裂面形狀（染色體）交給遺傳演算法程序進行計算。具體過程參見前文。

4．算例分析[4]

圖1 天生橋二級電站首部樞紐進水口右岸滑坡示意圖

選用天生橋二級電站首部樞紐進水口右岸滑坡作為算例，圖1為其計算簡圖。滑坡高約30m，總方量為7000餘m3，主要為第四系沖坡積物和施工堆碴。物理力學參數見表1。

表1 各土層物理力學性能指標
土層 密度（g/cm3） 抗剪強度指標
內摩擦角 凝聚力（kPa）
① 施工棄碴 1.85 21.8° 19.6
② 坡積土 1.85 21.8° 0.0
③ 砂土 1.85 21.8° 29.4
④ 砂質淤泥 1.85 20.8° 34.3
⑤ 河卵石、礫石 1.90 24.2° 0.0

滑坡發生前，靠近坡腳處因修建擋土牆被開挖而削弱邊坡的整體穩定性，可以斷定滑坡的滑裂面將從此經過。本例題還將忽略實際工程中坡頂張裂縫的影響。選用5個點的折線來模擬滑裂面形狀，初步確定AiBiCiDiE（i=1~4）為可能的滑裂面。滑裂面上端點Ai的y坐標已受限制，下端點E的x、y坐標均已確定，故滑裂面只有7個自由度。按遺傳演算法的要求將滑裂面表示成如下形式：
xAxByBxCyCxDyD
四個模擬滑裂面的坐標和由EMU程序分析的安全系數列於表2。
表2 模擬滑裂面坐標及安全系數（坐標單位 m）
滑裂面 xA xB yB xC yC xD yD 安全系數
A1B1C1D1E 35.44 27.69 16.82 18.79 9.25 11.39 4.49 0.92
A2B2C2D2E 38.15 30.60 20.69 23.14 14.60 14.12 8.37 0.99
A3B3C3D3E 39.02 34.18 18.47 26.28 10.41 16.07 4.58 1.02
A3B3C4D4E 39.02 34.18 18.47 25.12 11.39 14.70 4.97 1. 03

限制搜索范圍為每個自由度可在2.0m范圍內變化。將4個排列好的數字串作為輸入數據交給遺傳演算法程序進行編碼、計算。經過大量運算，最後在最大種群代數（1000）群體中找到使安全系數最小的坐標數字串，經解碼形成如下坐標：
（36.89，30.07）（33.25，21.52）（21.71，9.34）（13.54，5.07）（0.0，0.0）
即為圖1中的ABCDE滑裂面。由遺傳演算法求出其相應的安全系數為0.90。滑裂面形式和安全系數都比較接近實際情況。

5．結語

遺傳演算法是一種高效的尋優演算法，而且能有效地解決局部最小問題、非線性映射關系的表示、非線性映射關系不可微等普通優化演算法常遇到的問題。算例的成果證明了這一特點。將遺傳演算法應用於滑坡滑裂面搜索問題，主要的工作是將工程問題簡化成遺傳演算法需要的形式，簡化時需詳細參考地質調查資料和工程經驗，務使簡化的形式接近實際情況。對於簡化的搜索樣本，其安全系數的計算必須可靠，為此可應用一些比較成熟的計算程序，如EMU等。充分考慮實際工程地質情況和選取切合實際的搜索樣本後，遺傳演算法程序必將能為滑坡搜索出最有可能的滑裂面。

參考文獻

1 陳祖煜，邵長明，最優化方法在確定邊坡最小安全系數方面的應用，岩土工程學報，Vol.10, No.4, 1998.7。
2 肖專文，張奇志，梁力，林韻梅，遺傳進化演算法在邊坡穩定性分析中的應用，岩土工程學報，Vol.20, No.1, 1998.1。
3 周明，孫樹棟，遺傳演算法原理及應用，國防工業出版社，1999.6。
4 陳祖煜，岩質高邊坡穩定分析程序EMU，1995.5。

Research on Searching Least Factor of Safety of Slopes with Genetic Algorithm

Lu Feng Chen Zuyu Li Sumei
(Department of Structure and Material, IWHR)

Abstract

The problem of searching least factor of safety of slopes and the theory of Genetic Algorithm have been introced in this paper. This theory has been employed to solve this problem to find the most possible slide of slopes. As an example, the application of genetic algorithm on the Tianshengqiao Power Station Right Bank Slide has been presented.

Keywords: Slope, Factor of Safety, Genetic Algorithm, EMU Program.

❹ 遺傳演算法的核心是什麼！

遺傳操作的交叉運算元。

在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳演算法中起核心作用的是遺傳操作的交叉運算元。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳演算法的搜索能力得以飛躍提高。

交叉運算元根據交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。

(4)遺傳演算法導圖擴展閱讀

評估編碼策略常採用以下3個規范：

a)完備性(completeness):問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現。

b)健全性(soundness): GA空間中的染色體能對應所有問題空間中的候選解。

c)非冗餘性(nonrendancy):染色體和候選解一一對應。

目前的幾種常用的編碼技術有二進制編碼，浮點數編碼，字元編碼，變成編碼等。

而二進制編碼是目前遺傳演算法中最常用的編碼方法。即是由二進制字元集{0,1}產生通常的0,1字元串來表示問題空間的候選解。

❺ 遺傳演算法路徑規劃是什麼原理

遺傳演算法有相當大的引用。遺傳演算法在游戲中應用的現狀在遺傳編碼時, 一般將瓦片的坐標作為基因進行實數編碼, 染色體的第一個基因為起點坐標, 最後一個基因為終點坐標, 中間的基因為路徑經過的每一個瓦片的坐標。在生成染色體時, 由起點出發, 隨機選擇當前結點的鄰居節點中的可通過節點, 將其坐標加入染色體, 依此循環, 直到找到目標點為止, 生成了一條染色體。重復上述操作, 直到達到指定的種群規模。遺傳演算法的優點：1、遺傳演算法是以決策變數的編碼作為運算對象，可以直接對集合、序列、矩陣、樹、圖等結構對象進行操作。這樣的方式一方面有助於模擬生物的基因、染色體和遺傳進化的過程，方便遺傳操作運算元的運用。另一方面也使得遺傳演算法具有廣泛的應用領域，如函數優化、生產調度、自動控制、圖像處理、機器學習、數據挖掘等領域。2、遺傳演算法直接以目標函數值作為搜索信息。它僅僅使用適應度函數值來度量個體的優良程度，不涉及目標函數值求導求微分的過程。因為在現實中很多目標函數是很難求導的，甚至是不存在導數的，所以這一點也使得遺傳演算法顯示出高度的優越性。3、遺傳演算法具有群體搜索的特性。它的搜索過程是從一個具有多個個體的初始群體P(0)開始的，一方面可以有效地避免搜索一些不必搜索的點。另一方面由於傳統的單點搜索方法在對多峰分布的搜索空間進行搜索時很容易陷入局部某個單峰的極值點，而遺傳演算法的群體搜索特性卻可以避免這樣的問題，因而可以體現出遺傳演算法的並行化和較好的全局搜索性。4、遺傳演算法基於概率規則，而不是確定性規則。這使得搜索更為靈活，參數對其搜索效果的影響也盡可能的小。5、遺傳演算法具有可擴展性，易於與其他技術混合使用。以上幾點便是遺傳演算法作為優化演算法所具備的優點。遺傳演算法的缺點：遺傳演算法在進行編碼時容易出現不規范不準確的問題。

❻ 遺傳演算法對生活的啟示

遺傳演算法使用選擇運算來實現對群體中的個體進行優勝劣汰操作:適應度高的個體被遺傳到下一代群體中的概率大。

遺傳演算法（Genetic Algorithm，GA）最早是由美國的John holland於20世紀70年代提出,該演算法是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。

20世紀80年代後,遺傳演算法進入興盛發展時期，被廣泛應用於自動控制、生產計劃、圖像處理、機器人等研究領域。由於遺傳演算法不能直接處理問題空間的參數,因此必須通過編碼將要求解的問題表示成遺傳空間的染色體或者個體。這一轉換操作就叫做編碼，也可以稱作（問題的）表示。