多種群遺傳演算法

『壹』 遺傳演算法

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

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

『貳』 遺傳演算法的基本原理

遺傳演算法的基本原理和方法

一、編碼

編碼：把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。

解碼（解碼）：遺傳演算法解空間向問題空間的轉換。

二進制編碼的缺點是漢明懸崖（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的正態分布的一個隨機數來替換原有的基因值。

『叄』 遺傳演算法的現狀

進入90年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳演算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳演算法進行優化和規則學習的能力也顯著提高，同時產業應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳演算法增添了新的活力。遺傳演算法的應用研究已從初期的組合優化求解擴展到了許多更新、更工程化的應用方面。
隨著應用領域的擴展，遺傳演算法的研究出現了幾個引人注目的新動向：一是基於遺傳演算法的機器學習，這一新的研究課題把遺傳演算法從歷來離散的搜索空間的優化搜索演算法擴展到具有獨特的規則生成功能的嶄新的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精煉的瓶頸難題帶來了希望。二是遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是並行處理的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智能計算機體系結構的研究都是十分重要的。四是遺傳演算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳演算法在這方面將會發揮一定的作用，五是遺傳演算法和進化規劃（Evolution Programming,EP）以及進化策略（Evolution Strategy,ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳演算法同時獨立發展起來的，同遺傳演算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳演算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。
1991年D.Whitey在他的論文中提出了基於領域交叉的交叉運算元（Adjacency based crossover），這個運算元是特別針對用序號表示基因的個體的交叉，並將其應用到了TSP問題中，通過實驗對其進行了驗證。D.H.Ackley等提出了隨機迭代遺傳爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）採用了一種復雜的概率選舉機制，此機制中由m個「投票者」來共同決定新個體的值（m表示群體的大小）。實驗結果表明，SIGH與單點交叉、均勻交叉的神經遺傳演算法相比，所測試的六個函數中有四個表現出更好的性能，而且總體來講，SIGH比現存的許多演算法在求解速度方面更有競爭力。H.Bersini和G.Seront將遺傳演算法與單一方法（simplex method）結合起來，形成了一種叫單一操作的多親交叉運算元（simplex crossover），該運算元在根據兩個母體以及一個額外的個體產生新個體，事實上他的交叉結果與對三個個體用選舉交叉產生的結果一致。同時，文獻還將三者交叉運算元與點交叉、均勻交叉做了比較，結果表明，三者交叉運算元比其餘兩個有更好的性能。
1992年，英國格拉斯哥大學的李耘（Yun Li）指導博士生將基於二進制基因的遺傳演算法擴展到七進制、十進制、整數、浮點等的基因，以便將遺傳演算法更有效地應用於模糊參量，系統結構等的直接優化，於1997年開發了可能是世界上最受歡迎的、也是最早之一的遺傳/進化演算法的網上程序 EA_demo，以幫助新手在線互動式了解進化計算的編碼和工作原理 ，並在格拉斯哥召開第二屆IEE/IEEE遺傳演算法應用國際會議，於2000年組織了由遺傳編程(Genetic Programming)發明人斯坦福的 John Koza 等參加的 EvoNet 研討會，探索融合GA與GP結構尋優，超越固定結構和數值優化的局限性。
國內也有不少的專家和學者對遺傳演算法的交叉運算元進行改進。2002年，戴曉明等應用多種群遺傳並行進化的思想，對不同種群基於不同的遺傳策略，如變異概率，不同的變異運算元等來搜索變數空間，並利用種群間遷移運算元來進行遺傳信息交流，以解決經典遺傳演算法的收斂到局部最優值問題
2004年，趙宏立等針對簡單遺傳演算法在較大規模組合優化問題上搜索效率不高的現象，提出了一種用基因塊編碼的並行遺傳演算法（Building-block Coded Parallel GA，BCPGA）。該方法以粗粒度並行遺傳演算法為基本框架，在染色體群體中識別出可能的基因塊，然後用基因塊作為新的基因單位對染色體重新編碼，產生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。
2005年，江雷等針對並行遺傳演算法求解TSP問題，探討了使用彈性策略來維持群體的多樣性，使得演算法跨過局部收斂的障礙，向全局最優解方向進化。

『肆』 遺傳演算法的基本原理

遺傳演算法通常的實現方式，就是用程序來模擬生物種群進化的過程。對於一個求最優解的問題，我們可以把一定數量的候選解（稱為個體）抽象地表示為染色體，使種群向更好的解來進化。大家知道，使用演算法解決問題的時候，解通常都是用數據或者字元串等表示的，而這個數據或字元串對應到生物中就是某個個體的「染色體」。進化從完全隨機個體的種群開始，之後一代一代發生。在每一代中評價其在整個種群的適應度，從當前種群中隨機地選擇多個個體（基於它們的適應度），通過自然選擇和突變產生新的種群，該種群在演算法的下一次迭代中成為當前種群。其具體的計算步驟如下：

