1、第16卷第1期1999年2月工程數學學報JOU RNAL O F EN G I N EER I N G M A TH EM A T I CSV o l.16N o.1Feb.1999遺傳算法(綜述 任平(暨南大學數學系,廣州510632摘要遺傳算法提供了在很寬的領域中實用的優化技術,本文綜述其基本概念與近期的發展。關鍵詞遺傳算法,人工智能,運籌學分類號AM S(199168T,92B;CCL T P18近年來,一種被稱為遺傳算法(Genetic A lgo rithm s,GA的優化技術有了很大發展,由于在許多重要領域獲得成功應用,它受到普遍關注而成為當前十分熱門的研究領域。1GA的基本概念遺

2、傳算法,有的作者譯為基因算法1,是一種模擬自然選擇和遺傳機制的尋優程序,它是60年代中期美國密執安大學Ho lland J H教授首先提出2并隨后主要由他和他的一批學生發展起來的。把計算機科學與進化論撮合到一塊的最初嘗試是在50年代末60年代初。但由于過分依賴突變(m u tati on而不是配對(m ating來產生新的基因,所以收效甚微。Ho lland的功績在于開發一種既可描述交換也可描述突變的編碼技術,這是最早的遺傳算法,文獻中現在把它稱為簡單遺傳算法(Si m p le GA,SGA。一般的遺傳算法由四個部分組成:編碼機制、控制參數、適應度函數、遺傳算子。編碼機制(encoding

3、m echan is m這是GA的基礎。GA不是對研究對象直接進行討論,而是通過某種編碼機制把對象統一賦于由特定符號(字母按一定順序排成的串(string。正如研究生物遺傳,是從染色體著手,染色體則是由基因排成的串。在SGA,字符集由0與1組成,碼為二元串。對一般的GA,自然可不受此限制。串的集合構成總體,個體就是串。對GA的碼可以有十分廣泛的理解。在優化問題,一個串對應于一個可能解;在分類問題,串可解釋為一個規則,即串的前半部為輸入或前件,后半部為輸出或后件、結論,等等。這也正是GA有廣泛應用的重要原因。適應度函數(fitness functi on優勝劣敗是自然進化的原則。優、劣要有標準。

4、在GA,國務院僑辦重點學科科研基金資助項目。本文1996年1月16日收到。用適應度函數描述每一個體的適宜程度。對優化問題,適應度函數就是目標函數。引進適應度函數的目的在于可根據其適應度對個體進行評估比較,定出優劣程度。為方便起見,在SGA,適應度函數的值域常取為0,1。遺傳算子(genetic op erato r最重要的算子有三種:選擇(selecti on、交換(cro ssover、突變(m u tati on。選擇算子也稱復制(rep roducti on算子。它的作用在于根據個體的優劣程度決定它在下一代是被淘汰還是被復制。一般地說,通過選擇,將使適應度即優良的個體有較大的存在機會,而

5、適應度小即低劣的個體繼續存在的機會也較小。有很多方式可以實現有效的選擇。例如,兩兩對比的方式,即隨機從父代抽取一對個體進行比較,較好的個體在下一代將被復制繼續存在。SGA采取的則是按比例選擇的模式,即適應度為f i的個體以f i f k的概率繼續存在,其中分母為父代中所有個體適應度之和。如果只有選擇算子,GA不會有什么新意。因為后代的群體不會超出初始群體即第一代的范圍。因此,還需要一些更合理的算子。常用的有交換和突變。交換算子有多種形式,最簡單的是所謂的單點交換(sing leopo in t cro ssover,這也是SGA使用的交換算子,即從群體中隨機取出兩個字符串,設串長為L,隨機確定

6、交叉點,它在1到L-1間的正整數取值。于是,將兩個串的右半段互換再重新連接得到兩個新串。當然,得到的新串不一定都能保留在下一代,需和原來的串(親本進行比較,保留適應度大的兩個,如圖1所示。000010交叉點1 00000000000交叉點100010圖1單點交換進行交換后,可進行突變。突變算子是改變字符串的某個位置上的字符。在SGA,即為0與1互換:0突變為1,1突變為0,如圖2所示。一般認為,突變算子重要性次于交換算子,但其作用也不能忽視。例如,若在某個位置上,初始群體所有串都取0,但最優解在這個位置上卻取1,于是只通過交換達不到1而突變則可做到。控制參數(con tro l param e

7、ters在GA 的實際操作時,需適當確定某些參數的值以提高選優的效果。這些參數是字符串所含字符的個數,即串長。在SGA,這一長度為常數,即為定長,記為L;000010001010圖2突變每一代群體的大小,即所包含字符串的個數,也稱群體的容量,記為n;交換率(cro ssover rare,即施行交換算子的概率,記為P c;突變率(m u tati on rate,即施行突變算子的概率,記為Pm。在SGA,若群體容量較大,如n=100,通常取P c=0.6,Pm=0.001;若群體容量較小,如n=30,通過取P c=0.9。Pm=0.01。此外還有遺傳的“代”數,或其他可供確定中止繁殖的指標,等

8、等。為具體理解GA的思想,現以一個可用手算求解的簡例說明。此例取自GA一本著名的2工程數學學報第16卷教材3。例求函數f (x =x 2的最大值,變量x 在0與31之間的整數取值。解為用SGA 解此問題,容易想到將決策變量x 取的值以二進位數表示從而得到一種自然的編碼;每一個體均為長度是5的二進制位串。初始群體的容量取4。于是,從總體中隨機抽取4個個體組成第一代群體,即初始群體。具體操作可通過擲硬幣確定。例如,將一枚硬幣連續擲20次,或指定了順序的5枚硬幣各擲4次,正面為1,反面為0,得4個5位二進制字符串,不妨記為(01101、(11000、(01000、(10011。SGA 采取按適應度大

9、小比例進行選擇的機制,則可用專門設計的簡易輪盤來決定第一代群體中哪個個體能被保留。結果如表1所示。表1第一代群體的選擇串N o.1初始群體(隨機生成xf (x =x 2f f nf f 實際生存數(由輪盤決定101101131690.1440.5761211000245760.4921.96823010008640.0550.2200410011193610.3091.2361和11701.0004.0004平均2930.2501.0001m ax 5760.4921.9682交換率取為1,即肯定施行交換算子。同樣,可通過擲硬幣的方法將復制出的4個串配成兩對并隨機確定交叉點進行交換,結果如表2

10、。表2交換的進行交換后的配對(豎線為交換點的位置配對(隨機選擇交叉點(隨機選擇新種群x f (x =x 20110110011110000011240110012141100125421101127321000016144625729256和1754平均439m ax729突變率取為0.001,這意味著每1000位平均有一位產生突變。本例的群體只包含4個5位的字符串共20位,平均只有0.02個位產生突變,可認為實際上不產生突變。于是,經過選擇、交換完成了一代的遺傳。事實證明,第二代群體的質量有了明顯的提高,平均適應度由293增加為439,最大適應度由576增加到729。2應用GA 最直接的應用

11、或許就是多元函數的優化問題。如果函數表達式是清楚的,又具有良好的分析性質,自然用不著GA 。但若所討論的函數受到嚴重的噪聲干擾而呈現出非常不規則的形狀,同時所求的也不一定非是精密的最大(小值,則GA 就可以找到它的應用。3第1期任平:遺傳算法(綜述4工程數學學報第16卷一般說來,在一些實際問題中應用GA時,首先要解決兩個問題:(1編碼的設計;(2適應度函數的確定。對函數優化問題,這兩個問題乍一看來都比較容易解決。特別是,有現成的二進位制可將變量取的值編為二元的位串,很是方便。實際不然。因為對一般的二進位制,有時增加1,需要改變所有的位元,如011為十進制的3,而4為100,這就造成困難。為此,

12、設計了一種所謂的“灰碼”(gray codes。這種碼的特點是增加或減少1都只需要改動一個位元。當然,根據不同需要還可設計各種不同的碼。這在包括飛機設計、信號檢測以至非線性差分方程組穩定域的確定等近百種問題中有廣泛應用。關于這方面的情況可參閱文3表4.4所列舉的項目。GA另一個十分引入注目的應用領域是機器學習。這是因為,與傳統的優化技術比較, GA的特點在于1GA的工作對象不是決策變量本身,而是將有關變量進行編碼所得的碼,即位串;2傳統的尋優技術都是從一個初始點出發,再逐步迭代以求最優解。GA則不然,它是從點的一個群體出發經過代代相傳求得滿意解;3GA只充分利用適應度函數(目標函數的信息而完全

13、不依靠其它補充知識;4GA的操作規則是概率性的而非確定性的。這就表明,GA較為適合于維數很高、總體很大、環境復雜、問題結構不十分清楚的場合,機器學習就屬這類情況。一般的學習系統要求具有隨時間推移逐步調整有關參數或者改變自身結構以更加適應其環境,更好完成目標的能力。由于其多樣性與復雜性,通常難以建立完善的理論以指導整個學習過程,從而使傳統尋優技術的應用受到限制,而這恰好能使GA發揮其長處。關于GA在機器學習中的應用,Jong K D e在文4中有很好的綜述。有時,問題的數學結構十分清楚,但由于某些原因,如維數太高或計算量太大,依靠傳統方法實際上難以求解。運籌學中許多排序問題,如旅行商問題、工序安

14、排、設備布置等都屬此類。GA在這方面也有大量工作。以旅行商問題為例:設有幾個城市,則很自然會把旅行方式編為n個正整數1,2,n的一個排列;但是,這種編碼不適用于GA,因為交換算子作用于兩個排列所得的結果有時是沒有意義的。為克服這個困難,或是要設計新的編碼規則;或是要適當修改原有的交換算子。對這方面工作的評述。可參閱文5。GA在這一領域中的應用,引起運籌學界的重視:1995年,國際運籌學專業期刊Com pu ters&Op erati on R esearch以GA為主題編發了一期特刊6,組織了包括四個方面內容的12篇論文。期刊主編R aff S J 在特刊前言中把GA稱為“對當前運籌學

15、有巨大興趣的課題。”這一點決非偶然,進入70年代后期,運籌學面臨新的挑戰7,由于研究工作過分“學院化”,使理論發展在一定程度上與實際脫節。原來生氣勃勃的運籌學出現了沉悶的局面;另一方面,計算技術、控制技術的智能化趨勢已不能滿足于傳統優化方法的框架;特別是,傳統運籌學理論缺乏對變動環境的適應性,“造成最優解維持最優的壽命在很多情況下甚至比求解所耗費的時間還要來得短”。因此,GA的崛起,對運籌學無疑是一個有力的推動。在復雜性問題的研究中,GA也嶄露頭角,倍受青睞。什么叫復雜性問題,各家看法不一。共同認識還是有的,即復雜性問題應是多層次、多因素,其相互作用是非線性、不確定和不穩定的,這樣的學習問題自

16、然屬復雜性研究的范疇。事實上,在復雜系統例如適應性系統學習策略的研究中,GA占重要地位8。另一個典型例子是地震數據反演問題9:由于介質參數的模型非常大,同時觀測數據不完備、噪音的存在、源的情況復雜且未知,很難用傳統的方法求得目標函數的全局最優值,而只能求一定意義下的“滿意解”。這時,可供選擇的方法之一自然是GA 。值得注意的是,近年來,GA 在商業應用方面取得一系列重要成果。或許這也是它受到學術界之外的企業界、政府部門以及更廣泛的社會階層普遍重視的原因。GA 的商業應用五花八門,覆蓋面甚廣,Co ldbo rg 在Comm.A C M 上的一篇專論10較為詳細地介紹了美國近年來的一些成果。例如

17、,通用電器的計算機輔助設計系統Engeneou s,這是一個混合系統(hyb rid system ,采用了GA 以及其他傳統的優化技術做為尋優手段。Engeneou s 已成功地應用于汽輪機設計,并改善了新的波音777發動機的性能。美國新墨西哥州州立大學心理學系開發了一個所謂的Facep rin t 系統,可根據目擊者的印象通過計算機生成嫌疑犯的面貌。計算機在屏幕上顯示出20種面孔,目擊者按十分制給這些面孔評分。在這基礎上,GA 按通常的選擇、交換和突變算子生成新的面孔。Facep rin t 的效果很好,已申報專利。同一個州的一家企業預測公司(P redicti on Com pany 則

18、首先開發了一組用于金融交易的時間序列預測和交易工具,其中GA 起了重要作用:據說,這一系統實際運行效果很好,可以達到最好的交易員的水平,引起銀行界的關注。GA 在軍事上的應用也有報道:如用于紅外線圖象目標判別的休斯遺傳程序系統(H ughes genetic p rogramm ing system ,效果很好,以至準備把它固化成硬件。在GA 的應用研究和推廣普及中,相應的程序環境的開發占有重要地位。文11將GA 程序環境(GA P rogramm ing Environm en ts 區分為三類:面向應用系統,面向算法系統以及工具。表3列出了文11所評價的一些系統,文中并附有系統開發者的聯系

19、地址。表3文11所列GA 程序的分類面向應用系統面向算法系統特定算法系統算法庫工具教育系統通用系統Evo lverE scap ade E M GA W o rkbench Engeneer Om egaGA GA GAM E Pc BeagelGAU CSD M icro GA Xp ert R u leGenesis OO GA Pegasu s GenA sys Gen ito r Sp licer例如,Sp licer 為NA SA 約翰遜航天中心信息系統理事會軟件技術部研制的,是當時最完備的一種通用系統。它由三個部分構成:GA 核、可交換表現庫和適應度模塊;有兩個用戶界面庫,一對M

20、acin to shes,一對X w indow s 。當用戶使用Sp licer 解某個具體問題時,只要用C 構造一個適應度模塊而無需其他編程工作。為大力推廣GA ,NA SA 以及政府項目承擔者可免費使用Sp eicer 1.0版本。這些系統的研制開發和推廣使用,對GA 在美國的發展無疑起著積極推動作用。3GA 的理論基礎GA 在應用上確已取得顯著成功,但其基礎研究相對來說卻比較薄弱。就目前情況看,能稱得上為理論成果的只有所謂的型式定理2(Sehem a T heo rem 。型式(schem a 是在某些確定位置上取相同字符的字符串集合。例如,在SGA ,形式5第1期任平:遺傳算法(綜述

21、6 工程數學學報第 16 卷 3 3 000 表示后三個位置都取 0 的字符串的集合, 即00000, 01000, 10000, 11000; 類似地, 103 03 表示 10000, 10001, 10100, 10101。 因此, 可以直觀地把型式看成一個相似性模板 ( sim ila rity tem p la te , 在對應的確定位置, 0 和 0 匹配, 1 和 1 匹配, 3 為通配符, 可和 0、 兩 1 者匹配。 型式表示的就是和它匹配的字符串。 這些字符串稱為型式的實現 ( in stance 或解 ( so lu tion 。 在某個型式中, 確定字符的個數稱為型式的

22、階 (o rder , 其最左端確定字符到最 右 端確定字符間的距離稱為型式的定義長度 ( defin ing leng th , 例如, 型式 3 3 000 的階是 3, 定義長度是 5 - 3 = 2, 型式 103 03 的階的 3, 定義長度是 4 - 1 = 3 (H : H 的定義長度; 0 (H : H 的階。 先考慮選擇的效果。 SGA , 選擇標準是采用按適應度大小比例的原則, 因此, 第 i 個體 在 經選擇算子的作用在下一代繼續存在的個數的期望值為 n ( f i f , 注意到 1 f (H , t = ( f i n H , t 則 n (H , t + 1 = n

23、 (H , t. f (H , t f ( t 上述等式表明, 選擇算子的作用將使適應度高于 ( 低于 平均水平的型式在代代相傳時增大 ( 減小 其容量, 從而提高群體的質素。 綜合考慮選擇和交換的作用則有 n (H , t + 1 n (H , t f (H , t 1 - P c (H (L - 1 f ( t 最后, 由于 Pm 表示突變算子作用的概率, 不變的概率為 1 - Pm , 若所有確定字符都不 變, 型式 H 在下一代自然能繼續存在, 概率為 ( 1 - Pm O (H , Pm 通常很小, Pm 1, 則經過 突變算子作用后, H 繼續存在的概率為 ( ( 1 - Pm O

24、 H 1 - Pm o (H 被淘汰的概率近似地為 o (H Pm 。 于是, 綜合考慮選擇, 交換和突變算子的作用, 最后有 (H n (H , t + 1 n (H , t f (H , t 1 - P c - o (H Pm f ( t L - 1 這就是所謂的型式定理, 也稱 GA 的基本定理。 型式定理表明, 如果只考慮選擇算子的影響, 某個型式所含解的個數隨同群體代代相傳而遞增或減少與型式的平均適應度大小有關。 特 (H , t = f ( t ( 1 + c , c > 0 為常數, 則 別地, 若有 f n (H , t = n (H , t - 1 ( 1 + c =

25、n (H , 0 ( 1 + c t 現在分析交換算子的作用。 若不進行交換或雖交換但交叉點落在型式最左、 右兩端確定 字符所處位置之外, 該型式在下一代顯然能被保留。 于是, 型式 H 在下一代得以繼續存在的 概率 P s 應滿足。 P s 1 - P c (H (L - 1 為簡便起見, 只就 SGA 進行討論。 引入下列符號 H : 某個型式; f i: 第 i 個字符串 ( 解、 實現 的適應度; ( t : 第 t 代群體的平均適應度; f f (H , t : 型式 H 在第 t 代群體的平均適應度; n i (H , t + 1 : 由 ( 第 t 代 型式 H 的某個解 i 在

26、第 t + 1 代生成的后代數的期望值; n (H , t : 第 t 代屬于型式 H 的解的個數; 第 1 期任平: 遺傳算法 ( 綜述 7 即高平均適應度的型式在與其它型式的競爭中其容量呈指數增長。 然而, 只是高平均適應度 還 不足以保證高的成長率。 當綜合考慮其它算子影響時, 要求優良的型式的定義長度應較 短、 階數應較低。 高平均適應度、 短定義長度和低階數的型式在群體代代相傳中其所含解的 個數是指數增長, 正是型式定理的本質。 但是, 低階數意味著較大的搜索空間, 這對尋優自然是不利的。 的實踐表明, GA 的 GA 威力不僅僅在于開始時能將搜索方向引導到高適應度低階數的型式, 隨

27、后, 還能利用交換算 子將低階型式的信息組合成高階型式, 從而最后收斂于高適應高階數、 即較小的搜索空間。 這一 事 實 并 非 普 遍 成 立, 但 確 實 是 非 常 重 要, 被 稱 為 建 筑 塊 假 設 ( bu ild ing b lock s hypo lhesis 。 有趣的是, 建筑塊假設揭露了 GA 的工作方式和傅立葉分析之間的某些相似之 處。特別是, B ethke 提出了所謂的 W a lsh 2 型式交換, 并用它有效地計算型式的平均適應 度 12 。 這方面的進一步工作可參看文 5 所介紹的文獻。 4 展 望 GA 在應用方面取得的豐碩成果, 使人們對它的發展前景充

28、滿信心。 認識到這一點, GA 的奠基人之一, Go ld sberg D 戲言 10 :“已不再需要水晶球” 。 今后幾年, 可以預期, 拓廣更加多樣的應用領域, 其中包括各種 GA 程序設計環境的開 發, 仍將是 GA 發展的主流。 事實上這也是本世紀高新技術迅速發展帶有規律性的特點, 即 面向應用。 與此同時, 這并不意味著理論研究會被忽視, 這方面同樣有大量工作要做。 例如: 控制參數的選擇; 交換和突變這兩類最重要的算子的確切作用; 并行 GA 和分布式 GA 的研究; 其他類型生物機制的模仿, 如免疫、 病毒、 寄生等, 以豐富 GA 的內容, 等等。 自然, 不論從理論還是應用的

29、角度看, 最緊迫的應是關于算法收斂性問題的研究, 特別 是過早收斂的防止。 這對 GA 的實際應用關系重大。 當 前一個特別值得重視的趨勢是一些面向對象的智能技術, 其中主要是模糊邏輯 ( Fuzzy L og ic, FL , 神經網絡 (N eu ra l N etw o rk, NN 以及 GA 等的綜合應用。 眾所周知, FL 有較強的知識表達能力, NN 的長處在于自學習, 它們與 GA 相結合形成新的集成化技 術, 即所謂的混合智能系統 (H yb rid In tellectua l System 。 這一思想在 90 年代初逐步形成, 而由模糊集論的創始人, 美國 Zadeh

30、L A 在 1993 年于漢城召開的國際模糊系統協會 ( IFSA 第五屆世界會議首先明確提出 13 , 隨后在許多有關的國際學術會議上得到充分體現。 應該 指出, 我國學者對這一趨勢的認識較早。 例如, 清華大學李衍達院士領導的研究集體在幾乎 14 同一時期開展了這一重要方向的研究 。 1995 年, Zadeh 在 IFSA 的第六屆世界會議上再次 強調了這一方向的重要性, 并且認為上述所謂的混合智能系統的應用將覆蓋從消費品生產 到核反應堆設計以至證券管理, 而 “在未來幾年中可能無處不在” 15 。 就 GA 本身的研究而言, 應該說, 我國起步較晚, 近幾年才陸續看到一些介紹性的文章、

31、 不多于兩三部的專著以及初步的研究報告。 和國外工作比較, 一個顯著區別是, 國內工作多 只停留在論文這一層次, 幾乎沒有看到具體實際應用, 與研究成果商品化的差距就更遠。 理 論研究與實際應用不夠緊密, 阻礙了我國高新技術的迅速發展, 幾乎已經成為頑癥。 因此, 在 我國發展 GA , 當前應該特別重視它的應用和推廣普及。 學術界要主動和企業界連手開發 8 工程數學學報第 16 卷 GA 的應用, 要重視引進或自行研制類似于 Sp licer 的程序設計環境, 使 GA 的應用更加方便 和快捷。 國家組建的工程研究中心應該在這方面發揮更大的作用。 工科數學教育也應有所調 整, 以適應高新技術

32、發展的需要。 例如, 工科運籌學和最優化方法的課程應該適當加入有關 GA 等方面的內容, 以開闊學生的視野, 同時也有利于加快傳統課程內容的更新。 參考文獻 1Ho lland J H. 基因算法. 科學, 1992; 11: 24 31 2Ho lland J H. A dap ta tion in na tu ra l and a rtificia l system s U n iv of M ich igan P ress, A nn A rbo r M ich, . 1975 3 Go ldberg D E. Genetic a lgo rithm s in sea rch. O p

33、ti iza tion and M ach ine L ea rn ing, A dd ison 2 esley, m W R ead ing, M a ss, 1989 4D e Jong K A. L ea rn ing w ith genetic a lgo rithm s: an overview. M ach ine lea rn ing 3, K luw er A cdem ic, H ingham , M a ss, 1988; 121 133 vo l 261, 872 878 5Fo rrest S. Genetic a lgo rithm s: p rincip les of na tu ra l seclection app lied to com p u ta tion. Science, 1993; 6Com p u ter & op era tion