遺傳演算法介紹

㈠ 遺傳演算法具體應用

1、函數優化

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

2、組合優化

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

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

3、車間調度

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

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

(1)遺傳演算法介紹擴展閱讀：

遺傳演算法的缺點

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

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

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

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

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

㈡ 十進制遺傳演算法簡介

8.2.1 反演優化問題

用遺傳演算法反演水文地質參數^{［38，61］}，首先要構造優化問題。設區域有m個觀測值，則構造誤差函數為：

含水層參數識別方法

其中：為實測值，h_i （p₁，p₂，…，p_n）為計算值。和h_i 具有相同的時間和坐標點，p₁，p₂，…，p_n 為參數，為書寫方便記 P=[p₁，p₂，…，p_n]。

模型選定之後，通過改變參數使誤差函數達到最小值。那麼本問題就轉化為約束條件下的優化問題（8-2）。

含水層參數識別方法

8.2.2 遺傳演算法步驟

可用遺傳演算法求解優化問題（8-2），具體步驟如下。

1）解的表示結構。用十進制浮點向量，表示優化問題的解。每個染色體由一個浮點向量表示，其長度和解向量相同。這里用（p₁，p₂，…，p_n）表示最優化問題（8-2）的解。相應的染色體為V=（p₁，p₂，…，p_n）。

2）初始化過程。定義整數Pop-Size作為染色體的個數，並且隨機產生Pop-Size個初始染色體。從優化問題的約束條件可以看出，（p₁，p₂，…，p_n）的可行域是一個長方形，我們用隨機的方法可以得到Pop-Size個初始可行的染色體。

檢驗（p₁，p₂，…，p_n）是否為可行染色體，如果是，就保留。如果不是就再產生一組可行染色體。直到產生Pop-Size個初始可行的染色體V₁，V₂，…，V_Pop-Size。

3）評價函數。評價函數（用eval（V）表示）用來對種群中的每個染色體V設定一個概率，以使該染色體被選擇的可能性與其種群中其他染色體的適應性成比例。通過輪盤賭，適應性強的染色體被選擇產生後代的機會大。在實際應用中我們採取如下方法確定評價函數。

設目前該代中的染色體為V₁，V₂，…，V_Pop-Size，可以根據染色體的序進行再分配，無論採用何種數學規劃均可以將染色體由好到壞進行重排，就是說，一個染色體越好，其序號越小。設參數α∈（0，1）給定，定義於序的評價函數為：

含水層參數識別方法

i=1意味著染色體是最好的，i=Pop-Size說明是最差的。

4）選擇過程。選擇過程是以旋轉賭輪Pop-Size次為基礎的。每次旋轉都為新的種群選擇一個染色體。賭輪是按每個染色體的適應度進行選擇染色體的。其過程如下。

A.對每個染色體V_i，計算累積概率q_i

含水層參數識別方法

B.從區間（0，q_Pop-Size）中產生一個隨機數r。

C.若q_i-1＜r≤q_i，則選擇第i個染色體V_i（1≤i≤Pop-Size）。

D.重復步驟②和步驟③共Pop-Size次，這樣可以得到Pop-Size個復制的染色體。上述過程並沒有要求滿足條件q_Pop-Size=1。實際上，可以用q_Pop-Size除以所有的q_i，使q_Pop-Size=1，新得到的概率同樣與適應度成比例。

5）交叉操作。設P_c為交叉操作的概率，這個概率說明種群中有期望值為P_c·Pop

-Size個染色體進行交叉操作。為確定交叉操作的父代，從i=1到Pop-Size重復以下過程：從［0，1］中產生隨機數r，如果r＜P_c，則選擇V_i作為一個父代。

用V′₁，V′₂，V′₃，…表示上面選擇的父代，並把他們隨機分為交叉對。

（V′₁，V′₂），（V′₃，V′₄），（V′₅，V′₆），…

現僅以第一對為例說明交叉操作的過程，從（0，1）區間產生一個隨機數c，然後按下式進行交叉操作，並產生兩個後代X和Y

X=cV′₁+（1-c）V′₂，Y=（1-c）V′₁+cV′₂

檢驗新產生的後代是否為可行解，如果可行，用它們代替父代；否則，保留其中可行的。然後，產生新的隨機數c，重新進行交叉操作，直到得到兩個可行的後代為止。

