改进遗传模拟退火算法优化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，本文改进算法在收敛速度、预测精度方面更有优势.