遺傳演算法的本質

1. 遺傳演算法、數值演算法、爬山演算法、模擬退火 各自的優缺點

遺傳演算法：其優點是能很好地處理約束，跳出局部最優，最終得到全局最優解。缺點是收斂速度慢，局部搜索能力弱，運行時間長，容易受到參數的影響。

模擬退火：具有局部搜索能力強、運行時間短的優點。缺點是全局搜索能力差，容易受到參數的影響。

爬山演算法：顯然爬山演算法簡單、效率高，但在處理多約束大規模問題時，往往不能得到較好的解決方案。

數值演算法：這個數值演算法的含義太寬泛了，指的是哪種數值演算法，陣列演算法與爬山演算法一樣，各有優缺點。

(1)遺傳演算法的本質擴展閱讀：

注意事項：

遺傳演算法的機制比較復雜，在Matlab中已經用工具箱中的命令進行了打包，通過調用可以非常方便的使用遺傳演算法。

函數GA：［x，Fval，reason］＝GA（＠fitnessfun，Nvars，options）x為最優解，Fval為最優值，＠Fitnessness為目標函數，Nvars為自變數個數，options為其他屬性設置。系統的默認值是最小值，所以函數文檔中應該加上一個減號。

要設置選項，您需要以下函數：options＝GaOptimset（＇PropertyName1＇，＇PropertyValue1＇，＇PropertyName2＇，＇PropertyName3＇，＇PropertyValue3＇…）通過該函數，可以確定一些遺傳演算法的參數。

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

遺傳操作的交叉運算元。

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

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

(2)遺傳演算法的本質擴展閱讀

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

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

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

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

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

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

3. 請問遺傳演算法和進化演算法是什麼關系

對主角的形態進行拆分，用數值表示問題解的最小構成單位即表示基因本身，基因串即表示一個個體。以字元串的形態存儲耳朵顏色，形狀，眼睛顏色形狀，皮膚顏色，花紋以及尾巴顏色，形狀的相關數據，通過多點交叉，然後產生新的子代個體，接下來進行圖像組合，調整每一個部件的相對位置，組合成完整的個體。適應度由玩家交互的次數決定，玩家對自己最喜愛的寵物的關心最多，然後依次遞減，適應度最高的個體有大幾率繁衍下一代且攜帶優秀基因（玩家喜愛度更高），實現進化。

4. 用改進遺傳演算法求取水文地質參數

任廣軍¹ 張勇²

（1.山東省魯南地質工程勘察院，兗州272000；2.山東省地礦工程集團有限公司，濟南250013）

作者簡介：任廣軍（1972—），男，工程師，主要從事水文地質、環境地質等。

摘要：本文利用非穩定流抽水試驗資料，採用改進的十進制遺傳演算法在計算機上自動優選含水層水文地質參數。該方法同傳統上使用的配線法相比較，具有節省時間，減少人工配線誤差，所求參數逼真，且能對一些線性、非線性問題求解，具有很高的推廣和應用價值。

關鍵詞：遺傳演算法；隨機模擬；含水層；水文地質參數；優選

0 引言

利用改進的十進制遺傳演算法，根據抽水試驗資料來認識水文地質條件、反求水文地質參數是水文地質計算中的基本問題。具體地講，在探明含水層范圍、類型的基礎上，建立描述該含水層水流運動模型，利用抽水試驗過程中的地下水位變化過程資料來確定水文地質參數。

雖然非穩定抽水試驗公式適用條件非常苛刻，但能反映出含水層非穩定流的一些基本特點，還可運用疊加原理解決某些比較復雜的非穩定流問題。此外，作為檢驗數值方法精確性的重要依據，具有廣泛應用和發展前景。

目前，由於非穩定流抽水試驗確定水文地質參數的具體實現方法主要有人工配線法或以計算輔助的配線法，但這種方法的效果好壞完全取決於肉眼觀察，帶有很大的主觀性。本文作者選取了一些典型實例，採用遺傳演算法建立了一種計算機全自動求參的全局優選法，通過與人工配線分析比較，確定本方法計算機求參的高精度與高可靠性。

求取參數是通過實測結果與模型計算結果的最佳擬合（模擬）程度來實現的，參數的精確程度在很大程度上取決於實測資料的精度。

1 遺傳演算法介紹

生物的進化是一個奇妙的優化過程，它通過選擇淘汰，突然變異，基因遺傳等規律產生適應環境變化的優良物種。遺傳演算法是根據生物進化思想而啟發得出的一種全局優化演算法。

