改進的遺傳算法在優化BP網絡權值中的應用

姚明海

1.渤海大學信息科學與技術學院，遼寧錦州 121013

2.東北師范大學數學與統計學院，長春 130024

改進的遺傳算法在優化BP網絡權值中的應用

姚明海

1.渤海大學信息科學與技術學院，遼寧錦州 121013

2.東北師范大學數學與統計學院，長春 130024

神經網絡是隨著神經生物學的發展而發展起來的一個領域，人工神經網絡（Artificial Neural Network，ANN）是在人類對其大腦神經網絡認識理解的基礎上構造的能夠實現某種功能的神經網絡。由于人工神經網絡具有高度的并行性、分布式存儲、自適應學習能力等特點，已經廣泛應用于模式識別、人工智能、預測、評價、信號處理及非線性控制等領域[1-3]。其中以BP神經網絡的應用最為廣泛。BP神經網絡具有網絡結構簡單、工作狀態穩定及自學習能力等優點。盡管如此，仍然存在著一些問題。如學習算法的收斂速度慢、易陷入局部極小值等問題。而遺傳算法恰恰能夠解決這些問題。遺傳算法既可以避免陷入局部最小，又可以加快收斂速度。但是，以標準遺傳算法[4]、小生境遺傳算法[5]、量子遺傳算法[6]、混合遺傳算法[7]為代表的經典模型在遺傳操作方面，先通過選擇算子從父代群體P(t)中選擇出具有相同特征的染色體構成交配池，然后交配池中的染色體通過交叉操作生成新的群體P(t+1)，最后用新群體P(t+1)淘汰父代群體P(t)。也就是說，經典模型在迭代運算過程中，只有屬于同代的染色體才有可能進行交叉操作。但是，從遺傳學的角度來看，同代染色體遺傳操作產生的后代不一定就具有遺傳優勢，交叉產生的新種群中不一定有優于父代染色體群中的最優個體。相反，很可能造成算法的過早收斂。因此，本文提出新的交叉操作過程。從初始種群開始對最優的染色體進行保存，通過保存的父代最優染色體與子代進行交叉操作，然后在保存的父代最優染色體和新產生的種群中選擇最優的個體進行保存。從而保證最優染色體始終參與遺傳操作。這樣在滿足選擇算子約束的條件下，保證了遺傳操作是圍繞最優個體進行的，提高了算法的搜索速度。從實驗結果來看，同代交叉的約束條件在很多情況下會使群體的多樣性迅速降低，從而使遺傳算法過早喪失了進化的能力。而采用父代最優個體參與遺傳操作的方法很好地避免了傳統算法中存在的這些問題。

1 BP神經網絡

BP網絡是一種多層的網絡[8]，一般由一個輸入層，一個或多個隱含層（也稱中間層）和一個輸出層構成。各層之間實行全連接，同一層內的神經元無連接，圖1表示了僅具有一個隱含層的三層BP神經網絡結構圖。輸入層節點數為n，隱層節點數為l，輸出層節點數為m（各層的節點數可以根據實際樣本的情況進行設定）。輸入為X=(x1,x2,…,xn)′，輸入層到隱層的權值為W1=(w1ij)n×l，隱層閾值為B= (b1,b2,…,bl)′，隱層到輸出層的權值為W2=(w2ij)l×m，輸出層閾值為S=(s1,s2,…,sm)′，輸出為Y=(y1,y2,…,ym)′。

圖1 三層網絡結構

BP神經網絡中隱層神經元轉移函數一般有階躍函數、準線性函數、Sigmoid函數和雙正切函數等，本文采用的轉移函數為Sigmoid函數。其表達式如下：

2 改進的遺傳算法

到目前為止還沒有任何證據能證明同代遺傳比隔代遺傳更好，并且同代遺傳很容易降低種群的多樣性，使整個算法過早喪失進化能力。因此，本文提出了一種改進的遺傳算法。即：采用隔代遺傳的方式，在初始染色體池T中選擇最優染色體Tmax，然后通過Tmax與初始染色體池中的染色體進行交叉，產生新的種群。在新種群中對所有染色體進行排序，選擇最好的染色體Tmax'與Tmax進行比較，如果優于Tmax則用Tmax'替換Tmax。同時，在新的種群中選擇較好的部分生成新的染色體池T′，用T′替換原有染色體池T。在該迭代過程中要根據一定的概率對部分染色體進行變異操作。如此迭代，直到滿足結束條件為止。

