计算机系统应用  2020, Vol. 29 Issue (1): 244-249   PDF    
粒子群退火算法优化的BP神经网络及其应用
王荣1, 白尚旺1, 党伟超1, 潘理虎1,2     
1. 太原科技大学 计算机科学与技术学院, 太原 030024;
2. 中国科学院 地理科学与资源研究所, 北京 100101
摘要:以提高预测软件老化趋势为应用背景, 提出一种新型粒子群退火算法(New Particle Swarm Annealing Algorithm, NPSOSA)优化BP神经网络的权值和阈值, 继而构建NPSOSA-BP神经网络预测模型. 实验通过搭建软件老化测试平台, 收集所需的老化数据并进行仿真训练. 实验结果表明, NPSOSA-BP神经网络模型相比于传统粒子群算法(PSO)、传统粒子群退火算法(PSOSA)优化的BP神经网络模型提高了预测精度和适用度, 在该应用领域验证了本文方法的有效性.
关键词: BP神经网络    粒子群算法    模拟退火算法    软件老化预测    
BP Neural Network Optimized by Particle Swarm Annealing Algorithms and Its Application
WANG Rong1, BAI Shang-Wang1, DANG Wei-Chao1, PAN Li-Hu1,2     
1. School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China;
2. Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China
Foundation item: Applied Basic Research Project of Shanxi Province (201801D221179); Scientific Research Start-Up Fund for Doctorate of Taiyuan University of Science and Technology (20162036); Industry-University Cooperation Project of Ministry of Education (201801128011); Year 2019, Fund of Association of Fundamental Computing Education in Chinese Universities (CERACU2019R02); Education Reform Innovation Project of Taiyuan University of Science and Technology (201937)
Abstract: In order to improve the forecasting software aging trend, a New Particle Swarm Optimization Simulated Annealing algorithm (NPSOSA) is proposed to optimize the weights and thresholds of BP neural network, and then NPSOSA-BP neural network forecasting model is constructed. The software aging test platform was built to collect the required aging data and conduct simulation training. The experimental results show that the NPSOSA-BP neural network model improves the prediction accuracy and applicability compared with the BP neural network model optimized by the traditional Particle Swarm Optimization (PSO) and the traditional Particle Swarm Optimization Simulated Annealing algorithm (PSOSA). The validity of this method is verified in this application field.
Key words: BP neural network     Particle Swarm Optimization (PSO)     Simulated Annealing (SA) algorithm     software aging prediction    

软件老化通常是由软件故障激活的累积效应造成的, 从而导致内存泄漏、操作系统资源耗尽等系统错误, 最终致使软件失效或系统宕机的现象[1]. 随着软件系统的广泛应用, 研究发现在Web服务器[2]、文件服务器、数据库管理系统[3]、DNS服务器以及虚拟化环境[4]等, 出现软件老化现象的概率会更高. 随着云计算时代的到来, 提高系统可靠性的问题显得尤为重要. 因此, 对软件老化趋势进行早期预测, 在系统发生故障之前采取相应措施, 能够有效的提高软件的可靠性与安全性.

软件老化, 受系统性能参数的相互影响和制约, 呈现出一种非线性的特性. 而BP神经网络, 是一种应用较广泛的多层前馈型神经网络, 能够拟合任意的非线性映射, 是一个复杂的非线性动力学习系统[5]. 现有的基于BP神经网络的软件老化预测模型虽然在一定程度上取得了很大的进展, 但仍存在一些不足之处, 如BP神经网络的初始权值和阈值都是随机设定的[6], 而粒子群算法能够很好的解决BP神经网络对初始参数选取比较敏感的问题. 因此本文通过构建NPSOSA-BP神经网络预测模型, 将NPSOSA算法得到的最优解赋值给BP神经网络的权值和阈值, 并实现对软件老化趋势进行预测, 实验表明本文提出的NPSOSA-BP神经网络预测模型, 相比于传统粒子群算法改进的BP神经网络模型的预测精度更高.

1 BP神经网络

BP (Back Propagation)神经网络是目前应用比较广泛的神经网络算法, 是一种误差逆向推导的训练模型. 由输入层、隐含层和输出层3层组成, 每一层都有大量且数量不同的神经元. BP神经网络在学习的过程中, 由数据正向传播和误差的逆向推导两部分构成. 正向传播即在输入层输入训练样本后, 神经元被激活, 激活值由输入层经隐含层处理后最终由输出层输出网络响应; 逆向传播的过程为: 如果在正向传播过程中训练输出与期望输出间存在误差, 则按照梯度下降法, 经输出层和隐含层沿着误差减小的方向进行调整, 不断修改各个神经元的连接权值和阈值, 直至满足网络的输出要求.