遺傳演算法的概念最早是由Bagley J.D在1967年提出的；而開始遺傳演算法的理論和方法的系統性研究的是1975年，這一開創性工作是由Michigan大學的J.H.Holland所實行。當時，其主要目的是說明自然和人工系統的自適應過程。

遺傳演算法簡稱GA（Genetic Algorithm），在本質上是一種不依賴具體問題的直接搜索方法。遺傳演算法在模式識別、神經網路、圖像處理、機器學習、工業優化控制、自適應控制、生物科學、社會科學等方面都得到應用。在人工智慧研究中，現在人們認為「遺傳演算法、自適應系統、細胞自動機、混沌理論與人工智慧一樣，都是對今後十年的計算技術有重大影響的關鍵技術」。

2 目標函數的確定

通過綜合考慮計算程序的運算時間、速度以及含水層的類型，確立利用抽水實測資料和計算資料的擬合程度為目標函數。其計算公式為：

山東省環境地質文集

式中：s_實測為實測抽水試驗觀測孔的降深；s_計算為計算抽水試驗觀測孔的降深；NT為計算時段。

3 計算實例及結果分析

3.1 承壓含水層地下水降深公式

承壓含水層地下水降深公式為：

山東省環境地質文集

式中：S為以固定流量Q抽水時與抽水井距離為r處任一時間的水位降深（m）；T為導水系數；Q為涌水量；W（u）為井函數，是一個指數積分函數：

山東省環境地質文集

式中：u為井函數的自變數，

其中s為承壓含水層的儲存系數；T為含水層的導水系數；t為時間。

例1：某地區進行非穩定流抽水試驗。區域地層剖面是：地表下18～25 m是由含礫粗砂層組成的含水層，其底板由粘土質沉積物組成，18 m以上是粘土、泥炭層。抽水井的過濾器安裝在含水層的整個厚度上。觀測孔距抽水井30m，觀測資料如表1所示。主井作定流量抽水，Q＝788m³/d，抽水接近14小時。試根據觀測資料求取水文地質參數。

（1）lgS-lgt配線法所求參數：T_配線＝439m²/d，s_配線＝1.694×10^-4；

（2）S-lgt直線圖解法所求參數：T_配線＝450.7m²/d，s_配線＝1.392×10^-4；

（3）計算機所求參數：T＝383.0088m²/d，s＝ 1.78×10^-4。

為更直觀地說明上述所求參數的可靠性，由上述參數所求計算降深與實測降深進行比較（圖1）。通過比較，進一步確定了計算機求參的高精度與穩定性。承壓含水層配線參數與優選參數比較分析：T_配線＝439m²/d，s_配線＝0.0001694；T_計算＝383.0088m²/d，s_計算＝0.0001780。

表1 遺傳演算法計算水位降深與實測水位降深結果表

圖1 計算降深與實測降深比較圖

3.2 在有越流補給的承壓含水層地下水降深公式

在有越流補給的承壓含水層地下水降深公式為：

山東省環境地質文集

式中：u同（3）式；

為越流井函數，本文中

採用數值積分：

山東省環境地質文集

例2：有一無限分布的承壓含水層，厚度20m，其底部為絕對隔水的粘土層；上部為弱透水的亞砂土層，厚2m；弱透水層之上為潛水含水層。在承壓含水層中有一完整抽水井，抽水時的穩定流量Q＝5530m³/d。距抽水井r＝17.34m處有一觀測孔據觀測知，在抽水過程中上部潛水的水位不變。抽水層的水位降深值載於表2，試計算含水層水文地質參數。

（1）lgS-lgt配線法所求參數：T_配線＝853.50m²/d，s_配線＝4.20×10^-4；B_配線＝568.50m；

（2）lgS-lgt配線法所求參數：T_計算＝817.19m²/d，s_計算＝4.31×10^-4；B_計算＝482.80m。

為更直觀地說明上述所求參數的可靠性，由上述參數所求計算降深與實測降深進行比較（圖2）。通過比較，進一步確定了計算機求參的高精度與穩定性。有越流時承壓含水層優選參數誤差分析：T_配線＝853.50m²/d，s_配線＝0.00042，B_配線＝568.50m；T_計算＝817.1950m²/d，s_計算＝0.00043103，B_計算＝482.798m。

表2 遺傳演算法計算水位降深與實測水位降深結果表

續表

圖2 計算降深與實測降深比較圖