6）變異操作。設參數P_m為遺傳操作中的變異概率，為確定變異操作的父代，從i=1到Pop-Size重復以下過程：從［0，1］中產生隨機數r，如果r＜P_m，則選擇V_i作為一個變異父代。先選擇一個變異方向D，M為一個隨機數，則可以用下式：

X=V+M·D

為新後代，檢驗X是否為可行解。如不可行，改變隨機數M或變異方向D直到X為可行解為止。

另一種產生變異的操作是在可行域中另外產生一個染色體，或染色體中的一個元素。

7）遺傳演算法的一般過程。遺傳演算法的一般過程可歸納如下：

輸入參數Pop-Size，P_c，P_m；

通過初始化過程產生Pop-Size個染色體；

重復

根據某抽樣機制選擇染色體；

對染色體進行交叉和變異操作；

計算所有染色體的評價函數；

滿足終止條件時終止，否則重復以上三個過程。

㈢ 基本的遺傳演算法

在許多實際應用領域，無論是工程技術科學還是社會經濟科學中，都會遇到全局最優化問題^{[53，56～59，61]}，這一類問題大多數可以形式化為一個對（S，f）的尋優問題，其中 S⊂R ⁿ 是 R ⁿ 中的有界集，f∶S→R是 n 維實值函數。所要求解的問題就是要找到一點 x _best∈S，使得 f（x_best）是 S 上的全局最優解，可以是極大值或極小值。以極小值為例，即求一點 x _min∈S，滿足

含水層參數識別方法

盡管人們對這類問題進行了大量的研究，但得到的成績仍不能令人滿意，目前只能解決一些簡單的問題。對於更復雜的全局最優化問題，通常是利用數值解法，但許多數值解法都不能找到最優解，只是返回一個接近於全局最優的值。

全局最優化數值方法可以分為兩大類：確定性演算法和隨機演算法。在隨機演算法中，最優化步驟在一定程度上依賴於概率事件，它排除了確定性演算法中的一個最大障礙——預先詳細說明一個問題的全部特徵並針對問題的特徵決定演算法應採用的對策。與常規的優化演算法相比，遺傳演算法有可能在更大的范圍內探尋問題潛在的解。確定性演算法沒有用到概率信息。只有當對S上進行窮舉搜索及對f規定附加的假設條件下，演算法才能找到全局最優解。實行窮舉搜索在很多情況下（如實數解）是不可能的，因此多採用對f規定附加的假設條件，這必然影響到最終解的可靠性。在這些演算法中，搜索速度越快的演算法往往意味著需要對f做更多的假設，或者不能保證搜索成功。與此相對照，許多隨機演算法都可以證明在概率意義下漸近收斂到全局最優解，即這些演算法保證以概率1漸近收斂，而且隨機演算法的計算結果一般要優於那些確定性演算法的結果。遺傳演算法就是其中具有代表性的隨機演算法。

常用的遺傳演算法操作有選擇（Selection）、交叉（Crossover）、變異（Mutation）。復制是直接將個體的代碼進行拷貝形成新個體。下面就選擇、交叉與變異操作做一介紹。

7.3.1 選擇過程

選擇過程是以旋轉賭輪Pop-Size次（種群規模，即群體中個體的總個數）為基礎，每次旋轉都為新的種群選擇一個染色體。首先計算出個體i被選擇的概率P_i，優秀的染色體其選擇概率大，然後根據選擇概率的大小將一個圓盤分為Pop-Size個扇形，每個扇形的中心角的大小為2πP_i。

每次進行選擇時，先選擇賭輪邊界旁一個不動的參考點，賭輪隨機地轉動，若不動點停留在扇形j內，則選擇個體j。個體的適應值越大，被選擇的概率越大，從而其染色體被遺傳到下一代的概率越大。

賭輪式選擇的特點是對於種群內的所有個體，無論其適應值大小，都有被選擇的機會。適應值大的個體被選擇的概率大，適應值小的個體被選擇的概率小。經過選擇後適應值大的個體在種群中的數目會增加。這正體現了適者生存的原則。

7.3.2 交叉操作

交叉操作是個有組織的、隨機的字元串間的信息交換過程。假設群體G（t）是模式庫。歷史信息以每個模式實例數目的形式存儲於G（t）中。交叉作用產生模式庫中已有模式的新的實例，同時也產生新的模式。簡單的交叉操作分為三步：

（1）從當前群體G（t）中選擇兩個個體結構：A=a₁a₂…a_n，B=b₁b₂…b_n；

（2）以交叉概率 P_c 隨機選擇一個整數 x∈{1，2，…，n}；

