鄧 敏 伍志高 姚志強(qiáng) 陳永其

①(中國電子科技集團(tuán)第36研究所通信信息控制和安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 嘉興 314000)

②(湘潭大學(xué)自動(dòng)化與電子信息學(xué)院 湘潭 411105)

1 引言

近年來，無人機(jī)(Unmanned Aerial Vehicle,UAV)應(yīng)用領(lǐng)域不斷擴(kuò)展，如何高效使用反無人機(jī)設(shè)備反制、干擾“黑飛”無人機(jī)，防護(hù)禁飛區(qū)域、防止重大事件現(xiàn)場(chǎng)信息泄露、打擊利用無人機(jī)進(jìn)行違法活動(dòng)，成為行業(yè)熱點(diǎn)，而通過電磁干擾使對(duì)方設(shè)備癱瘓是主要目標(biāo)[1]。隨著電磁環(huán)境復(fù)雜化、無人機(jī)行動(dòng)方式協(xié)同化[2]，調(diào)度各種規(guī)模數(shù)量的干擾資源對(duì)無人機(jī)群進(jìn)行協(xié)同干擾成為一種趨勢(shì)。資源調(diào)度問題是一種NP(Nondeterministic Polynomially)問題[3]，至今沒有最優(yōu)的求解方法。已有研究集中在調(diào)度建模和求解算法兩個(gè)方面。

在干擾資源調(diào)度建模與優(yōu)化求解中，用最小的調(diào)度成本達(dá)到最大的干擾效益是主要目的。在模型構(gòu)建方面，文獻(xiàn)[4]將目標(biāo)威脅等級(jí)、資源干擾樣式以及目標(biāo)雷達(dá)網(wǎng)的檢測(cè)概率作為干擾效益，并對(duì)干擾數(shù)量、模式數(shù)量、被干擾數(shù)量和相同模式干擾機(jī)數(shù)量進(jìn)行了限制。文獻(xiàn)[5]以資源的協(xié)同規(guī)則構(gòu)建了基于協(xié)同目標(biāo)分配規(guī)則的模型，以反輻射殺傷收益為目標(biāo)，并對(duì)是否攻擊、單個(gè)無人機(jī)可攻擊數(shù)量和目標(biāo)可被攻擊數(shù)量進(jìn)行了約束。文獻(xiàn)[6]根據(jù)干擾前后被攔截的雷達(dá)脈沖的幅度和數(shù)據(jù)速率變化，提出了一種從偵察和干擾系統(tǒng)的角度定量評(píng)估自我篩選干擾有效性和效果的方法。文獻(xiàn)[7]從抑制功率、頻率對(duì)準(zhǔn)比、干擾覆蓋空間和干擾模式分析收益，但僅對(duì)單個(gè)資源的可干擾數(shù)量和單個(gè)目標(biāo)的可被干擾數(shù)量進(jìn)行了限制。文獻(xiàn)[8]以雷達(dá)網(wǎng)檢測(cè)概率為評(píng)價(jià)指標(biāo)，計(jì)算了單部雷達(dá)在多樣式干擾下的檢測(cè)概率，再映射到計(jì)算全網(wǎng)的受干擾影響程度。文獻(xiàn)[9]將UAV的飛行距離作為效益，飛行時(shí)間作為成本，并對(duì)資源和目標(biāo)的干擾數(shù)量以及被干擾數(shù)量、目標(biāo)執(zhí)行順序、時(shí)間窗口、最大飛行路徑和時(shí)間以及同時(shí)到達(dá)時(shí)間這幾個(gè)方面進(jìn)行約束。總體來說，現(xiàn)有單個(gè)干擾資源調(diào)度模型的評(píng)價(jià)指標(biāo)類型較少，資源與目標(biāo)的分配模式約束多為一對(duì)一或多對(duì)一，較少考慮完成任務(wù)數(shù)和資源使用情況的約束。而在一些應(yīng)用中，只有當(dāng)對(duì)方被干擾掉的無人機(jī)達(dá)到一定數(shù)量時(shí)，才能達(dá)到有效防護(hù)和反制目的，上述研究并未充分凸顯出干擾無人機(jī)群的復(fù)雜環(huán)境。