3.3 考慮有滯後補給的潛水含水層地下水降深公式

根據博爾頓理論，潛水含水層地下水降深公式計算公式可分為抽水前期、抽水中期和抽水後期。參數優選主要根據抽水前期和抽水後期的資料擬合而得：

山東省環境地質文集

其中D為疏干因子。

抽水前期計算公式：

抽水後期計算公式：同（2）式。

4 結論及不足之處

4.1 結論

通過上述實例計算結果表明：計算結果同人工加以計算機輔助配線法相比較，其計算水文地質參數精度較高，且其參數初值依賴程度較低，對於復雜的線性、非線性及多態性、多峰值問題在全局優化方面有著其他方法所無法比擬的優勢，具有很高的推廣和應用價值。

4.2 不足之處

遺傳演算法雖然可以在多種領域都有實際應用，並且也展示了它潛力和寬廣前景；但是，遺傳演算法還有大量的問題需要研究，目前也還存在著各種不足。首先，在變數多，取值范圍大或無給定范圍時，收斂速度下降；其次，可找到最優解附近，但無法精確確定最優解位置；最後，遺傳演算法的參數選擇尚未有定量方法。對於遺傳演算法，一是還需要進一步研究其數學基礎理論；二是還需要在理論上證明它與其他優化技術的優劣及原因；三是還需研究硬體化的遺傳演算法；以及遺傳演算法的通用編程和形式等。此外，對於地下水滲流問題的數值解反求多類各種水文地質參數雖有成功實例，對於運算速度問題，還存在著相當大的難度。

參考文獻

陳崇希，唐仲華.1990.地下水流動問題數值方法.武漢：中國地質大學出版社

陳喜.1998.含水層水文地質參數自動優選方法.工程勘察，（2）

郭東屏.1994.地下水動力學.西安：陝西科學技術出版社

GB 50027—2001 供水水文地質勘察規范

李俊亭，王愈吉.1987.地下水動力學.北京：地質出版社

劉寶碇，趙瑞清，王綱.2003.不確定規劃及應用.北京：清華大學出版社

朱國祥，王峰.1999.利用配線法水文地質參數計算機程序簡介.工程勘察，（3）

鄒正盛，趙智榮.2001.淺析抽水水文地質參數確定中的問題.水文地質工程地質，（3）

5. 遺傳演算法可以解決哪些問題

遺傳演算法主要是用來求解最優化問題的。
一般來講可以求解函數的最大、最小值問題，還可以結合其它一些方法解決（非）線性回歸、分類問題等等。

但遺傳演算法有兩個缺點，一是時間長，二是初值的選擇會影響收斂的效果。

它的本質，實際上還是隨機搜索演算法，還是屬於所謂的蒙特卡羅式的方法。

6. 什麼是遺傳演算法實值變數

1.2 遺傳演算法的原理
遺傳演算法GA把問題的解表示成「染色體」，在演算法中也即是以二進制編碼的串。並且，在執行遺傳演算法之前，給出一群「染色體」，也即是假設解。然後，把這些假設解置於問題的「環境」中，並按適者生存的原則，從中選擇出較適應環境的「染色體」進行復制，再通過交叉，變異過程產生更適應環境的新一代「染色體」群。這樣，一代一代地進化，最後就會收斂到最適應環境的一個「染色體」上，它就是問題的最優解。
一、遺傳演算法的目的
典型的遺傳演算法CGA(Canonical Genetic Algorithm)通常用於解決下面這一類的靜態最優化問題：
考慮對於一群長度為L的二進制編碼bi，i＝1，2，…，n；有
bi∈{0,1}L (3-84)
給定目標函數f，有f(bi)，並且
0<f(bi)<∞
同時
f(bi)≠f(bi+1)
求滿足下式
max{f(bi)|bi∈{0,1}L} (3-85)
的bi。
很明顯，遺傳演算法是一種最優化方法，它通過進化和遺傳機理，從給出的原始解群中，不斷進化產生新的解，最後收斂到一個特定的串bi處，即求出最優解。二、遺傳演算法的基本原理
長度為L的n個二進制串bi(i＝1，2，…，n)組成了遺傳演算法的初解群，也稱為初始群體。在每個串中，每個二進制位就是個體染色體的基因。根據進化術語，對群體執行的操作有三種：
1．選擇(Selection)
這是從群體中選擇出較適應環境的個體。這些選中的個體用於繁殖下一代。故有時也稱這一操作為再生(Reproction)。由於在選擇用於繁殖下一代的個體時，是根據個體對環境的適應度而決定其繁殖量的，故而有時也稱為非均勻再生(differential reproction)。
2．交叉(Crossover)
這是在選中用於繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而產生新的個體。
3．變異(Mutation)
這是在選中的個體中，對個體中的某些基因執行異向轉化。在串bi中，如果某位基因為1，產生變異時就是把它變成0；反亦反之。
遺傳演算法的原理可以簡要給出如下：
choose an intial population
determine the fitness of each indivial
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each indivial
perform selection
until some stopping criterion applies
這里所指的某種結束准則一般是指個體的適應度達到給定的閥值；或者個體的適應度的變化率為零。
三、遺傳演算法的步驟和意義
1．初始化
選擇一個群體，即選擇一個串或個體的集合bi，i=1，2，...n。這個初始的群體也就是問題假設解的集合。一般取n＝30-160。
通常以隨機方法產生串或個體的集合bi,i＝1，2，...n。問題的最優解將通過這些初始假設解進化而求出。
2．選擇
根據適者生存原則選擇下一代的個體。在選擇時，以適應度為選擇原則。適應度准則體現了適者生存，不適應者淘汰的自然法則。
給出目標函數f，則f(bi)稱為個體bi的適應度。以