（3）交換A和B中位置x右邊的元素，產生兩個新的個體結構：a₁a₂…a_xb_x+1…b_n和b₁b₂…b_xa_x+1…a_n。

7.3.3 變異操作

對於群體G（t）中的每個個體A=a₁a₂…a_n，簡單的變異操作過程如下：

1）每個位置的字元變數都有一個變異概率P_m，各位置互相獨立，通過隨機過程選擇發生變異的位置x₁，x₂，…，x_n。

2）產生一個新個體結構 B=a₁ a₂……a_n ，其中是從對應位置x ₁ 的字元變數的值域中隨機選擇的一個取值。類似地，，…，可以同樣得到。

如果每個位置的變異概率等於P_m，那麼模式H（階為o（H））發生一次或多次變異的概率是

含水層參數識別方法

遺傳操作除了有選擇、交叉、變異等運算元外，還有染色體內部復制（Intrachromo-somal plication）、刪除、易位（Translocation）、分異（Segregation）等。

㈣ 如何通俗易懂地解釋遺傳演算法

遺傳演算法，核心是達爾文優勝劣汰適者生存的進化理論的思想。

我們都知道一個種群，通過長時間的繁衍，種群的基因會向著更適應環境的趨勢進化，牛B個體的基因被保留，後代越來越多，適應能力低個體的基因被淘汰，後代越來越少。經過幾代的繁衍進化，留下來的少數個體，就是相對能力最強的個體了。

那麼在解決一些問題的時候，我們能不能學習這樣的思想，比如先隨機創造很多很多的解，然後找一個靠譜的評價體系，去篩選比較好的解，再用這些好的解像生小寶寶一樣生一堆可能更好的解，然後再篩再生，反復弄個幾代，得到的說不定就是近似最優解喲

說干就干，有一個經典組合問題叫「背包問題」，我們拿這種思路來試試

「背包問題（Knapsack Problem）是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。」

這個問題的衍生簡化問題「0-1背包問題」 增加了限制條件：每件物品只有一件，可以選擇放或者不放，更適合我們來舉例

這樣的問題如果數量少，當然最好選擇窮舉法

比如一共3件商品，用0表示不取，1表示取，那麼就一共有

000 001 010

011 100 101

110 111

這樣方案，然後讓計算機去累加和，與重量上限比較，留下來的解里取最大即可。

㈤ 遺傳演算法及其應用的內容簡介

本書系統全面地介紹了遺傳演算法的基本原理、設計方法及其並行實現，以及它在組合優化、機器學習、圖像處理、過程式控制制、進化神經網路、模糊模式識別和人工生命等方面的應用。
本書可作為高等院校計算機、無線電電子學、自動控制、生物醫學工程等有關專業高年級學生或研究生的教材和參考書，也可供從事人工智慧、信息處理研究和應用的科技人員學習參考。

㈥ 遺傳演算法有哪些應用

遺傳演算法的搜索策略和優化搜索方法是不依附於梯度信息及其它的輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳演算法提供了一種求解復雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用於許多科學。遺傳演算法的應用領域有很多，下面針對一些主要的應用領域做簡單的介紹。

1．函數優化：該領域是遺傳演算法得以應用的經典領域，同時它也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對於函數優化問題，如一些非線性、多模型、多目標等函數問題用遺傳演算法很容易得到較好的結果，而用其他演算法則較難。

2．組合優化：由於組合優化問題的搜索空間在不斷地增大，有時用枚舉法很難得到最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳演算法對於組合優化中的NP問題非常有效。比如，在旅行商問題、裝箱問題及圖形劃分等問題上，已經成功得以應用了遺傳演算法。

㈦ 遺傳演算法

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

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

㈧ 高分尋達人分別介紹下遺傳演算法和演化演算法，以及之間的聯系和區別

根據閱讀的資料，大概有以下判斷：
遺傳演算法是演化演算法中的一種。

遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳演算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。

遺傳演算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它的思想源於生物遺傳學和適者生存的自然規律，是具有「生存＋檢測」的迭代過程的搜索演算法。遺傳演算法以一種群體中的所有個體為對象，並利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。其中，選擇、交叉和變異構成了遺傳演算法的遺傳操作；參數編碼、初始群體的設定、適應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳演算法的核心內容。 作為一種新的全局優化搜索演算法，遺傳演算法以其簡單通用、魯棒性強、適於並行處理以及高效、實用等顯著特點，在各個領域得到了廣泛應用，取得了良好效果，並逐漸成為重要的智能演算法之一。