根據(jù)資源調(diào)度優(yōu)化問題的模型，已有研究提出了一些有效的求解算法。文獻(xiàn)[10]提出了帶動(dòng)態(tài)交叉率與變異率的遺傳算法，維持了群體的多樣性，且避免了過早收斂。文獻(xiàn)[11]提出了一種分層多代理優(yōu)化算法，結(jié)合了多智能體優(yōu)化算法和遺傳算法(Genetic Algorithm, GA)，以提高資源利用率。文獻(xiàn)[12]基于最佳動(dòng)態(tài)反應(yīng)設(shè)計(jì)了集中式迭代干擾策略選擇算法，并基于學(xué)習(xí)自動(dòng)機(jī)原理提出了分布式有限反饋干擾資源分配算法。文獻(xiàn)[13]通過引入貪婪算法，增強(qiáng)了遺傳算法的性能。文獻(xiàn)[14]和文獻(xiàn)[4]分別提出自適應(yīng)蟻群算法、混合量子行為粒子群優(yōu)化和自調(diào)整遺傳算法，提高算法可靠性。文獻(xiàn)[15]則利用人工免疫系統(tǒng)來求解問題。文獻(xiàn)[16]聚焦于干擾抑制法的干擾能量比，將所提模型松弛為一個(gè)凸優(yōu)化問題。文獻(xiàn)[17]提出一種基于自舉專家軌跡分層強(qiáng)化學(xué)習(xí)的干擾資源分配決策算法，解決跳頻干擾決策難題。目前智能算法大多被用于求解小規(guī)模的資源調(diào)度問題，求解速度快于傳統(tǒng)數(shù)學(xué)算法。文獻(xiàn)[18]提出改進(jìn)遺傳算法，驗(yàn)證了大規(guī)模(如500:500)資源調(diào)度性能，但方案不能保證最少完成任務(wù)數(shù)等復(fù)雜情況。上述文獻(xiàn)大多采用小規(guī)模、較少約束的干擾無人機(jī)群資源調(diào)度模型，對(duì)所用算法能達(dá)到的時(shí)效性和規(guī)模擴(kuò)展后的適用性提及較少。而此類算法在中、大規(guī)模、多約束的情況下會(huì)有運(yùn)行時(shí)間過長、局部收斂等問題，求解復(fù)雜度和耗時(shí)會(huì)增加，設(shè)計(jì)算法需要在時(shí)間和優(yōu)化目標(biāo)值之間折中。

并行計(jì)算因具有加速代碼運(yùn)行和避免算法過早收斂的特點(diǎn)，成為改進(jìn)智能算法的一個(gè)方向[19]。并行進(jìn)化算法有個(gè)體分布和維度分布兩種類別。其中常用的個(gè)體分布有主-從模型、島嶼模型、細(xì)胞模型、混合模型以及池模型。基于并行進(jìn)化模型的算法能夠比非并行算法更快解決中、大規(guī)模的干擾資源調(diào)度問題，且能得到近似的優(yōu)化目標(biāo)值。

