計算機遺傳演算法

『壹』 遺傳演算法的現狀

進入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問題，探討了使用彈性策略來維持群體的多樣性，使得演算法跨過局部收斂的障礙，向全局最優解方向進化。

『貳』 遺傳演算法的迭代次數是怎麼確定的，與什麼有關

1. 遺傳演算法簡介

遺傳演算法是用於解決最優化問題的一種搜索演算法，演算法的整體思路是建立在達爾文生物進化論「優勝劣汰」規律的基礎上。它將生物學中的基因編碼、染色體交叉、基因變異以及自然選擇等概念引入最優化問題的求解過程中，通過不斷的「種群進化」，最終得到問題的最優解。

2. 遺傳演算法實現步驟

在講下面幾個基於生物學提出的概念之前，首先我們需要理解為什麼需要在最優化問題的求解中引入生物學中的各種概念。

假設我們需要求一個函數的最大值，但這個函數異常復雜以至於無法套用一般化的公式，那麼就會想到：如果可以將所有可能的解代入方程，那麼函數最大值所對應的那個解就是問題的最優解。但是，對於較復雜的函數來說，其可能的解的個數的數量級是我們所無法想像的。因此，我們只好退而求其次，只代入部分解並在其中找到最優解。那麼這樣做的核心就在於如何設定演算法確定部分解並去逼近函數的最優解或者較好的局部最優解。

遺傳演算法就是為了解決上述問題而誕生的。假設函數值所對應的所有解是一個容量超級大的種群，而種群中的個體就是一個個解，接下去遺傳演算法的工作就是讓這個種群中的部分個體去不斷繁衍，在繁衍的過程中一方面會發生染色體交叉而產生新的個體。另一方面，基因變異也會有概率會發生並產生新的個體。接下去，只需要通過自然選擇的方式，淘汰質量差的個體，保留質量好的個體，並且讓這個繁衍的過程持續下去，那麼最後就有可能進化出最優或者較優的個體。這么看來原來最優化問題居然和遺傳變異是相通的，而且大自然早已掌握了這樣的機制，這著實令人興奮。為了將這種機制引入最優化問題並利用計算機求解，我們需要將上述提到的生物學概念轉化為計算機能夠理解的演算法機制。

下面介紹在計算機中這種遺傳變異的機制是如何實現的：

基因編碼與解碼：

在生物學中，交叉與變異能夠實現是得益於染色體上的基因，可以想像每個個體都是一串超級長的基因編碼，當兩個個體發生交叉時，兩條基因編碼就會發生交換，產生的新基因同時包含父親和母親的基因編碼。在交叉過程中或者完成後，某些基因點位又會因為各種因素發生突變，由此產生新的基因編碼。當然，發生交叉和變異之後的個體並不一定優於原個體，但這給了進化（產生更加優秀的個體）發生的可能。

因此，為了在計算機里實現交叉和變異，就需要對十進制的解進行編碼。對於計算機來說其最底層的語言是由二進制0、1構成的，而0、1就能夠被用來表示每個基因點位，大量的0、1就能夠表示一串基因編碼，因此我們可以用二進制對十進制數進行編碼，即將十進制的數映射到二進制上。但是我們並不關心如何將十進制轉換為二進制的數，因為計算機可以隨機生成大量的二進制串，我們只需要將辦法將二進制轉化為十進制就可以了。

二進制轉換為十進制實現方式：

假設，我們需要將二進制映射到以下范圍：

首先，將二進制串展開並通過計算式轉化為[0,1]范圍內的數字：

將[0,1]范圍內的數字映射到我們所需要的區間內：

交叉與變異：

在能夠用二進制串表示十進制數的基礎上，我們需要將交叉與變異引入演算法中。假設我們已經獲得兩條二進制串（基因編碼），一條作為父親，一條作為母親，那麼交叉指的就是用父方一半的二進制編碼與母方一半的二進制編碼組合成為一條新的二進制串（即新的基因）。變異則指的是在交叉完成產生子代的過程中，二進制串上某個數字發生了變異，由此產生新的二進制串。當然，交叉與變異並不是必然發生的，其需要滿足一定的概率條件。一般來說，交叉發生的概率較大，變異發生的概率較小。交叉是為了讓演算法朝著收斂的方向發展，而變異則是為了讓演算法有幾率跳出某種局部最優解。

自然選擇：

在成功將基因編碼和解碼以及交叉與變異引入演算法後，我們已經實現了讓演算法自動產生部分解並優化的機制。接下去，我們需要解決如何在演算法中實現自然選擇並將優秀的個體保留下來進而進化出更優秀的個體。

首先我們需要確定個體是否優秀，考慮先將其二進制串轉化為十進制數並代入最初定義的目標函數中，將函數值定義為適應度。在這里，假設我們要求的是最大值，則定義函數值越大，則其適應度越大。那是否在每一輪迭代過程中只需要按照適應度對個體進行排序並選出更加優秀的個體就可以了呢？事實上，自然選擇的過程中存在一個現象，並沒有說優秀的個體一定會被保留，而差勁的個體就一定被會被淘汰。自然選擇是一個概率事件，越適應環境則生存下去的概率越高，反之越低。為了遵循這樣的思想，我們可以根據之前定義的適應度的大小給定每個個體一定的生存概率，其適應度越高，則在篩選時被保留下來的概率也越高，反之越低。