(3-86)為選中bi為下一代個體的次數。
顯然．從式(3—86)可知：
(1)適應度較高的個體，繁殖下一代的數目較多。
(2)適應度較小的個體，繁殖下一代的數目較少；甚至被淘汰。
這樣，就產生了對環境適應能力較強的後代。對於問題求解角度來講，就是選擇出和最優解較接近的中間解。
3．交叉
對於選中用於繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率P。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在於產生新的基因組合，也即產生新的個體。交叉時，可實行單點交叉或多點交叉。
例如有個體
S1=100101
S2=010111
選擇它們的左邊3位進行交叉操作，則有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值為0.25—0.75。
4．變異
根據生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些位執行變異。在變異時，對執行變異的串的對應位求反，即把1變為0，把0變為1。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。
例如有個體S＝101011。
對其的第1，4位置的基因進行變異，則有
S'=001111
單靠變異不能在求解中得到好處。但是，它能保證演算法過程不會產生無法進化的單一群體。因為在所有的個體一樣時，交叉是無法產生新的個體的，這時只能靠變異產生新的個體。也就是說，變異增加了全局優化的特質。
5．全局最優收斂(Convergence to the global optimum)
當最優個體的適應度達到給定的閥值，或者最優個體的適應度和群體適應度不再上升時，則演算法的迭代過程收斂、演算法結束。否則，用經過選擇、交叉、變異所得到的新一代群體取代上一代群體，並返回到第2步即選擇操作處繼續循環執行。
圖3—7中表示了遺傳演算法的執行過程。