為了解決中、大規(guī)模復(fù)雜干擾資源調(diào)度問題，本文以干擾效益最大化、干擾成本最小化為目標(biāo)，構(gòu)建了資源調(diào)度優(yōu)化模型，并提出一種基于主-從、島嶼混合模型的改進(jìn)并行遺傳算法。主要工作如下：(1)干擾效益從距離、頻段、威脅等級(jí)以及功率壓制比4個(gè)方面進(jìn)行評(píng)價(jià)，干擾成本從資源占用，地理位置和被發(fā)現(xiàn)概率3個(gè)方面進(jìn)行評(píng)價(jià)。(2)為靈活適應(yīng)多無人機(jī)干擾環(huán)境，允許一個(gè)干擾資源最多能干擾K1個(gè)目標(biāo)，一個(gè)目標(biāo)最多可被分配K2個(gè)資源。(3)將資源被分配給某個(gè)目標(biāo)與否建模為0-1規(guī)劃，把某個(gè)目標(biāo)被分配了干擾資源看作一個(gè)任務(wù)，提出最少完成任務(wù)數(shù)的約束，則需非線性約束來描述。與其他模型相比，所提模型的約束更復(fù)雜、對(duì)抗規(guī)模更大，在允許多對(duì)多的場(chǎng)景中保證優(yōu)化調(diào)度方案能完成的最少任務(wù)數(shù)，并對(duì)閑置資源數(shù)量進(jìn)行了限制。(4)針對(duì)中、大規(guī)模情況下，現(xiàn)有算法收斂過慢、耗時(shí)過長的問題，本文提出基于混合模型的改進(jìn)并行遺傳算法，并通過對(duì)比傳統(tǒng)遺傳算法、非支配排序遺傳算法II[20]、修復(fù)遺傳算法[18]、基于島嶼模型的并行遺傳算法[21]和自適應(yīng)模擬退火遺傳禁忌搜索算法[22]，驗(yàn)證在迭代次數(shù)、耗時(shí)、目標(biāo)值方面的性能。

2 干擾資源調(diào)度模型

2.1 干擾資源調(diào)度場(chǎng)景

假設(shè)在復(fù)雜通信場(chǎng)景中，多架無人機(jī)分布在海、陸、空3種地理位置中，由M個(gè)干擾資源和N個(gè)被干擾目標(biāo)組成，每個(gè)干擾資源用序號(hào)i, i∈I={1,2,...,M}表 示，每個(gè)目標(biāo)用序號(hào)j, j∈J={1,2,...,N}表示。具體干擾關(guān)系如圖1所示。其中：單個(gè)干擾資源i最多可以干擾K1(1≤K1≤N)個(gè)目標(biāo)；單個(gè)目標(biāo)j最多可以被K2(1≤K2≤M)個(gè)干擾資源干擾；為了節(jié)約成本，這里限定未被調(diào)用的資源數(shù) 要 大 于 等 于K3M(0≤K3≤1)且 小 于 等 于K4M(0≤K4≤1) ；要 有K5N(0≤K5≤1)以 上 的目標(biāo)被分配有干擾資源，即最少完成任務(wù)數(shù)為K5N。

圖1 干擾關(guān)系

假設(shè)目標(biāo)的相關(guān)參數(shù)已通過偵察手段得到，則可通過分配干擾資源給合適的目標(biāo)來得到干擾效益，同時(shí)支付相應(yīng)的干擾成本。干擾效益和成本可根據(jù)雙方參數(shù)計(jì)算相應(yīng)的評(píng)估指標(biāo)值來確定。其中，目標(biāo)與干擾源通信的信道環(huán)境可根據(jù)實(shí)際場(chǎng)景設(shè)置經(jīng)歷信道衰落。在計(jì)算干擾效益和成本指標(biāo)時(shí)，本文的接收功率和回波功率設(shè)置為空對(duì)空通信環(huán)境[23]中衰落后的功率。干擾效益和干擾成本則通過層次分析法(Analytic Hierarchy Process, AHP)進(jìn)行加權(quán)整合，作為離散組合優(yōu)化問題的目標(biāo)函數(shù)，將雙目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題。2.2節(jié)將介紹干擾資源調(diào)度的評(píng)價(jià)指標(biāo)，2.3節(jié)介紹干擾資源調(diào)度的數(shù)學(xué)模型。

2.2 干擾資源調(diào)度評(píng)價(jià)指標(biāo)

2.2.1 干擾效益評(píng)價(jià)指標(biāo)

(1) 干擾作用距離S1ij

2.3 數(shù)學(xué)模型

其中，K1, K2, K3, K4, K5的定義見2.1節(jié)場(chǎng)景部分，則K3M和K4M分別為未調(diào)用的資源數(shù)的最小值和最大值，以進(jìn)一步約束調(diào)用資源的平均成本；K5N為被分配有干擾資源的最少目標(biāo)數(shù)。

