改进微分进化算法在压缩感知中的应用①

闵 涛,李艳敏

(西安理工大学 理学院,西安 710054)

1 引言

压缩感知是数字化时代的一个重要手段,它是针对被测信号的稀疏性而提出的,近年来得到广泛的研究[1].压缩感知主要有三个重要部分：信号稀疏表示、测量矩阵的构建和重构算法.其中重构算法是研究压缩感知问题的核心之一,压缩感知问题在数学上讲就是解决优化问题.针对这一问题学者们提出了一些优化算法.例如Bregman迭代算法[2]、原始对偶算法[3,4]、正交匹配追踪算法OMP[5]、截断牛顿内点法、基于交替方向算法、加速迭代收缩阈值算法、可分近似稀疏重建算法[6-8]等.但是这些方法都具有一定的局限与不足,因此寻找高效、快速的重构算法具有重要的理论意义.

微分进化[9]是比较新的基于群体的随机优化方法.它具有简单、快速、鲁棒性好等特点,它的基本思想是：对种群中的每个个体i,从当前种群中随机选择3个点,以其中一个点为基础,另外两个点为参照做一个扰动,所得点与个体i交叉后进行“自然选择”,保留较优者,实现这种种群的优化[10].微分进化算法具有较好的全局优化性,不容易陷入局部极值.考虑到该算法的诸多优点,本文对该算法进行改进,提出了一种带约束的微分进化算法应用于压缩感知的求解中,并进行了数值模拟.

2 问题描述

压缩传感的基本问题是对一个信号进行传输,为了节省空间资源需要对信号进行压缩处理,即对其乘上一个“长而窄”矩阵,亦即：

其中,称为压缩矩阵,为传输的信号.

在信号处理中一个重要的概念是稀疏性,它是指信号中零分量在信号总长度中所占的比重,若把信号中非零分量的个数记作0-范数则信号重建问题可以变成等式约束优化问题：

上述问题是一个组合优化问题[11],不能使用已有的数学分析工具进行求解,而且当维数增大时,问题的复杂度也会增大,为了更好的解决此类问题,可以将上述优化问题转化为求解问题：

其中

当p＞0可以得出式(3)的稀疏解,从下面的几何图形来说明.考虑：

求解式(3)实质上是一个优化问题,本文主要对微分进化算法进行改进,提出一种带约束的微分算法,利用此方法求解式(3),取得了较好的效果.

3 改进的微分算法

微分进化算法具有很好地全局优化性,是经典的全局优化算法,该算法适用于无约束连续变量的全局优化问题,包括线性规划、非线性规划、非光滑优化[12].但是实际中我们会遇到一些带有约束条件的较复杂的问题,所以我们采用改进的微分进化算法,该算法在微分进化算法的基础上加入了对约束条件的处理.

图1 极小化范数导致稀疏解的几何说明

设待求的优化问题如下：

其中称为搜索空间为目标函数为约束条件.

微分进化算法是经过编码和初始化、交叉、变异、选择等操作实现的,而这些操作过程中参数的选择对微分进化算法的搜索性能有较大的影响,微分进化算法的种群规模越大,搜索能力会加强,但也会增加微分进化的计算量,一般取为变量个数),交叉概率因子是一个位于 (0,1)内的常数,它决定了变异个体分量值代替前个体分量值的概率,即它越大发生交叉的可能性越大.变异因子F是用来控制差分向量的缩进,它的取值范围一般在 (0,1).

改进微分进化算法选择的参数为种群的规模取为变量个数),交叉概率取0.1,变异因子F取0.5,在此基础上以上述约束优化问题(5)为例,对标准微分进化算法进行改进,主要表现在对约束条件进行处理的这一方面.如下：

针对上述优化问题(5),称为可行点集或可行区域称为搜索空间,通常为n维立方体,即称为目标函数,n是变量空间维数.记：

定义逻辑函数如下：

对于个体X1和X2,如果b etter(X1,X2)为真则表示X1优于X2,否则X2优于X1.

改进微分进化算法的步骤如下：

Setp 1.(初始化) 输入参数：种群的规模N,交叉概率Pc,交叉因子F,随机生成的初始种群P(0)={X1(0),}为个体的集合,其中

Step 2.(个体评价) 将群体按逻辑函数better(x,y)进行从好到坏排序,排序后记为其中按顺序,X1为最好的个体,XN为最差的个体.计算每个个体Xi(t)的适应值F(Xi(t)).

Step 3.(繁殖) 对种群中的每个个体Xi(t),随机生成4个互不相同的随机整数和