圖3-7 遺傳演算法原理
1.3 遺傳演算法的應用
遺傳演算法在很多領域都得到應用；從神經網路研究的角度上考慮，最關心的是遺傳演算法在神經網路的應用。在遺傳演算法應用中，應先明確其特點和關鍵問題，才能對這種演算法深入了解，靈活應用，以及進一步研究開發。
一、遺傳演算法的特點
1．遺傳演算法從問題解的中集開始嫂索，而不是從單個解開始。
這是遺傳演算法與傳統優化演算法的極大區別。傳統優化演算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳演算法從串集開始搜索，復蓋面大，利於全局擇優。
2．遺傳演算法求解時使用特定問題的信息極少，容易形成通用演算法程序。
由於遺傳演算法使用適應值這一信息進行搜索，並不需要問題導數等與問題直接相關的信息。遺傳演算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。
3．遺傳演算法有極強的容錯能力
遺傳演算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，遺傳演算法有很高的容錯能力。
4．遺傳演算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。
這說明遺傳演算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。
5．遺傳演算法具有隱含的並行性
遺傳演算法的基礎理論是圖式定理。它的有關內容如下：
(1)圖式(Schema)概念
一個基因串用符號集{0，1，*}表示，則稱為一個因式；其中*可以是0或1。例如：H=1x x 0 x x是一個圖式。
(2)圖式的階和長度
圖式中0和1的個數稱為圖式的階，並用0(H)表示。圖式中第1位數字和最後位數字間的距離稱為圖式的長度，並用δ(H)表示。對於圖式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
(3)Holland圖式定理
低階，短長度的圖式在群體遺傳過程中將會按指數規律增加。當群體的大小為n時，每代處理的圖式數目為0(n3)。
遺傳演算法這種處理能力稱為隱含並行性(Implicit Parallelism)。它說明遺傳演算法其內在具有並行處理的特質。
二、遺傳演算法的應用關鍵
遺傳演算法在應用中最關鍵的問題有如下3個
1．串的編碼方式
這本質是問題編碼。一般把問題的各種參數用二進制編碼，構成子串；然後把子串拼接構成「染色體」串。串長度及編碼形式對演算法收斂影響極大。
2．適應函數的確定
適應函數(fitness function)也稱對象函數(object function)，這是問題求解品質的測量函數；往往也稱為問題的「環境」。一般可以把問題的模型函數作為對象函數；但有時需要另行構造。
3．遺傳演算法自身參數設定
遺傳演算法自身參數有3個，即群體大小n、交叉概率Pc和變異概率Pm。
群體大小n太小時難以求出最優解，太大則增長收斂時間。一般n＝30-160。交叉概率Pc太小時難以向前搜索，太大則容易破壞高適應值的結構。一般取Pc=0.25-0.75。變異概率Pm太小時難以產生新的基因結構，太大使遺傳演算法成了單純的隨機搜索。一般取Pm＝0．01—0．2。
三、遺傳演算法在神經網路中的應用
遺傳演算法在神經網路中的應用主要反映在3個方面：網路的學習，網路的結構設計，網路的分析。
1．遺傳演算法在網路學習中的應用
在神經網路中，遺傳演算法可用於網路的學習。這時，它在兩個方面起作用
(1)學習規則的優化
用遺傳演算法對神經網路學習規則實現自動優化，從而提高學習速率。
(2)網路權系數的優化
用遺傳演算法的全局優化及隱含並行性的特點提高權系數優化速度。
2．遺傳演算法在網路設計中的應用
用遺傳演算法設計一個優秀的神經網路結構，首先是要解決網路結構的編碼問題；然後才能以選擇、交叉、變異操作得出最優結構。編碼方法主要有下列3種：
(1)直接編碼法
這是把神經網路結構直接用二進制串表示，在遺傳演算法中，「染色體」實質上和神經網路是一種映射關系。通過對「染色體」的優化就實現了對網路的優化。
(2)參數化編碼法
參數化編碼採用的編碼較為抽象，編碼包括網路層數、每層神經元數、各層互連方式等信息。一般對進化後的優化「染色體」進行分析，然後產生網路的結構。
(3)繁衍生長法
這種方法不是在「染色體」中直接編碼神經網路的結構，而是把一些簡單的生長語法規則編碼入「染色體」中；然後，由遺傳演算法對這些生長語法規則不斷進行改變，最後生成適合所解的問題的神經網路。這種方法與自然界生物地生長進化相一致。
3．遺傳演算法在網路分析中的應用
遺傳演算法可用於分析神經網路。神經網路由於有分布存儲等特點，一般難以從其拓撲結構直接理解其功能。遺傳演算法可對神經網路進行功能分析，性質分析，狀態分析。
遺傳演算法雖然可以在多種領域都有實際應用，並且也展示了它潛力和寬廣前景；但是，遺傳演算法還有大量的問題需要研究，目前也還有各種不足。首先，在變數多，取值范圍大或無給定范圍時，收斂速度下降；其次，可找到最優解附近，但無法精確確定最擾解位置；最後，遺傳演算法的參數選擇尚未有定量方法。對遺傳演算法，還需要進一步研究其數學基礎理論；還需要在理論上證明它與其它優化技術的優劣及原因；還需研究硬體化的遺傳演算法；以及遺傳演算法的通用編程和形式等

7. 關於遺傳演算法為什麼可以求解npc類問題

遺傳演算法本質上只是一個優化的比較好的搜索演算法， 每個NPC問題都可以通過暴力搜索的方法求解

其通過模擬生物的方式能夠在某些情況下有效的避免陷於local optimum，而通常能在較短的時間得到比較好的解， 但遺傳演算法並不保證在多項式時間解決NPC問題....

8. 你好，遺傳演算法在網路編碼中可以應用嗎，還有就是遺傳演算法和量子遺傳演算法的本質區別是啥啊求回答啊

遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。
量子遺傳演算法是量子計算與遺傳演算法相結合的產物。
量子遺傳演算法對於遺傳演算法的優點，搜索范圍更廣,適應性更強,效率更高,效果更好。