遺傳演算法是基於生物學的，理解或編程都不太難。下面是遺傳演算法的一般演算法：
創建一個隨機的初始狀態

初始種群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智慧系統的情況不一樣，在那裡問題的初始狀態已經給定了。

評估適應度

對每一個解(染色體)指定一個適應度的值，根據問題求解的實際接近程度來指定(以便逼近求解問題的答案)。不要把這些「解」與問題的「答案」混為一談，可以把它理解成為要得到答案，系統可能需要利用的那些特性。

繁殖(包括子代突變)

帶有較高適應度值的那些染色體更可能產生後代(後代產生後也將發生突變)。後代是父母的產物，他們由來自父母的基因結合而成，這個過程被稱為「雜交」。

下一代

如果新的一代包含一個解，能產生一個充分接近或等於期望答案的輸出，那麼問題就已經解決了。如果情況並非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。

並行計算

非常容易將遺傳演算法用到並行計算和群集環境中。一種方法是直接把每個節點當成一個並行的種群看待。然後有機體根據不同的繁殖方法從一個節點遷移到另一個節點。另一種方法是「農場主/勞工」體系結構，指定一個節點為「農場主」節點，負責選擇有機體和分派適應度的值，另外的節點作為「勞工」節點，負責重新組合、變異和適應度函數的評估。
http://ke..com/view/45853.html

演化演算法：
這部分的研究主要是提供具有演化特徵的演算法，已知的遺傳演算法是其中之一。許多新的演算法正在研究中。由於遺傳演算法的整體搜索策略和優化計算時不依賴於梯度信息，所以它的應用非常廣泛，尤其適合於處理傳統搜索方法難以解決的高度復雜的非線性問題。人工生命研究的重要內容就是進化現象，遺傳演算法是研究進化現象的重要方法之一
我國學者接觸這個領域較晚，目前尚未形成聲勢和有規模的研究隊伍。1997年夏天，在中科院基礎局、國家科委基礎司及中國國際經濟及技術交流中心的支持下，由中科院系統科學所和自動化研究所舉辦了第一次人工生命及進化機器人研討會[20]。與會者約60人。除去邀請了五位國際知名學者的學術報告之外，國內也有數名學者介紹了相關的研究成果。主要在數字生命、復雜巨系統方面進行了一些研究。據目前了解到的情況，國內尚有一些人在研究演化演算法，在人工智慧的一本書上有一段介紹人工生命。但對人工社會、人工生態環境及進化機器人等尚無人問津。
http://blog.ustc.e.cn/chujx/archives/000925.html

㈨ 請問什麼是遺傳演算法，並給兩個例子

遺傳演算法(Genetic Algorithm, GA)是近幾年發展起來的一種嶄新的全局優化演算法，它借
用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制，實現各個個體的適應性
的提高。這一點體現了自然界中"物競天擇、適者生存"進化過程。1962年Holland教授首次
提出了GA演算法的思想，從而吸引了大批的研究者，迅速推廣到優化、搜索、機器學習等方
面，並奠定了堅實的理論基礎。 用遺傳演算法解決問題時，首先要對待解決問題的模型結構
和參數進行編碼，一般用字元串表示，這個過程就將問題符號化、離散化了。也有在連續
空間定義的GA(Genetic Algorithm in Continuous Space, GACS)，暫不討論。

一個串列運算的遺傳演算法(Seguential Genetic Algoritm, SGA)按如下過程進行：

