遺傳算法研究綜述

收稿日期：2008-01-12；修回日期：2008-03-26

基金項目：西南大學研究生科技創(chuàng)新基金資助項目（2006011）

作者簡介：葛繼科(1977-)，男，河南濮陽人，博士研究生，主要研究方向為人工智能、語義網格（gjkid@swu.edu.cn）；邱玉輝(1938-)，男， 教授，博導，主要研究方向為人工智能、語義網格；吳春明(1972-)，男，博士研究生，主要研究方向為網絡技術；蒲國林(1971-)，男， 博士研究生，主要研究方向為人工智能.*

(1.西南大學 計算機與信息科學學院，重慶 400715；2.四川文理學院 計算機科學系，四川達州 635000)

摘 要：介紹了遺傳算法的基本工作原理和主要特點，討論了遺傳算法的理論、技術、存在

問題及改進方法，概述了遺傳算法的常見應用領域，分析了近五年國內對遺傳算法的研究現狀。最后，進一步探討了遺傳算法的未來研究方向。

關鍵詞：遺傳算法；算子；優(yōu)化；收斂性

中圖分類號：TP301.6

文獻標志碼：A

文章編號：1001-3695(2008)10-2911-06

Summary of genetic algorithms research

GE Ji-ke¹， QIU Yu-hui¹， WU Chun-ming¹， PU Guo-lin²

(1. School of Computer Information Science， Southwest University， Chongqing 400715， China；2. Dept. of Computer Science， Sichuan University of Arts Science， Dazhou Sichuan 635000， China)

Abstract:This paper introduced the history， basic principle and main characters of genetic algorithms， discussed the theory， technology， limitation and improving measures about genetic algorithm. Then summarized the implementation techniques and applications of genetic algorithms， analyzed the research state of genetic algorithms in China during the past five years， and pointed out the genetic algorithms’ research directions in the future.

Key words：genetic algorithm(GA); operator; optimization; convergence

遺傳算法是由美國Michigan大學的Holland教授于1969年提出，后經DeJong、Goldberg等人歸納總結所形成的一類模擬進化算法[1~3]。它來源于達爾文的進化論、魏茨曼的物種選擇學說和孟德爾的群體遺傳學說。遺傳算法是模擬自然界生物進化過程與機制求解極值問題的一類自組織、自適應人工智能技術[4]，其基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優(yōu)解的算法，具有堅實的生物學基礎；它提供從智能生成過程觀點對生物智能的模擬，具有鮮明的認知學意義；它適合于無表達或有表達的任何類函數，具有可實現的并行計算行為；它能解決任何種類實際問題，具有廣泛的應用價值。因此，遺傳算法廣泛應用于自動控制、計算科學、模式識別、工程設計、智能故障診斷、管理科學和社會科學等領域，適用于解決復雜的非線性和多維空間尋優(yōu)問題。

雖然遺傳算法在許多領域中都有成功的應用，但其自身也存在不足，如局部搜索能力差、存在未成熟收斂和隨機游走等現象，導致算法的收斂性能差，需要很長時間才能找到最優(yōu)解等問題。這些不足阻礙了遺傳算法的推廣應用。如何改善遺傳算法的搜索能力和提高算法的收斂速度，使其更好地應用于實際問題的解決中，是各國研究者一直探索的主要課題。

1 遺傳算法的執(zhí)行過程及特點

11 遺傳算法的執(zhí)行過程

遺傳算法作為一種自適應全局優(yōu)化搜索算法，使用二進制遺傳編碼，即等位基因Γ={0，1}，個體空間HL={0，1}L，且繁殖分為交叉與變異兩個獨立的步驟進行。其基本執(zhí)行過程如下[5]：

a)初始化。確定種群規(guī)模N、交叉概率Pc、變異概率Pm和置終止進化準則；隨機生成N個個體作為初始種群X(0)；置進化代數計數器t←0。

b)個體評價。計算或估價X（t）中各個體的適應度。

c)種群進化。

(a)選擇（母體）。從X(t)中運用選擇算子選擇出M/2對母體（M≥N）。

(b)交叉。對所選擇的M/2對母體，依概率Pc執(zhí)行交叉形成M個中間個體。

(c)變異。對M個中間個體分別獨立依概率Pm執(zhí)行變異，形成M個候選個體。

(d)選擇（子代）。從上述所形成的M個候選個體中依適應度選擇出N個個體組成新一代種群X(t+1)。

d）終止檢驗。如已滿足終止準則，則輸出X(t+1)中具有最大適應度的個體作為最優(yōu)解，終止計算；否則置t←t+1并轉c)。

12 遺傳算法的特點