• 編碼：將問題空間轉換為遺傳空間；

• 生成初始種群：隨機生成P個染色體；

• 種群適應度計算：按照確定的適應度函數，計算各個染色體的適應度；

• 選擇：根據染色體適應度，按照選擇運算元進行染色體的選擇；

• 交叉：按照交叉概率對被選擇的染色體進行交叉操作，形成下一代種群；

• 突變：按照突變概率對下一代種群中的個體進行突變操作；

• 返回第3步繼續迭代，直到滿足終止條件。

『伍』 什麼是拉馬克運算元

如果在代的演化過程中，遺傳演算法保留最好的解，並且演算法以交叉和變異作為隨機化運算元，則對於一個全局優化問題，隨著演化代數趨於無窮，遺傳演算法將以概率1找到全局最優解
多種群遺傳演算法相比遺傳演算法在性能上能夠有所提高,但對具有較多局部最優解的作業車間調度問題,多種群遺傳演算法仍然難以改善易陷入局部最優解和局部搜索能力差的缺點.因此,提出了一種求解作業車間調度問題的新演算法MGA-MBL(multi-population genetic algorithm based on memory-base and Lamarckian evolution for jobshop scheling problem).MGA-MBL在多種群遺傳演算法的基礎上通過引入記憶庫策略,不但使子種群間的個體可以進行信息交換,而且有利於保持整個種群的多樣性;通過構造基於拉馬克進化機制的局部搜索運算元來提高多種群遺傳演算法中子種群進化的局部搜索能力.由於MGA-MBL採用了全局尋優能力較強的模擬退火演算法對記憶庫中的個體進行優化,從而緩解了多種群遺傳演算法易陷入局部最優解的問題,並提高了演算法求解作業車間調度問題的性能.對著名的benchmark數據進行測試,實驗結果證實了MGA-MBL在求解作業車間調度問題上的有效性.

『陸』 遺傳演算法是什麼

遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。
遺傳演算法(Genetic Algorithms簡稱GA)是由美國Michigan大學的John Holland教授於20世紀60年代末創建的。它來源於達爾文的進化論和孟德爾、摩根的遺傳學理論，通過模擬生物進化的機制來構造人工系統。遺傳演算法作為一種全局優化方法，提供了一種求解復雜系統優化問題的通用框架，它不依賴於問題的具體領域，對優化函數的要求很低並且對不同種類的問題具有很強的魯棒性，所以廣泛應用於計算機科學、工程技術和社會科學等領域。John Holland教授通過模擬生物進化過程設計了最初的遺傳演算法，我們稱之為標准遺傳演算法。
標准遺傳演算法流程如下：
1）初始化遺傳演算法的群體，包括初始種群的產生以及對個體的編碼。
2）計算種群中每個個體的適應度，個體的適應度反映了其優劣程度。
3）通過選擇操作選出一些個體，這些個體就是母代個體，用來繁殖子代。
4）選出的母代個體兩兩配對，按照一定的交叉概率來進行交叉，產生子代個體。
5）按照一定的變異概率，對產生的子代個體進行變異操作。
6）將完成交叉、變異操作的子代個體，替代種群中某些個體，達到更新種群的目的。
7）再次計算種群的適應度，找出當前的最優個體。
8）判斷是否滿足終止條件，不滿足則返回第3）步繼續迭代，滿足則退出迭代過程，第7）步中得到的當前最優個體，通過解碼，就作為本次演算法的近似最優解。

具體你可以到網路文庫去搜索遺傳演算法相關的論文，很多的。
你也可以參考網路里對遺傳演算法的介紹。

『柒』 遺傳演算法^[1，]

遺傳演算法，又稱基因演算法(Genetic Algorithm，簡稱GA)，也是一種啟發式蒙特卡洛優化演算法。遺傳演算法最早是由Holland(1975)提出，它模擬了生物適者生存、優勝劣汰的進化過程，具有不依賴於初始模型的選擇、不容易陷入局部極小、在反演過程中不用計算偏導數矩陣等優點。遺傳演算法最早由Stoffa和Sen(1991)用於地震波的一維反演，之後在地球物理資料的非線性反演中得到廣泛的應用。GA演算法對模型群體進行追蹤、搜索，即模型狀態通過模型群體傳送，具有比模擬退火法更大、更復雜的「記憶」，潛力更大。

遺傳演算法在反演中的基本思路和過程是:

(1)將生物體看成模型，模型參數看成染色體，有多少個模型的參數就有多少個染色體。對每個模型的參數(染色體)用二進制進行編碼，這個編碼就是基因。

(2)隨機生成一個模型群體(相當於生物的種群)，然後在模型群體中進行繁殖，通過母本的選擇、交換和變異等遺傳操作產生下一代，然後保留較好基因，淘汰較差基因。

