﻿ 改进回溯搜索优化回声状态网络时间序列预测
 计算机系统应用  2020, Vol. 29 Issue (1): 236-243 PDF

Time Series Forecasting Based on Echo State Network Optimized by Improved Backtracking Search Optimization Algorithm
HU Shuai, XIAO Zhi-Hua, RAO Qiang, LIAO Rong-Tao
Information & Communication Branch, State Grid Hubei Electric Power Co. Ltd., Wuhan 430077, China
Foundation item: Scientific and Technological Project of State Grid Hubei Electric Power Co. Ltd. ( 52153317000B)
Abstract: Echo State Network (ESN) owns simple network structure and is coupled with a time parameter and thus it shows important theoretical and application values in time series forecasting. In this study, we propose to optimize the output weight matrix by Adaptive Backtracking Search optimization Algorithm (ABSA) to overcome overfitting problem caused by linear regression algorithm. ABSA adopts adaptive mutation factor strategy to replace the strategy of randomly given mutation factor in standard BSA to achieve the balance between convergence accuracy and convergence rate. Experimental results show that the ESN optimized by ABSA outperforms the basic ESN without optimization and the ESNs optimized by other EAs.
Key words: time series forecasting     Echo State Network (ESN)     Adaptive Backtracking Search optimization Algorithm (ABSA)     forecasting model     evolutionary algorithm

2004年, Jaeger等[4]提出了一种全新的递归神经网络——回声状态网络(Echo State Network, ESN). ESN最显著特征是网络训练过程简单: 只有储备池(隐藏层)到输出层的输出连接权值矩阵需要计算, 其他各层之间的连接权值矩阵在网络初始化阶段随机生成并保持不变. ESN能够克服传统递归神经网络的网络结构难以确定、训练效率低下、收敛速度慢、容易陷入局部最优等缺点, 因而应用广泛. 例如网络流量预测[5]、变风量空调内模控制[6]和非线性卫星信道盲均衡[7]等. 标准的ESN在计算输出连接权值矩阵时会采用最小二乘估计或者岭回归等线性方法, 这类方法在节约计算成本的同时会造成网络过拟合. 因此, 对ESN的输出连接权值矩阵进行优化以提升其性能具有现实意义.

1 相关知识 1.1 回声状态网络

 图 1 回声状态网络的标准结构

ESN在时刻 $n$ 的输入, 储备池神经元的状态和输出层神经元输出分别表示如下:

 $u(n) = {({u_1}(n),{u_2}(n), \cdots ,{u_K}(n))^{\rm{T}}}$ (1)
 $x(n) = {({x_1}(n),{x_2}(n), \cdots ,{x_N}(n))^{\rm{T}}}$ (2)
 $y(n) = {({y_1}(n),{y_2}(n), \cdots ,{y_L}(n))^{\rm{T}}}$ (3)

 $x(n{\rm{ + }}1) = f({{\rm{W}}^{\rm in}}u(n + 1) + {\rm{W}}x(n))$ (4)
 $y(n + 1) = {f^{\rm out}}({{\rm{W}}^{\rm out}}u(n + 1))$ (5)

1.2 回溯搜索算法及其改进

 图 2 标准BSA算法流程

 $F = {F_{\min}} + ({F_{\max}} - {F_{\min}}) \times {e^{1 - \tfrac{{GenM}}{{GenM - G + 1}}}}$ (6)

2 预测模型 2.1 模型介绍

(1) ESN. 标准的ESN模型.

(2) GA_ESN. 使用遗传算法(Genetic Algorithm, GA)优化ESN输出连接权值矩阵.

(3) DE_ESN. 使用差分进化算法(Differential Evolution, DE) 优化ESN输出连接权值矩阵.

(4) BSA_ESN. 使用标准回溯搜索算法(BSA)优化ESN输出连接权值矩阵.

(5) ABSA_ESN. 使用自适应回溯搜索算法(ABSA)优化ESN输出连接权值矩阵.

2.2 ESN的优化流程

ESN的 ${{\rm{W}}^{\rm out}}$ 优化流程分为以下几个步骤:

Step 1. 设置ESN参数并收集网络输入产生的状态矩阵.

Step 2. 设置ABSA (GA, DE或BSA)的参数并生成初始化种群. 设置ABSA的初始迭代代数 $G = 0$ .

Step 3. 判断ABSA (GA, DE或BSA)的迭代是否达到最大迭代次数. 如果当前迭代次数 $G$ 等于最大迭代次数 $GenM$ , 则ABSA (GA, DE或BSA)的迭代过程结束, 获得最优种群和最优个体; 否则, 流程继续执行.

Step 4. 依次执行ABSA (GA, DE或BSA)的选择I (或没有)、自适应变异(或变异)、交叉和选择II (或选择)等几个操作, 获得当前迭代过程 $G$ 的新种群.

Step 5. 计算新种群中每个个体的适应值, 按照贪婪选择原则更新当前迭代过程的种群. 比较当前迭代过程获得的最优个体与当前获得的全局最优个体的适应值, 适应值较小的将作为新的全局最优适应值且相应的个体更新为全局最优个体.