遺傳算法利用了生物進化和遺傳的思想。它不同于枚舉法、啟發(fā)式算法、搜索算法等傳統(tǒng)的優(yōu)化方法，具有如下特點：

a）自組織、自適應和智能性。遺傳算法削除了算法設計中的一個最大障礙，即需要事先描述問題的全部特點，并說明針對問題的不同特點算法應采取的措施。因此，它可用來解決復雜的非結構化問題，具有很強的魯棒性。

b）直接處理的對象是參數編碼集，而不是問題參數本身。

c）搜索過程中使用的是基于目標函數值的評價信息，搜索過程既不受優(yōu)化函數連續(xù)性的約束，也沒有優(yōu)化函數必須可導的要求。

d）易于并行化，可降低由于使用超強計算機硬件所帶來的昂貴費用。

e）基本思想簡單，運行方式和實現步驟規(guī)范，便于具體使用。

2 遺傳算法的理論研究

21 編碼表示

在許多問題求解中，編碼是遺傳算法中首要解決的問題，對算法的性能有很重要的影響。Holland提出的二進制編碼是遺傳算法中最常用的一種編碼方法，它采用最小字符編碼原則，編/解碼操作簡單易行，利于交叉、變異操作的實現，也可以采用模式定理對算法進行理論分析[1]。但二進制編碼用于多維、高精度數值問題優(yōu)化時，不能很好地克服連續(xù)函數離散化時的映射誤差；不能直接反映問題的固有結構，精度不高，并且個體長度大、占用內存多。針對二進制編碼存在的不足，人們提出了多種改進方法，比較典型的有以下幾種：

a）格雷碼編碼。為了克服二進制編碼在連續(xù)函數離散化時存在的不足，人們提出了用格雷碼進行編碼的方法，它是二進制編碼的變形[6]。假設有一個二進制編碼為X=xmxm-1…x2x1，其對應的格雷碼為Y=ymym-1…y2y1，則

ym=xm

yi=xi+1xi

i=m-1，m-2，…，1

格雷碼不僅具有二進制編碼的一些優(yōu)點，而且能夠提高遺傳算法的局部搜索能力。

b）實數編碼。該方法適合于遺傳算法中表示范圍較大的數，使遺傳算法更接近問題空間，避免了編碼和解碼的過程。它便于較大空間的遺傳搜索，提高了遺傳算法的精度要求[6]；便于設計專門問題的遺傳算子；便于算法與經典優(yōu)化方法的混合作用，改善了遺傳算法的計算復雜性，提高了運算效率。

c）十進制編碼。該方法利用十進制編碼控制參數，緩解了“組合爆炸”和遺傳算法的早熟收斂問題[7]。

d）非數值編碼。染色體編碼串中的基因值取一個僅有代碼含義而無數值含義的符號集，這些符號可以是數字也可以是字符[8]。非數值編碼的優(yōu)點是在遺傳算法中可以利用所求問題的專門知識及相關算法。對于非數值編碼，問題的解和染色體的編碼要注意染色體的可行性、染色體的合法性和映射的惟一性。

22 適應度函數

在遺傳算法中，適應度是描述個體性能的主要指標，根據適應度的大小對個體進行優(yōu)勝劣汰。對于求解有約束的優(yōu)化問題時，一般采用罰函數方法將目標函數和約束條件建立成一個無約束的優(yōu)化目標函數；然后再將目標函數作適當處理，建立適合遺傳算法的適應度函數。將目標函數轉換成適應度函數一般應遵循兩個原則：適應度必須非負；優(yōu)化過程中目標函數的變化方向應與群體進化過程中適應度函數變化方向一致[9]。在使用遺傳算法求解具體問題時，適應度函數的選擇對算法的收斂性以及收斂速度的影響較大，針對不同的問題需根據經驗或算法來確定相應的參數。

何新貴等人在對遺傳算法的研究過程中，考慮函數在搜索點的函數值及其變化率，并將該信息加入適應度函數，使得按概率選擇的染色體不但具有較小的函數值，而且具有較大的函數變化率值[10]。實驗結果表明，這類方法的收斂速度明顯高于標準的遺傳算法。陶卿等人提出基于約束區(qū)域神經網絡的動態(tài)遺傳算法[11]，將遺傳算法的全局搜索和約束區(qū)域神經網絡模型的局部搜索結合起來；利用動態(tài)遺傳算法確定神經網絡模型的初始點，同時使用神經網絡確定動態(tài)遺傳算法的適應度函數。

23 遺傳算子

在遺傳算法中通過一系列算子來決定后代，算子對當前群體中選定的成員進行重組和變異。

1）選擇算子 選擇操作通過適應度選擇優(yōu)質個體而拋棄劣質個體，體現了“適者生存”的原理。Potts等人概括了23種選擇方法[12]。常見的選擇操作主要有以下幾種：

