2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

联合弹性碰撞与梯度追踪的WSNs压缩感知重构

刘洲洲 李士宁 王皓 张倩昀

刘洲洲, 李士宁, 王皓, 张倩昀. 联合弹性碰撞与梯度追踪的WSNs压缩感知重构. 自动化学报, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241
引用本文: 刘洲洲, 李士宁, 王皓, 张倩昀. 联合弹性碰撞与梯度追踪的WSNs压缩感知重构. 自动化学报, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241
LIU Zhou-Zhou, LI Shi-Ning, WANG Hao, ZHANG Qian-Yun. A Compressed Sensing Reconstruction Based on Elastic Collision and Gradient Pursuit Strategy for WSNs. ACTA AUTOMATICA SINICA, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241
Citation: LIU Zhou-Zhou, LI Shi-Ning, WANG Hao, ZHANG Qian-Yun. A Compressed Sensing Reconstruction Based on Elastic Collision and Gradient Pursuit Strategy for WSNs. ACTA AUTOMATICA SINICA, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241

联合弹性碰撞与梯度追踪的WSNs压缩感知重构


DOI: 10.16383/j.aas.c170241
详细信息
    作者简介:

    李士宁  西北工业大学教授.主要研究方法为无线网络通信与安全, 大数据分析, 物联网, 智能计算. E-mail: lishining@nwpu.edu.cn

    王皓  挪威科技大学奥勒松校区工程与科学学院副教授. 2006年获得华南理工大学博士学位.主要研究方向为大数据, 物联网, 软件工程. E-mail: hawa@ntnu.no

    张倩昀  西安航空学院讲师. 2007获得南京航空航天大学硕士学位, 主要研究方向为信号处理. E-mail: jinganqy1988@126.com

    通讯作者: 刘洲洲  西安航空学院教授. 2016年获得西北工业大学信息工程专业博士学位.主要研究方向为移动通信, 随机接入网络, 传感器器网络.本文通信作者. E-mail: nazi2005@126.com
  • 本文责任编委  杨健
  • 基金项目:

    国家自然科学基金 61871313

    中国博士后科学基金 2018M633573

    西安市科技计划项目 2017076CG/RC039 (XAHK001)

    校级科研基金 2017KY1112

A Compressed Sensing Reconstruction Based on Elastic Collision and Gradient Pursuit Strategy for WSNs

More Information
    Author Bio:

    LI Shi-Ning  Professor at Northwestern Polytechnical University, China. His research interest covers wireless communication and security, big data analytics, industrial internet of things, and intelligent computing

    WANG Hao  Associate professor at Natural Sciences in Norwegian University of Science & Technology, Norway. He received his Ph. D. degree from South China University of Technology, China in 2006. His research interest covers wireless communication and security, big data analytics, and industrial internet of things, high performance computing, and safety-critical systems

    ZHANG Qian-Yun  Lecturer at Xi'an Aeronautical University, China. She received her bachelor from Nanchang Hangkong University, China in 2007. Her main research interest is signal processing

    Corresponding author: LIU Zhou-Zhou  Professor at Xi'an Aeronautical University, China. He received his Ph. D. degree in information engineering from Northwestern Polytechnical University, China in 2016. His main research interest covers mobile communications, random access in mobile radio networks, sensor networks. Corresponding author of this paper
  • Recommended by Associate Editor YANG Jian
  • Fund Project:

    National Natural Science Foundation of China 61871313

    China Postdoctoral Science Foundation Funded Project 2018M633573

    Xi'an Science and Technology Project 2017076CG/RC039 (XAHK001)

    School Level Scientiflc Research Fund 2017KY1112

图(12) / 表(3)
计量
  • 文章访问数:  2648
  • HTML全文浏览量:  302
  • PDF下载量:  55
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-05-05
  • 录用日期:  2018-05-07
  • 刊出日期:  2020-01-20

联合弹性碰撞与梯度追踪的WSNs压缩感知重构

