改進遺傳模擬退火算法優化BP算法研究

郭彩杏，郭曉金，柏林江，

1(重慶郵電大學 通信與信息工程學院，重慶 400065) 2(重慶郵電大學 寬帶網絡及信息處理研究所，重慶 400065)E-mail:491620845@qq.com

1 引 言

人工神經網絡是人類在對大腦神經網絡認識理解的基礎上人工構造的、能實現某種功能的、理論化的數學模型[1].神經網絡算法在信息處理、人工智能、模式識別等領域應用十分廣泛.尤其是BP神經網絡，主要因為BP網絡具有很強的自主學習能力，泛化性高，靈活性強.但該算法也有缺陷，例如收斂速度慢、精度低、易陷入局部極小值點等[2].針對這些問題，研究者們提出了許多改進方法.文獻[3-6]分別引入遺傳算法(Genetic Algorithm，GA)、人工魚群算法、粒子群算法(Particle swarm optimization，PSO)、模擬退火算法(Simulated Annealing，SA)來初始化BP神經網絡權閾值.雖然在一定程度上提升了BP網絡的性能，但是GA算法易陷入局部最優、PSO算法易產生早熟收斂、SA算法收斂速度慢等原因導致改進BP網絡性能并不理想.因此，陳闖[7]等提出基于種群相似系數改進的自適應遺傳算法，可以線性自適應改變交叉、變異概率公式，很好地提高了BP網絡的收斂速度及預測精度；楊從銳[8]等提出基于種群適應度密集度改進的自適應遺傳算法，可以起到非線性地自適應改變.以上兩種改進的遺傳算法加快了算法收斂精度及收斂速度，但增加了陷入局部最優的危險性；模擬退火算法可以擺脫局部最優但收斂速度慢.因此，本文結合兩種算法的優點，提出一種改進的遺傳模擬退火算法 (Improved Genetic Simulated Annealing Algorithm，IGSAA)：1)根據進化中種群適應度的集中分散程度改進了自適應遺傳算法的交叉和變異概率公式，使算法能夠更加有效地避免陷入局部最優；2)根據舊種群和新種群中每個對應個體的進化程度提出一種改進的Metropolis準則，分情況修正新種群的所有個體，增加了種群個體多樣性，使算法能夠更加有效地避免陷入局部最優.利用IGSAA算法初始化BP神經網絡的權閾值，基于非線性函數擬合的實驗表明IGSAA-BP算法不僅提高了BP網絡的收斂速度，還有效提高了預測精度.

2 BP神經網絡

BP神經網絡是由Rumelhart 等人于1986年提出的一種按誤差逆傳播算法訓練的不少于三層的前饋網絡.學習過程包含信號正向傳播和誤差反向傳播.三層BP神經網絡結構如圖1所示.在訓練BP神經網絡之前，首先隨機初始化網絡的權閾值，信號通過輸入層進入隱含層，在經過各神經元的信息處理后，經輸出層輸出.若不滿足期望輸出，則進入誤差反向傳播過程，修正各層連接權閾值，進入下一個樣本的訓練.如此循環，直到訓練誤差達到目標要求或所有樣本訓練完畢算法結束.但文獻[9，10]表明，BP算法具有收斂速度慢、精度低、易陷入局部極值等缺點，而這與BP網絡初始的權閾值緊密相關.

圖1 三層BP神經網絡結構Fig.1 Three-layer BP neural network structure

3 遺傳模擬退火算法

遺傳算法是一類借鑒生物進化規律演化而來的隨機搜索方法，常用于尋優，但易陷入局部極值[11].隨后自適應遺傳算法[12](Adaptive Genetic Algorithm，AGA)應運而生，在一定程度上提高了尋優能力，但是增加了算法陷入局部極值的危險性.模擬退火算法[13]是一種通過模擬熱力學中固體退火原理的隨機尋優算法，不易陷入局部最優，但是該算法收斂速度慢，會產生震蕩效應.因此，有學者提出了結合遺傳算法和模擬退火算法的遺傳模擬退火算法.