2 NPSOSA-BP神经网络预测模型的建立 2.1 基本粒子群算法

基本粒子群算法(Particle Swarm Optimization, PSO), 具有良好的搜索机制, 最早由Kennedy和Eberhart于1995年提出的. PSO算法起源于对鸟类捕食行为的研究, 并将其与优化问题的求解过程进行对比及研究. 该算法中每个粒子都可以看作是搜索空间中的最优解, 在移动与飞行的过程中, 利用适应度函数求得适应度值, 用适应度值评价当前解的优劣. 每个粒子由位置、速度和适应度值三项特征值进行表示. PSO算法随机初始化一群粒子, 接着在迭代搜索过程中, 参照个体和群体极值的最优解, 不断调整飞行的速度和位置, 以搜索到全局最优值. 速度和位置更新公式如下[7]:

$V_{im}^{k + 1} = V_{im}^k + {c_1}{r_1}(P_{im}^k - X_{im}^k) + {c_2}{r_2}(P_{gm}^k - X_{im}^k)$ (1)
$X_{im}^{k + 1} = X_{im}^k + V_{im}^{k + 1}$ (2)

其中, $m = 1,2, \cdots, M$ ; $i = 1,2, \cdots, N$ ; ${V_{im}}$ 为第 $i$ 个粒子在第 $m$ 维的飞行速度; ${X_{im}}$ 为粒子的位置; ${c_1}$ ${c_2}$ 为非负的常数, 称为加速度因子; ${r_1}$ ${r_2}$ 为介于[0, 1]之间的随机变量; ${P_{im}}$ 为个体粒子经历过自身最优位置; ${P_{gm}}$ 为种群粒子集合中各个粒子进行比较后所经历的全局最优位置.

2.2 PSO算法的改进

PSO算法从种群的多个个体出发并行处理, 具有良好的全局收敛性. 但是PSO算法应用在高维复杂问题上, 往往会出现迭代期间搜索不平衡, 极易陷入局部极值得不到全局最优解、早熟收敛的问题. 针对PSO算法的缺陷, 本文提出一种NPSOSA优化算法, 分别采用动态变化惯性权重法, 以及引入模拟退火算法(Simulated Annealing algorithm, SA), 对PSO算法进行改进. 首先采用动态变化惯性权重法, 使得迭代初期较大的惯性权重能够拥有较强的全局搜索能力, 而迭代后期较小的惯性权重有利于进行更精确的局部搜索, 以此达到在整个迭代过程中平衡粒子的全局与局部搜索能力. 其次针对粒子群算法易聚集到次优解而陷入局部最优发生早熟的情况, 利用SA算法的概率突跳性来跳出局部极值, 避免早熟问题.

2.2.1 动态变化惯性权重的设置

PSO算法是粒子在飞行过程中不断寻找最优值, 但是当粒子以较快速度飞向全局最优解所在的区域时, 尤其是在靠近最优解时, 由于飞行速度过快, 缺乏有效控制与约束, 粒子的移动将会超过最优解的位置, 粒子只能在最优解的附近来回移动, 往前一步超过最优解位置, 后退一步错过最优解位置, 使得粒子陷入局部优化的状态.

为了使PSO算法在迭代周期内达到局部与全局搜索的有效平衡, 并实现对粒子飞行速度的有力控制, 本文引入了“动态变化惯性权重”参数. 实验表明, 在惯性权重ɷ不变的情况下PSO算法拥有较快的收敛速度, 但容易出现在最优解的位置来回反复移动, 陷入局部最优的问题. 而采用“动态变化惯性权重法”优化的PSO算法, 具有比固定值更为良好的搜索结果, 使得迭代初期较大的惯性权重能够在全局搜索范围内得到较好的粒子, 且搜索后期较小的惯性权重能够在极值点的周围做精细的搜索[8], 有效提高了算法的求解精度. 本文采用的动态变化惯性权重法公式如下, 对应的曲线如图1所示.

图 1 动态变化惯性权重

$\omega (k) = {\omega _{\rm start}} - ({\omega _{\rm start}} - {\omega _{\rm end}}){\left(\frac{k}{{{T_{\max }}}}\right)^2}$ (3)

