A Four Directional Cooperative Three-dimensional Packing Method Based on Deep Reinforcement Learning
-
摘要: 物流作为现代经济的重要组成部分, 在国民经济和社会发展中发挥着重要作用. 物流中的三维装箱问题(Three-dimensional bin packing problem, 3D-BPP)是提高物流运作效率必须解决的关键难题之一. 深度强化学习(Deep reinforcement learning, DRL)具有强大的学习与决策能力, 基于DRL的三维装箱方法(Three-dimensional bin packing method based on DRL, DRL-3DBP)已成为智能物流领域的研究热点之一. 现有DRL-3DBP面对大尺寸容器3D-BPP时难以达成动作空间、计算复杂性与探索能力之间的平衡. 为此, 提出一种四向协同装箱(Four directional cooperative packing, FDCP)方法: 两阶段策略网络接收旋转后的容器状态, 生成4个方向的装箱策略; 根据由4个策略采样而得的动作更新对应的4个状态, 选取其中价值最大的对应动作为装箱动作. FDCP在压缩动作空间、减小计算复杂性的同时, 鼓励智能体对4个方向合理装箱位置的探索. 实验结果表明, FDCP在100 × 100大尺寸容器以及20、30、50箱子数量的装箱问题上实现了1.2% ~ 2.9%的空间利用率提升.Abstract: As an important part of the modern economy, logistics plays an important role in the national economy and social development. The three-dimensional bin packing problem (3D-BPP) in logistics is one of the key problems that must be solved to improve the efficiency of logistics operations. Deep reinforcement learning (DRL) has a powerful learning and decision-making ability, and the three-dimensional bin packing method based on DRL (DRL-3DBP) has become one of the research hotspots in the field of intelligent logistics. The existing DRL-3DBPs have difficulty in striking a balance between the action space, computational complexity, and exploration capability when solving 3D-BPP with large-size bins. To this end, this paper proposes a four directional cooperative packing (FDCP) method. The two-stage policy network receives the rotated bin states and generates four directional packing policies. Based on the actions sampled from the four policies, the four states are updated accordingly, and the action corresponding to the highest value is selected as the packing action. FDCP encourages agent to explore reasonable packing positions in all four directions while compressing the action space and reducing computational complexity. Experimental results show that FDCP achieves 1.2% ~ 2.9% improvement in space utilization on the packing problem with 100 × 100 large-sized bin and the numbers of 20, 30, and 50 items.
-
时频分析方法采用时间和频率域联合函数来处理时序信号, 获取信号频率随时间变化的细节信息, 是现代信号处理领域的重要技术手段之一. 1946年, Gabor首次对傅里叶变换加高斯窗函数, 提出了著名的Gabor变换, 由此开启了时频联合分析的新思路[1]. Ville将量子力学的Wigner分布用于信号分析与处理领域, 提出了Wigner-Ville分布(Wigner-Ville distribution, WVD)[2]. WVD具有良好的时频聚集特性, 但存在严重的交叉项干扰问题. Cohen对WVD进行时频二维卷积得到Cohen类时频分布[3]. Cohen类时频分布通过构造核函数, 达到消除或抑制交叉项的目的, 缺点是降低了频率聚集度. 20世纪80年代, Mallat[4]提出了多尺度分析思想和Mallat算法, 成功地统一了各种小波函数的构造模型, 使用可调节的时间和频率窗口, 有效提高了频率聚集度. 1996年, 美国地球物理学家Stockwell等[5]对短时傅里叶变换和连续小波变换的思想进行延伸与推广, 提出了S变换. 1998年, Huang等[6]提出经验模态分解(Empirical mode decomposition, EMD), 将信号分解为有限个固有模态函数(Intrinsic mode functions, IMF)的集合. EMD方法可应用于多种类型信号的分解, 在处理非平稳、非线性信号方面, 效果良好[7-8]. 但相对来讲, S变换和EMD的聚集度不够理想. 2012年, Yang等[9]提出了适用范围更广泛的参数化时频分析广义Warblet变换(Generalized Warblet transform, GWT), 该方法具有真实反映信号频率分布的特点, 但存在频率泄露现象, 时频聚集度较差, 需要结合其他算法加以改进.
WVD作为一种优良的双线性时频分析方法具有其他方法不可替代的高锐化时频聚集特性, 但在处理多分量信号时会出现交叉项干扰问题. 文献[10-12]提出对信号进行WVD处理前, 分别采用变分模态分解 (Variational mode decomposition, VMD)、 集成经验模态分解 (Ensemble empirical mode decomposition, EEMD)、自适应匹配追踪 (Adaptive matching pursuit, AMP)将多分量信号转换为单分量信号, 有效避免产生交叉项; 文献[13]通过对信号进行带通滤波和相位矫正的方法去除交叉项; 文献[14]提出矩阵旋转变换的方法, 将WVD交叉项旋转至与频率轴平行, 再通过滤波器滤除交叉项; 文献[15]通过二重余弦信号的WVD, 推导自项与交叉项位置关系以及振荡特性, 滤除交叉项; 文献[16-17]采用两种算法结合的思想(如Gabor-WVD、BGabor-NSPWVD、SPWVD-WVD等), 对比实验证明此方法有效抑制了WVD交叉项.
本文在分析WVD交叉项的产生原因基础上, 将交叉项分为新产生的交叉项分量和混入自项的交叉项分量两种类型. 利用GWT较好还原信号真实频率分布的特性, 将GWT矩阵与WVD矩阵联合处理以实现滤波效应, 抑制WVD的两种类型交叉项. 使用两种定量评价方法将NGWT-WVD算法与同类算法进行对比, 检验算法有效性. 最后将该算法用于处理金属破裂样本信号, 获取破裂期间的时频分布图, 找出滤波器的窗口门限近似频率, 为声发射信号监测传感器采集卡提供门限设置依据.
1. NGWT-WVD算法
1.1 WVD (Wigner-Ville分布)
WVD是一种双线性时频分布, 设信号为
$ {z}\left( t \right) $ , 其Wigner-Ville分布表达式为$${{WVD}}\left( {t,f} \right) = \int {z} \left( {t + \frac{\tau }{2}} \right){z^*}\left( {t - \frac{\tau }{2}} \right){{\rm{e}}^{ - {\rm{j}}2\pi \tau f}}{\rm{d}}\tau $$ (1) $ R\left( {t,\tau } \right) = z\left( {t + \tau /2} \right){z^*}\left( {t - \tau /2} \right) $ 表示信号的自相关函数, WVD可看作信号自相关函数的傅里叶变换. WVD具有优良的时频聚集度, 但处理多分量信号时会出现交叉项, 如式(2)所示$$\begin{split} R\left( {t,\tau } \right) = \,&\sum {{z^*}(t - \frac{1}{2}\tau )} \sum {z(t - \frac{1}{2}\tau )} =\\ & \sum\limits_i {z_i^*(t - \frac{1}{2}\tau )} {z_i}(t - \frac{1}{2}\tau )\, +\\ &\sum\limits_i {\sum\limits_j {z_i^*(t - \frac{1}{2}\tau ){z_j}(t - \frac{1}{2}\tau )} } =\\ & {R_a}\left( {t,\tau } \right) + {R_s}\left( {t,\tau } \right) \end{split}$$ (2) $ {R_a}\left( {t,\tau } \right) $ 表示自相关成分(自项), 是有用信息;$ {R_s}\left( {t,\tau } \right) $ 表示互相关成分(交叉项), 是干扰信息. 对于同时间区间的多分量信号, 交叉项具有两个特点: 任意两个信号分量均会产生一个交叉项; 交叉项位于两频率分量中间.选取三分量线性调频信号
$ {z_1}\left( t \right) $ 为例, 说明信号各成分之间的关系. 其表达式如式(3)所示$${z_1}(t) = \sum\limits_{i = 0}^2 {{{\rm{e}}^{({\rm{j}}2\pi (0.1it + \frac{{3{t^2}}}{{80\,000}}))}}} $$ (3) 信号二维、三维WVD时频分布如图1所示. 由图1(a)和图1(b)对比可见, 三分量线性调频信号的Wigner-Ville分布引入了一些新分量, 这些分量是新产生的交叉项分量; 而由图1(c)的三维图可见, 中间分量能量远高于两边分量, 说明有部分交叉项混入进自项成分. 本文需要解决的问题有两个: 一是抑制新产生的交叉项分量; 二是抑制混入自项的交叉项分量.
1.2 GWT (广义Warblet变换)
GWT是核函数以傅里叶级数为模型定义的参数化时频分析方法. 其定义为
$${{GWT}}({t_0},\alpha ,\beta ,f,\omega ;\sigma ) = \int_{ - \infty }^{ + \infty } {\overline {z}(t) {w_\sigma }(t - {t_0}){{\rm{e}}^{ - {\rm{j}}\omega t}}{\rm{d}}t} $$ (4) 其中,
${t_0} \in {\boldsymbol{{\rm{R}}}}$ 表示时间窗滑动时的窗中心所在时间,$ {w_\sigma } \in {L^2}(R) $ 定义了一个非负对称的标准化实窗, 通常是高斯窗,$\overline {z}(t)$ 计算式为$$\left\{ {\begin{array}{*{20}{l}} {\overline {z}(t) = z(t){\Phi ^R}(t,a,b,f){\Phi ^S}(t,{t_0},a,b,f)}\\ {{\Phi ^R}(t,a,b,f) = {{\rm{e}}^{ - {\rm{j}}(\sum\limits_{i = 1}^m {\frac{{{a_i}}}{{{f_i}}}\cos 2\pi {f_i}t} + \sum\limits_{i = 1}^m {\frac{{{b_i}}}{{{f_i}}}\sin 2\pi {f_i}t} )}}}\\ {{\Phi ^S}(t, {t_0}, a, b, f) = {{\rm{e}}^{({\rm{j}}2\pi ( - \sum\limits_{i = 1}^m {{a_i}\cos 2\pi {f_i}{t_0}} + \sum\limits_{i = 1}^m {{b_i}\sin 2\pi {f_i}t)} t)}}} \end{array}} \right.$$ (5) 其中.
$ z(t) $ 为解析信号,$ m $ 表示正弦函数或余弦函数的总数,$ {a_i} $ 和$ {b_i} $ 为傅里叶系数,$ {f_i} $ 为对应谐波分量频率,$ {\Phi ^R}(t,a,b,f) $ 和$ {\Phi ^S}(t,{t_0},a,b,f) $ 分别为频率平移算子与频率旋转算子. 频率旋转算子用瞬时频率减去$\rho = - \sum\nolimits_{i = 1}^m {{a_i}\cos 2\pi {f_i}t} + \sum\nolimits_{i = 1}^m {{b_i}\sin 2\pi {f_i}t}$ (Hz)来旋转分析信号频率分量; 频率平移算子在频率分量添加频率增量$\gamma = - \sum\nolimits_{i = 1}^m {{a_i}\cos 2\pi {f_i}{t_0}} \;+ \sum\nolimits_{i = 1}^m {{b_i} \sin 2\pi {f_i}{t_0}}$ (Hz)使频率分量平移时间$ {t_0} $ , 最后对频率分量进行短时傅里叶变换.参数化时频分析方法选取合适的核函数对其分析效果有很大影响, 采用傅里叶级数变换核的GWT能够分析具有周期性或非周期性时频特征的非平稳信号, 以及具有强振荡时频特征的信号, 使其适用范围更加广阔.
三分量线性调频信号的GWT时频图如图2所示.
图2中GWT算法采用傅里叶级数模型作为核函数, 较好地还原了信号的真实频率分布, 虽然时频聚集度较差, 但能够保留真实频率分量, 不会产生交叉项. 由此, 基于WVD的高锐化特性和GWT真实还原信号时频分布的特性, 将二者相结合, 得到GWT-WVD算法, 既能抑制交叉项, 又能保留高锐化时频聚集度的性能.
1.3 GWT-WVD算法: 抑制新产生的交叉项分量
本文提出的GWT-WVD算法, 可有效抑制WVD的交叉项分量. 该算法通过对GWT算法与WVD算法得到的矩阵进行运算, 在保留较好的时频聚集度的同时, 能较好地消除或抑制交叉项. 其表达式为
$${{G}}{{{W}}_x}(t,f) = p({{GWa}}{{{r}}_x}(t,f),{{{W}}_x}(t,f))$$ (6) 其中,
$ {{\mathop{GWar}\nolimits} _x}\left( {t,f} \right) $ 与$ {{\mathop{ W}\nolimits} _x}\left( {t,f} \right) $ 分别代表GWT与WVD,$ p\left( {x,y} \right) $ 为联合处理函数. 本文采用了3种不同的函数, 得到GWT-WVD算法的3种定义式$${{G}}{{{W}}_x}\left( {t,f} \right) = \min \left\{ {{{GWa}}{{{r}}_x}\left( {t,f} \right),\left| {{{{W}}_x}\left( {t,f} \right)} \right|} \right\}$$ (7) $${{G}}{{{W}}_x}(t,f) = {{GWar}}_x^a(t,f) \times {{W}}_x^b(t,f)$$ (8) $${{G}}{{{W}}_x}\left( {t,f} \right) = {{{W}}_x}\left( {t,f} \right) \times \left\{ {\left| {{{GWa}}{{{r}}_x}\left( {t,f} \right)} \right| > c} \right\}$$ (9) 式(7) ~ (9)分别采用最小值法、二值化法、幂指数调节法对两矩阵进行处理, 其各自实现思想如下．
1)最小值法. 比较WVD矩阵及GWT矩阵对应位置元素, 筛选其中较小的元素, 按比例处理后组成GWT-WVD矩阵, 使WVD矩阵新产生的交叉项所在位置的元素被GWT矩阵元素取代.
2)幂指数调节法. 调节幂指数, 增强GWT与WVD矩阵中信号数据对应的元素, 削弱交叉项数据对应的元素, 再将两矩阵点乘, 得到GWT-WVD矩阵.
3)二值化法. 选取合适的阈值将GWT矩阵二值化得到新矩阵, 用新矩阵点乘WVD矩阵得到GWT-WVD矩阵. WVD矩阵有交叉项的元素位置对应的GWT矩阵元素会小于阈值, 二值化后为0, 与WVD矩阵相乘后可消除新产生的交叉项.
线性调频信号
$ {z_1}\left( t \right) $ 的3种GWT-WVD时频分布如图3所示. 3种结合方法均能优化信号的时频分布, 有效抑制交叉项, 但幂指数调节法的时频聚集度比另外两种方法差(第3节讨论时频聚集度问题). 在处理复杂信号时, 二值化法阈值难以确定. 综合比较, 最小值法的GWT-WVD算法性能最佳.1.4 NGWT-WVD算法: 抑制混入自项的交叉项分量
GWT-WVD算法能够有效抑制新产生的交叉项分量, 但无法抑制混入自项分量的交叉项. 针对这个问题, 本文对GWT-WVD算法进行改进, 又提出NGWT-WVD算法, 其主要实现思路如下.
图 5 三分量信号三维时频图比较Fig. 5 Three-dimensional time-frequency diagrams comparison of three-component signals1)采用广义Warblet变换和WVD分别对原信号进行处理, 得到GWT矩阵和WVD矩阵;
2)找出GWT矩阵中元素数值的最大值GWTmax, 并记录其所对应的位置
$(i,j)$ , 将GWT矩阵中的各元素除以GWTmax, 即对GWT矩阵进行归一化, 得到矩阵GWT-1;3)记录GWT-1矩阵中元素数值的最小值GWTmin, 最小值GWTmin要求非零, 并用GWTmin的数值替换掉矩阵GWT-1中所有值为0的元素;
4)找出WVD矩阵中位置为
$(i,j) $ 的元素, 将其记为WVDmax, 同时将WVD矩阵中的各个元素除以WVDmax, 得到矩阵WVD-1;5)用矩阵WVD-1点除矩阵GWT-1, 得到矩阵T, 选取矩阵T中大于x的元素以及小于y的元素, x设置为5, y设置为2, 将所对应的元素位置置1, 并记录大于x的元素位置;
6)在WVD矩阵中找出与上一步记录对应的元素位置, 并将此位置上元素置为0, 最后用WVD矩阵点除矩阵T, 输出NGWT-WVD矩阵. 其流程如图4所示.
线性调频信号的GWT-WVD算法和NGWT-WVD算法三维时频分布如图5所示. 由图5(a)可见, 中间分量的能量谱明显高于其他分量的能量谱, GWT-WVD算法不能有效抑制混入自项的交叉项分量; 而图5(b)中3个信号分量能量一致, 混入自项成分上的交叉项被有效抑制. 图5说明NGWT-WVD算法能有效抑制线性调频信号的两类交叉项.
NGWT-WVD算法中的阈值参数x是为了抑制存在于自项中的干扰项, 阈值y是为了抑制新产生的干扰项并且去除发散的能量. 阈值对NGWT-WVD算法性能起决定性作用, 这里使用后文的两种定量评价方式对两个阈值的敏感性进行分析, 其结果如图6所示.
图6(a)是CM值(时频聚集度定量评价方法, 数值越大代表聚集度越高, 其计算式见第3.2节)随阈值y变化折线图, 此时阈值x设置为5, x1, x2, x3, x4分别代表文中使用的4种仿真信号. 图中, 阈值y小于1时, NGWT-WVD算法的时频聚集度低于WVD算法; 随着阈值y的增加, CM值逐渐增加, WVD中部分扩散的时频系数被滤除, 时频聚集度提高. 当阈值y超过2时, 时频聚集度CM值迅速提高, 但这是以滤除部分WVD有用信息分量为代价. 因此阈值y取值为2即可, 此时新产生的交叉项基本消除干净(由图5(b)可见), 且时频聚集度较理想. 图6(b)是时变功率谱误差随阈值x变化折线图, 此时阈值y设置为2 (基本消除了新产生的交叉项分量). 阈值x是为滤除混入自项的交叉项(只有仿真信号1含有混入自项的交叉项), 当阈值x大于10时, 时变功率谱误差保持在25%左右, 无法滤除混入自项的交叉项; 阈值x在5 ~ 6之间时, 时变功率谱误差接近0, 此时抑制效果较好; 小于5后, 由于滤除了信息项, 导致误差进一步增加, 因此阈值x设置为5较合适. 实际应用信号由一系列单分量信号线性叠加而成, 也可按照此参数设置相应阈值.
NGWT-WVD算法通过对GWT矩阵进行归一化且做去零处理得到的GWT-1矩阵, 此矩阵为对照矩阵, 通过设置两个阈值, 实现了滤波效应, 剔除了WVD中发散能量, 且抑制了混入自项的交叉项和新产生的交叉项, 得到了更加理想的时频分布结果.
2. 数值实验
为了评价NGWT-WVD算法的处理效果, 本文另外构造了3种具有代表性的信号, 并通过与Garbor-WVD、VMD-WVD两种较有代表性的方法进行对比, 验证该算法的有效性.
2.1 分段信号
函数表达式为
$${z_2}(t)\left\{ {\begin{array}{*{20}{l}} {\cos (2\pi\times 0.4t)},&{250 \le t \le 700}\\ {\cos (2\pi \times{\rm{0}}.{\rm{2}}t)},&{700 < t \le 1\,500}\\ {\cos (2\pi \times{\rm{0}}.{\rm{1}}t)},&{1\,500 < t \le 2\,200}\\ {\cos (2\pi\times {\rm{0}}.{\rm{025}}t)},&{2\,200 < t \le 3\,500} \end{array}} \right.$$ (10) 分段信号
$ {z_2}(t) $ 的WVD、Gabor-WVD (文献[14]中采用的处理方法)、VMD-WVD (选取模数为4)、NGWT-WVD算法时频分布如图7所示. 图7(a)中WVD在端点处出现严重的交叉项干扰; 图7(b)中Gabor-WVD算法处理信号时仍然会出现少许交叉项; 图7(c)中, VMD的参数设置准确的情况下, VMD-WVD算法交叉项抑制效果较好; 图7(d)中NGWT-WVD算法得到的时频分布也基本没有交叉项.2.2 交叉型信号
函数表达式为
$${z_3}(t) = {{\rm{e}}^{{\rm{j}}2\pi \left(\frac{{{t^2}}}{{20\,000}}\right)}} + {{\rm{e}}^{{\rm{j}}2\pi \left(0.4t - \frac{{3{t^2}}}{{80\,000}}\right)}}$$ (11) 交叉信号
$ {z_3}(t) $ 的WVD、Gabor-WVD、VMD-WVD (选取模数为2)以及NGWT-WVD算法的时频分布如图8所示. 此信号为两个线性调频信号交叉于一点, 交叉点的频率分量混合在一起, 分离困难. 图8(b)中Gabor-WVD算法在处理该信号时, 不能十分有效地抑制交叉项, 且时频聚集度较低. 图8(c)中VMD-WVD算法交叉项抑制效果较好, 时频聚集度略差; 图8(d)中NGWT-WVD算法对此信号的频率分量刻画准确, 时频聚集度高.2.3 两分量调频信号
函数表达式为
$${z_4}(t) = {{\rm{e}}^{{\rm{j}}2\pi (0.1{t^3} - 0.2{t^2} + 3t)}} + {{\rm{e}}^{{\rm{j}}2\pi (20t - 4\cos t)}}$$ (12) 信号
$ {z_4}(t) $ 是由一个抛物线调频信号和一个正弦调频信号组成, 并存在交叉点. 该信号的WVD、Gabor-WVD、VMD-WVD (选取模数为2)以及NGWT-WVD算法的时频分布如图9所示. 由图可见, 图9(b)中Garbor-WVD不能完全抑制, 图9(c)中VMD-WVD在处理这一类复杂调频信号时, 即使参数设置准确, 也无法有效将单分量信号完全分开, 交叉项干扰较为严重; 而NGWT-WVD算法对交叉项具有较好的抑制效果. 由此, 以上3个仿真实验都能说明NGWT-WVD算法具有较好的抑制信号交叉项效果, 同时保留了高时频聚集度, 提高了时频分析质量.
图 9 两分量调频信号时频图Fig. 9 Time-frequency diagram of two-component frequency modulated signal3. 算法性能评价
为定量说明NGWT−WVD算法性能, 本文选取交叉项抑制效果评价和时频聚集度评价两个指标评判该算法的时频分析效果.
3.1 交叉项抑制效果评价
交叉项抑制效果是WVD改进算法性能评价的重要指标, 以往均使用定性分析, 即通过观察时频分布结果得出判断. 本文在分析WVD交叉项出现规律的基础上, 提出一种定量的交叉项抑制效果评价方法. 由式(2)知, 信号经WVD处理后, 分量包括自项成分与交叉项成分, 本文计算信号在时间−频率平面的时变功率谱
$ {P_i} $ , 并与信号标准时变功率谱$ I{P_i} $ (不含交叉项的信号功率谱)作对比, 计算出时变功率谱误差, 以此评价交叉项抑制效果. 选取信号$ {z_1}(t) $ ,$ {z_2}(t) $ ,$ {z_3}(t) $ ,$ {z_4}(t) $ 作为研究对象, 计算各算法的功率谱与标准功率谱的平均相对误差, 其计算式为$${\eta _s} = 20\lg \left(\frac{1}{N}\sum\limits_{i = 0}^N {\frac{{P(i) - IP(i)}}{{IP(i)}}} \right)$$ (13) 其中,
$ N $ 为信号采样点数. 标准时变功率谱计算式为$$IP(i) = {P_{f1}}(i) + {P_{f2}}(i) + \cdots + {P_{fj}}(i)+ \cdots + {P_{fn}}(i)$$ (14) 其中,
$ n $ 表示信号含有单分量的个数,$ {P_{fj}}\left( i \right) $ 代表第$ j $ 个单分量的时变功率谱. 将各单分量分别求时频分布后相加, 得到没有交叉项的标准时变功率谱. 四种仿真信号平均时变功率谱误差对应的柱形图如图10所示, 数据如表1所示, z1, z2, z3, z4分别代表信号$ {z_1}(t) $ ,$ {z_2}(t) $ ,$ {z_3}(t) $ ,$ {z_4}(t) $ .
图 10 各算法的时变功率谱误差柱形图Fig. 10 Time-varying power spectrum error column chart of each algorithm表 1 各算法的时变功率谱误差比较Table 1 Time-varying power spectrum error comparison of each algorithm算法类型 ${ {z_1}( t )}$ ${{z_2}( t )}$ ${{z_3}( t )}$ ${{z_4}( t )}$ WVD 0.6061 0.3153 0.5139 0.5603 Gabor-WVD 0.3095 0.0854 0.0599 0.0736 GWT-WVD 0.2072 0.1084 0.1287 0.1394 VMD-WVD 0.0720 0.0274 0.0105 0.2375 NGWT-WVD 0.0210 0.0587 0.0099 0.0136 表1中不同信号的NGWT-WVD算法的时变功率谱误差均为最小, 反映出算法抑制交叉项性能最佳. 图11为表1的平均时变功率谱误差折线图形式.
图 11 各算法的时变功率谱误差折线图Fig. 11 Time-varying power spectrum error line chart of each algorithm图11中WVD算法的误差值最大, 说明时频分布中含有大量的交叉项, Gabor-WVD、GWT-WVD算法都能一定程度上抑制交叉项, 但是无法有效抑制混入自项成分中的交叉项, 其时变功率谱误差仍很大; VMD-WVD算法会先分解信号, 在处理恒频信号时, 分解效果好, 交叉项抑制效果也好, 在处理复杂信号时, 分解效果不佳, 时变功率谱误差远高于NGWT-WVD算法; 而NGWT-WVD算法可以较好地抑制两种交叉项, 时变功率谱误差较小, 且不需要设置初始参数, 算法的适应性强.
3.2 时频聚集度评价
Shafi等[18]于2009年提出了关于时频聚集度量化评定的方法, 本文选取CM值作为时频聚集度量化标准, 评价信号的时频图的聚集度, 其计算式为
$${{CM}} = \frac{{{{\displaystyle\sum\limits_{n = 0}^{N - 1} {\displaystyle\sum\limits_{\omega = 0}^{W - 1} {\left| {Q(n,\omega )} \right|}^4 } }}}}{{{{\left({{\displaystyle\sum\limits_{n = 0}^{N - 1} {\displaystyle\sum\limits_{\omega = 0}^{W - 1} {\left| {Q(n,\omega )} \right|}^2 } }}\right)}^2}}}$$ (15) 其中,
$ n $ 为时间窗长度,$ \omega $ 为信号在某点的频率,$ Q $ 表示信号的时频分布. 选取上述4种仿真信号作为实验对象, 计算CM值. 图12为4种信号各时频分析方法的CM值柱形图, 其数据如表2所示.表 2 各算法的CM值比较$(\times{10^{ - 3}})$ Table 2 CM value comparison of each algorithm$(\times{10^{ - 3}})$ 算法类型 ${{z_1}( t )}$ ${{z_2}( t)}$ ${{z_3}( t )}$ ${{z_4}( t )}$ GWT 0.0079 0.0282 0.0167 0.0194 Gabor-WVD 0.0303 0.0852 0.0576 0.0554 GWT-WVD 0.0386 0.0921 0.0596 0.1164 WVD 0.0687 0.1821 0.0776 0.1008 VMD-WVD 0.0649 0.2143 0.1204 0.1526 NGWT-WVD 0.0722 0.2254 0.1336 0.1625 表2中NGWT-WVD算法在评价不同信号的时频聚集度时, 其CM值均为最大, 反映出算法时频聚集度性能最佳, 锐化程度最高. 图13时频聚集度CM值折线图.
图 13 各算法的CM值折线图$(\times{10^{ - 3}})$ Fig. 13 CM value line chart of each algorithm$(\times{10^{ - 3}})$ 图13中, GWT算法CM值最小, 时频聚集度最差. Gabor-WVD算法CM值低于GWT-WVD算法, 时频聚集度较GWT-WVD算法低, 其去除交叉项的同时, 降低了时频聚集度. 信号z1因为是一种线性调频信号, 其VMD-WVD、NGWT-WVD算法的CM值与WVD的CM值相差不大, 但对于另外3种信号, VMD-WVD、NGWT-WVD算法的时频聚集度CM值明显高于WVD算法, 且NGWT-WVD算法略优于VMD-WVD算法. 通过比较4种信号各时频分析方法的时频聚集度CM值大小, 验证了NGWT-WVD算法具有高锐化的时频聚集度.
4. 金属破裂检测信号的时频分析应用
人造金刚石合成过程中, 六面顶压机顶锤的破裂损坏是经常发生的生产事故. 顶锤采用的钨钴类硬质合金, 在高温高压环境中, 长期处于超临界应力状态, 会出现疲劳损伤, 进而而导致顶锤破裂[19]. 若金刚石生产加工过程中未发现顶锤破裂前的异常情况, 将会使六面顶压机顶锤出现不可逆性损坏, 造成严重生产损失. 六面顶压机和顶锤结构如图14所示.
声发射技术是一种有效的探伤检测手段. 构件在外力或应变力的作用下会激发一定频谱的声发射信号, 通过判断接收到的信号频谱强度来预判构件的缺陷严重程度[20]. 顶锤破裂大致分为: 裂纹成核、裂纹拓展、断裂3个过程, 在这3个过程中应变能以弹性应力波的形式释放出来, 会产生剧烈的声发射信号[20].
为了避免生产事故, 需要在初步检测到钨钴合金出现破裂时立即终止加工过程. 而采集到的声发射信号振幅微弱(如图15(a)所示), 难于甄别判断. 本文使用的疑似金属破裂信号数据采样频率为40 000 Hz, 选取2 000个采样点数据, 由于篇幅限制, 仅绘制时域图、WVD算法时频分布图以及NGWT-WVD算法时频分布图, 结果如图15所示. 两种时频分析方法的CM值对比如表3所示, NGWT-WVD的时频聚集度CM值最大, 时频聚集度最好.
表 3 六种算法的CM值比较$(\times{10^{ - 5}})$ Table 3 CM value comparison of six algorithms$(\times{10^{ - 5}})$ 算法类型 CM 值 GWT 4.3669 Gabor-WVD 5.6375 GWT-WVD 7.5044 WVD 7.5046 VMD-WVD 17.6381 NGWT-WVD 20.8527 图15(a)为某一疑似金属破裂样本信号时域图, 该信号振幅微弱, 不利于监测传感器报警阈值的设置; 图15(b)和图15(c)分别为该样本信号WVD算法以及NGWT-WVD算法处理得到的时频分布图. 为便于更精确的分析, 截取了频率发生剧烈波动的片段(采样点数为900 ~ 1300之间数据)进行分析, 结果如图15(d)和图15(e)所示. 图15(d)中WVD算法得到的时频分布图交叉项分量与信号分量混杂, 整个时频分布图杂乱不清, 难以确定出现金属破裂的精确时间节点, 无法有效示警. 图15(e)中可较为明显地看出抑制了图15(d)中的交叉项(尤其是图15(d)方框中的主要交叉项), 时频分布锐化聚集度有明显的提高, CM值验证了这一结果. 图15(e)中椭圆框标记了金属破裂过程中频率较集中的频率分量区域, 可作为监测滤波器组的通带上下限的选取范围. 其中滤波器通带2作为主要预警通带, 滤波器通带1由于频率较低, 较容易受到外界噪声干扰, 通带3则由于频率阈值过高, 容易遗漏低频预警信号, 因此滤波器通带1、3通常作为辅助预警通带, 此外还可以在各通带间再设置部分滤波器通带, 提高识别几率. 实验结果表明, NGWT-WVD算法能够较精确地显示出各信号出现破裂的具体时间和频率窗口值, 可为信号监测传感器和滤波器组提供可操作的判断阈值, 提高设备的监测成功率.
5. 结束语
本文分析了WVD产生交叉项的原理, 针对交叉项干扰和时频模糊问题, 提出了NGWT-WVD算法. 该算法不仅能够有效抑制新产生的交叉项分量, 而且解决了Gabor-WVD等算法无法消除混入自项成分的交叉项分量问题, 在交叉项抑制效果评价和时频聚集度评价中表现良好. 仿真结果表明, NGWT-WVD算法能够实现保持高锐化聚集度的同时, 有效抑制交叉项干扰, 是一种高质量的时频分析方法. 将该算法用于处理金属破裂样本信号, 能够得到较为精确的信号时间和频率窗口值, 为监测传感器报警阈值的设置和数据采集滤波器组的设计提供有效依据.
-
图 9 FDCP在不同箱子数量算例上的测试结果
Fig. 9 Test results of FDCP on instances with different numbers of items
图 10 容器各区域放置次数热力图
Fig. 10 Heat map of the number of placements in each area of the bin
表 1 $ 100 \times 100 $容器装箱算例上的对比结果
Table 1 Comparative results on packing instances with $ 100 \times 100 $ bin
方法 $N=20$ $N=30$ $N=50$ UR (%) Time (s) UR (%) Time (s) UR (%) Time (s) Heuristic-3DBP GA+DBLF 70.2 17.5 69.4 36.3 66.3 71.9 EP 62.7 <1.0 63.8 <1.0 66.3 <1.0 LAFF 58.6 <1.0 59.1 <1.0 61.9 <1.0 EBAFIT 65.4 <1.0 65.9 <1.0 66.1 1.5 DRL-3DBP MTSL 62.4 4.8 60.1 10.2 55.3 23.0 CQL 67.0 1.0 69.3 1.2 73.6 3.3 JIANG 73.5 2.3 76.9 3.2 82.0 10.9 QUE 76.5 1.4 79.3 2.1 82.4 3.5 FDCP 79.4 1.9 81.7 3.1 83.6 5.2 
下载: 导出CSV
表 2 $ 200 \times 200 $和$ 400 \times 200 $容器算例上各方法的空间利用率UR (%)
Table 2 Space utilization (UR) of each method on instances with $ 200 \times 200 $ and $ 400 \times 200 $ bins (%)
容器尺寸 GA+DBLF EP LAFF EBAFIT MTSL CQL JIANG QUE FDCP 200$\times$200 61.4 63.3 58.0 62.8 50.8 58.7 75.2 80.5 81.2 400$\times$200 58.7 60.1 55.4 60.5 46.9 47.5 70.5 76.7 76.8
下载: 导出CSV
表 3 消融实验结果 (%)
Table 3 Results of ablation experiment (%)
方法 $N=20$ $N=30$ $N=50$ FDCP 79.4 81.7 83.6 −CO 75.9 79.2 81.4 −FD 75.9 79.0 81.5 −PN 76.5 79.5 81.9
下载: 导出CSV
-
[1] Bortfeldt A, Wascher G. Constraints in container loading——A state-of-the-art review. European Journal of Operational Research, 2013, 229(1): 1−20 doi: 10.1016/j.ejor.2012.12.006 [2] Jiao G S, Huang M, Song Y, Liu H B, Wang X W. Container loading problem based on robotic loader system: An optimization approach. Expert Systems With Applications, 2024, 236: Article No. 121222 doi: 10.1016/j.eswa.2023.121222 [3] Consolini L, Laurini M, Locatelli M. A dynamic programming approach for cooperative pallet-loading manipulators. IEEE Transactions on Automation Science and Engineering, DOI: 10.1109/TASE.2023.3310007 [4] Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem. Operations Research, 2000, 48(2): 256−267 doi: 10.1287/opre.48.2.256.12386 [5] Hifi M. Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study. Computers & Operations Research, 2004, 31(5): 657−674 [6] Chen C S, Lee S M, Shen Q S. An analytical model for the container loading problem. European Journal of Operational Research, 1995, 80(1): 68−76 doi: 10.1016/0377-2217(94)00002-T [7] Dósa G, Sgall J. First Fit bin packing: A tight analysis. In: Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Dagstuhl, Germany: Schloss Dagstuhl——Leibniz-Zentrum für Informatik, 2013. 538−549 [8] Crainic T G, Perboli G, Tadei R. Extreme point-based heuristics for three-dimensional bin packing. INFORMS Journal on Computing, 2008, 20(3): 368−384 doi: 10.1287/ijoc.1070.0250 [9] Karabulut K, Inceoglu M M. A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. In: Proceedings of the Third International Conference on Advances in Information Systems. Berlin, Heidelberg: Springer, 2004. 441−450 [10] Gurbuz M Z, Akyokus S, Emiroglu I, Guran A. An efficient algorithm for 3D rectangular box packing. In: Proceedings of the Selected AAS 2009 Papers. Skopje, Macedonia: Society for ETAI of Republic of Macedonia, 2009. 131−134 [11] Parreño F, Alvarez-Valdés R, Tamarit J M, Oliveira J F. A maximal-space algorithm for the container loading problem. INFORMS Journal on Computing, 2008, 20(3): 412−422 doi: 10.1287/ijoc.1070.0254 [12] Hasan J, Kaabi J, Harrath Y. Multi-objective 3D bin-packing problem. In: Proceedings of the 8th International Conference on Modeling Simulation and Applied Optimization (ICMSAO). Manama, Bahrain: IEEE, 2019. 1−5 [13] 张德富, 魏丽军, 陈青山, 陈火旺. 三维装箱问题的组合启发式算法. 软件学报, 2007, 18(9): 2083−2089 doi: 10.1360/jos182083Zhang De-Fu, Wei Li-Jun, Chen Qing-Shan, Chen Huo-Wang. A combinational heuristic algorithm for the three-dimensional packing problem. Journal of Software, 2007, 18(9): 2083−2089 doi: 10.1360/jos182083 [14] 何琨, 黄文奇. 基于动作空间的三维装箱问题的确定性高效率求解算法. 计算机学报, 2014, 37(8): 1786−1793He Kun, Huang Wen-Qi. An action space based deterministic efficient algorithm for solving the three-dimensional container loading. Chinese Journal of Computers, 2014, 37(8): 1786−1793 [15] Wu Y, Li W K, Goh M, de Souza R. Three-dimensional bin packing problem with variable bin height. European Journal of Operational Research, 2010, 202(2): 347−355 doi: 10.1016/j.ejor.2009.05.040 [16] Yang J L, Liu H W, Liang K B, Zhou L, Zhao J H. Variable neighborhood genetic algorithm for multi-order multi-bin open packing optimization. Applied Soft Computing, 2024, 163: Article No. 111890 doi: 10.1016/j.asoc.2024.111890 [17] Silveira M E, Vieira S M, Sousa J M D C. An ACO algorithm for the 3D bin packing problem in the steel industry. In: Proceedings of the 26th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. Berlin, Heidelberg: Springer, 2013. 535−544 [18] 张德富, 彭煜, 朱文兴, 陈火旺. 求解三维装箱问题的混合模拟退火算法. 计算机学报, 2009, 32(11): 2147−2156Zhang De-Fu, Peng Yu, Zhu Wen-Xing, Chen Huo-Wang. A hybrid simulated annealing algorithm for the three-dimensional packing problem. Chinese Journal of Computers, 2009, 32(11): 2147−2156 [19] Tsao Y C, Tai J Y, Vu T L, Chen T H. Multiple bin-size bin packing problem considering incompatible product categories. Expert Systems With Applications, 2024, 247: Article No. 123340 doi: 10.1016/j.eswa.2024.123340 [20] Bortfeldt A, Gehring H. Applying tabu search to container loading problems. In: Proceedings of the Operations Research Proceedings 1997. Berlin, Heidelberg: Springer, 1998. 533−538 [21] 刘胜, 沈大勇, 商秀芹, 赵红霞, 董西松, 王飞跃. 求解三维装箱问题的多层树搜索算法. 自动化学报, 2020, 46(6): 1178−1187Liu Sheng, Shen Da-Yong, Shang Xiu-Qin, Zhao Hong-Xia, Dong Xi-Song, Wang Fei-Yue. A multi-level tree search algorithm for three dimensional container loading problem. Acta Automatica Sinica, 2020, 46(6): 1178−1187 [22] Ren J D, Tian Y J, Sawaragi T. A tree search method for the container loading problem with shipment priority. European Journal of Operational Research, 2011, 214(3): 526−535 doi: 10.1016/j.ejor.2011.04.025 [23] Zhu W B, Lim A. A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem. European Journal of Operational Research, 2012, 222(3): 408−417 doi: 10.1016/j.ejor.2012.04.036 [24] Araya I, Moyano M, Sanchez C. A beam search algorithm for the biobjective container loading problem. European Journal of Operational Research, 2020, 286(2): 417−431 doi: 10.1016/j.ejor.2020.03.040 [25] Vinyals O, Fortunato M, Jaitly N. Pointer networks. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. Montreal, Canada: MIT Press, 2015. 2692−2700 [26] Bello I, Pham H, Le Q V, Norouzi M, Bengio S. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1611.09940, 2017. [27] Jin Y, Ding Y D, Pan X H, He K, Zhao L, Qin T, et al. Pointerformer: Deep reinforced multi-pointer Transformer for the traveling salesman problem. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence. Washington, USA: AAAI Press, 2023. 8132−8140 [28] Tang Y H, Agrawal S, Faenza Y. Reinforcement learning for integer programming: Learning to cut. In: Proceedings of the 37th International Conference on Machine Learning. Vienna, Austria: PMLR, 2020. 9367−9376 [29] Theodoropoulos T, Makris A, Psomakelis E, Carlini E, Mordacchini M, Dazzi P, et al. GNOSIS: Proactive image placement using graph neural networks & deep reinforcement learning. In: Proceedings of the IEEE 16th International Conference on Cloud Computing (CLOUD). Chicago, USA: IEEE, 2023. 120−128 [30] Ahn S, Seo Y, Shin J. Deep auto-deferring policy for combinatorial optimization [Online], avaliable: https://openreview.net/forum?id=Hkexw1BtDr, March 12, 2024 [31] Hu H Y, Zhang X D, Yan X W, Wang L F, Xu Y H. Solving a new 3D bin packing problem with deep reinforcement learning method. arXiv preprint arXiv: 1708.05930, 2017. [32] Duan L, Hu H Y, Qian Y, Gong Y, Zhang X D, Xu Y H, et al. A multi-task selected learning approach for solving 3D flexible bin packing problem. arXiv preprint arXiv: 1804.06896, 2019. [33] Verma R, Singhal A, Khadilkar H, Basumatary A, Nayak S, Singh H V, et al. A generalized reinforcement learning algorithm for online 3D bin-packing. arXiv preprint arXiv: 2007.00463, 2020. [34] Liu H W, Zhou L, Yang J L, Zhao J H. The 3D bin packing problem for multiple boxes and irregular items based on deep Q-network. Applied Intelligence, 2023, 53(20): 23398−23425 doi: 10.1007/s10489-023-04604-6 [35] Li D D, Ren C W, Gu Z Q, Wang Y X, Lau F. Solving packing problems by conditional query learning [Online], avaliable: https://openreview.net/forum?id=BkgTwRNtPB, March 12, 2024 [36] Jiang Y, Cao Z G, Zhang J. Learning to solve 3-D bin packing problem via deep reinforcement learning and constraint programming. IEEE Transactions on Cybernetics, 2023, 53(5): 2864−2875 doi: 10.1109/TCYB.2021.3121542 [37] Zhang J W, Zi B, Ge X Y. Attend2Pack: Bin packing through deep reinforcement learning with attention. arXiv preprint arXiv: 2107.04333, 2021. [38] Que Q Q, Yang F, Zhang D F. Solving 3D packing problem using Transformer network and reinforcement learning. Expert Systems With Applications, 2022, 214: Article No. 119153 [39] Parker J A, Kenyon R V, Troxel D E. Comparison of interpolating methods for image resampling. IEEE Transactions on Medical Imaging, 1983, 2(1): 31−39 doi: 10.1109/TMI.1983.4307610 -
下载:
计量
- 文章访问数: 601
- HTML全文浏览量: 159
- PDF下载量: 107
- 被引次数: 0