2.1 染色體編碼

遺傳算法采用編碼來代替問題參數，在所有的實際問題表示方式與編碼位串之間必須構成一一對應關系，同時在運算過程需要進行多次編碼和解碼操作。針對BP神經網絡的權值優化問題，本文采用的是實數編碼的方式，對網絡中每一層的權值和閾值進行編碼。將表示BP網絡權值和閾值的多維矩陣W1,B,W2,S采用一維矩陣的形式表示，這里，染色體的每一個基因代表網絡中的一個權值或閾值。以圖1的三層網絡機構為例，其編碼形式如下：

2.2 產生初始種群和局部最優染色體Tmax

BP神經網絡的初始權值取均勻分布的(-1,1)之間的隨機數小數。染色體長度為L=W1+B+W2+S+1。每條染色體的最后一位為該染色體的適應值，在遺傳操作中，該位不參與交叉、變異等操作。這里使用初始種群函數Initalizega()來生成初始染色體池和局部最優染色體Tmax。具體函數如下：

這里T為初始染色體群，Tmax為初始染色體群T中的最優染色體，Psize為初始種群的規模，aa為染色體中每個基因的取值范圍，gabpEbal為適應度函數。

2.3 選擇算子

遺傳算法中的選擇是指在整個群體中尋找適應度較高的個體去生成初始的交配池。最常用的選擇方法有適應比例選擇、最佳保留選擇、排序選擇和期望值選擇。本文采用的是適應比例選擇，利用個體的適應值與整個群體的平均適應值的比例進行選擇。先計算群體中每個個體的適應值，然后看該適應值在總群體適應值中所占的比例，所占的比例越大被選中的概率就越大。反之，概率就越小。

對于給定的規模為n的群體P={a1,a2,…,an}，個體aj∈P的適應值為f(aj)，其選擇概率為：

2.4 適應度函數gabpEbal()

遺傳算法是通過適應度函數來進行模擬生物的“適者生存”機制的。在遺傳算法中通過適應度函數計算個體的適應值，通過個體的適應值大小來體現個體在群體中的差異程度，進而確定該個體有沒有權利作為父本進行新一代的遺傳操作。遺傳算法的適應度函數（本文中是針對BP神經網絡的性能評價函數）也是遺傳算法指導搜索的唯一標準，它的選取是算法好壞的關鍵。適應度函數要能有效地指導搜索沿著面向優化參數組合的方向，逐漸逼近最優解，并能保證不會導致搜索不收斂和陷入局部最優。針對BP神經網絡，訓練誤差越小則染色體越優。所以，本文采用所有個體與對應的所有目標樣本的誤差平方和的倒數作為染色體的適應值。具體函數如下：[fitness]=gabpEbal(T)，這里fitness為染色體的適應值。在計算神經網絡的輸出值時，對每個染色體進行解碼，計算神經網絡中對應神經元的各個權值W1,W2和閾值B,S，按公式（4）計算出每個樣本的對應網絡輸出值矩陣Y。

2.5 交叉算子

遺傳算法中交叉操作的目的是為了能夠在下一代產生新的個體。通過交叉重組操作，遺傳算法的搜索能力得以飛躍地提高。在遺傳算法中將染色體進行交叉重組是獲取新的優良個體的主要方法。同時交叉操作對遺傳算法的質量也具有非常重要的影響。因此本文選取父代最優解Tmax與子代染色體池進行交叉操作，從而避免算法過早喪失進化能力。常用的交叉方法有一點交叉、兩點交叉、多點交叉和一致交叉等，本文采用的是多點位單基因交叉的方式。具體算法如下：

2.6 變異算子