a）輪盤賭選擇。選擇某假設的概率是通過這個假設的適應度與當前群體中其他成員的適應度的比值而得到。此方法是基于概率選擇的，存在統(tǒng)計誤差，因此可以結合最優(yōu)保存策略以保證當前適應度最優(yōu)的個體能夠進化到下一代而不被遺傳操作的隨機性破壞，保證算法的收斂性。

b）排序選擇。對個體適應值取正值或負值以及個體適應度之間的數值差異程度無特殊要求，對群體中的所有個體按其適應度大小進行排序，根據排序來分配各個體被選中的概率。

c）最優(yōu)個體保存。父代群體中的最優(yōu)個體直接進入子代群體中。該方法可保證在遺傳過程中所得到的個體不會被交叉和變異操作所破壞，它是遺傳算法收斂性的一個重要保證條件；它也容易使得局部最優(yōu)個體不易被淘汰，從而使算法的全局搜索能力變強。

d）隨機聯(lián)賽選擇。每次選取N個個體中適應度最高的個體遺傳到下一代群體中。具體操作如下：從群體中隨機選取N個個體進行適應度大小比較，將其中適應度最高的個體遺傳到下一代群體中；將上述過程重復執(zhí)行M(為群體大小)次，則可得到下一代群體。

2）交叉算子 交叉是指對兩個相互交叉的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。它是產生新個體的主要方法，決定了遺傳算法的全局搜索能力，在遺傳算法中起關鍵作用。Potts等人概括了17種交叉方法[12]。幾種常用的適用于二進制編碼或實數編碼方式的交叉算子如下：

a）單點交叉。在個體編碼串中隨機設置一個交叉點后在該點相互交換兩個配對個體的部分基因。

b）兩點交叉。在相互配對的兩個個體編碼串中隨機設置兩個交叉點，并交換兩個交叉點之間的部分基因。

c）均勻交叉。兩個相互配對個體的每一位基因都以相同的概率進行交換，從而形成兩個新個體。

d）算術交叉。由兩個個體的線性組合而產生出新的個體。

3）變異算子 變異是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。它是產生新個體的輔助方法，決定了遺傳算法的局部搜索能力[12]。變異算子與交叉算子相互配合，可以共同完成對搜索空間的全局搜索和局部搜索，從而使得遺傳算法以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。在遺傳算法中使用變異算子主要有以下兩個目的：改善遺傳算法的局部搜索能力；維持群體的多樣性，防止出現早熟現象。下面是幾種常用的變異操作：

a）基本位變異。對個體編碼串以變異概率P隨機指定某一位或某幾位基因進行變異操作。

b）均勻變異(一致變異)。分別用符合某一范圍內均勻分布的隨機數，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。均勻變異操作特別適合應用于遺傳算法的初期運行階段，它使得搜索點可以在整個搜索空間內自由地移動，從而可以增加群體的多樣性，使算法能夠處理更多的模式。

c）二元變異。需要兩條染色體參與，通過二元變異操作后生成兩條新個體中的各個基因分別取原染色體對應基因值的同或/異或。它改變了傳統(tǒng)的變異方式，有效地克服了早熟收斂，提高了遺傳算法的優(yōu)化速度[13]。

d）高斯變異。在進行變異時用一個均值為μ、方差為σ²的正態(tài)分布的一個隨機數來替換原有基因值。其操作過程與均勻變異類似。

24 參數選擇

遺傳算法的參數選擇一般包括群體規(guī)模、收斂判據、雜交概率和變異概率等。參數選擇關系到遺傳算法的精度、可靠性和計算時間等諸多因素，并且影響到結果的質量和系統(tǒng)性能。因此，在遺傳算法中參數選擇的研究非常重要。

在標準的遺傳算法中經常采用經驗對參數進行估計，這將帶來很大的盲目性從而影響算法的全局最優(yōu)性和收斂性，人們意識到這些參數應該隨著遺傳進化而自適應變化。基于這一觀點，Davis提出了自適應算子概率方法[14]，即用自適應機制把算子概率與算子產生的個體表示適應性相結合，高適應性值被分配高算子概率。Whitley等人提出了自適應突變策略與一對父串間的Hamming距離成反比的觀點[15]，結果顯示能有效地保持基因的多樣性。張良杰等人通過引入i位改進子空間概念，采用模糊推理技術確定選取突變概率的一般性原則[16]。文獻[17]中用模糊規(guī)則對選擇概率和變異概率進行控制，在線改變其值。相應的算例表明，這種方法有較好的性能。

25 收斂性分析