doi: 10.16383/j.aas.c170241
    基金项目:

    国家自然科学基金 61871313

    中国博士后科学基金 2018M633573

    西安市科技计划项目 2017076CG/RC039 (XAHK001)

    校级科研基金 2017KY1112

    作者简介:

    李士宁  西北工业大学教授.主要研究方法为无线网络通信与安全, 大数据分析, 物联网, 智能计算. E-mail: lishining@nwpu.edu.cn

    王皓  挪威科技大学奥勒松校区工程与科学学院副教授. 2006年获得华南理工大学博士学位.主要研究方向为大数据, 物联网, 软件工程. E-mail: hawa@ntnu.no

    张倩昀  西安航空学院讲师. 2007获得南京航空航天大学硕士学位, 主要研究方向为信号处理. E-mail: jinganqy1988@126.com

    通讯作者: 刘洲洲  西安航空学院教授. 2016年获得西北工业大学信息工程专业博士学位.主要研究方向为移动通信, 随机接入网络, 传感器器网络.本文通信作者. E-mail: nazi2005@126.com
  • 本文责任编委  杨健

摘要: 为提高压缩感知(Compressed sensing, CS)大规模稀疏信号重构精度, 提出了一种联合弹性碰撞优化与改进梯度追踪的WSNs (Wireless sensor networks)压缩感知重构算法.首先, 创新地提出一种全新的智能优化算法---弹性碰撞优化算法(Elastic collision optimization algorithm, ECO), ECO模拟物理碰撞信息交互过程, 利用自身历史最优解和种群最优解指导进化方向, 并且个体以N(0, 1)概率形式散落于种群最优解周围, 在有效提升收敛速度的同时扩展了个体搜索空间, 理论定性分析表明ECO依概率1收敛于全局最优解, 而种群多样性指标分析证明了算法全局寻优能力.其次, 针对贪婪重构算法高维稀疏信号重构效率低、稀疏度事先设定的缺陷, 在设计重构有效性指数的基础上将ECO应用于压缩感知重构算法中, 并引入拟牛顿梯度追踪策略, 从而实现对大规模稀疏度未知数据的准确重构.最后, 利用多维测试函数和WSNs数据采集环境进行仿真, 仿真结果表明, ECO在收敛精度和成功率上具有一定优势, 而且相比于其他重构算法, 高维稀疏信号重构结果明显改善.

本文责任编委  杨健

English Abstract