那麼問題就來了，如何定義這種生存概率，一般來說，我們可以將個體適應度與全部個體適應度之和的比率作為生存概率。但我們在定義適應度時使用函數值進行定義的，但函數值是有可能為負的，但概率不能為負。因此，我們需要對函數值進行正數化處理，其處理方式如下：

定義適應度函數：

定義生存概率函數：

註：最後一項之所以加上0.0001是因為不能讓某個個體的生存概率變為0，這不符合自然選擇中包含的概率思想。

3. 遺傳算例

在這里以一個比較簡單的函數為例，可以直接判斷出函數的最小值為0，最優解為(0，0)

若利用遺傳演算法進行求解,設定交叉概率為0.8，變異概率為0.005，種群內個體數為2000，十進制數基因編碼長度為24，迭代次數為500次。

從遺傳演算法收斂的動態圖中可以發現，遺傳演算法現實生成了大量的解，並對這些解進行試錯，最終收斂到最大值，可以發現遺傳演算法的結果大致上與最優解無異，結果圖如下：

4. 遺傳演算法優缺點

優點：

1、 通過變異機制避免演算法陷入局部最優，搜索能力強

2、 引入自然選擇中的概率思想，個體的選擇具有隨機性

3、 可拓展性強，易於與其他演算法進行結合使用

缺點：

1、 遺傳演算法編程較為復雜，涉及到基因編碼與解碼

2、 演算法內包含的交叉率、變異率等參數的設定需要依靠經驗確定

3、 對於初始種群的優劣依賴性較強

『叄』 遺傳演算法^[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)，遺傳演算法的性能較優。

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

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

『肆』 遺傳演算法研究進展

遺傳演算法^{［56，53］}研究的興起是在20世紀80年代末和90年代初期，但它的歷史起源可追溯到20世紀60年代初期。早期的研究大多以對自然遺傳系統的計算機模擬為主。早期遺傳演算法的研究特點是側重於對一些復雜的操作的研究。雖然其中像自動博弈、生物系統模擬、模式識別和函數優化等給人以深刻的印象，但總的來說這是一個無明確目標的發展時期，缺乏帶有指導性的理論和計算工具的開拓。這種現象直到20世紀70年代中期由於Holland和De Jong的創造性研究成果的發表才得到改觀。當然，早期的研究成果對於遺傳演算法的發展仍然有一定的影響，尤其是其中一些有代表性的技術和方法已為當前的遺傳演算法所吸收和發展。

在遺傳演算法作為搜索方法用於人工智慧系統中之前，已有不少生物學家用計算機來模擬自然遺傳系統。尤其是Fraser的模擬研究，他於1962年提出了和現在的遺傳演算法十分相似的概念和思想。但是，Fraser和其他一些學者並未認識到自然遺傳演算法可以轉化為人工遺傳演算法。Holland教授及其學生不久就認識到這一轉化的重要性，Holland認為比起尋找這種或那種具體的求解問題的方法來說，開拓一種能模擬自然選擇遺傳機制的帶有一般性的理論和方法更有意義。在這一時期，Holland不但發現了基於適應度的人工遺傳選擇的基本作用，而且還對群體操作等進行了認真的研究。1965年，他首次提出了人工遺傳操作的重要性，並把這些應用於自然系統和人工系統中。

1967年，Bagley在他的論文中首次提出了遺傳演算法（genetic algorithm）這一術語，並討論了遺傳演算法在自動博弈中的應用。他所提出的包括選擇、交叉和變異的操作已與目前遺傳演算法中的相應操作十分接近。尤其是他對選擇操作做了十分有意義的研究。他認識到，在遺傳進化過程的前期和後期，選擇概率應合適地變動。為此，他引入了適應度定標（scaling）概念，這是目前遺傳演算法中常用的技術。同時，他也首次提出了遺傳演算法自我調整概念，即把交叉和變異的概率融於染色體本身的編碼中，從而可實現演算法自我調整優化。盡管Bagley沒有對此進行計算機模擬實驗，但這些思想對於後來遺傳演算法的發展所起的作用是十分明顯的。

在同一時期，Rosenberg也對遺傳演算法進行了研究，他的研究依然是以模擬生物進化為主，但他在遺傳操作方面提出了不少獨特的設想。1970年Cavicchio把遺傳演算法應用於模式識別中。實際上他並未直接涉及到模式識別，而僅用遺傳演算法設計一組用於識別的檢測器。Cavicchio對於遺傳操作以及遺傳演算法的自我調整也做了不少有特色的研究。

