基于動態規劃理論的改進型價值迭代算法?

(電子科技大學電子工程學院,四川成都611731)

0 引言

隨著無線電測量技術的不斷發展,雷達技術也邁上了一個新的臺階[1-2]。傳統的雷達利用回波信號分析目標的特性,這樣的探測方式被動,無法體現雷達的空間認知能力。于是,有人提出了認知雷達的概念。認知雷達是一種能夠根據回波信號認識環境狀態的雷達。它通過對回波信號的分析,提取出環境信息并動態地改變發射波形,以達到更高的目標分辨率。而認知雷達的核心便在于其智能化,它能自適應地學習認知環境,并能根據環境的變化而作出調整[3-5]。這種能力的高低需要依靠準確而快速的自適應算法來支撐。這樣,提高自適應算法的計算速度和準確度則是在提高寬帶認知雷達的認知能力,所以研究寬帶認知雷達的自適應波形選擇算法有著重要的意義。策略迭代算法、價值迭代算法、Q學習算法都是當前比較流行的自適應算法,它們都是基于動態規劃理論,而動態規劃理論的核心思想來源于貝爾曼最優準則[6-7]。故本文將基于動態規劃理論及其核心思想貝爾曼最優準則,討論一種改進型的價值迭代算法,并通過仿真比較它與其他算法的優劣。

1 動態規劃算法

動態規劃算法是基于貝爾曼最優準則,在馬爾科夫決策模型下提出的。馬爾科夫理論為動態規劃算法提供了選擇決策序列的數學理論基礎,而貝爾曼最優準則為其提供了選擇最優策略的數學代價函數。兩者共同奠定了動態規劃算法的基礎[8-10]。

1.1 馬爾科夫決策模型

圖1表示了馬爾科夫決策裝置與環境交互圖,圖中,對于任意給定的狀態i,可以選擇的動作u ik(就是決策裝置產生的對環境的輸入)集合用U={u ik}表示。其中u ik意味著在i狀態下有k個動作可以選擇。不同的動作作用于環境,將產生不同的下一狀態j,而環境從i狀態轉移到j狀態的概率完全由當前狀態i和當前動作u ik決定,這個特性就是馬爾科夫特性。它表明決策裝置采取哪一動作可以從當前狀態中獲取信息,并根據當前狀態決定。同時,在i狀態下,若能確定下一狀態,則可以選擇合適的動作與之匹配,這便與認知雷達的波形選擇聯系起來了。這樣,動作的選擇便成為了關鍵點。根據圖中的模型,在狀態i時,當采取動作u ik而轉移到狀態j時,狀態將反饋給決策裝置一個報酬λnr(i,u ik,j),其中,λ為折扣因子(0＜λ＜1),r(i,u ik,j)表示狀態從i轉移到狀態j的過程中,采取動作u ik而獲得的報酬。

圖1 馬爾科夫過程模型

1.2 貝爾曼最優準則

現在考慮雷達實際的環境狀態,由于雷達測量目標的實際狀態是有限的,本文將它定為K,即雷達環境共有K個狀態。本文重新定義報酬函數為r(X n,u n(X n),X n+1),表示狀態從X n到狀態X n+1所獲得的報酬。對于一個K狀態的動態規劃問題,本文定義

式中,V n(X n)代表總期望報酬。若策略π={u k}為最優策略,那么,在π={u k}時,

即此時π使得總期望報酬在n時刻以后的值達到最大,對于n時刻以后的所有子問題,π都為最優策略;若π不為最優策略,那么,當狀態發生轉移時,以后子問題所選擇的最優策略將增大V n(X n)的值,這樣通過對n時刻后每一時刻狀態的報酬值進行迭代更新后,將確定出一個滿足所有狀態最優策略。這便是貝爾曼最優準則。

1.3 動態規劃算法

根據以上的敘述,現在本文將動態規劃算法描述如下:該算法從K-1到0時刻反向進行動態規劃。假設π={u k},那么對于n=0,1,…,K-1,式(1)的最優表達式即為

對于一個策略π,現在重新定義報酬函數

令當前狀態X n=i,下一狀態X n+1=j,則式(6)可以表示為

將式(7)寫成概率形式為

每一個狀態都對應了一個最優貝爾曼方程,一共有N個方程,所有狀態的最優貝爾曼方程聯立求解后得到的π={u k}即為最優策略。

2 價值迭代算法及改進的價值迭代算法