遺傳模擬退火算法是一種基于組合思想而產生的混合優化算法[14].在把握全局搜索能力比較強的遺傳算法中融入局部搜索能力較強的模擬退火算法，減小遺傳算法陷入局部極值的概率，提升了遺傳算法的全局尋優能力.

遺傳模擬退火算法以遺傳算法為框架，在執行遺傳操作的過程中加入退火操作.首先產生隨機初始種群，然后通過選擇、交叉、變異操作產生新的個體，最后對每個新個體執行退火操作，得到新一代種群.如此循環，直到滿足算法結束條件.遺傳模擬退火算法基本流程如下：

a)初始化參數(種群規模、最大迭代次數、交叉、變異概率、退火算法初始溫度、退火系數)；

b)隨機初始化種群；

c)計算種群個體適應度函數；

d)選擇種群的較優個體執行交叉、變異操作，產生新一代個體；

e)對新個體執行退火操作，并以Metropolis準則接受退火操作前后的個體，形成新一代種群；Metropolis準則如下：

(1)

xnew為產生的新解，xold為當前解，E為溫度T時的內能.

f)計算種群個體適應度值，并對個體進行評價；

g)判斷結束條件，若滿足則輸出最優解，算法結束；否則跳轉到步驟d)，進入下一輪迭代.

4 改進遺傳模擬退火算法優化BP神經網絡

針對BP神經網絡自身的缺陷，不少學者提出利用遺傳模擬退火算法來優化.這雖然在一定程度上提高了BP網絡性能，但效果并不十分理想.因此，本文分別從遺傳算法和退火算法各自的缺點入手，提出相關改進方法，以期提高算法的收斂性和全局尋優能力，進而優化BP網絡的權閾值，提高BP網絡的性能.

4.1 改進的交叉和變異概率

交叉概率Pc和變異概率Pm是影響遺傳算法尋優能力的關鍵因素[15].交叉概率決定著種群個體多樣性，在遺傳算法中起核心作用；變異概率則決定著遺傳算法能不能跳出局部最優，因此選擇合適的交叉和變異概率更容易尋得全局最優解.但是傳統遺傳算法交叉、變異概率為常數，實際應用中難以調至最佳；自適應遺傳算法通過自適應調整交叉、變異概率，盡可能使種群個體向著適應度值高的方向進化，但增加了算法陷入局部極值的危險性.對此，本文利用種群適應度集中分散的不同程度改進了自適應交叉概率Pc和變異概率Pm.改進的自適應交叉概率Pc和變異概率Pm如下[16]：

(2)

(3)

其中fmax為種群的最大適應度值，favg表示種群的平均適應度值；k1～k2為自適應控制參數.

陳闖、Srinivas等人提出的自適應交叉、變異概率地自適應改變是基于線性的，當個體的適應度值小于種群平均適應度時不再具有自適應性.而本文中的arcsin(favg/fmax)參數可以使交叉和變異概率非線性地自適應改變.若arcsin(favg/fmax)<π/6成立，說明種群的平均適應度值不接近種群的最大適應度值，比π/6小的越多，種群的適應度值就越分散，種群越豐富.由公式(2)、公式(3)可知，交叉概率的值自適應增加，使個體可以充分交叉，產生新的優質個體；同時變異概率的值自適應減少，減小破壞優良個體的概率，加快算法的收斂速度.

同理，若arcsin(favg/fmax)≥π/6成立，說明種群的平均適應度值接近種群的最大適應度值，比π/6大的越多，種群的適應度值分布越集中，種群多樣性降低.此時由公式(2)、公式(3)可知，交叉概率自適應減小，減少交叉操作，加快算法收斂速度；同時變異概率自適應增加，使算法可以更好的擺脫局部極值，得到全局最優解.

4.2 改進的Metropolis準則

傳統模擬退火算法收斂速度慢，易產生震蕩效應，基于標準Metropolis準則對新種群的所有個體進行修正.修正結果只有兩種：1)接受新種群中的個體；2)保存舊種群中個體，這就造成種群個體多樣性不理想.針對這個問題，本文根據舊種群和新種群中每個對應個體的進化程度提出一種改進的Metropolis準則，分情況修正新種群的所有個體.