(3)通過一代一代的繁殖優勝劣汰的進化過程，最後所剩下的種群基本上都是最優的基因，種群趨於一致。所謂群體「一致」，即群體目標函數的方差或標准差很小，或者群體目標函數的均值接近於極值(可能是極大值或極小值)，從而獲得非線性反演問題所對應的最優解或近似最優解。

下面以一個實例來簡述遺傳演算法的基本過程。

[例1]設m是正整數，且0≤m≤127，求方程φ(m)=m²的極大值。

這個例子極為簡單，只有一個模型參數，因此只有一條染色體，目標函數的極值是極大值(此例子來自阮百堯課件)。遺傳演算法通過以下7個步驟來實現:

(1)模型參數二進制編碼。

每個模型參數就是一條染色體，把十進制的模型參數表示為二進制，這就是基因。首先確定二進制碼的長度(基因的長度):

2^N=[m_max(i)-m_min(i)]/Δm(i) (8.20)

其中:N為第i條染色體基因的長度(也就是第i個模型參數的二進制碼位數);[m_min(i)，m_max(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(m_i)為繁殖概率;φ(m_i)為第i個模型的目標函數;φ_AVG為目標函數的平均值。對於極小化問題來說，規定目標函數值高於平均值的不傳代;對於極大化問題來說，反之即可。

就[例1]來說，要求目標函數取極大值，所以規定目標函數小於平均值的模型不傳代，大於它的可以傳代。對第一代，為了防止基因丟失，可先不捨去繁殖概率小的模型，讓它與概率大的模型配對。如:本例中70與56配對，101與15配對產生子代，見表8.2。

表8.2 基因交換表

(4)基因交換。

將配對的兩個親本模型的部分染色體相互交換，其中交換點可隨機選擇，形成兩個新的子代(見表8.2)。兩個染色體遺傳基因的交換過程是遺傳演算法的「繁殖」過程，是母本的重組過程。

為了使染色體的基因交換比較徹底，Stoffa等人提出了一個交換概率p_x來控制選擇操作的效果。如果p_x的值較小，那麼交換點的位置就比較靠低位，這時的交換操作基本是低位交換，交換前後模型的染色體變化不是太大。如果p_x的值較大，那麼交換點的位置就比較靠高位，此時的交換操作可以在較大的染色體空間進行，交換前後模型數值變化可以很大。

在[例1]中:15、101和56、70作為母本通過交換繁殖出子代5、6、111、120。所選擇的基因交換位置見表8.2。有下劃線的，是要交換的基因位置。

(5)更新。

母本模型和子本模型如何選擇保留一定數量作為新的母本，就是模型更新。不同的策略會導致不同的結果。一般而言，若產生的新一代模型較好，則選擇新一代模型而淘汰上一代模型。否則，則必須根據一定的更新概率p_u來選擇上一代模型來取代新一代中某些較劣的模型。

經過更新以後，繁殖時對子代再進行優勝劣汰的選擇。對於極大值問題，大於目標函數平均值的子代可以繁殖，小於目標函數平均值的子代不能繁殖。由於新的種群能繁殖的個體數量減小了，所以要多繁殖幾次，維持種群個體的數量保持平衡。

在[例1]中，子代較好，所以完全淘汰上一代模型，完全用子代作為新的母本。選擇子代目標函數最大的兩個模型進行繁殖，分別是111、120。

(6)基因變異。

在新的配對好的母本中，按一定比例隨機選擇模型進行變異，變異操作就是模擬自然界中的環境因素，就是按比較小的變異概率p_m將染色體某位或某幾位的基因發生突變(即將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、變異概率p_m以及更新概率p_u，這些參數的選擇與設定目前尚無統一的理論指導，多數都視具體問題而定。Stoffa等(1991)的研究表明，適中的交換概率(p_x≈0.6)、較小的變異概率(p_m≈0.01)和較大的更新概率(p_u≈0.9)，遺傳演算法的性能較優。

與模擬退火反演演算法相同，遺傳演算法與傳統的線性反演方法相比，該方法具有:不依賴初始模型的選擇、能尋找全局最小點而不陷入局部極小、在反演過程中不用計算雅克比偏導數矩陣等優點。另外，遺傳演算法具有並行性，隨著並行計算和集群式計算機技術的發展，該演算法將會得到越來越廣泛的研究與應用。

但是遺傳演算法作為類蒙特卡洛演算法同樣需要進行大量的正演計算，種群個體數量越大，繁衍代數越多，則計算量越大。所以和前面的最小二乘法相比，速度不是它的優勢。

『捌』 遺傳演算法種群規模是怎麼得到的

種群規模是指任意一代中的個體總數，這個是人為設定的，種群規模越大越可能找到全局解，但運行時間也相對較長，一般在40-100之間取值，像我就習慣選60.
至於你所處理的問題，可以對比不同的種群規模下最優解和運行時間，然後折衷取。
拓展資料：
遺傳演算法（Genetic Algorithm，GA）最早是由美國的 John holland於20世紀70年代提出，該演算法是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。該演算法通過數學的方式，利用計算機模擬運算，將問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為復雜的組合優化問題時，相對一些常規的優化演算法，通常能夠較快地獲得較好的優化結果。遺傳演算法已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。
運算過程
遺傳演算法的基本運算過程如下：
（1）初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。
（2）個體評價：計算群體P(t)中各個個體的適應度。
（3）選擇運算：將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。
（4）交叉運算：將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。[2]
（5）變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t+1)。
（6）終止條件判斷：若t=T，則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。
遺傳操作包括以下三個基本遺傳運算元(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。

『玖』 遺傳演算法理解

遺傳演算法是一種進化演算法，進化是什麼哪？就是種群逐漸適應生存環境，種群中個體不斷得到改良的過程。

遺傳演算法是一種對生物遺傳的模擬、在演算法中，初始化一個種群，種群中的每個染色體個體都是一種解決方案，我們通過適應性fitness來衡量這個解決方案的好壞。並對它們進行選擇、變異、交叉的操作，找到最優的解決方案。

總結一下遺傳演算法的基本的步驟：

1.初始化一個種群，並評估每條染色體所對應個體的適應度。

2.選擇、交叉、變異，產生新的種群

3.再評估每個個體的適應值，如果適應值達到要求或者達到最大循環次數，否則重復2，不斷產生新種群。

知道了GA的大致流程之後、來具體分析一下細節，怎麼實現吧

我們知道遺傳演算法起源於生物遺傳，因此在種群中每個個體就是一個染色體，那如何對染色體進行編碼，讓它表示我們的解決方案那（就是把現實要優化的參數用編碼表示成一個染色體）。這里就遇到了一個編碼、解碼的問題，我們將需要優化的目標編碼成染色體，然後再解碼為我們可以用來計算fitness的解；

一般在進行參數優化時，一般有兩種方式：實數編碼、二進制編碼

實數編碼：基因直接用實數進行表示，這樣的表示方法比較簡單，不用特意解碼了，但是在交叉和變異時，容易過早收斂，陷入局部最優。

二進制編碼：將基因用二進制的形式表示，將參數的值轉化為二進制形式，這樣交叉、變異時更好操作，多樣性好，但是佔用的存儲空間大，需要解碼。

染色體就稱為個體。對於一次實驗，個體就是需要優化參數的一種解、許多這樣的個體就構成了種群。

在面對群體中那麼多個體時，如何判斷個體的好壞呢，就是通過適應值函數了，將解帶入適應值函數，適應值越大、解越好。

在遺傳演算法中，我們怎麼使得裡面的個體變得越來越優秀呢？

核心思想就是：選擇優秀的、淘汰不好的，並且為了生成更好的解，我們要嘗試交叉、變異，帶來新的解。

選擇就是從當前的種群中選擇出比較好的個體、淘汰不好的個體

常見的選擇方法有：輪盤賭選擇、錦標賽選擇、最佳保留選擇等等

輪盤賭選擇就是根據每個個體fitness和種群所有fitness之和比較，確定每個個體被選中的概率，然後進行n次選擇，選擇n個個體構成新種群，是一種放回抽樣的方式。

錦標賽就是每次從種群中選擇m個個體，選擇最優的，放入新種群，重復選擇，直到新種群中個體數目達到n。

最佳保留選擇就是在輪盤賭的基礎上，將fitness個體先加進新種群，因為輪盤賭是一種概率模型，可能存在最優個體沒有進入新種群的情況。

在選擇之後，就要考慮產生新的、更優秀的解，為種群帶來新的血液。遺傳演算法的思路是交叉兩個優秀的解，往往get好的解。

交叉通過在經過選擇的種群中，隨機選擇一對父母，將它們的染色體進行交叉，生成新的個體，替代原來的解。

常用的交叉方法有：單點交叉、多點交叉等等。

交叉就像生物裡面，染色體交換基因一樣的～但是並不是種群中所有個體都進行交叉的，實現時可以，設置一個交叉率和交叉概率，隨機選擇種群中兩個體、隨機一個數，小於交叉率就進行交叉操作，並根據交叉概率判斷交叉的程度，從而生成新個體，反之就保留這兩個體。

變異也是一種產生新個體的方式，通過改變個體上基因，期望產生更好的解。比如在以二進制編碼的個體上，將裡面的0、1進行等位變化啥的，就是0變1、1變0這樣。同樣也要考慮變異率、變異產生的新解是不可控的，可能很好，也可能很壞，不能像交叉一樣，確保一定的效果，所以往往變異率設置的比較小。