A Bi-objective Synergy Optimization Algorithm of Ant Colony for Scheduling on Non-identical Parallel Batch Machines
-
摘要: 利用用户的偏好信息, 提出一种基于蚁群的双目标协同优化算法(Bi-objective synergy ant colony optimization algorithm based on Pareto domination, PDACO)并用于求解平行批处理机调度问题. 考虑在一组差异容量并带有不同加工功率的平行批处理机器上, 加工带有不同到达时间、尺寸和加工时间的一组工件, 以同时最小化最大完工时间和总能耗. 偏好向量的引入虽然可以提高算法的收敛性, 但会降低解的多样性. 为了弥补这一缺陷, 在本文所提算法中, 利用两个子蚁群分别沿着不同方向, 迭代地进行独立和联合搜索. 最后, 通过大量的仿真实验验证了本文提出算法的有效性.Abstract: The paper proposed a bi-objective synergy optimization algorithm based on ant colony (PDACO) using preference vectors. It is used to solve the batch scheduling problem. These constraints, a set of jobs with different arrival times, sizes, and processing times on a group of parallel batch processing machines (BPMs) with different capacities and different processing powers, are taken into consideration. The objective is to minimize the maximum completion time and the total energy consumption, simultaneously. Although the preference vector is effective to improve the convergence of algorithm, it will deteriorate the diversity of solutions. In order to reduce the adverse effects of the preference vector, two colonies searching solutions in different directions iteratively use the independent and co-operation search approaches in the proposed algorithm. Finally, through extensive simulation experiments, the validity of the algorithm PDACO proposed in this paper is verified.
-
时间序列数据在现实生活中广泛存在, 例如金融领域中的交易数据和经济统计数据、消费电商领域中的用户浏览和购买数据、医疗领域中的医疗器械的信号记录、天气监测站记录的天气指标数据等[1-4]. 这些时间序列数据是相应领域非常宝贵的数据资源, 对这些数据的准确、有效分析和利用有助于减小人力成本, 提高生产效率, 提高经济收益[5].
现实中的时间序列通常具有复杂的非线性动态, 这为时间序列预测带来了困难. 另外, 由于人类活动或自然运动的影响, 时间序列数据常常体现出一定的周期性. 周期性的提取对时间序列预测有着积极意义. 时间序列的趋势同样具有重要的意义, 有时甚至作为预测的目的.
传统的时间序列分析方法源自于自回归模型(Autoregressive model, AR)和移动平滑模型(Mo-ving average, MA). 自回归移动平滑模型(Autoregressive model and moving average, ARMA)和在其基础上发展起来的自回归差分移动平滑模型(Auto-regressive integrated moving average, ARIMA)是时间序列分析的经典方法[6]. 另外, 自回归条件异方差模型(Autoregressive conditional heteroscedasticity, ARCH)[7]和广义自回归条件异方差模型(Gen-eralized autoregressive conditional heteroscedasticity, GARCH)[8]引入了异方差, 对时间序列的波动性进行建模. 基于机器学习的支持向量机回归(Sup-port vactor regression, SVR)和核岭回归(Kernel ridge regression, KRR)等方法在时间序列分析上已经有大量的研究[9-11]. 随着深度学习理论的发展, 循环神经网络(Recurrent neural networks, RNNs)已经成为处理时间序列数据的主流, 在大量应用场景中取得了不俗的效果[12-13]. 回声状态网络(Echo state network, ESN)也是时间序列预测的常用模型[14].
传统的时间序列分析方法基于平稳性假设[15], 对短期平稳的时间序列有较好的预测效果, 但是难以对复杂非线性时间序列数据进行有效建模. SVR和KRR等机器学习方法使用滑动窗口的方式处理预测序列, 忽略了时间序列数据的序列属性, 不能很好地捕捉时间序列中的长时依赖. 同时SVR和KRR受限于模型容量, 难以达到预测非线性时间序列的最佳效果. 深度神经网络由于其超强的拟合能力, 在复杂非线性时间序列数据的处理方面有着天然的优势. 同样对于分割后的序列窗口, 深度神经网络仍能从中捕捉时间序列的长期依赖.
能源领域是产生大量时间序列的领域, 如电力用量数据、风力序列数据、太阳能数据和电力价格数据等. 其中, 电力价格是能源市场上的关键因素, 影响着能源市场的流通和运行. 能源市场的自由属性使电力价格具备了金融商品性质, 但其还受到电力传输和需求量的影响. 电力传输受电网传输容量的限制, 而电力需求量受人类活动和天气因素的影响. 在这些影响因素下, 电力价格数据呈现出长期复杂非线性动态, 体现出高波动性. 另外电力价格还存在着明显的周期性.
传统的时间序列预测方法对电力价格的预测已有大量研究和应用[16], 而循环神经网络在电力价格预测中同样取得了不错的效果[17]. 针对能源领域时间序列的周期性属性, 传统的方法主要采用信号处理方法, 而常规的循环神经网络中并没有对时间序列的周期性进行建模的模块. 目前, 许多研究针对数据的周期性展开, 主要研究工作有: Clements等[18]提出了多方程时间序列方法, 在方程中加入了周期设定, 对澳洲能源市场的电力负载进行预测; Anbazhagan等[19]使用离散余弦变换处理原始序列, 并用神经网络进行建模; Rafiei等[20]使用小波变换处理原始序列, 并用极限学习机对分解结果进行建模等.
针对循环神经网络难以对时间序列数据的周期性直接进行建模的问题, 本文结合时间序列周期分解的思想, 设计了循环神经网络的周期损失和趋势损失, 分别对时间序列中的周期和趋势进行辅助建模; 在多任务学习框架下, 将周期损失、趋势损失和模型自身的损失函数相结合, 联合优化循环神经网络. 提出的模型用于能源市场的电力价格预测, 实验结果取得了较好的预测精度, 验证了周期和趋势对时间序列预测的作用, 说明本文提出的周期损失和趋势损失能够有效地辅助模型捕捉数据特征.
1. 循环神经网络
循环神经网络是常用的建模时间序列的神经网络模型. 循环神经网络使用基于时间的反向传播算法(Back-propagation through time, BPTT)来训练网络.
1.1 基础循环单元
基础的循环神经网络及其展开形式如图1所示. 其数学形式为
$$ h_t = f\left( {Ux_t +Wh_{t-1} } \right) $$ (1) $$ o_t = g\left( {Vh_t } \right) \quad \quad \quad \quad \;\; $$ (2) 其中,
$ U $ ,$ V $ ,$ W $ 都是网络的参数,$ f $ 和$ g $ 表示激活函数, 可以是ReLU、sigmoid和tanh等非线性函数.$ x_t $ 表示$ t $ 时刻的输入,$ h_t $ 表示$ t $ 时刻网络的隐藏状态,$ o_t $ 表示$ t $ 时刻网络的输出.基础的循环神经网络在训练时会面对梯度爆炸或梯度消失的问题[21].
1.2 长短时记忆网络
为了克服循环神经网络的梯度爆炸和梯度消失问题, Hochreiter等[22]提出了长短时记忆网络(Long short term memory, LSTM). LSTM的内部结构如图2所示.
LSTM的主要思想是引入门控单元和长时记忆单元. 门控单元负责控制长时记忆单元中状态的记忆、修改和遗忘. 同时, LSTM还具有和基础循环神经网络相同的短期记忆单元.
LSTM的数学表示为
$$ f_t = \sigma \left( {W_f \left[ {h_{t-1} ,x_t } \right]+b_f } \right) \quad \quad \!\!\!$$ (3) $$ i_t = \sigma \left( {W_i \left[ {h_{t-1} ,x_t } \right]+b_i } \right) \quad \quad $$ (4) $$ o_t = \sigma \left( {W_o \left[ {h_{t-1} ,x_t } \right]+b_o } \right) \quad \quad \!\!\!$$ (5) $$ \tilde {C}_t = \tanh \left( {W_C \left[ {h_{t-1} ,x_t } \right]+b_C } \right) $$ (6) $$ C_t = i_t \tilde {C}_t +f_t C_{t-1} \quad \quad \quad \quad \quad \!\!\! $$ (7) $$ h_t = o_t \tanh \left( {C_t } \right) \quad \quad \quad \quad \quad\quad $$ (8) 其中,
$ C_t $ 和$ \tilde {C}_t $ 分别表示$ t $ 时刻的长期记忆和短期记忆,$ f_t $ ,$ i_t $ 和$ o_t $ 分别表示LSTM的遗忘门、输入门和输出门在$ t $ 时刻的值.$ \left( {W_f ,b_f } \right) $ ,$ \left( {W_i ,b_i } \right) $ ,$ \left( {W_o ,b_o } \right) $ 和$ \left( {W_C ,b_C } \right) $ 分别表示LSTM的遗忘门、输入门、输出门和长时记忆单元的参数.$ \sigma $ 代表sigmoid函数.$ x_t $ 表示$ t $ 时刻的输入,$ h_t $ 表示$ t $ 时刻隐藏状态的输出.由于引入了门控单元和长时记忆单元, 状态的更新方式从乘性增量更新变为了加性增量更新[23], 从而一定程度上避免了梯度消失问题.
1.3 门控循环单元
门控循环单元(Gate recurrent unit, GRU)[24]是LSTM的一个重要变体. 相比于LSTM, GRU进行了一定的简化: 将遗忘门和输入门合并成为一个门控单元, 称为更新门; 去除了长期记忆单元, 与隐藏状态混合, 保留短期记忆单元; 去除了输出门, 改为重置门. GRU的内部结构如图3所示.
GRU的数学表示为
$$ z_t = \sigma \left( {W_z \left[ {h_{t-1} ,x_t } \right]} \right) \quad \quad \quad $$ (9) $$ r_t = \sigma \left( {W_r \left[ {h_{t-1} ,x_t } \right]} \right) \quad \quad \quad $$ (10) $$ \tilde {h}_t = \tanh \left( {W\left[ {r_t \times h_{t-1} ,x_t } \right]} \right) $$ (11) $$ h_t = \left( {1-z_t } \right)h_{t-1} +z_t \tilde {h}_t \quad \quad $$ (12) 其中,
$ \tilde {h}_t $ 表示$ t $ 时刻的短期记忆,$ h_t $ 表示$ t $ 时刻的隐藏状态.$ z_t $ 和$ r_t $ 分别表示GRU的更新门和重置门在$ t $ 时刻的值.$ W_z $ ,$ W_r $ 和$ W $ 分别表示GRU的更新门、重置门和短期记忆单元的参数.GRU大大精简了参数, 相同隐藏状态的GRU的参数量约为LSTM的2/3, 使得模型更不容易过拟合. 本文使用GRU作为默认的循环神经网络模型.
2. 基于周期损失和趋势损失的时间序列预测
结合时间序列周期分解, 设计了循环神经网络的周期损失和趋势损失, 将周期损失、趋势损失和模型自身的损失函数相结合, 在多任务学习框架下, 联合优化循环神经网络.
2.1 周期分解
周期分解是一种对时间序列的周期和趋势建模的经典方式.
周期建模是指, 针对周期性的时间序列, 可以显式的考虑序列跨周期的关系. 周期性的一种形式化表述为
$$ \begin{split} & ACF\left( {x_t ,x_{t-T} } \right)\gg ACF\left( {x_t ,x_{t-\tau } } \right) \\ & \quad \quad \quad \quad \quad \quad \quad \quad \quad \!\!\!\! \forall \tau :od \left( {\tau ,T} \right)\ne 0 \end{split} $$ (13) 其中,
$ ACF $ 代表自相关函数. 周期序列按照周期的延迟序列的自相关性应该远远大于其他的延迟序列.趋势建模是指除了建模每一个具体时间点的具体数值, 还应该捕捉到一段时间的“整体状态”, 包括总体走势、变化范围等因素.
可以认为, 时间序列是趋势、周期和余差的组合. 时间序列的分解可以是加性的, 也可以是乘性的, 即
$$ X_t = T_t +S_t +R_t $$ (14) $$ X_t = T_t \times S_t \times R_t $$ (15) 其中,
$ X_t $ 表示原始时间序列,$ T_t $ 表示趋势分量,$ S_t $ 表示周期分量,$ R_t $ 表示余差. 乘性的组合可以通过对数函数转换为加性组合, 所以这两种组合实质上是一致的.2.2 周期损失函数和趋势损失函数
时间序列的周期分解启发了周期损失函数和趋势损失函数的提出.
周期损失函数鼓励循环神经网络预测的隐藏状态出现周期性. 假设一个循环神经网络的隐藏状态具有周期性, 它的隐藏状态需要满足一定的条件:
$$ \begin{split} \cos nt =\; & h_t +h_{t+1} +\cdots +h_{t+T-1}\cong \\ & h_{t+1} +h_{t+2} +\cdots +h_{t+T} \end{split} $$ (16) 即有
$$ h_t \cong h_{t+T} $$ (17) 为了在循环神经网中加入这样的隐藏状态关系, 在
$ \left[ {t_1 ,t_2 ,\cdots ,t_n } \right] $ 的时间窗上定义如下的周期损失函数$$ \ell _{\rm seasonal} \left( {kT} \right) = \frac{1}{n}\sum\limits_{t = t_1 }^{t_n } {D\left( {h_t ,h_{t+\tau } } \right)} $$ (18) 其中,
$ D\left( {\ast ,\ast } \right) $ 表示距离度量函数,$ \tau $ 表示隐藏状态之间的时间跨度.针对周期为
$ T $ 的时间序列, 一般取$ \tau = kT $ .$ \tau $ 也可以取1, 这样式(18)可以视为循环神经网络的一种正规化方法.$ D\left( {\cdot ,\cdot } \right) $ 一般取平方距离, 此时的周期损失为$$ \ell _{\rm seasonal} \left( {kT} \right) = \frac{1}{nm}\sum\limits_{t = t_1 }^{t_n } {\sum\limits_{i = 1}^m {\left\| {h_t^{\left( i \right)} -h_{t+kT}^{\left( i \right)} } \right\|^2} } $$ (19) 其中,
$ m $ 表示循环神经网络的隐藏状态的维度,$ h_t^{\left( i \right)} $ 表示$ t $ 时刻隐藏状态的第$ i $ 维的值. 更长周期跨度有助于鼓励长距离的周期平稳性.在很多实际应用中, 每个时间点的数值并不是最受关注的问题, 而关注的重点在于捕获某种趋势. 时间序列的趋势可以由一段时间内的均值、最大最小值和波动率来反映.
在
$ \left[ {t_1 ,t_2 ,\cdots ,t_n } \right] $ 的时间窗上对时间序列的趋势进行建模, 从均值、最大最小值和波动率的角度可以得到如下的几个趋势损失函数$$ \begin{split} \ell _{\rm trend}^{\rm MEAN} \left( w \right) =\; & \frac{1}{n}\sum\limits_{t = t_1 }^{t_n } {\left\| {mean\left( {\hat {y}_{t-w+1} ,\cdots ,\hat {y}_t } \right)} \right.}- \\ & \left. {mean\left( {y_{t-w+1} ,\cdots ,y_t } \right)} \right\|^2 \end{split} $$ (20) $$ \begin{split} \ell _{\rm trend}^{\rm MAX} \left( w \right) =\; & \frac{1}{n}\sum\limits_{t = t_1 }^{t_n } {\left\| {\max \left( {\hat {y}_{t-w+1} ,\cdots ,\hat {y}_t } \right)} \right.} - \\ & \left. {\max \left( {y_{t-w+1} ,\cdots ,y_t } \right)} \right\|^2 \end{split}\;\;\;\; $$ (21) $$ \begin{split} \ell _{\rm trend}^{\rm MIN} \left( w \right) =\; & \frac{1}{n}\sum\limits_{t = t_1 }^{t_n } {\left\| {\min \left( {\hat {y}_{t-w+1} ,\cdots ,\hat {y}_t } \right)} \right.} -\\ &\left. {\min \left( {y_{t-w+1} ,\cdots ,y_t } \right)} \right\|^2 \end{split} $$ (22) $$ \begin{split} \ell _{\rm trend}^{\rm VAR} \left( w \right) =\; & \frac{1}{n}\sum\limits_{t = t_1 }^{t_n } {\left\| {var\left( {\hat {y}_{t-w+1} ,\cdots ,\hat {y}_t } \right)} \right.} - \\ & \left. {var\left( {y_{t-w+1} ,\cdots ,y_t } \right)} \right\|^2 \end{split} $$ (23) 其中,
$ \ell _{\rm trend}^{\rm MEAN} $ 、$ \ell _{\rm trend}^{\rm MAX} $ 、$ \ell _{\rm trend}^{\rm MIN} $ 和$ \ell _{\rm trend}^{\rm VAR} $ 分别代表均值趋势损失、最大趋势损失、最小趋势损失和波动趋势损失.$ w $ 表示趋势窗宽, 一般与序列的时间窗宽度$ n $ 不同.$ \hat {y} $ 是循环神经网络的预测值,$ y $ 是真实值.2.3 基于多任务学习的混合预测模型
在机器学习中, 通常只关注一个优化目标. 多任务学习(Multi-task learning)[25]是同时学习多个相关的任务并在这些任务间共享某些底层的特征表示的机器学习方式. 在深度学习中, 多任务学习非常普遍.
一般地, 针对多个优化目标, 多任务学习框架中存在共同优化和分开交替优化两种优化方式. 共同优化适用于紧密相关的任务, 分开交替优化则适用于不相关任务和对抗性任务. 周期性和趋势约束作为时间序列预测的辅助任务, 与预测任务关系密切. 因此, 将周期损失和趋势损失引入优化目标进行共同优化是合理的.
本文根据多任务学习的框架, 将周期损失和趋势损失将作为预测任务的共同优化目标, 在原来的损失函数的基础上, 加入了辅助损失函数, 得到时间序列多任务学习混合模型的优化目标函数
$$ J = L_{\rm main} +\lambda _S \ell _{\rm seasonal} +\ell _{\rm trend} \quad \quad \quad \;$$ (24) $$ \begin{split} \ell _{\rm trend} =\; & \lambda _T^{\rm MEAN} \ell _{\rm trend}^{\rm MEAN} +\lambda _T^{\rm MAX} \ell _{\rm trend}^{\rm MAX}+ \\ & \lambda _T^{\rm MIN} \ell _{\rm trend}^{\rm MIN} +\lambda _T^{\rm VAR} \ell _{\rm trend}^{\rm VAR} \end{split} \;\;\;\; $$ (25) 其中,
$ \lambda _S $ 是周期损失的权重,$ \lambda _{\rm trend}^{\rm MEAN} $ ,$ \lambda _{\rm trend}^{\rm MAX} $ ,$ \lambda _{\rm trend}^{\rm MIN} $ 和$ \lambda _{\rm trend}^{\rm VAR} $ 分别代表对应的趋势损失的权重.引入周期损失和趋势损失的循环神经网络依然可以通过BPTT算法来训练.
3. 仿真实验
3.1 能源市场简介
欧洲能源交易所(European Power Exchange, EPEX)是欧洲最重要的能源交易市场, 覆盖了德国、法国、英国等欧洲最主要的国家. 电力在各个国家的电网之间进行交换, 其中一部分是通过事先规划的方式, 而另一部分则通过能源交易所进行交易. 每个国家都会有自己的子市场, 例如EPEX法国市场. EPEX 法国市场的现货市场主要分为三个子市场: 日前交易市场(Day-ahead market)、日内交易市场(Intraday market)和再平衡市场(Balancing market). 能源市场的实际交易主要发生在日前交易市场. 通常EPEX法国市场的日前交易市场每天形成24个报价, 即每小时一个报价.
图4展示了EPEX法国市场2012年～2015年的一天的不同小时的价格的均值和标准差. 可以看出, 电力价格的标准差非常高, 在均值的1/4以上, 在个别时间段(9:00~11:00)的标准差甚至超出了均值. 这说明EPEX法国市场的电力价格具有超高的波动性. 图5和图6分别展示了EPEX法国市场2012年～2015年每年的日级别平均价格和周级别平均价格. 可以看出, 无论是按日的级别还是周的级别对电价进行统计, 每年的电力价格均呈现非常相似的走势, 体现出明显的周期性.
3.2 实验及结果
选用EPEX法国市场的电力价格数据作为仿真来源. 数据来自日前电力市场, 时间段取自2012年1月1日～2016年6月30日, 其中2012年1月1日～2015年12月31日(共1 461天)的序列数据用来做训练和验证, 2016年1月1日～2016年6月30日(共182天)的序列数据用来做测试. 通常每天有24个时间点(夏令时转换日有23个时间点, 冬令时转换日有25个时间点).
为了保证数据的稳定性, 需要对数据进行预处理, 去除数据的均值和波动率的影响
$$ \tilde {x}_t^h = \frac{x_t^h -\bar {x}_t }{std\left( x \right)} $$ (26) 其中,
$ x $ 代表所有的序列数据,$ h $ 表示序列中的年份信息(2012年~2016年),$ x_t^h $ 表示不同年份的在同一时间点$ t $ 的序列值,$ \bar {x}_t $ 表示$ x_t^h $ 按年份展开的子序列的均值,$ \tilde {x}_t^h $ 为处理后的序列值. 经过这样的变换, 大部分时间点的数据处于[−1, 1]区间, 可以避免出现一些数值问题.实验对比了几种基础的循环神经网络: RNN、LSTM和GRU. 为了分析周期损失和趋势损失的作用, 在GRU的基础上分别添加周期损失、趋势损失或者两者都添加.
循环神经网络需要调整的超参数有: 隐层大小、优化器、初始学习率、批大小(batch size)、训练轮数(epochs)以及延迟窗宽. 针对引入周期损失和趋势损失的GRU, 还需要调整的有: 周期损失系数
$ \lambda _S $ 、周期损失中的周期跨度kT、趋势损失系数($ \lambda _{\rm trend}^{\rm VAR} $ 、$ \lambda _{\rm trend}^{\rm MEAN} $ 、$ \lambda _{\rm trend}^{\rm MAX} $ 和$ \lambda _{\rm trend}^{\rm MIN} $ )和趋势窗宽$ w $ . 这里考虑能源市场的短期周期, 故$ k $ 取1,$ T $ 取24. 由于能源市场的价格预测任务往往不关注每日的平均价格和价格的波动预测的误差,$ \lambda _{\rm trend}^{\rm MEAN} $ 和$ \lambda _{\rm trend}^{\rm VAR} $ 的值都预设为0, 不再纳入超参数选择中. 能源市场的价格预测比较关注一天内的最大最小值, 因此趋势窗宽$ w $ 设为24. 训练时间段的最后一个月(2015年12月)作为验证时间段. 通过在验证时间段内进行多次实验的方式来选取超参数. 选出来的超参数将被用于在完整的训练时间段上的训练. 循环神经网络的超参数设置如表1所示.表 1 循环神经网络的超参数设置Table 1 The hyperparameters of RNN超参数 具体取值 隐层大小 64 优化器 RMSProp, 配合梯度裁剪 初始学习率 0.001 批大小 64 训练轮数 12 延迟窗宽 14 表2列出了周期损失和趋势损失的合理的取值范围.
表 2 周期损失和趋势损失的权重范围Table 2 Weights range of seasonal loss and trend loss权重 取值范围 $\lambda_S $ 0.05~0.15 $\lambda_T^{\rm{MEAN}} $ 0 $\lambda_T^{\rm{MAX}} $ 0.05~0.1 $\lambda_T^{\rm{MIN}} $ 0.05~0.1 $\lambda_T^{\rm{VAR}} $ 0 除了与基础的循环神经网络进行对比, 另外还选取了ARIMA、SVR和KRR作为对比模型. SVR和KRR的超参数均通过在训练时间段内的5折交叉验证直接选取, 均选用3阶多项式核. 为了满足ARIMA模型的静态性要求, 电力价格数据还需要经过特殊处理, 即将序列减去最小值后取对数, 然后进行天级和周级的延迟差分
$$ {p}' = (1-\beta ^{24})(1-\beta ^{168})\ln (p-\min p+1) $$ (27) 实验采用均方根误差(Root mean square error, RMSE)和平均绝对误差(Mean absolute error, MAE)作为评价指标
$$ RMSE = \sqrt {\frac{1}{N}\sum\limits_{t = 1}^N {\left( {\hat {y}_t -y_t } \right)^2} } $$ (28) $$ MAE = \frac{1}{N}\sum\limits_{t = 1}^N {\left| {\hat {y}_t -y_t } \right|} \quad \quad \quad $$ (29) 其中,
$ N $ 表示测试时间段的时间点数. RMSE也是各模型训练时的损失指标.为了更合理地比较趋势损失的影响, 本文还引入了两个额外指标, 最大趋势绝对误差
$ {MAE}^{\rm{MAX}} $ 和最小趋势绝对误差$ {MAE}^{\rm{MIN}} $ , 分别考察模型对每天电力价格最大值和最小值的预测能力$$ \begin{split} MAE^{\rm{MAX}} =\; & \frac{1}{M}\sum\limits_{t = 1}^M {\left| {\max \left( {\hat {y}_{t-w+1} ,\cdots ,\hat {y}_t } \right)} \right.}- \\ & \left. {\max \left( {y_{t-w+1} ,\cdots ,y_t } \right)} \right| \\ \end{split} $$ (30) $$ \begin{split} MAE^{\rm{MIN}} =\; & \frac{1}{M}\sum\limits_{t = 1}^M {\left| {\min \left( {\hat {y}_{t-w+1} ,\cdots ,\hat {y}_t } \right)} \right.}- \\ & \left. {\min \left( {y_{t-w+1} ,\cdots ,y_t } \right)} \right| \\ \end{split} $$ (31) 其中,
$ M $ 表示测试时间段划分的趋势窗的数目.由于神经网络在训练过程中具有一定的随机性, 每次训练的得到的结果都有所不同. 为了保证实验结果的可信性, 对所有循环神经网络采用了重复10次训练并取测试结果的平均值和标准差. 各方法在能源价格预测的结果见表3.
表 3 各种方法的能源价格预测效果对比Table 3 The result comparisons of different methods for electricity price forecasting模型 RMSE MAE ${MAE}^{\rm{MAX}}$ ${MAE}^{\rm{MIN}}$ ARIMA 6.41 4.77 5.15 4.82 SVR 4.91 3.71 4.27 3.34 KRR 5.14 3.75 3.81 3.78 RNN 5.09±0.24 3.75±0.19 3.72±0.28 3.78±0.19 LSTM 4.90±0.18 3.65±0.17 3.65±0.42 3.61±0.26 GRU 4.83±0.19 3.54±0.06 3.64±0.31 3.56±0.26 GRU, $\lambda_S$ = 0.1, $\lambda_T^{\rm{MAX}}$ = 0, $\lambda_T^{\rm{MIN}}$ = 0 4.71±0.16 3.49±0.13 3.53±0.28 3.53±0.15 GRU, $\lambda_S$ = 0.05, $\lambda_T^{\rm{MAX}}$ = 0, $\lambda_T^{\rm{MIN}}$ = 0 4.74±0.11 3.45±0.18 3.53±0.23 3.48±0.26 GRU, $\lambda_S$ = 0 , $\lambda_T^{\rm{MAX}}$ = 0.1 , $\lambda_T^{\rm{MIN}}$ = 0.1 4.85±0.16 3.57±0.20 3.41±0.26 3.41±0.18 GRU, $\lambda_S$ = 0 , $\lambda_T^{\rm{MAX}}$ = 0.05 , $\lambda_T^{\rm{MIN}}$ = 0.05 4.83±0.11 3.54±0.08 3.39±0.18 3.42±0.15 GRU, $\lambda_S$ = 0.1, $\lambda_T^{\rm{MAX}}$ = 0.1 , $\lambda_T^{\rm{MIN}}$ = 0.1 4.68±0.08 3.45±0.03 3.35±0.13 3.33±0.12 GRU, $\lambda_S$ = 0.05, $\lambda_T^{\rm{MAX}}$ = 0.05 , $\lambda_T^{\rm{MIN}}$ = 0.05 4.60±0.15 3.34±0.12 3.38±0.13 3.27±0.11 从实验结果可以看出, 对于电力价格预测这类复杂的时间序列预测问题, ARIMA模型的预测效果不佳, SVR、KRR和RNN的效果接近且远远优于ARIMA模型LSTM和GRU的预测效果比SVR和KRR更好, 而基础的GRU在对比模型中效果最佳. 添加周期损失能对GRU起到比较好的辅助效果, 有助于降低模型的预测误差, 提升预测效果. 趋势损失最直接的影响是显著降低最大趋势误差和最小趋势误差, 说明模型通过趋势损失捕捉到了数据在时间窗内的趋势信息(包括电力价格的极值、均值和变化率等), 这对模型捕捉数据特征的能力起到了有力的补充. 另外可以注意到的是, 加入周期损失也能够降低最大趋势误差和最小趋势误差. 这说明周期损失有助于网络捕捉一些数据的本质特征. 实验结果表明: 同时引入周期损失和趋势损失可以使GRU的性能达到最佳.
引入周期损失和趋势损失的GRU在最佳的参数下(
$ \lambda _S = \lambda _T^{\rm{MAX}} = \lambda _T^{\rm{MIN}} = 0.05 $ )的预测结果如图7所示.
图 7 加入了周期损失和趋势损失的GRU模型的预测结果Fig. 7 The results of electricity price forecasting with seasonal loss and trend loss可以看出, 引入周期损失和趋势损失的GRU对电力价格数据的预测效果不错, 预测曲线对真实数值的走势和变化跟踪准确. 预测曲线具有非常好的周期性, 这体现了周期损失中周期性约束的作用. 同时, 预测曲线更偏向于平稳的预测, 这在一定程度上避免了噪声带来的预测性能损失. 另外, 预测曲线在正常情况下的最大最小值的预测效果很好, 说明趋势损失能够起到有效的监督效果. 但可以观察到的是, 模型在一些极端值(电力价格的异常攀升和下降)上的预测效果不佳. 这涉及到突变的预测问题, 在现有模型框架下难有较好的预测效果.
为了进一步分析周期损失的效果, 将GRU和加入周期损失的GRU在训练一段时间之后的隐藏状态
$ h_t $ 分别抽出, 并将向量$ h_t $ 的均值作对比, 部分结果如图8所示.
图 8 GRU在有无周期损失时的隐藏状态均值的比较Fig. 8 Hidden states of GRU with and without the seasonality由于时间序列本身具有一定的周期性, 使得隐藏状态序列都表现出了一定的周期性. 但是, 使用了周期损失的GRU的隐藏状态明显更加平稳, 并且每个周期内的数值更加平滑; 而未使用周期损失的GRU的隐藏状态的波动性更大, 并且单个周期内的波动也更大. 这些更大的波动可以认为是捕捉到了更多的噪声. 所以, 周期损失有助于捕捉数据更本质的特征而非噪声.
4. 结论
循环神经网络能够提取时间序列中的深层信息, 是非常有效的时间序列预测方法. 本文通过定义周期损失和趋势损失的合理形式, 试图在循环神经网络内对时间序列的周期和趋势进行建模, 改善模型的性能, 建立了基于周期性建模和多任务学习的时间序列预测模型. 在能源市场价格预测的任务的仿真实验表明: 本文提出的周期损失能够有效引导循环神经网络学习数据的周期性, 提升预测效果, 降低数据噪声的影响. 周期损失还有助于模型捕捉数据的本质特征. 趋势损失则能对提升趋势相关的预测任务的预测效果.
-
图 4 (
$ N_1 $ ,$ N_2 $ ),$ K $ ,$ \rho $ ,$ Q $ 不同取值获得的$ H $ 值Fig. 4 The values of
$ H $ under different values of ($ N_1 $ ,$ N_2 $ ),$ K $ ,$ \rho $ and$ Q $ 
图 5
$ ({\alpha _{{\rm{1}}}},{\beta _1}) $ ,$ ({\alpha _{{\rm{2}}}},{\beta _2}) $ 不同取值获得的$ H $ 值Fig. 5 The values of
$ H $ under different values of$ ({\alpha _{{\rm{1}}}},{\beta _1}) $ ,$ ({\alpha _{{\rm{2}}}},{\beta _2}) $ 
图 7 4组不同工件数测试实例目标函数
Fig. 7 Solution distribution on four instances with different number of jobs
表 1 编码实例
Table 1 An example of a solution encoding
Jj b i J1 2 3 J2 1 4 J3 3 2 J4 5 4 J5 4 1 J6 2 3 J7 3 2 J8 5 5 J9 1 4 
下载: 导出CSV
表 2 实例参数
Table 2 The example of the problem
Bbi Rbi PTbi B11 3 7 B21 12 5 B12 5 4 B22 2 5 B32 3 4
下载: 导出CSV
表 3 实验参数设置
Table 3 Experimental parameter settings
参数 符号 取值 工件数 n $n \in $ {90, 108, 126, 144, 162, 180, 216,
252, 306, 360, 432}工件尺寸 $s_j$ ${s_j}\sim $ P$({\lambda_i}),{\lambda _1} = 5,{\lambda _2} = 12.5, $ ${\lambda _3} = 32.5 $ 工件到达时间 rj U [1, R] 工件加工时间 pj U [8, 48] 机器数 $m_i$ m1 = 5, m2 = 3, m3 = 2 机器容量 $S^i$ S 1 = 10, S 2 = 25, S 3 = 65 机器功率 $l^i$ l 1 = 10, l 2 = 35, l 3 = 85
下载: 导出CSV
表 4 比较算法的参数设置
Table 4 The parameter settings of comparative algorithms
PDACO PACO NSGA-II SPEA2 SMPSO $N_1: 50$ $N:100$ $N:100$ $N:100$ $N: 100$ $N_2: 50$ $Q_a: 100$ $Q_a: 100$ $r_1 \in [0,1], r_2 \in[0,1]$ 交叉概率: 1.0 交叉概率: 1.0 交叉概率: 0.9 变异概率: 0.01 变异概率: 0.01 变异概率: 1/L $T_{\max}=200$ $T_{\max}=200$ $T_{\max}=200$ $T_{\max}=200$ $T_{\max}=200$
下载: 导出CSV
表 5 NPS指标值比较结果
Table 5 Comparison of the five algorithms using the NPS metric
工件数 PDACO PACO NSGA-II SPEA2 SMPSO MAX MIN AVG MAX MIN AVG MAX MIN AVG MAX MIN AVG MAX MIN AVG 90 11.10 3.20 6.80 10.40 2.65 6.30 7.75 1.00 2.74 4.25 1.00 1.22 8.4 1.2 4.26 108 11.45 3.00 7.00 10.05 2.75 6.36 7.85 1.00 2.92 5.65 1.00 1.51 7.95 1.4 4.07 126 11.40 3.80 7.24 10.50 2.75 6.28 7.75 1.05 2.84 6.95 1.00 1.73 8.2 1.3 3.99 144 12.85 3.65 7.62 19.15 7.40 13.04 8.80 1.00 3.02 8.05 1.00 1.92 7.9 1.35 4 162 11.50 3.60 7.39 10.50 3.30 6.63 9.70 1.00 3.05 6.95 1.00 1.73 7.35 1.25 3.93 180 12.35 3.45 7.40 11.40 2.55 6.64 8.95 1.00 2.95 7.70 1.00 2.11 8.35 1.25 4.15 216 12.40 3.90 7.75 11.40 3.20 7.04 8.55 1.00 2.71 8.20 1.00 2.11 7.95 1.2 4.03 252 12.45 3.75 7.87 11.35 3.55 7.16 9.25 1.00 2.71 8.60 1.00 2.01 7.6 1.4 4.02 306 12.35 3.60 7.72 11.30 3.20 7.00 8.45 1.00 2.55 8.50 1.00 2.00 8.1 1.3 4.11 360 12.75 3.60 7.79 11.85 3.35 7.40 7.75 1.00 2.42 9.05 1.00 2.06 8.15 1.3 4.21 432 13.15 4.00 8.10 12.15 3.25 7.61 8.05 1.00 2.39 7.65 1.00 1.76 8.2 1.25 4.04
下载: 导出CSV
表 6 覆盖率
$(C) $ 比较结果Table 6 Comparison of the five algorithms using the C metric
工件数 C (PDACO,
PACO)C (PACO,
PDACO)C (PDACO,
NSGA-II)C (NSGA-II,
PDACO)C (PDACO,
SPEA2)C (SPEA2,
PDACO)C (PDACO,
SMPSO)C (SMPSO,
PDACO)90 0.988 0.001 0.801 0.001 0.757 0 0.833 0.021 108 0.971 0.003 0.608 0.001 0.564 0.001 0.743 0.004 126 0.986 0.002 0.656 0 0.599 0 0.647 0 144 0.994 0 0.504 0 0.476 0 0.561 0 162 0.997 0 0.421 0 0.677 0 0.587 0 180 0.999 0 0.554 0 0.533 0 0.533 0 216 0.995 0 0.470 0 0.577 0 0.516 0 252 0.997 0 0.421 0 0.426 0 0.452 0 306 0.997 0 0.529 0 0.645 0 0.513 0 360 0.989 0 0.606 0 0.553 0 0.459 0 432 0.997 0 0.501 0 0.439 0 0.466 0
下载: 导出CSV
表 7 超体
$(H) $ 指标比较结果Table 7 Comparison of the five algorithms using the H metric
工件数 PDACO PACO NSGA-II SPEA2 SMPSO 90 469 603 277 319 110 110 111 396 121 352 108 650 187 403 180 146 403 148 960 147 856 126 933 105 539 363 256 380 236 164 271 332 144 1 232 318 690 126 275 805 303 290 288 495 162 1 472 585 793 386 318 719 358 388 341 864 180 1 814 061 1 000 950 413 532 465 956 428 793 216 2 577 210 1 385 263 560 037 671 642 635 549 252 3 489 851 1 874 024 749 649 888 686 815 992 306 4 969 991 2 614 455 1 079 066 1 314 258 1 179 523 360 6 638 616 3 478 054 1 555 105 1 878 950 1 638 628 432 8 805 782 4 469 622 2 106 786 2 439 180 2 266 835
下载: 导出CSV
表 8 多样性(DVR)、Spacing(SPC)和时间(T)指标比较结果
Table 8 Comparison of the five algorithms using the DVR, SPC and T metrics
工件数 PDACO PACO NSGA-II SPEA2 SMPSO DVR SPC T DVR SPC T DVR SPC T DVR SPC T DVR SPC T 90 137 262 0.89 0.86 89 010 0.82 0.83 17 167 0.26 1.87 4 121 0.04 2.17 21 362 0.36 1.14 108 164 060 0.89 1.08 110 360 0.84 1.13 20 772 0.29 2.39 17 299 0.11 2.96 26 815 0.33 1.28 126 219 865 0.92 1.44 141 594 0.86 1.49 46 860 1.01 2.88 28 803 0.13 3.93 52 619 0.52 1.5 144 256 752 0.91 1.80 166 727 0.84 1.65 24 153 0.29 3.61 59 443 0.22 4.65 39 526 0.23 1.7 162 294 754 0.88 2.30 197 631 0.86 2.53 24 276 0.28 4.43 54 872 0.14 5.62 43 511 0.22 1.83 180 328 732 0.92 2.67 213 904 0.83 3.17 27 072 0.26 5.07 102 915 0.27 6.59 27 342 0.24 2.28 216 435 913 0.94 3.83 290 015 0.90 4.40 21 623 0.25 17.00 133 770 0.27 9.01 25 113 0.24 2.29 252 520 652 0.93 5.05 370 128 0.90 5.94 23 940 0.22 9.43 179 343 0.23 12.87 34 619 0.25 2.57 306 664 941 0.94 7.36 451 475 0.89 8.53 24 801 0.24 20.53 293 842 0.27 21.12 33 428 0.24 3.07 360 800 856 0.91 10.33 535 670 0.93 12.33 23 838 0.19 27.58 431 781 0.28 27.80 49 734 0.26 3.46 432 1 010 000 0.96 14.77 789 834 0.94 17.54 23 959 0.17 36.70 374 310 0.19 40.10 66 253 0.21 4.03
下载: 导出CSV
-
[1] Ahmadi J H, Ahmadi R H, Dasu S, Tang C S. Batching and scheduling jobs on batch and discrete processors. Operations research, 1992, 40(4): 750−763 doi: 10.1287/opre.40.4.750 [2] 原豪男, 郭戈. 交通信息物理系统中的车辆协同运行优化调度. 自动化学报, 2019, 45(1): 143−152Yuan Hao-Nan, Guo Ge. Vehicle cooperative optimization scheduilng intransportation cyber physical systems. Acta Automatica Sinica, 2019, 45(1): 143−152 [3] Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 1994, 32(7): 1615−1635 doi: 10.1080/00207549408957026 [4] Ikura Y, Gimple M. Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 1986, 5(2): 61−65 doi: 10.1016/0167-6377(86)90104-5 [5] 赵玉芳, 唐立新. 极小化最大完工时间的单机连续型批调度问题. 自动化学报, 2006, 32(5): 730−737Zhao Yu-Fang, Tang Li-Xin. Scheduling a single continuous batch processing machine to minimize makespan. Acta Acta Automatica Sinica, 2006, 32(5): 730−737 [6] Zhou H M, Pang J H, Chen P K, Chou F D. A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes. Computers and Industrial Engineering, 2018, 123: 67−81 [7] Chang P Y, Damodaran P, Melouk S. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 2004, 42(19): 4211−4220 doi: 10.1080/00207540410001711863 [8] Jia Z H, Wang Y, Wu C, Yang Y, Zhang X Y, Chen H P. Multi-objective energy-aware batch scheduling using ant colony optimization algorithm. Computer and Industrial Engineering, 2019, 131: 41−56 [9] Shi Z S, Huang Z W, Shi L Y. Customer order scheduling on batch processing machines with incompatible job families. International Journal of Production Research, 2018, 56(1-2): 795−808 doi: 10.1080/00207543.2017.1401247 [10] Zhou S C, Xie J H, Du N, Pang Y. A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capcities and arbitrary job sizes. Applied Mathematics and Computation, 2018, 334: 254−268 doi: 10.1016/j.amc.2018.04.024 [11] Arroyo J E C, Leung J Y T. Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Computers and Operations Research, 2017, 78: 117−128 [12] 陆志强, 刘欣仪. 考虑资源转移时间的资源受限项目调度问题的算法. 自动化学报, 2018, 44(6): 1028−1036Lu Zhi-Qiang, Liu Xin-Yi. Algorithm for resource-constrained project scheduling problem with resource transfer time. Acta Automatica Sinica, 2018, 44(6): 1028−1036 [13] Zhou S C, Li X L, Du N, Pang Y, Chen H P. A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Computers and Operations Research, 2018, 96: 55−68 [14] Du B, Chen H P, Huang G Q, Yang H D. Preference vector ant colony system for minimising make-span and energy consumption in a hybrid flow shop. Multi-objective Evolutionary Optimisation for Product Design and Manufacturing. Springer-London, 2011. 279–304 [15] Jia Z H, Zhang Y L, Leung J Y T, Li K. Bi-criteria ant colony optimization algorithm for minimizing makespan and energy consumption on parallel batch machines. Applied Soft Computing, 2017, 55: 226−237 doi: 10.1016/j.asoc.2017.01.044 [16] 汪恭书, 刘静宜, 唐立新. 连铸–轧制混流生产模式下轧批调度问题的分支–定价算法. 自动化学报, 2017, 43(7): 1178−1189Wang Gong-Shu, Liu Jing-Yi, Tang Li-Xin. Branch-and-price algorithm for rolling batch scheduling problem in continuous-casting and rolling processes with hybrid production mode. Acta Automatica Sinica, 2017, 43(7): 1178−1189 [17] 郎劲, 唐立新. 考虑爬坡约束的油井间抽批调度问题. 自动化学报, 2019, 45(2): 388−397Lang Jin, Tang Li-Xin. Batch scheduling problem of oil well considering ramping constraints in oilfield production. Acta Automatica Sinica, 2019, 45(2): 388−397 [18] Zhao B X, Gao J M, Chen K, Guo K. Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines. Journal of Intelligent Manufacturing, 2018, 29(1): 93−108 doi: 10.1007/s10845-015-1091-z [19] Wu Y, Gong M G, Ma W P, Wang S F. High-order graph matching based on ant colony optimization. Neurocomputing, 2019, 328: 97−104 doi: 10.1016/j.neucom.2018.02.104 [20] Eskandari L, Jafarian A, Rahimloo P, Baleanu D. A modified and enhanced ant colony optimization algorithm for traveling salesman problem. Mathematical Methods in Engineering. Springer-Cham, 2019. 257–265 [21] Stützle T, Hoos H H. MAX-MIN ant system. Future Generation Computer Systems, 2000, 16(8): 889−914 doi: 10.1016/S0167-739X(00)00043-1 [22] Jia Z H, Leung J Y T. A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes. European Journal of Operational Research, 2015, 240(3): 649−665 doi: 10.1016/j.ejor.2014.07.039 [23] Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Proceedings of the 2000 International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2000. 849–858 [24] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-Report, 2001, 103 [25] Nebro A J, Durillo J J, Garcia-Nieto J, Coello C C A, Luna F, Alba E. SMPSO: A new PSO-based metaheuristic for multi-objective optimization. In: Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making. IEEE, 2009. 66–73 [26] Wang J Q, Leung J Y T. Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan. International Journal of Production Economics, 2014, 156: 325−331 doi: 10.1016/j.ijpe.2014.06.019 [27] Jia Z H, Li X H, Leung J Y T. Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities. Future Generation Computer Systems, 2017, 67: 22−34 期刊类型引用(2)
1. 卢弘，王耀南，乔非，方遒. 面向可持续生产中多任务调度的双重增强模因算法. 自动化学报. 2024(04): 731-744 . 
本站查看2. 李瑞，龚文引. 改进的基于分解的多目标进化算法求解双目标模糊柔性作业车间调度问题. 控制理论与应用. 2022(01): 31-40 . 百度学术其他类型引用(13)
-
下载:
计量
- 文章访问数: 1812
- HTML全文浏览量: 83
- PDF下载量: 195
- 被引次数: 15
