Ⅰ 優化演算法筆記（六）遺傳演算法
遺傳演算法(Genetic Algorithms，GA)是一種模擬自然中生物的遺傳、進化以適應環境的智能演算法。由於其演算法流程簡單，參數較少優化速度較快，效果較好，在圖像處理、函數優化、信號處理、模式識別等領域有著廣泛的應用。
在遺傳演算法（GA）中，每一個待求問題的候選解被抽象成為種群中一個個體的基因。種群中個體基因的好壞由表示個體基因的候選解在待求問題中的所的得值來評判。種群中的個體通過與其他個體交叉產生下一代，每一代中個體均只進行一次交叉。兩個進行交叉的個體有一定幾率交換一個或者多個對應位的基因來產生新的後代。每個後代都有一定的概率發生變異。發生變異的個體的某一位或某幾位基因會變異成其他值。最終將以個體的適應度值為概率選取個體保留至下一代。
遺傳演算法啟發於生物的繁殖與dna的重組，本次的主角選什麼呢？還是根據大家熟悉的孟德爾遺傳規律選豌豆吧，選動物的話又會有人疑車，還是植物比較好，本次的主角就是它了。
遺傳演算法包含三個操作（運算元）：交叉，變異和選擇操作。下面我們將詳細介紹這三個操作。
大多數生物的遺傳信息都儲存在DNA，一種雙螺旋結構的復雜有機化合物。其含氮鹼基為腺嘌呤、鳥嘌呤、胞嘧啶及胸腺嘧啶。
表格中表示了一個有10個基因的個體，它們每一個基因的值為0或者1。
生物的有性生殖一般伴隨著基因的重組。遺傳演算法中父輩和母輩個體產生子代個體的過程稱為交叉。
表中給出了兩個豌豆的基因，它們均有10個等位基因（即編號相同的基因）。
遺傳演算法的交叉過程會在兩個個體中隨機選擇1位或者n位基因進行交叉，即這兩個個體交換等位基因。
如，A豌豆和B豌豆在第6位基因上進行交叉，則其結果如下
當兩個個體交叉的等位基因相同時，交叉過程也有可能沒有產生新的個體，如交叉A豌豆和B豌豆的第2位基因時，交叉操作並沒有產生新的基因。
一般的會給群體設定一個交叉率，crossRate，表示會在群體中選取一定比例的個體進行交叉，交叉率相對較大，一般取值為0.8。
基因的變異是生物進化的一個主要因素。
遺傳演算法中變異操作相對簡單，只需要將一個隨機位基因的值修改就行了，因為其值只為0或1，那麼當基因為0時，變異操作會將其值設為1，當基因值為1時，變異操作會將其值設為0。
上圖表示了A豌豆第3位基因變異後的基因編碼。
與交叉率相似，變異操作也有變異率，alterRate，但是變異率會遠低於交叉率，否則會產生大量的隨機基因。一般變異率為0.05。
選擇操作是遺傳演算法中的一個關鍵操作，它的主要作用就是根據一定的策略隨機選擇個體保留至下一代。適應度越優的個體被保留至下一代的概率越大。
實現上，我們經常使用「輪盤賭」來隨機選擇保留下哪個個體。
假設有4個豌豆A、B、C、D，它們的適應度值如下：
適應度值越大越好，則它們組成的輪盤如下圖：
但由於輪盤賭選擇是一個隨機選擇過程，A、B、C、D進行輪盤賭選擇後產生的下一代也有可能出現A、A、A、A的情況，即雖然有些個體的適應度值不好，但是運氣不錯，也被選擇留到了下一代。
遺產演算法的三個主要操作介紹完了，下面我們來看看遺傳演算法的總體流程：
前面我們說了遺傳演算法的流程及各個操作，那麼對於實際的問題我們應該如何將其編碼為基因呢？
對於計算機來所所有的數據都使用二進制數據進行存放，如float類型和double類型的數據。
float類型的數據將保存為32位的二進制數據：1bit（符號位） 8bits（指數位） 23bits（尾數位）
如-1.234567f，表示為二進制位
Double類型的數據將保存為64位的二進制數據：1bit（符號位） 11bits（指數位） 53bits（尾數位）
如-1.234567d，表示為二進制為
可以看出同樣的數值不同的精度在計算機中存儲的內容也不相同。之前的適應度函數 ，由於有兩個double類型的參數，故其進行遺傳演算法基因編碼時，將有128位基因。
雖然基因數較多，但好在每個基因都是0或者1，交叉及變異操作非常簡單。
相比二進制編碼，十進制編碼的基因長度更短，適應度函數 有兩個輸入參數，那麼一個個體就有2個基因，但其交叉、變異操作相對復雜。
交叉操作
方案1：將一個基因作為一個整體，交換兩個個體的等位基因。
交換前
交換第1位基因後
方案2：將兩個個體的等位基因作為一個整體，使其和不變，但是值隨機
交換前
交換第1位基因後
假設A、B豌豆的第一位基因的和為40，即 ,第一位基因的取值范圍為0-30，那麼A、B豌豆的第一位基因的取值范圍為[10,30],即 為[0,30]的隨機數， 。
變異操作，將隨機的一位基因設置為該基因取值范圍內的隨機數即可。
這個過程說起來簡單但其實現並不容易。
我們要將它們的值映射到一個軸上才能進行隨機選擇，畢竟我們無法去繪制一個輪盤來模擬這個過程
如圖，將ABCD根據其值按順序排列，取[0,10]內的隨機數r，若r在[0,1]內則選擇A,在(1,3]內則選擇B,在(3,6]內則選擇C,在(6,10]則選擇D。
當然這仍然會有問題，即當D>>A、B、C時，假如它們的值分布如下
那麼顯然，選D的概率明顯大於其他，根據輪盤賭的選擇，下一代極有可能全是D的後代有沒有辦法均衡一下呢？
首先我想到了一個函數，
不要問我為什麼我不知道什麼是神經什麼網路的，什麼softmax、cnn統統沒聽說過。
這樣一來，它們之間的差距沒有之前那麼大了，只要個體適應度值在均值以上那麼它被保留至下一代的概率會相對較大，當然這樣縮小了個體之間的差距，對真正優秀的個體來說不太公平，相對應，我們可以在每次選擇過程中保留當前的最優個體到下一代，不用參與輪盤賭這個殘酷的淘汰過程。
最令人高興的環節到了，又可以愉快的湊字數了。
由於遺傳演算法的收斂速度實在是太慢，區區50代，幾乎得不到好的結果，so我們把它的最大迭代次數放寬到200代。
使用二進制編碼來進行求解
參數如下：
求解過程如上圖，可以看出基因收斂的很快，在接近20代時就圖中就只剩一個點了，之後的點大概是根據變異操作產生。看一下最後的結果。
可以看出最好的結果已經得到了最優解，但是10次實驗的最差值和平均值都差的令人發指。為什麼會這樣呢？
問題出在二進制編碼上，由於double類型的編碼有11位指數位和52位小數位，這會導致交叉、變異操作選到指數位和小數位的概率不均衡，在小數位上的修改對結果的影響太小而對指數為的修改對結果的影響太大，
如-1.234567d，表示為二進制為
對指數為第5位進行變異操作後的結果為-2.8744502924382686E-10，而對小數位第5為進行變異操作後的結果為-1.218942。可以看出這兩部分對數值結果的影響太不均衡，得出較好的結果時大概率是指數位與解非常相近，否則很難得出好的結果，就像上面的最差值和均值一樣。
所以使用上面的二進制編碼不是一個好的基因編碼方式，因此在下面的實驗中，將使用十進制來進行試驗。
使用:十進制編碼來進行求解
參數如下：
我們可以看到直到40代時，所有的個體才收束到一點，但隨後仍不斷的新的個體出現。我們發現再後面的新粒子總是在同一水平線或者豎直線上，因為交叉操作直接交換了兩個個體的基因，那麼他們會相互交換x坐標或者y坐標，導致新個體看起來像在一條直線上。
我們來看看這次的結果。
這次最優值沒有得到最優解，但是最差值沒有二進制那麼差，雖然也不容樂觀。使用交換基因的方式來進行交叉操作的搜索能力不足，加之輪盤賭的選擇會有很大概率選擇最優個體，個體總出現在矩形的邊上。
下面我們先改變輪盤賭的選擇策略，使用上面的sigmod函數方案，並且保留最優個體至下一代。
使用:十進制編碼來進行求解
參數如下：
看圖好像跟之前的沒什麼區別，讓我們們看看最終的結果：
可以看出，最優值沒有什麼變化，但是最差值和平均值有了較大的提升，說明該輪盤賭方案使演算法的魯棒性有了較大的提升。在每次保留最優個體的情況下，對於其他的個體的選擇概率相對平均，sigmod函數使得即使適應度函數值相差不太大的個體被選到的概率相近，增加了基因的多樣性。
使用:十進制編碼來進行求解，改變交叉方案，保持兩個個體等位基因和不變的情況下隨機賦值。
參數如下：
上圖可以看出該方案與之前有明顯的不同，在整個過程中，個體始終遍布整個搜索空間，雖然新產生的個體大多還是集中在一個十字架型的位置上，但其他位置的個體比之前的方案要多。
看看結果，
這次的結果明顯好於之前的所有方案，但仍可以看出，十進制的遺傳演算法的精度不高，只能找到最優解的附近，也有可能是演算法的收斂速度實在太慢，還沒有收斂到最優解。
遺傳演算法的探究到此也告一段落，在研究遺傳演算法時總有一種力不從心的感覺，問題可能在於遺傳演算法只提出了一個大致的核心思想，其他的實現細節都需要自己去思考，而每個人的思維都不一樣，一萬個人能寫出一萬種遺傳演算法，其實不僅是遺傳演算法，後面的很多演算法都是如此。
為什麼沒有對遺傳演算法的參數進行調優，因為遺傳演算法的參數過於簡單，對結果的影響的可解釋性較強，意義明顯，實驗的意義不大。
遺傳演算法由於是模仿了生物的進化過程，因此我感覺它的求解速度非常的慢，而且進化出來的結果不一定是最適應環境的，就像人的闌尾、視網膜結構等，雖然不是最佳的選擇但是也被保留到了今天。生物的進化的隨機性較大，要不是恐龍的滅絕，也不會有人類的統治，要不是人類有兩只手，每隻手有5根手指，也不會產生10進制。
以下指標純屬個人yy,僅供參考
目錄
上一篇 優化演算法筆記（五）粒子群演算法（3）
下一篇 優化演算法筆記（七）差分進化演算法
優化演算法matlab實現（六）遺傳演算法matlab實現
Ⅱ 遺傳演算法 交叉的個數怎麼確定
遺傳演算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。這說明遺傳演算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。
Ⅲ 遺傳演算法<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)，遺傳演算法的性能較優。
與模擬退火反演演算法相同，遺傳演算法與傳統的線性反演方法相比，該方法具有:不依賴初始模型的選擇、能尋找全局最小點而不陷入局部極小、在反演過程中不用計算雅克比偏導數矩陣等優點。另外，遺傳演算法具有並行性，隨著並行計算和集群式計算機技術的發展，該演算法將會得到越來越廣泛的研究與應用。
但是遺傳演算法作為類蒙特卡洛演算法同樣需要進行大量的正演計算，種群個體數量越大，繁衍代數越多，則計算量越大。所以和前面的最小二乘法相比，速度不是它的優勢。
Ⅳ 遺傳演算法
參考文獻： 知乎 遺傳演算法 編碼解碼知識
實現遺傳演算法的第一步就是明確對求解問題的編碼和解碼方式。對於函數優化問題，一般有兩種編碼方式，各具優缺點
實數編碼：直接用實數表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優
二進制編碼：穩定性高，種群多樣性大，但需要的存儲空間大，需要解碼且難以理解
對於求解函數最大值問題，我選擇的是二進制編碼。
以我們的目標函數 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.變異：根據需要進行選擇
Ⅳ 遺傳演算法的編碼方法有幾種
常用的編碼介紹
1、二進制編碼：
（1）定義：二進制編碼方法是使用二值符號集{0,1}，它所構成的個體基因型是一個二進制編碼符號串。二進制編碼符號串的長度與問題所要求的求解精度有關。
（2）舉例：0≤x≤1023,精度為1,m表示二進制編碼的長度。則有建議性說法：使
2m-1≤1000（跟精度有關）≤2m-1。取m=10
則X:0010101111就可以表示一個個體，它所對應的問題空間的值是x=175。
（3）優缺點
優點：符合最小字元集原則，便於用模式定理分析；
缺點：連續函數離散化時的映射誤差。
2、格雷碼編碼
（1）定義：格雷碼編碼是其連續的兩個整數所對應的編碼之間只有一個碼位是不同的，其餘碼位完全相同。它是二進制編碼方法的一種變形。
十進制數0—15之間的二進制碼和相應的格雷碼分別編碼如下。
二進制編碼為：0000，0001，0010，001
1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷碼編碼為：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）舉例：對於區間[0。1023]中兩個鄰近的整數X1=175和X2=176，若用長度為10位的二進制編碼，可表示為X11：0010101111和X12
0010110000，而使用同樣長度的格雷碼，它們可分別表示為X21：0010101111和X22：0010101000。
（3）優點：增強了遺傳演算法的局部搜索能力，便於連續函數的局部控制項搜索。
3、浮點數(實數)編碼
（1）定義：浮點數編碼是指個體的每個基因值用某一范圍內的一個浮點數來表示，而個體的編碼長度等於其決策變數的個數。因為這種編碼方法使用的決策變數的真實值，也稱之為真值編碼方法。
（2）舉例：
（3）優點：實數編碼是遺傳演算法中在解決連續參數優化問題時普遍使用的一種編碼方式，具有較高的精度，在表示連續漸變問題方面具有優勢。
4、排列編碼
排列編碼也叫序列編碼，是針對一些特殊問題的特定編碼方式。排序編碼使問題簡潔，易於理解。該編碼方式將有限集合內的元素進行排列。若集合內包含m個元素，則存在m!種排列方法，當m不大時，m!也不會太大，窮舉法就可以解決問題。當m比較大時，m!就會變得非常大，窮舉法失效，遺傳演算法在解決這類問題上具有優勢。如解決TSP問題時，用排列編碼自然、合理。
5、其它編碼方式
多參數級聯編碼等
Ⅵ 遺傳演算法的基本原理
遺傳演算法的基本原理和方法
一、編碼
編碼：把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。
解碼（解碼）：遺傳演算法解空間向問題空間的轉換。
二進制編碼的缺點是漢明懸崖（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的正態分布的一個隨機數來替換原有的基因值。
Ⅶ 遺傳演算法
遺傳演算法是從代表問題可能潛在解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因的組合，它決定了個體形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼。初始種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解。在每一代，根據問題域中個體的適應度（fitness）大小挑選（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群自然進化一樣的後生代種群比前代更加適應環境，末代種群中的最優個體經過編碼（decoding），可以作為問題近似最優解。
5.4.1 非線性優化與模型編碼
假定有一組未知參量
xi（i=1，2，…，M）
構成模型向量m，它的非線性目標函數為Φ（m）。根據先驗知識，對每個未知量都有上下界αi及bi，即αi≤x≤bi，同時可用間隔di把它離散化，使
di=（bi-αi）/N （5.4.1）
於是，所有允許的模型m將被限制在集
xi=αi+jdi（j=0，1，…，N） （5.4.2）
之內。
通常目標泛函（如經濟學中的成本函數）表示觀測函數與某種期望模型的失擬，因此非線性優化問題即為在上述限制的模型中求使Φ（m）極小的模型。對少數要求擬合最佳的問題，求目標函數的極大與失擬函數求極小是一致的。對於地球物理問題，通常要進行殺重離散化。首先，地球模型一般用連續函數表示，反演時要離散化為參數集才能用於計算。有時，也將未知函數展開成已知基函數的集，用其系數作為離散化的參數集xi，第二次離散化的需要是因為每一個未知參數在其變化范圍內再次被離散化，以使離散模型空間最終包含著有限個非線性優化可選擇的模型，其個數為
地球物理數據處理教程
其中M為未知參數xi的個數。由此式可見，K決定於每個參數離散化的間隔di及其變化范圍（αi，bi），在大多數情況下它們只能靠先驗知識來選擇。
一般而言，優化問題非線性化的程度越高，逐次線性化的方法越不穩定，而對蒙特卡洛法卻沒有影響，因為此法從有限模型空間中隨機地挑選新模型並計算其目標函數 Φ（m）。遺傳演算法與此不同的是同時計算一組模型（開始時是隨機地選擇的），然後把它進行二進制編碼，並通過繁殖、雜交和變異產生一組新模型進一步有限的模型空間搜索。編碼的方法可有多種，下面舉最簡單的例說明之，對於有符號的地球物理參數反演時的編碼方式一般要更復雜些。
假設地球為有三個水平層的層次模型，含層底界面深度hj（j=1，2，3）及層速度vj（j=1，2，3）這兩組參數。如某個模型的參數值為（十進制）：
h1=6，h2=18，h3=28，單位為10m
v1=6，v2=18，v3=28，單位為 hm/s
按正常的二進制編碼法它們可分別用以下字元串表示為：
地球物理數據處理教程
為了減少位元組，這種編碼方式改變了慣用的單位制，只是按精度要求（深度為10m，波速為hm/s）來規定參數的碼值，同時也意味著模型空間離散化間距di都規格化為一個單位（即10m，或hm/s）。當然，在此編碼的基礎上，還可以寫出多種新的編碼字元串。例如，三參數值的對應位元組順序重排，就可組成以下新的二進制碼串：
地球物理數據處理教程
模型參數的二進制編碼是一種數學上的抽象，通過編碼把具體的非線性問題和生物演化過程聯系了起來，因為這時形成的編碼字元串就相當於一組遺傳基因的密碼。不僅是二進制編碼，十進制編碼也可直接用於遺傳演算法。根據生物系統傳代過程的規律，這些基因信息將在繁殖中傳到下一帶，而下一代將按照「適者生存」的原則決定種屬的發展和消亡，而優化准則或目標函數就起到了決定「適者生存」的作用，即保留失擬較小的新模型，而放棄失擬大的模型。在傳帶過程中用編碼表示的基因部分地交合和變異，即字元串中的一些子串被保留，有的改變，以使傳代的過程向優化的目標演化。總的來說，遺傳演算法可分為三步：繁殖、雜交和變異。其具體實現過程見圖5.8。
圖5.8 遺傳演算法實現過程
5.4.2 遺傳演算法在地震反演中的應用
以地震走時反演為例，根據最小二乘准則使合成記錄與實測數據的擬合差取極小，目標函數可取為
地球物理數據處理教程
式中：Ti，0為觀測資料中提取出的地震走時；Ti，s為合成地震或射線追蹤算出的地震走時；ΔT為所有合成地震走時的平均值；NA為合成地震數據的個數，它可以少於實測Ti，0的個數，因為在射線追蹤時有陰影區存在，不一定能算出合成數據Tj，0。利用射線追蹤計算走時的方法很多，參見上一章。對於少數幾個波速為常數的水平層，走時反演的參數編碼方法可參照上一節介紹的分別對深度和速度編碼方法，二進制碼的字元串位數1不會太大。要注意的是由深度定出的字元串符合數值由淺到深增大的規律，這一約束條件不應在雜交和傳代過程中破壞。這種不等式的約束（h1＜h2＜h3…）在遺傳演算法中是容易實現的。
對於波場反演，較方便的做法是將地球介質作等間距的劃分。例如，將水平層狀介質細分為100個等厚度的水平層。在上地殼可假定波速小於6400 m/s（相當於解空間的硬約束），而波速空間距為100m/s，則可將波速用100m/s為單位，每層用6位二進制字元串表示波速，地層模型總共用600位二進制字元串表示（l=600）。初始模型可隨機地選取24～192個，然後通過繁殖雜交與變異。雜交概率在0.5～1.0之間，變異概率小於0.01。目標函數（即失擬方程）在頻率域可表示為
地球物理數據處理教程
式中：P0（ωk，vj）為實測地震道的頻譜；ωk為角頻率；vj為第j層的波速；Ps（ωk，vj）為相應的合成地震道；A（ωk）為地震儀及檢波器的頻率濾波器，例如，可取
A（ω）=sinC4（ω/ωN） （5.4.6）
式中ωN為Nyquist頻率，即ωN=π/Δt，Δt為時間采樣率。參數C為振幅擬合因子，它起到合成與觀測記錄之間幅度上匹配的作用。C的計算常用地震道的包絡函數的平均比值。例如，設E［］為波動信號的包絡函數，可令
地球物理數據處理教程
式中：tmax為包絡極大值的對應時間；J為總層數。包絡函數可通過復數道的模擬取得。
用遺傳演算法作波速反演時失擬最小的模型將一直保存到迭代停止。什麼時候停止傳代還沒有理論上可計算的好辦法，一般要顯示解空間的搜索范圍及局部密度，以此來判斷是否可以停止傳代。值得指出的是，由（5.4.4）和（5.4.5）式給出的目標函數對於有誤差的數據是有問題的，反演的目標不是追求對有誤差數據的完美擬合，而是要求出准確而且解析度最高的解估計。
遺傳演算法在執行中可能出現兩類問題。其一稱為「早熟」問題，即在傳代之初就隨機地選中了比較好的模型，它在傳代中起主導作用，而使其後的計算因散不開而白白浪費。通常，增加Q值可以改善這種情況。另一類問題正相反，即傳相當多代後仍然找不到一個特別好的解估計，即可能有幾百個算出的目標函數值都大同小異。這時，最好修改目標函數的比例因子（即（5.4.5）式的分母），以使繁殖概率Ps的變化范圍加大。
對於高維地震模型的反演，由於參數太多，相應的模型字元串太長，目前用遺傳演算法作反演的計算成本還嫌太高。實際上，為了加快計算，不僅要改進反演技巧和傳代的控制技術，而且還要大幅度提高正演計算的速度，避免對遺傳演算法大量的計算花費在正演合成上。