Step 6. 更新 $G = G + 1$ . 返回Step 3.

Step 7. 将进化算法获得的最优个体设置为ESN的最优输出连接权值矩阵 ${{\rm{W}}^{\rm out}}$ , ESN网络训练完成.

Step 8. 将测试集中样本按顺序输入到训练好的ESN中, 进行预测.

 图 3 利用ABSA (GA, DE或BSA)优化ESN的 ${{\rm{W}}^{\rm out}}$ 的流程图

2.3 模型合理性分析及模型比较

(1) ESN是最先进的时间序列预测模型之一. ESN因为其网络结构简单、训练效率高且耦合“时间参数”, 因而能够有效地应用于时间序列预测问题研究. 然而, 标准的ESN计算地输出连接权值矩阵容易致使网络陷入过拟合状态, 影响ESN性能的发挥.

(2) GA_ESN, DE_ESN和BSA_ESN是优化的ESN预测模型. GA、DE和BSA 3种智能算法的算法流程、算子和参数个数不尽相同. 使用3种智能算法对ESN进行优化的目的是克服标准ESN容易陷入网络过拟合状态的缺陷, 增加优化方法的多样性. 相对于GA和DE, BSA在全局寻优时只有一个参数需要设定, 在很大程度上能够简化算法参数设置过程, 进而节约计算成本.

(3) ABSA_ESN是采用改进BSA优化的ESN预测模型. 标准BSA的参数变异因子在算法初始化过程中随机给定并在整个过程中保持不变, 这种策略难以平衡BSA算法的搜索能力和收敛速率. ABSA是采用自适应变异因子策略改进的BSA, 其能够有效地克服上述缺陷. 具体而言, ABSA在迭代初期变异因子取值较大, 能够扩大搜索范围从而保证种群的多样性. 此时, ABSA的收敛速度较慢且收敛精度较低. 随着迭代过程的进行, 变异因子的取值将逐渐变小, 种群的搜索范围将围绕已经获得的优秀个体展开以保证优秀个体将会以较大概率被保留. 此时, ABSA的收敛速度和收敛精度逐步加快和提高. 总体而言, ABSA_ESN在算法的参数设置、收敛速度和收敛精度上较GA_ESN, DE_ESN和BSA_ESN等均有优势.

3 数值实验和结果分析 3.1 实验设置

3.2 数据集及性能评估标准

3.2.1 NARMA模型

NARMA模型方程式表示如下:

 $y(t) = 0.7e(t - \delta ) + 0.1 + (1 - y(t - 1))y(t - 1)$ (7)

 图 4 NARMA模型输入序列

 图 5 NARMA模型输出序列

3.2.2 Mackey-Glass混沌系统

Mackey-Glass时间序列是从时延差分系统导出, 其方程如式(8)所示:

 $\frac{{{\rm d}x(t)}}{{{\rm d}t}} = - cx(t) + \frac{{ax(t - \tau )}}{{1 + {x^b}(t - \tau )}}$ (8)

 图 6 Mackey-Glass时间序列

3.2.3 性能评估标准

 $RMSE = \sqrt {\frac{1}{k}\sum\limits_{t = 1}^k {{{({{\hat y}_t} - {y_t})}^2}} }$ (9)

3.3 参数设置与分析 3.3.1 参数设置

3.3.2 自适应变异因子F取值分析

ABSA的变异因子F取值如图7所示. 从图中可以看出, 在算法迭代初期变异因子F取值较大(第一个迭代阶段, F取值为最大设定值0.9). 此时, ABSA的种群中的个体以较大概率进行变异, ABSA主要是在种群个体空间中进行全局寻优, 形成的新种群个体随机分布在个体空间之中且个体之间的关联性较小. 可以说, ABSA在迭代初期的全局寻优能力非常强而局部寻优能力非常弱, 种群个体的相似性很小. 随着迭代过程的更迭, 变异因子F取值逐步减小, ABSA种群中的优秀个体逐渐沉淀并且这些优秀个体以逐渐减小的概率进行变异. 此时, ABSA逐渐由全局寻优转变为局部寻优. 新种群的形成主要是围绕已经获得的优秀个体进行局部寻优. 即随着迭代的进行, ABSA的局部寻优能力逐渐加强而全局寻优能力逐渐减弱, 种群个体的相似性逐渐加强. 直到迭代进行到后期(图7中的迭代次数达到90次左右), 变异因子F取值趋于稳定(最小设定值0.1), ABSA已经由全局寻优过渡到局部寻优. 此时, ABSA全局寻优能力非常弱而局部寻优能力非常强. 所以, ABSA的自适应变异因子取值策略能够平衡算法的全局寻优能力和局部寻优能力.

 图 7 ABSA的变异因子F取值曲线

3.4 参数设置与分析

 图 8 NARMA上5种模型的预测值和期望值

 图 9 Mackey-Glass上5种模型的预测值和期望值

3.4.1 优化的ESN与标准的ESN

3.4.2 ABSA_ESN与其他4种模型