Weinberg於1971年發表了題為《活細胞的計算機模擬》的論文。由於他和Rosenberg一樣注意於生物遺傳的模擬，所以他對遺傳演算法的貢獻有時被忽略。實際上，他提出的多層次或多級遺傳演算法至今仍給人以深刻的印象。

第一個把遺傳演算法用於函數優化的是Hollstien。1971年他在論文《計算機控制系統中的人工遺傳自適應方法》中闡述了遺傳演算法用於數字反饋控制的方法。實際上，他主要是討論了對於二變數函數的優化問題。其中，對於優勢基因控制、交叉和變異以及各種編碼技術進行了深入的研究。

1975年在遺傳演算法研究的歷史上是十分重要的一年。這一年，Holland出版了他的著名專著《自然系統和人工系統的適配》。該書系統地闡述了遺傳演算法的基本理論和方法，並提出了對遺傳演算法的理論研究和發展極為重要的模式理論（schemata theory）。該理論首次確認了結構重組遺傳操作對於獲得隱並行性的重要性。直到這時才知道遺傳操作到底在干什麼，為什麼又幹得那麼出色，這對於以後陸續開發出來的遺傳操作具有不可估量的指導作用。

同年，De Jong完成了他的重要論文《遺傳自適應系統的行為分析》。他在該論文中所做的研究工作可看作是遺傳演算法發展進程中的一個里程碑，這是因為他把Holland的模式理論與他的計算實驗結合起來。盡管De Jong和Hollstien一樣主要側重於函數優化的應用研究，但他將選擇、交叉和變異操作進一步完善和系統化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術。可以認為，De Jong的研究工作為遺傳演算法及其應用打下了堅實的基礎，他所得出的許多結論迄今仍具有普遍的指導意義。

進入20世紀80年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳演算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳演算法進行優化和規則學習的能力也顯著提高，同時產業應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳演算法增添了新的活力。

隨著應用領域的擴展，遺傳演算法的研究出現了幾個引人注目的新動向：一是基於遺傳演算法的機器學習（Genetic Base Machine Learning），這一新的研究課題把遺傳演算法從歷來離散的搜索空間的優化搜索演算法擴展到具有獨特的規則生成功能的嶄新的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精煉的瓶頸難題帶來了希望。二是遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其他智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是並行處理的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智能計算機體系結構的研究都是十分重要的。四是遺傳演算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳演算法在這方面將會發揮一定的作用。五是遺傳演算法和進化規劃（Evolution Programming，EP）以及進化策略（Evolution Strategy，ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳演算法同時獨立發展起來的，同遺傳演算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，既同遺傳演算法具有相同之處，也有各自的特點。

隨著遺傳演算法研究和應用的不斷深入和發展，一系列以遺傳演算法為主題的國際會議十分活躍。從1985年開始，國際遺傳演算法會議，即ICGA（International Conference on Genetic Algorithm）每兩年舉行一次。在歐洲，從1990年開始也每隔一年舉辦一次類似的會議，即 PPSN（Parallel Problem Solving from Nature）會議。除了遺傳演算法外，大部分有關ES和EP的學術論文也出現在PPSN中。另外，以遺傳演算法的理論基礎為中心的學術會議有FOGA（Foundation of Genetic Algorithm）。它也是從1990年開始，隔年召開一次。這些國際學術會議論文集中反映了遺傳演算法近些年來的最新發展和動向。

『伍』 遺傳演算法都能幹啥啊

遺傳演算法的應用有很多，一般用於解決工程優化問題。像選址問題、排班問題、路線優化、參數優化、函數求極值等等

『陸』 如何通俗易懂地解釋遺傳演算法

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

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

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

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

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

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

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

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

000 001 010

011 100 101

110 111

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

『柒』 請教計算機高手，關於遺傳演算法問題

這個容易，就是使用原樣本數據，很據復制，突變，片段交換等方法生成新的數據樣本，只不過不用像遺傳演算法那樣進行遺傳選擇而已。

『捌』 遺傳演算法有哪些方向

遺傳演算法研究方向主要有以下幾個方面：
1. 遺傳演算法基礎理論研究
在遺傳演算法中,群體規模和遺傳運算元的控制參數的選取 是必要的試驗參數。
遺傳演算法的收斂也是遺傳演算法基礎理論研究方向之一。

2. 遺傳演算法的分類系統
分類系統屬於基於遺傳演算法的機器學習中的一類,包括一個簡單 的基於串規則的並行生成子系統、規則評價子系統和遺傳演算法子系統 。
分類系統被人們越來越多地應用在科學、工程和經濟領域中,是目 前遺傳演算法研究中一個十分活躍的領域。
3. 分布並行遺傳演算法
分布並行遺傳算 法的研究表明,只要通過保持多個群體和恰當控制群體間的相互作用 來模擬並行執行過程,即使不使用並行計算機,也能提高演算法的執行效 率。
4. 遺傳進化演算法
模擬自然進化過程可以產生魯棒的計算機演算法--進化演算法。其餘兩種演算法是進化規劃和進化策略 。

5. 遺傳神經網路
包括連接權、網路結構和學習規則的進化。