遺傳算法理論及技術(shù)研究綜述

1、軟件縱橫 計算機與信息技術(shù) ·37·遺傳算法理論及技術(shù)研究綜述周昕 凌興宏(1. 哈爾濱理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150080;2. 蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,江蘇 蘇州 215006摘 要 本文首先闡述了遺傳算法的主要特點和基本原理,隨后對遺傳算法的理論與技術(shù)研究的主體,即編碼機制、 適應(yīng)度評價以及選擇、交叉、變異等遺傳算子進行了探討;比較分析了各種遺傳操作方法的優(yōu)缺點和適用場合;對遺傳算法 的理論和技術(shù)做了初步研究綜述。關(guān)鍵詞 遺傳算法;編碼機制;遺傳算子;適應(yīng)度評價1 引言遺傳算法是模擬遺傳選擇和自然淘汰的生物進化過程的 計算模型, 由美國

2、 Michigan 大學(xué)的 Holland 教授于 1969年提 出,后經(jīng) DeJong、Goldberg 等人歸納總結(jié),形成一種新的全 局優(yōu)化搜索算法 1。所謂遺傳算法來源于達爾文的進化論、魏茨曼的物種選 擇學(xué)說和孟德爾的群體遺傳學(xué)說。遺傳算法是模擬自然界生 物進化過程與機制求解極值問題的一類自組織、自適應(yīng)人工 智能技術(shù) 2 ,其基本思想是模擬自然界遺傳機制和生物進化 論,引用了隨機統(tǒng)計理論而形成的。在求解過程中,遺傳算 法從一個初始變量群體開始, 一代一代地尋找問題的最優(yōu)解, 直至滿足收斂判據(jù)或預(yù)先設(shè)定的迭代次數(shù)為止。它是一種迭 代式算法,是一種過程搜索最優(yōu)解的算法,具有堅實的生物 學(xué)基礎(chǔ)

3、。遺傳算法廣泛應(yīng)用于自動控制、計算科學(xué)、模式識別、 工程設(shè)計、智能故障診斷、管理科學(xué)和社會科學(xué)等領(lǐng)域,適 用于解決復(fù)雜的非線性和多維空間尋優(yōu)問題。2 遺傳算法的基本原理及特點2.1 遺傳算法的基本原理遺傳算法是一種基于自然選擇和群體遺傳機理的搜索算 法,它模擬了自然選擇和自然遺傳過程中發(fā)生的繁殖、雜交 和突變現(xiàn)象。在利用遺傳算法求解問題時,問題的每個可能 的解都被編碼成一個“染色體”,即個體,若干個個體構(gòu)成 了群體(所有可能解,通過適應(yīng)度函數(shù)給每個個體一個數(shù) 值評價,淘汰低適應(yīng)度的個體,選擇高適應(yīng)度的個體參加遺 傳操作,這些個體經(jīng)過交叉和變異算子進行再組合生成下一 代新的種群。這一群新個體由于

4、繼承了上一代的一些優(yōu)良性 狀,因而在性能上要優(yōu)于上一代,這樣逐步朝著更優(yōu)解的方 向進化。因此,遺傳算法可以看作是一個由可行解組成的群 體逐代進化的過程。 3遺傳算法的基本流程描述如圖1所示。 圖 1 遺傳算法基本流程2.2 遺傳算法的特點遺傳算法利用了生物進化和遺傳的思想, 不同于枚舉法、 啟發(fā)式算法、搜索算法等傳統(tǒng)的優(yōu)化方法,具有如下特點 4: (1自組織、自適應(yīng)和智能性。遺傳算法消除了算法設(shè) 計中最大的障礙,即需要事先描述問題的全部特點,并說明 針對問題的不同特點,算法應(yīng)采取的措施。直接處理的對象 是參數(shù)編碼集,而不是問題參數(shù)本身。它可用來解決復(fù)雜的 非結(jié)構(gòu)化問題,具有很強的魯棒性。(2搜

5、索過程中使用的是基于目標(biāo)函數(shù)值的評價信息, 搜索過程既不受優(yōu)化函數(shù)連續(xù)性的約束,也沒有優(yōu)化函數(shù)必 須可導(dǎo)的要求。·38· 計算機與信息技術(shù) 軟件縱橫(3 易于并行化, 可降低由于使用超強計算機硬件所帶 來的昂貴費用。(4 算法基本思想簡單,運行方式和實現(xiàn)步驟規(guī)范, 便于具體使用。3 遺傳算法的理論與技術(shù)研究遺傳算法的研究主要包括三個領(lǐng)域 5 :遺傳算法的理論 與技術(shù);用遺傳算法進行優(yōu)化;用遺傳算法進行分類系統(tǒng)的 機器學(xué)習(xí)。 其中, 遺傳算法的理論與技術(shù)研究主要包括編碼、 交叉運算、變異運算、選擇運算以及適應(yīng)度評價等問題。本 文限于篇幅,僅就遺傳算法的理論與技術(shù)研究進行探討。

6、 3.1 編碼機制在許多問題求解中,編碼是遺傳算法中首要解決的問題, 對算法的性能有很重要的影響。 常見的編碼方法有如下幾種 6:1 二進制編碼由Holland最初提出,遺傳算法中最常用的一種編碼方 法。 它采用最小字符編碼原則, 特點是編/解碼操作簡單易行, 利于交叉、變異操作的實現(xiàn),也可以采用模式定理對算法進 行理論分析。但二進制編碼用于多維、高精度數(shù)值問題優(yōu)化 時,不能很好地克服連續(xù)函數(shù)離散化時的映射誤差;不能直 接反映問題的固有結(jié)構(gòu),精度不高,個體長度大、占用內(nèi)存 多。2 格雷碼編碼為了克服二進制編碼在連續(xù)函數(shù)離散化時存在的不足, 人們提出了用格雷碼進行編碼的方法,它是二進制編碼的變

7、形。 假設(shè)有一個二進制編碼為 121-m m x x x x X =, 其對應(yīng)的 格雷碼為 121-m m y y y y Y =,則=+i 1i i mm x x y x y i=m-1,m-2,2,1格雷碼不僅具有二進制編碼的一些優(yōu)點,而且能夠提高 遺傳算法的局部搜索能力。3 編碼該方法適合于遺傳算法中表示范圍較大的數(shù),使遺傳算 法更接近問題空間,避免了編碼和解碼的過程。它便于較大 空間的遺傳搜索,提高了遺傳算法的精度要求;便于設(shè)計專 門問題的遺傳算子;便于算法與經(jīng)典優(yōu)化方法的混合作用, 改善了遺傳算法的計算復(fù)雜性,提高了運算效率。4 十進制編碼該方法利用十進制編碼控制參數(shù),緩解了“組合爆

8、炸” 和遺傳算法的早熟收斂問題。5 符號編碼染色體編碼串中的基因值取一個僅有代碼含義而無數(shù)值含義的符號集,這些符號可以是數(shù)字也可以是字符。非數(shù)值 編碼的優(yōu)點是在遺傳算法中可以利用所求問題的專門知識及 相關(guān)算法。對于非數(shù)值編碼,問題的解和染色體的編碼要注 意染色體的可行性、染色體的合法性和映射的惟一性。符號 編碼的主要優(yōu)點是便于在遺傳算法中利用所求問題的專門知 識及相關(guān)算法。 3.2 適應(yīng)度函數(shù)遺傳算法在進化搜索中基本上不利用外部信息,僅以適 應(yīng)函數(shù)為依據(jù), 利用群體中每個個體的適應(yīng)度值來進行搜索。 因此適應(yīng)函數(shù)的選取至關(guān)重要,直接影響遺傳算法的收斂速 度以及能否找到最優(yōu)解。 7在遺傳算法中,適

9、應(yīng)度是描述個體性能的主要指標(biāo),根 據(jù)適應(yīng)度的大小對個體進行優(yōu)勝劣汰。對于求解有約束的優(yōu) 化問題時,一般采用罰函數(shù)方法將目標(biāo)函數(shù)和約束條件建立 成一個無約束的優(yōu)化目標(biāo)函數(shù),然后再將目標(biāo)函數(shù)作適當(dāng)處 理,建立適合遺傳算法的適應(yīng)度函數(shù)。將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度函數(shù)一般應(yīng)遵循兩個原則: (1 適應(yīng)度必須非負(fù)。(2 優(yōu)化過程中目標(biāo)函數(shù)的變化方向應(yīng)與群體進化過 程中適應(yīng)度函數(shù)變化方向一致。在使用遺傳算法求解具體問題時,適應(yīng)度函數(shù)的選擇對 算法的收斂性以及收斂速度的影響較大,針對不同的問題需 根據(jù)經(jīng)驗或算法來確定相應(yīng)的參數(shù)。 3.3 遺傳操作遺傳操作的任務(wù)是根據(jù)個體的適應(yīng)度對其施加一定的操 作, 從而實現(xiàn)優(yōu)勝

10、劣汰的進化過程。 從優(yōu)化搜索的角度而言, 遺傳操作可使問題的解逐代地優(yōu)化,逼近最優(yōu)解。選擇是在適應(yīng)度評估的基礎(chǔ)上,從群體中選擇優(yōu)良的個 體,并淘汰劣質(zhì)個體的操作。適應(yīng)度越大的個體,被選擇的 可能性就越大。常用的選擇方法有: 1 輪盤賭選擇法又稱為適應(yīng)度比例法,是目前遺傳算法中最基本也是最 常用的選擇方法。個體的適應(yīng)度值越大,它被選中的概率就 越高,體現(xiàn)了“適者生存”這一自然選擇原理。被選中的個 體被放入配對庫中,隨機地進行配對,以進行下面的交叉操 作。2局部選擇法在局部選擇法中,每個個體處于一個約束環(huán)境中,稱為 局部鄰集(而其它選擇方法中視整個種群為個體之鄰集, 個體僅與其臨近個體產(chǎn)生交叉,該

11、鄰集的定義由種群的分布 結(jié)構(gòu)給出,鄰集可被當(dāng)作潛在的交配伙伴。3 最佳個體保存法把群體中適應(yīng)度最高的個體不進行配對交叉而直接復(fù)制 到下一代。這樣做的好處是保證了進化過程中某一代的最優(yōu) 解不被交叉和變異操作所破壞。但會使局部最優(yōu)的遺傳基因 急速增加,而使進化停滯于局部最優(yōu)解,即這種方法影響了 遺傳算法的全局搜索能力。因此,最佳個體保存法通常不單 獨使用。4 競爭法個體的選擇公式為f m = maxf i, f j,即隨機地選取兩 個個體,對其適應(yīng)值進行比較,大的被選中,小的被自然淘 汰;如果兩個個體的適應(yīng)值相同,則任意選取其中的一個。 被選中的個體放入配對庫中。重復(fù)此過程,直至配對庫中包 含N

12、個個體為止。這種方法既保證了配對庫中的個體在解空 間中有較好的分散性,同時又保證了加入配對庫中的個體具 有較大的適應(yīng)值。5 排序選擇法首先根據(jù)各個體的適應(yīng)度大小進行排序,然后基于所排 序號進行選擇。交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生 成新個體的操作。交叉的目的是為了能夠在下一代產(chǎn)生新的 個體,就象人類社會的婚姻過程。通過交叉操作,遺傳算法 的搜索能力得以飛躍性的提高。交叉是遺傳算法獲取新優(yōu)良 個體的最重要手段。交叉操作是按照一定的交叉概率(也稱交叉率在配對 庫中隨機地選取兩個個體進行的。交叉的位置也是隨機確定 的。交叉算子分為以下幾種:1 單點交叉又簡稱為簡單交叉,即在個體串中隨

13、機地選定一個交叉 點, 兩個個體在該點前或后進行部分互換, 以產(chǎn)生新的個體。 2 多點交叉多個個體無重復(fù)隨機地選擇,在交叉點之間的變量間續(xù) 地相互交換,產(chǎn)生兩個新的后代。3 均勻交叉是通過設(shè)置屏蔽字來決定新個體的基因如何繼承父代個 體中相應(yīng)的基因。變異就是以很小的變異概率Pm隨機地改變?nèi)后w中個體 的某些基因的值。變異操作的基本過程是:對于交叉操作中 產(chǎn)生的后代個體的每一基因值, 產(chǎn)生一個 0, 1 之間的偽隨 機數(shù)rand,如果rand < Pm,就進行變異操作。變異本身是一種局部隨機搜索,與選擇、交叉算子結(jié)合 在一起,就能避免由于選擇和交叉算子而引起的某些信息的 永久性丟失,保證了遺傳

14、算法的有效性,使遺傳算法具有局 部的隨機搜索能力;同時使得遺傳算法保持群體的多樣性, 以防止出現(xiàn)未成熟收斂。因此,變異操作是一種防止算法早 熟的措施。幾種常用的變異操作如下:1基本位變異對個體編碼串以變異概率Pm隨機指定某一位或某幾位 基因進行變異操作。2均勻變異也叫一致變異,分別用符合某一范圍內(nèi)均勻分布的隨機 數(shù),以某一較小的概率來替換個體編碼串中原有基因值。均 勻變異操作特別適合應(yīng)用于遺傳算法的初期運行階段,它使 得搜索點可以在整個搜索空間內(nèi)自由地移動,從而可以增加 群體的多樣性,使算法能夠處理更多的模式。3二元變異需要兩條染色體參與,通過二元變異操作后生成兩條新 個體中的各個基因分別取原

15、染色體對應(yīng)基因值的同或/異或。 它改變了傳統(tǒng)的變異方式,有效地克服了早熟收斂,提高了 遺傳算法的優(yōu)化速度。4高斯變異在進行變異時用一個均值為、 方差為2的正態(tài)分布的 一個隨機數(shù)來替換原有基因值。 其操作過程與均勻變異類似。 4 結(jié)束語遺傳算法的理論與技術(shù)研究主要包括編碼、交叉運算、 變異運算、選擇運算等遺傳操作以及適應(yīng)度評價等問題。本 文就遺傳算法的理論與技術(shù)研究的諸方面進行了探討。 遺傳算法是一個十分活躍的研究領(lǐng)域,遺傳算法的研究 正在從理論的深度、技術(shù)的多樣化以及應(yīng)用的廣度不斷地探 索,朝著計算機擁有甚至超過人類智能的方向努力。參考文獻1 HOLLAND J H. Adap tation

16、in natural and artificial systems M .Ann Arbor: University ofMichigan Press, 1975 2 張文修,梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)M .西安:西 安交通大學(xué)出版社,2000(下轉(zhuǎn)第 43頁換。算法 2:設(shè)計 GF (28 上的 4×4級的 Hadamard MDS矩 陣。Step1、 從 有 限 域 (82GF 中 選 取 4個 非 零 元 素0123, , , i i i i a a a a 且滿足 222201231i i i i a a a a +=;Step2、生成 Hadamard 矩陣 01231032

17、23013210i i i i i i i i i i i i i i i i a a a a a a a a H a a a a a a a a =; Step3、 驗證 H 是否為 MDS 矩陣; 如果 H 為 MDS 矩陣,則輸出 H ;否則返回 Step1重新選取。在 有 限 域GF (28 (生 成 多 項 式 為(8651p x x x x x =+上,我們通過編程生成了若干個4×4的自對偶的 MDS 矩陣,列舉 3個如下:=, 13473174247137431H =251H =。 參考文獻1 Biham E. Shamir A. Differential crypta

18、nalysis of DES-like CryptosystemsJ. Journal of Cryptology. 1991(4 : 3-722 Lai X, Massey J L, Murphy S. Markov Ciphers and DifferentialCryptanalysisC.AdvancesinCryptology-Eurocrypt, 91, LNCS 547. 1991. 17-383 Masayuki Kanda , Youichi Takashima , Tsutomu Matsumoto, et al. A Strategy for constructing Fast Round Functions with Practical Security Against Differential and Linear Cryptanalysis, SAC98, LNCS 1556. 1999. 264-2794 Bon Wook Koo, Hwan Seok Jang, and Jung Hwan Song,Constructin