遺傳算法的收斂性通常是指遺傳算法所生成的迭代種群(或其分布)收斂到某一穩(wěn)定狀態(tài)(或分布)，或其適應值函數的最大或平均值隨迭代趨于優(yōu)化問題的最優(yōu)值。依不同的研究方法及所應用的數學工具，收斂性分析可分為Vose-Liepins模型、Markov鏈模型和公理化模型等。

1）Vose-Liepins模型

該模型是Vose和Liepins提出來的，它用兩個矩陣算子分別刻畫比例選擇與組合算子(即雜交算子與變異算子的復合)，通過這兩個算子不動點的存在性與穩(wěn)定性來刻畫遺傳算法的漸近行為[18]。

Vose-Liepins模型只適用于簡單遺傳算法，可應用于比例選擇、單點雜交和單點變異等，沒有推廣到更具實用性的其他遺傳算法執(zhí)行策略中，如錦標賽選擇、多點雜交等。另外，Vose-Liepins模型不易處理變異、雜交概率隨時間變化的情形，其框架亦很難推廣到描述一般非二進制或連續(xù)變量情形的遺傳算法。

Vose-Liepins模型雖然在種群規(guī)模無限的假設下可精確刻畫遺傳算法，但在有限規(guī)模情形下卻只能描述遺傳算法的平均形態(tài)。為了克服這個缺陷，Nix和Vose結合Vose-Liepins模型與Markov鏈描述，發(fā)展了遺傳算法的一個精確Markov鏈模型[19]。

2）Markov鏈模型

遺傳算法的馬氏鏈模型主要有三種：種群馬氏模型、Vose模型[19]和Cerf擾動馬氏鏈模型[20]。

種群馬氏鏈模型將遺傳算法的種群迭代序列視為一個有限狀態(tài)馬氏鏈加以研究，主要是運用種群馬氏鏈轉移概率矩陣的某些一般性質分析遺傳算法的極限行為。

在Vose模型中，種群的狀態(tài)由一個概率向量表示，概率向量的維數為所有可能個體的數目。當種群規(guī)模趨于無窮大時，相對頻率的極限就代表了每一個個體在種群中出現的概率。在無限種群規(guī)模假設下，可以導出表示種群的概率向量的不動點及其穩(wěn)定性，從而導致對遺傳算法極限行為的刻畫。

R.Cerf利用Azencott等人關于模擬退火的一系列工作，將遺傳算法看成一種特殊形式的廣義模擬退火模型，利用動力系統(tǒng)的隨機擾動理論對遺傳算法的極限行為及收斂速度進行了研究[20]。盡管在Cerf模型中所研究的馬氏鏈序列仍然是種群序列，但研究方法與種群馬氏鏈模型有差異，所以稱之為Cerf擾動馬氏鏈模型。

用Markov鏈模型描述遺傳算法雖然有直接、精確的優(yōu)點，但由于有限狀態(tài)Markov鏈理論本身的限制，與Vose-Liepins模型類似，該模型只能用于描述通常的二進制或特殊的非二進制遺傳算法。另外，這類方法所得收斂性一般是指相應的Mar-kov鏈趨于某一平穩(wěn)分布。這與優(yōu)化中通常所指的收斂性定義不同，它并不保證遺傳算法一定能收斂到問題的全局最優(yōu)解。再者，相應Markov鏈的狀態(tài)數(轉移矩陣的規(guī)模)通常很大，這使得具體確定、分析轉移矩陣的性態(tài)十分困難，因而對于較大規(guī)模的遺傳算法，Markov鏈分析只能基于遍歷性考察而得出相應遺傳算法收斂性的某些“粗糙”結論。

3）公理化模型

遺傳算法的公理化方法基于對模擬進化計算操作的公理化描述，應用各個相關操作的本質特征數來對算法的收斂性直接進行概率估計[21]。這一方法不僅適用于包括非齊次、自適應等在內的各種遺傳算法分析，而且分析方法本身直觀、清晰，所導出的結論也對遺傳算法的各種參數選擇提供參考依據。這一模型具有重要的理論意義與實用價值。

文獻[5]還通過詳細估計常見選擇算子與演化算子的選擇壓、選擇強度、保持率、遷入率、遷出率等參數，導出了一系列具有重要應用價值的遺傳算法收斂性結果。公理化模型也可用于其他模擬演化算法的收斂性分析。

26 欺騙問題