(1) 對待解決問題進行編碼；
(2) 隨機初始化群體X(0):=(x1, x2, … xn)；
(3) 對當前群體X(t)中每個個體xi計算其適應度F(xi)，適應度表示了該個體的性能好
壞；
(4) 應用選擇運算元產生中間代Xr(t)；
(5) 對Xr(t)應用其它的運算元，產生新一代群體X(t+1)，這些運算元的目的在於擴展有限
個體的覆蓋面，體現全局搜索的思想；
(6) t:=t+1；如果不滿足終止條件繼續(3)。
GA中最常用的運算元有如下幾種：
(1) 選擇運算元(selection/reproction): 選擇運算元從群體中按某一概率成對選擇個
體，某個體xi被選擇的概率Pi與其適應度值成正比。最通常的實現方法是輪盤賭(roulett
e wheel)模型。
(2) 交叉運算元(Crossover): 交叉運算元將被選中的兩個個體的基因鏈按概率pc進行交叉
，生成兩個新的個體，交叉位置是隨機的。其中Pc是一個系統參數。
(3) 變異運算元(Mutation): 變異運算元將新個體的基因鏈的各位按概率pm進行變異，對
二值基因鏈(0,1編碼)來說即是取反。
上述各種運算元的實現是多種多樣的，而且許多新的運算元正在不斷地提出，以改進GA的
某些性能。系統參數(個體數n,基因鏈長度l,交叉概率Pc,變異概率Pm等)對演算法的收斂速度
及結果有很大的影響，應視具體問題選取不同的值。
GA的程序設計應考慮到通用性，而且要有較強的適應新的運算元的能力。OOP中的類的繼
承為我們提供了這一可能。
定義兩個基本結構：基因(ALLELE)和個體(INDIVIDUAL)，以個體的集合作為群體類TP
opulation的數據成員，而TSGA類則由群體派生出來，定義GA的基本操作。對任一個應用實
例，可以在TSGA類上派生，並定義新的操作。

TPopulation類包含兩個重要過程：
FillFitness: 評價函數，對每個個體進行解碼(decode)並計算出其適應度值，具體操
作在用戶類中實現。
Statistic: 對當前群體進行統計，如求總適應度sumfitness、平均適應度average、最好
個體fmax、最壞個體fmin等。

TSGA類在TPopulation類的基礎上派生，以GA的系統參數為構造函數的參數，它有4個
重要的成員函數：
Select: 選擇運算元，基本的選擇策略採用輪盤賭模型（如圖2）。輪盤經任意旋轉停止
後指針所指向區域被選中，所以fi值大的被選中的概率就大。
Crossover: 交叉運算元，以概率Pc在兩基因鏈上的隨機位置交換子串。
Mutation: 變異運算元，以概率Pm對基因鏈上每一個基因進行隨機干擾(取反)。
Generate: 產生下代，包括了評價、統計、選擇、交叉、變異等全部過程，每運行一
次，產生新的一代。

SGA的結構及類定義如下(用C++編寫)：
[code] typedef char ALLELE; // 基因類型
typedef struct{
ALLELE *chrom;
float fitness; // fitness of Chromosome
}INDIVIDUAL; // 個體定義

class TPopulation{ // 群體類定義
public:
int size; // Size of population: n
int lchrom; // Length of chromosome: l
float sumfitness, average;

INDIVIDUAL *fmin, *fmax;
INDIVIDUAL *pop;

TPopulation(int popsize, int strlength);
~TPopulation();
inline INDIVIDUAL &Indivial(int i){ return pop[i];};
void FillFitness(); // 評價函數
virtual void Statistics(); // 統計函數
};

class TSGA : public TPopulation{ // TSGA類派生於群體類
public:
float pcross; // Probability of Crossover
float pmutation; // Probability of Mutation
int gen; // Counter of generation

TSGA(int size, int strlength, float pm=0.03, float pc=0.6):
TPopulation(size, strlength)
{gen=0; pcross=pc; pmutation=pm; } ;
virtual INDIVIDUAL& Select();
virtual void Crossover(INDIVIDUAL &parent1, INDIVIDUAL &parent2,
INDIVIDUAL &child1, INDIVIDUAL &child2);
&child1, INDIVIDUAL &child2);
virtual ALLELE Mutation(ALLELE alleleval);
virtual void Generate(); // 產生新的一代
};
用戶GA類定義如下：
class TSGAfit : public TSGA{
public:
TSGAfit(int size,float pm=0.0333,float pc=0.6)
:TSGA(size,24,pm,pc){};
void print();
}; [/code]

由於GA是一個概率過程，所以每次迭代的情況是不一樣的；系統參數不同，迭代情況
也不同。在實驗中參數一般選取如下：個體數n=50-200，變異概率Pm=0.03, 交叉概率Pc=
0.6。變異概率太大，會導致不穩定。

參考文獻
● Goldberg D E. Genetic Algorithm in Search, Optimization, and machine