刘洲洲, 李士宁, 王皓, 张倩昀. 联合弹性碰撞与梯度追踪的WSNs压缩感知重构. 自动化学报, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241
引用本文: 刘洲洲, 李士宁, 王皓, 张倩昀. 联合弹性碰撞与梯度追踪的WSNs压缩感知重构. 自动化学报, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241
LIU Zhou-Zhou, LI Shi-Ning, WANG Hao, ZHANG Qian-Yun. A Compressed Sensing Reconstruction Based on Elastic Collision and Gradient Pursuit Strategy for WSNs. ACTA AUTOMATICA SINICA, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241
Citation: LIU Zhou-Zhou, LI Shi-Ning, WANG Hao, ZHANG Qian-Yun. A Compressed Sensing Reconstruction Based on Elastic Collision and Gradient Pursuit Strategy for WSNs. ACTA AUTOMATICA SINICA, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241
  • 智能优化算法又称启发式计算技术[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$\left({0, 1} \right) $概率散落算法的更新机制, 并从理论角度分析算法收敛性和群体样本多样性.

    2) 对StOMP贪婪重构算法进行改进, 引入ECO和拟牛顿梯度追踪策略以实现大规模稀疏度未知数据的准确重构.

    3) 利用多维测试函数和WSNs数据采集环境进行仿真, 以验证所提算法的有效性.

    • 碰撞是一种常见的物理现象, 两个做相对运动的物体在极短时间内发生接触, 并迅速改变运动状态.碰撞按能量角度可以分为完全弹性碰撞(Complete elastic collision, CE)、完全非弹性碰撞(Complete inelastic collision, CI)和非完全弹性碰撞(Non complete elastic collision, NCE), 为了方便描述碰撞物理过程, 以对心碰撞进行研究:设质量为$ m_{1} $、$ m_{2} $的两个物体分别以速度$ \bm{v}_{1} $和$ \bm{v}_{2} $相向运动, $ \Delta t $时刻后发生碰撞, 碰撞后物体速度为$ \bm{v}_{1} ^{\prime } $和$ \bm{v}_{2}^{\prime } $, 对于不同的碰撞过程, $ \bm{v}_{1}^{\prime } $和$ \bm{v}_{2} ^{\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 $个单位质量粒子组成的群体$ {\bf{\Theta }}\left(t \right)=\left\{ {\bm{X}_{1} (t), \bm{X}_{2} \left(t \right), \cdots, \bm{X}_{n} (t)} \right\} $, 每个粒子$ \bm{X}_{i} (t)=\left[{x_{i1} \left(t \right), x_{i2} (t), \cdots, x_{iD} (t)} \right] $代表一个可能的解, $ \bm{G}_{i} (t)=\left[{g_{i1} (t), g_{i2} (t), \cdots, g_{iD} (t)} \right] $、$ \bm{B}(t)=\left[{b_{1} (t), b_{2} (t), \cdots, b_{D} (t)} \right] $分别为$ \bm{X}_{i} (t) $历史最优解和当前群体最优解.

      定义1(优化模型).  对于给定优化函数$ f: {\bf{\Theta }}(t)\to R^{D} $, 寻找一个粒子$ \bm{X}_{\rm best} \in \{ \bm{P}\left(1 \right), \bm{P}\left(2 \right)$, $ \cdots, \bm{P}\left({T_{\max } } \right) \} $ $ (T_{\max } $为算法最大运算次数), 使得$ f\left({\bm{X}_{\rm best} } \right) $最优.

      定义2(极值碰撞).  在ECO中, $ \bm{G}_{i} (t) $与$ \bm{B}(t) $分别以速度$ \bm{v}_{G} $与$ \bm{v}_{B} $相向运动, $ \Delta t $时刻后发生碰撞, 随后两粒子以速度$ \bm{v}'_{G} $与$ \bm{v}'_{B} $继续运动, $ \Delta {t}' $时刻后得到达新的位置$ \bm{G}_{i}^{\prime }(t) $和$ \bm{B}'\left(t \right) $, 即有(以$ \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)可以得到$ \bm{v}'_{G} \left({\bm{v}'_{B} } \right)=\left({\bm{v}_{B} +\bm{v}_{G} } \right)/2 $, 令$ \Delta {t}'=k\Delta t $有:

      $$ \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)

      图  1  极值碰撞示意图

      Figure 1.  Extreme value collision schematic diagram

      定义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.如果$ f\left({\bm{X}_{i} \left({t+1} \right)} \right)\leq f\left({\bm{X}_{i} (t)} \right) $, 用新得到的粒子替换$ \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$\left({n\log D} \right) $, 种群初始化计算复杂度为O$\left(n \right) $, 因此ECO计算复杂度为$ T_{\max } {\rm O}\!\left({n\log D} \right)+{\rm O}\!\left(n \right) $.

    • 对于群体$ {\bf{\Theta }}(t) $, $ \left\{ {{\bf{\Theta }}(t), t=0, 1, 2, \cdots } \right\} $构成离散时间随机过程, 其状态空间为$ E=\left\{ {\theta_{0}, \theta _{1}, \cdots, \theta_{t} } \right\} $, 根据"碰撞更新"定义可以看出, $ {\bf{\Theta }}(t) $当前状态只与上一个状态有关, 即$ p\left\{ {\theta_{t} \left| {\theta _{0}, \theta_{1}, \cdots, \theta_{t-1} } \right.} \right\}=p\left\{ {\theta_{t} \left| {\theta_{t-1} } \right.} \right\} $, 因此$ \left\{ {{\bf{\Theta }}(t), t=0, 1, 2, \cdots } \right\} $为马尔科夫链.

      定义4 (最优解结合).  对于优化问题$ f: {\bf{\Theta }}(t)\to R^{D} $, $ 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)

      令$ \mathbb{Z}\left({{\bf{\Theta }}(t)} \right)=\left| {{\bf{\Theta }}(t)\cap \bm{E}^{\ast }} \right| $为$ {\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) $的数学期望值$ {\rm E}\left({\bm{X}_{i} \left(t \right)} \right) $收敛于某个稳定值.

      证明.  从式(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)可知$ p(\mathbb{Z}({{\bf{\Theta }}\left({t+1} \right)})=0 \, |\, \mathbb{Z}({{\bf{\Theta }}(t)})\ne 0)=0 $, 因此:

      $$ \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 $存在一个足够小的正实数$ \gamma $使得$ 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 $, 由于$ p(\mathbb{Z}({{\bf{\Theta }}({t+1})})=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群体样本多样性评价指标$ \aleph \left({{\bf{\Theta }}(t)} \right) $为:

      $$ %\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) $的标准差.

      证明.  令$ \overline {x_{j} (t)} =\left[ {\sum\limits_{i=1}^n {x_{ij} (t)} } \right]/n $, 则:

      $$ \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) $表示$ {\rm E}(x_{ij} (t)) $的多样性, 根据推论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) $取值较大, 表明算法样本多样性较强, 随着迭代次数增加, 群体向全局最优解靠拢, 导致$ \sigma _{ij} (t) $逐渐降低, 也就说群体多样性在下降, 但是由于ECO算法采用高斯扰动机制, 保证了粒子间差异性, 维持了群体样本多样性.特别的, 扰动机制和不同的"极值碰撞"方式有效提高了算法跳出局部极值的能力, 增强了算法深度搜索能力.

      从ECO实现流程可以看出, ECO属于随机搜索技术范畴, "大规模种群粒子随机分布解空间"的形式使得当前大多数智能优化算法能够以一定概率收敛于全局最优解, 但是"容易陷入局部极值"的缺陷是目前绝大多数智能优化算法需要继续解决的难题, 而ECO通过模拟多种弹性碰撞过程, 提供了多种学习策略, 而且其涉及参数较少, 因此具有容易实现、收敛精度高的优势.此外, 智能优化算法研究已经进入了从理论上深度分析算法性能的阶段, ECO多样性分析证明了其能够保持较好的深度搜索能力, 从一定意义上来讲, ECO研究内容对当前智能优化算法论证具有一定借鉴意义, 很好地克服了传统智能优化算法盲目引入改进策略的缺陷.

    • 当一个$ 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} $, 有$ \bm{y}_{M\times 1} =\bm{A}_{M\times N} \bm{s}_{N\times 1} $. 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].

    • 方红等[18]对贪婪重构算法进行了深入研究, 并指出StOMP (stage-wise orthogonal matching pursuit)算法重构速度快, 适用于大规模信号处理, 但是存在运算量大、测量矩阵RIP (Restricted isometry property)条件要求高以及稀疏度$K $事先确定的缺陷, 为此在StOMP贪婪重构算法内引入ECO和拟牛顿梯度追踪策略, 并将稀疏信号重构分成"线下"和"线上"两个阶段(如图 2所示), 以实现大规模稀疏度未知数据的准确重构(基本StOMP贪婪重构算法原理见相关文献, 不再赘述).

      图  2  改进StOMP贪婪重构算法实现

      Figure 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 $和$ t_{s} $进行训练, 以得到最佳参数组合.

      定义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}_{1}, \bm{y}_{2}, \cdots, $ $\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)

      其中, $ \bm{s}_{N\times 1} =\left({s_{1}, \cdots, s_{N} } \right) $为真实信号, $ {\hat{\bm{s}}}_{N\times 1} =\left({\hat{{s}}_{1}, \cdots, \hat{{s}}_{N} } \right) $为重构信号.从定义7可以看出, $ V_{N} $反映了$ \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} $、测量量$ \bm{y} $、利用ECO得到的$ \left({\tau, t_{s} } \right) $

      1. For $ k=1: {K}' $ // $ {K}' $为未知稀疏度$ K $上限

      2. For $ t=1: t_{s} \left({\left\lfloor {x_{i2} } \right\rfloor } \right) $

      3. IStOMP算法初始化: $ t=1 $、$ \bm{r}_{0} =\bm{y} $、支撑集$ \bm{I}=\bm{\phi } $ $ {\hat{\bm{s}}}_{h, t} =\bm{0} $、$ B_{0} =0 $;

      4.根据计算公式$ J= \{ j\, |\, | \langle {r_{t-1}, \bm{\phi }_{j} } \rangle |\!>\!\tau \left({x_{i1} } \right) \} \, (j= 1, \cdots, N) $, 找出$ \bm{A}_{M\times N} =({\bm{\phi }_{1}, \bm{\phi }_{2}, \cdots, \bm{\phi }_{N} }) $中与$ r_{t-1} $匹配的索引;

      5.更新$ \bm{I}=\bm{I}\cup \bm{J} $, 根据式(33) $ \sim $ (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 $即为稀疏度; 对应的$ {\hat{\bm{s}}}_{t} $即为稀疏信号重构结果.

      从IStOMP重构算法实现过程可以看出, 算法复杂度为O$\left({Kt_{s} \log \left(m \right)} \right) $, 运算量明显降低, 这样保证了算法能够高效地处理大规模数据.

    • 以无线传感器网络(Wireless sensor networks, WSNs)稀疏事件检测为对象进行研究:在WSNs监测范围内放置$ Q $个传感器节点用于监控$ N $个事件源, 某时刻$ N $个事件源随机发生$ K $个网络事件, 用向量$ \bm{s}_{N\times 1} =\left[{s_{1}, s_{2}, \cdots, s_{N} } \right]^{\rm T} $表示所有事件能量信号$ (s_{i} =0 $表示该事件源无事件发生), 显然当$ K\ll N $时, $ \bm{s}_{N\times 1} $为$ K $度稀疏信号.假设$ Q=N $, 则$ N $个节点测量信号$ \bm{x}_{N\times 1} =\left[ {x_{1}, x_{2}, \cdots, x_{N} } \right]^{\rm T} $为:

      $$ \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], 因此对$ \bm{A}_{M\times N} $进行矩阵变换处理, 即:

      $$ \begin{equation} \label{eq40} \bm{A}=\bm{U\Sigma V}^{\rm T} \end{equation} $$ (40)

      其中, $ \bm{\Sigma }_{M\times N} $为半正定对角矩阵, $ \bm{U} $、$ \bm{V} $为正交矩阵, 因此式(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)代表的新测量系统, 根据推导过程可以看出测量矩阵$ \bm{V}_{1} ^{\rm T} $为行正交矩阵, 因此满足RIP条件.

      此时, WSNs稀疏事件检测转换为利用$ M $个工作节点实现对$ K $个事件源检测的问题, 具体实现过程为:在WSNs部署测试阶段利用实验样本数据进行参数训练以得到最佳参数配置组合; 在实际检测阶段利用IStOMP重构算法对测量信号处理以得到稀疏信号向量$ \bm{s}_{N\times 1} $, 从而完成对稀疏事件的实时有效监控.

    • 为了验证ECO算法优化性能, 采用系列基准测试函数进行实验仿真, 表 1给出了6个典型基准测试函数.

      表 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) $
    • 群体规模$ n $、更新控制系数$ \varepsilon $、碰撞自适应学习因子$ \xi $和控制系数$ \beta $是ECO算法涉及的主要参数, 目前关于智能算法参数设置问题普遍采用实验法进行确定, 因此设置$ n $、$ \varepsilon $、$ \xi $、$ \beta $不同取值对$ f_{3} $函数进行测试, 每次运行10次, 取算法最优解均值和平均运行时间进行分析, 图 3~6给出了不同$ n $、$ \varepsilon $、$ \xi $、$ \beta $下最优解均值和平均运行时间变化曲线.

      图  3  不同$ n $下最优解均值和平均运行时间变化曲线

      Figure 3.  Mean value and average run time curve of optimal solution under different $ n $

      图  4  不同$ \varepsilon $下最优解均值和平均运行时间变化曲线

      Figure 4.  The mean value and average run time curve of optimal solution under different $ \varepsilon $

      图  5  不同$ \xi $下最优解均值和平均运行时间变化曲线

      Figure 5.  The mean value and average run time curve of optimal solution under different $ \xi $

      图  6  不同$ \xi $下最优解均值和平均运行时间变化曲线

      Figure 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 $变大逐渐降低, 当$ \varepsilon >0.6 $时, 随着$ \varepsilon $变大, 算法收敛效果明显降低, 这是因为$ \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 $.

    • 为了进一步分析ECO算法收敛性能, 选取经典PSO算法和最近才提出的海豚群算法(Dolphin swarm algorithm, DSA)[20]、狼群智能算法(Smart wolf pack algorithm, SWPA)[21]进行对比实验, 对比分析不同改进策略对优化算法寻优性能影响, 以及ECO收敛效率(PSO、DSA和SWPA参数设置参考相关文献).每种算法独立运行100次, 选取成功率$ Su $ (算法最优解与理论最优解小于阈值$ \delta $次数占实验次数的比值)、最大值$ Max $、最小值$ Min $、均值$ \overline {Ave} $和运算时间$ T $为算法收敛性能对比指标. 图 7给出了4种优化算法函数收敛曲线, 表 2给出了不同函数收敛性能指标对比结果.

      图  7  4种不同优化算法函数收敛曲线

      Figure 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种算法都还要进一步改进, 这是因为函数$ f_{6} $欺骗性较强, 使得算法很难找到全局最优解, 这也表明, 算法改进策略不是万能的, 往往只针对某一类优化问题具有突出性能, 因此需要结合具体实际优化问题对算法进行改进.

    • 将具有$ Q=500 $个传感器节点的WSNs部署在$ N=120 $个需要实时监控温度信息的场所, 传感器节点位置信息和性能指标参数已知, 事件源序列与事件源能量信号$ \bm{s}_{N\times 1} =\left[{s_{1}, s_{2}, \cdots, s_{N} } \right]^{\rm T} $对应.选取均方误差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 } $为重构成功率控制阀值.

    • 在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) $变化情况

      Figure 8.  Changes in different $ K $ values $ \left({\tau, t_{s} } \right) $

      图 8可以看出, 不同$ K $取值下, $ \left({\tau, t_{s} } \right) $取值变化不大, 并且MSE相对较小.因此也证明了利用线下阶段优化$ \left({\tau, t_{s} } \right) $的可行性.后续实验中设置IStOMP参数$ \left({\tau, t_{s} } \right) $为$ \left({2.32, 10} \right) $.

    • 为了进一步分析IStOMP重构算法性能, 在WSNs部署区域人为设定$ K=15 $个事件源发生事件, 并测量这些事件的温度值作为原始信号$ \bm{s}_{N\times 1} $.选取StOMP重构算法[22]、SP重构算法[23]和BSMP重构算法[24]进行对比实验, 实验过程中这些重构算法不知道信号稀疏度$ K $的大小, 每种算法独立重复试验100次.为了降低$ M $取值对重构结果的影响, 根据$ M\geq {\rm O}\left({c\left({K+1} \right)\ln \left({N/K} \right)} \right) $, 令$ M=100 $即网络中有100个节点处于工作状态. 图 9给出了4种重构算法稀疏信号重构对比结果, 表 3给出了重构评价指标对比结果.

      图  9  4种重构算法稀疏信号重构结果对比

      Figure 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重构算法更具有实际应用意义.

    • 为了分析稀疏度$ 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 $对重构结果影响

      Figure 10.  The influence of the sparsity $K$ on the reconstruction results

      图  11  测量数目$ M $对重构结果影响

      Figure 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  不同算法抗噪声能力干扰对比

      Figure 12.  Interference contrast of anti noise ability of different algorithms

      图 12可以看出, 当信噪比在35 db以下是, 4种算法重构成功率都达到90以上, 并且IStOMP要好于其他三种算法, 这也表明IStOMP算法能够提高系统重构鲁棒性.

    • 从稀疏信号重构对比和参数设置对重构性能影响实验可以看出, IStOMP重构性能更加突出:

      1) IStOMP能够实现稀疏度未知信号的精确重构.这是因为针对$ K $未知情况, IStOMP算法采用循环探索方式, 以确保得到最匹配稀疏度, 当然这一定程度牺牲了时间代价, 而IStOMP也采用了拟牛顿迭代方式以提高算法运行速度.因此在实际应用领域, 在可以接受的运算时间范围内, IStOMP重构算法对重构稀疏度未知信号更具有实际应用意义.

      2) IStOMP具有更高的重构精度和重构成功率. "线下"和"线上"阶段划分、ECO算法优化参数配置以及测量矩阵变换处理从不同角度提高了IStOMP重构精度, 仿真实验也验证了这些策略的有效性.

    • 对一种全新智能优化算法及其在WSNs稀疏事件检测中的应用进行了研究, 从理论角度对碰撞优化算法收敛性和样本多样性进行了分析, 这对研究智能优化算法具有一定借鉴意义; 从WSNs稀疏事件检测应用研究入手, 针对稀疏度未知、重构精度要求高、传统贪婪算法固有缺陷, 将ECO与压缩感知相结合, 引入了分阶段检测框架和IStOMP重构算法, 最后仿真实验也验证了ECO算法和IStOMP重构算法的有效性.下一步将针对高维病态函数优化和提高重构算法普适性上做进一步研究.

参考文献 (24)

目录

    /

    返回文章
    返回