欺騙問題是遺傳算法研究中的一個熱點。根據模式定理可知，低階、短距的優(yōu)模式在遺傳子代中將以指數級增長，最終，不同的最優(yōu)模式相互組合，從而得到最優(yōu)解。但是，對于欺騙問題，復制算子受欺騙條件的“迷惑”，使最優(yōu)低階模式在組合后形成非最優(yōu)高階模式，從而使遺傳算法偏離最優(yōu)解。由于欺騙問題的存在，許多問題被歸結為遺傳算法難題，使遺傳算法的應用受到一定的局限。目前遺傳算法的欺騙問題研究主要集中在三個方面：a)設計欺騙函數，如Goldberg曾設計一個離散遺傳算法的最小欺騙問題。b)修改遺傳算法以解決欺騙函數的影響，如黃炎等人提出一種基于可調變異算子求解遺傳算法中欺騙問題的方法，即在遺傳搜索過程中通過改變變異算子的方向和概率求解遺傳算法的欺騙問題[22]。該方法能夠在消除遺傳算法中欺騙性條件的同時保持群體的多樣性，使遺傳算法可以順利地收斂到全局最優(yōu)解。c)理解欺騙函數對遺傳算法的影響，何軍等人討論了一類遺傳算法求解完全欺騙性問題的平均計算時間[23]。

27 并行遺傳算法

并行算法的基本思想是將一個復雜的任務分解為多個較簡單的子任務，然后將各子任務分別分配給多個處理器并行執(zhí)行求解。例如，Zeigler等人把高性能并行遺傳算法應用到大型并行計算機[24]，這種分而治之的思想可以由不同的方法和途徑實現，導致了各種不同類型的并行遺傳算法。并行遺傳算法可以分為四大類，即全局并行遺傳算法、粗粒度并行遺傳算法、細粒度并行遺傳算法和混合并行遺傳算法。

侯廣坤等人討論了并行遺傳算法的遷移現象及群體規(guī)模估算模型，分析了遷移的過程，揭示了遷移的實質，并提出了在理想條件下的遷移計算模型[25]，基于遷移計算模型導出了粗粒度并行遺傳算法進化質量估量模型。王洪燕等人對并行遺傳算法的研究現狀進行了詳細的介紹[26]。

3 遺傳算法的應用

遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，廣泛應用于多種學科領域。

31 函數優(yōu)化

函數優(yōu)化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。不同研究者構造出了各種各樣的復雜形式的測試函數，有連續(xù)函數也有離散函數，有凸函數也有凹函數，有低維函數也有高維函數，有確定函數也有隨機函數，有單峰值函數也有多峰值函數等。用這些幾何特性各具特色的函數來評價遺傳算法的性能，更能反映算法的本質效果。對于一些非線性、多模型、多目標的函數優(yōu)化問題，用其他優(yōu)化方法較難求解，遺傳算法卻可以方便地得到較好的結果[27]。

32 組合優(yōu)化

隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確的最優(yōu)解。對這類復雜問題，應把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法已經在求解旅行商問題、背包、裝箱、布局優(yōu)化、圖形劃分等各種具有NP難度的問題上得到成功的應用[6，28~30]。

33 生產調度

在很多情況下，用常規(guī)方法建立的數學模型難以精確求解生產調度問題，即使經過一些簡化之后可以進行求解，有時也會因簡化太多而使得求解結果與實際目標相差甚遠。一般情況下，在現實生產中主要是靠經驗來進行調度。研究發(fā)現，遺傳算法已成為解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規(guī)劃、任務分配等方面，遺傳算法都得到了有效的應用[8，31，32]。

34 自動控制

在自動控制領域中有很多與優(yōu)化相關的問題需要求解，遺傳算法已在其中得到了初步的應用，并顯示出良好的效果。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化[33]、使用遺傳算法設計空間交匯控制器、基于遺傳算法的模糊控制器的優(yōu)化設計[34]、基于遺傳算法的參數辨識、基于遺傳算法的模糊控制規(guī)則的學習，利用遺傳算法進行人工神經網絡的結構優(yōu)化設計和權值學習等，都顯示出了遺傳算法在這些領域中應用的可能性。

35 機器人學

機器人是一類復雜的、難以精確建模的人工系統(tǒng)。由于遺傳算法的起源來自于人工自適應系統(tǒng)的研究，機器人學理所當然地成為遺傳算法的一個重要應用領域。遺傳算法已經在移動機器人路徑規(guī)劃[35]、關節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結構優(yōu)化和行為協(xié)調等方面進行了研究和應用[36]。

36 圖像處理

圖像處理是計算機視覺中的一個重要研究領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一些誤差，從而影響圖像的效果。如何使這些誤差最小化是計算機視覺達到實用化的重要要求。遺傳算法可用于圖像處理中的優(yōu)化計算，目前已在模式識別（包括漢字識別[37]）、圖像恢復、圖像邊緣特征提取等方面得到了應用[38，39]。

37 人工生命

人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學習能力是人工生命的兩大主要特征。人工生命與遺傳算法有著密切的聯(lián)系，基于遺傳算法的進化模型是研究人工生命現象的重要基礎理論。雖然人工生命的研究尚處于初期階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力，并且必將會得到更為深入的應用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供一個有效的工具，人工生命的研究也必將促進遺傳算法的進一步發(fā)展[40]。