其中, ${\omega _{\rm start}}$ 为PSO算法迭代初期时的惯性权重值; ${\omega _{\rm end}}$ 为最大迭代次数时的终止权重值; $k$ 为当前迭代数; ${T_{\max }}$ 为最大迭代数. 从图1可以看出, 迭代初期惯性权重变化较慢, 粒子可以进行较大范围的搜索, 随着迭代次数的增加, 惯性权重下降的速度也逐渐加快, 较好的局部搜索能力展现出来. 该策略下的粒子速度更新公式如下:

$V_{im}^{k + 1} = \omega V_{im}^k + {c_1}{r_1}(P_{im}^k - X_{im}^k) + {c_2}{r_2}(P_{gm}^k - X_{im}^k)$ (4)
2.2.2 模拟退火算法的引入

SA算法, 主要源于热力学的理论, 通过研究热平衡问题, 将其应用在优化问题的求解过程中. 在模拟高温物体退火过程中寻找优化问题的全局或者近似全局最优解[9]. 因此如何有效的调整温度成为SA算法最重要的问题, 在算法中温度是一个很重要的参数, 一方面, 温度可以限制SA的搜索范围; 另一方面, 温度决定了算法在运行过程中以多大的概率接受劣于当前解的新解. 其中, SA算法采用Metepolis准则作为接受新解的概率. 公式如下:

$P(x = > {x'}) = \left\{ {\begin{aligned} &{1,}&{f({x'}) < f(x)}\\ &{\exp \left[ - \frac{{f({x'}) - f(x)}}{T}\right],}&{f({x'}) \ge f(x)} \end{aligned}} \right.$ (5)

其中, $x$ 为当前解; ${x'}$ 为新解; $f( \cdot )$ 代表解的目标函数值; T为温度.

本文提出的NPSOSA算法以NPSO算法为主要的流程, 是在继承NPSO算法优点的基础上, 引入SA算法. 该算法的思想是: 在更新个体和种群极值时加入SA算法, 对NPSO算法的适应度值和位置按照Metropolis准则接受最优解的同时以一定的概率接受恶化值. 该过程不断迭代进行, 开始时温度较高, 接受劣解的概率相对较高, 使得粒子有很高的机率跳出局部最优解, 随着温度的逐步下降, 能量降低, 粒子接受较差解的概率变小, 最终收敛至全局最优解, 避免早熟问题. ${p_i}$ 存储的是各个粒子的位置和适应值, ${P_g}$ 存储种群最优粒子的位置和适应值. 计算各粒子接受概率公式如下:

$TF({P_i}) = \frac{{{e^{ - (f({p_i}) - f({p_g}))/t}}}}{{\displaystyle \sum\limits_{i = 1}^N {{e^{ - (f({p_i}) - f({p_g})/t}}} }}$ (6)
2.3 构建NPSOSA-BP神经网络

NPSOSA-BP神经网络其本质是利用NPSOSA算法寻优能力强, 收敛速度快的优势, 获得最优的初始权值和阈值, 并将最优值赋值给BP神经网络, 应用在软件老化预测趋势上. 实验表明, 利用NPSOSA算法优化BP神经网络能有效提高网络的性能, 预测精度也相对提升.

2.3.1 NPSOSA-BP神经网络结构的确定

本文实验的输入层与输出层节点数分别为3、10. 隐含层节点数按照传统的计算公式 $l = \sqrt {m + n} + a$ , $a \in (1,10) $ , 得出适宜的节点数值范围为3~12. 经过仿真实验, 验证得出当隐含层节点数为10的时候, 模型能达到最佳软件老化预测状态. 于是本文搭建了具有3-10-1结构的NPSOSA-BP神经网络预测模型. 实际上, 除了选取最佳隐含层神经元个数以外, 也可以通过增加隐含层数来提高神经网络的学习能力, 但后者方法使网络结构复杂化, 训练时间增长, 因此本文采用单隐含层BP神经网络.

2.3.2 NPSOSA-BP神经网络预测模型的训练与预测

NPSOSA-BP神经网络预测模型的训练与预测流程如下:

① 数据预处理. 由于原始数据数量级差别较大, 对BP神经网络训练过程产生较大的影响, 加大训练难度. 因此为了提高神经网络的训练效率, 在对数据进行分析之前, 需要对数据进行归一化处理, 将输入层数据和输出层数据归一化到[–1, 1]之间.

② NPSOSA-BP算法参数的设定. 本实验NPSO算法参数设定: 加速度因子 ${c_1} = {c_2} = 1.494\;45$ , $\omega _{\rm start} = $ 0.9, ${\omega _{\rm end}} = 0.4$ , 迭代次数为1000次, 种群规模为60. SA算法参数设置: 初始温度为10 000, 温度下降速率采用公式: $T = {T_0}({0.9^{j - 1}})$ , 其中 ${T_0}$ 为初始温度, $j$ 为迭代次数. BP算法初始参数设置: 学习速率为0.05, 期望误差为1×10–6.

③ 初始化粒子群. NPSO算法需要对BP神经网络中所有权值和阈值的集合进行优化. 粒子的速度和位置向量的维数等于BP神经网络中所有权值和阈值的数量之和, 即3×10+10×1+10+1=51. 采用算法开发与分析工具Matlab 2016a, 其内部函数rands(1, 51)随机初始化粒子的位置和速度.

④ 更新粒子的速度和位置. 将所有粒子放置在预测模型中进行训练, 通过适应度函数式(7)计算适应度值, 以此作为评价粒子的优劣, 适应值越小, 表示适应度越高. 此外根据式(2)和式(4), 更新粒子的速度和位置, 本文采用BP神经网络的输出均方根平均误差和作为神经网络的适应度值, 公式如下:

$F = {\sum\limits_{i = 1}^m {({y_i} - \mathop y\limits^ \wedge )} ^2}$ (7)

⑤ 迭代输出最优值. 粒子在每次更新时, 采用Metropolis准则计算适应度值, 随着温度的降低, 收敛得到全局最优解.

⑥ NPSOSA-BP神经网络模型训练. 获得最优解并确定BP神经网络的权值和阈值, 输入训练数据来训练模型. 用训练好的模型对软件老化趋势进行预测.

3 实验与结果分析 3.1 软件老化加速寿命实验

为研究与内存泄漏相关的软件老化现象, 本文以一个符合TPC-W基准测试规范的Web应用服务器为研究对象, 在其后台程序中注入关于内存泄漏的代码加速其老化, 从而设计出加速寿命测试实验[10], 并收集老化数据作为实验的训练集和测试集. TPC-W的组成在逻辑上分为3层: 一个Web服务器, 一个数据库, 以及一定量的模拟浏览器. 三者之间的流程为: 数据库存储售书网站的数据; 模拟浏览器以会话的形式并发访问网站页面; 当请求发送给Web服务器查询相应网页和图像时, Web服务器紧接着与数据库通信, 传输数据并动态生成响应页. 实验配置如表1所示, 三者间的工作原理如图2所示.

表 1 实验配置

图 2 三者间工作原理

本文选取了内存消耗速率作为加速寿命测试中的加速压力, 对Java虚拟机的内存管理进行研究. 由于所有的Servlet运行在同一个JVM中, 因此所有对象的数据都存储在JVM堆中[11]. 为了模拟软件老化现象, 实验修改了购书网站中的Search Request Page这个页面, 对应TPCW_search_request_servlet这个Servlet, 为其注入一段内存泄漏代码. 由于JVM有垃圾回收器(GC), 程序在运行时, 对象的堆内存由GC的自动内存管理系统回收, 当JVM内存使用量逐渐增加并达到最大值时, GC将自动启动并释放内存. GC回收任何不再被引用的对象, 其占用的内存也会被释放. 为了模拟软件老化现象, 本文增加一个HeapLeak类, 使服务器整个生命周期都保持对该类对象的引用, 且HeapLeak类对象在程序运行期间不会被GC回收, 当创建的实例数量达到最大堆容量时, 会产生JVM堆溢出. 运行客户端, 每隔1 s采集一次JVM内存使用量, 共持续14 400 s, 采集样本14 281个. 每隔120 s取一次均值, 实验数据图如图3所示.

3.2 实验分析

为了证明模型的有效性, 使用Matlab 2016a编程实现了NPSOSA算法优化的BP神经网络模型, 以及与其对比分析的传统PSOSA-BP、PSO-BP, BP预测模型. 神经网络结构采用3-10-1, 每组实验的工作负载为100个客户端. 实验共收集到14 281个数据, 取前7000个作为训练集, 后7281个作为预测集. 不同的预测模型在实验训练过程中采用的是相同的老化数据, 实验结束后分别得到4个模型的预测与期望输出的对比曲线, 如图4图7所示. 本文选取MAE (平均绝对误差), MSE (均方误差)作为评价标准, 公式如下. 4种不同预测模型的评价指标对比如表2所示.

$MAE = \frac{1}{m}\sum\limits_{i = 1}^m {\left| {({y_i} - \mathop y\limits^ \wedge )} \right|} $ (8)
$MSE = \frac{1}{m}{\sum\limits_{i = 1}^m {({y_i} - \mathop y\limits^ \wedge )} ^2}$ (9)
图 3 JVM在120 s内平均使用内存变化趋势

图 4 BP神经网络预测

图4图7可以看出本文提出的NPSOSA-BP神经网络预测模型, 经引入动态变化惯性权重法, SA算法的优化后, 预测输出曲线与期望输出曲线的拟合效果越来越好, 预测精度也明显提高. 从表2可以得出NPSOSABP神经网络模型相比PSOSA-BP神经网络模型预测精度提高了8%, 相比PSOBP神经网络预测模型提高了10%, 相比BP神经网络模型提高了30%. 由此可以得出, 本文提出的基于新型粒子群退火算法优化的BP神经网络模型相比于其他优化算法在预测精度、拟合效果方面存在明显的优势.

图 5 PSO-BP神经网络预测

图 6 PSOSA-BP神经网络预测

图 7 NPSOSA-BP神经网络预测

表 2 神经网络模型误差对比图

4 结束语

软件老化是影响软件系统性能的重要因素, 本文通过建立一个软件老化测试平台, 为其注入一段内存泄漏代码加速老化, 收集系统老化数据, 根据获取的老化数据构造NPSOSA-BP神经网络预测模型. NPSOSA算法不仅解决了BP神经网络对初始权值和阈值依赖性的问题, 而且克服了PSO算法全局与局部搜索不平衡、早熟收敛相关问题, 提高了神经网络的预测精度. 使得BP神经网络拥有良好的学习能力和泛化能力, 能够很好的应用在软件老化趋势预测方面.

参考文献
[1]
Yan YQ. Variance analysis of software ageing problems. IET Software, 2018, 12(1): 41-48. DOI:10.1049/iet-sen.2016.0290
[2]
Zhao J, Trivedi KS, Grottke M, et al. Ensuring the performance of apache HTTP server affected by aging. IEEE Transactions on Dependable and Secure Computing, 2014, 11(2): 130-141. DOI:10.1109/TDSC.2013.38
[3]
Bovenzi A, Cotroneo D, Pietrantuono R, et al. On the Aging Effects due to concurrency bugs: A case study on MySQL. 2012 IEEE 23rd International Symposium on Software Reliability Engineering. Dallas, TX, USA. 2012. 211–220.
[4]
Machida F, Kim DS, Trivedi KS. Modeling and analysis of software rejuvenation in a server virtualized system with live VM migration. Performance Evaluation, 2013, 70(3): 212-230. DOI:10.1016/j.peva.2012.09.003
[5]
Huang DM, He SQ, He XH, et al. Prediction of wind loads on high-rise building using a BP neural network combined with POD. Journal of Wind Engineering and Industrial Aerodynamics, 2017, 170: 1-17. DOI:10.1016/j.jweia.2017.07.021
[6]
Chen X, Wang T, Liang W. General aircraft material demand forecast based on PSO-BP neural network. International Journal of Control and Automation, 2016, 9(5): 407-418. DOI:10.14257/ijca.2016.9.5.39
[7]
Lu HY, Sriyanyong P, Song YH, et al. Experimental study of a new hybrid PSO with mutation for economic dispatch with non-smooth cost function. International Journal of Electrical Power & Energy Systems, 2010, 32(9): 921-935.
[8]
Zhang YD, Wang SH, Phillips P, et al. Binary PSO with mutation operator for feature selection using decision tree applied to spam detection. Knowledge-Based Systems, 2014, 64: 22-31. DOI:10.1016/j.knosys.2014.03.015
[9]
蒋美云. 遗传模拟退火算法在云调度中的应用研究. 计算机与现代化, 2013(6): 38-41. DOI:10.3969/j.issn.1006-2475.2013.06.011
[10]
Yin YC, Coolen FPA, Coolen-Maturi T. An imprecise statistical method for accelerated life testing using the power-Weibull model. Reliability Engineering and System Safety, 2017, 167: 158-167. DOI:10.1016/j.ress.2017.05.045
[11]
刘飞. Java虚拟机内存管理与内存泄漏. 信息与电脑, 2017(6): 69-71. DOI:10.3969/j.issn.1003-9767.2017.06.025