變異運算中變異率通常取pm=0.1，在單個染色體為Ti=(ti1,ti2,…,tiL-1)上隨機選擇第k個基因tik，對tik加一個小的擾動，實現染色體的變異。由于采用了最優個體Tmax保留的策略，所以在變異運算中，可以加大在當前最優個體附近進行搜索的概率以求得更優解，而不用擔心破壞已經存在的優良染色體。因此，取種群中較好的一部分染色體進行變異操作。

3 數據預處理及算法流程

3.1 數據的歸一化處理

在數據計算中樣本的屬性具有多樣性，某些屬性之間量級上有較大的差異，這些數據的不均衡將導致在網絡訓練過程中，部分屬性特征不能被充分體現，甚至可能會導致網絡的不收斂。因此，在進行網絡訓練和識別之前，需要對原始數據進行適當的預處理，使其更適合于神經網絡的訓練。這里采用的是數據歸一化的方法。該方法就是將訓練樣本的輸入數據和目標數據進行變換，讓數據分布在[-1,1]的區間上。歸一化函數采用的是premnmx()函數。具體公式：

這里，P為原始的輸入數據，maxp和minp分別是P中的最大值和最小值，Pn為經過歸一化處理后的輸入數據。T為原始的目標數據，maxt和mint分別代表目標數據T中的最大值和最小值，Tn為經過歸一化處理后的目標數據。

3.2 算法基本流程及基本框架

改進遺傳算法優化神經網絡權值基本流程如圖2所示。

圖2 算法流程圖

算法框架：

（1）給定樣本數據對數據進行歸一化處理。

（2）建立網絡。

（3）根據網絡神經元數量確定編碼長度。

（4）初始化群體，選擇局部最優染色體Tmax。

（5）調用適應度函數，評價網絡性能，滿足約束條件退出并保存網絡。

（6）數據交叉操作，并保存最優染色體。

（7）利用適應比例法選擇染色體。

（8）判斷是否進行變異操作。

（9）返回到（5）。

4 仿真實驗

圖3 傳統算法適應值曲線（wine）

圖4 改進算法適應值曲線（wine）

圖5 傳統算法網絡訓練（wine）

圖6 改進算法網絡訓練（wine）

圖7 傳統算法適應值曲線（letter）

為了檢驗算法的性能，本文采用UCI數據庫[9]中標準數據集wine、letter-recognition、glass和yeast數據集進行了算法驗證，并在相同迭代次數下對傳統算法與改進算法的適應度函數值進行了比較（實驗環境：CPU為Celeron1.6，內存1 GB，操作系統Windows XP，編程語言Matlab2009）。

實驗1采用的是wine數據，由于數據量較少，所以網絡訓練的收斂速度較快。如圖3和圖4所示分別是在迭代200次時傳統算法與改進算法的適應值變化曲線。從適應值的變化來看改進算法明顯優于傳統算法，在同樣迭代200次時，改進算法的適應值達到了0.7左右，而傳統算法僅達到0.2左右。圖5和圖6為兩種算法的網絡收斂次數曲線，相同條件下改進算法的網絡訓練次數明顯低于傳統算法。

圖8 改進算法適應值曲線（letter）

實驗2采用的是letter-recognition數據，從26類數據中選取每類200個樣本進行訓練。如圖7和圖8所示分別是在迭代200次時傳統算法與改進算法的適應值變化曲線。傳統算法和改進算法的網絡訓練效果如圖9和圖10所示。

實驗3采用的是glass數據。適應值變化曲線及網絡訓練效果如圖11～14所示。

實驗4采用的是yeast數據。適應值變化曲線及網絡訓練效果如圖15～18所示。

5 小結

圖9 傳統算法網絡訓練（letter）

圖10 改進算法網絡訓練（letter）

圖11 傳統算法適應值曲線（glass）

圖12 改進算法適應值曲線（glass）

圖13 傳統算法網絡訓練（glass）

圖14 改進算法網絡訓練（glass）

圖15 傳統算法適應值曲線（yeast）

圖16 改進算法適應值曲線（yeast）