該資源調(diào)度優(yōu)化模型的目標(biāo)函數(shù)為非線性非凸的，約束條件中也含有非線性條件，難以用現(xiàn)有數(shù)學(xué)優(yōu)化方法直接求解。

3 并行遺傳模型求解算法

本文提出基于混合主-從、孤島模型的并行遺傳算法，來求解上述干擾資源調(diào)度問題。

3.1 基于主-從和島嶼模型的混合模型

主-從模式中，主處理器處理交叉變異和選擇操作，隨后把個(gè)體發(fā)送給從處理器。從處理器評(píng)估個(gè)體的適應(yīng)度，且不需要與其他從處理器進(jìn)行信息交流，從處理器之間相互獨(dú)立。

島嶼模型與主-從模型不同之處在于將種群劃分為不同子種群后，各子種群之間獨(dú)立進(jìn)化，只在固定的間隔與周圍子種群進(jìn)行隨機(jī)的信息交流。島嶼模型的優(yōu)點(diǎn)是節(jié)省時(shí)間，提高進(jìn)化算法的全局收斂能力，但存在過早收斂的可能。

混合模型結(jié)構(gòu)如圖2所示，將種群劃分為不同子種群，子種群獨(dú)立進(jìn)化一定次數(shù)后，將各自的最優(yōu)個(gè)體上傳至精英集。精英集將當(dāng)前最優(yōu)個(gè)體與全局最優(yōu)個(gè)體進(jìn)行比較后，更新全局最優(yōu)個(gè)體，并通過信息交換將其發(fā)送給各子種群，繼續(xù)進(jìn)化。

圖2 混合主-從和島嶼模型結(jié)構(gòu)

混合模型結(jié)合了主-從模型可以接收全局信息和島嶼模型提高收斂能力的特點(diǎn)，既增加了種群的多樣性，又減少了過早收斂的可能。

3.2 基于混合模型的并行遺傳算法

使用混合模型的關(guān)鍵是設(shè)置多個(gè)并行的子種群。并行的子種群在信息交流階段之前各自并行進(jìn)行遺傳迭代，減少迭代耗時(shí)；在信息交流階段產(chǎn)生精英集合G，保存全局最優(yōu)個(gè)體的最優(yōu)精英b0。S個(gè)子種群會(huì)在整個(gè)計(jì)算中進(jìn)行多次信息交流。在信息交流階段中，各子種群上傳自己種群中的最優(yōu)個(gè)體gk(k=1,2,...,S)到精英集合中，比較后將當(dāng)前最優(yōu)個(gè)體b1與全局最優(yōu)個(gè)體b0比較，之后更新全局最優(yōu)個(gè)體b0并將其發(fā)送回各子種群，進(jìn)入下一階段信息交流。干擾資源調(diào)度算法步驟如表1所示。

表1 基于混合模型的并行遺傳算法(算法1)

遺傳算法采取整數(shù)編碼，每個(gè)個(gè)體表示為一個(gè)長度為干擾資源總數(shù)的向量，元素序號(hào)表示干擾資源的序號(hào)，向量中每個(gè)元素中的值為該干擾資源被分配的目標(biāo)序號(hào)，若沒有被分配目標(biāo)則默認(rèn)為0。

算法使用≥3個(gè)子種群并行進(jìn)行遺傳進(jìn)化，隨后輸出各子種群的最優(yōu)和最差個(gè)體，再通過信息交換，進(jìn)行精英集更新等操作。

在算法運(yùn)算中，通過多個(gè)子種群同時(shí)進(jìn)行搜索，結(jié)合遺傳交叉和變異操作，算法的搜索空間相對(duì)擴(kuò)大，可以顯著減少算法局部收斂的概率。同時(shí)，算法中的精英集收集和廣播各子種群的最優(yōu)個(gè)體，可以加快算法收斂速度。

4 仿真結(jié)果對(duì)比