改進Metropolis準則如下：

1)定義跳變概率:

(4)

其中，k為Boltzmann常數，f(xnew(j))為新種群中第j個個體xnew(j)的適應度值，f(xold(j))為舊種群中第j個個體xold(j)的適應度值.

2)當新種群中個體的適應度值大于舊種群中對應個體的適應度值時(極大值情況下)，接受新個體為下一代新種群中的個體；

3)當新種群中個體的適應度值小于等于舊種群中對應個體的適應度值時，首先遍歷該新個體染色體的所有基因，各基因以0.01的概率與該染色體隨機一個基因進行位置互換產生新個體；然后以概率P1接受該新個體為下一代新種群中的個體，否則接受舊種群中的相應個體.

改進Metropolis準則在產生較差個體后，首先對該較差個體染色體的各基因進行隨機位置互換，以提高個體的性能；然后以概率P1接受該新個體.改進準則增加了種群個體多樣性，提高退火算法尋優能力.

IGSAA-BP算法步驟如下：

1)初始化相關參數.

隨機初始化種群，定義種群規模N，設置最大迭代次數gmax，計算個體染色體長度M：

M=ni×nh+nh×no+nh+no

(5)

其中ni，nh，no分別為BP網絡各層神經元個數.規定初始溫度T0=100℃，當前溫度Tnow，結束溫度Tmin.

2)初始化當前迭代次數g=1.

3)計算個體適應度值.

個體解碼，訓練BP神經網絡，計算均方誤差并將其倒數作為個體適應度值，記錄當前最優個體Cb.適應度函數如下：

fit=1/MSE(x)

(6)

x是種群個體，對應BP 網絡的權值和閾值排列.適應度值越大，代表該個體越優秀.

4)通過3.1中改進的自適應交叉、變異概率公式執行遺傳操作產生新種群.

判斷arcsin(favg/fmax)<π/6是否成立，如果成立，說明種群的適應度值分布較分散，先執行交叉、變異操作，后執行選擇操作產生新種群；如果不成立，說明種群的適應度值分布較集中，則執行變異、交叉操作后，再進行選擇操作產生新種群.

5)通過3.2中改進的Metropolis準則，分情況修正步驟3)中產生的新種群中的所有個體，得到新一代種群.

i)若xnew(j)的適應度值大于xold(j)的適應度值，則接受xnew(j)為新一代種群中的第j個個體，依此類推.

6)更新全局最優個體.

7)循環操作.

5 實驗仿真與分析

5.1 IGSAA算法性能分析

為了驗證本文提出的IGSAA算法的性能，選取了4個標準測試函數進行仿真測試.選取測試函數如表1所示，除了f1是單峰值函數外，f2～f4都是多峰值函數.實驗相關參數設置如表2所示(種群規模40，迭代次數100).將 GA、IAGA 與 IGSAA 三種算法對每一個測試函數進行測試，算法獨立實驗 30 次的最優值、最差值、平均值如表3所示.

表1 標準測試函數Table 1 Standard test function

從表3可以看出，在測試極易陷入局部極值的f2函數時，IGSAA尋優精度較IAGA提高了10倍；在測試具有大量局部極值的f3函數時該算法直接找到最優解0；在測試較難搜索到全局最優點的f4函數時，尋優精度提高了約10^3倍.因此，在尋優精度、擺脫局部極值方面IGSAA表現突出.

表2 實驗中算法相關參數設置Table 2 Algorithm-related parameter settings in the experiment

5.2 IGSAA-BP神經網絡性能分析

表3 標準函數測試結果Table 3 Standard function test results

經多次驗證，采用2-10-1的網絡結構，神經網絡相關參數設置如下：最大迭代次數5000，目標精度0.00001，學習率0.1.IGSAA算法相關參數設置如下：GA種群規模為30，最大迭代次數為100，初始交叉、變異概率分別為0.9和0.001，自適應控制參數k1=1，k2=0.5；SA算法中，初始溫度為100°C，結束溫度為90℃，退溫系數為0.98.選取均方誤差MSE、平均絕對誤差MAE作為預測樣本的評價指標[17].圖2為三種算法下的網絡預測誤差對比.圖3為三種算法下最優個體適應度值曲線.

