改進(jìn)微分進(jìn)化算法在壓縮感知中的應(yīng)用①

閔 濤,李艷敏

(西安理工大學(xué) 理學(xué)院,西安 710054)

1 引言

壓縮感知是數(shù)字化時(shí)代的一個(gè)重要手段,它是針對被測信號(hào)的稀疏性而提出的,近年來得到廣泛的研究[1].壓縮感知主要有三個(gè)重要部分：信號(hào)稀疏表示、測量矩陣的構(gòu)建和重構(gòu)算法.其中重構(gòu)算法是研究壓縮感知問題的核心之一,壓縮感知問題在數(shù)學(xué)上講就是解決優(yōu)化問題.針對這一問題學(xué)者們提出了一些優(yōu)化算法.例如Bregman迭代算法[2]、原始對偶算法[3,4]、正交匹配追蹤算法OMP[5]、截?cái)嗯ｎD內(nèi)點(diǎn)法、基于交替方向算法、加速迭代收縮閾值算法、可分近似稀疏重建算法[6-8]等.但是這些方法都具有一定的局限與不足,因此尋找高效、快速的重構(gòu)算法具有重要的理論意義.

微分進(jìn)化[9]是比較新的基于群體的隨機(jī)優(yōu)化方法.它具有簡單、快速、魯棒性好等特點(diǎn),它的基本思想是：對種群中的每個(gè)個(gè)體i,從當(dāng)前種群中隨機(jī)選擇3個(gè)點(diǎn),以其中一個(gè)點(diǎn)為基礎(chǔ),另外兩個(gè)點(diǎn)為參照做一個(gè)擾動(dòng),所得點(diǎn)與個(gè)體i交叉后進(jìn)行“自然選擇”,保留較優(yōu)者,實(shí)現(xiàn)這種種群的優(yōu)化[10].微分進(jìn)化算法具有較好的全局優(yōu)化性,不容易陷入局部極值.考慮到該算法的諸多優(yōu)點(diǎn),本文對該算法進(jìn)行改進(jìn),提出了一種帶約束的微分進(jìn)化算法應(yīng)用于壓縮感知的求解中,并進(jìn)行了數(shù)值模擬.

2 問題描述

壓縮傳感的基本問題是對一個(gè)信號(hào)進(jìn)行傳輸,為了節(jié)省空間資源需要對信號(hào)進(jìn)行壓縮處理,即對其乘上一個(gè)“長而窄”矩陣,亦即：

其中,稱為壓縮矩陣,為傳輸?shù)男盘?hào).

在信號(hào)處理中一個(gè)重要的概念是稀疏性,它是指信號(hào)中零分量在信號(hào)總長度中所占的比重,若把信號(hào)中非零分量的個(gè)數(shù)記作0-范數(shù)則信號(hào)重建問題可以變成等式約束優(yōu)化問題：

上述問題是一個(gè)組合優(yōu)化問題[11],不能使用已有的數(shù)學(xué)分析工具進(jìn)行求解,而且當(dāng)維數(shù)增大時(shí),問題的復(fù)雜度也會(huì)增大,為了更好的解決此類問題,可以將上述優(yōu)化問題轉(zhuǎn)化為求解問題：

其中

當(dāng)p＞0可以得出式(3)的稀疏解,從下面的幾何圖形來說明.考慮：

求解式(3)實(shí)質(zhì)上是一個(gè)優(yōu)化問題,本文主要對微分進(jìn)化算法進(jìn)行改進(jìn),提出一種帶約束的微分算法,利用此方法求解式(3),取得了較好的效果.

3 改進(jìn)的微分算法

微分進(jìn)化算法具有很好地全局優(yōu)化性,是經(jīng)典的全局優(yōu)化算法,該算法適用于無約束連續(xù)變量的全局優(yōu)化問題,包括線性規(guī)劃、非線性規(guī)劃、非光滑優(yōu)化[12].但是實(shí)際中我們會(huì)遇到一些帶有約束條件的較復(fù)雜的問題,所以我們采用改進(jìn)的微分進(jìn)化算法,該算法在微分進(jìn)化算法的基礎(chǔ)上加入了對約束條件的處理.

圖1 極小化范數(shù)導(dǎo)致稀疏解的幾何說明

設(shè)待求的優(yōu)化問題如下：

其中稱為搜索空間為目標(biāo)函數(shù)為約束條件.

微分進(jìn)化算法是經(jīng)過編碼和初始化、交叉、變異、選擇等操作實(shí)現(xiàn)的,而這些操作過程中參數(shù)的選擇對微分進(jìn)化算法的搜索性能有較大的影響,微分進(jìn)化算法的種群規(guī)模越大,搜索能力會(huì)加強(qiáng),但也會(huì)增加微分進(jìn)化的計(jì)算量,一般取為變量個(gè)數(shù)),交叉概率因子是一個(gè)位于 (0,1)內(nèi)的常數(shù),它決定了變異個(gè)體分量值代替前個(gè)體分量值的概率,即它越大發(fā)生交叉的可能性越大.變異因子F是用來控制差分向量的縮進(jìn),它的取值范圍一般在 (0,1).

改進(jìn)微分進(jìn)化算法選擇的參數(shù)為種群的規(guī)模取為變量個(gè)數(shù)),交叉概率取0.1,變異因子F取0.5,在此基礎(chǔ)上以上述約束優(yōu)化問題(5)為例,對標(biāo)準(zhǔn)微分進(jìn)化算法進(jìn)行改進(jìn),主要表現(xiàn)在對約束條件進(jìn)行處理的這一方面.如下：

針對上述優(yōu)化問題(5),稱為可行點(diǎn)集或可行區(qū)域稱為搜索空間,通常為n維立方體,即稱為目標(biāo)函數(shù),n是變量空間維數(shù).記：