38 遺傳編程

遺傳編程（genetic programming， GP）采用樹型結構表示計算機程序，運用遺傳算法的思想，通過自動生成計算機程序來解決問題。雖然遺傳編程的理論尚未成熟，應用也有一些限制，但它已成功地應用于人工智能、機器學習等領域[41]。Koza等人描述了基本的遺傳編程方法并且給出了很多可以被GP成功學習的程序[42~44]。

39 機器學習

學習能力是高級自適應系統(tǒng)所具備的能力之一，基于遺傳算法的機器學習，特別是分類器系統(tǒng)，在很多領域中都得到了應用。遺傳算法被用于學習模糊控制規(guī)則，可以更好地改進模糊系統(tǒng)的性能；基于遺傳算法的機器學習不但可以用來調整人工神經網絡的連接權，也可用于人工神經網絡結構的優(yōu)化設計[45，46]。

310 數據挖掘

數據挖掘能夠從大規(guī)模數據庫中提取隱含的、未知的、有潛在應用價值的知識和規(guī)則。許多數據挖掘問題可以看做是搜索問題。其中，數據庫可看做是搜索空間，挖掘算法可看做是搜索策略。應用遺傳算法在數據庫中進行搜索，對隨機產生的一組規(guī)則進行進化，直到數據庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數據庫中的規(guī)則[47~49]。Sunil 已成功地開發(fā)了一個基于遺傳算法的數據挖掘工具[50]，利用該工具對兩個飛機失事的真實數據庫進行了數據挖掘實驗，結果表明遺傳算法是進行數據挖掘的有效方法之一。

4 近五年國內遺傳算法研究現狀

在前人研究的基礎上，本文以已發(fā)表論文為依據，重點考查了2002—2006年國內學者及工程技術人員在遺傳算法方面的研究情況，如表1所示。該表數據的統(tǒng)計源是中國知網（CNKI）的“電子技術及信息科學類”中收錄的中文核心期刊。

表1 2002—2006年國內遺傳算法研究現狀年度綜述函數

優(yōu)化組合

優(yōu)化生產

調度自動

控制機器

人學圖像

處理人工

生命遺傳

編程機器

學習數據

挖掘

表1分別從綜述、函數優(yōu)化、組合優(yōu)化、生產調度、自動控制、機器人學、圖像處理、人工生命、遺傳編程、機器學習、數據挖掘11個方面對近五年國內發(fā)表在中文核心期刊上、與遺傳算法有關的論文進行了分類。圖1是根據表1生成的對比分析圖。

通過對表1及圖1的分析可以得出如下結論：

a）針對遺傳算法函數優(yōu)化和組合優(yōu)化方面進行研究的文章每年幾乎都是最多的。這說明對遺傳算法進行的研究更多的還是停留在理論層面，而生產調度及自動控制等實際應用領域的研究成果較少，有待進一步深入研究。

b）總體來看，近五年國內對遺傳算法的研究在逐年增長，但從2005年起有所回落，到2006年出現減少的現象。從這一現象來看，國內關于遺傳算法的研究興趣可能已達到飽和，理論研究已經比較成熟。另外，就目前研究現狀來看，很難在原有的基礎上得出更多新的成果。

c）遺傳算法在數據挖掘和機器學習領域進行的研究在研究成果中所占的比重逐年明顯增長。這說明遺傳算法在數據挖掘和機器學習領域的研究成為新的熱點。雖然有效成果占總的研究成果的比例還很少，但這是一個可以進行深入研究的方向。

5 遺傳算法的未來研究方向

遺傳算法在各種問題的求解與應用中展現了其特點和魅力，同時也暴露出它在理論和應用上的諸多不足和缺陷。未來幾年內遺傳算法的研究重點可能集中在以下幾方面：

a）算法的數學基礎，包括算法的收斂性、收斂速度估計、早熟機理的探索與預防、交叉算子的幾何意義與統(tǒng)計解釋、參數設置對算法的影響等方面。算法的收斂速度估計是當前特別值得研究和探討的問題，它能從理論上對遺傳算法的任何修正形式提供評判標準，從而指明改進算法性能的正確方向。

b）遺傳算法與優(yōu)化技術的融合。對遺傳算法的大范圍群體搜索性能與快速收斂的局部優(yōu)化方法進行混合，從而產生有效的全局優(yōu)化方法。這種策略可從根本上提高遺傳算法計算性能，對此可以進行大量的理論分析和實驗。

c）算法的改進與深化。根據具體應用領域對遺傳算法進行改進與完善，僅泛泛地對一般問題進行研究是遠遠不夠的。當前針對具體應用問題深化研究遺傳算法是特別值得提倡的工作。

