遺傳算法在人工智能領域中的應用

摘要：該文介紹了遺傳算法的基本概念、基本遺傳算法的特點和基本遺傳算法的求解步驟，同時也介紹了遺傳算法在機器學習、并行處理、人工生命以及遺傳算法與進化規則及進化策略的結合的發展動向，最后討論了基于遺傳算法的人工神經網絡學習中的應用研究，具體論述了遺傳算法在學習神經網絡權重和學習神經網絡拓撲結構的應用方法。

關鍵字：遺傳算法；機器學習；人工生命；人工神經網絡；神經網絡拓撲結構

中圖分類號：TP183文獻標識碼：A文章編號：1009-3044(2008)27-2040-03

The Application of Genetic Algorithm to the Artificial Intelligence

WANG Hui

(Xinjiang Petroleum Institute， Urumqi 830000， China)

Abstract: In this paper the author introduces the basic conception of genetic algorithm(GA for short)，the feature of GA and the calculation steps. We can also get a general idea of the development in the machine learning， Parallel Processing， artificial Life， and the integration of evolutionary rules and strategies. At last， the application of GA to artificial neural networks is discussed， especially the application of GA to the study of neural networks weight and the neural network topology.

Key words: genetic algorithm; machine learning; artificial life;artificial neural networks; neural network topology

1 遺傳算法簡介

遺傳算法是模仿生物遺傳學和自然選擇機理，通過人工方式構造的一類優化搜索算法，與傳統數學模型截然不同，它為那些難以找到傳統數學模型的難題找出了一個解決方法。遺傳算法借鑒了生物科學中達爾文的物競天擇、適者生存的進化準則，1975年，Michigan大學Holland教授根據這一規律首次提出了遺傳算法（genetic algorithm，簡稱GA），其基本思想是力求充分模仿這一自然尋優過程的隨機性、魯棒性和全局性。這是一種新型的全局優化搜索算法，因為其直接對結構對象進行操作，不存在求導和函數連續性的限定等數學問題，魯棒性強、隨機性、全局性以及適于并行處理，已廣泛應用于神經網絡、計算機科學、優化調度、運輸問題、組合優化、機器學習、信號處理、自適應控制和人工生命等領域，并且遺傳算法在實際應用中也取得了巨大成功。

2 基本遺傳算法

遺傳算法的工作過程本質上就是模擬生物的進化過程。首先，要規定一種編碼方法，使得你的問題的任何一個潛在可行解都能表示成為一個“數字”染色體。然后，創建一個由隨機的染色體組成的初始群體（每個染色體代表了一個不同的候選解），并在一段時期中，以培育適應性最強的個體的辦法，讓它們進化，在此期間，染色體的某些位置上要加入少量的變異。

遺傳算法是一種基于空間搜索的算法，它的求解可以看成是最優化過程。遺傳算法的最大優點就是，你不需要知道怎么去解決一個問題，你需要知道的僅僅是用什么樣的方式對可行解進行編碼，使得它能被遺傳算法機制所利用。遺傳算法并不能保證所得到的解是最優解，但可以將誤差控制在容許的范圍內。遺傳算法具有以下特點：

1） 遺傳算法是對參數集合的編碼而非針對參數本身進行優化；

2） 遺傳算法是從問題解的編碼組開始而非從單個解開始搜索；

3） 遺傳算法利用目標函數的適應度這一信息而非利用導數或其他輔助信息來指導搜索；

4） 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規則進行隨機操作。

那么下面對基本遺傳算法給出一個求解步驟：

1） 定義一個目標函數；

2） 將可行解群體在一定的約束條件下初始化，每一個可行解用一個向量x來編碼，稱為一條染色體，向量的分量代表基因，它對應可行解的某一決策變量；

3） 計算群體中每條染色體xi(i＝1，2，…，n)所對應的目標函數值，并以此計算適應值Fi，按Fi的大小來評價該可行解的好壞；

4） 以優勝劣汰的機制，將適應值差的染色體淘汰掉，對幸存的染色體根據其適應值的好壞，按概率隨機選擇，進行繁殖，形成新的群體；

5） 通過雜交和變異的操作，產生子代。雜交是隨機選擇兩條染色體（雙親），將某一點或多點的基因互換而產生兩個新個體，變異是基因中的某一點或多點發生突變；