通过交叉变异产生的新个体：

Step 4.(选择) 当且仅当新个体的评价函数值更好时才被保留到下一代群体中,否则,父代个体仍然保留在群体中,再一次作为下一代的父向量,即得到：

Step 5.(终止检验) 如果种群Xi(t+1)满足终止条件,则输出Xi(t+1)中具有最小适应值得个体为最优解,否则转Step 2.

标准微分进化算法通过这种方式进行改进之后,可以简单有效的处理等式约束和不等式约束.具体的判断方法为：用函数H(X)来衡量违反约束的程度,H(X)的值大则视为坏个体,当H(X)的值相同时,根据目标函数f(X)来决定它们的优劣.

4 数值模拟

为了利用改进微分进化算法的求解,将式(3)转化成求解上述问题：

以下给出数值模拟：

对上述未知数个数为2、3、4的约束优化问题利用改进微分进化算法进行求解,主要控制参数选取为：种群的 规模N取为变量个数),交叉概率Pc取0.1,交叉因子F取0.5,最大演化代数取为5000代.当p取不同值时,计算结果见表1至表3.

从表中可以看出当未知数个数为2、3且当0

下面将改进微分进化算法(RDE)与截断牛顿内点法(TNIPM)、可变分稀疏重建算法(SpaRSA)、基于交替方向算法的稀疏解(DAIM)、原始对偶内点算法(PDIPA)对比.结果见表4和表5.

表1 模拟1的计算结果

表2 模拟2的计算结果

表3 模拟3的计算结果

由表4、表5可以看出改进微分算法的稀疏解比其他优化算法的更好,在其它算法中原始对偶算法的稀疏解比截断牛顿内点法和基于交替方向算法的更好,而可变分稀疏重建算法效果较差.图2给出了迭代过程中最好、最差以及新个体的迭代图,图中可以看出随着迭代次数的增加改进微分进化算法的适应值越来越好.

图2 改进微分进化算法的迭代优化曲线图

表4 模拟4的计算结果

表5 模拟5的计算结果

5 结论

本文在微分进化的基础上对其改进,提出了一种寻优性、稳定性更好的改进微分进化算法,将其应用到带约束的压缩感知求解中,并给出了数值模拟,模拟结果表明在改进微分算法中选择范数得到的解具有较好的稀疏性,而范数的求解方法得到的解并不具备稀疏性.当维数较小时本文所提出的改进微分进化算法的稀疏解更准确.

1 徐立军.压缩感知重构算法及其应用研究[硕士学位论文].太原：中北大学,2016.

2 Yin WT,Osher S,Goldfarb D,et al.Bregman iterative algorithms for L1-minimization with applications to compressed sensing.SIAM Journal on Imaging Sciences,2008,1(1)：143-168.[doi：10.1137/070703983]

3 Chambolle A,Pock T.A first-order primal-dual algorithm for convex problems with applications to imaging.Journal of Mathematical Imaging and Vision,2011,40(1)：120-145.[doi：10.1007/s10851-010-0251-1]

4 李建华,李子鹏,吕显瑞,等.带参数扰动的原始对偶内点算法求解一类非线性规划问题.吉林大学学报(理学版),2015,53(6)：1099-1104.

5 Tropp JA,Gilbert AC.Signal recovery from random measurements via orthogonal matching pursuit.IEEE Transactions on Information Theory,2007,53(12)：4655-4666.[doi：10.1109/TIT.2007.909108]

6 Zhang Z,Xu Y,Yang J,et al.A survey of sparse representation：Algorithms and applications.IEEE Access,2015,3：490-530.[doi：10.1109/ACCESS.2015.2430359]

7 Sun T,Cheng LZ.Reweighted fast iterative shrinkage thresholding algorithm with restarts forl1-l1minimisation.IET Signal Processing,2016,10(1)：28-36.[doi：10.1049/ietspr.2015.0096]

8 宁矿凤,王景芳.压缩感知分组分离语音增强.计算机工程与应用,2014,50(24)：204-208.[doi：10.3778/j.issn.1002-8331.1309-0040]

9 贾杰.微分进化算法研究与仿真实现[硕士学位论文].大连：大连理工大学,2015.

10 Liang W,Li XG.Low altitude penetration trajectory planning based on digital map.Flight Dynamics,2008,26(4)：81-85.

11 张敏华.压缩感知中的信号重构算法研究[硕士学位论文].天津：天津理工大学,2013.

12 Kaelo P,Ali MM.Differential evolution algorithms using hybrid mutation. Computational Optimization and Applications,2007,37(2)：231-246.