A Compressed Sensing Reconstruction Based on Elastic Collision and Gradient Pursuit Strategy for WSNs
-
摘要: 为提高压缩感知(Compressed sensing, CS)大规模稀疏信号重构精度, 提出了一种联合弹性碰撞优化与改进梯度追踪的WSNs (Wireless sensor networks)压缩感知重构算法.首先, 创新地提出一种全新的智能优化算法---弹性碰撞优化算法(Elastic collision optimization algorithm, ECO), ECO模拟物理碰撞信息交互过程, 利用自身历史最优解和种群最优解指导进化方向, 并且个体以N(0, 1)概率形式散落于种群最优解周围, 在有效提升收敛速度的同时扩展了个体搜索空间, 理论定性分析表明ECO依概率1收敛于全局最优解, 而种群多样性指标分析证明了算法全局寻优能力.其次, 针对贪婪重构算法高维稀疏信号重构效率低、稀疏度事先设定的缺陷, 在设计重构有效性指数的基础上将ECO应用于压缩感知重构算法中, 并引入拟牛顿梯度追踪策略, 从而实现对大规模稀疏度未知数据的准确重构.最后, 利用多维测试函数和WSNs数据采集环境进行仿真, 仿真结果表明, ECO在收敛精度和成功率上具有一定优势, 而且相比于其他重构算法, 高维稀疏信号重构结果明显改善.Abstract: In order to improve the precision of compressed sensing (CS) sparse reconstruction algorithm, a CS reconstruction algorithm based on elastic collision optimization (ECO) and improved gradient pursuit strategy for WSNs is proposed. First of all, a new intelligent optimization computing technology: ECO is put forward. Referred to physical collision information interaction process, the historical optimal solution and population optimal solution are used to guide evolutionary direction and individuals are spread around the optimal solution in the form of N(0, 1), which helps to improve the convergence speed and extend the individual search space. Qualitative analysis shows that ECO can converge to the global optimal solution in probability 1 and the analysis of the diversity index shows that the algorithm has the ability of global optimization. Secondly, aiming at the defects of greedy reconstruction algorithm as low reconstruction efficiency and sparsity set in advance for high dimensional sparse signals, the ECO is applied to the CS reconstruction algorithm on the basis of the design validity index, and the quasi Newton gradient pursuit strategy is also introduced, which helps to realize the accurate reconstruction of large scale sparse data. Finally, simulation is carried out using multidimensional test functions and WSNs data acquisition environment. The simulation results show that ECO has certain advantages in convergence accuracy and success rate, and compared with other reconstruction algorithms, the reconstruction results significantly improved for high dimensional sparse signal.
-
Key words:
- Wireless sensor networks (WSNs) /
- elastic collision optimization (ECO) /
- convergence efficiency /
- compressed sensing (CS) /
- sparse reconstruction algorithm
-
智能优化算法又称启发式计算技术[1], 其在模拟种群生物学行为或者物质物理属性变化的基础上, 通过迭代计算实现最优化问题的求解.由于具有全局搜索能力以及稳定性好、容易实现等特点[2], 智能优化算法已经被广泛应用于日常生产生活各个领域.
随着智能优化理论研究不断深入, 大量不同类型的智能优化算法被相继提出, 如蚁群算法(Ant colony optimization, ACO)[3]、粒子群算法(Particle swarm optimization, PSO)[2]、混合蛙跳算法(Shuffled frog leaping algorithm, SFLA)[4]、烟花算法(Fireworks algorithm, FA)[5]、模拟退火算法(Simulated annealing, SA)[6]等等.当前实际优化问题日趋复杂, 高维度、多模态[7]和动态性[8]给经典智能优化算法带来了严酷的挑战.研究表明种群样本多样性和局部极值逃避学习能力是影响智能优化算法收敛性能的重要因素, 学者们也围绕扩展算法学习进化搜索空间、不同类型算法混合协同进化等方向展开深入研究: Liang[9]等提出了一种CLPSO (Comprehensive learning PSO)算法, 利用种群历史信息对PSO进化方向进行引导, 以增强算法跳出局部极值能力, 这种借鉴历史信息"回溯"思想具有典型代表意义, 不仅让算法具有了记忆功能, 而且有效改善了算法全局寻优能力; 文献[10]提出了一种改进布谷鸟优化算法, 将模式搜索(Pattern search, PS)引入到算法中, 利用PS快速搜索能力以提高算法收敛效率, 另外, 田瑾提出的量子行为粒子群优化算法[11]、Kang提出的和声粒子群算法[12]等都属于利用特定策略或者特定模型对算法进行引导, 以期达到克服容易陷入局部极值、收敛效率低的缺陷; 文献[13]融合粒子群与模拟退火算法, 提出了一种(Particle swarm optimization-simulated annealing, PSO-SA)协同进化算法, 利用不同算法的互补特性, 取长补短, 并行协同进化, 从而提高了改进算法的鲁棒性和适应性.这些改进算法提高了解决复杂优化问题的能力, 但是仍存在局限性: 1)改进算法往往简单融合不同类型进化策略, 并没有深入分析融合的合理性; 2)大多数改进算法虽然扩展了种群搜索空间, 但是缺少种群样本多样性理论分析支撑. 3)改进算法很大程度上增加了实现难度和计算复杂度, 然而这些牺牲代价却没有得到足够重视. "看似简单的过程往往包含着最朴素的哲理", 本文模拟物体间极短的相互作用过程, 以碰撞前后物理量变化作为学习进化机制, 提出一种全新的智能优化算法—弹性碰撞优化算法(Elastic collision optimization algorithm, ECO), 并从理论角度对算法收敛性和全局寻优能力进行分析.
压缩感知(Compressed sensing, CS)是一种新的信号处理理论[14], 其颠覆了传统Shannon-Nyquist采样定理限制, 具有强大的生命力.稀疏信号重构算法是当前CS研究热点之一, 也相继提出了组合优化、凸优化以及贪婪迭代等不同类型重构算法, 特别是对于信号稀疏度未知下的重构算法, 学者们进行了深入研究:王艳芬等[15]提出了一种稀疏度自适应超宽带信道估计算法, 该算法通过逐步逼近信道稀疏度, 实现稀疏度未知信号的精确重构, 但是逐步逼近方式很大程度地增加了算法运算量; YANG等[16]提出了一种稀疏自适应匹配追踪算法, 通过设置自适应步长逐渐逼近原始信号, 但是步长设置大小对重构精度和重构效率具有重要影响.当前大规模数据处理效率低、重构算法参数难以选择、信号稀疏度事先确定等缺陷仍是亟需解决的问题, 为此本文提出一种联合弹性碰撞优化与改进梯度追踪的WSNs压缩感知重构算法, 主要做了以下几个方面工作:
1) 提出全新弹性碰撞优化算法, 给出基于碰撞信息交换和N概率散落算法的更新机制, 并从理论角度分析算法收敛性和群体样本多样性.
2) 对StOMP贪婪重构算法进行改进, 引入ECO和拟牛顿梯度追踪策略以实现大规模稀疏度未知数据的准确重构.
3) 利用多维测试函数和WSNs数据采集环境进行仿真, 以验证所提算法的有效性.
1. 弹性碰撞优化算法(ECO)
1.1 ECO算法实现
碰撞是一种常见的物理现象, 两个做相对运动的物体在极短时间内发生接触, 并迅速改变运动状态.碰撞按能量角度可以分为完全弹性碰撞(Complete elastic collision, CE)、完全非弹性碰撞(Complete inelastic collision, CI)和非完全弹性碰撞(Non complete elastic collision, NCE), 为了方便描述碰撞物理过程, 以对心碰撞进行研究:设质量为、$ m_{2} $的两个物体分别以速度$ \bm{v}_{1} $和$ \bm{v}_{2} $相向运动, $ \Delta t $时刻后发生碰撞, 碰撞后物体速度为和$ \bm{v}_{2}^{\prime } $, 对于不同的碰撞过程, $ \bm{v}_{1}^{\prime } $和计算公式分别为:
$$ \begin{align} \label{eq1}\nonumber {\rm CE}: &\begin{cases} m_{1} \bm{v}_{1} +m_{2} \bm{v}_{2} =m_{1} \bm{v}_{1}^{\prime }+m_{2} \bm{v}_{2}^{\prime } \\ \frac{1}{2}m_{1} \bm{v}^{2}_{1} +m_{2} \bm{v}^{2}_{2} =m_{1} \bm{v'}^{2}_{1}+m_{2} \bm{v'}^{2}_{2} \\ \end{cases}\Rightarrow \\ &\begin{cases} \bm{v}_{1}^{\prime }=\dfrac{\left( {m_{1} -m_{2} } \right) \bm{v}_{1} +2m_{2} \bm{v}_{2} }{m_{1} +m_{2} } \\[3mm] \bm{v}_{2}^{\prime }=\dfrac{\left( {m_{2} -m_{1} } \right) \bm{v}_{2} +2m_{1} \bm{v}_{1} }{m_{1} +m_{2} } \end{cases} \end{align} $$ (1) $$ \begin{align} \label{eq2}\nonumber {\rm CI}: & m_{1} \bm{v}_{1} +m_{2} \bm{v}_{2} =\left( {m_{1} +m_{2} } \right)\bm{v}^{\prime }\Rightarrow \\ &\bm{v}^{\prime }=\frac{m_{1} \bm{v}_{1} +m_{2} \bm{v}_{2} }{m_{1} +m_{2} } \end{align} $$ (2) $$ \begin{align} \label{eq3}\nonumber {\rm NCE}: &\left| {\bm{v}_{1}^{\prime }} \right|_{CI} ＜\left| {\bm{v}_{1}^{\prime }} \right|＜\left| {\bm{v}_{1}^{\prime }} \right|_{CE}, \\ & \left| {\bm{v}_{2}^{\prime }} \right|_{CI} ＜\left| {\bm{v}_{2}^{\prime }} \right|＜\left| {\bm{v}_{2}^{\prime }} \right|_{CE} \end{align} $$ (3) 从式(1)~(3)可以看出, 碰撞后速度融合了碰撞前物体动量信息, 也可以说碰撞过程具有一定的"学习"能力.为此借鉴弹性碰撞过程, 提出弹性碰撞优化算法:对于$ D $维优化问题, 在解空间$ R^{D} $内分布着由$ n $个单位质量粒子组成的群体, 每个粒子$ \bm{X}_{i} (t)=\left[{x_{i1} \left(t \right), x_{i2} (t), \cdots, x_{iD} (t)} \right] $代表一个可能的解, 、$ \bm{B}(t)=\left[{b_{1} (t), b_{2} (t), \cdots, b_{D} (t)} \right] $分别为$ \bm{X}_{i} (t) $历史最优解和当前群体最优解.
定义1(优化模型). 对于给定优化函数, 寻找一个粒子$ \bm{X}_{\rm best} \in \{ \bm{P}\left(1 \right), \bm{P}\left(2 \right)$, $ (T_{\max } $为算法最大运算次数), 使得$ f\left({\bm{X}_{\rm best} } \right) $最优.
定义2(极值碰撞). 在ECO中, $ \bm{G}_{i} (t) $与$ \bm{B}(t) $分别以速度$ \bm{v}_{G} $与相向运动, $ \Delta t $时刻后发生碰撞, 随后两粒子以速度与$ \bm{v}'_{B} $继续运动, $ \Delta {t}' $时刻后得到达新的位置$ \bm{G}_{i}^{\prime }(t) $和, 即有(以$ \max f\left[{\bm{X}_{i} (t)} \right] $为例):
1) 完全弹性碰撞
根据式(1)~(3)可以得到$ \bm{v}'_{G} =-\bm{v}_{B} $、$\bm{v}'_{B} =-\bm{v}_{G} $, 令$ \Delta {t}'=k\Delta t $有:
$$ \begin{equation} \label{eq4} { {\rm CE}: \begin{cases} \bm{B}'( t )=\bm{B}( t ) \dfrac{\left( {1+k} \right)\left| {\bm{v}_{G} } \right|} {\left| {\bm{v}_{G} } \right|+\left| {\bm{v}_{B} } \right|} +\\[3mm] \qquad\qquad\bm{G}_{i} ( t )\dfrac{\left| {\bm{v}_{B} } \right|- k\left| {\bm{v}_{G} } \right|}{\left| {\bm{v}_{G} } \right|+ \left| {\bm{v}_{B} } \right|} \\[3mm] \bm{G}_{i}^{\prime }( t )=\bm{B}( t ) \dfrac{\left| {\bm{v}_{G} } \right|-k\left| {\bm{v}_{B} } \right|} {\left| {\bm{v}_{G} } \right|+\left| {\bm{v}_{B} } \right|}+ \\[3mm]\qquad \qquad\bm{G}_{i} ( t )\dfrac{\left( {1+k} \right)\left| {\bm{v}_{B} } \right|}{\left| {\bm{v}_{G} } \right|+\left| {\bm{v}_{B} } \right|} \end{cases} } \end{equation} $$ (4) 2) 完全非弹性碰撞
根据式(1)~(3)可以得到, 令有:
$$ \begin{align} \label{eq5}\nonumber {\rm CI}: &\bm{B}"( t )\left( {\bm{G}_{i}^{\prime \prime }( t )} \right) =\\\nonumber & \bm{B}( t )\frac{\left( {2+k} \right)\left| {\bm{v}_{G} } \right|-k\left| {\bm{v}_{B} } \right|}{2\left( {\left| {\bm{v}_{G} } \right|+\left| {\bm{v}_{B} } \right|} \right)}+\\ & \bm{G}_{i} ( t )\frac{\left( {2+k} \right)\left| {\bm{v}_{B} } \right|-k\left| {\bm{v}_{G} } \right|}{2\left( {\left| {\bm{v}_{G} } \right|+\left| {\bm{v}_{B} } \right|} \right)} \end{align} $$ (5) 3) 非完全弹性碰撞
根据式(1)~(3)且令:
$$ \begin{equation} \label{eq6} {\rm NCE}: \bm{B}"'( t )=\beta \bm{B}'( t ), \bm{G}_{i}^{\prime \prime \prime }\left( t \right)=\beta \bm{G}_{i}^{\prime }( t ) \end{equation} $$ (6) 其中, $ k $、$ \beta \in \left({0, 1} \right) $为控制系数. 图 1给出了极值碰撞示意图.为了进一步反映粒子适应度值对碰撞过程的影响, 设定粒子速度为粒子自身目标函数值, 即:
$$ \begin{equation} \label{eq7} \left| {\bm{v}_{G} } \right|=f\left[ {\bm{G}_{i}^{\prime }( t )} \right], \left| {\bm{v}_{B} } \right|=f\left[ {\bm{B}( t )} \right] \end{equation} $$ (7) 定义3(碰撞更新) 对于粒子$ \bm{X}_{i} \left(t \right) $, 根据极值碰撞定义(不失一般性取$ k=1) $, 给出其更新方式为:
$$ \begin{equation} \label{eq8} \bm{X}_{i} \left( {t+1} \right)=\begin{cases} {\pmb U}_{i} ( t )+\sigma_{i} ( t )N\left( {0, 1} \right), r_{1} \geq \varepsilon \\ \bm{X}_{i} ( t ) \\ \end{cases} \end{equation} $$ (8) $$ \begin{equation} \label{eq9} \sigma_{i} ( t )=\left| {\bm{B}\left( t \right)-\bm{G}_{i} ( t )} \right| \end{equation} $$ (9) $$ \begin{equation} \label{eq10} {\pmb U}_{i} ( t )= \begin{cases} \bm{B}( t )\dfrac{2f\left( {\bm{G}_{i} } \right)} {f\left( {\bm{G}_{i} } \right)+f\left( {\bm{B}} \right)}+ \\[3mm]\qquad \bm{G}_{i} ( t ) \dfrac{f\left( {\bm{B}} \right)-f\left( {\bm{G}_{i} } \right)} {f\left( {\bm{G}_{i} } \right)+f\left( {\bm{B}} \right)}, \quad r_{2} \leq 0.5 \\[3mm] \bm{B}( t )\dfrac{3f\left( {\bm{G}_{i} } \right)- f\left( {\bm{B}} \right)}{2\left( {f\left( {\bm{G}_{i} } \right)+ f\left( {\bm{B}} \right)} \right)}+\\[3mm]\qquad \bm{G}_{i} ( t ) \dfrac{3f\left( {\bm{B}} \right)-f\left( {\bm{G}_{i} } \right)} {2\left( {f\left( {\bm{G}_{i} } \right)+f\left( {\bm{B}} \right)} \right)}, \\ \qquad \quad 0.5＜r_{2} \leq 0.5+\xi \\[3mm] \beta \Bigg[ \bm{B}( t )\dfrac{2f\left( {\bm{G}_{i} } \right)}{f\left( {\bm{G}_{i} } \right)+f\left( {\bm{B}} \right)}+ \\[3mm]\qquad \bm{G}_{i} ( t )\dfrac{f\left( {\bm{B}} \right)-f\left( {\bm{G}_{i} } \right)}{f\left( {\bm{G}_{i} } \right)+f\left( {\bm{B}} \right)} \Bigg], \\ \qquad \quad\quad 0.5+\xi ＜r_{2} ＜1 \end{cases} \end{equation} $$ (10) 其中, $ r_{1} \in \left({0, 1} \right) $、$ r_{2} \in \left({0, 1} \right) $为随机数, $ \varepsilon \in \left({0, 1} \right) $为更新控制系数, $ \xi \in \left({0, 0.5} \right) $为碰撞自适应学习因子.
从碰撞更新参数设置来看, 更新策略只涉及$ \varepsilon $、$ \xi $和$ \beta \in \left({0, 1} \right) $ 3个参数, 因此具有参数设置少的特点; 从碰撞更新方式来看, $ \bm{X}_{i} \left(t \right) $以概率$ 1-\varepsilon $进行更新, 并且利用$ \xi $融合了3种不同的"极值碰撞"方式, 而且粒子直接向自身历史最优解和当前群体最优解学习, 并且以N$ \left({0, 1} \right) $形式进行扰动.不同的更新策略以及高斯扰动提高了群体样本多样性, 有效扩展了算法搜索空间. ECO具体实现流程为:
算法1. ECO算法
1.设置参数$ \varepsilon $、$ \xi $、$ \beta $、$ T_{\max } $, 在解空间内随机生成群体$ {\bf{\Theta }}\left(0 \right) $ //初始化
2. while $ (t\leq T_{\max }) $ //迭代更新
3. For $ i=1: n $
4.根据式(8) $\sim$ (10)对$ \bm{X}_{i} (t) $进行更新;
5.如果, 用新得到的粒子替换$ \bm{X}_{i} (t) $; 否则保持$ \bm{X}_{i} (t) $不变;
6.更新$ \bm{X}_{i} (t) $历史最优解$ \bm{G}_{i}^{\prime }(t) $;
7. end for
8.更新群体最优解$ \bm{B}(t) $, $ t+1\to t $
9. end while
计算复杂度 ECO算法迭代一次计算复杂度为O, 种群初始化计算复杂度为O$\left(n \right) $, 因此ECO计算复杂度为$ T_{\max } {\rm O}\!\left({n\log D} \right)+{\rm O}\!\left(n \right) $.
2. ECO收敛性和群体样本多样性分析
对于群体$ {\bf{\Theta }}(t) $, $ \left\{ {{\bf{\Theta }}(t), t=0, 1, 2, \cdots } \right\} $构成离散时间随机过程, 其状态空间为, 根据"碰撞更新"定义可以看出, 当前状态只与上一个状态有关, 即, 因此为马尔科夫链.
定义4 (最优解结合). 对于优化问题, $ t $时刻最优解集合为:
$$ \begin{align} \label{eq11}\nonumber \bm{E}^{\ast }&=\left\{ {\bm{X}^{\ast }\left| {\exists\: \bm{X}\ne \bm{X}^{\ast }, f\left( {\bm{X}} \right)＜f\left( {\bm{X}^{\ast }} \right)} \right.} \right\} \\ &\quad \bm{X}\in \left\{ {{\bf{\Theta }}( t ), t=0, 1, 2, \cdots } \right\} \end{align} $$ (11) 令为$ {\bf{\Theta }}(t) $内最优解个数.从粒子更新过程可以看出, 算法总是选择保留较优的粒子留在群体内, 因此$ \mathbb{Z}\left({{\bf{\Theta }}\left({t+1} \right)} \right)\geq \mathbb{Z}\left({{\bf{\Theta }}(t)} \right) $, 即序列$ \left\{ {\mathbb{Z}\left({{\bf{\Theta }}\left(0 \right)} \right), \cdots, \mathbb{Z}\left({{\bf{\Theta }}\left(t \right)} \right)} \right\} $是单调不递减的.即:
$$ \begin{equation} \label{eq12} p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( t \right)} \right)>0\left| {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t-1} \right)} \right)>0} \right.} \right)\bm{>}\bf{0}, \forall\: t\geq \bf{1} \end{equation} $$ (12) 另外, 由于采用高斯扰动形式, 使得任意时刻粒子成为任一可行解的概率不为0, 也就是说任意时刻粒子成为最优解的概率也不为0, 这表明算法在某个时刻存在不包含最优解的可能, 但是满足:
$$ \begin{equation} \label{eq13} p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( t \right)} \right)>0\left| {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t-1} \right)} \right)=0} \right.} \right)\bm{>}\bm{0}, \forall\: t\geq \bm{1} \end{equation} $$ (13) 推论1. 序列$ \bm{X}_{i} (t) \, (i=1, 2, \cdots, n) $的数学期望值收敛于某个稳定值.
证明. 从式(8)和式(10)可以得出:
$$ \begin{equation} \label{eq14} {\rm E}\left[ {\bm{X}_{i} \left( {t+1} \right)} \right]=\varepsilon {\rm E}\left[ {\bm{X}_{i} ( t )} \right]+\left( {1-\varepsilon } \right)\times \Delta \left( t \right) \end{equation} $$ (14) 其中, $ \Delta (t) $具体计算公式为:
$$ \begin{equation}\label{eq15} \begin{subarray}{l} \Delta ( t )=\, 0.5\left[ \frac{\left( {2\bm{B}( t )f\left( {\bm{G}_{i} } \right)+ \bm{G}_{i} ( t )\left( {f\left( {\bm{B}} \right)- f\left( {\bm{G}_{i} } \right)} \right)} \right)}{\left( {f\left( {\bm{G}_{i} } \right)+ f\left( {\bm{B}} \right)} \right)} \right]+\\ \qquad \xi \left[ \frac{\left( {\bm{B}( t )\left( {3f\left( {\bm{G}_{i} } \right)- f\left( {\bm{B}} \right)} \right)+\bm{G}_{i} ( t )\left( {3f\left( {\bm{B}} \right)- f\left( {\bm{G}_{i} } \right)} \right)} \right)}{\left( {2\left( {f\left( {\bm{G}_{i} } \right)+ f\left( {\bm{B}} \right)} \right)} \right)} \right]+ \\\qquad \beta \left( {0.5-\xi } \right)\left[ \frac{\left( {2\bm{B} ( t )f\left( {\bm{G}_{i} } \right)+\bm{G}_{i} ( t )\left( {f\left( {\bm{B}} \right)- f\left( {\bm{G}_{i} } \right)} \right)} \right)}{\left( {f\left( {\bm{G}_{i} } \right)+f\left( {\bm{B}} \right)} \right)} \right] \end{subarray}\end{equation} $$ (15) 根据式(14)有:
$$ \begin{align} \label{eq16}\nonumber & {\rm E}\left[ {\bm{X}_{i} \left( {t+1} \right)} \right] =\varepsilon {\rm E}\left[ {\bm{X}_{i} \left( t \right)} \right]+\left( {1-\varepsilon } \right)\times \Delta ( t ) =\\ \nonumber &\qquad\varepsilon^{2}{\rm E}\left[ {\bm{X}_{i} \left( {t-1} \right)} \right]+\varepsilon \left( {1-\varepsilon } \right)\Delta \left( {t-1} \right)+ =\\\nonumber & \qquad\left( {1-\varepsilon } \right)\times \Delta ( t )=\cdots = \\ \nonumber &\qquad\varepsilon^{t}{\rm E}\left[ {\bm{X}_{i} \left( 1 \right)} \right]+\varepsilon^{t-1}\left( {1-\varepsilon } \right)\Delta \left( 1 \right)+\\ &\qquad \varepsilon^{t-2}\left( {1-\varepsilon } \right)\Delta \left( 2 \right)+\cdots +\left( {1-\varepsilon } \right)\times \Delta ( t ) \end{align} $$ (16) 由于$ \varepsilon \in \left({0, 1} \right) $, 因此有:
$$ \begin{equation} \label{eq17} \lim\limits_{t\to \infty } {\rm E}\left[ {\bm{X}_{i} \left( {t+1} \right)} \right]=\sum\limits_{i=0}^{t-1} {\varepsilon^{t-i}\left( {1-\varepsilon } \right)\Delta \left( i \right)} \end{equation} $$ (17) 推论2. ECO算法以概率1收敛于全局最优解.
证明. 设$ t $时刻$ \mathbb{Z}\left({{\bf{\Theta }}(t)} \right)=0 $的概率为$ p\left({\mathbb{Z}\left({{\bf{\Theta }}(t)} \right)=0} \right) $, 由于$ {\bf{\Theta }}(t) $为马尔科夫链, 因此根据条件概率公式有:
$$ \begin{align}\nonumber & p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0} \right) = \\\nonumber &\qquad p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0\left| {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)=0} \right.} \right)\times\\\nonumber &\qquad p\left( {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)=0} \right) +\\\nonumber &\qquad p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0\left| {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)\ne 0} \right.} \right)\times \\ &\qquad p\left( {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)\ne 0} \right) \end{align} $$ (18) 根据式(13)可知, 因此:
$$ \begin{align}\nonumber & p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0} \right) = \\\nonumber &\qquad p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0\left| {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)=0} \right.} \right)\times \\ &\qquad p\left( {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)=0} \right) \end{align} $$ (19) 根据式(13)可知, $ \forall\: t\geq 1 $存在一个足够小的正实数使得$ p\left({\mathbb{Z}\left({{\bf{\Theta }}\left(t \right)} \right)>0\left| {\mathbb{Z}\left({{\bf{\Theta }}\left({t-1} \right)} \right)=0} \right.} \right)\bm{>}\gamma $成立, 因此有:
$$ \begin{align}\nonumber &p\left( \mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0\left| {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)=0} \right. \right) = \nonumber\\ &\qquad 1-p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)>0\left| {\mathbb{Z}\left( {{\bf{\Theta }}\left( t \right)} \right)=0} \right.} \right)\leq \nonumber\\ &\qquad 1-\gamma \end{align} $$ (20) 联立式(19)和式(20)可得:
$$ \begin{align} \label{eq21}\nonumber &p\left( {\mathbb{Z}\left( {\bm{\Theta }\left( {t+1} \right)} \right)=0} \right)\leq \nonumber\\& \qquad\left( {1-\gamma } \right)p\left( {\mathbb{Z}\left( {{\bf{\Theta }}( t )} \right)=0} \right) \Rightarrow\nonumber\\& \qquad p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0} \right)\leq \cdots \leq\nonumber\\ &\qquad \left( {1-\gamma } \right)^{t+1}p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( 0 \right)} \right)=0} \right) \end{align} $$ (21) 当$ t\to \infty $时, $ \lim\nolimits_{t\to \infty } ({1-\gamma })^{t+1}=0 $, 所以有$ p(\mathbb{Z}({\bf{\Theta }}(t+ $ $1))=0)\leq 0 $, 由于表示概率值, 因此有:
$$ \begin{equation} \label{eq22} \lim\limits_{t\to \infty } p\left( {\mathbb{Z}\left( {{\bf{\Theta }}\left( {t+1} \right)} \right)=0} \right)=0 \end{equation} $$ (22) 从式(22)可以得出, 随着算法不断运行, $ {\bf{\Theta }}\left(t \right) $不含最优解的概率为0, 即表明ECO算法以概率1收敛于全局最优解.
从推论2可以看出, ECO算法具有全局收敛性, 而群体样本多样性也是判断算法收敛性能好坏的重要指标, 为此给出ECO样本多样性评价指标.
定义4. $ t $时刻, ECO群体样本多样性评价指标为:
$$ %\pagebreak %\onecolumn %\begin{multicols}{2} \vspace{-5mm} \begin{equation} \label{eq23} \aleph \left( {{\bf{\Theta }}( t )} \right)=\frac{1}{nD}\sum\limits_{i=1}^n {\sum\limits_{j=1}^D {\left[ {x_{ij} ( t )-\frac{1}{n}\sum\limits_{i=1}^n {x_{ij} ( t )} } \right]^{2}} } \end{equation} $$ (23) 从定义4可以看出, $ \aleph \left({{\bf{\Theta }}(t)} \right) $反映了粒子与群体均值的远近程度, 取值越大表明群体内粒子间相对位置更加分散, 群体样本多样性越高.
推论3. $ t\to \infty $时, ECO群体样本多样性评价指标期望值$ {\rm E}\left[{\aleph \left({{\bf{\Theta }}(t)} \right)} \right] $为:
$$ \begin{equation} \label{eq24} \lim\limits_{t\to \infty } {\rm E}\left[ {\aleph \left( {{\bf{\Theta }}( t )} \right)} \right]=\frac{n-1}{n^{2}D}\sum\limits_{i=1}^n {\sum\limits_{j=1}^D {\sigma_{ij}^{2} } } ( t ) \end{equation} $$ (24) 其中, $ \sigma_{ij} (t) $为$ x_{ij} \left(t \right) $的标准差.
证明. 令, 则:
$$ \begin{align} \label{eq25}\nonumber & {\rm E}\left[ {\aleph \left( {{\bf{\Theta }}( t )} \right)} \right]=\frac{1}{nD}\sum\limits_{i=1}^n {\sum\limits_{j=1}^D {{\rm E}\left[ {x_{ij} ( t )-\overline {x_{j} ( t )} } \right]^{2}} } = \\ \nonumber &\qquad\frac{1}{nD}\sum\limits_{i=1}^n \sum\limits_{j=1}^D {\rm E}\!\Big[ x_{ij} ( t )\!-\! {\rm E}(x_{ij} ( t ))+ \\ \nonumber &\qquad{\rm E}(x_{ij} ( t ))\!-\! \overline {x_{j} ( t )} \Big]^{2}\!\!= \\\nonumber &\qquad\frac{1}{nD}\sum\limits_{i=1}^n {\sum\limits_{j=1}^D \bigg\{ {{\rm E}[ {x_{ij} ( t )-{\rm E}(x_{ij} ( t ))} ]^{2}} } -\\ \nonumber &\qquad 2{\rm E}( {\left[ {x_{ij} ( t )-{\rm E}(x_{ij} ( t ))} \right][ {{\rm E}(x_{ij} ( t ))-\overline {x_{j} ( t )} } ]} )+ \\ &\qquad {{\rm E}\left[ {{\rm E}(x_{ij} ( t ))-\overline {x_{j} ( t )} } \right]^{2}} \Bigg\} \end{align} $$ (25) 令$ \sigma_{ij}^{2} (t)={\rm E}\left[{x_{ij} (t)-{\rm E}(x_{ij} (t))} \right]^{2} $, 则:
$$ \begin{align} \label{eq26} &{\rm E}( {[ {x_{ij} ( t )\!-\! {\rm E}(x_{ij} ( t ))} ][ {{\rm E}(x_{ij} ( t ))-\overline {x_{j} ( t )} } ]} )=\frac{\sigma_{ij}^{2} ( t )}{n} \end{align} $$ (26) $$ \begin{align} \label{eq27}\nonumber &{\rm E}[ {\overline {x_{j} ( t )} -{\rm E}(x_{ij} ( t ))} ]^{2}=\\ &\quad \frac{1}{n}\sum\limits_{k=1}^n {\sigma_{kj}^{2} ( t )} +\left[ {{\rm E}(x_{kj} ( t ))-\frac{1}{n}\sum\limits_{k=1}^n {{\rm E}(x_{kj} ( t ))} } \right]^{2} \end{align} $$ (27) 联立式(25)~(27)有:
$$ \begin{equation} \label{eq28} {\rm E}\left[ {\aleph \left( {{\bf{\Theta }}\left( t \right)} \right)}\right]=\frac{n-1}{n^{2}D}\sum\limits_{i=1}^n {\sum\limits_{j=1}^D {\sigma _{ij}^{2} } } ( t )+\aleph \left( {{\rm E}(x_{ij} ( t ))} \right) \end{equation} $$ (28) 其中, $ \aleph \left({{\rm E}(x_{ij} (t))} \right) $表示的多样性, 根据推论1, 当$ t\to \infty $时$ {\rm E}\left({\bm{X}_{i} (t)} \right) $收敛于某个稳定值, 即$ \lim\nolimits_{t\to \infty } \aleph \left({{\rm E}(x_{ij} (t))} \right)=0 $, 因此有:
$$ \begin{equation} \label{eq29} \lim\limits_{t\to \infty } {\rm E}\left[ {\aleph \left( {{\bf{\Theta }}( t )} \right)} \right]=\frac{n-1}{n^{2}D}\sum\limits_{i=1}^n {\sum\limits_{j=1}^D {\sigma_{ij}^{2} } } ( t ) \end{equation} $$ (29) 从推论3可以看出, 算法运算初期, 由于粒子随机分布在搜索空间内, 因此$ \sigma_{ij} (t) $取值较大, 表明算法样本多样性较强, 随着迭代次数增加, 群体向全局最优解靠拢, 导致逐渐降低, 也就说群体多样性在下降, 但是由于ECO算法采用高斯扰动机制, 保证了粒子间差异性, 维持了群体样本多样性.特别的, 扰动机制和不同的"极值碰撞"方式有效提高了算法跳出局部极值的能力, 增强了算法深度搜索能力.
从ECO实现流程可以看出, ECO属于随机搜索技术范畴, "大规模种群粒子随机分布解空间"的形式使得当前大多数智能优化算法能够以一定概率收敛于全局最优解, 但是"容易陷入局部极值"的缺陷是目前绝大多数智能优化算法需要继续解决的难题, 而ECO通过模拟多种弹性碰撞过程, 提供了多种学习策略, 而且其涉及参数较少, 因此具有容易实现、收敛精度高的优势.此外, 智能优化算法研究已经进入了从理论上深度分析算法性能的阶段, ECO多样性分析证明了其能够保持较好的深度搜索能力, 从一定意义上来讲, ECO研究内容对当前智能优化算法论证具有一定借鉴意义, 很好地克服了传统智能优化算法盲目引入改进策略的缺陷.
3. 压缩感知StOMP贪婪重构算法改进
3.1 压缩感知理论(CS)
当一个$ N $维信号$ \bm{x}_{N\times 1} $可以在某个稀疏矩阵${\bf{\Psi }}_{N\times N} $下用仅含有$ K\ll N $个非零系数的向量$ \bm{s}_{N\times 1} $进行稀疏表示时, 即$ \bm{x}_{N\times 1}={\bf{\Psi }}_{N\times N} \times \bm{s}_{N\times 1} $, 则称$ \bm{x}_{N\times 1} $在$ {\bf{\Psi }}_{N\times N} $上是$ K $度稀疏的.此时用测量矩阵$ {\bf{\Phi }}_{M\times N} $将$ \bm{x}_{N\times 1} $进行投影, 得到测量向量$ \bm{y}_{M\times 1}$
$$ \begin{equation} \label{eq30} \bm{y}_{M\times 1} ={\bf{\Phi }}_{M\times N} \times \bm{x}_{N\times 1} ={\bf{\Phi }}_{M\times N} \times {\bf{\Psi }}_{N\times N} \times \bm{s}_{N\times 1} \end{equation} $$ (30) 令$ \bm{A}_{M\times N} {\bf{=\Phi }}_{M\times N} \times {\bf{\Psi}}_{N\times N} $, 有. CS理论认为当$ \bm{A}_{M\times N} $满足RIP条件[17]且测量数目$ M\geq CK\ln \left( {N/K} \right) $时, 可以通过求解最小$ l_{0} $范数稀恢复出$ \bm{s}_{N\times 1} $, 即:
$$ \begin{equation} \label{eq31} \min \| {\bm{s}} \|_{l_{0} }\;\;\;\;\;{\rm s.\, t.} \bm{y}=\bm{As}=\bf{\Phi \Psi}\bm{s} \end{equation} $$ (31) 由于求解(31)属于完全NP-hard难题, Donoho[14]等证明可以将最小$ l_{0} $范数求解转化为最小$l_{1}$范数求解.求解最小$l_{1}$范数重构方法统称为$l_{1} -LP$重构算法, 其中应用最为广泛、重构效果较为突出的是贪婪重构算法[16].
3.2 StOMP贪婪重构算法改进实现
方红等[18]对贪婪重构算法进行了深入研究, 并指出StOMP (stage-wise orthogonal matching pursuit)算法重构速度快, 适用于大规模信号处理, 但是存在运算量大、测量矩阵RIP (Restricted isometry property)条件要求高以及稀疏度$K $事先确定的缺陷, 为此在StOMP贪婪重构算法内引入ECO和拟牛顿梯度追踪策略, 并将稀疏信号重构分成"线下"和"线上"两个阶段(如图 2所示), 以实现大规模稀疏度未知数据的准确重构(基本StOMP贪婪重构算法原理见相关文献, 不再赘述).
图 2 改进StOMP贪婪重构算法实现Fig. 2 Improved StOMP greedy reconstruction algorithm implementation线下阶段 由于StOMP算法主要采用正交投影实现稀疏信号重构, 算法实际运算量较大, 不适用于实时性要求较高的场合, 而且算法参数"阈值$ \tau $ "和迭代次数$ t_{s} $取值对重构精度影响很大, 为此提出"线下ECO参数训练阶段"策略, 即利用样本数据$ \left({\bm{y}_{h}, {\hat{\bm{s}}}_{h} } \right) (\bm{y}_{h} $、$ {\hat{\bm{s}}}_{h} $分别为第$ h $个样本数据测量值和稀疏信号重构值)对StOMP算法$ \tau $和进行训练, 以得到最佳参数组合.
定义5. 对于StOMP算法参数配置问题, 定义ECO算法粒子编码为:
$$ \begin{equation} \label{eq32} \bm{X}_{i} =\left( {x_{i1}, x_{i2} } \right), \tau =x_{i1}, t_{s} =\left\lfloor {x_{i2} } \right\rfloor \end{equation} $$ (32) 其中$ \left\lfloor \cdot \right\rfloor $表示向下取整.
算法2. ECO优化StOMP算法参数配置
输入. 矩阵$ \bm{A}_{M\times N} $、样本数据 $\bm{ y}_{H} \} $、稀疏度$ K $、ECO算法相关参数、初始化ECO群体
1. For $ h=1: H $ //对第$ h $个样本进行训练
2. While (不满足ECO算法终止条件) do//执行ECO操作
3. For $ i=1: n $ //对第$ i $个粒子进行处理
4.根据ECO进化机制对粒子$ \bm{X}_{i} $进行更新; //粒子更新
5. StOMP算法初始化: $ t=1 $、$ \bm{r}_{0} =\bm{y}_{h} $、支撑集$ \bm{I}=\bm{\phi } $、$ {\hat{\bm{s}}}_{h, t} =\bm{0} $;
6. For $ t=1: t_{s} \left({\left\lfloor {x_{i2} } \right\rfloor } \right) $ // StOMP重构算法求解$ {\hat{\bm{s}}}_{h} $
7.根据计算公式$ J=\{ j \, |\, | \langle {r_{t-1}, \bm{\phi }_{j} } \rangle | > \tau \left({x_{i1} } \right) \} \, (j=1, $ $ \cdots, N) $, 找出$ \bm{A}_{M\times N} =\left({\bm{\phi }_{1}, \bm{\phi }_{2}, \cdots, \bm{\phi }_{N} } \right) $中与$ r_{t-1} $匹配的索引;
8.更新$ \bm{I}=\bm{I}\cup \bm{J} $、$ {\hat{\bm{s}}}_{h, t} =\left({\Phi_{I}^{\rm T} \Phi_{I} } \right)^{-1}\Phi_{I}^{\rm T} \bm{y}_{h} $、$ r_{t} =\bm{y}_{h} -\Phi_{I} {\hat{\bm{s}}}_{h, t} $;
9. End for
10.根据式(32)计算粒子$ \bm{X}_{i} $函数值, 更新$ \bm{X}_{i} $历史最优解;
11. End for
12.更新ECO群体最优解;
13. End while
14.输出第$ h $个样本对应的$ \left({\tau_{h}, t_{s, h} } \right) $;
15. End for
16.根据$ \tau =({\sum\nolimits_{h=1}^H {\tau_{h} } })/H $和$ t_{s} =\lfloor ({\sum\limits_{h=1}^H {t_{s, h} } })/H \rfloor $得到StOMP最佳参数配置$ \left({\tau, t_{s} } \right) $.
定义6. 对于StOMP算法参数配置问题, 定义ECO算法目标函数为:
$$ \begin{equation} \label{eq33} \min \left\| \bm{y}_{i} -{\Phi \Psi \hat{\bm{s}}}_{i} \right\|_{l_{0}} \end{equation} $$ (33) ECO优化StOMP算法参数实现过程描述为:
从"线下阶段"实现规程可以看出, 算法复杂度为O$\left({KnMN\log \left({m+D} \right)} \right) $, 运算时间相对较长, 但是该阶段目的是寻求最佳StOMP算法参数配置, 因此对时间要求不高, 而且ECO算法的引入提高了求解精度, 为下一步"线上阶段"提供了精确的参数配置.
线上阶段 "线上阶段"定义为稀疏信号实际处理阶段, 因此对实时性要求较高, 为此引入拟牛顿梯度追踪策略以提高贪婪重构算法运算效率, 另外引入重构有效性指数, 以实现针对稀疏度$ K $未知信号的重构.
拟牛顿梯度追踪策略 拟牛顿梯度追踪[19]策略实质为利用梯度追踪思想替代贪婪重构算法中的正交投影计算, 以加快搜索速度, 即:
$$ \begin{equation} \label{eq34} \begin{cases} {\hat{\bm{s}}}_{t} ={\hat{\bm{s}}}_{t-1} +a_{t} d_{t} \\ r_{t} =r_{t-1} -a_{t} \Phi_{t} d_{t} \\ \end{cases} \end{equation} $$ (34) 其中, $ d_{t} $代表了梯度进化方向, $ d_{t} $、$ a_{t} $计算公式为:
$$ \begin{equation} \label{eq35} B_{t}^{t} d_{t} =\left\langle {r_{t-1}, A_{M\times N} } \right\rangle, a_{t} =\frac{\left\langle {r_{t-1}, \Phi_{t} d_{t} } \right\rangle }{\left\| {\Phi_{t} d_{t} } \right\|^{2}} \end{equation} $$ (35) 其中, $ B_{t} $替代了牛顿迭代[17]中的Hessian矩阵, 其具体计算公式为:
$$ \begin{align} \label{eq36}\nonumber B_{t} &={B}'_{t-1} -\frac{{B}'_{t-1} \left( {a_{t} d_{t} } \right)\left( {a_{t} d_{t} } \right)^{\rm T}B_{t-1} }{\left( {a_{t} d_{t} } \right)^{\rm T}B_{t-1} \left( {a_{t} d_{t} } \right)}+\\ &\quad \frac{\left( {\left( {\Phi _{t} } \right)^{\rm T}\Phi_{t} \left( {a_{t} d_{t} } \right)} \right)\left( {\left( {\Phi_{t} } \right)^{\rm T}\Phi_{t} \left( {a_{t} d_{t} } \right)} \right)^{\rm T}}{\left( {\left( {\Phi_{t} } \right)^{\rm T}\Phi_{t} \left( {a_{t} d_{t} } \right)} \right)^{\rm T}\left( {a_{t} d_{t} } \right)} \\ \nonumber &\!\!\!\!\!{B}'_{t-1} =\left[ {{\begin{matrix} {B_{t-1} } & 0 \\ 0 & 1 \\ \end{matrix} }} \right] \end{align} $$ (36) 其中, $ {B}'_{t-1} $表示对$ B_{t-1} $的扩展.可以证明采用式(33)进行迭代能够收敛于稳定值.
定义7(重构有效性指数). 对于稀疏信号重构算法, 定义重构有效性指数$ V_{N} $:
$$ \begin{align} \label{eq37}\nonumber V_{N} &=\frac{1}{N}\sum\limits_{i=1}^N {\left( {s_{i} -\hat{{s}}_{i} } \right)^{2}} +\max \limits_{1\leq i\leq N} \left( {s_{i} -\hat{{s}}_{i} } \right)^{2}+\\ &\quad \min \limits_{1\leq i\leq N} \left( {s_{i} -\hat{{s}}_{i} } \right)^{2} \end{align} $$ (37) 其中, 为真实信号, $ {\hat{\bm{s}}}_{N\times 1} =\left({\hat{{s}}_{1}, \cdots, \hat{{s}}_{N} } \right) $为重构信号.从定义7可以看出, 反映了$ \bm{s}_{N\times 1} $与$ {\hat{\bm{s}}}_{N\times 1} $拟合度, $ V_{N} $取值越小, $ {\hat{\bm{s}}}_{N\times 1} $更接近于$ \bm{s}_{N\times 1} $.
基于拟牛顿梯度追踪策略的改进StOMP (Improved StOPM, IStOMP)重构算法实现过程可以描述为:
算法3. IStOMP法
输入. 矩阵$ \bm{A}_{M\times N} $、测量量、利用ECO得到的$ \left({\tau, t_{s} } \right) $
1. For $ k=1: {K}' $ // $ {K}' $为未知稀疏度$ K $上限
2. For
3. IStOMP算法初始化: $ t=1 $、、支撑集$ \bm{I}=\bm{\phi } $ 、$ B_{0} =0 $;
4.根据计算公式, 找出$ \bm{A}_{M\times N} =({\bm{\phi }_{1}, \bm{\phi }_{2}, \cdots, \bm{\phi }_{N} }) $中与匹配的索引;
5.更新$ \bm{I}=\bm{I}\cup \bm{J} $, 根据式(33) (35)计算$ {\hat{\bm{s}}}_{t} $、$ r_{t} $;
6. End for
7.根据式(36)计算$ V^{k}_{N} $;
8. End for
9. $ \max \nolimits_{1\leq k\leq {K}'} V^{k}_{N} $对应的$ K $即为稀疏度; 对应的即为稀疏信号重构结果.
从IStOMP重构算法实现过程可以看出, 算法复杂度为O, 运算量明显降低, 这样保证了算法能够高效地处理大规模数据.
3.3 IStOMP}在WSNs中的应用
以无线传感器网络(Wireless sensor networks, WSNs)稀疏事件检测为对象进行研究:在WSNs监测范围内放置$ Q $个传感器节点用于监控$ N $个事件源, 某时刻$ N $个事件源随机发生$ K $个网络事件, 用向量表示所有事件能量信号$ (s_{i} =0 $表示该事件源无事件发生), 显然当$ K\ll N $时, $ \bm{s}_{N\times 1} $为$ K $度稀疏信号.假设$ Q=N $, 则$ N $个节点测量信号为:
$$ \begin{align} & \left[ \begin{matrix} {{x}_{1}} \\ {{x}_{2}} \\ \vdots \\ {{x}_{N}} \\ \end{matrix} \right]= \\ & \left[ \begin{matrix} \left| {{h}_{1,1}} \right|{{\left( {{d}_{1,1}} \right)}^{-\alpha }} & \left| {{h}_{1,2}} \right|{{\left( {{d}_{1,2}} \right)}^{-\alpha }} & \cdots & \left| {{h}_{1,N}} \right|{{\left( {{d}_{1,N}} \right)}^{-\alpha }} \\ \left| {{h}_{2,1}} \right|{{\left( {{d}_{2,1}} \right)}^{-\alpha }} & \left| {{h}_{2,2}} \right|{{\left( {{d}_{2,2}} \right)}^{-\alpha }} & \cdots & \left| {{h}_{2,N}} \right|{{\left( {{d}_{2,N}} \right)}^{-\alpha }} \\ \vdots & \vdots & \ddots & \vdots \\ {{h}_{N,1}}\left| {{\left( {{d}_{M,1}} \right)}^{-\alpha }} \right|{{h}_{N,2}}| & {{\left( {{d}_{M,2}} \right)}^{-\alpha }} & \cdots & \left| {{h}_{N,N}} \right|{{\left( {{d}_{M,N}} \right)}^{-\alpha }} \\ \end{matrix} \right]\times \\ & \left[ \begin{matrix} {{s}_{1}} \\ {{s}_{2}} \\ \vdots \\ {{s}_{N}} \\ \end{matrix} \right]={{\Psi }_{N\times N}}s \\ \end{align} $$ (38) 其中, $ d_{i, j} $为信号传播距离, $ h_{i, j} $为能量衰减模型.根据CS理论, 只需要$ M $个工作节点测量值即可实现稀疏事件检测:
$$ \begin{align}\nonumber \label{eq39} \bm{y}_{M\times 1} &=\left[ {{\begin{matrix} {y_{1} } \\ {y_{2} } \\ \vdots \\ {y_{M} } \\ \end{matrix} }} \right]=\left[ {{\begin{matrix} 1 & 0 & \cdots & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & 0 & 0 \\ \end{matrix} }} \right]\left[ {{\begin{matrix} {x_{1} } \\ {x_{2} } \\ \vdots \\ {x_{N} } \\ \end{matrix} }} \right]=\\ &{\bf{\Phi }}_{M\times N} \bm{x}_{N\times 1} \end{align} $$ (39) 联立式(37)和式(38)有$ \bm{y}_{M\times 1} ={\bf{\Phi }}_{M\times N} \bm{x}_{N\times 1} ={\bf{\Phi }}_{M\times N} {\bf{\Psi }}_{N\times N} \bm{s}_{N\times 1} \bm{=A}_{M\times N} \bm{s}_{N\times 1} $, 可以证明当$ M\geq {\rm O}\left({c\left({K+1} \right)\ln \left({N/K} \right)} \right) $时, $ \bm{A} $可以较好地符合RIP条件, 但是IStOMP重构算法需要精确测量矩阵保证[16], 因此对进行矩阵变换处理, 即:
$$ \begin{equation} \label{eq40} \bm{A}=\bm{U\Sigma V}^{\rm T} \end{equation} $$ (40) 其中, $ \bm{\Sigma }_{M\times N} $为半正定对角矩阵, $ \bm{U} $、为正交矩阵, 因此式(38)可以转换为:
$$ \begin{align} \label{eq41}\nonumber \bm{y}=&{\bf{\Phi }}_{M\times N} \bm{x}_{N\times 1} =\bm{{A}s}=\bm{U\Sigma V}^{\rm T}\bm{s}=\\ &\bm{U}\left[ {{\begin{matrix} {\overbrace {{\begin{matrix} {\sigma_{1} } & 0 & \cdots & 0 \\ 0 & {\sigma_{2} } & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & {\sigma_{M} } \\ \end{matrix} }}^{M\times M}} & {\overbrace {{\begin{matrix} 0 & \cdots & 0 \\ 0 & \cdots & 0 \\ \vdots & & 0 \\ 0 & \cdots & 0 \\ \end{matrix} }}^{\left( {N-M} \right)\times M}} \\ \end{matrix} }} \right]\bm{V}^{\rm T}\bm{s} \end{align} $$ (41) 对式(40)进一步处理有:
$$ \begin{align} \label{eq42}\nonumber &\bm{\Sigma }_{1}^{-1} \bm{U}^{\rm T}\bm{y} =\bm{\Sigma }_{1}^{-1} \bm{U}^{\rm T}\bm{U}\\\nonumber &\left[ {{\begin{matrix} {\overbrace {\bm{\Sigma }_{1} }^{M\times M}} & {\overbrace 0^{\left( {N-M} \right)\times M}} \\\nonumber \end{matrix} }} \right]\left[ {{\begin{matrix} {\overbrace {\bm{V}_{1} }^{M\times M}} & {\overbrace {\bm{V}_{2} }^{\left( {N-M} \right)\times M}} \\\nonumber \end{matrix} }} \right]\bm{s}=\\\nonumber &\bm{V}_{1}^{\rm T}\bm{s} \Rightarrow \bm{{y}'}=\bm{\Sigma }_{1}^{-1} \bm{U}^{\rm T}\bm{y}=\bm{V}_{1}^{\rm T}\bm{s} \end{align} $$ 对于式(41)代表的新测量系统, 根据推导过程可以看出测量矩阵为行正交矩阵, 因此满足RIP条件.
此时, WSNs稀疏事件检测转换为利用$ M $个工作节点实现对$ K $个事件源检测的问题, 具体实现过程为:在WSNs部署测试阶段利用实验样本数据进行参数训练以得到最佳参数配置组合; 在实际检测阶段利用IStOMP重构算法对测量信号处理以得到稀疏信号向量$ \bm{s}_{N\times 1} $, 从而完成对稀疏事件的实时有效监控.
4. 实验仿真
4.1 ECO性能试验测试
为了验证ECO算法优化性能, 采用系列基准测试函数进行实验仿真, 表 1给出了6个典型基准测试函数.
表 1 基准测试函数Table 1 Benchmark functions函数名称 目标函数 维数 取值范围 Scaffer 2 [0, 1] Sphere $ f_{2} \left(x \right)=\sum\limits_{i=1}^n {x_{i}^{2} } $ 5 $ (-30, 30) $ Griewank 20 $ (-30, 30) $ Scaffer7 30 $ (-100, 100) $ Rastrigin $ n $ $ (-5.12, 5.12) $ Rosenrrock $ n $ $ (-30, 30) $ 4.1.1 ECO参数设置实验
群体规模$ n $、更新控制系数$ \varepsilon $、碰撞自适应学习因子和控制系数$ \beta $是ECO算法涉及的主要参数, 目前关于智能算法参数设置问题普遍采用实验法进行确定, 因此设置$ n $、$ \varepsilon $、$ \xi $、$ \beta $不同取值对$ f_{3} $函数进行测试, 每次运行10次, 取算法最优解均值和平均运行时间进行分析, 图 3~6给出了不同$ n $、$ \varepsilon $、$ \xi $、$ \beta $下最优解均值和平均运行时间变化曲线.
图 3 不同$ n $下最优解均值和平均运行时间变化曲线Fig. 3 Mean value and average run time curve of optimal solution under different $ n $
图 4 不同$ \varepsilon $下最优解均值和平均运行时间变化曲线Fig. 4 The mean value and average run time curve of optimal solution under different $ \varepsilon $
图 5 不同$ \xi $下最优解均值和平均运行时间变化曲线Fig. 5 The mean value and average run time curve of optimal solution under different $ \xi $
图 6 不同$ \xi $下最优解均值和平均运行时间变化曲线Fig. 6 The mean value and average run time curve of optimal solution under different $ \beta $从图 3可以看出, 随着群体规模不断扩大, 算法最优解逐渐降低, 并逐渐收敛于全局最优解, 但是当$ n\geq 200 $时, 随着$ n $增大算法最优解无明显变化, 而运算时间成倍增加, 因此在满足收敛精度的前提下, 应降低群体规模以减少运算时间.从图 4可以看出, 当$ \varepsilon \leq 0.6 $时, 算法收敛情况变化不大并且收敛于全局最优解, 但是算法运算时间随着变大逐渐降低, 当$ \varepsilon >0.6 $时, 随着变大, 算法收敛效果明显降低, 这是因为$ \varepsilon $取值越大, 粒子更新的概率越低, 导致算法无法找到最优解.同理, $ \xi $、$ \beta $取值影响了群体样本多样性, 当$ \xi \geq 0.3 $、$ \beta \geq 0.8 $时, $ \xi $与$ \beta $取值越大, 粒子更新机制趋于2种方式, 导致算法深度搜索能力降低, 算法收敛效果不理想.综上所述ECO参数设置为: $ n=200 $、$ \varepsilon =0.6 $、$ \xi =0.3 $、$ \beta =0.6 $.
4.1.2 不同优化算法对比实验
为了进一步分析ECO算法收敛性能, 选取经典PSO算法和最近才提出的海豚群算法(Dolphin swarm algorithm, DSA)[20]、狼群智能算法(Smart wolf pack algorithm, SWPA)[21]进行对比实验, 对比分析不同改进策略对优化算法寻优性能影响, 以及ECO收敛效率(PSO、DSA和SWPA参数设置参考相关文献).每种算法独立运行100次, 选取成功率$ Su $ (算法最优解与理论最优解小于阈值$ \delta $次数占实验次数的比值)、最大值$ Max $、最小值$ Min $、均值和运算时间$ T $为算法收敛性能对比指标. 图 7给出了4种优化算法函数收敛曲线, 表 2给出了不同函数收敛性能指标对比结果.
图 7 4种不同优化算法函数收敛曲线Fig. 7 Function convergence curves of four different optimization algorithms表 2 不同函数收敛性能指标对比结果Table 2 Comparison results of convergence performance indexes of different functions$ f $ 算法 $ Su $ (%) $ Max $ $ Min $ $ \overline {Ave} $ $ T$ (s) $ f_{1} $ ECO 100 -0.997 -1 -0.999 6.79 PSO 12 -0.23 -0.95 -0.68 11.37 DSA 100 -0.96 -1 -0.98 6.13 SWPA 100 -0.93 -1 -0.97 7.74 $ f_{2} $ ECO 100 1.78E-6 0 6.37E-10 6.37 PSO 100 5.27E-4 5.77E-6 1.19E-4 12.76 DSA 100 6.27E-3 3.09E-4 1.62E-3 8.36 SWPA 100 1.04E-4 3.33E-5 6.24E-5 14.55 $ f_{3} $ ECO 100 7.24E-4 0 1.29E-3 10.88 PSO 0 1.51 0.012 0.84 15.27 DSA 98 3.28E-3 1.93E-3 2.74E-3 12.70 SWPA 100 6.53E-3 2.85E-3 3.48E-3 11.09 $ f_{4} $ ECO 100 2.81E-5 6.34E-8 7.11E-7 22.16 PSO 0 17.11 6.25 10.78 27.94 DSA 79 0.07 1.83E-2 0.04 11.22 SWPA 80 0.18 3.64E-72 0.01 14.55 $ f_{5} $ ECO 100 1.11E-6 0 4.89E-9 7.41 PSO 0 20.47 11.25 19.86 10.28 DSA 65 0.063 3.21E-2 0.017 6.89 SWPA 86 0.025 4.44E-3 0.008 8.77 $ f_{6} $ ECO 17 0.467 0.013 0.227 15.23 PSO 0 88.171 21.073 44.110 20.79 DSA 0 22.145 6.667 8.936 18.81 SWPA 11 6.652 2.147 3.667 12.56 从图 7及表 2可以看出, 对于单峰函数$ f_{2} $ (理论全局最优解为0, 设置$ \delta =10^{-3} $, ), 4种优化算法都能够收敛于全局最优解0, 并且成功率都为100 %; 对于多峰多极值函数$ f_{1} $、$ f_{3} $、$ f_{4} $和$ f_{5} \, (f_{1} $、$ f_{3} $的$ \delta =10^{-2} $, 其余函数$ \delta =10^{-1}) $, 由于这些函数存在大量局部极值, 导致基本PSO除函数$ f_{1} $成功率为12 %外, 其他函数成功率都为0, 而DSA和SWPA算法只在$ f_{1} $、$ f_{3} $两个函数求解过程中具有较高成功率, 对于$ f_{4} $和$ f_{5} $函数, DSA和SWPA算法的成功率和收敛精度都要远远小于ECO算法; 对于病态高维函数$ f_{6} $ (理论全局最优解为0), 在收敛精度设置为$ \delta =10^{-1} $的情况下, 4种算法成功率最高的ECO算法也只有17 %, 并且找到的最优解最小值也只有0.013, 几乎无法发现全局最优解, 综合分析上述对比结果可知:
1) 利用特定策略或者特定模型对算法改进能够很大程度改善算法全局收敛性能, 特别是对于多局部极值复杂函数优化问题, 改进策略增加了样本多样性和局部深度探索能力, 从而使得算法能够增大跳出局部极值概率.
2) ECO算法收敛成功率以及收敛精度要好于其他三种算法, 这是因为ECO更新策略实质为3种碰撞方式, 改善了样本多样性, 而且高斯分布的引入使得算法在运算后期还具有较强的深度搜索能力, 进而表现出突出的全局寻优能力, 对于算法运算时间, ECO算法运算时间与DSA和SWPA算法接近, 并且有时候要大于这两种算法, 这也符合"收敛精度和收敛速度不可兼得"的定律.
3) 对于高维病态函数, 4种算法都还要进一步改进, 这是因为函数欺骗性较强, 使得算法很难找到全局最优解, 这也表明, 算法改进策略不是万能的, 往往只针对某一类优化问题具有突出性能, 因此需要结合具体实际优化问题对算法进行改进.
4.2 WSNs稀疏事件检测实验
将具有$ Q=500 $个传感器节点的WSNs部署在$ N=120 $个需要实时监控温度信息的场所, 传感器节点位置信息和性能指标参数已知, 事件源序列与事件源能量信号对应.选取均方误差MSE、重构成功率DSR和重构信噪比SNR对稀疏信号重构结果进行分析.
$$ \begin{align} & \text{MSE}=\frac{1}{Z}\left( \sum\limits_{i}^{Z}{\left\| s-{{{\hat{s}}}_{i}} \right\|} \right) \\ & \text{SNR}=\frac{1}{Z}\left( \sum\limits_{i}^{Z}{1}0\lg \left( \|s{{\|}^{2}}/{{\left\| s-{{{\hat{s}}}_{i}} \right\|}^{2}} \right) \right) \\ \end{align} $$ (42) $$ \begin{equation} \label{eq44} {\rm DSR}=\frac{\left( {\sum\limits_i^Z {z_{i} } } \right)}{Z}, \begin{cases} z_{i} =1, \frac{\left[ {\sum\limits_{j=1}^N {\left( {s_{j} - \widehat{s}_{j} } \right)} } \right]}{N}\leq \lambda_{\min } \\ z_{i} =0, \frac{\left[ {\sum\limits_{j=1}^N {\left( {s_{j} - \widehat{s}_{j} } \right)} } \right]}{N}>\lambda_{\min } \\ \end{cases} \end{equation} $$ (43) 其中, $ Z $为实验次数, $ \widehat{s}_{j} $为第$ j $次重构结果, $ \lambda_{\min } $为重构成功率控制阀值.
4.2.1 稀疏度$\pmb K $与$\bf \left(\pmb \tau, t_{s} \right) $和$\pmb t_{s} $的关系
在ECO优化StOMP算法参数阶段, 在假定稀疏度$ K $已知的前提下得到最佳$ \left({\tau, t_{s} } \right) $组合, 然而在实际监测阶段, 信号稀疏度未知且不一定等于"线下阶段"设定的稀疏度, 因此需要分析ECO优化StOMP算法参数阶段不同稀疏度$ K $对$ \left({\tau, t_{s} } \right) $的影响, 为止设置不同$ K $取值以观察$ \left({\tau, t_{s} } \right) $变化, 图 8给出了对比结果.
图 8 不同$ K $取值下$ \left({\tau, t_{s} } \right) $变化情况Fig. 8 Changes in different $ K $ values $ \left({\tau, t_{s} } \right) $从图 8可以看出, 不同$ K $取值下, 取值变化不大, 并且MSE相对较小.因此也证明了利用线下阶段优化$ \left({\tau, t_{s} } \right) $的可行性.后续实验中设置IStOMP参数为$ \left({2.32, 10} \right) $.
4.2.2 稀疏信号重构对比实验
为了进一步分析IStOMP重构算法性能, 在WSNs部署区域人为设定$ K=15 $个事件源发生事件, 并测量这些事件的温度值作为原始信号.选取StOMP重构算法[22]、SP重构算法[23]和BSMP重构算法[24]进行对比实验, 实验过程中这些重构算法不知道信号稀疏度$ K $的大小, 每种算法独立重复试验100次.为了降低$ M $取值对重构结果的影响, 根据, 令$ M=100 $即网络中有100个节点处于工作状态. 图 9给出了4种重构算法稀疏信号重构对比结果, 表 3给出了重构评价指标对比结果.
图 9 4种重构算法稀疏信号重构结果对比Fig. 9 Comparison of four reconstruction algorithms for sparse signal reconstruction results表 3 不同重构评价指标对比Table 3 Comparison of evaluation indexes of different reconfiguration重构算法稀疏度 $ K=15 $ MSE DSR (%) $ \overline {T_{l} } $ (s) SNR IStOMP 1.23 100 14.881 39.114 StOMP 91.27 7 9.524 27.047 SP 12.54 89 6.227 36.541 BSMP 16.76 99 8.123 35.046 从图 9及表 3可以看出, IStOMP算法、BSMP算法和SP算法能够实现稀疏信号的精确重构, 并且IStOMP算法重构误差只有1.23, 要好于BSMP算法和SP算法, 然而StOMP算法无法实现稀疏度未知信号的重构, 重构结果与原始信号差距很大, 几乎每个事件源都发生了错误判断.在算法运算时间上, IStOMP算法要大于其他三种算法, 这是因为算法要循环判定最佳稀疏度, 导致运算时间增加, 但是针对$ K=15 $时, 运算时间也只有14.881 s, 因此在可以接受的运算时间范围内, IStOMP重构算法更具有实际应用意义.
4.2.3 参数设置对重构性能影响实验
为了分析稀疏度$ K $对重构结果的影响, 设置$ K $从10到100以步长10进行变化$ (M=100 $、$ N=120) $, 采用4种算法独立重复实验100次. 图 10给出了不同稀疏度下4种算法$ MSE $和DSR对比结果.为了分析测量数目$ M $对重构结果的影响, 设置$ M $从40到110以步长5进行变化$ (K=40 $、$ N=120) $, 同样采用4种算法独立重复实验100次. 图 11给出了不同测量数目下4种算法MSE和DSR对比结果.
图 10 稀疏度$ K $对重构结果影响Fig. 10 The influence of the sparsity $K$ on the reconstruction results
图 11 测量数目$ M $对重构结果影响Fig. 11 The influence of the number of measurements $M$ on the reconfiguration results从图 10和图 11可以看出, 无论是重构成功率还是重构误差, IStOMP都要好于StOMP、SP法和BSMP算法, 并且StOMP表现最差.对于不同稀疏度$ K $, 当$ K $达到70时, IStOMP重构成功率仍在90 %以上, 重构误差也只有1.33, 而此时表现较好的BSMP的成功率只有13 %, 而重构误差达到了3.95.同样对于测量数目, IStOMP只需要较小的测量数目即可以实现稀疏信号的精确重构, 而StOMP至少需要80个节点才能达到90 %以上的成功率, 然而工作节点越多, 网络能耗也就越大, 从而不利于延长WSNs网络生存时间.
为了进一步分析4种算法抗噪声干扰能力和鲁棒性, 设置输入信噪比从20 db到45 db以步长1 db变化$ (K=30 $、$ M=100 $、$ N=120) $, 图 12给出了4种算法在不同噪声影响下的抗噪声能力.
图 12 不同算法抗噪声能力干扰对比Fig. 12 Interference contrast of anti noise ability of different algorithms从图 12可以看出, 当信噪比在35 db以下是, 4种算法重构成功率都达到90以上, 并且IStOMP要好于其他三种算法, 这也表明IStOMP算法能够提高系统重构鲁棒性.
5. 结果分析
从稀疏信号重构对比和参数设置对重构性能影响实验可以看出, IStOMP重构性能更加突出:
1) IStOMP能够实现稀疏度未知信号的精确重构.这是因为针对$ K $未知情况, IStOMP算法采用循环探索方式, 以确保得到最匹配稀疏度, 当然这一定程度牺牲了时间代价, 而IStOMP也采用了拟牛顿迭代方式以提高算法运行速度.因此在实际应用领域, 在可以接受的运算时间范围内, IStOMP重构算法对重构稀疏度未知信号更具有实际应用意义.
2) IStOMP具有更高的重构精度和重构成功率. "线下"和"线上"阶段划分、ECO算法优化参数配置以及测量矩阵变换处理从不同角度提高了IStOMP重构精度, 仿真实验也验证了这些策略的有效性.
6. 结束语
对一种全新智能优化算法及其在WSNs稀疏事件检测中的应用进行了研究, 从理论角度对碰撞优化算法收敛性和样本多样性进行了分析, 这对研究智能优化算法具有一定借鉴意义; 从WSNs稀疏事件检测应用研究入手, 针对稀疏度未知、重构精度要求高、传统贪婪算法固有缺陷, 将ECO与压缩感知相结合, 引入了分阶段检测框架和IStOMP重构算法, 最后仿真实验也验证了ECO算法和IStOMP重构算法的有效性.下一步将针对高维病态函数优化和提高重构算法普适性上做进一步研究.
-
图 2 改进StOMP贪婪重构算法实现
Fig. 2 Improved StOMP greedy reconstruction algorithm implementation
图 3 不同$ n $下最优解均值和平均运行时间变化曲线
Fig. 3 Mean value and average run time curve of optimal solution under different $ n $
图 4 不同$ \varepsilon $下最优解均值和平均运行时间变化曲线
Fig. 4 The mean value and average run time curve of optimal solution under different $ \varepsilon $
图 5 不同$ \xi $下最优解均值和平均运行时间变化曲线
Fig. 5 The mean value and average run time curve of optimal solution under different $ \xi $
图 6 不同$ \xi $下最优解均值和平均运行时间变化曲线
Fig. 6 The mean value and average run time curve of optimal solution under different $ \beta $
图 7 4种不同优化算法函数收敛曲线
Fig. 7 Function convergence curves of four different optimization algorithms
图 8 不同$ K $取值下$ \left({\tau, t_{s} } \right) $变化情况
Fig. 8 Changes in different $ K $ values $ \left({\tau, t_{s} } \right) $
图 9 4种重构算法稀疏信号重构结果对比
Fig. 9 Comparison of four reconstruction algorithms for sparse signal reconstruction results
图 10 稀疏度$ K $对重构结果影响
Fig. 10 The influence of the sparsity $K$ on the reconstruction results
图 11 测量数目$ M $对重构结果影响
Fig. 11 The influence of the number of measurements $M$ on the reconfiguration results
图 12 不同算法抗噪声能力干扰对比
Fig. 12 Interference contrast of anti noise ability of different algorithms
表 1 基准测试函数
Table 1 Benchmark functions
函数名称 目标函数 维数 取值范围 Scaffer $ \begin{aligned} f_{1} \left(x \right)= 0.5-\frac{[{\sin^{2}\left({x_{1}^{2} +x_{2}^{2} } \right)^{0.5}}]}{[{1+0.001\left({x_{1}^{2} +x_{2}^{2} } \right)^{2}}]} \end{aligned} $ 2 [0, 1] Sphere $ f_{2} \left(x \right)=\sum\limits_{i=1}^n {x_{i}^{2} } $ 5 $ (-30, 30) $ Griewank $ \begin{aligned} f_{3} \left(x \right)=\frac{1}{4000}\sum\limits_{i=1}^n {x_{i}^{2} } - \prod\limits_{i=1}^n {\cos \left({\frac{x_{i} }{\sqrt{i}}} \right)} +1 \end{aligned} $ 20 $ (-30, 30) $ Scaffer7 $ \begin{aligned} f_{4} \left(x \right)=\sum\limits_{i=1}^{n-1} {\left({x_{i}^{2} +x_{i+1}^{2} } \right)^{0.25}} \times [{\sin^{2}({50\left({x_{i}^{2} +x_{i+1}^{2} } \right)^{0.1}})+2}] \end{aligned} $ 30 $ (-100, 100) $ Rastrigin $ \begin{aligned} f_{5} \left(x \right)= \sum\limits_{i=1}^n {({x_{i}^{2} -10\cos 2\pi x_{i} +10})} \end{aligned} $ $ n $ $ (-5.12, 5.12) $ Rosenrrock $ \begin{aligned} f_{6} \left(x \right)= \sum\limits_{i=1}^n {[{100\left({x_{i+1} -x_{i}^{2} } \right)^{2}+x_{i}^{2} }]} \end{aligned} $ $ n $ $ (-30, 30) $ 
下载: 导出CSV
表 2 不同函数收敛性能指标对比结果
Table 2 Comparison results of convergence performance indexes of different functions
$ f $ 算法 $ Su $ (%) $ Max $ $ Min $ $ \overline {Ave} $ $ T$ (s) $ f_{1} $ ECO 100 -0.997 -1 -0.999 6.79 PSO 12 -0.23 -0.95 -0.68 11.37 DSA 100 -0.96 -1 -0.98 6.13 SWPA 100 -0.93 -1 -0.97 7.74 $ f_{2} $ ECO 100 1.78E-6 0 6.37E-10 6.37 PSO 100 5.27E-4 5.77E-6 1.19E-4 12.76 DSA 100 6.27E-3 3.09E-4 1.62E-3 8.36 SWPA 100 1.04E-4 3.33E-5 6.24E-5 14.55 $ f_{3} $ ECO 100 7.24E-4 0 1.29E-3 10.88 PSO 0 1.51 0.012 0.84 15.27 DSA 98 3.28E-3 1.93E-3 2.74E-3 12.70 SWPA 100 6.53E-3 2.85E-3 3.48E-3 11.09 $ f_{4} $ ECO 100 2.81E-5 6.34E-8 7.11E-7 22.16 PSO 0 17.11 6.25 10.78 27.94 DSA 79 0.07 1.83E-2 0.04 11.22 SWPA 80 0.18 3.64E-72 0.01 14.55 $ f_{5} $ ECO 100 1.11E-6 0 4.89E-9 7.41 PSO 0 20.47 11.25 19.86 10.28 DSA 65 0.063 3.21E-2 0.017 6.89 SWPA 86 0.025 4.44E-3 0.008 8.77 $ f_{6} $ ECO 17 0.467 0.013 0.227 15.23 PSO 0 88.171 21.073 44.110 20.79 DSA 0 22.145 6.667 8.936 18.81 SWPA 11 6.652 2.147 3.667 12.56
下载: 导出CSV
表 3 不同重构评价指标对比
Table 3 Comparison of evaluation indexes of different reconfiguration
重构算法稀疏度 $ K=15 $ MSE DSR (%) $ \overline {T_{l} } $ (s) SNR IStOMP 1.23 100 14.881 39.114 StOMP 91.27 7 9.524 27.047 SP 12.54 89 6.227 36.541 BSMP 16.76 99 8.123 35.046
下载: 导出CSV
-
[1] Luo C, Wu F, Sun J, Chen C W. Efficient measurement generation and pervasive sparsity for compressive data gathering. IEEE Transactions on Wireless Communications, 2010, 9(12): 3728-3738 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=c2a1c12bd89e33b724c1e1e60d41dd00 [2] Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of the 1995 IEEE International Conference on Neural Networks. Perth, Australia: IEEE, 1995. 1942-1948 [3] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. In: Proceedings of the First European Conference on Artificial Life. Paris, France: Elsevier Publishing, 1991. 134-142 [4] Eusuff M M, Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm. Journal of Water Resources Planning and Management, 2003, 129(3): 210-225 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=0e23c56470bc29ab284b932833c2fe22 [5] Tan Y, Zhu Y C. Fireworks algorithm for optimization. In: Proceedings of the First International Conference on Advances in Swarm Intelligence. Beijing, China: Springer-Verlag, 2010. 355-364 [6] 莫修文, 张强, 陆敬安.模拟退火法建立数字岩心的一种补充优化方案.地球物理学报, 2016, 59(5): 1831-1838 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dqwlxb201605026Mo Xiu-Wen, Zhang Qiang, Lu Jing-An. A complement optimization scheme to establish the digital core model based on the simulated annealing method. Chinese Journal of Geophysics, 2016, 59(5): 1831-1838 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dqwlxb201605026 [7] 李宝磊, 施心陵, 苟常兴, 吕丹桔, 安镇宙, 张榆锋.多元优化算法及其收敛性分析.自动化学报, 2015, 41(5): 949-959 doi: 10.16383/j.aas.2015.c140585Li Bao-Lei, Shi Xin-Ling, Gou Chang-Xing, Lv Dan-Ju, An Zhen-Zhou, Zhang Yu-Feng. Multivariant optimization algorithm and its convergence analysis. Acta Automatica Sinica, 2015, 41(5): 949-959 doi: 10.16383/j.aas.2015.c140585 [8] Ebrahimi D, Assi C. Network coding-aware compressive data gathering for energy-efficient wireless sensor networks. ACM Transactions on Sensor Networks, 2015, 11(4): Article No. 61 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=8f2aa328e1976324b2567f8fb8839203 [9] Liang J J, Qin A K, Suganthan P N, Baskar S. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295 http://cn.bing.com/academic/profile?id=cf4e7f5803244a494e7503db7e0301fc&encoded=0&v=paper_preview&mkt=zh-cn [10] 马卫, 孙正兴.采用搜索趋化策略的布谷鸟全局优化算法.电子学报, 2015, 43(12): 2429-2439 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dianzixb201512013Ma Wei, Sun Zheng-Xing. A global cuckoo optimization algorithm using coarse-to-fine search. Acta Electronica Sinica, 2015, 43(12): 2429-2439 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dianzixb201512013 [11] 田瑾.高维多峰函数的量子行为粒子群优化算法改进研究.控制与决策, 2016, 31(11): 1967-1972 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201611006Tian Jin. Improvement of quantum-behaved particle swarm optimization algorithm for high-dimensional and multi-modal function. Control and Decision, 2016, 31(11): 1967-1972 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201611006 [12] Lee K S, Geem Z W. A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice. Computer Methods in Applied Mechanics and Engineering, 2005, 194(36-38): 3902-3933 http://cn.bing.com/academic/profile?id=cf8b4b943f7d683011d8b80fe90e576f&encoded=0&v=paper_preview&mkt=zh-cn [13] 崔晓晖, 印桂生, 董红斌.面向服务匹配问题的协同演化算法.软件学报, 2015, 26(7): 1601-1614 http://d.old.wanfangdata.com.cn/Periodical/rjxb201507004Cui Xiao-Hui, Yin Gui-Sheng, Dong Hong-Bin. Co-evolutionary algorithm for web service matching. Journal of Software, 2015, 26(7): 1601-1614 http://d.old.wanfangdata.com.cn/Periodical/rjxb201507004 [14] Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306 http://d.old.wanfangdata.com.cn/Periodical/hwyhmb200904014 [15] 王艳芬, 丛潇雨, 孙彦景.一种稀疏度自适应超宽带信道估计算法.电子科技大学学报, 2017, 46(3): 498-504 http://d.old.wanfangdata.com.cn/Periodical/dzkjdxxb201703004Wang Yan-Fen, Cong Xiao-Yu, Sun Yan-Jing. Sparsity adaptive algorithm for ultra-wideband channel estimation. Journal of University of Electronic Science and Technology of China, 2017, 46(3): 498-504 http://d.old.wanfangdata.com.cn/Periodical/dzkjdxxb201703004 [16] 杨成, 冯巍, 冯辉, 杨涛, 胡波.一种压缩采样中的稀疏度自适应子空间追踪算法.电子学报, 2010, 38(8): 1914-1917 http://d.old.wanfangdata.com.cn/Periodical/dianzixb201008032Yang Cheng, Feng Wei, Feng Hui, Yang Tao, Hu Bo. A sparsity adaptive subspace pursuit algorithm for compressive sampling. Acta Electronica Sinica, 2010, 38(8): 1914-1917 http://d.old.wanfangdata.com.cn/Periodical/dianzixb201008032 [17] Candés E J, Wakin M B. An introduction to compressive sampling. IEEE Signal Processing Magazine, 2008, 25(2): 21-30 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f038caf0ee508db10a5b5fd193679bc2 [18] 方红, 杨海蓉.贪婪算法与压缩感知理论.自动化学报, 2011, 37(12): 1413-1421 doi: 10.3724/SP.J.1004.2011.01413Fang Hong, Yang Hai-Rong. Greedy algorithms and compressed sensing. Acta Automatica Sinica, 2011, 37(12): 1413-1421 doi: 10.3724/SP.J.1004.2011.01413 [19] Jing M L, Zhou X Q, Qi C. Quasi-newton iterative projection algorithm for sparse recovery. Neurocomputing, 2014, 144: 169-173 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=931bdad879f0a11b0d9e3465eb736397 [20] Wu T Q, Yao M, Yang J H. Dolphin swarm algorithm. Frontiers of Information Technology & Electronic Engineering, 2016, 17(8): 717-729 http://d.old.wanfangdata.com.cn/Periodical/zjdxxbc-e201608001 [21] 薛俊杰, 王瑛, 李浩, 肖吉阳.一种狼群智能算法及收敛性分析.控制与决策, 2016, 31(12): 2131-2139 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201612003Xue Jun-Jie, Wang Ying, Li Hao, Xiao Ji-Yang. A smart wolf pack algorithm and its convergence analysis. Control and Decision, 2016, 31(12): 2131-2139 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201612003 [22] 刘盼盼, 李雷, 王浩宇.压缩感知中基于变尺度法的贪婪重构算法的研究.通信学报, 2014, 35(12): 98-105 http://d.old.wanfangdata.com.cn/Periodical/txxb201412012Liu Pan-Pan, Li Lei, Wang Hao-Yu. Research on greedy reconstruction algorithms of compressed sensing based on variable metric method. Journal on Communications, 2014, 35(12): 98-105 http://d.old.wanfangdata.com.cn/Periodical/txxb201412012 [23] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249 http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_0803.0811 [24] Sun B, Shan X, Wu K, Xiao Y. Anomaly detection based secure in-network aggregation for wireless sensor networks. IEEE Systems Journal, 2013, 7(1): 13-25 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=79912c1f6f0509917d4454d2752aa4a4 期刊类型引用(1)
1. 陈蕾，邵楷，林腾涛，陈兴国. 一种噪声容错弱监督矩阵补全的生存分析方法. 自动化学报. 2021(12): 2801-2814 . 
本站查看其他类型引用(3)
-
下载:
计量
- 文章访问数: 4396
- HTML全文浏览量: 534
- PDF下载量: 135
- 被引次数: 4