6） 對子代群體重復步驟(3)～(5)的操作，進行新一輪遺傳進化過程，直到迭代收斂（適應值趨穩定）即找到了最優解或準最優解。

3 遺傳算法的發展動向

GA在應用方面的取得了較豐碩的成果，其主要應用領域在于函數優化，機器人學，設計，組合優化，信號處理，人工生命等，此外遺傳算法還有幾個引人注目的新動向。

3.1 基于GA的機器學習

這一新的研究方向把GA從歷史離散的搜索空間的優化搜索算法擴展到具有獨特的規則生成功能的嶄新的機器學習算法，這一新的學習機制對于解決人工智能中知識獲取和知識優化精煉的瓶頸難題帶來了希望，GA作為一種搜索算法從一開始就與機器學習有密切聯系。分類器系統是第一個基于GA的機器學習系統。基于GA的概念學習是近幾年機器學習領域的一個較為引人注目的研究方向。還有一些嵌入領域知識的基于GA的機器學習的研究。

3.2 并行處理的GA

并行處理的GA的研究不僅是GA本身的發展，而且對于新一代智能計算機體現結構的研究都是十分重要的，GA在操作上具有高度的并行性，許多研究人員都正在搜索在并行機上高效執行GA的策略。近幾年也發表了不少這方面的論文，研究表明，只要通過保持多個群體和恰當地控制群體間的相互作用來模擬并執行過程，即使不使用并行計算機，我們也能提高算法的執行效率。在并行GA的研究方面，一些并行GA可以分為兩類：一是粗粒度并行GA，它主要開發群體間的并行性，如Coboon分析了在并行計算機上解圖劃分問題的多群體GA的性能；另一類是細粒度并行GA，它主要開始一個群體中的并行性，如Kosak將群體中的每個個體映射到一個連接機的處理單元上，并指出了這種方法對網絡圖設計問題的有效性。

3.3 GA與人工生命的滲透

人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統特有行為的人造系統。人工生命與GA有密切的關系，基于遺傳算法的進化模型是研究人工生命現象的重要理論基礎，雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力，并且必將得到更為深入的應用和發展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供了一個有效的工具，人工生命的研究也必將促進遺傳算法的進一步發展。

3.4 GA與進化規則及進化策略的結合

GA，進化規則及進化策略是進化計算的三個主要分支，這三種典型的進化算法都以自然界中生物的進化過程為自適應全局優化搜索過程的借鑒對象，所以三者之間有較大的相似性，但三種算法又是從不完全相同的角度出發來模擬生物的進化過程，分別是依據不同的生物進化背景，不同的生物進化機制而開發出來的，所以又有差異。但在進化計算領域內更重要的工作是生物的進化機制，構造性能更加優良且適應性更加廣泛的進化算法。

4 基于遺傳算法優化神經網絡的應用研究

神經網絡和遺傳算法目標相近而方法各異。因此，將這兩種方法相互結合，必能達到取長補短的作用。近年來，在這方面已經取得了不少研究成果，形成了以遺傳算法與神經網絡相結合的進化神經網絡(ENN)。遺傳算法在神經網絡中的應用主要是用遺傳算法學習神經網絡的權重和學習神經網絡的拓撲結構兩個部分。

4.1 遺傳算法學習神經網絡的權重

而最主要的是學習神經網絡的權重，也就是用遺傳算法來取代一些傳統的學習算法 。目前廣泛研究的前饋網絡中采用的是Rumel hart等人推廣的誤差反向傳播（BP）算法，BP算法具有簡單和可塑的優點，但是BP算法是基于梯度的方法，這種方法的收斂速度慢，且常受局部極小點的困擾，采用遺傳算法則可把神經網絡的結構優化和權值學習合并起來一起求解，克服了BP算法的缺陷，是神經網絡權值學習的有效方法。

遺傳算法學習神經網絡權值的算法步驟如下：

1） 隨機產生一組分布，采用某種編碼方案對該組中的每個權值（或閾值）進行編碼，進而構造出一個個碼鏈（每個碼鏈代表網絡的一種權值分布），在網絡結構和學習算法已定的前提下，該碼鏈就對應一個權值和閾值取特定值的一個神經網絡；

2） 對所產生的神經網絡計算它的誤差函數，從而確定其適應度函數值，誤差與適應度成反比關系；