計算最優策略的方法一般有策略迭代算法和常規價值迭代算法[11],現在分別加以討論。

2.1 策略迭代算法

策略迭代的基本思想是任意選擇一個策略開始,不斷迭代,直到不再有更好的策略出現為止。基本步驟如下:

步驟1 估值階段:此階段中,本文隨機選擇一個策略uk(i),用貝爾曼最優方程計算其價值函數mk(i),隨后進入步驟2。其中

步驟2 策略改進階段:此階段,利用步驟1中的價值函數值得到一個更好的策略uk+1(i)。

步驟3 如果步驟1和步驟2中的策略完全相同,即uk+1(i)=uk(i)對于每一個狀態i都成立,那么,停止迭代。否則,反復執行步驟1、步驟2,直到uk+1(i)=uk(i)出現。

2.2 常規價值迭代算法

價值迭代算法是一種不斷近似于最優方案的算法,因為它不斷利用貝爾曼最優方程更新,最終得到一個最優的價值函數[12-13]。根據1.3節中的討論,貝爾曼最優方程如下:

式中,S為狀態空間,U為波形控制變量集合。

價值迭代最基本的思想就是,先將價值向量Vn(i)賦予初值,然后再用貝爾曼最優方程即式(11)進行不斷的迭代更新,更新過程中,Vn(i)的值會趨近于一個固定值。如果這種迭代不斷進行下去,那么Vn(i)的值就會在某一時刻達到這個固定值,此值即為最大的價值。但是,通常認為當Vn(i)的值非常接近該固定值時,即可認為該值即為接近最優價值的次優近似值。此時,便可以停止迭代,減少算法的計算量。現在給出價值迭代算法的終止條件:

式中,δ為一很小的控制量,用來控制前后迭代價值的接近程度,λ為式(11)中的折扣因子。式(12)表明,當前后迭代價值即Vn+1(i)與Vn(i)的差別小于δ(1-λ)/2λ時,即停止迭代。

下面給出常規價值迭代的算法步驟:

步驟1初始化所有的V(i),令k=0,設定δ, δ為大于0的常數;

步驟2 對于每一個i∈S,計算

步驟3 如果當前

成立,則轉移到步驟4,否則,令k=k+1,返回到步驟2,繼續迭代;

步驟4 對于每一個i∈S,選擇

此時停止迭代,得到最優策略d?(i)。

步驟3中‖Vk(i)-Vk+1(i)‖的值每一次迭代都會下降,直到其下于門限值時,迭代停止。并且需要指出,該算法是針對所有的i∈S,故每一個狀態都要完成以上每一個步驟。由于常規價值迭代算法需要應用到實際的雷達工作環境中去,所以考慮到實際環境中,該算法并不是最優的。因為該算法運算速度慢,收斂時需要的迭代次數多,這樣便降低了雷達的自適應能力和應變環境變化的能力,所以現在提出一種改進型的價值迭代算法。

2.3 一種改進的價值迭代算法

在常規的價值迭代算法中,計算當前迭代的價值函數時,需要將以前已經計算過的狀態空間中的狀態又計算一遍,這樣便加大了計算的復雜度[14]。改進價值迭代算法便是針對這一缺點而提出。當狀態為i時,已經計算出了Vk+1(i′),其中i′=1,2,…,i-1,此時,可以將已經計算得出的狀態的函數價值Vk+1(i′)來代替Vk(i′),從而避免了重復計算,提高了算法的收斂速度。這種價值迭代算法的收斂速度更快,對環境的變化適應能力也越強。

下面給出改進價值迭代的算法步驟:

步驟1初始化所有的V(i),令k=0,設定δ,δ為大于0的常數;

步驟2 對于每一個i∈S,計算

步驟3 如果當前

成立,則轉移到步驟4,否則,令k=k+1,返回到步驟2,繼續迭代;

步驟4 對于每一個i∈S,選擇

此時停止迭代,得到最優策略d?(i)。

2.4 現在已有的改進價值迭代算法

目前,雷達領域已經擁有幾類改進價值迭代算法,如Gauss Siedel價值迭代算法、相對價值迭代算法以及跨度半-范數判決準則價值迭代算法。這些算法在某一方面都有所改進,但是工程應用實踐性不強。下面,本文將對其中幾種算法的原理加以討論,并與本文的算法進行比較。

(1)相對價值迭代算法