假設(shè)干擾方有M個(gè)干擾資源(M默認(rèn)為100)，干擾N個(gè)目標(biāo)(N默認(rèn)為50)，目標(biāo)參數(shù)已通過偵察等手段獲得。干擾約束條件同2.3節(jié)，K1=1，K2=2，K3=0.05，K4=0.5，K5=0.8。經(jīng)多次遺傳算法參數(shù)調(diào)整實(shí)驗(yàn)，并行遺傳算法的交叉概率取0.8，變異概率取0.6，最大迭代次數(shù)為1500[11]，初始種群規(guī)模根據(jù)調(diào)度規(guī)模和子種群數(shù)量進(jìn)行調(diào)整，在中等規(guī)模下初始種群規(guī)模為120。

本文將提出的基于混合模型的并行遺傳算法，與遺傳算法、修復(fù)遺傳算法[18]、非支配排序遺傳算法II[20]、基于島嶼模型的并行遺傳算法[21]和自適應(yīng)模擬退火遺傳禁忌搜索算法[22]進(jìn)行仿真比較。資源與目標(biāo)的空間坐標(biāo)隨機(jī)變量服從均勻分布，包含海、陸、空地理屬性，具體見2.2.2節(jié)干擾成本評(píng)價(jià)指標(biāo)。

圖3為單次中、大規(guī)模資源調(diào)度優(yōu)化的目標(biāo)函數(shù)值迭代趨勢(shì)對(duì)比。其中，修復(fù)遺傳算法在中間每次迭代中沒有及時(shí)修正為滿足多對(duì)一、最少完成任務(wù)數(shù)等多限制條件的可行解，雖具有最高的目標(biāo)函數(shù)值，但迭代結(jié)束后的可行解目標(biāo)函數(shù)值較低。為了便于對(duì)比，圖中在修復(fù)遺傳算法基礎(chǔ)上，增加了每次迭代修復(fù)可行解的目標(biāo)函數(shù)值統(tǒng)計(jì)。

由于本文算法通過3個(gè)子種群并行搜索，加大了可行解的搜索空間，減少了遺傳算法局部收斂的可能性，而混合模型中精英集的引入，能夠提高搜索速度。通過圖3可以看出，本文算法的迭代收斂次數(shù)和收斂后目標(biāo)函數(shù)值的性能。

圖3 中、大規(guī)模資源調(diào)度優(yōu)化目標(biāo)函數(shù)值迭代趨勢(shì)對(duì)比

表2為用改進(jìn)的基于混合模型的并行遺傳算法與其余5種算法進(jìn)行不同規(guī)模下1500次迭代干擾資源調(diào)度優(yōu)化的對(duì)比數(shù)據(jù)，取100次仿真的用時(shí)平均值與最終目標(biāo)函數(shù)值平均值。由于非支配排序遺傳算法II單次迭代運(yùn)算方式與其余算法差異較大且耗時(shí)更長，其最大迭代次數(shù)僅取150。從表中可知提出的基于混合模型的并行遺傳算法在指定迭代次數(shù)和計(jì)算至收斂兩種情況都具有較短的計(jì)算時(shí)間和最高的目標(biāo)函數(shù)值，且隨著規(guī)模不斷增大，優(yōu)勢(shì)越來越明顯。

表2 迭代1500次所用時(shí)間/最終目標(biāo)函數(shù)值對(duì)比(100次仿真平均值)

圖4為判斷收斂后停止計(jì)算的上述算法在100次仿真中用時(shí)平均值和最終目標(biāo)函數(shù)值平均值對(duì)比數(shù)據(jù)，最大迭代次數(shù)取10000次，超出后停止計(jì)算。非支配排序遺傳算法II由于上述原因取150次。時(shí)間方面，修復(fù)遺傳算法雖然計(jì)算時(shí)間快，但沒有在每次迭代后都修復(fù)不可行解，收斂之后再修復(fù)得到的滿足約束條件的可行解的目標(biāo)函數(shù)值并不高。

圖4 算法收斂性能對(duì)比(100次仿真平均)