d）算法的選擇。基于實驗研究的結論并不具有普遍意義上的指導作用，因此從數學的角度進行遺傳算法的理論研究將對算法的合理選擇提供理論指導。

e）算法的并行化研究。遺傳算法的群體適應度評價、隨機搜索等特征使其具有明顯的并行性。因此，設計各種并行執(zhí)行策略、建立相應的并行化遺傳算法的數學基礎，是一項具有重要意義的工作。

6 結束語

遺傳算法作為一種非確定性的擬自然算法，為復雜系統(tǒng)的優(yōu)化提供了一種新的方法，實踐證明其效果顯著。盡管遺傳算法在很多領域具有廣泛的應用價值，但它仍存在一些問題，各國學者一直都在探索對遺傳算法的改進及發(fā)展，以使遺傳算法有更廣泛的應用領域。

參考文獻：

[1]HOLLAND J H. Adaptation in natural and artificial systems[M]. Ann Arbor: University of Michigan Press，1975.

[2]DeJONG K A. The analysis of the behavior of a class of genetic adaptive systems[D]. Ann Arbor: University of Michigan， 1975.

[3]GOLDBERG D E. Genetic algorithms in search， optimization and machine learning[M]. Boston: Addison-Wesley Longman Press， 1989.

[4]張文修， 梁怡. 遺傳算法的數學基礎[M].西安：西安交通大學出版社，2000.

[5]徐宗本， 張講社， 鄭亞林. 計算智能中的仿生學：理論與算法[M]. 北京：科學出版社，2003.

[6]周明， 孫樹棟. 遺傳算法原理及應用[M]. 北京：國防工業(yè)出版社，1999.

[7]唐飛， 滕弘飛. 一種改進的遺傳算法及其在布局優(yōu)化中的應用[J]. 軟件學報， 1999，10(10):1096-1102.

[8]玄光男， 程潤傳. 遺傳算法與工程設計[M]. 北京：科學出版社，2000.

[9]邢文訓， 謝金星. 現代優(yōu)化計算方法[M]. 北京：清華大學出版社，1999.

[10]何新貴， 梁久禎. 利用目標函數梯度的遺傳算法[J]. 軟件學報，2001，12(7):981-985.

[11]陶卿， 曹進德， 孫德敏，等. 基于約束區(qū)域神經網絡的動態(tài)遺傳算法[J]. 軟件學報， 2001，12(3):462-467.

[12]POTTS C J， TERRI D. The development and evaluation of an improved genetic algorithm based on migration and artificial selection[J]. IEEE Trans on Systems， Man， and Cybernetics， 1994， 24(1):73-86.

[13]楊啟文， 蔣靜坪， 張國宏. 遺傳算法優(yōu)化速度的改進[J]. 軟件學報，2001，12(2):270-275.

[14]DAVIS L. Adaptive operator probability in genetic algorithms[C]// Proc of the 3rd International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann Publishers，1989: 61-69.

[15] WHITLEY D， STARKWEATHER D. Gene-tic II: a distributed genetic algorithms[J]. Journal of Experimental Theoretical Artificial Intelligence， 1990， 7(7):189-214.

[16]張良杰， 毛志宏， 李衍達. 遺傳算法中突變算子的數學分析及改進策略[J]. 電子科學學刊， 1996， 18(6):590-595.

[17]LIU Li， CHEN Xue-yun. Reconfiguration of distribution networks based on fuzzy genetic algorithms[J]. Proceedings of the Chinese Society of Electrical Engineering，2000，20(2)：66-69.

[18]VOSE M D， LIEPINS G E. Punctuated equilibria in genetic search[J]. Complex Systems， 1991， 5(1):31-34.

[19]NIX A E， VOSE M D. Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics and Artificial Intelligence， 1992， 5(1):79-88.

[20]CERF R. Asymptotic convergence of a genetic algorithms[J]. Comptes Rendus de l’Académie des Sciences: Série 1， Mathématique， 1994， 319(33): 271-276.

[21]GOLDBERG D E. Genetic and evolutionary algorithms come of age[J]. Communications of the ACM， 1994，37(3): 113-119.

[22]黃炎， 蔣培， 王嘉松，等. 基于可調變異算子求解遺傳算法的欺騙問題[J]. 軟件學報，1999，10(2):216-219.

[23]何軍， 黃厚寬， 康立山. 遺傳算法求解完全欺騙問題的平均計算時間[J]. 計算機學報， 1999， 22(9):999-1003.

[24]ZEIGLER B P， KIM J. Asynchronous genetic algorithms on parallel computers[C]// Proc of the 5th International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann Publishers，1991: 75-83.