相對價值迭代算法是當前已經被提出的一種改進型價值迭代算法,該算法利用當前已知的狀態情況所產生的價值作為基準,并用當前情況的價值相對于已知狀態價值的差距作為下一狀態的更新依據,對于不含有折扣因子λ時,更新速度很快。然而,實際的雷達環境是需要折扣報酬λ的,所以,此方法不適用于實踐環境。

(2)跨度半-范數判決準則價值迭代算法

此算法的優越性在于提高了前后狀態的判決準確度,即使用半-范數準則代替了常規價值迭代算法的步驟3作為判決方式。這樣做使得算法在判決的準確度上提高了一個層次,但并未在提高更新速度上產生積極效果,雷達依然需要經過大量的計算才能確定發射波形,所以不適應于雷達響應速度的要求。而本文所述算法與其相比的優勢正是在于計算量小,更新速度快。

綜上所述,本文所提價值迭代算法在波形選擇的準確性上雖略顯不足,但其快速的更新速度減輕了雷達的計算量,更加適用于實際環境。故本文所提算法不失為一種實際適應能力更強的算法。

2.5 雷達波形選擇的數學建模

雷達對波形的選擇主要依靠不同波形產生的價值V(i)來決定。如圖2所示,在同一環境情況下,選擇能使目標價值達到最大的波形作為最優波形。設定環境空間為X(x∈X),雷達波形庫為U(u∈U),目標報酬為R(p k,u k,p k+1)。雷達通過對環境的學習將波形庫中的波形與目標環境對應起來,建立一一對應的關系即(x,u)集合,每一個狀態x都會有一個最優波形u與之對應。這樣,當雷達遇到已知環境時,便可以通過波形庫中的對應關系選擇出合適的波形,達到自適應波形選擇的目的。

圖2 雷達波形選擇圖示

2.5.1 目標環境空間和雷達波形庫的設置

目標環境空間設置為X={1,2,3,…,N}表示環境空間X中有N個不同的目標狀態。1,2,3,…,N代表了不同的目標狀態,區分出N個目標狀態。每一個目標狀態都會有一個目標狀態變量值pt與之對應。pt為噪聲對環境目標的污染值,利用M ATLAB噪聲矩陣和隨機矩陣產生。

雷達波形庫設置為U={1,2,3,…,M},表示雷達波形庫U中有M個可供選擇的波形。此處1, 2,3,…,M代表了不同的波形,區分出M個波形可供選擇。不同的波形對環境的影響不同,最終經過學習將確定出不同環境對應的最優波形。

2.5.2 目標環境報酬函數的設置

由于實際環境的狀態情況未知,故只能利用噪聲對環境的污染值來估計環境情況[15],令p k為環境變量值,不同的p k代表了不同的環境狀態,p k的值由隨機噪聲對環境的污染值來確定,選取R(p k,u k,p k+1)=p k+1p k-1作為報酬函數。仿真中,利用M ATLAB產生的隨機矩陣和噪聲函數,對未知環境進行模擬。

2.5.3 建立狀態波形映射表(Mapping)

經過雷達對環境的學習認知,目標環境都會對不同的雷達波形產生不同的報酬,從而產生不同的迭代價值。本文把能使迭代價值達到最大的雷達波形與環境狀態一一對應起來,此時,2.5.1節中的X和U將組合成一個二維映射表,即每一個狀態都將對應于一個最優波形。當雷達進入工作階段時,雷達將以此表作為選擇波形的依據。

2.6 雷達利用改進價值迭代算法進行波形選擇的步驟

雷達對波形的選擇主要分為兩個階段:學習階段和工作階段。學習階段中,雷達將對未知的環境進行學習和認知,并將認知的結果記錄下來。然后,雷達在實際的工作中根據已學習到的波形-狀態關系對波形進行選擇,以適應不同的目標環境。下面將對這兩種環境進行分析。

(1)學習(認知)階段

步驟1 雷達設置當前狀態為x t,并對目標環境隨機發生波形,獲得當前波形所產生的報酬,并計算出迭代價值V(x t)選取迭代價值最大值所對應的波形作為最優波形u t。

步驟2 雷達根據下一時刻狀態再對目標隨機發射波形,獲得下一狀態x t+1的最大迭代價值V(x t+1),并確定最優波形u t+1,并且雷達再根據更新公式更新上一狀態x t的迭代價值V(x t+1)。依次往下,每一步都要確定一個新的狀態及其對應的波形,同時還要更新上一狀態的迭代價值,改變上一狀態的最優波形與狀態的對應關系。