Learning. Addison-Wesley, Reading, MA, 1989
● 陳根社、陳新海，"遺傳演算法的研究與進展"，《信息與控制》，Vol.23,
NO.4, 1994, PP215-222
● Vittorio Maniezzo, "Genetic Evolution of the Topology and Weight Distri
bution of the Neural Networks", IEEE, Trans. on Neural Networks, Vol.5, NO
.1, 1994, PP39-53
● Xiaofeng Qi, Francesco Palmieri, "Theoretical Analysis of Evolutionary
Algorithms with an Infinite Population Size in Continuous Space. Part Ⅰ
l Networks, Vol.5, NO.1, 1994, PP102-119
● Xiaofeng Qi, Francesco Palmieri, "Theoretical Analysis of Evolutionary
Algorithms with an Infinite Population Size in Continuous Space. Part Ⅱ
al Networks, Vol.5, NO.1, 1994, PP102-119
● Gunter Rudolph, Convergence Analysis of Canonical Genetic Algorithms, I
EEE, Trans. on Neural Networks, Vol.5, NO.1, 1994, PP96-101
● A E Eiben, E H L Aarts, K M Van Hee. Gloable convergence of genetic alg
orithms: A Markov chain analysis. in Parallel Problem Solving from Nat
ure. H.-P.Schwefel, R.Manner, Eds. Berlin and Heidelberg: Springer, 1991
, PP4-12
● Wirt Atmar, "Notes on the Simulation of Evolution", IEEE, Trans. on Neu
ral Networks, Vol.5, NO.1, 1994, PP130-147
● Anthony V. Sebald, Jennifer Schlenzig, "Minimax Design of Neural Net Co
ntrollers for Highly Uncertain Plants", IEEE, Trans. on Neural Networks, V
ol.5, NO.1, 1994, PP73-81
● 方建安、邵世煌，"採用遺傳演算法自學習模型控制規則"，《自動化理論、技術與應
用》，中國自動化學會 第九屆青年學術年會論文集，1993, PP233-238
● 方建安、邵世煌，"採用遺傳演算法學習的神經網路控制器"，《控制與決策》，199
3,8(3), PP208-212
● 蘇素珍、土屋喜一，"使用遺傳演算法的迷宮學習"，《機器人》，Vol.16,NO.5,199
4, PP286-289
● M.Srinivas, L.M.Patnaik, "Adaptive Probabilities of Crossover and Mutat
ion", IEEE Trans. on S.M.C, Vol.24, NO.4, 1994 of Crossover and Mutation",
IEEE Trans. on S.M.C, Vol.24, NO.4, 1994
● Daihee Park, Abraham Kandel, Gideon Langholz, "Genetic-Based New Fuzzy
Reasoning Models with Application to Fuzzy Control", IEEE Trans. S. M. C,
Vol.24, NO.1, PP39-47, 1994
● Alen Varsek, Tanja Urbancic, Bodgan Filipic, "Genetic Algorithms in Con
troller Design and Tuning", IEEE Trans. S. M. C, Vol.23, NO.5, PP1330-13
39, 1993

㈩ 能通俗的介紹一下什麼是遺傳演算法嗎

遺傳演算法(Genetic Algorithms or GAs)是基於自然選擇和自然遺傳機制的搜索演算法，它是一種有效的解決最優化問題的方法。遺傳演算法最早是由美國Michigan大學的John Holland和他的同事及學生提出的。類似於自然界演化的基本法則，「適者生存」是遺傳演算法的核心機制，同樣，「復制（reproce）」、「雜交(crossover)」、「變異(mutation)」等自然界的生物演化規則在遺傳演算法中都得到類似的體現。

用遺傳演算法解最優化問題，首先應對可行域中的個體進行編碼，然後在可行域中隨機挑選指定群體大小的一些個體組成作為進化起點的第一代群體，並計算每個個體的目標函數值，即該個體的適應度。接著就像自然界中一樣，利用選擇機制從群體中隨機挑選個體作為繁殖過程前的個體樣本。選擇機制保證適應度較高的個體能夠保留較多的樣本；而適應度較低的個體則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳演算法提供了交叉和變異兩種演算法對挑選後的樣本進行交換和基因突變。交叉演算法交換隨機挑選的兩個個體的某些位，變異運算元則直接對一個個體中的隨機挑選的某一位進行突變。這樣通過選擇和繁殖就產生了下一代群體。重復上述選擇和繁殖過程，直到結束條件得到滿足為止。進化過程最後一代中的最優解就是用遺傳演算法解最優化問題所得到的最終結果。

與其他演算法相比，遺傳演算法主要有以下四個方面的不同： 遺傳演算法所面向的對象是參數集的編碼,而不是參數集本身； 遺傳演算法的搜索是基於若干個點，而不是基於一個點； 遺傳演算法利用目標函數的信息，而不是導數或者其他輔助信息； 遺傳演算法的轉化規則是概率性的，而不是確定性的。