定義邏輯函數(shù)如下：

對于個(gè)體X1和X2,如果b etter(X1,X2)為真則表示X1優(yōu)于X2,否則X2優(yōu)于X1.

改進(jìn)微分進(jìn)化算法的步驟如下：

Setp 1.(初始化) 輸入?yún)?shù)：種群的規(guī)模N,交叉概率Pc,交叉因子F,隨機(jī)生成的初始種群P(0)={X1(0),}為個(gè)體的集合,其中

Step 2.(個(gè)體評(píng)價(jià)) 將群體按邏輯函數(shù)better(x,y)進(jìn)行從好到壞排序,排序后記為其中按順序,X1為最好的個(gè)體,XN為最差的個(gè)體.計(jì)算每個(gè)個(gè)體Xi(t)的適應(yīng)值F(Xi(t)).

Step 3.(繁殖) 對種群中的每個(gè)個(gè)體Xi(t),隨機(jī)生成4個(gè)互不相同的隨機(jī)整數(shù)和

通過交叉變異產(chǎn)生的新個(gè)體：

Step 4.(選擇) 當(dāng)且僅當(dāng)新個(gè)體的評(píng)價(jià)函數(shù)值更好時(shí)才被保留到下一代群體中,否則,父代個(gè)體仍然保留在群體中,再一次作為下一代的父向量,即得到：

Step 5.(終止檢驗(yàn)) 如果種群Xi(t+1)滿足終止條件,則輸出Xi(t+1)中具有最小適應(yīng)值得個(gè)體為最優(yōu)解,否則轉(zhuǎn)Step 2.

標(biāo)準(zhǔn)微分進(jìn)化算法通過這種方式進(jìn)行改進(jìn)之后,可以簡單有效的處理等式約束和不等式約束.具體的判斷方法為：用函數(shù)H(X)來衡量違反約束的程度,H(X)的值大則視為壞個(gè)體,當(dāng)H(X)的值相同時(shí),根據(jù)目標(biāo)函數(shù)f(X)來決定它們的優(yōu)劣.

4 數(shù)值模擬

為了利用改進(jìn)微分進(jìn)化算法的求解,將式(3)轉(zhuǎn)化成求解上述問題：

以下給出數(shù)值模擬：

對上述未知數(shù)個(gè)數(shù)為2、3、4的約束優(yōu)化問題利用改進(jìn)微分進(jìn)化算法進(jìn)行求解,主要控制參數(shù)選取為：種群的 規(guī)模N取為變量個(gè)數(shù)),交叉概率Pc取0.1,交叉因子F取0.5,最大演化代數(shù)取為5000代.當(dāng)p取不同值時(shí),計(jì)算結(jié)果見表1至表3.

從表中可以看出當(dāng)未知數(shù)個(gè)數(shù)為2、3且當(dāng)0

下面將改進(jìn)微分進(jìn)化算法(RDE)與截?cái)嗯ｎD內(nèi)點(diǎn)法(TNIPM)、可變分稀疏重建算法(SpaRSA)、基于交替方向算法的稀疏解(DAIM)、原始對偶內(nèi)點(diǎn)算法(PDIPA)對比.結(jié)果見表4和表5.

表1 模擬1的計(jì)算結(jié)果

表2 模擬2的計(jì)算結(jié)果

表3 模擬3的計(jì)算結(jié)果

由表4、表5可以看出改進(jìn)微分算法的稀疏解比其他優(yōu)化算法的更好,在其它算法中原始對偶算法的稀疏解比截?cái)嗯ｎD內(nèi)點(diǎn)法和基于交替方向算法的更好,而可變分稀疏重建算法效果較差.圖2給出了迭代過程中最好、最差以及新個(gè)體的迭代圖,圖中可以看出隨著迭代次數(shù)的增加改進(jìn)微分進(jìn)化算法的適應(yīng)值越來越好.

圖2 改進(jìn)微分進(jìn)化算法的迭代優(yōu)化曲線圖

表4 模擬4的計(jì)算結(jié)果

表5 模擬5的計(jì)算結(jié)果

5 結(jié)論

本文在微分進(jìn)化的基礎(chǔ)上對其改進(jìn),提出了一種尋優(yōu)性、穩(wěn)定性更好的改進(jìn)微分進(jìn)化算法,將其應(yīng)用到帶約束的壓縮感知求解中,并給出了數(shù)值模擬,模擬結(jié)果表明在改進(jìn)微分算法中選擇范數(shù)得到的解具有較好的稀疏性,而范數(shù)的求解方法得到的解并不具備稀疏性.當(dāng)維數(shù)較小時(shí)本文所提出的改進(jìn)微分進(jìn)化算法的稀疏解更準(zhǔn)確.

1 徐立軍.壓縮感知重構(gòu)算法及其應(yīng)用研究[碩士學(xué)位論文].太原：中北大學(xué),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 李建華,李子鵬,呂顯瑞,等.帶參數(shù)擾動(dòng)的原始對偶內(nèi)點(diǎn)算法求解一類非線性規(guī)劃問題.吉林大學(xué)學(xué)報(bào)(理學(xué)版),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 寧礦鳳,王景芳.壓縮感知分組分離語音增強(qiáng).計(jì)算機(jī)工程與應(yīng)用,2014,50(24)：204-208.[doi：10.3778/j.issn.1002-8331.1309-0040]

9 賈杰.微分進(jìn)化算法研究與仿真實(shí)現(xiàn)[碩士學(xué)位論文].大連：大連理工大學(xué),2015.

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

11 張敏華.壓縮感知中的信號(hào)重構(gòu)算法研究[碩士學(xué)位論文].天津：天津理工大學(xué),2013.

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