改進(jìn)遺傳模擬退火算法優(yōu)化BP算法研究

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

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

1 引 言

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

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

BP神經(jīng)網(wǎng)絡(luò)是由Rumelhart 等人于1986年提出的一種按誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的不少于三層的前饋網(wǎng)絡(luò).學(xué)習(xí)過程包含信號正向傳播和誤差反向傳播.三層BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示.在訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)之前，首先隨機(jī)初始化網(wǎng)絡(luò)的權(quán)閾值，信號通過輸入層進(jìn)入隱含層，在經(jīng)過各神經(jīng)元的信息處理后，經(jīng)輸出層輸出.若不滿足期望輸出，則進(jìn)入誤差反向傳播過程，修正各層連接權(quán)閾值，進(jìn)入下一個樣本的訓(xùn)練.如此循環(huán)，直到訓(xùn)練誤差達(dá)到目標(biāo)要求或所有樣本訓(xùn)練完畢算法結(jié)束.但文獻(xiàn)[9，10]表明，BP算法具有收斂速度慢、精度低、易陷入局部極值等缺點(diǎn)，而這與BP網(wǎng)絡(luò)初始的權(quán)閾值緊密相關(guān).

圖1 三層BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Three-layer BP neural network structure

3 遺傳模擬退火算法

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

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

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

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

b)隨機(jī)初始化種群；

c)計(jì)算種群個體適應(yīng)度函數(shù)；

d)選擇種群的較優(yōu)個體執(zhí)行交叉、變異操作，產(chǎn)生新一代個體；

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

(1)

xnew為產(chǎn)生的新解，xold為當(dāng)前解，E為溫度T時的內(nèi)能.

f)計(jì)算種群個體適應(yīng)度值，并對個體進(jìn)行評價；

g)判斷結(jié)束條件，若滿足則輸出最優(yōu)解，算法結(jié)束；否則跳轉(zhuǎn)到步驟d)，進(jìn)入下一輪迭代.

4 改進(jìn)遺傳模擬退火算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)

針對BP神經(jīng)網(wǎng)絡(luò)自身的缺陷，不少學(xué)者提出利用遺傳模擬退火算法來優(yōu)化.這雖然在一定程度上提高了BP網(wǎng)絡(luò)性能，但效果并不十分理想.因此，本文分別從遺傳算法和退火算法各自的缺點(diǎn)入手，提出相關(guān)改進(jìn)方法，以期提高算法的收斂性和全局尋優(yōu)能力，進(jìn)而優(yōu)化BP網(wǎng)絡(luò)的權(quán)閾值，提高BP網(wǎng)絡(luò)的性能.

4.1 改進(jìn)的交叉和變異概率

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

(2)

(3)

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

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

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

4.2 改進(jìn)的Metropolis準(zhǔn)則

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

改進(jìn)Metropolis準(zhǔn)則如下：

1)定義跳變概率:

(4)

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

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

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

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

IGSAA-BP算法步驟如下：

1)初始化相關(guān)參數(shù).

隨機(jī)初始化種群，定義種群規(guī)模N，設(shè)置最大迭代次數(shù)gmax，計(jì)算個體染色體長度M：

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

(5)

其中ni，nh，no分別為BP網(wǎng)絡(luò)各層神經(jīng)元個數(shù).規(guī)定初始溫度T0=100℃，當(dāng)前溫度Tnow，結(jié)束溫度Tmin.

2)初始化當(dāng)前迭代次數(shù)g=1.

3)計(jì)算個體適應(yīng)度值.

個體解碼，訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)，計(jì)算均方誤差并將其倒數(shù)作為個體適應(yīng)度值，記錄當(dāng)前最優(yōu)個體Cb.適應(yīng)度函數(shù)如下：

fit=1/MSE(x)

(6)

x是種群個體，對應(yīng)BP 網(wǎng)絡(luò)的權(quán)值和閾值排列.適應(yīng)度值越大，代表該個體越優(yōu)秀.

4)通過3.1中改進(jìn)的自適應(yīng)交叉、變異概率公式執(zhí)行遺傳操作產(chǎn)生新種群.

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

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

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

6)更新全局最優(yōu)個體.

7)循環(huán)操作.

5 實(shí)驗(yàn)仿真與分析

5.1 IGSAA算法性能分析

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

表1 標(biāo)準(zhǔn)測試函數(shù)Table 1 Standard test function

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

表2 實(shí)驗(yàn)中算法相關(guān)參數(shù)設(shè)置Table 2 Algorithm-related parameter settings in the experiment

5.2 IGSAA-BP神經(jīng)網(wǎng)絡(luò)性能分析

表3 標(biāo)準(zhǔn)函數(shù)測試結(jié)果Table 3 Standard function test results

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

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

把三種算法重復(fù)執(zhí)行30次以后，記錄迭代次數(shù)、均方誤差、平均絕對誤差和擬合準(zhǔn)確度并進(jìn)行對比，結(jié)果如表4所示.

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

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

表4 三種網(wǎng)絡(luò)模型預(yù)測誤差指標(biāo)Table 4 Three network model prediction error indicators

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

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

6 總 結(jié)

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