從圖2可以看出，改進的遺傳模擬退火算法優化BP神經網絡對非線性函數的擬合和預測取得了良好的效果.三種算法中GA-BP網絡擬合能力最差，IAGA-BP網絡次之，IGSAA-BP網絡擬合能力最強.此外，還可以看到擬合誤差波動范圍從最開始的-0.1～0.07，降低到-0.01～0.02，誤差大大減小，波動趨于平穩.因此，在擬合能力、擬合精度方面本文改進算法有明顯優勢.

把三種算法重復執行30次以后，記錄迭代次數、均方誤差、平均絕對誤差和擬合準確度并進行對比，結果如表4所示.

從表4可知，相同的訓練目標精度下，GA-BP、IAGA-BP、IGSAA-BP三種網絡模型停止訓練的學習次數依次為36次、26次、9次，IGSAA有效地提高了BP神經網絡的收斂速度，收斂率較IAGA提高了約65%，較GA提高了約75%.此外，還可以看出IGSAA-BP的擬合均方誤差較IAGA提高了約63%，較GA提高了約84%；擬合平均絕對誤差較IAGA提高了約52%，較GA提高了約68%；擬合準確度較IAGA提高了2%，較GA提高了5%.仿真結果表明：本文改進算法不僅提高了BP網絡的收斂速度，還有效地提高了網絡的擬合能力.

圖2 三種算法下的預測誤差Fig.2 Prediction errors under three kinds of algorithms

表4 三種網絡模型預測誤差指標Table 4 Three network model prediction error indicators

圖3 三種算法下最優個體的適應度值曲線Fig.3 Fitness curve of optimal individual under three kinds of algorithms

如圖3所示，隨著進化代數的增加，最優個體的適應度值呈階梯狀上升，且IGSAA的全局尋優能力明顯優于GA、IAGA.GA經過4次收斂進化至75代時找到最優個體的適應度值257.09；IAGA經過4次收斂進化至67代時找到最優個體的適應度值371.56；IGSAA經過4次收斂進化至95代時找到最優個體的適應度值667.39.由此可知本文改進算法預測誤差比GA縮小了2.6倍，比IAGA縮小了1.8倍，尋優能力明顯增強.雖然GA、IAGA較快地收斂，但是二者均陷入了局部極值，本文提出的改進算法理論上可以尋得最優個體(初始溫度足夠大).本文用arcsin(favg/fmax)作為判斷依據，可以非線性地自適應調整交叉、變異概率，使得遺傳算法的全局尋優能力更強，減小陷入局部極值的概率.此外，又引入改進的Metropolis準則，在每次執行完遺傳操作后如果得到更差個體，以0.01的概率對該較差個體染色體的各基因進行隨機位置互換產生新個體，再以概率P1接受新個體為新一代種群的個體.改進算法爬坡能力較強，不易陷入局部最優.由圖3可以看出IGSAA算法呈階梯狀上升，產生多次收斂，最終擺脫了局部收斂，體現出了較強的自適應性.

6 總 結

本文針對BP神經網絡在非線性函數擬合應用中收斂速度慢、精度低、易陷入局部極值等問題，提出一種改進的遺傳模擬退火算法來優化BP神經網絡.該算法首先引入arcsin(favg/fmax)變量，使得遺傳算法部分的交叉、變異概率可以非線性地自適應調整；然后通過比較arcsin(favg/fmax)與π/6的大小，可以很好地判斷種群適應度集中分散的程度，從而決定交叉、變異操作的執行順序；最后，根據改進的Metropolis準則對新種群中所有個體分情況進行修正，增加了種群個體的多樣性，很好地提高了算法的收斂速度和全局尋優能力.將上述改進算法優化BP神經網絡后用于擬合非線性函數，仿真結果表明：改進的遺傳模擬退火算法優化BP神經網絡對非線性函數的擬合和預測取得了良好的效果.相比GA-BP、IAGA-BP，本文改進算法在收斂速度、預測精度方面更有優勢.