遺傳演算法作用

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

② 遺傳演算法的作用

與傳統的優化相比，在求取符合運行要求的全局最優解時，遺傳演算法作為一種搜索的方法，已經成為成熟的具有良好收斂性、極高魯棒性和廣泛適用性的優化方法，很好的解決了電力系統的多變數、非線性、不連續、多約束的優化控制問題。

③ 基因演算法和遺傳演算法的區別

遺傳演算法
一種基於自然群體遺傳演化機制的高效探索演算法，它是美國學者Holland於1975年首先提出來的。它摒棄了傳統的搜索方式，模擬自然界生物進化過程，採用人工進化的方式對目標空間進行隨機化搜索。它將問題域中的可能解看作是群體的一個個體或染色體，並將每一個體編碼成符號串形式，模擬達爾文的遺傳選擇和自然淘汰的生物進化過程，對群體反復進行基於遺傳學的操作（遺傳，交叉和變異），根據預定的目標適應度函數對每個個體進行評價，依據適者生存，優勝劣汰的進化規則，不斷得到更優的群體，同時以全局並行搜索方式來搜索優化群體中的最優個體，求得滿足要求的最優解。
Holland創建的遺傳演算法是一種概率搜索演算法，它是利用某種編碼技術作用於稱為染色體的數串，其基本思想是模擬由這些組成的進化過程。跗演算法通過有組織地然而是隨機地信息交換重新組合那些適應性好的串，在每一代中，利用上一代串結構中適應好的位和段來生成一個新的串的群體；作為額外增添，偶爾也要在串結構中嘗試用新的位和段來替代原來的部分。
遺傳演算法是一類隨機化演算法，但是它不是簡單的隨機走動，它可以有效地利用已經有的信息處理來搜索那些有希望改善解質量的串，類似於自然進化，遺傳演算法通過作用於染色體上的基因，尋找好的染色體來求解問題。與自然界相似，遺傳演算法對待求解問題本身一無所知，它所需要的僅是對演算法所產生的每個染色體進行評價，並基於適應度值來造反染色體，使適用性好的染色體比適應性差的染色體有更多的繁殖機會。
基因演算法
一種生物進化的演算法,實際上是一種多目標的探索法.能夠用於計劃與排程.它是非常新的技術,目前,還沒有在商業中實際運用.
採用生物基因技術高級演算法,處理日益復雜的現實世界,也是人工智慧上,高級約束演算法上的挑戰. 基因演算法是一種搜索技術，它的目標是尋找最好的解決方案。這種搜索技術是一種優化組合，它以模仿生物進化過程為基礎。基因演算法的基本思想是，進化就是選擇了最優種類。基因演算法將應用APS上，以獲得「最優」的解決方案。

④ 遺傳演算法具體應用

1、函數優化

函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。

2、組合優化

隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。

此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

3、車間調度

車間調度問題是一個典型的NP-Hard問題，遺傳演算法作為一種經典的智能演算法廣泛用於車間調度中，很多學者都致力於用遺傳演算法解決車間調度問題，現今也取得了十分豐碩的成果。

從最初的傳統車間調度（JSP）問題到柔性作業車間調度問題（FJSP），遺傳演算法都有優異的表現，在很多算例中都得到了最優或近優解。

(4)遺傳演算法作用擴展閱讀：

遺傳演算法的缺點

1、編碼不規范及編碼存在表示的不準確性。

2、單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值，這樣，計算的時間必然增加。

3、遺傳演算法通常的效率比其他傳統的優化方法低。

4、遺傳演算法容易過早收斂。

5、遺傳演算法對演算法的精度、可行度、計算復雜性等方面，還沒有有效的定量分析方法。

⑤ 關於遺傳演算法

遺傳演算法（Genetic Algorithm，簡稱GA）是美國 Michigan大學的 John Golland提出的一種建立在自然選擇和群體遺傳學機理基礎上的隨機、迭代、進化、具有廣泛適用性的搜索方法。現在已被廣泛用於學習、優化、自適應等問題中。圖4-1 給出了 GA搜索過程的直觀描述。圖中曲線對應一個具有復雜搜索空間（多峰空間）的問題。縱坐標表示適應度函數（目標函數），其值越大相應的解越優。橫坐標表示搜索點。顯然，用解析方法求解該目標函數是困難的。採用 GA時，首先隨機挑選若干個搜索點，然後分別從這些搜索點開始並行搜索。在搜索過程中，僅靠適應度來反復指導和執行 GA 搜索。在經過若干代的進化後，搜索點後都具有較高的適應度並接近最優解。

一個簡單GA由復制、雜交和變異三個遺傳運算元組成：

圖4-2 常規遺傳演算法流程圖

⑥ 什麼叫遺傳演算法，遺傳演算法有什麼用希望通俗一點兒

首先有個很神奇的現象：人類以及動物的進化都是朝著好的方向發展，雖然有的往壞的方向發展了，但是總體肯定是往好的方向發展。這看似不奇怪，但是我們知道，人類的基因組合是隨機的，沒有上帝約束。這種隨機過程的結果卻是一致的！！！！！我們的遺傳演算法就是從這里得到啟發！比如我要求y=x1+x2的最大值，兩個變數，我不用傳統的數學方法，就用幼兒園的方法，把所有可能取值帶進去算，然後找出最大的就行了！但是，有時候取值是連續的，沒關系！使其離散化，就像把模擬信號化成數字信號一樣！還有個問題，如果取值太多咋辦？這就是遺傳演算法的精髓！
首先，我不用取所有可能取值，我只取幾十個或者幾百個（自己定），然後進行處理，怎樣處理呢？讓我們回到剛開始的人類進化問題，雖然沒有上帝的幫忙，但是我們知道，自然界遵循優勝劣汰的發賊，遵循交叉變異的法則，雖然不能數字化，但是這是個趨勢！我們就是把這種法則數學化！所取的幾十個值我要剩下哪些？要拋棄哪些？要處理哪些？這都要我們自己選擇，肯定是選擇最合適的取值留下，經過一系列的處理，就生成了新的群體，然後再處理，自己約定處理到第幾次就可以了，取出現過的最大值
不用擔心取到的是不是最大值，因為數學上已經有了證明，這種方法是收斂的，概率是1，所以盡管放心的做，具體的做法要參考相關書籍，不難的。
遺傳演算法的最大用處就是解決數學理論不能解決的問題！比如路徑規劃，調度問題……

⑦ 遺傳演算法

遺傳演算法是從代表問題可能潛在解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因的組合，它決定了個體形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼。初始種群產生之後，按照適者生存和優勝劣汰的原理，逐代（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的變化范圍加大。

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

⑧ TSP遺傳演算法的作用是什麼

你是問為什麼要用遺傳演算法求解TSP？那麼答案就是，TSP問題如果用窮舉的方法搜索，會由於可行解太多而無法在有效時間之內完成，而遺傳演算法則是不使用窮舉的方法之一。
如果你是想問為什麼要求解TSP，那麼就是因為兩個原因，一個是TSP本身是實際問題抽象而來的，而且和tsp近似的還有很多不同的最短路徑問題，都是實際生活中會出現的，不管是規劃人的路徑還是機械手臂的路徑，都會用到。第二個原因是tsp是NP完全問題，和很多其他問題一樣，都是NP完全的，這就意味著，只要其中一個問題解決了，另外的NP完全問題也能夠解決，所以研究它也具有理論價值。

⑨ 遺傳演算法

優化的演算法有很多種，從最基本的梯度下降法到現在的一些啟發式演算法，如遺傳演算法(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、所求問題最優值小於給定的閾值.