[25]侯廣坤， 駱江鵬. 一種理想并行遺傳算法模型[J]. 軟件學報， 1999，10(5):557-559.

[26]王洪燕， 楊敬安. 并行遺傳算法研究進展[J]. 計算機科學， 1999， 26(6):48-53.

[27]黃冀卓， 王湛， 馬人樂. 一種新的求解約束多目標優(yōu)化問題的遺傳算法[J]. 計算機工程與應用， 2006，42(23):47-51.

[28]錢志勤， 滕弘飛， 孫治國. 人機交互的遺傳算法及其在約束布局優(yōu)化中的應用[J]. 計算機學報， 2001，24(5):553-558.

[29]王征應， 石冰心. 基于啟發(fā)式遺傳算法的QoS組播路由問題求解[J]. 計算機學報，2001，24(1):55-61.

[30]趙振勇， 王力， 王保華，等. 遺傳算法改進策略的研究[J]. 計算機應用， 2006， 26(12):189-191.

[31]李素粉， 朱云龍. 流水車間作業(yè)提前/拖期調度問題研究[J]. 計算機集成制造系統(tǒng)，2006， 12(8):1235-1240.

[32]饒運清， 嚴治雄， 張超勇，等. 一種混合遺傳算法在車間作業(yè)調度中的應用研究[J]. 機械科學與技術， 2006， 25(5):584-587，607.

[33]虞蕾， 趙紅， 趙宗濤. 一種基于遺傳算法的航跡優(yōu)化方法[J]. 西北大學學報:自然科學版， 2006， 36(2):205-208，213.

[34]李輝， 韓紅， 韓崇昭，等. 基于遺傳算法的模糊邏輯控制器優(yōu)化設計[J]. 西安交通大學學報， 2002，36(4):385-389.

[35]王科俊， 徐晶， 王磊，等. 基于可拓遺傳算法的機器人路徑規(guī)劃[J]. 哈爾濱工業(yè)大學學報， 2006， 38(7):1135-1138.

[36]周明， 孫樹棟， 彭炎午.使用遺傳算法規(guī)劃移動機器人路徑[J]. 西北工業(yè)大學學報， 1998，16(4):580-583.

[37]林磊， 王曉龍， 劉家鋒. 基于遺傳算法的手寫體漢字識別系統(tǒng)優(yōu)化方法的研究[J]. 計算機研究與發(fā)展，2001，38(6) :658-661.

[38]趙應丁， 劉金剛. 基于遺傳算法的指紋圖像二值化算法研究[J]. 計算機工程， 2006，32(7):169-171.

[39]王建鋒， 吳慶標. 分層遺傳算法實現圖像邊緣檢測[J]. 計算機工程與應用， 2006，42(14):95-96，151.

[40]王小平， 曹立明， 施鴻寶. 基于遺傳算法的人工生命演示系統(tǒng)設計[J]. 同濟大學學報:自然科學版， 2003， 31(2):224-228.

[41]查志琴， 高波， 鄭成增. 遺傳編程實現的研究[J].計算機應用， 2003， 23(7):137-139.

[42]KOZA J R. Genetic programming: on the programming of computers by means of natural selection[M]. Cambridge: MIT Press，1992.

[43]KOZA J R. Genetic programming II: automatic discovery of reusable programs[M]. Cambridge: MIT Press，1994.

[44]KOZA J R， BENNETT III F H， ANDRE D， et al. Four problems for which a computer program evolved by genetic programming is competitive with human performance[C]// Proc of IEEE International Conference on Evolutionary Computation. 1996:1-10.

[45]文紹純， 羅飛， 付連續(xù). 遺傳算法在人工神經網絡中的應用綜述[J]. 計算技術與自動化， 2001， 20(2):1-5.

[46]承向軍， 賀振歡， 楊肇夏. 基于遺傳算法的交通信號機器學習控制方法[J]. 系統(tǒng)工程理論與實踐， 2004， 24(8): 130-135.

[47]賈兆紅， 倪志偉. 改進型遺傳算法及其在數據挖掘中的應用[J]. 計算機應用， 2002，22(9):31-33.

[48]王靜蓮， 劉弘， 李少輝. 基于決策樹的遺傳算法在數據挖掘領域的應用[J]. 計算機工程與應用， 2005， 41(28): 153-155.

[49]張細政， 邢立寧， 伍棲. 基于遺傳算法的數據挖掘方法及應用[J]. 哈爾濱工程大學學報， 2006，27(7):384-388.

[50]SUNIL C. Design and implementation of a genetic based algorithm for data mining[C]//Proc of the 26th International Conference on Very Large Databases. San Francisco: Morgan Kaufmann Publishers，2000:33-42.