遺傳算法在優化問題的處理上應用非常廣泛，用遺傳算法優化神經網絡權值問題也非常普遍。但是，大多數的遺傳算法都避免不了同代交叉所導致的過早收斂問題，本文提出的改進遺傳算法避免了這種問題。將該算法的全局搜索優勢與BP神經網絡收斂速度快的優勢相互結合，更好地提高了BP神經網絡的收斂速度，加快了網絡的訓練進程。為解決一些分類和主成分分析等實際問題提供了一種較好的方法。從實驗的效果也可以看出，該算法對樣本量較大的數據效果更為明顯。該方法在處理連續數據效果非常好。但是，在處理離散數據方面還存在一些問題，還需要進一步的改進。

圖17 傳統算法網絡訓練（yeast）

圖18 改進算法網絡訓練（yeast）

[1]張毅，楊建國.基于灰色神經網絡的機床熱誤差建模[J].上海交通大學學報，2011，45（11）：1581-1585.

[2]黃偉，何曄，夏暉.基于小波神經網絡的IP網絡流量預測[J].計算機科學，2011，38（10）：296-298.

[3]聶鵬，諶鑫.基于主元分析和BP神經網絡對刀具VB值預測[J].北京航空航天大學學報，2011，37（3）：344-367.

[4]任昊南.用遺傳算法求解TSP問題[D].濟南：山東大學，2008.

[5]Jelasity M，Dombi T.GAS，a concept on modeling species in genetic algorithm[J].Artificial Intelligence，1998，99（1）：1-19.

[6]Han K H，Kim J H.Quantum-inspired evolutionary algorithms with a new termination criterion，Hεgate，and two-phase scheme[J].IEEE Trans on Evolutionary Computation，2004，8（2）：156-169.

[7]Tsai C F，Tsai C W，Tseng C C.A new hybrid heuristic approach for solving large traveling salesman problem[J].Information Sciences，2004，166（1）：67-81.

[8]徐璘俊，楊建剛.基于多層神經網絡的洗錢風險評估方法[J].計算機工程，2011，36（22）：181-183.

[9]Merz C J，Murphy P M.UCI repository of machine learning databases[EB/OL].[2012-03-01].http：//www.ics.uci.edu/～mlearn/ MLRepository.html.

YAO Minghai

1.College of Information Science and Technology,Bohai University,Jinzhou,Liaoning 121013,China
2.School of Mathematics and Statistics,Northeast Normal University,Changchun 130024,China

The characteristics of genetic algorithm and BP neural networks are compared.As evolutionary algorithm neural network and genetic algorithm have same goal but they have different methods.The necessity of the combination genetic algorithm and neural networks is expounded.This paper puts forward a kind of improved genetic algorithm to optimize BP neural network weights,using the global random searching ability of genetic algorithm to make up the question that neural network is easy to fall into local optimal solution.At the same time,the crossover method of genetic algorithm is changed.The same generation does not cross.The parent and son are crossed.Genetic algorithm premature loss of evolutionary ability is averted.

genetic algorithm;neural networks;optimization;weight;optimal solution

對遺傳算法和BP神經網絡的特點進行了比較，作為進化算法神經網絡與遺傳算法的目標相近而方法各異。闡述了遺傳算法與神經網絡結合的必要性。提出了一種改進的遺傳算法優化BP神經網絡的權值，用遺傳算法的全局隨機搜索能力彌補了神經網絡容易陷入局部最優解的問題。同時，在遺傳算法中改變傳統的同代交叉機制，采用父代與子代進行交叉，避免了遺傳算法過早喪失進化能力。

遺傳算法；神經網絡；優化；權值；最優解

A

TP301.6

10.3778/j.issn.1002-8331.1204-0762

YAO Minghai.Application of improved genetic algorithm in optimizing BP neural networks weights.Computer Engineering and Applications,2013,49（24）：49-54.

遼寧省教育科學規劃項目（No.JG10DB129）。

姚明海（1980—），男，博士研究生，講師，主要研究方向：模式識別和智能計算。E-mail：yao_ming_hai@163.com

2012-05-09

2012-06-28

1002-8331（2013）24-0049-06

CNKI出版日期：2012-08-01http://www.cnki.net/kcms/detail/11.2127.TP.20120801.1652.017.html

◎網絡、通信、安全◎