摘 要 在稀疏重构中，重构误差项和稀疏项通常使用一个正则化参数聚合成单目标函数，很难实现2个目标的均衡优化,这个缺陷通常导致稀疏重构精度低.为此，提出一种自适应局部搜索的多目标进化算法.首先，基于范数和l1范数和l1
2范数分别设计了2种梯度迭代软阈值法的局部搜索方法求得相应解，这2种局部搜索方法可以提高解的收敛速度和精确度；其次，通过比较对应的目标函数值来竞争选取每轮的优胜解；然后,采用基于竞争成功率的自适应择优局部搜索方法来产生后期解；最后,在帕雷托前沿面的膝盖区域上采用角度法选取最优解.实验结果表明:测量误差和稀疏项可以达到平衡,在重构精度方面,提出的方法远高于现有的传统单目标方法.相比于StEMO算法，当测量维度M=600时，该方法可以提高33.8%；当噪声强度δ=0.002时可以提高82.7%；当稀疏率KN=0.3时可以提高7.38%.
压缩感知(compressed sensing, CS)把信号采样和压缩相结合，突破了传统的奈奎斯特采样定律.压缩感知理论主要分为3个分支：稀疏表示、观测矩阵的设计和信号重构[1]，其中信号重构在各领域起着重要作用.信号重构的本质是通过M维观测信号(M≪N)恢复一个长度为N的信号.考虑稀疏信号向量x∈RN，根据压缩感知理论可知，在理想情况下可以恢复出原始信号x：
(1)
而当观测过程中存在噪声n时，观测向量为y=Ax+n(n∈Rm).众所周知，直接求解l0范数是一个NP困难问题，可以使用一些方法来求解[2].贪婪算法：包括正交匹配追踪(orthogonal matching pursuit, OMP)[3]和子空间追踪(subspace pursuit, SP)[4]、迂回式匹配追踪(detouring matching pursuit, DMP)[5]等；松弛法：包括基追踪(basis pur-suit, BP)[6]、基追踪去噪(basis pursuit denoising, BPDN)[7]、匹配追踪(matching pursuit, MP)[8]；迭代阈值算法(iterative soft-thresholding algorithm, IST)[9]等.
和贪婪算法相比，松弛法在抗噪方面更有优势[10],其处理方法一般是通过一个拉格朗日乘子α把
和
转化成一个单目标函数
其中α是一个非负数.显然不同的α将产生不同的结果，一般很难选取合适的α值来获得信号的最佳估计.此外，目标函数也可以表示成
分别表示l1范数和l12范数[11-12].在稀疏优化中，l1范数具有低复杂度和良好的鲁棒性，而l12范数具有高精度和更快的收敛速度[13].同时在单目标函数中，α的取值会对重构精度产生剧烈影响，因此，如何在
和
之间达到均衡以克服敏感参数α对重构精度的影响是一个亟需解决的问题.
为此，本文提出了一种新的方法：自适应局部搜索进化多目标(adaptive local search evolutionary multi-objective, ALSEMO)算法.该方法将
和
作为2个目标函数，采用基于分解的多目标进化算法设计了2个局部搜索方法，利用这2个方法的竞争策略来构成自适应性.本文提出的ALSEMO算法有3个优点：
1) 由于2种局部搜索方法产生2个解，保证解的多样性，提高了全局解的可信度；
2) 通过比较2个解的优劣性，保证下一个解总是由前最优解产生，提高解的精确度；
3) 由于在进化前期对解进行了批量搜索，获得了足够多高质量的解，在后期只需选择一个优胜的局部搜索方法，既保证了后期解是在最优方法下产生的，又减少了计算成本.
多目标进化算法主要有非支配排序遗传算法(non-dominated sorting genetic algorithm, NSGA-II)[14]和基于分解的多目标进化算法(multi-objective evolutionary algorithm based on decomposition, MOEAD)[15]两大类.NSGA-Ⅱ适合估计连续的帕雷托前沿(Pareto front, PF)，而当PF不连续或非凸时很难找到PF的膝盖区域(knee region, KR).而且，由于该算法采用拥挤距离来控制种群的多样性，在寻找KR时会被有些次优解干扰导致定位不准确，最优目标向量在PF上难以呈均匀分布.MOEAD算法将目标函数分解成多个子目标函数，加入规范化技术来处理不同比例的目标函数，从而将偏好整合在PF的局部区域，且可以进化出1组在PF上均匀分布的解.
已有文献将多目标进化算法应用在稀疏重构问题上，其中文献[16]提出了多组优化算法来提高在有噪声环境中的重构精度;文献[17]提出软阈值进化多目标算法(soft-thresholding evolutionary multi-objective, StEMO)，通过单次运行产生的1组解来同时优化测量误差和信号稀疏度,最后在PF[18]的KR上获得最优解;文献[19]提出了多目标稀疏模型并且将其用于神经网络;文献[20]提出了多目标自步学习模型(multi-objective self-paced learning, MOSPL)用于解决在初始化过程中参数设置的敏感问题;另外，多目标进化算法也在图像处理领域得到了应用[21-22],文献[23]提出了多目标稀疏解混模型(multi-objective sparse unmixing, MOSU)用于高光谱图像解混.
多目标问题可以描述为
min F(x)=(f1(x),f2(x),…,fm(x))T
(2)
s.t. x∈Ω，
其中，Ω⊆Rm表示决策空间，x=(x1,x2,…,xn)T为n维决策向量，Ω={x∈Rm|hj(x)≤0,j=1,2,…,m}，hj是连续函数，F:Ω→Rm是由m个目标函数组成，Rm是目标函数空间[24].对于解的支配关系有定义，当且仅当：
(3)
成立时，称x1支配x2，表示为x1
x2.若在解空间中不存在x比x*要好，则称x*为帕累托最优解，表示为x*x.最优解的目标函数值所组成的集合称为SPF[25]，表示为
SPF={(f1(x*),f2(x*),…,fm(x*))T| x*∈X*}.
(4)
基于分解的多目标进化方法通常是将前沿面的逼近问题转化为若干个标量优化问题，一般有3种方分解法，分别是加权法[26]、边界交集法[27]和切比雪夫法[28].加权法针对凸问题具有更好效果，而边界交集法必须处理等式约束问题，需要设置惩罚因子，但是惩罚因子的值会影响算法性能.本文采用切比雪夫分解方法，通过调整权重向量来获得不同的帕累托最优解，其模型可表示为
min gte(x|λj,z*)= 
(5)
其中，
是参考点的集合，
是权重向量.利用权重向量λ1,λ2,…,λN把多目标问题分解成N个不同的子问题，然后同时对这些子问题进行优化.MOEAD算法近年来受到学者的广泛认可[29]，它将多目标问题直接分解成N个标量子问题，通过优化这些子问题来产生1组最优解.同时，种群的多样性和适应度也得到了很好的解决.由于该方法用每个子问题的权重向量之间的欧氏距离来确定它们的邻域关系，所以2个相邻子问题进化出的解是非常相似的，因此，每个子问题可以利用其相邻子问题的信息来优化本身.
稀疏重构问题可以近似等价为求解式(1)中x的非零项的位置，在传统方法求解中，通常利用权重参数将测量误差项和稀疏项聚合成一个函数，但是权重参数的值会影响求解精度.为了解决权重参数对重构精度影响的问题，本文采用多目标进化算法，将测量误差和信号稀疏度作为2个目标函数:
(6)
解决该问题的方法主要有NSGA-Ⅱ和MOEAD，根据上文关于NSGA-Ⅱ和MOEAD优劣势分析，本文选用MOEAD.
算法1. ALSEMO算法.
输入：目标函数和
测量矩阵A、观测向量y、算法最大迭代次数Maxt、子问题的个数N、权重向量λ1,λ2,…,λN、每个子问题的邻居个数T；
输出：解集{x1,x2,…,xN}对应的目标函数组成的集合SEF、目标函数值向量F=(F1,F2,…,FN).
步骤1. 初始化：
步骤1.1. 设SEF=∅,k=0.
步骤1.2. 计算出任意2个权重向量之间的欧氏距离，然后获得任意一个权重向量与之最近的T个权重向量并将其作为邻居.对任意的i=1,2,…,N，假设B(i)=(i1,i2,…,iT)，λi1,λi2,…,λiT是距离λi最近的T个权重向量.
步骤1.3. 初始化{x1,x2,…,xN}为第1代种群，其目标函数向量Fi=F(xi).
步骤1.4. 初始化参考点集合z*.
步骤2. 循环与更新：
For i=1,2,…,N do
步骤2.1. 执行差分(differential evolution, DE)进化操作：随机从B(i)中选择2个索引值p，l，然后由xp,xl产生新解
步骤2.2. 执行局部搜索方法：分别将2种局部
搜索方法作用于
产生2个新解
步骤2.3. 提升解质量：对
分别执行修剪策略和变异操作产生非支配解和支配解.
步骤2.4. 执行竞争策略选出非支配解：通过比较ya，yb的目标函数值大小，选择出目标函数值小的解作为非支配解ns.
步骤2.5. 更新参考点z*:对任意j=1,2,…,m，如果
那么将
更新为fj(ns)，即
步骤2.6. 更新相邻的解和SEF：对任意的j∈B(i)，如果gte(ns|λj,z*)≤gte(xj|λj,z*)，则xj=ns，Fj=F(ns)，移除在SEF中所有被F(ns)支配的向量，如果在SEF中没有向量可以支配F(ns)，那么就把F(ns)添加到SEF中.
步骤3. 重复步骤2直到k=Maxt；
步骤4. 获得PF解集{x1,x2,…,xN}；
步骤5. 在PF上用基于角度的方法[18]找到KR并且找出一个最优解.
在找最优解之前，首先利用2个目标函数和的最大值将PF进行规范化，然后使用B样条函数对PF进行插值操作使其平滑，从平滑样条中均匀重采样得到PF′，最后在PF′使用基于角度法找到KR[16]，并且在KR上用基于角度的方法找出一个最优解使得在稀疏重构中均衡测量误差和信号稀疏度.
算法1中初始化种群{x1,x2,…,xN}是由3个步骤完成的：1)随机产生一个从1～N的整数排列作为x的稀疏支撑集S;2)所有的x都设置为N×1的矩阵;3)产生一个1×K的随机数矩阵，其元素值在0～1之间，然后将这些元素值分别赋值给支撑集S的1～K个索引，K在本文中表示信号稀疏度.
在3.2节步骤2.1中，对于
中任意一个元素
它产生于
y-r={xi1r+θ×(xi2r-xi3r)， 概率为ω， xi1r， 概率1-ω，
(7)
其中，θ和ω是2个差分进化控制参数.步骤2.2中局部搜索方法(见3.6节)用来提高解的质量.
在步骤2.2中获得2个解之后，通过修剪策略和变异操作得到2个新解
对于
中任意一个元素
它得于修剪策略
(8)
同理，可以得到
这里ll=0，lh=1.再经过高斯变异可得2个解ya，yb.对于ya={ya1,ya2,…,yan}中任意一个元素yar.它由高斯变异得到:
(9)
这里
为高斯变异操作，N(·)表示高斯分布，yar∈[ll,lh]，σG=(ll-lh)M.其中P，M为高斯变异控制参数.
在3.2节步骤2.4中，对任意的j=1,2,…,m，如果有fj(ya)<fj(yb)，那么ya支配yb，否则相反.步骤2.5中参考点z*由非支配解更新.步骤2.6中考虑第i个子问题的所有邻居并且比较它们和当前非支配解的目标函数值的大小，如果有fj(ns)<fj(xj)就用ns代替xj，同时更新SEF，算法达到终止条件即可获得最优解集{x1,x2,…,xN}.
对于稀疏优化问题，为了有效地提高解的质量，在差分进化操作后采用梯度迭代软阈值(gradient iterative soft-thresholding, GIST)的局部搜索, 这样有利于促进次优个体向最优方向进化.
GIST是一个范数最小化优化方法，它可以解决问题:
F(x)=f(x)+αg(x)，
(10)
其中，α是拉格朗日乘子，
其2种情况分别为
和
若差分进化产生xc，然后由梯度下降法得到:
xk=xc+β
xc，
其中，xc=AT(y-Axc)为xc的梯度，β=1为步长，最后xk+1是由迭代获得：
当
时，
(11)
当
时，
(12)
其中，
为了提升解的精度，本文将3.6节中的局部搜索方法结合到进化算法中实现自适应局部搜索方法，一方面可以加速算法收敛速度从而在较短的时间内获得帕雷托最优解集(Pareto optimal set)，在另一方面，有利于保持解的多样性，从而在PF有均匀的分布.自适应方法结合了2种局部搜索策略，如图1所示:
Fig. 1 Adaptive local search method framework
图1 自适应局部搜索方法流程
算法2. 基于竞争策略的自适应算法.
输入：经过差分进化操作后得到的解
输出：最优解集{x1,x2,…,xN}.
步骤1. 初始化：t1,t2=0,j=1,2,…,m，q=1,2,…,n；
步骤2. 由梯度下降法获得
步骤3. ALS -Ⅰ产生
产生
步骤4. 若
则由
更新z*，同时t1自增，否则由
更新z*，同时t2自增；
步骤5. 若t1>t2，则由ALS -Ⅰ产生
否则由ALS -Ⅱ产生同时更新z*；
步骤6. 重复步骤3与4直到k=Maxt2且k%2=0.
在差分进化操作后，算法2利用2个局部搜索方法ALS -Ⅰ和ALS -Ⅱ产生2个解，然后比较这2个解的目标函数值选出当前优胜解来更新z*和邻域信息，最后根据优胜次数选出局部搜索方法产生解.
图2描述了2种局部搜索算法竞争获得最优解的流程，其中A={xk,k=0,1,…,n}由ALS -Ⅰ产生，B={sk,k=0,1,…,n}由ALS -Ⅱ产生.它们都满足式(10)，所以这2个解使得成立：
(13)
Fig. 2 The illustration of the optimal solutiongeneration process
图2 最优解的产生流程示例
根据文献[19]有xk+1≠xk，sk+1≠sk，所以A和B中解的关系可以描述为
(14)
为了分析 xk+1和sk+1的关系，首先需要计算这2个解的目标函数值：
(15)
其中，k=0,1,2,…n.xk+1和sk+1是由2种方法产生的，所以有F(xk+1)≠F(sk+1).除此之外还需要考虑2种情况：
1) 当F(xk+1)<F(sk+1)时，则有：
F(xk+1)<F(sk+1)⟹F(xk+1)-F(sk+1)<0⟹ (f(xk+1)+αg(xk+1))-(f(sk+1)+ αg(sk+1))<0⟹(f(xk+1)-f(sk+1))+ α(g(xk+1)-g(sk+1))<0，
(16)
其中，α>0，则有 f(xk+1)<f(sk+1)或g(xk+1)<g(sk+1)，所以xk+1sk+1.
2) 当 F(sk+1)<F(xk+1)时，证明过程和①相同，此时有sk+1xk+1.
如果ALS -Ⅰ在前k次迭代中竞争成功，那么按照算法2，ALS -Ⅱ生成B中的sk+1～sN将被淘汰，不在最优解集中.同理，如果ALS -Ⅱ在前k次迭代中竞争成功，则A中的xk+1～xN将不在最优解集中.具体比较过程如图2中示例所示，其中假设了一种2组解集可能存在的关系，此时2组解之间的支配关系为
{x1s1,s2x2,x3s3,x4s4,…,sk-1xk-1, xksk,xk+1sk+1,xk+2,xk+3,…,xN-1，xN}，
(17)
则帕雷托最优解集可表示为
{x1,s2,x3,s4,…,sk-1,xk,xk+1, xk+2,xk+3,…,xN-1,xN}，
(18)
其中，sk+1～s1已被淘汰.最后，用基于角度的方法(angle-based method)[18]在帕雷托最优解集上找到最优稀疏解.
实验分为2部分：1)证明稀疏重构问题存在KR，并且此区域的解能够使测量误差和稀疏度达到均衡;2)通过比较9种稀疏重构方法来证明了本文提出的ALSEMO算法具有更高的重构精度.为了与StEMO算法对比，本实验算法最大迭代次数为200，种群数为100，每个子问题的邻居个数为20.真实模拟信号xor是随机产生的稀疏信号，它由3个步骤产生：
1) 随机选择非零系数的子集，子集基数代表xor中的非零元素；
2) 非零元素值服从标准正态分布；
3) xor被归一化为单位长度,测量矩阵A是一个元素值服从标准正态分布的高斯随机矩阵.
4.1.1 测试M对KR的影响
高斯随机测量矩阵的维度M范围为600～1 800，间隔为200，N=2 000，x的长度n=2 000，原始信号稀疏度K=100.
图3显示了当M分别设置为600，1 200，1 800时KR位置的变化.图3(a)～(c)中上半部分为2D图，圆圈虚曲线表示测量误差，星型虚曲线表示重构误差E，这里E=x-xor.图3(a)～(c)中下半部分显示了，E和信号稀疏度
之间的3D图.共做了8组不同的M，分别从600～1 800，列出了3组具有代表变化趋势的实验结果.从图3中，可以看到PF上确实存在一个KR，且随着M的增大E变的不稳定，解的分布也比较分散，但KR的位置几乎不随M的变化而变化，其值大约是100，这与原始信号的稀疏度相符，从侧面印证了原始信号的最佳重构结果位于KR.
Fig. 3 The relations among E, 
, 
图
之间的关系
图4用盒图描述了不同的M对KR变化的统计结果, 对每1组M做10次独立重复实验.每1组实验由3个盒图组成，分别是KR中解的零范数，加性白噪声
，测量误差
.从图4中可以看出在KR中解的零范数大约是100，它的值不会随M的变化而变化.这个结果符合预期效果，因为初始化的信号稀疏度就是100.每个子图中的
和几乎是相等的，这一结论证明了尽管观测数据被噪声污染但依然能够精确重构原始信号.而在稀疏重构问题中, 噪声和信号稀疏度K往往是未知的，所以可以通过来估计，而KR可以用来估计信号稀疏度K，解决了在传统方法重构时需要以稀疏度已知为前提条件的缺陷.
Fig. 4 The box-plots of KR, 
and for each M
图4 每个M对应
的盒图
另一方面，随着M的增加，也越来越大，这是因为在观测过程中原始信号中越来越多的元素被噪声污染.分析图4实验数据可以得知，当M在1 000～1 800之间时，
与越来越接近，这意味着在此区间可以获得高精度的重构效果，若两者越接近，则说明信号重构精度越高，这也为稀疏重构提供了一个最佳的观测矩阵维度区间.从图3中也可以看出当测量维度M在1 200～1 800时，2条曲线有重合的趋势，也说明了在此区域测量误差和重构误差很接近，重构精度越高.
4.1.2 测试δ对KR的影响
本组实验中M=1 200，K=100，N=2 000，n=2 000, 通过向观测矩阵A中添加一个服从N(0,δ2)正态分布的随机变量来模拟噪声，δ取值范围为0.008～0.022，间隔为0.002.最左边的2D图描述了随着的变化，，E的变化趋势，中间的图描述了E和噪声强度之间的关系，因为前面提到测量误差可以估计噪声强度，最右边显示了
之间的3D图.从图5中最左边的2D可以看出明显存在一个KR且随着δ的增大KR变得平缓光滑，这是由于噪声的干扰使得KR中解分布得比较分散，从而使得最优解估计变得困难，但是KR的位置也不随δ的增大而改变，其值大约是100.实验证明KR上存在一个最优解可以在和之间达到均衡，也就是只有快速突破稀疏限制才能获得更高的重构精度.图6中的盒图显示了不同的δ对KR变化的统计结果，对每1组δ做10次独立重复实验.从图6中可以看出在KR中的解的零范数大约是100, 其值不会随δ的变化而变化.
Fig. 5 The relations among E, ,
图
之间的关系
Fig. 6 The box-plots of KR, and for each δ
图6 每个δ对应的盒图
4.1.3 测试K对KR的影响
在本组实验中M=1 200，N=2 000，K的取值范围为100～300，其间隔为100，δ=0.01.对于每个K，其非零元素的位置是随机的且元素值服从正态分布.随着K的增加，稀疏求解问题变得复杂困难，为此，将种群大小和最大迭代次数增加至300，以取得更好的PF和重构效果.图7显示了KR的位置随K变化情况，可以看出KR总是落在K的位置，这意味着KR中解的非零项刚好就是原始信号的稀疏度，KR可以提供一个与真实信号相近的解.对每1组K做10次独立重复实验，图8用盒图显示了不同的K对KR变化的统计结果.从图8中可以看出,KR区域中解的零范数随着K的变化而变化且其值是近似相等.另一方面，E随K的增加而增加，这是由于信号越复杂，重构越困难，精度就越低.
Fig. 7 The relations among E, 
, 
图
之间的关系
Fig. 8 The box-plots of KR, 
and for each K
图8 每个K对应
的盒图
在本组仿真实验中，真实信号的产生方法和之前一样，长度为2 000.将ALSEMO算法和其他8种经典的单目标方法[30]在重构性能上进行了比较，这8种方法分别是：OMP，BP，Homotopy Method (HM)，PFP，L1LS，SpaRSA，FISTA，ALM.对每1组实验，观测向量y中加入了服从N(0,0.01)分布的噪声，图9～12中每一个数据是经过10次独立重复实验后所得的平均重构误差(average estimation error)，表示为Ea.比较算法中所用的容忍参数为ε=0.3,α=0.02.
Fig. 9 The Ea on different M
图9 不同测量维度M下的重构误差
Fig. 10 The Ea on different noise level
图10 不同噪声强度δ下的重构误差
Fig. 11 The Ea on different sparsity ratio
图11 不同稀疏率K
N下的重构误差
Fig. 12 Performance comparison of ALSEMOwith StEMO
图12 比较ALSEMO和StEMO算法性能
在图9中，稀疏率KN=0.1，M为600～1 800，间隔为200，其显示了随着M的变化Ea的变化情况，可以看出ALSEMO算法的Ea低于其他算法，但是当M在1 000～1 600之间时OMP低于ALSEMO，这是因为容忍参数ε极大地影响了OMP的重构性能，并且这些实验的选择值ε=0.3恰好是最佳选择，但是在ε取其他值时可能表现不佳.在图10中，KN=0.1，噪声δ的取值范围为0.002～0.014, 间隔为0.002.随着δ的增加，所有算法的Ea都增大，但是ALSEMO算法的Ea始终保持最低，说明ALSEMO具有更好的抗噪性能.图11显示了随着稀疏率KN的增加，所有算法的Ea都在增加，但是ALSEMO算法的Ea始终保持最小.3组实验证明了本文提出的ALSEMO算法要比其他8种算法的重构精度高，这是由于本文建立了多目标模型，采用多目标进化求解方法避免了传统求解方法中存在参数敏感的问题，从而提高了重构准确度.
图12通过比较StEMO算法来证明ALSEMO具有更低的重构误差.在图12(a)中，随着M的增加，ALSEMO和StEMO算法的Ea都在下降，但是ALSEMO总保持较低的Ea，说明ALSEMO具有更高的重构精度.这是由于ALSEMO是以MOEAD为框架，相比于StEMO 它对KR的定位更加准确，并且结合基于l12和l1范数的2种局部搜索方法自适应地选择出最优解，提升了解的精度和收敛速度.在图12(b)中，两者的Ea都在增加，但ALSEMO总是低于StEMO，说明ALSEMO具有更好的抗噪性能.在图12(c)中，Ea随着稀疏率的增加而增加，但是ALSEMO总低于StEMO，这说明了ALSEMO在信号变得复杂时依然能够保持较低的重构误差.
本文的主要工作概括为3点：1)将稀疏重构问题中的单目标问题转化为多目标问题并建立多目标模型，然后提出了一种自适应局部搜索的多目标进化算法来求解此模型；2)通过实验证明了对于稀疏重构问题，可以在PF得到一个KR，此区域的解可以在和之间达到平衡；3)通过分析实验，可以得知KR的位置可以估计
可以估计测量过程中的噪声.实验结果表明，本文提出的自适应局部搜索方法能提高解的精度，且重构误差低于单目标算法和StEMO.在未来的研究中，将集中研究当PF不连续或者非凸时如何找到KR，并在此区域找到一个最优解的问题.
[1]Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory: Earth Interactions, 2006, 52(4): 1289-1360
[2]Nie Dongdong, Gong Yaoling. A sparse signal reconstruction algorithm based on approximate l0 norm[J]. Journal of Computer Research and Development, 2018, 55(5): 1090-1096 (in Chinese)(聂栋栋, 弓耀玲. 基于近似l0范数的稀疏信号重构[J]. 计算机研究与发展, 2018, 55(5): 1090-1096)
[3]Bruckstein A M, Donoho D L, Elad M. From sparse solutions of systems of equations to sparse modeling of signals and images[J]. SIAM Review, 2009, 51(1): 34-81
[4]Dai Wei, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Transactions on Information Theory, 2009, 55(5): 2330-2249
[5]Pei Tingrui, Yang Shu, Li Zhetao, et al. Detouring matching pursuit algorithm in compressed sensing[J]. Journal of Computer Research and Development, 2014, 51(9): 2101-2107 (in Chinese)(裴廷睿, 杨术, 李哲涛, 等. 压缩感知中迂回式匹配追踪算法[J]. 计算机研究与发展, 2014, 51(9): 2101-2107)
[6]Chen Shaobing, Saunders M A, Donoho D L.Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1): 129-159
[7]Sajjad M, Mehmood I, Abbas N, et al. Basis pursuit denoising-based image superresolution using a redundant set of atoms[J]. Signal, Image and Video Processing, 2016: 10(1): 181-188
[8]Abdel-Sayed M M, Khattab A, Abu-Elyazeed M F. Adaptive reduced-set matching pursuit for compressed sensing recovery[C] //Proc of IEEE Int Conf on Image Processing. Piscataway, NJ: IEEE, 2016: 2499-2503
[9]Carrillo R E, Polania L F, Barner K E. Iterative algorithms for compressed sensing with partially known support[C] //Proc of the 35th IEEE Int Conf on Acoustics Speech and Signal Processing. Piscataway, NJ: IEEE, 2010: 3654-3657
[10]Jiang Yuan, He Yunxiao, Zhang Heping. Variable selection with prior information for generalized linear models via the prior LASSO method[J]. Journal of the American Statistical Association, 2016, 111(513): 355-376
[11]Yin Penghang, Lou Yifei, He Qi, et al. Minimization of l1-2 for compressed sensing[J]. SIAM Journal on Scientific Computing, 2015, 37(1): A536-A563
[12]Xu Zongben, Chang Xiangyu, Xu Fengmin, et al. l1/2 regularization: A thresholding representation theory and a fast solver[J]. IEEE Transactions on Neural Networks & Learning Systems, 2012, 23(7): 1013-1027
[13]Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1): 183-202
[14]Li Hui, Zhang Qingfu. Multiobjective optimization problems with complicated pareto, MOEA/D and NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2009, 12(2): 284-302
[15]Zhang Qingfu, Li Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731
[16]Li Hui, Fan Yuanyuan, Zhang Qingfu, et al. A multi-phase multiobjective approach based on decomposition for sparse reconstruction[C] //Proc of IEEE Conf on Evolutionary Computation. Piscataway, NJ: IEEE, 2016: 601-608
[17]Li Lin, Yao Xin, Stolkin R, et al. An evolutionary multiobjective approach to sparse reconstruction[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(6): 827-845
[18]Branke J, Deb K, Dierolf H, et al. Finding knees in multi-objective optimization[G] //LNCS 3242: Proc of the 8th Int Conf on Parallel Problem Solving from Nature. Berlin: Springer, 2004: 722-731
[19]Gong Maoguo, Liu Jia, Li Hui, et al. A multiobjective sparse feature learning for model for deep neural networks[J]. IEEE Transactions on Neural Networks & Learning Systems, 2017, 26(12): 3263-3277
[20]Li Hao, Gong Maoguo, Meng Deyu, et al. Multi-objective self-paced learning[C] //Proc of the 30th AAAI Conf on Artificial Intelligence. Piscataway, NJ: IEEE, 2016: 1802-1808
[21]Gong Maoguo, Zhang Mingyang, Yuan Yuan. Unsupervised band selection based on evolutionary multiobjective optimization for hyperspectral images[J]. IEEE Transactions on Geoscience & Remote Sensing, 2015, 54(1): 544-557
[22]Li Hao, Gong Maoguo, Wang Qiao, et al. A multiobjective fuzzy clustering method for change detection in SAR images[J]. Applied Soft Computing, 2016, 46(C): 767-777
[23]Gong Maoguo, Li Hao, Luo Enhu, et al. A multi-objective cooperative coevolutionary algorithm for hyperspectral sparse unmixing[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(2): 234-248
[24]Gong Maoguo, Jiao Licheng, Yang Dongdong, et al. Research on evolutionary multi-objective optimization algorithms[J]. Journal of Software, 2009, 20(20): 271-289
[25]Jiang Xiangming, Gong Maoguo, Li Hao, et al. A two-phase multiobjective sparse unmixing approach for hyperspectral data[J]. IEEE Transactions on Geoscience and Remote Sensing, 2018, 56(1): 508-523
[26]Li Hui, Zhang Qingfu. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 284-302
[27]Siddiqui S, Azarm S, Gabriel S A. On improving normal boundary intersection method for generation of Pareto frontier[J]. Structural & Multidisciplinary Optimization, 2012, 46(6): 839-852
[28]Messac A, Ismail-Yahaya A, Mattson C A. The normalized normal constraint method for generating the Pareto frontier[J]. Structural & Multidisciplinary Optimization, 2003, 25(2): 86-98
[29]Liu Hailin, Gu Fangqing, Zhang Qingfu. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 450-455
[30]Yang Ailen, Zhou Zihan, Andrew W, et al. l1 Benchmark Package, Version 1.0: Available[EB/OL]. (2009-01-01) [2017-08-27]. http://www.eecs.berkeley.edu/yang/software/l1benchmark/l1benchmark.zip
Abstract In sparse recovery, a regularization parameter is usually introduced to aggregate the measurement error term and the sparsity term into a single function, but it is hard to balance them, and this weakness usually leads to low precision of sparse recovery. To solve this problem, a new evolutionary multi-objective approach based on adaptive local search method is proposed in this paper. First, two gradient iterative soft thresholding local search methods based on l1 norm and l12 norm are designed to obtain corresponding solutions, and they can improve the convergence speed and accuracy of the solutions. Second, the winner solution is selected by comparing the corresponding objective function values in each round. Then, based on the competition success rate, the winner local search method is chosen adaptively to generate latter solutions. Finally, the optimal solution is derived by the angle-based method on the keen region of Pareto front. Experiments show that the measurement error and the sparsity terms can be balanced and our proposed method gains an advantage over the other eight single objective algorithms in terms of recovery accuracy. Compared with the StEMO algorithm, our approach can improve more than 33.8% when the measurement dimension M=600, 82.7% when the noise intensity δ=0.002, and 7.38% when the sparsity ratio KN=0.3.