步驟3 直到迭代達到算法的終止條件,迭代結束。此時,雷達中便形成了一個波形-狀態的映射表(Mapping),此表便是以后雷達選擇波形的依據。

(2)工作階段

在此階段,雷達將根據學習階段所產生的波形-狀態映射表(Mapping)對不同的狀態選擇不同的波形。如果在此過程中雷達又認知到新的狀態,那么它會將新的狀態加入到映射表,并更新映射表。

綜合以上兩個階段,雷達將工作在一種動態平衡的環境中,即先認知—工作(同時認知)—再認知。這樣,雷達便能自適應地對環境作出最優的響應。

3 仿真

本節共進行了2個實驗,分別比較了改進型價值迭代算法、策略迭代算法和固定波形選擇算法以及常規價值迭代算法的優劣。然后,再對結果加以分析比較,得出結論。

3.1 基本數據設置

由于在實際情況下,這些參數是未知的,需要通過雷達對環境的學習后能得知,實際中的情況該如何選擇還需更多的研究。所以在仿真實驗中預先設定測量概率、折扣因子和狀態轉移矩陣的數據來模擬真實環境。其中設定狀態空間是4維的,同時使用5種不同的波形對環境進行學習。當目標位于x狀態采用u k波形且檢測為y時的測量概率如表1所示。折扣因子λ=0.91。

表1 測量概率

由于實際環境的狀態情況未知,因此只能利用噪聲對環境的污染值來估計環境情況。在MATLAB中,產生隨機矩陣和噪聲函數對未知環境進行模擬。p k即為k時刻對應的噪聲污染值。

選取報酬函數為

實驗中將通過對比不同算法的波形選擇的準確度來說明各種算法的優劣,現在對波形選擇準確度進行如下定義:

波形選擇的準確度:在改進價值迭代算法前提下,通過仿真雷達對環境進行認知學習后,將獲得一個波形-狀態的映射表。將此表與標準的波形選擇映射表相對應后,兩表將存在一定的差距,即波形選擇的誤差。將此誤差歸一化后,得到歸一化波形選擇誤差σ。再用1減去此歸一化誤差,便得到波形選擇的準確度,即波形選擇的接近率。

波形選擇的準確度(接近率)=1-波形選擇的歸一化誤差率(σ) (20)

3.2 實驗一

在實驗一中,進行改進型價值迭代算法、策略迭代算法和固定波形選擇算法的仿真,通過對波形選擇的準確度和測量次數的比較,說明本算法選擇波形上的有效性。

分別利用改進型價值迭代算法、策略迭代算法和固定波形選擇算法以及設定的數據仿真,得到圖3所示的波形選擇準確度曲線。

實驗一總結:圖3中,波形選擇的準確度隨著測量次數的增加而增加,在相同的測量次數下,可以看出所提改進型價值迭代算法的波形選擇準確度要高于固定波形選擇算法,但同時要差于策略迭代算法。如果使用策略迭代算法,這種準確度更高。但是,在遇到巨大的測量狀態空間和波形空間時,每次策略迭代求解都需要求解等式,要進行大量的計算,此時策略迭代方法的適應能力已經非常差。又因本文提出改進型價值迭代算法的效果已經非常接近策略迭代算法,該算法的優勢在于可以不用頻繁的求解等式和大量計算的情況下,對波形進行選擇,對環境進行判斷。那么此時本文所提算法便成為了一種接近最優方案的次優算法,又因其不需要求解等式,免去了繁瑣的求解工作,很適用于雷達工作狀態。

圖3 實驗一波形選擇的準確度曲線

3.3 實驗二

在實驗二中,比較改進型價值迭代算法、策略迭代算法與常規價值迭代算法的優劣,通過比較,說明改進型價值迭代算法在波形選擇上的優勢。

進行改進型價值迭代算法、策略迭代算法與常規價值迭代算法仿真,得到圖4所示的波形選擇準確度曲線。

圖4 實驗二波形選擇準確度曲線