3） 選擇若干適應度函數值最大的個體，直接遺傳給下一代（精英保護策略）；

4） 利用交叉和變異等遺傳操作算子對當前一代群體進行處理，產生下一代（新一代）群體；

5） 重復步驟2～4，使初始確定的一組權值分布得到不斷的進化，直到訓練目標得到滿足或者迭代次數達到預設目標為止。

4.2 遺傳算法學習神經網絡的拓撲結構

神經網絡結構包括網絡的拓撲結構（連接方式）和接點轉移函數兩方面。利用遺傳算法設計神經網絡可根據某些性能評價準則如學習速度，泛化能力或結構復雜程度等搜索結構空間中滿足問題要求的最佳結構。利用遺傳算法設計神經網絡的關鍵問題之一仍然是如何選取編碼方案。

遺傳算法學習神經網絡結構的算法步驟如下:

1） 隨機產生若干個不同結構的神經網絡，對每個結構編碼，每個碼鏈對應一個網絡結構，N個碼鏈構成種群。

2） 利用多種不同的初始連接權值分別對每個網絡進行訓練。

3） 計算在每個對應碼鏈下神經網絡的誤差函數，利用誤差函數或其他策略（如網絡的泛化能力或結構復雜度）確定每個個體的適應度函數。

4） 選擇若干適應度函數值最大的個體構成父本。

5） 利用交叉，變異等遺傳操作算子對當前一代群體進行處理，產生新一代群體。

6） 重復上述2）-5）步驟，直到群體中的某個個體（對應一個網絡結構）能滿足要求為止。

5 結束語

遺傳算法作為一種新型的全局優化搜索算法，由于其直接對結構對象進行操作，不存在求導和函數連續性的限定，又具有魯棒性強、隨機性、全局性以及適于并行處理的優點，在人工神經網絡的應用上展現了它的獨特魅力與優勢，但同時，它在理論和應用技術上也存在著許多不足和缺陷，比如相對鮮明的生物基礎，其數學基礎顯得極為薄弱，尤其是缺乏深刻且具有普遍意義的理論分析。隨著理論研究的深入，可以肯定，作為一種高效并行的全局搜索方法，遺傳算法以其特有的算法特點使其在許多實際問題中的應用會越來越廣；同時，廣泛的數學方法和強大的計算機模擬工具的出現，必將使遺傳算法的研究取得長足的進展。

參考文獻：

[1] 蔡自興. 人工智能及其應用[M]. 3版.北京：清華大學出版社，2003.

[2] 王風琴. 基于遺傳算法的神經網絡優化[J].燕山大學學報，2001，25（3）：234-239.

[3] 陳國良. 遺傳算法及其應用[M].北京：人民郵電出版社，1999.

[4] 陳穎琪. 進化計算與神經網絡的結合[J].紅外與激光工程，1999，（4）：8-11，35.

[5] Kretnovich v.Qmtana C and Puentes O.Genetnc Algorithms-What Fitness Scaling is Optimal. Ctberm and System 1993.24.

[6] S W Mathfoud.Genetic drift in sharing methods. 0-7803-I899-4/94.1994 IEEE

[7] V Petrochs.S Kazarns. Varying quality function Gengentic algorithms and the cutting problem. 0-7803-I899-4/94.1994 IEEE

[8] 楊旭東，張彤. 遺傳算法應用于系統在線識別研究[J].哈爾濱工業大學學報， 2000，32（1）：102-104.

[9] Pham D T，Jin G. Genetic algorithms using gradient-like ren reduction operator. Electronics Letters. 1995 .31.

[10] Nover D，Baskaran S，Scbuster P. Understanding genetic algorithms dynamics using harvesting strategies. Physics D 79， 1994.

[11] Kao T， Hwang S Y. A genetic algorithm with sruptive selection[J]. IEEE Transcations on System， Man. And Cybernetris-Part B: Cybernetics 1996，26.

[12] Arabas J. Michalewicz Z and Mulawka J. GAVaPS-a Genetic Algorithms with Varying Population Size[C].Proc O the 1st IEEE on Evolutonary Computation IEEE，1994.

[13] Liu Li， Chen Xueyun. Reconfiguration of distribution networks based on fuzzy genetic algorithms[J]. proceedings of Chinese Society of the CSEE， 2000，20(9):44-49.