Improved Differential Evolution Parameter Control and Bidirectional Scheduling Algorithm for the Resource-constrained Project
-
摘要: 针对资源约束项目调度组合优化难题, 提出一种改进的动态差分进化参数控制及双向调度算法.通过参数时变衰减与个体优劣评价, 自适应控制个体进化参数, 提高算法的收敛性能、勘探与开发最优解的能力; 基于动态差分进化(Dynamic differential evolution, DDE), 提出一种双向调度算法, 使用满足任务时序约束的优先数编码、交替正向反向调度, 结合标准化编码调整与精英保留的种群随机重建策略, 建立了一种高效稳健的双向编码调整机制.通过著名的项目调度问题库(Project scheduling problem library, PSPLIB)中实例集测试, 并与其他文献算法比较最优解平均偏差率, 验证了所提算法的有效性与优越性.Abstract: Aiming at the resource-constrained project scheduling problem (RCPSP) which is one of the most intractable combinatorial optimization problems, an improved dynamic differential evolution parameter control method and a bidirectional scheduling algorithm are proposed. Through parameters time-varying attenuation and individual objective evaluation, evolution parameters are adaptively controlled to improve the convergence performance of the algorithm and the ability of exploring and exploiting the optimal solution. Based on the dynamic differential evolution, a bidirectional scheduling algorithm, which uses time precedence constrained activity coding, alternating forward-backward scheduling and combinatorial strategies of standardized coding adjustment and elitist reserved population random reconstruction, is designed to establish an efficient and robust bidirectional coding adjustment mechanism. Through testing the instance set of the wellknown project scheduling problem library (PSPLIB) and comparing the average deviation rate with those of other algorithms, the proposed algorithm shows its effectiveness and superior performance.
-
Key words:
- Resource-constrained project /
- dynamic differential evolution /
- parameter control /
- bidirectional scheduling
-
状态估计在信号处理、计算机视觉、自动控制、目标跟踪、导航、金融、通信等领域[1-6]有着广泛应用.在高斯噪声环境下, 卡尔曼滤波(Kalman fllter, KF)[7]及其次优滤波算法可以很好解决该问题.在非高斯噪声环境下, KF算法及其次优滤波算法不再适用, 因此存在着粒子滤波(Particle filter, PF)[8]及其衍生滤波算法来解决状态估计问题.
基于无迹变换(Unscented transform, UT)的无迹卡尔曼滤波(Unscented Kalman fllter, UKF)[9-11]是一种计算非线性变换均值和协方差的次优卡尔曼滤波算法.相比于扩展卡尔曼滤波(Extended Kalman fllter, EKF), UKF不需要计算雅可比矩阵, 且其可以达到非线性函数二阶泰勒展开式的精度[9].因此其在导航制导、目标跟踪、信号处理和图像跟踪等方面有着很广泛应用.但UKF算法也存在着在某些情况下估计效果差等问题.
目前, 针对UKF算法估计值不准确的问题, 有众多改进方法.为了解决UKF在工程应用中因舍入误差导致数值不稳定的问题, 提出了求根UKF (Square-root unscented Kalman fllter, SRUKF)[12]算法.在加性噪声条件下, 为了降低UKF算法的计算复杂度, 提出了简化UKF (Simplified unscented Kalman fllter, SUKF)[13]算法.在先验信息不确定性大而量测精度高的情况下, 只用一次量测值的UKF算法的估计效果较差.因此, 提出了多次利用量测值的迭代UKF (Iterated unscented Kalman fllter, IUKF)[14], 递归更新滤波器(递归更新扩展卡尔曼滤波(Recursive update extended Kalman fllter, RUEKF)[15]、递归更新容积卡尔曼滤波(Recursive update cubature Kalman fllter, RUCKF)[16])等算法.基于二阶UT变换的UKF算法滤波估计精度只能达到二阶, 为了提高滤波精度, 提出了基于高阶UT变换和高阶容积变换(Cubature transform, CT)的高阶UKF[17-18]和高阶容积卡尔曼滤波(Cubature Kalman fllter, CKF)[19-21]等算法.
UKF及其改进算法虽然可以较好处理UKF算法的估计不准确的问题, 但其仍然存在在非线性程度高的环境下估计效果差等问题, 文献[22-23]中提出将UKF算法作为PF算法建议分布, 将UKF算法估计值作为重要性密度函数, 这就是无迹粒子滤波(Unscented particle fllter, UPF)[22-23]算法.从理论上讲, 随着随机采样粒子数量提高, UPF算法的精度可以逐渐提高.但UPF算法也存在一些问题, 如其运算时间很长, 时效性较差.且UPF算法效果不总是好于UKF算法, 在量测噪声较大时, UPF算法估计精度会不如UKF算法.
为了在低计算负载的情况下获得高的滤波估计精度, 本文提出了双层无迹卡尔曼滤波器(Double layer unscented Kalman filter, DLUKF)算法.其核心思想是用带有权值的采样点表示前一个时刻的后验密度函数; 而后用内层的UKF算法对每个带权值的采样点进行更新, 并用最新的量测值对采样点的权值进行更新; 然后将各个采样点进行加权融合, 得到了初始的估计值; 最后用外层UKF算法的更新机制对初始估计值进行更新得到最终的估计值.
1. 无迹卡尔曼滤波(UKF)算法
1.1 UT变换
假设非线性函数为$\mathit{\boldsymbol{y}} = \mathit{\boldsymbol{f}}(\mathit{\boldsymbol{x}}) $, UT变换是通过近似非线性函数的概率密度分布来近似非线性函数.其在得到先验均值$\bar {\mathit{\boldsymbol{x}}}$和协方差$ {\mathit{\boldsymbol{P}}_{xx}}$的基础上, 用采样策略选取一组确定性采样点集.而后得到这些采样点集经非线性变换后的采样点集, 进而求得经非线性变换后的均值$\bar {\mathit{\boldsymbol{y}}}$和协方差${\mathit{\boldsymbol{P}}_{yy}}$.
UT变换算法可以归纳为以下三步:
1) 根据先验均值$\bar {\mathit{\boldsymbol{x}}}$和协方差${\mathit{\boldsymbol{P}}_{xx}}$, 用采样策略得到$N$个确定性采样点$\{ {\mathit{\boldsymbol{x}}_i}\} _{i = 1}^N$.定义$w_i^m$为均值加权作用的权值, $w_i^c$为协方差加权所用的权值.
2) 将确定性采样点$\{ {\mathit{\boldsymbol{x}}_i}\} _{i = 1}^N$进行非线性$\mathit{\boldsymbol{f}}(\cdot) $变换, 得到$N$个经非线性变换后的采样点集$\{ {\mathit{\boldsymbol{y}}_i}\} _{i = 1}^N = \mathit{\boldsymbol{f}}(\{ {\mathit{\boldsymbol{x}}_i}\} _{i = 1}^N) $.
3) 通过对采样点集$\{ {\mathit{\boldsymbol{y}}_i}\} _{i = 1}^N$进行加权的形式得到经非线性变换后的均值和协方差为.
1.2 UKF算法
考虑典型的非线性系统, 其状态方程和量测方程分别为:
$ \begin{equation} {\mathit{\boldsymbol{x}}_{k + 1}} = \mathit{\boldsymbol{f}}({\mathit{\boldsymbol{x}}_k}) + {\mathit{\boldsymbol{w}}_k} \end{equation} $
(1) $ \begin{equation} {\mathit{\boldsymbol{z}}_{k + 1}} = \mathit{\boldsymbol{h}}({\mathit{\boldsymbol{x}}_{k + 1}}) + {\mathit{\boldsymbol{v}}_{k + 1}} \end{equation} $
(2) ${\mathit{\boldsymbol{x}}_k}$为$k$时刻$n$维的状态向量, ${\mathit{\boldsymbol{z}}_{k + 1}}$为$k + 1$时刻的量测向量. ${\mathit{\boldsymbol{w}}_k}$为$m$维的过程噪声, 其服从均值为0方差为$\mathit{\boldsymbol{Q}}$的高斯分布. ${\mathit{\boldsymbol{v}}_{k + 1}}$为$q$维的量测噪声, 其服从均值为0方差为$\mathit{\boldsymbol{R}}$的高斯分布.滤波算法的目的就是从带有噪声的量测值${\mathit{\boldsymbol{z}}_{k + 1}}$中估计出真实值${\mathit{\boldsymbol{x}}_{k + 1}}$.
UKF[9-10]算法是基于UT变换的一种滤波算法, 其思想是在一步预测的时候, 用UT变换来进行均值和协方差传递.在UKF算法中, 因为存在噪声项, 需要对状态进行扩维.因此状态向量可以表示为. UKF算法流程为:
1) 在$k$时刻由UT变换中的采样策略得到$N$个采样点集$\{ \mathit{\boldsymbol{x}}_k^i\} _{i = 1}^N$.
2) 采样点集$\{ \mathit{\boldsymbol{x}}_k^i\} _{i = 1}^N$经非线性变换$\mathit{\boldsymbol{f}}(\cdot) $后得到采样点集$\{ \mathit{\boldsymbol{x}}_{k + 1|k}^i\} _{i = 1}^N$.
3) 由采样点集$\{ \mathit{\boldsymbol{x}}_{k + 1|k}^i\} _{i = 1}^N$加权求得预测值${\hat {\mathit{\boldsymbol{x}}}_{k + 1|k}}$和预测协方差${\hat {\mathit{\boldsymbol{P}}}_{k + 1|k}}$.
4) 采样点集$\{ \mathit{\boldsymbol{x}}_{k + 1|k}^i\} _{i = 1}^N$经非线性变换$\mathit{\boldsymbol{h}}(\cdot) $后得到采样点集$\{ \mathit{\boldsymbol{z}}_{k + 1|k}^i\} _{i = 1}^N$.
5) 由采样点集$\{ \mathit{\boldsymbol{z}}_{k + 1|k}^i\} _{i = 1}^N$加权求得预测的量测值${\hat {\mathit{\boldsymbol{z}}}_{k + 1|k}}$及其协方差${\mathit{\boldsymbol{P}}_{zz}}$和互协方差${\mathit{\boldsymbol{P}}_{xz}}$.
6) 求得$k + 1$时刻的估计值${\hat {\mathit{\boldsymbol{x}}}_{k + 1}}$及和协方差${\hat {\mathit{\boldsymbol{P}}}_{k + 1}}$.
在实际应用中, 受初始误差的影响, UKF算法存在着收敛速度慢, 精度不高等问题.基于此, 文献[14]提出了IUKF算法, 文献[15]提出了RUEKF算法, 文献[16]出了RUCKF算法.这三种算法的核心思想都是多次利用量测值对估计值进行更形, 以获得更好的滤波估计效果.
2. 无迹粒子滤波(UPF)算法
UPF[22-23]算法是在PF算法的基础上, 用UKF算法的滤波估计值作为PF算法的建议密度函数.这虽然可以解决UKF算法不适用于非高斯环境等问题, 但其由于要选取大量的随机性采样点来逼近密度函数, 所以UPF算法会临着计算量大的问题. UPF算法具体步骤如下:
1) 由$p({\mathit{\boldsymbol{x}}_0}) $得到$N$个粒子点$\{ \mathit{\boldsymbol{x}}_0^{(i)}\} _{i = 1}^N$, 初始权值为$\mathit{\boldsymbol{w}}_0^{(i)} = 1/N$.
2) 用UKF算法对每一粒子进行状态更新.
3) 计算粒子点对应的权值$\mathit{\boldsymbol{w}}_k^{(i)} = \mathit{\boldsymbol{w}}_{k - 1}^{(i)}\frac{{p({\mathit{\boldsymbol{z}}_k}|\mathit{\boldsymbol{x}}_k^{(i)})p(\mathit{\boldsymbol{x}}_k^{(i)}|\mathit{\boldsymbol{x}}_{k - 1}^{(i)})}}{{q(\mathit{\boldsymbol{x}}_k^{(i)}|{\mathit{\boldsymbol{z}}_{1:k}})}}$并对其归一化.
4) 当粒子退化严重时, 对粒子进行重采样.
5) 计算每个粒子点${\mathit{\boldsymbol{x}}^{(i)}}$对应的协方差.
6) 重复步骤2)~5).
最后得到$k$时刻状态量的估计为${\hat {\mathit{\boldsymbol{x}}}_k} = \sum\nolimits_{i = 1}^N {\tilde {\mathit{\boldsymbol{w}}}_k^{(i)}\mathit{\boldsymbol{x}}_k^{(i)}} $.
3. 双层无迹卡尔曼滤波(DLUKF)算法
UPF需要用大量的粒子点去逼近状态的后验密度函数, 因此其有着运算量大的问题.本文所提的DLUKF算法用带权值的采样点去表征状态的后验密度函数, 其核心思想为用内层的UKF对每个带权值的采样点进行更新, 而后用最新的量测值对每个采样点的权值进行更新, 并对更新后的采样点进行加权求和得到下一时刻初始估计值, 然后将该初始估计值作为预测值运行外层UKF算法, 从而得到最终估计值.
3.1 DLUKF算法框架
DLUKF算法由外层UKF算法和内层UKF算法组成, 其算法流程如下:
状态初始条件为初始值${\hat {\mathit{\boldsymbol{x}}}_0} = {\rm E}({\mathit{\boldsymbol{x}}_0}) $, 初始协方差${\hat {\mathit{\boldsymbol{P}}}_0} = {\rm E}(({\mathit{\boldsymbol{x}}_0} - {\hat {\mathit{\boldsymbol{x}}}_0}){({\mathit{\boldsymbol{x}}_0} - {\hat {\mathit{\boldsymbol{x}}}_0})^{\rm T}}) $.因为存在噪声项, 需要对初始的状态进行扩维处理.其可以表示为
$ \begin{equation} \hat {\mathit{\boldsymbol{x}}}_0^a = {\left[ {\begin{array}{*{20}{c}} {{{\hat {\mathit{\boldsymbol{x}}}}_0}}&0&0 \end{array}} \right]^{\rm T}} \end{equation} $
(3) $ \begin{equation} \mathit{\boldsymbol{P}}_0^a = {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{P}}_0}}&0&0\\ 0&\mathit{\boldsymbol{Q}}&0\\ 0&0&\mathit{\boldsymbol{R}} \end{array}} \right]^{\rm T}} \end{equation} $
(4) 内层UKF算法:
在$k$时刻, 用采样策略选取$N$个采样点$\{ {\hat {\mathit{\boldsymbol{x}}}_{i, k}}\} _{i = 1}^N$, 并求取其权值对应的一阶矩$w_{i, k}^m$和二阶矩$w_{i, k}^c$.而后用内层UKF算法对每个采样点进行更新.
对每个采样点, 用采样策略选取$M$个采样点$ \{ {\hat {\mathit{\boldsymbol{x}}}_{j, i, k}}\} _{j = 1}^M$, 并取其对应的一阶矩$w_{j, i, k}^m$和二阶矩$w_{j, i, k}^c$.
时间更新:
$ \begin{equation} \hat {\mathit{\boldsymbol{x}}}_{j, i, k + 1|k}^x = \mathit{\boldsymbol{f}}(\hat {\mathit{\boldsymbol{x}}}_{j, i, k}^x, \hat {\mathit{\boldsymbol{x}}}_{j, i, k}^w) \end{equation} $
(5) $ \begin{equation} {\hat {\mathit{\boldsymbol{x}}}_{i, k + 1|k}} = \sum\limits_{j = 1}^M { w_{j, i, k}^m\hat {\mathit{\boldsymbol{x}}}_{j, i, k + 1|k}^x} \end{equation} $
(6) $ \begin{align} {{\hat {\mathit{\boldsymbol{P}}}}_{i, k + 1|k}} = &\sum\limits_{j = 1}^M {w_{j, i}^c(\hat {\mathit{\boldsymbol{x}}}_{j, i, k + 1|k}^x - {{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1|k}})}\times\nonumber\\& {(\hat {\mathit{\boldsymbol{x}}}_{j, i, k + 1|k}^x - {{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1|k}})^{\rm T}} + \mathit{\boldsymbol{Q}} \end{align} $
(7) 量测更新:
基于预测值${\hat {\mathit{\boldsymbol{x}}}_{i, k + 1|k}}$和预测协方差${\hat {\mathit{\boldsymbol{P}}}_{i, k + 1|k}}$产生新的$M$个带权值的采样点.
$ \begin{equation} {\mathit{\boldsymbol{z}}_{j, i, k + 1|k}} = \mathit{\boldsymbol{h}}(\mathit{\boldsymbol{x}}_{j, i, k + 1|k}^x, \mathit{\boldsymbol{x}}_{j, i, k + 1|k}^v) \end{equation} $
(8) $ \begin{equation} {\hat {\mathit{\boldsymbol{z}}}_{i, k + 1|k}} = \sum\limits_{j = 1}^M {w_{j, i}^m{\mathit{\boldsymbol{z}}_{j, i, k + 1|k}}} \end{equation} $
(9) $ \begin{align} {\mathit{\boldsymbol{P}}_{i, zz}} = & \sum\limits_{j = 1}^M {w_{j, i}^c({\mathit{\boldsymbol{z}}_{j, i, k + 1|k}} - {{\hat {\mathit{\boldsymbol{z}}}}_{i, k + 1|k}})}\times \nonumber\\& {({\mathit{\boldsymbol{z}}_{j, i, k + 1|k}} - {{\hat {\mathit{\boldsymbol{z}}}}_{i, k + 1|k}})^{\rm T}} + \mathit{\boldsymbol{R}} \end{align} $
(10) $ \begin{align} {\mathit{\boldsymbol{P}}_{i, xz}} = &\sum\limits_{j = 1}^M w_{j, i}^c(\hat {\mathit{\boldsymbol{x}}}_{j, i, k + 1|k}^x - {{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1|k}})\times \nonumber\\&{{({\mathit{\boldsymbol{z}}_{j, i, k + 1|k}} - {{\hat {\mathit{\boldsymbol{z}}}}_{i, k + 1|k}})}^{\rm T}} \end{align} $
(11) $ \begin{equation} {\mathit{\boldsymbol{K}}_{i, k + 1}} = {\mathit{\boldsymbol{P}}_{i, xz}}\mathit{\boldsymbol{P}}_{i, zz}^{ - 1} \end{equation} $
(12) $ \begin{equation} {\hat {\mathit{\boldsymbol{x}}}_{i, k + 1}} = {\hat {\mathit{\boldsymbol{x}}}_{i, k + 1|k}} + {\mathit{\boldsymbol{K}}_{i, k + 1}}({\mathit{\boldsymbol{z}}_{k + 1}} - {\hat {\mathit{\boldsymbol{z}}}_{i, k + 1|k}}) \end{equation} $
(13) $ \begin{equation} {\hat {\mathit{\boldsymbol{P}}}_{i, k + 1}} = {\hat {\mathit{\boldsymbol{P}}}_{i, k + 1|k}} - {\mathit{\boldsymbol{K}}_{i, k + 1}}{\mathit{\boldsymbol{P}}_{i, zz}}\mathit{\boldsymbol{K}}_{i, k + 1}^{\rm T} \end{equation} $
(14) 在采样点用内层UKF算法更新后, 类似于UPF算法, 表示一阶矩的权值和表示二阶矩的权值的更新可以表示为:
$ \begin{equation} \left\{ {\begin{array}{*{20}{c}} {w_i^m = w_i^m\frac{{p({\mathit{\boldsymbol{z}}_{k + 1}}|{{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}})p({{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}}|{{\hat {\mathit{\boldsymbol{x}}}}_{i, k}})}}{{q({{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}}|{\mathit{\boldsymbol{z}}_{1:k}})}}}\\ {w_i^c = w_i^c\frac{{p({\mathit{\boldsymbol{z}}_{k + 1}}|{{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}})p({{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}}|{{\hat {\mathit{\boldsymbol{x}}}}_{i, k}})}}{{q({{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}}|{\mathit{\boldsymbol{z}}_{1:k}})}}} \end{array}} \right. \end{equation} $
(15) 在得到权值更新的基础上, 对权值进行归一化处理, 有
$ \begin{equation} \left\{ {\begin{array}{*{20}{c}} {w_i^m = \frac{{w_i^m}}{{\sum\limits_{i = 1}^N {w_i^m} }}}\\ {w_i^c = \frac{{w_i^c}}{{\sum\limits_{i = 1}^N {w_i^c} }}} \end{array}} \right. \end{equation} $
(16) $k + 1$时刻的初始估计值及其协方差可以表示为
$ \begin{equation} \hat {\mathit{\boldsymbol{x}}}_{k + 1}^I = \sum\limits_{i = 1}^N {w_i^m{{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}}} \end{equation} $
(17) $ \begin{equation} \hat {\mathit{\boldsymbol{P}}}_{k + 1}^I = \sum\limits_{i = 1}^N {w_i^c({{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}} - \hat {\mathit{\boldsymbol{x}}}_{k + 1}^I){{({{\hat {\mathit{\boldsymbol{x}}}}_{i, k + 1}} - \hat {\mathit{\boldsymbol{x}}}_{k + 1}^I)}^{\rm T}}} + \mathit{\boldsymbol{Q}} \end{equation} $
(18) 外层UKF算法:
基于$\hat {\mathit{\boldsymbol{x}}}_{k + 1}^I$和$\hat {\mathit{\boldsymbol{P}}}_{k + 1}^I$, 用采样策略选取$N$个带权值的采样点$ \{ \mathit{\boldsymbol{x}}_{i, k + 1}^I\} _{i = 1}^N$.而后再次对粒子点进行量测更新, 可以表示为:
$ \begin{equation} \mathit{\boldsymbol{z}}_{i, k + 1}^I = \mathit{\boldsymbol{h}}(\mathit{\boldsymbol{x}}_{i, k + 1}^{I, x}, \mathit{\boldsymbol{x}}_{i, k + 1}^{I, v}) \end{equation} $
(19) $ \begin{equation} \hat {\mathit{\boldsymbol{z}}}_{k + 1}^I = \sum\limits_{j = 1}^N {w_i^m\mathit{\boldsymbol{z}}_{i, k + 1}^I} \end{equation} $
(20) $ \begin{equation} \mathit{\boldsymbol{P}}_{zz}^I = \sum\limits_{i = 1}^N {w_i^c(\mathit{\boldsymbol{z}}_{i, k + 1}^I - \hat {\mathit{\boldsymbol{z}}}_{k + 1}^I){{(\mathit{\boldsymbol{z}}_{i, k + 1}^I - \hat {\mathit{\boldsymbol{z}}}_{k + 1}^I)}^{\rm T}}} + \mathit{\boldsymbol{R}} \end{equation} $
(21) $ \begin{equation} \mathit{\boldsymbol{P}}_{xz}^I = \sum\limits_{i = 1}^N {w_i^c(\mathit{\boldsymbol{x}}_{i, k + 1}^{I, x} - \hat {\mathit{\boldsymbol{x}}}_{k + 1}^I){{(\mathit{\boldsymbol{z}}_{i, k + 1}^I - \hat {\mathit{\boldsymbol{z}}}_{k + 1}^I)}^{\rm T}}} \end{equation} $
(22) $ \begin{equation} \mathit{\boldsymbol{K}}_{k + 1}^I = \frac{{\mathit{\boldsymbol{P}}_{xz}^I}}{{\mathit{\boldsymbol{P}}_{zz}^I}} \end{equation} $
(23) $ \begin{equation} {\hat {\mathit{\boldsymbol{x}}}_{k + 1}} = \hat {\mathit{\boldsymbol{x}}}_{k + 1}^I + \mathit{\boldsymbol{K}}_{k + 1}^I({\mathit{\boldsymbol{z}}_{k + 1}} - \hat {\mathit{\boldsymbol{z}}}_{k + 1}^I) \end{equation} $
(24) $ \begin{equation} {\hat {\mathit{\boldsymbol{P}}}_{k + 1}} = \hat {\mathit{\boldsymbol{P}}}_{k + 1}^I - \mathit{\boldsymbol{K}}_{k + 1}^I\mathit{\boldsymbol{P}}_{zz}^I{(\mathit{\boldsymbol{K}}_{k + 1}^I)^{\rm T}} \end{equation} $
(25) 不断重复方程(5)~(25), 即可求得DLUKF算法在每个时刻的估计值${\hat x_k}$.
DLUKF算法的流程图如图 1所示.
3.2 基于对称采样策略的DLUKF算法
根据选取粒子点的采样策略不同, 又可以得到多种DLUKF算法.在UT变换中, 目前的采样策略方法包括对称采样、单形采样、3阶矩偏度采样和高斯分布4阶矩对称采样[8]等.还有为了保证经过非线性变换后协方差${\mathit{\boldsymbol{P}}_{yy}}$的正定性而提出的对基本采样策略进行比例修正的算法框架.
下面主要详细介绍对称采样策略.
考虑均值$\bar {\mathit{\boldsymbol{x}}}$和协方差${\mathit{\boldsymbol{P}}_{xx}}$的情况下, 通过对称采样的策略选取$N = 2n + 1$个采样点.采样点及其权值可以表示为:
$ \begin{equation} \left\{ \begin{array}{l} {\mathit{\boldsymbol{x}}^{(1)}} = \bar {\mathit{\boldsymbol{x}}}\\ \{ {\mathit{\boldsymbol{x}}^{(i)}}\} _{i = 2}^{N - n} = \bar {\mathit{\boldsymbol{x}}} + \sqrt {(n + \kappa )} {(\sqrt {{\mathit{\boldsymbol{P}}_{xx}}} )_{i - 1}}\\ \{ {\mathit{\boldsymbol{x}}^{(i)}}\} _{i = N - n + 1}^N = \bar {\mathit{\boldsymbol{x}}} - \sqrt {(n + \kappa )} {(\sqrt {{\mathit{\boldsymbol{P}}_{xx}}} )_{i - n + 1}} \end{array} \right. \end{equation} $
(26) $ \begin{equation} \left\{ \begin{array}{l} w_1^m = w_1^c = \frac{{\kappa }}{{n + \kappa }}\\ \{ w_i^m\} _{i = 2}^N = \{ w_i^c\} _{i = 2}^N = \frac{{1}}{{2n + 2\kappa }} \end{array} \right. \end{equation} $
(27) 式(26)中的$n$表示均值$\bar {\mathit{\boldsymbol{x}}}$维数. $\kappa $为比例参数, 可调节采样点与均值$\bar x$间的距离, 仅影响二阶以后高阶矩带来的误差. $ {(\sqrt {{\mathit{\boldsymbol{P}}_{xx}}})_i}$表示平方根矩阵的第$i$列或行.
在对称采样策略中, 采样点除了中心点外, 其他的采样点的权值是相同的.这说明除中心点外, 其他采样点的重要性是相同的.从采样点的分布可以看出, 采样点是关于中心点呈中心对称的.
基于对称采样的DLUKF算法就是在产生粒子点时用对称采样策略产生粒子点, 其具体的算法流程如下:
1) $k$时刻的估计值为${\hat {\mathit{\boldsymbol{x}}}_k}$, 协方差为${\hat {\mathit{\boldsymbol{P}}}_k}$.
2) 基于${\hat {\mathit{\boldsymbol{x}}}_k}$和${\hat {\mathit{\boldsymbol{P}}}_k}$, 通过式(26)和式(27)求得外层UKF算法$N$个采样点$\{ {\hat {\mathit{\boldsymbol{x}}}_{i, k}}\} _{i = 1}^N$, 及其权值对应的一阶矩$w_{i, k}^m$和二阶矩$w_{i, k}^c$.
3) 通过方程(5) $ \sim $ (14)得到每个粒子经内层UKF更新后的粒子点$\{ {\hat {\mathit{\boldsymbol{x}}}_{i, k + 1}}\} _{i = 1}^N$及其协方差$\{ {\hat {\mathit{\boldsymbol{P}}}_{i, k + 1}}\} _{i = 1}^N$.
4) 通过方程(15) $ \sim $ (16)得到外层UKF更新后的权值$\{ w_i^m\} _{i = 1}^N$和$\{ w_i^c\} _{i = 1}^N$.
5) 通过方程(17) $ \sim $ (18), 得到$k + 1$时刻的初始估计值$\hat {\mathit{\boldsymbol{x}}}_{k + 1}^I$及其协方差$\hat {\mathit{\boldsymbol{P}}}_{k + 1}^I$.
6) 基于$\hat {\mathit{\boldsymbol{x}}}_{k + 1}^I$和$\hat {\mathit{\boldsymbol{P}}}_{k + 1}^I$, 通过式(26)和式(27)求得$N$个采样点$\{ \mathit{\boldsymbol{x}}_{i, k + 1}^{I}\} _{i = 1}^N$.
7) 通过方程(19) $ \sim $ (25), 得到$k + 1$时刻的估计值为${\hat {\mathit{\boldsymbol{x}}}_{k + 1}}$, 协方差为${\hat {\mathit{\boldsymbol{P}}}_{k + 1}}$.
4. 仿真分析
将本文所提的基于对称采样策略DLUKF算法与UKF算法、IUKF算法、RUEKF算法、RUCKF算法、高阶UKF算法、高阶UKF算法和UPF算法分别在一维和二维仿真场景下进行仿真对比分析, 用滤波算法估计值与真实值间的均方根误差(Root mean square error, RMSE)来表示滤波算法估计效果.
4.1 单维仿真
假设有下述状态空间模型, 其状态方程和量测方程分别可以表示为:
$ \begin{equation} {x_{k + 1}} = 0.5{x_k} + \sin (0.04\pi k) + 1 + {w_k} \end{equation} $
(28) $ \begin{equation} {z_{k + 1}} = 0.2x_{k + 1}^2 + {v_{k + 1}} \end{equation} $
(29) 式(28)中${w_k}$表示过程噪声, 其服从$Ga(3, 2) $的伽马分布.式(29)中的${v_{k + 1}}$表示量测噪声, 其服从均值为0, 方差为的高斯分布.初始位置为${x_0} = 3$, IUKF算法, RUEKF算法和RUCKF算法的迭代次数都为10次. UPF算法粒子数量为100个, DLUKF算法产生粒子的方法是对称采样策略.仿真时间为30 s, 蒙特卡洛仿真次数为100次.其仿真结果如图 2所示.
通过图 2可以看出, IUKF算法、RUEKF算法、RUCKF算法、高阶UKF算法、高阶UKF算法和UPF算法滤波估计效果都略好于UKF算法.这是因为IUKF算法、RUEKF算法、RUCKF算法、高阶UKF算法、高阶UKF算法和UPF算法都对UKF算法进行了改进, 所以其效果是好于UKF算法的.本文所提的DLUKF算法在每个时刻的估计效果都好于其他的滤波算法.这说明, DLUKF算法对于UKF算法的改进效果比其他经典算法更加显著.且因为DLUKF算法用两层UKF算法对状态进行估计, 所以可以有着很好的滤波估计效果.
将UPF算法的粒子数由100逐渐增加到500, 其与UKF算法、IUKF算法、RUEKF算法、RUCKF算法、高阶UKF算法、高阶UKF算法和DLUKF算法的单次运行时间以及平均RMSE如表 1所示.
表 1 各算法计算时间及RMSE对比分析表Table 1 The calculation time and RMSE of each algorithm算法 运行时间(s) 平均RMSE UKF 0.0002 0.1566 IUKF 0.0014 0.0881 RUEKF 0.0006 0.0378 RUCKF 0.0031 0.0337 高阶UKF 0.0006 0.1434 高阶CKF 0.0006 0.1437 UPF (100) 0.1032 0.1153 UPF (200) 0.2097 0.0714 UPF (300) 0.3200 0.0626 UPF (400) 0.4296 0.0564 UPF (500) 0.5416 0.0476 DLUKF 0.0016 0.0297 通过表 1可以看出, UKF算法、RUEKF算法、高阶UKF算法和高阶CKF算法的用时都很少. IUKF算法、RUCKF和DLUKF算法的用时略长, 这是由于这三种算法都进行了多次滤波计算. UPF算法用时最长.在UPF算法中, 随着粒子数目的增多, 用时也是逐渐增加.在RMSE方面, DLUKF算法比另外7种方法小很多.在UPF算法中, 随着粒子数增多, RMSE也是逐渐变小的.但当500个粒子点时, UPF算法RMSE依然是DLUKF算法的两倍.这说明了基于带权值的采样点表征后验分布的方法是优于随机点表征后验分布的.
4.2 多维仿真
考虑一个二维匀速直线运动的例子, 其状态方程和量测方程分别为:
$ \begin{equation} {\mathit{\boldsymbol{{\rm{X}}}}_{k + 1}} = \mathit{\boldsymbol{F}}{\mathit{\boldsymbol{X}}_k} + {\mathit{\boldsymbol{w}}_k} \end{equation} $
(30) $ \begin{equation} {\mathit{\boldsymbol{Z}}_{k + 1}} = \mathit{\boldsymbol{h}}({\mathit{\boldsymbol{X}}_{k + 1}}) + {\mathit{\boldsymbol{v}}_{k + 1}} \end{equation} $
(31) 式(30)中, ${{\mathit{\boldsymbol{X}}_k} = [{x_k}, {\dot x_k}, {y_k}, {\dot y_k}]^{\rm T}}$是状态变量, 分别表示$x$轴和$y$轴方向的位置和速度. ${\mathit{\boldsymbol{w}}_k}$为过程噪声, 其服从均值为0, 方差为$\mathit{\boldsymbol{Q}}$的高斯分布.其中, $\mathit{\boldsymbol{F}}$和$\mathit{\boldsymbol{Q}}$分别可以表示为
$ \begin{equation} \mathit{\boldsymbol{F}} = \left[ {\begin{array}{*{20}{c}} 1&T&0&0\\ 0&1&0&0\\ 0&0&1&T\\ 0&0&0&1 \end{array}} \right] \end{equation} $
(32) $ \begin{equation} \mathit{\boldsymbol{Q}} = {q^2}\left[ {\begin{array}{*{20}{c}} {\frac{T^3}{3}}&{\frac{T^2}{2}}&0&0\\ {\frac{T^2}{2}}&T&0&0\\ 0&0&{\frac{T^3}{3}}&{\frac{T^2}{2}}\\ 0&0&{\frac{T^2}{2}}&T \end{array}} \right] \end{equation} $
(33) 式(31)中, ${\mathit{\boldsymbol{Z}}_{k + 1}} = {[{r_{k + 1}}, {\theta _{k + 1}}]^{\rm T}}$为观测变量, 分别表示对目标的径向距和方位角. ${\mathit{\boldsymbol{v}}_{k + 1}}$为量测噪声, 其为闪烁噪声, 可以表示为:
$ \begin{align} p({\mathit{\boldsymbol{v}}_{k + 1}}) = &(1 - \varepsilon ){p_1}({\mathit{\boldsymbol{v}}_{k + 1}}) + \varepsilon {p_2}({\mathit{\boldsymbol{v}}_{k + 1}}) = \nonumber\\& (1 - \varepsilon )N({\mathit{\boldsymbol{v}}_{k + 1}};0, {\mathit{\boldsymbol{R}}_1}) + \varepsilon N({\mathit{\boldsymbol{v}}_{k + 1}};0, {\mathit{\boldsymbol{R}}_2}) \end{align} $
(34) 量测方程$\mathit{\boldsymbol{h}}(\cdot) $可以表示为:
$ \begin{equation} \mathit{\boldsymbol{h}}({\mathit{\boldsymbol{X}}_{k + 1}}) = {\left[ {\begin{array}{*{20}{c}} {\sqrt {x_{k + 1}^2 + y_{k + 1}^2} }&{\arctan (\frac{{{y_{k + 1}}}}{{{x_{k + 1}}}})} \end{array}} \right]^{\rm{T}}} \end{equation} $
(35) 式(34)中, ${\mathit{\boldsymbol{R}}_1}$和${\mathit{\boldsymbol{R}}_2}$分别可以表示为
$ \begin{equation} {\mathit{\boldsymbol{R}}_1} = \left[ {\begin{array}{*{20}{c}} {\sigma _{1r}^2}&0\\ 0&{\sigma _{1\varepsilon }^2} \end{array}} \right] \end{equation} $
(36) $ \begin{equation} {\mathit{\boldsymbol{R}}_2} = \left[ {\begin{array}{*{20}{c}} {\sigma _{2r}^2}&0\\ 0&{\sigma _{2\varepsilon }^2} \end{array}} \right] \end{equation} $
(37) 仿真中, 仿真时间为100 s, 蒙特卡洛仿真次数为300次.目标初始位置为(20 000 m, 40 000 m), 初始速度为(-160 m/s, -150 m/s). IUKF算法、RUEKF算法和RUCKF算法的迭代次数都为10次. UPF算法粒子数量为300个, DLUKF算法产生粒子的方法是对称采样策略.
其他的参数设置为:
表 2 仿真参数设置Table 2 The Simulation parameters参数 $T$ $q$ ${\sigma _{1r}}$ ${\sigma _{1\varepsilon }}$ ${\sigma _{2r}}$ ${\sigma _{2\varepsilon }}$ $\varepsilon $ 数值 1 1 20 m 0.2$^{o}$ 200 m 0.2$^{o}$ 0.1 位置的RMSE公式可以表示为$RMS{E_{}} = \sqrt {RMSE_{x}^2 + RMSE_{y}^2} $, 进行仿真分析, 其效果如图 3所示.
图 3是各个算法在位置方面的RMSE, 可以看出, RUEKF算法、RUCKF算法、高阶UKF算法、高阶CKF算法和UKF算法的估计效果基本相同, 而IUKF算法和UPF算法的估计效果优于UKF算法.而本文算法性能是最好的, 这是因为本文算法用带权值的采样点表征后验分布, 这比随机的粒子点表征后验分布更有优势, 故DLUKF算法的RMSE是好于其他滤波算法的.这也说明所提的DLIKF算法对匀速直线运动可以有着很好的滤波估计效果.
在匀速直线运动中, 将UPF算法的粒子数由300逐渐增加到1 000, 其与其他算法的单次运行时间以及位置和速度的平均RMSE如表 3所示.
表 3 各个算法的性能Table 3 The performance of each algorithm算法 运行时间(s) 平均RMSE UKF 0.0059 99.8709 IUKF 0.0424 85.0107 RUEKF 0.0150 100.2616 RUCKF 0.0397 99.8704 高阶UKF 0.0193 100.4763 高阶CKF 0.0191 99.7558 UPF (300) 3.5953 88.2638 UPF (400) 4.8406 86.5004 UPF (500) 6.0552 85.8206 UPF (600) 7.2596 85.1056 UPF (700) 8.4211 84.6700 UPF (800) 9.6178 83.2706 UPF (900) 10.8389 82.9057 UPF (1 000) 12.0105 82.4258 DLUKF 0.0757 78.5559 从表 3可以看出, 本文算法的运算时间虽然略长于UKF算法、IUKF算法、REUKF算法、RUCKF算法, 高阶UKF算法和高阶CKF算法, 却远远小于UPF算法.且由于DLUKF算法的外层UKF算法选取了9个确定性采样点, 所以其运算时间是大约是UKF算法的9倍.在UPF算法中, 随着粒子数目的增多, 运算时间也是逐渐增加的.在各个方面的RMSE、DLUKF算法都是最好的.在UPF算法中, 随着粒子数目的增多, RMSE也是逐渐减小的, 但比起DLUKF算法、UPF算法的RMSE依然是很大的.这说明基于双层采样的的DLUKF算法在多维目标跟踪中有着很好的滤波估计效果.
5. 结论
本文所提的DLUKF算法是在双层UKF算法的基础上, 用采样策略选取带权值的采样点, 而后用内层UKF算法对每个采样点进行更新, 同时用最新的量测对采样点的权值进行更新, 最后通过外层UKF算法的更新机制得到每个时刻的滤波估计值.仿真结果表明, 在一维和二维的仿真场景中, 相比于存在的经典算法, 本文所提的DLUKF算法可以在较短的时间内获得很好的滤波估计效果.
-
图 2 动态差分进化参数控制及双向调度算法流程图
Fig. 2 Flowchart of DDE parameter control and bidirectional scheduling algorithm
图 3 J30系列不同DE方案性能比较
Fig. 3 Comparison of the performance by different DE schemes for J30
图 4 J3013不同DE方案收敛性能比较
Fig. 4 Comparison of the convergent performance by different DE schemes for J3013
表 1 J30系列不同测试方案结果比较
Table 1 Comparison of the results by different test schemes for J30
方案 DE类型 参数控制 调度算法 避免局部最优 标准化编码 平均偏差率
$av\_dev\, (\%)$ bh成功率
$success\, (\%)$平均代数
$av\_gen$平均CPU时间
$CPUTime$ (s)平均值 标准差 1 DE 固定 正向 0.143 0.013 92.40 109 4.59 2 DDE 固定 正向 0.143 0.021 92.42 90 2.54 3 DDE 正态分布[21] 正向 0.142 0.015 92.46 89 2.62 4 DDE 自适应 正向 0.050 0.011 96.94 53 1.56 5 DDE 自适应 双向 0.027 0.005 98.25 27 2.22 6 DDE 自适应 双向 是 0.065 0.013 96.00 44 1.14 7 DDE 自适应 双向 是 0.016 0.005 98.90 22 1.91 8 DDE 自适应 双向 是 是 0.008 0.003 99.35 13 0.93 
下载: 导出CSV
表 2 显著性水平($\alpha=0.05)$下平均偏差率双总体t检验
Table 2 Paired-sample t-test of the average deviation rate at the significance level of 0.05
1 2 3 4 5 6 7 8 1 1 2 $\textbf{0.983}$ 1 3 $\textbf{0.939}$ $\textbf{0.937}$ 1 4 1.34$\, \times 10^{-12}$ 3.83$\, \times 10^{-10}$ 4.66$\, \times 10^{-12}$ 1 5 6.69$\, \times 10^{-16}$ 1.98$\, \times 10^{-12}$ 4.33$\, \times 10^{-15}$ 1.38$\, \times 10^{-5}$ 1 6 8.97$\, \times 10^{-11}$ 1.16$\, \times 10^{-8}$ 2.63$\, \times 10^{-10}$ 1.18$\, \times 10^{-2}$ 8.02$\, \times 10^{-8}$ 1 7 1.30$\, \times 10^{-16}$ 4.06$\, \times 10^{-13}$ 8.40$\, \times 10^{-16}$ 5.81$\, \times 10^{-8}$ 3.64$\, \times 10^{-5}$ 1.50$\, \times 10^{-9}$ 1 8 $ {\bf{2}}.{\bf{83}}\times {\bf{1}}{{\bf{0}}^{ - {\bf{17}}}}$ $ {\bf{1}}.{\bf{25}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{13}}}}$ $ {\bf{2}}.{\bf{03}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{16}}}}$ $ {\bf{1}}.{\bf{53}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{9}}}}$ ${\bf{4}}.{\bf{69}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{9}}}}$ $ {\bf{9}}.{\bf{62}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{11}}}}$ $ {\bf{5}}.{\bf{62}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{4}}}}$ 1
下载: 导出CSV
表 3 方案5与方案7性能比较
Table 3 Comparison between scheme 5 and scheme 7
Ⅰ类(36个实例) Ⅱ类(444个实例) 平均偏差率 平均代数 平均偏差率 平均代数 $av\_dev~(\%)$ $av\_gen$ $av\_dev~(\%)$ $av\_gen$ 方案5 0.346 285 0.001 6 方案7 0.194 238 0.001 5
下载: 导出CSV
表 4 ADDE-BS算法结果
Table 4 Results of ADDE-BS algorithm
最大调度次数 5 000 50 000 实例集 J30 J60 J90 J120 J30 J60 J90 J120 $av\_dev~(\%)$ 0.04 1.32 2.88 25.37 $\textbf{0.01}$ 1.03 2.62 24.43 $success~(\%)$ 97.44 79.58 76.67 30.00 $\textbf{99.35}$ 83.75 77.50 31.50 $CPUTime$ (s) 0.40 6.78 16.24 86.92 $\textbf{0.93}$ 66.55 179.89 1 004.36
下载: 导出CSV
表 5 与其他文献算法平均偏差率(%)比较
Table 5 Comparison of average deviation rate (%) with art-of-state algorithms
J30 J60 J90 J120 5 000 50 000 5 000 50 000 5 000 50 000 5 000 50 000 本文ADDE-BS $\textbf{0.04}$ $\textbf{0.01}$ $\textbf{1.32}$ $\textbf{1.03}$ $\textbf{2.88}$ $\textbf{2.62}$ $\textbf{25.37}$ $\textbf{24.43}$ DE[18] 2016 0.00 0.00 0.98 2.07 4.04 8.81 19.62 31.68 ACO CRO[6] 2017 - - 11.40 11.40 12.21 12.21 26.53 26.51 COAs[14] 2017 0.00 0.00 10.77 10.58 - - 32.35 31.23 GA-Part[9] 2017 0.07 0.01 11.08 10.71 - - 33.36 31.81 Heuristic[24] 2017 0.09 0.03 11.31 10.91 - - 34.08 32.52 ReVNS[10] 2016 0.01 0.00 11.10 10.88 - - 33.36 32.21 H-RPSO[7] 2016 0.03 0.01 10.23 10.11 - - 31.94 30.25 GA-MBX[25] 2013 0.04 0.00 10.94 10.65 - - 32.89 31.30 MAOA[26] 2015 0.06 0.01 10.84 10.64 - - 32.64 31.02 PSO-HH[13] 2014 0.04 0.01 11.13 10.68 - - 32.59 31.23 HGA[27] 2013 0.07 0.01 11.14 10.63 - - 32.75 30.66 ASH[27] 2013 0.11 0.03 11.33 10.85 - - 33.54 31.97
下载: 导出CSV
-
[1] Kolisch R, Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: an update. European Journal of Operational Research, 2006, 174(1): 23-37 doi: 10.1016/j.ejor.2005.01.065 [2] Kolish R, Sprecher A. PSPLIB-A project scheduling problem library. European Journal of Operational Research, 1997, 96(1): 205-216 doi: 10.1016/S0377-2217(96)00170-1 [3] Hartmann S. A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 2002, 49(5): 433-448 doi: 10.1002/nav.10029 [4] 邓林义, 林焰, 金朝光.采用优先规则的粒子群算法求解RCPSP.计算机工程与应用, 2009, 45(10): 40-44 doi: 10.3778/j.issn.1002-8331.2009.10.013Deng Lin-Yi, Lin Yan, Jin Chao-Guang. Priority rule-based particle swarm optimization for RCPSP. Computer Engineering and Applications, 2009, 45(10): 40-44 doi: 10.3778/j.issn.1002-8331.2009.10.013 [5] 戴月明, 汤继涛, 纪志成.协同震荡搜索混沌粒子群求解资源受限项目调度问题.计算机应用, 2014, 34(6): 1798-1802 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201406060Dai Yue-Ming, Tang Ji-Tao, Ji Zhi-Cheng. Cooperative shock search particle swarm optimization with chaos for resource-constrained project scheduling problems. Journal of Computer Applications, 2014, 34(6): 1798-1802 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201406060 [6] Gonzalez-Pardo A, Del Ser J, Camacho D. Comparative study of pheromone control heuristics in ACO algorithms for solving RCPSP problems. Applied Soft Computing, 2017, 60: 241-255 doi: 10.1016/j.asoc.2017.06.042 [7] Munlin M, Anantathanavit M. Hybrid radius particle swarm optimization. In: Proceedings of the 2016 IEEE Region 10 Conference (TENCON). Singapore: IEEE, 2016. 2180-2184 [8] Valls V, Ballestín F, Quintanilla S. Justification and RCPSP: a technique that pays. European Journal of Operational Research, 2005, 165(2): 375-386 doi: 10.1016/j.ejor.2004.04.008 [9] Zamani R. An evolutionary implicit enumeration procedure for solving the resource-constrained project scheduling problem. International Transactions in Operational Research, 2017, 24(6): 1525-1547 doi: 10.1111/itor.12196 [10] Paraskevopoulos D C, Tarantilis C D, Ioannou G. An adaptive memory programming framework for the resource-constrained project scheduling problem. International Journal of Production Research, 2016, 54(16): 4938-4956 doi: 10.1080/00207543.2016.1145814 [11] 黄志宇.具有资源约束的项目调度问题中的量子进化算法.计算机集成制造系统, 2009, 15(9): 1779-1787, 1822 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200909016Huang Zhi-Yu. Quantum-inspired evolutionary algorithm for resources constrainted project scheduling problem. Computer Integrated Manufacturing Systems, 2009, 15(9): 1779-1787, 1822 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200909016 [12] 陆志强, 刘欣仪.考虑资源转移时间的资源受限项目调度问题的算法.自动化学报, 2018, 44(6): 1028-1036 doi: 10.16383/j.aas.2017.c160834Lu Zhi-Qiang, Liu Xin-Yi. Algorithm for resource-constrained project scheduling problem with resource transfer time. Acta Automatica Sinica, 2018, 44(6): 1028-1036 doi: 10.16383/j.aas.2017.c160834 [13] Koulinas G, Kotsikas L, Anagnostopoulos K. A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem. Information Sciences, 2014, 277: 680-693 doi: 10.1016/j.ins.2014.02.155 [14] Elsayed S, Sarker R, Ray T, Coello C C. Consolidated optimization algorithm for resource-constrained project scheduling problems. Information Sciences, 2017, 418-419: 346-362 doi: 10.1016/j.ins.2017.08.023 [15] 吴亮红, 王耀南.动态差分进化算法及其应用.北京:科学出版社, 2014. 1-7Wu Liang-Hong, Wang Yao-Nan. Dynamic Differential Evolution Algorithm and Its Applications. Beijing: Science Press, 2014. 1-7 [16] Das S, Mullick S S, Suganthan P N. Recent advances in differential evolution-an updated survey. Swarm and Evolutionary Computation, 2016, 27: 1-30 [17] Cheng M Y, Tran D H, Wu Y W. Using a fuzzy clustering chaotic-based differential evolution with serial method to solve resource-constrained project scheduling problems. Automation in Construction, 2014, 37: 88-97 doi: 10.1016/j.autcon.2013.10.002 [18] Ali I M, Elsayed S M, Ray T, Sarker R A. A differential evolution algorithm for solving resource constrained project scheduling problems. In: Artificial Life and Computational Intelligence. Lecture Notes in Computer Science, Vol. 9592. Cham: Springer, 2016. 209-220 [19] Ciupe A, Meza S, Orza B. Heuristic optimization for the resource constrained Project Scheduling Problem: a systematic mapping. In: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems. Gdansk, Poland: IEEE, 2016. 619-626 [20] Brest J, Greiner S, Boskovic B, Mernik M, Zumer V. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-657 doi: 10.1109/TEVC.2006.872133 [21] Qin A K, Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398-417 doi: 10.1109/TEVC.2008.927706 [22] Zhang J Q, Sanderson A C. JADE: adaptive differential evolution with optional external archive. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945-958 doi: 10.1109/TEVC.2009.2014613 [23] Qing A Y. Dynamic differential evolution strategy and applications in electromagnetic inverse scattering problems. IEEE Transactions on Geoscience and Remote Sensing, 2006, 44(1): 116-125 [24] Chand S, Singh H K, Ray T. A heuristic algorithm for solving resource constrained project scheduling problems. In: Proceedings of IEEE Congress on Evolutionary Computation. San Sebastian, Spain: IEEE, 2017. 225-232 [25] Zamani R. A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem. European Journal of Operational Research, 2013, 229(2): 552-559 doi: 10.1016/j.ejor.2013.03.005 [26] Zheng X L, Wang L. A multi-agent optimization algorithm for resource constrained project scheduling problem. Expert Systems with Applications, 2015, 42(15-16): 6039-6049 doi: 10.1016/j.eswa.2015.04.009 [27] Lim A, Ma H, Rodrigues B, Tan S T, Xiao F. New meta-heuristics for the resource-constrained project scheduling problem. Flexible Services and Manufacturing Journal, 2013, 25(1-2): 48-73 doi: 10.1007/s10696-011-9133-0 期刊类型引用(6)
1. 田润丰. 基于时序差分的OFDM无线网络信道自适应分配方法. 电子设计工程. 2025(03): 144-150 . 
百度学术2. 鲁宇明，张祥飞，涂传明，黎政秀. 多变异策略融合的约束优化问题求解算法. 小型微型计算机系统. 2023(10): 2151-2156 . 百度学术3. 李斌，黄起彬. 面向资源约束项目调度的二阶段帝国竞争算法. 计算机科学与探索. 2023(11): 2620-2639 . 百度学术4. 张牧仁，项前，吕志军，尹英豪，俞卓韬. 面向低能耗的密集仓储货位分配优化. 东华大学学报(自然科学版). 2023(05): 88-96+135 . 百度学术5. 田启华，黄佳康，明文豪，杜义贤，周祥曼，付君健. 资源约束下产品开发任务调度的多目标优化. 计算机集成制造系统. 2022(02): 564-573 . 百度学术6. 项前，周亚云，陆枳屹，余玉风. 响应动态约束条件的多目标货位优化算法研究. 智能系统学报. 2020(05): 925-933 . 百度学术其他类型引用(9)
-
下载:
计量
- 文章访问数: 2665
- HTML全文浏览量: 347
- PDF下载量: 173
- 被引次数: 15