(1)当单独关注NARMA或者Mackey-Glass数据集时, ABSA_ESN能够比ESN、GA_ESN、DE_ESN和BSA_ESN等模型在两个数据集上都能获得更好的预测结果, 主要表现在ABSA_ESN在两个数据集上的预测精度提升比例分别为16.19%/36.36%、37.59%/37.62%、9.23%/28%和8.33%/22.22%.

(2)当关注所有5种预测模型在两个数据集上的总体性能时, ABSA_ESN模型比其他4个模型在预测精度上也有大幅提升. ABSA_ESN模型相对于ESN、GA_ESN、DE_ESN和BSA_ESN等模型的平均相对误差提升比例分别为26.28%、37.61%、18.64%和15.28%. 这个信息如表4中最后一列“MEAN”所示.

4 结束语

 [1] Lee Giles C, Lawrence S, Tsoi AC. Noisy time series prediction using recurrent neural networks and grammatical inference. Machine Learning, 2001, 44(1–2): 161-183. [2] Zhang GQ, Patuwo BE, Hu MY. Forecasting with artificial neural networks:: The state of the art. International Journal of Forecasting, 1998, 14(1): 35-62. DOI:10.1016/S0169-2070(97)00044-7 [3] Wang L, Wang ZG, Qu H, et al. Optimal forecast combination based on neural networks for time series forecasting. Applied Soft Computing, 2018, 66: 1-17. DOI:10.1016/j.asoc.2018.02.004 [4] Jaeger H, Haas H. Harnessing nonlinearity: Predicting chaotic systems and saving energy in wireless communication. Science, 2004, 304(5667): 78-80. DOI:10.1126/science.1091277 [5] 田中大, 高宪文, 李树江, 等. 遗传算法优化回声状态网络的网络流量预测. 计算机研究与发展, 2015, 52(5): 1137-1145. DOI:10.7544/issn1000-1239.2015.20131757 [6] 王华秋, 王斌, 龙建武. 回声状态网络在变风量空调内模控制中的应用. 重庆理工大学学报(自然科学), 2017, 31(6): 120-126, 153. [7] 杜晟磊. 基于回声状态网络的非线性卫星信道盲均衡. 科技创新与应用, 2017(30): 19-21. [8] 宗宸生, 郑焕霞, 王林山. 改进粒子群优化BP神经网络粮食产量预测模型. 计算机系统应用, 2018, 27(12): 204-209. DOI:10.15888/j.cnki.csa.006651 [9] 朱海龙, 陶晶, 俞凯, 等. 基于GA-BP神经网络的胎儿体重预测分析. 计算机系统应用, 2018, 27(3): 162-167. DOI:10.15888/j.cnki.csa.006252 [10] Chouikhi N, Ammar B, Rokbani N, et al. PSO-based analysis of Echo State Network parameters for time series forecasting. Applied Soft Computing, 2017, 55: 211-225. DOI:10.1016/j.asoc.2017.01.049 [11] Wang HS, Yan XF. Optimizing the echo state network with a binary particle swarm optimization algorithm. Knowledge-Based Systems, 2015, 86: 182-193. DOI:10.1016/j.knosys.2015.06.003 [12] Jaeger H. The " echo state” approach to analysing and training recurrent neural networks-with an erratum note. Bonn: German National Research Center for Information Technology GMD Technical Report, 2001. [13] Civicioglu P. Backtracking search optimization algorithm for numerical optimization problems. Applied Mathematics and Computation, 2013, 219(15): 8121-8144. DOI:10.1016/j.amc.2013.02.017 [14] Wang S, Da XY, Li MD, et al. Adaptive backtracking search optimization algorithm with pattern search for numerical optimization. Journal of Systems Engineering and Electronics, 2016, 27(2): 395-406. DOI:10.1109/JSEE.2016.00041 [15] Madasu SD, Kumar MLSS, Singh AK. Comparable investigation of backtracking search algorithm in automatic generation control for two area reheat interconnected thermal power system. Applied Soft Computing, 2017, 55: 197-210. DOI:10.1016/j.asoc.2017.01.018 [16] Chaib AE, Bouchekara HREH, Mehasni R, et al. Optimal power flow with emission and non-smooth cost functions using backtracking search optimization algorithm. International Journal of Electrical Power & Energy Systems, 2016, 81: 64-77. [17] 庞世伟, 于开平, 邹经湘. 基于时变NARMA模型的非线性时变系统辨识. 工程力学, 2006, 23(12): 25-29. DOI:10.3969/j.issn.1000-4750.2006.12.005 [18] MacKey MC, Glass L. Oscillation and chaos in physiological control systems. Science, 1977, 197(4300): 287-289. DOI:10.1126/science.267326 [19] Farmer JD. Chaotic attractors of an infinite-dimensional dynamical system. Physics D: Nonlinear Phenomena, 1982, 4(3): 366-393. DOI:10.1016/0167-2789(82)90042-2 [20] Bauer E, Kohavi R. An empirical comparison of voting classification algorithms: Bagging, boosting, and variants. Machine Learning, 1999, 36(1–2): 105-139.