實驗二總結:圖4比較了改進型價值迭代算法、策略迭代算法和常規價值迭代算法三種方法。橫坐標為波形對環境的測量次數,縱坐標為波形選擇的準確度。可以看出,改進型價值迭代算法和常規價值迭代算法的選擇準確度都要低于策略迭代算法,同時,常規價值迭代算法還要略優于改進型價值迭代算法。但考慮到策略迭代算法求解等式的繁瑣,故改進型價值迭代算法和常規價值迭代算法都有很大的優勢,又因為改進型價值迭代算法利用了許多已知的迭代信息,免去了重復計算的計算量,提高了更新速度。所以在雷達探測環境中還是有很大的優勢的,再者,從圖中可以看出改進型價值迭代算法和常規價值迭代算法已經相差無幾。所以,改進型價值迭代算法是一種可行的選擇。

4 結束語

自適應波形選擇是認知雷達需要解決的核心問題,波形選擇的好壞直接影響到認知雷達的工作質量。本文所提出的改進型價值迭代算法,從仿真中可以看到該算法的優點,在相同的測量次數下,改進型價值迭代算法相比固定波形算法有更高的波形選擇準確度;相比于常規價值迭代算法而言,雖然波形選擇準確度有一定下降但相差無幾。關鍵是在于,改進型價值迭代算法避免了重復計算的計算量,提高了計算速度,提高了雷達工作的效率和自適應能力,這對雷達探測目標環境有著非常積極的作用。所以,綜合考慮波形選擇準確度和計算量時,改進型價值迭代算法不失為一種良好的可應用于雷達實際環境的自適應算法。未來還需在此基礎上進一步研究如何提高改進型價值迭代算法波形選擇的準確度,使其自適應能力進一步增強。

[1]LUO Y,ZHANG Q,HONG W,et al.Waveform Design and High-Resolution Imaging of Cognitive Radar Based on Compressive Sensing[J].Science China (Information Sciences),2012,55(11):2590-2603.

[2]GE P,CUI G,KONG L,et al.Cognitive Radar Waveform Design for Coexistence with Overlaid Telecommunication Systems[C]∥IEEE International Conference on Communication Problem-Solving,Beijing:IEEE,2014:5.

[3]WANG B,WANG J,SONG X,et al.Research on Model and Algorithm of Waveform Selection in Cognitive Radar[J].Journal of Networks,2010,5(9): 1041-1046.

[4]WANG B,WANG J,SONG X,et al.Q-Learning-Based Adaptive Waveform Selection in Cognitive Radar[J].International Journal of Communications, Network and System Sciences,2009,2(7):669-674.

[5]GUERCI J R.Cognitive Radar:The Knowledge-Aided Fully Adaptive Approach[M].Boston:Artech House, 2010.

[6]TAO R,LI B,SUN H.Research Progress of the Algebraic and Geometric Signal Processing[J].Defence Technology,2013,9(1):40-47.

[7]NGUYEN N H,DOGANCAY K,DAVIS L M. Adaptive Waveform and Cartesian Estimate Selection for Multistatic Target Tracking[J].Signal Processing,2015,111(1):13-25.

[8]WANG L,WANG H,CHENG Y,et al.Joint Adaptive Waveform and Baseline Range Design for Bistatic Radar[J].Journal of Central South University,2014, 21(6):2262-2272.

[9]XIN F,WANG J,ZHAO Q,et al.Optimal Waveform Selection for Robust Target Tracking[J].Journal of Applied Mathematics,2013,2013(1):1-7.

[10]葉映宇,文鐵牛,陳俊,等.外輻射源雷達運動目標信號特性及檢測方法研究[J].雷達科學與技術,2014, 12(6):604-608,612.

[11]MCDILL K K,MINCHEW C D.Waveform Selection for an Electrically Enhanced Seine for Use in Harvesting Channel Catfish Ictalurus Punctatus from Ponds[J].Journal of the World Aquaculture Society, 2001,32(3):342-347.

[12]WONG T F,LOK T M,LEHNERT J S.Asynchronous Multiple-Access Interference Suppression and Chip Waveform Selection with Aperiodic Random Sequences[J].IEEE Trans on Communications,1999,47(1):103-114.

[13]KOJIMA H,OMURA Y,MATSUMOTO H,et al.Automatic Waveform Selection Method for Electrostatic Solitary Waves[J].Earth,Planets and Space,2000,52(7):495-502.

[14]ZHAO Y,FENG J,ZHANG B,et al.Current Progress in Sparse Signal Processing Applied to Radar Imaging[J].Science China(Technological Sciences), 2013,56(12):3049-3054.

[15]李靜.基于自適應動態規劃的波形選擇方法研究[D].沈陽:東北大學,2009.