由于中、大規(guī)模資源調(diào)度問題中，啟發(fā)式算法難以在多項(xiàng)式時(shí)間內(nèi)取得最優(yōu)解，為了對(duì)比各啟發(fā)式算法取得最優(yōu)解的穩(wěn)定性，在小規(guī)模下，通過窮舉法獲得最優(yōu)解，再將各啟發(fā)式算法在同樣的小規(guī)模情況下進(jìn)行仿真實(shí)驗(yàn)。表3為在小規(guī)模(12:6)下，上述算法在100次仿真中達(dá)到最優(yōu)的百分比統(tǒng)計(jì)，最優(yōu)解的取值精度為1位小數(shù)。從表中可知，小規(guī)模的情況下基于混合模型的并行遺傳算法達(dá)到最優(yōu)的次數(shù)最多。

表3 在M=12, N=6規(guī)模下各算法在100次計(jì)算中取得最優(yōu)解次數(shù)的百分比

為進(jìn)一步研究所提算法在不同建模環(huán)境中的優(yōu)化求解性能，本文在上述隨機(jī)分布無人機(jī)干擾源、目標(biāo)位置的基礎(chǔ)上，考慮一種干擾源和目標(biāo)群之間有一定空間界限的場(chǎng)景。圖5為改變后的無人機(jī)干擾源和目標(biāo)3維位置分布圖。其中，最遠(yuǎn)目標(biāo)離干擾源的距離為其信噪比達(dá)到最小可探測(cè)值時(shí)的探測(cè)距離。以中等規(guī)模資源調(diào)度問題為例，本文與5種對(duì)比算法得到的目標(biāo)函數(shù)值迭代趨勢(shì)如圖6所示，可以看出本文算法仍能達(dá)到更優(yōu)的目標(biāo)函數(shù)值。當(dāng)對(duì)抗場(chǎng)景中的資源或目標(biāo)參數(shù)發(fā)生改變時(shí)，亦可將評(píng)估指標(biāo)歸一化，更新效益矩陣E后，使用本文算法優(yōu)化調(diào)度方案。

圖5 干擾資源與目標(biāo)的空間位置

圖6 中規(guī)模資源調(diào)度優(yōu)化的目標(biāo)函數(shù)值迭代趨勢(shì)對(duì)比

5 結(jié)論

本文針對(duì)中、大規(guī)模干擾資源調(diào)度的時(shí)效和綜合效益優(yōu)化問題，構(gòu)建了聯(lián)合優(yōu)化4種干擾效益和3種干擾成本的多目標(biāo)優(yōu)化模型，提出在允許多個(gè)干擾資源干擾單個(gè)目標(biāo)、單個(gè)資源可同時(shí)干擾多個(gè)目標(biāo)等條件下，保證最少完成任務(wù)數(shù)的約束，并提出基于混合模型的帶精英集并行遺傳算法來求解優(yōu)化問題。

仿真結(jié)果表明，與基于島嶼模型的并行遺傳算法、非支配排序遺傳算法II和自適應(yīng)模擬退火遺傳禁忌搜索算法、修復(fù)遺傳算法、經(jīng)典遺傳算法相比，所提算法在中、大規(guī)模下能夠以較好穩(wěn)定性在較短的時(shí)長內(nèi)得到較高的目標(biāo)函數(shù)值。

在其他領(lǐng)域的任務(wù)分配或資源調(diào)度應(yīng)用中，可通過將分配、調(diào)度的對(duì)象處理成資源與目標(biāo)對(duì)應(yīng)關(guān)系，并采用合適的運(yùn)算處理器，根據(jù)規(guī)模調(diào)整并行子種群數(shù)量后，將本文算法進(jìn)行擴(kuò)展應(yīng)用，可提高時(shí)效性。后續(xù)研究將結(jié)合持續(xù)調(diào)度場(chǎng)景，根據(jù)不斷變化的干擾場(chǎng)景，構(gòu)建動(dòng)態(tài)資源調(diào)度模型，引入新興的偵干一體機(jī)，提出偵察干擾雙層資源調(diào)度模型和算法，以適應(yīng)各種規(guī)模資源調(diào)度優(yōu)化。