姚明海

1.渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院，遼寧錦州 121013

2.東北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，長春 130024

改進的遺傳算法在優(yōu)化BP網(wǎng)絡(luò)權(quán)值中的應(yīng)用

姚明海

1.渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院，遼寧錦州 121013

2.東北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，長春 130024

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

1 BP神經(jīng)網(wǎng)絡(luò)

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

圖1 三層網(wǎng)絡(luò)結(jié)構(gòu)

BP神經(jīng)網(wǎng)絡(luò)中隱層神經(jīng)元轉(zhuǎn)移函數(shù)一般有階躍函數(shù)、準(zhǔn)線性函數(shù)、Sigmoid函數(shù)和雙正切函數(shù)等，本文采用的轉(zhuǎn)移函數(shù)為Sigmoid函數(shù)。其表達式如下：

2 改進的遺傳算法

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

2.1 染色體編碼

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

2.2 產(chǎn)生初始種群和局部最優(yōu)染色體Tmax

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

這里T為初始染色體群，Tmax為初始染色體群T中的最優(yōu)染色體，Psize為初始種群的規(guī)模，aa為染色體中每個基因的取值范圍，gabpEbal為適應(yīng)度函數(shù)。

2.3 選擇算子

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

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

2.4 適應(yīng)度函數(shù)gabpEbal()

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

2.5 交叉算子

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

2.6 變異算子

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

3 數(shù)據(jù)預(yù)處理及算法流程

3.1 數(shù)據(jù)的歸一化處理

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

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

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

改進遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)權(quán)值基本流程如圖2所示。

圖2 算法流程圖

算法框架：

（1）給定樣本數(shù)據(jù)對數(shù)據(jù)進行歸一化處理。

（2）建立網(wǎng)絡(luò)。

（3）根據(jù)網(wǎng)絡(luò)神經(jīng)元數(shù)量確定編碼長度。

（4）初始化群體，選擇局部最優(yōu)染色體Tmax。

（5）調(diào)用適應(yīng)度函數(shù)，評價網(wǎng)絡(luò)性能，滿足約束條件退出并保存網(wǎng)絡(luò)。

（6）數(shù)據(jù)交叉操作，并保存最優(yōu)染色體。

（7）利用適應(yīng)比例法選擇染色體。

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

（9）返回到（5）。

4 仿真實驗

圖3 傳統(tǒng)算法適應(yīng)值曲線（wine）

圖4 改進算法適應(yīng)值曲線（wine）

圖5 傳統(tǒng)算法網(wǎng)絡(luò)訓(xùn)練（wine）

圖6 改進算法網(wǎng)絡(luò)訓(xùn)練（wine）

圖7 傳統(tǒng)算法適應(yīng)值曲線（letter）

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

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

圖8 改進算法適應(yīng)值曲線（letter）

實驗2采用的是letter-recognition數(shù)據(jù)，從26類數(shù)據(jù)中選取每類200個樣本進行訓(xùn)練。如圖7和圖8所示分別是在迭代200次時傳統(tǒng)算法與改進算法的適應(yīng)值變化曲線。傳統(tǒng)算法和改進算法的網(wǎng)絡(luò)訓(xùn)練效果如圖9和圖10所示。

實驗3采用的是glass數(shù)據(jù)。適應(yīng)值變化曲線及網(wǎng)絡(luò)訓(xùn)練效果如圖11～14所示。

實驗4采用的是yeast數(shù)據(jù)。適應(yīng)值變化曲線及網(wǎng)絡(luò)訓(xùn)練效果如圖15～18所示。

5 小結(jié)

圖9 傳統(tǒng)算法網(wǎng)絡(luò)訓(xùn)練（letter）

圖10 改進算法網(wǎng)絡(luò)訓(xùn)練（letter）

圖11 傳統(tǒng)算法適應(yīng)值曲線（glass）

圖12 改進算法適應(yīng)值曲線（glass）

圖13 傳統(tǒng)算法網(wǎng)絡(luò)訓(xùn)練（glass）

圖14 改進算法網(wǎng)絡(luò)訓(xùn)練（glass）

圖15 傳統(tǒng)算法適應(yīng)值曲線（yeast）

圖16 改進算法適應(yīng)值曲線（yeast）

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

圖17 傳統(tǒng)算法網(wǎng)絡(luò)訓(xùn)練（yeast）

圖18 改進算法網(wǎng)絡(luò)訓(xùn)練（yeast）

[1]張毅，楊建國.基于灰色神經(jīng)網(wǎng)絡(luò)的機床熱誤差建模[J].上海交通大學(xué)學(xué)報，2011，45（11）：1581-1585.

[2]黃偉，何曄，夏暉.基于小波神經(jīng)網(wǎng)絡(luò)的IP網(wǎng)絡(luò)流量預(yù)測[J].計算機科學(xué)，2011，38（10）：296-298.

[3]聶鵬，諶鑫.基于主元分析和BP神經(jīng)網(wǎng)絡(luò)對刀具VB值預(yù)測[J].北京航空航天大學(xué)學(xué)報，2011，37（3）：344-367.

[4]任昊南.用遺傳算法求解TSP問題[D].濟南：山東大學(xué)，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īng)網(wǎng)絡(luò)的洗錢風(fēng)險評估方法[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神經(jīng)網(wǎng)絡(luò)的特點進行了比較，作為進化算法神經(jīng)網(wǎng)絡(luò)與遺傳算法的目標(biāo)相近而方法各異。闡述了遺傳算法與神經(jīng)網(wǎng)絡(luò)結(jié)合的必要性。提出了一種改進的遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值，用遺傳算法的全局隨機搜索能力彌補了神經(jīng)網(wǎng)絡(luò)容易陷入局部最優(yōu)解的問題。同時，在遺傳算法中改變傳統(tǒng)的同代交叉機制，采用父代與子代進行交叉，避免了遺傳算法過早喪失進化能力。

遺傳算法；神經(jīng)網(wǎng)絡(luò)；優(yōu)化；權(quán)值；最優(yōu)解

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.

遼寧省教育科學(xué)規(guī)劃項目（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

◎網(wǎng)絡(luò)、通信、安全◎