無人機(jī)集群協(xié)同搜索跟蹤任務(wù)規(guī)劃方法

張曉杰， 鄭紀(jì)彬， 蘇 濤， 劉宏偉， 高 琦

(1. 西安電子科技大學(xué)雷達(dá)信號(hào)處理國家重點(diǎn)實(shí)驗(yàn)室， 陜西西安 710071；2. 陜西長嶺電子科技有限責(zé)任公司， 陜西寶雞 721006)

0 引言

在科學(xué)研究和實(shí)際應(yīng)用中，由于在成本、靈活性和機(jī)動(dòng)性能方面的優(yōu)勢(shì)，無人機(jī)受到了越來越多的關(guān)注。隨著通信與控制技術(shù)的發(fā)展，無人機(jī)集群可以取代單機(jī)無人機(jī)，帶來分工協(xié)作、集群智能化等諸多優(yōu)勢(shì)。無人機(jī)集群規(guī)模較大，需要高效的決策指揮無人機(jī)執(zhí)行任務(wù)。然而，在復(fù)雜動(dòng)態(tài)環(huán)境中，傳統(tǒng)的任務(wù)規(guī)劃方法很難使大規(guī)模無人機(jī)集群發(fā)揮出執(zhí)行任務(wù)的優(yōu)勢(shì)。因此，對(duì)無人機(jī)集群的高效動(dòng)態(tài)任務(wù)規(guī)劃的需求與日俱增。

真實(shí)的戰(zhàn)場(chǎng)環(huán)境普遍具有動(dòng)態(tài)和不確定的特征。目前，分布式優(yōu)化方法的研究已獲得較大進(jìn)展，較多有效方法被提出，可以較好解決真實(shí)戰(zhàn)場(chǎng)環(huán)境的任務(wù)分配問題，然而從無人機(jī)集群的成本和可靠性方面來說，分布式無人機(jī)集群難以在危險(xiǎn)多變的戰(zhàn)場(chǎng)環(huán)境中大規(guī)模部署，且分布式優(yōu)化算法難以求得全局最優(yōu)解。因此，可有效應(yīng)對(duì)動(dòng)態(tài)戰(zhàn)場(chǎng)環(huán)境且能求得全局最優(yōu)解的集中式優(yōu)化算法是較優(yōu)的選擇。

針對(duì)集中式無人機(jī)集群任務(wù)規(guī)劃建模，文獻(xiàn)[10]構(gòu)建了約束滿足問題(Constraint Satisfaction Problem, CSP)模型，文獻(xiàn)[11-12]在CSP基礎(chǔ)上以無人機(jī)集群的執(zhí)行任務(wù)成本、飛行時(shí)間、危險(xiǎn)性和數(shù)量作為目標(biāo)函數(shù)和以傳感器類型、任務(wù)順序和各項(xiàng)時(shí)間等作為約束，構(gòu)建了適合解決靜態(tài)場(chǎng)景下的無人機(jī)集群面對(duì)已知確定目標(biāo)的任務(wù)規(guī)劃模型。第二代非支配排序算法及在其基礎(chǔ)上開發(fā)的算法可以很好地解決CSP。然而，真實(shí)戰(zhàn)場(chǎng)環(huán)境的動(dòng)態(tài)性導(dǎo)致優(yōu)化問題的目標(biāo)函數(shù)和約束具有動(dòng)態(tài)性，CSP模型難以應(yīng)對(duì)動(dòng)態(tài)優(yōu)化問題。為有效應(yīng)對(duì)動(dòng)態(tài)戰(zhàn)場(chǎng)環(huán)境，動(dòng)態(tài)多目標(biāo)優(yōu)化問題(Dynamic Multiobjective Optimization Problems, DMOPs)模型被廣泛研究，該模型適合目標(biāo)函數(shù)隨時(shí)間變化的場(chǎng)景。針對(duì)該模型，較多的動(dòng)態(tài)多目標(biāo)進(jìn)化算法(DMOEA)已經(jīng)被提出，例如，基于多樣性增強(qiáng)、基于種群預(yù)測(cè)和基于記憶機(jī)制等動(dòng)態(tài)多目標(biāo)進(jìn)化算法。然而，DMOPs僅適配目標(biāo)函數(shù)時(shí)變而約束不變的動(dòng)態(tài)場(chǎng)景優(yōu)化問題，無法適應(yīng)于動(dòng)態(tài)約束的情況。文獻(xiàn)[25]構(gòu)建了動(dòng)態(tài)約束多目標(biāo)優(yōu)化問題(Dynamic Constrained Multiobjective Optimization Problems, DCMOPs)模型,并提出了動(dòng)態(tài)約束多目標(biāo)進(jìn)化算法(Dynamic Constrained MOEA, DC-MOEA)。該模型的目標(biāo)函數(shù)和約束都具有時(shí)變性，在有效應(yīng)對(duì)時(shí)變目標(biāo)函數(shù)的基礎(chǔ)上，所提算法引入了自適應(yīng)懲罰函數(shù)機(jī)制，合理利用有價(jià)值的不可行個(gè)體，得以應(yīng)對(duì)動(dòng)態(tài)約束導(dǎo)致的個(gè)體進(jìn)入不可行區(qū)域的問題，從而加快種群收斂并求得最優(yōu)解。

然而，動(dòng)態(tài)環(huán)境發(fā)生變化還會(huì)導(dǎo)致數(shù)量的改變，這是更為棘手的難題。目標(biāo)函數(shù)數(shù)量的變化將會(huì)改變目標(biāo)函數(shù)域的維度，進(jìn)而使帕累托前沿面發(fā)生擴(kuò)張或收縮，上述動(dòng)態(tài)優(yōu)化算法很難處理此種類型變化。針對(duì)該問題，文獻(xiàn)[26]構(gòu)建了目標(biāo)函數(shù)數(shù)量可變的動(dòng)態(tài)多目標(biāo)優(yōu)化問題模型，該模型可較好地匹配目標(biāo)函數(shù)數(shù)量發(fā)生變化的優(yōu)化問題，提出的動(dòng)態(tài)雙檔案進(jìn)化算法(Dynamic Two-Archive EA, DTAEA)在目標(biāo)函數(shù)發(fā)生變化時(shí)，可重新構(gòu)建收斂性種群和多樣性種群，適應(yīng)目標(biāo)域的維度變化，同時(shí)維持加速種群收斂。相關(guān)研究證明該算法也可同時(shí)應(yīng)對(duì)時(shí)變目標(biāo)函數(shù)的問題。然而，該算法僅能有效應(yīng)對(duì)目標(biāo)函數(shù)的動(dòng)態(tài)變化，未考慮約束時(shí)變和數(shù)量動(dòng)態(tài)變化對(duì)求解優(yōu)化問題的影響，導(dǎo)致在環(huán)境發(fā)生動(dòng)態(tài)變化時(shí)，大量先前可行解進(jìn)入不可行區(qū)域，可行解不足，影響優(yōu)化問題求解速度。

針對(duì)以上問題，為有效應(yīng)對(duì)無人機(jī)集群協(xié)同搜索跟蹤的動(dòng)態(tài)場(chǎng)景，本文構(gòu)建了動(dòng)態(tài)多約束多目標(biāo)優(yōu)化問題(Dynamic Multiconstraint Multiobjective Optimization Problems, DMCM-OPs)，該模型適用于目標(biāo)函數(shù)與約束的數(shù)量動(dòng)態(tài)變化且時(shí)變的復(fù)雜場(chǎng)景。為有效求解DMCMOPs，本文提出了基于動(dòng)態(tài)自適應(yīng)懲罰的動(dòng)態(tài)約束雙檔案進(jìn)化算法(Dynamic Constraint Two-Archive EA, DCTAEA)，該算法同時(shí)維持兩個(gè)種群，平衡種群多樣性和收斂性，同時(shí)，在收斂性種群更新時(shí)引入自適應(yīng)懲罰函數(shù)機(jī)制，整合不可行個(gè)體的目標(biāo)函數(shù)值和違反約束的懲罰值獲得修正目標(biāo)函數(shù)值，并作為不可行個(gè)體的選擇依據(jù)。根據(jù)可行個(gè)體所占比率動(dòng)態(tài)調(diào)整不可行解的約束違反值和目標(biāo)函數(shù)值在修正的目標(biāo)函數(shù)值中所占比重，使得有價(jià)值不可行個(gè)體獲得競爭機(jī)會(huì)，促使種群進(jìn)入可行區(qū)域并向帕累托前沿面收斂。仿真結(jié)果證明，相比第二代非支配排序遺傳算法(NSGA-II)的動(dòng)態(tài)版本、基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)、約束雙檔案進(jìn)化算法(CTAEA)和動(dòng)態(tài)雙檔案進(jìn)化算法(DTAEA)，本文所提算法能更加有效地解決動(dòng)態(tài)多約束多目標(biāo)優(yōu)化問題，實(shí)現(xiàn)動(dòng)態(tài)環(huán)境下的無人機(jī)集群高效任務(wù)規(guī)劃。

1 物理場(chǎng)景描述

1.1 無人機(jī)描述

考慮到戰(zhàn)場(chǎng)環(huán)境的復(fù)雜性和危險(xiǎn)性，以及無人機(jī)負(fù)載重量和自身攜帶的電池能量的限制，無人機(jī)裝備被動(dòng)偵察系統(tǒng)，采用測(cè)向交叉定位方式對(duì)目標(biāo)進(jìn)行定位。無人機(jī)搜索編隊(duì)由兩架無人機(jī)組成，通過被動(dòng)測(cè)向交叉定位方法粗略地確定目標(biāo)位置，如圖1(a)所示。搜索編隊(duì)的有效探測(cè)范圍可以看作半徑為的圓，如圖1(b)所示，在此范圍內(nèi)的目標(biāo)可以被無人機(jī)搜索編隊(duì)發(fā)現(xiàn)。為了簡化場(chǎng)景模型，我們把搜索編隊(duì)的有效探測(cè)范圍視為半徑為的圓的內(nèi)接正方形。此外，目標(biāo)跟蹤需要更精確的定位精度，且面臨危險(xiǎn)性變高，設(shè)置無人機(jī)跟蹤編隊(duì)由4架無人機(jī)組成，如圖2所示。

(a) 搜索編隊(duì)交叉定位示意圖 (b) 無人機(jī)編隊(duì)探測(cè)范圍示意圖圖1 無人機(jī)編隊(duì)定位示意圖

圖2 跟蹤編隊(duì)交叉定位示意圖

為方便無人機(jī)集群協(xié)同搜索跟蹤任務(wù)規(guī)劃方法設(shè)計(jì)，本文作出以下假設(shè)：

1) 集群中無人機(jī)是同構(gòu)的并且每架無人機(jī)都能通過編隊(duì)執(zhí)行搜索和跟蹤任務(wù)；

2) 無人機(jī)能以固定速度飛行或盤旋在空中，飛行和盤旋狀態(tài)可以在可忽略的極短時(shí)間內(nèi)轉(zhuǎn)換，且具有相同飛行自持力；

3) 中央控制站覆蓋的通信覆蓋范圍以及與無人機(jī)集群的通信帶寬可以滿足任務(wù)要求；

4) 在無人機(jī)搜索或跟蹤編隊(duì)到達(dá)某個(gè)有效探測(cè)范圍的中心，并懸停一定時(shí)間，則表示對(duì)該范圍內(nèi)的目標(biāo)進(jìn)行有效搜索和跟蹤任務(wù)。

1.2 離散任務(wù)區(qū)域描述

真實(shí)戰(zhàn)場(chǎng)環(huán)境為三維空間區(qū)域，但是無人機(jī)的運(yùn)動(dòng)可以解耦為二維平面和垂直方向上的運(yùn)動(dòng)。因此，本文使用水平方向的二維平面來描述戰(zhàn)場(chǎng)環(huán)境。任務(wù)區(qū)域被建模為由*=個(gè)正方形網(wǎng)格區(qū)域構(gòu)成的戰(zhàn)場(chǎng)整體，戰(zhàn)場(chǎng)環(huán)境網(wǎng)格化如圖3所示。每個(gè)正方形網(wǎng)格區(qū)域代表無人機(jī)搜索跟蹤編隊(duì)的有效探測(cè)范圍。因此，有個(gè)搜索任務(wù)要執(zhí)行。無人機(jī)的運(yùn)動(dòng)可以視為網(wǎng)格離散中心之間的運(yùn)動(dòng)。

圖3 戰(zhàn)場(chǎng)離散網(wǎng)格區(qū)域及其初始化威脅示意圖

由回報(bào)函數(shù)的啟發(fā)，本文提出威脅度函數(shù)的概念。在無人機(jī)集群執(zhí)行任務(wù)前，預(yù)警機(jī)或衛(wèi)星可以提供戰(zhàn)場(chǎng)的先驗(yàn)信息，根據(jù)先驗(yàn)信息，計(jì)算出每個(gè)網(wǎng)格區(qū)域的初始威脅度和威脅度變化函數(shù)。網(wǎng)格區(qū)域的顏色越深代表該網(wǎng)格區(qū)域威脅值越大。

戰(zhàn)場(chǎng)網(wǎng)格區(qū)域在時(shí)刻的威脅函數(shù)和所有網(wǎng)格在時(shí)刻總威脅值函數(shù)表達(dá)式分別為

(1)

(2)

(3)

式中，表示目標(biāo)的威脅值的初始化因子，表示目標(biāo)的威脅等級(jí)相關(guān)參數(shù)，表示跟蹤編隊(duì)對(duì)目標(biāo)建立跟蹤后該目標(biāo)的常數(shù)威脅值。圖4表示網(wǎng)格區(qū)域和發(fā)現(xiàn)目標(biāo)威脅度隨時(shí)間的變化情況。其中藍(lán)色線條表示某網(wǎng)格區(qū)域在第60 s被無人機(jī)搜索編隊(duì)搜索完畢，根據(jù)公式(2)，該區(qū)域的威脅值降低，而隨著搜索編隊(duì)離開，威脅值上升。紅色線條表示在70 s時(shí)刻發(fā)現(xiàn)的目標(biāo)并在90 s時(shí)刻跟蹤編隊(duì)開始對(duì)該目標(biāo)進(jìn)行跟蹤的威脅值變化情況。

圖4 網(wǎng)格區(qū)域和目標(biāo)威脅度隨時(shí)間變化示意圖

1.3 協(xié)同搜索跟蹤規(guī)劃描述

戰(zhàn)場(chǎng)場(chǎng)景時(shí)刻發(fā)生動(dòng)態(tài)變化，戰(zhàn)場(chǎng)場(chǎng)景所構(gòu)建的戰(zhàn)場(chǎng)離散網(wǎng)格區(qū)域威脅值函數(shù)是時(shí)變的，無人機(jī)集群在執(zhí)行戰(zhàn)場(chǎng)覆蓋搜索任務(wù)的過程中隨時(shí)會(huì)發(fā)現(xiàn)不可預(yù)測(cè)的目標(biāo)，使無人機(jī)集群的任務(wù)性質(zhì)發(fā)生改變。由下述2.2、2.3和2.4節(jié)可知，上述兩大動(dòng)態(tài)變化因素，導(dǎo)致任務(wù)規(guī)劃問題的目標(biāo)函數(shù)和約束發(fā)生動(dòng)態(tài)變化，進(jìn)而使得已求得的任務(wù)規(guī)劃方案在動(dòng)態(tài)變化后的場(chǎng)景中不再是最優(yōu)解，無人機(jī)集群不能高效執(zhí)行任務(wù)。

針對(duì)上述問題，本文提出了無人機(jī)集群協(xié)同跟蹤搜索任務(wù)規(guī)劃方法，流程圖如圖5所示。無人機(jī)集群按照初始任務(wù)規(guī)劃方案執(zhí)行戰(zhàn)場(chǎng)覆蓋搜索任務(wù)，一旦戰(zhàn)場(chǎng)環(huán)境發(fā)生變化，則需要求解新的任務(wù)規(guī)劃方案。該方法的難點(diǎn)在于建立符合真實(shí)戰(zhàn)場(chǎng)環(huán)境的動(dòng)態(tài)任務(wù)規(guī)劃問題模型，以及快速求解最優(yōu)任務(wù)規(guī)劃方案。因此，下文將對(duì)符合戰(zhàn)場(chǎng)要求的復(fù)雜動(dòng)態(tài)優(yōu)化問題模型和動(dòng)態(tài)優(yōu)化問題求解算法展開研究。

圖5 協(xié)同搜索跟蹤規(guī)劃流程圖

2 協(xié)同搜索跟蹤任務(wù)規(guī)劃模型

真實(shí)的戰(zhàn)場(chǎng)環(huán)境普遍具有動(dòng)態(tài)和不確定的特征，時(shí)刻變化的網(wǎng)格區(qū)域威脅值函數(shù)和發(fā)現(xiàn)的威脅目標(biāo)導(dǎo)致構(gòu)建的任務(wù)規(guī)劃優(yōu)化問題模型的目標(biāo)函數(shù)和約束時(shí)變且數(shù)量變化。然而，CSP、DMOPs、DCMOPs和目標(biāo)函數(shù)可變的動(dòng)態(tài)多目標(biāo)優(yōu)化問題等模型不適用于目標(biāo)函數(shù)和約束時(shí)變且數(shù)量變化的復(fù)雜場(chǎng)景。對(duì)此，本節(jié)構(gòu)建了DMCMOPs模型，可以有效應(yīng)對(duì)動(dòng)態(tài)戰(zhàn)場(chǎng)環(huán)境任務(wù)規(guī)劃所面臨的目標(biāo)函數(shù)與約束時(shí)變且數(shù)量變化的難題。下文將詳細(xì)闡述構(gòu)成該優(yōu)化問題模型的決策變量、目標(biāo)函數(shù)和約束。

2.1 任務(wù)規(guī)劃問題的決策變量

決策變量是優(yōu)化問題中與目標(biāo)函數(shù)和約束有關(guān)的變量。在無人機(jī)集群協(xié)同搜索跟蹤任務(wù)規(guī)劃問題中，決策變量決定了無人機(jī)編隊(duì)執(zhí)行哪些任務(wù)和執(zhí)行任務(wù)的順序，而決策變量的變化影響了任務(wù)規(guī)劃方案的優(yōu)劣。本文提取的兩個(gè)決策變量如下所示：

1) 任務(wù)分配變量：以兩架無人機(jī)組成的搜索無人機(jī)編隊(duì)作為基本單位，此變量表示為*維的二進(jìn)制矩陣。當(dāng)且僅當(dāng)分配向量[,]=1時(shí)，任務(wù)被分配給了無人機(jī)編隊(duì)。

2) 任務(wù)執(zhí)行順序變量：定義了每個(gè)無人機(jī)編隊(duì)執(zhí)行所分配任務(wù)的順序。如果集合{1,2,3,4}是分配給編隊(duì)執(zhí)行的任務(wù)，則定義Γ={1,3,4,2}表示編隊(duì)執(zhí)行任務(wù)集合{1,2,3,4}的順序。

2.2 規(guī)劃問題的目標(biāo)函數(shù)

最優(yōu)規(guī)劃方案通過同時(shí)優(yōu)化一組相互沖突的目標(biāo)函數(shù)構(gòu)成的帕累托最優(yōu)解驅(qū)動(dòng)。復(fù)雜優(yōu)化問題的目標(biāo)函數(shù)不是唯一的，根據(jù)無人機(jī)集群協(xié)同搜索任務(wù)規(guī)劃問題設(shè)置3個(gè)評(píng)價(jià)任務(wù)規(guī)劃方案優(yōu)劣的目標(biāo)函數(shù)。

1) 戰(zhàn)場(chǎng)所有網(wǎng)格區(qū)域在任務(wù)規(guī)劃執(zhí)行期間的最小威脅值定義為

(4)

式中，和分別為執(zhí)行任務(wù)規(guī)劃起始時(shí)刻和結(jié)束時(shí)刻。

2) 最短飛行時(shí)間 規(guī)劃執(zhí)行結(jié)束的無人機(jī)最短飛行時(shí)間：

min

(5)

3) 最短建立跟蹤時(shí)間 從發(fā)現(xiàn)目標(biāo)到對(duì)該目標(biāo)建立跟蹤的最短時(shí)間：

(6)

2.3 規(guī)劃問題的約束

約束是從現(xiàn)實(shí)問題提取的必須滿足的條件，同時(shí)也決定了任務(wù)規(guī)劃方案是否可行。根據(jù)實(shí)際問題，本文提取了4個(gè)戰(zhàn)場(chǎng)和無人機(jī)約束條件。

1) 避免碰撞約束 考慮無人機(jī)編隊(duì)之間的安全距離以避免編隊(duì)之間相互碰撞，編隊(duì)內(nèi)的無人機(jī)相互之間可視為始終保持安全距離：

()>,=1,…,;≠

(7)

2) 威脅值約束 常數(shù),max表示所能接受的網(wǎng)格區(qū)域威脅值上限要求：

(,)≤,max,∈

(8)

3) 飛行時(shí)間約束 無人機(jī)滿足執(zhí)行完任務(wù)安全返回的飛行時(shí)間限制：

(9)

4) 已發(fā)現(xiàn)的目標(biāo)威脅值約束 常數(shù)表示所能容忍的已發(fā)現(xiàn)的目標(biāo)的威脅值上限。目標(biāo)在時(shí)刻的威脅值(,)應(yīng)小于常數(shù)，公式表示如下：

(,)≤,∈

(10)

2.4 搜索跟蹤動(dòng)態(tài)任務(wù)規(guī)劃問題數(shù)學(xué)表征

根據(jù)1節(jié)和2節(jié)所述，在發(fā)現(xiàn)目標(biāo)前，無人機(jī)集群需要對(duì)戰(zhàn)場(chǎng)網(wǎng)格區(qū)域進(jìn)行戰(zhàn)場(chǎng)覆蓋式搜索，此時(shí)建立的優(yōu)化問題數(shù)學(xué)表征：

min

s.t.()>,=1,…,;≠

,≤,max,∈

(11)

一旦無人機(jī)集群搜索編隊(duì)發(fā)現(xiàn)目標(biāo)，則無人機(jī)集群的任務(wù)性質(zhì)發(fā)生變化，即從純粹的戰(zhàn)場(chǎng)覆蓋式搜索轉(zhuǎn)為在戰(zhàn)場(chǎng)覆蓋式搜索和對(duì)已發(fā)現(xiàn)目標(biāo)進(jìn)行精確跟蹤。無人機(jī)集群任務(wù)性質(zhì)的轉(zhuǎn)變導(dǎo)致優(yōu)化問題數(shù)學(xué)表征動(dòng)態(tài)調(diào)整。無人機(jī)集群協(xié)同搜索跟蹤任務(wù)規(guī)劃的優(yōu)化問題數(shù)學(xué)表征為

min

s.t. d()>,=1,…,;≠

,≤,max,∈

target,≤,∈

(12)

相較于單純的搜索任務(wù)規(guī)劃優(yōu)化問題數(shù)學(xué)表征式(11)，優(yōu)化問題數(shù)學(xué)表征式(12)增加了目標(biāo)函數(shù)公式(6)與約束函數(shù)式(10)。其中目標(biāo)函數(shù)式(6)目的在于促使無人機(jī)集群盡快對(duì)已發(fā)現(xiàn)的目標(biāo)建立跟蹤，約束式(10)可以將已發(fā)現(xiàn)目標(biāo)的威脅值限定在安全范圍內(nèi)。由公式(11)到公式(12)的變化本質(zhì)是DMCMOPs，如下式所示：

min(,)=((,),…,(,),…,()(,))

(13)

式中(,)和(,)分別為等式約束和不等式約束，()表示目標(biāo)函數(shù)的數(shù)量，()和()表示等式約束和不等式約束的數(shù)量。

相比CSP、DMOPs、DCMOPs和目標(biāo)函數(shù)可變的動(dòng)態(tài)多目標(biāo)優(yōu)化問題模型，公式(13)構(gòu)建的DMCMOPs模型目標(biāo)函數(shù)和約束發(fā)生時(shí)變且數(shù)量變化。然而，現(xiàn)有算法解決DMCMOP時(shí)存在難以應(yīng)對(duì)該模型的復(fù)雜動(dòng)態(tài)變化的難題，對(duì)此，下一節(jié)將提出一種針對(duì)目標(biāo)函數(shù)和約束發(fā)生時(shí)變且數(shù)量變化的優(yōu)化問題的動(dòng)態(tài)優(yōu)化算法。

3 動(dòng)態(tài)約束雙檔案進(jìn)化算法

DMCMOPs模型的目標(biāo)函數(shù)和約束具有時(shí)變且數(shù)量變化的動(dòng)態(tài)特征，針對(duì)目標(biāo)函數(shù)的動(dòng)態(tài)變化，文獻(xiàn)[26]提出了DTAEA，然而該方法很難同時(shí)應(yīng)對(duì)目標(biāo)函數(shù)和約束的動(dòng)態(tài)變化。目標(biāo)函數(shù)和約束同時(shí)發(fā)生動(dòng)態(tài)變化時(shí)，不僅會(huì)導(dǎo)致目標(biāo)函數(shù)域維度和種群收斂性、多樣性的變化，還會(huì)使大量種群個(gè)體落入不可行區(qū)域，導(dǎo)致可行個(gè)體數(shù)量不足，影響種群收斂。本節(jié)針對(duì)DMCMOPs模型求解難題，提出了一種基于動(dòng)態(tài)自適應(yīng)懲罰機(jī)制的動(dòng)態(tài)雙檔案進(jìn)化算法(DCTAEA)，該算法核心部分在于維護(hù)兩個(gè)相互協(xié)作檔案，即CA和DA，CA起主要作用，在CA更新過程中，當(dāng)可行性個(gè)體不足時(shí)，通過引入的動(dòng)態(tài)自適應(yīng)懲罰機(jī)制整合不可行個(gè)體的目標(biāo)函數(shù)值和違反約束的懲罰值獲得修正目標(biāo)函數(shù)值，根據(jù)可行個(gè)體所占比率動(dòng)態(tài)調(diào)整不可行解的約束違反值和目標(biāo)函數(shù)值在修正的目標(biāo)函數(shù)值中所占比重，使得有價(jià)值不可行個(gè)體獲得競爭機(jī)會(huì)，促使種群進(jìn)入可行區(qū)域并向帕累托前沿面收斂；DA增強(qiáng)種群多樣性，更新過程中探索CA未開發(fā)區(qū)域。算法流程圖如圖6所示，當(dāng)環(huán)境發(fā)生變化時(shí)，CA和DA重新構(gòu)建種群，改變目標(biāo)域的維度，使得種群更快地適應(yīng)新環(huán)境。環(huán)境未發(fā)生改變時(shí)，直接產(chǎn)生CA和DA子代種群，CA和DA在每次迭代過程中更新各自種群。重復(fù)上述過程直到種群收斂獲得最優(yōu)解。

圖6 DCTAEA流程圖

在公式(13)所示的優(yōu)化問題模型中，目標(biāo)函數(shù)發(fā)生動(dòng)態(tài)變化，導(dǎo)致目標(biāo)函數(shù)域的維度改變，采用文獻(xiàn)[26，32]的方法重構(gòu)種群，改變目標(biāo)域維度，加快適應(yīng)新環(huán)境。重構(gòu)的CA和DA產(chǎn)生子代種群后通過迭代更新使種群收斂， CA和DA的側(cè)重點(diǎn)不同。因此本節(jié)將分別闡述CA和DA的更新方法。

3.1 CA的更新方法

DTAEA很難應(yīng)對(duì)DMCMOPs模型的約束發(fā)生動(dòng)態(tài)變化導(dǎo)致的大量種群個(gè)體落入不可行區(qū)域的問題?？尚袀€(gè)體數(shù)量的不足影響了種群的進(jìn)化，本小節(jié)在DTAEA的CA更新方法中引入動(dòng)態(tài)自適應(yīng)懲罰機(jī)制，整合不可行個(gè)體的目標(biāo)函數(shù)值和違反約束的懲罰值獲得修正的目標(biāo)函數(shù)值，并作為不可行個(gè)體的選擇依據(jù)，充分利用有價(jià)值的不可行個(gè)體，促使種群進(jìn)入可行區(qū)域并向帕累托前沿面收斂。

CA和子代種群的個(gè)體數(shù)量都為，結(jié)合形成個(gè)體數(shù)量為2*的種群。由于DMCMOPs模型約束的動(dòng)態(tài)變化，導(dǎo)致部分動(dòng)態(tài)變化前的可行解變?yōu)椴豢尚薪?，CA種群部分個(gè)體進(jìn)入不可行區(qū)域，中可行個(gè)體的集合記為種群，此時(shí)數(shù)量往往小于，可行個(gè)體數(shù)量的不足嚴(yán)重影響CA的收斂。針對(duì)約束動(dòng)態(tài)變化導(dǎo)致可行個(gè)體數(shù)量的不足影響種群收斂的問題，本小節(jié)在CA的更新中引入動(dòng)態(tài)自適應(yīng)懲罰機(jī)制，通過自適應(yīng)整合歸一化目標(biāo)函數(shù)和歸一化約束違反值獲得不可行解的修正目標(biāo)函數(shù)。動(dòng)態(tài)自適應(yīng)懲罰機(jī)制取決于解的價(jià)值(即該解的目標(biāo)函數(shù)值和約束違反值的大小)和種群中可行性解的比率。種群中可行性解的比率較低時(shí)，不可行解的約束違反值所占權(quán)重較大，約束違反值對(duì)不可行解的選擇起較大作用。種群中可行性解的比率較高時(shí)，則目標(biāo)函數(shù)值對(duì)不可行解的選擇起較大作用。在DMCMOPs發(fā)生動(dòng)態(tài)變化時(shí)，自適應(yīng)懲罰機(jī)制為具有小目標(biāo)函數(shù)值和小約束違反值的有價(jià)值解提供較大參與進(jìn)化競爭的可能性，進(jìn)而充分利用可行解和有價(jià)值的不可行解共同探索最優(yōu)解。

不可行解的第維度歸一化修正目標(biāo)函數(shù)值如下式所示：

(14)

其中，第維目標(biāo)函數(shù)的自適應(yīng)懲罰值為

(15)

(16)

式中，(,)和(,)分別為不等式約束和等式約束的約束違反值。

為了挑選有價(jià)值的不可行解，需要建立優(yōu)化問題作為選擇標(biāo)準(zhǔn)。依據(jù)不可行個(gè)體的歸一化約束違反值和切比雪夫分解函數(shù)值建立二維目標(biāo)優(yōu)化問題如下式：

(17)

式中，

-penalty(()|(),())=

(18)

優(yōu)化問題的目標(biāo)函數(shù)和約束發(fā)生動(dòng)態(tài)變化后，隨著CA的更新次數(shù)增加，中可行個(gè)體數(shù)量也隨之增加，可行個(gè)體數(shù)量不再小于。如果CA更新時(shí)中個(gè)體數(shù)量等于則CA更新完畢，如果中個(gè)體數(shù)量大于，參照文獻(xiàn)[25,30]，執(zhí)行以下操作。

根據(jù)文獻(xiàn)[26,33]生成一組均勻分布的權(quán)重向量()，如下式所示：

()={(),…,()()}

(19)

權(quán)重向量()將目標(biāo)空間劃分為()個(gè)子空間。圖7表示二維目標(biāo)函數(shù)空間的子空間劃分和CA個(gè)體的分布示意圖。圖中CA (圖7黃色個(gè)體)和子代種群(圖7紅色個(gè)體) 組成種群，在可行空區(qū)域的個(gè)體集合組成種群。每個(gè)子空間由唯一的權(quán)重向量代表，子空間Δ(),∈{1,…,()}如下式所示：

Δ()={(,)∈R()|〈(,),〉≤〈(,),〉}

(20)

式中，∈{1,…,()}，〈(,),()〉表示(,)與和原點(diǎn)之間連線的垂直距離。

圖7 二維目標(biāo)函數(shù)空間的子空間劃分和CA個(gè)體的分布示意圖

CA和子代的所有個(gè)體按照子空間分區(qū)，個(gè)體與唯一的子區(qū)域相關(guān)聯(lián)，其所在的子區(qū)域?yàn)?/p>

(21)

(,)=((,),…,()(,))

(22)

并且，

(23)

式中，()為目標(biāo)域各維度估計(jì)的最小值，表示如下：

(24)

式中，

(25)

()為目標(biāo)域各維度的最大值，表示如下：

(26)

式中，

(27)

計(jì)算每個(gè)子空間的個(gè)體密度。根據(jù)公式(19)～(21) 計(jì)算出子空間存在的可行個(gè)體數(shù)量，得到個(gè)體密度最大的子空間Δ。個(gè)體之間的相互距離越近，擁擠度越大，種群的多樣性也越差。為了提高種群多樣性，需要從密度最高子空間中選出相互距離最近的個(gè)體集合。計(jì)算子空間Δ里個(gè)體之間的相互距離：

(28)

相互距離最小的個(gè)體存入中，下一步根據(jù)切比雪夫分解方法計(jì)算最劣個(gè)體并舍棄直至種群個(gè)體數(shù)量等于。最劣個(gè)體表示如下：

(29)

其中，

(()|(),())=

(30)

優(yōu)化問題的目標(biāo)函數(shù)和約束發(fā)生動(dòng)態(tài)變化后，可行解的數(shù)量不足，影響種群收斂。引入動(dòng)態(tài)自適應(yīng)懲罰機(jī)制，充分利用了有價(jià)值的具有合適目標(biāo)函數(shù)值和低約束違反值的解，促進(jìn)不可行解向可行區(qū)域移動(dòng)，加速CA種群收斂。

3.2 DA的更新方法

DA作為CA的輔助角色，不考慮約束導(dǎo)致的個(gè)體是否可行。DA 的作用是探索 CA 尚未開發(fā)空間，提高了可行區(qū)域內(nèi) CA 的種群多樣性，并且有助于跳過局部最優(yōu)或局部不可行區(qū)域。本小節(jié)參照文獻(xiàn)[26，30], 給出DA的更新步驟。

同CA的更新機(jī)制類似，首先將DA與子代種群結(jié)合組成種群，然后依次探索每個(gè)子空間，找到最優(yōu)個(gè)體。最優(yōu)個(gè)體定義為：將更新的CA作為參考集，在第(1≤≤)次迭代中，如果子空間Δ已經(jīng)存在個(gè)及以上的CA個(gè)體或中沒有與當(dāng)前正在研究的子空間相關(guān)的解，則在此迭代期間不再探索該子空間并直接移動(dòng)到下一個(gè)子空間。否則，將選擇與當(dāng)前探索的子空間相關(guān)的中的最佳非支配解，將其視為在新形成的 DA 中的一員。其中，當(dāng)前子空間的最佳解定義為

(31)

圖8表示DA更新過程中的目標(biāo)域空間CA和DA的父代子代個(gè)體分布。其中黃色和紅色個(gè)體分別為DA種群的父代和子代，黑色方塊代表CA種群的個(gè)體。在第一次迭代期間，空間Δ到Δ和Δ都存在CA個(gè)體，所以直接跳過，對(duì)空間Δ，依據(jù)公式(23)，選擇個(gè)體7作為最優(yōu)解劃入CA。在第二次迭代期間，空間Δ存在CA的兩個(gè)個(gè)體，所以依然跳過該空間，其余空間分別選擇個(gè)體3,5,10,8作為最優(yōu)個(gè)體劃入DA。此時(shí)DA數(shù)量種群達(dá)到要求，DA更新完畢。

圖8 二維目標(biāo)函數(shù)空間的子空間劃分和CA及DA個(gè)體的分布示意圖

以上是本文所提DCTAEA，本文算法針對(duì)目標(biāo)函數(shù)和約束的動(dòng)態(tài)變化，通過重建CA和DA種群，增加種群多樣性，快速適應(yīng)新的環(huán)境。在CA的更新過程中引入動(dòng)態(tài)自適應(yīng)懲罰機(jī)制，整合不可行個(gè)體的目標(biāo)函數(shù)值和違反約束的懲罰者獲得修正的目標(biāo)函數(shù)值，充分利用有價(jià)值的不可行個(gè)體，促使不可行個(gè)體向可行區(qū)域移動(dòng)，有利于加快CA收斂，解決了動(dòng)態(tài)約束導(dǎo)致的種群可行個(gè)體不足導(dǎo)致的種群難以收斂問題。DA在更新時(shí)輔助增強(qiáng)多樣性，探索CA未開發(fā)的空間，有助于獲得最優(yōu)解。

4 實(shí)驗(yàn)設(shè)置與結(jié)果分析

本文所提算法在解決目標(biāo)函數(shù)和約束時(shí)變且數(shù)量變化的優(yōu)化問題能更快適應(yīng)動(dòng)態(tài)變化，加快種群收斂，獲得Pareto前沿面。在發(fā)生目標(biāo)函數(shù)和約束的動(dòng)態(tài)變化時(shí)，通過CA和DA種群重建增強(qiáng)多樣性。在CA的更新過程中，引入動(dòng)態(tài)自適應(yīng)懲罰機(jī)制，整合不可行個(gè)體的目標(biāo)函數(shù)值和違反約束的懲罰者獲得修正的目標(biāo)函數(shù)值，充分利用有價(jià)值的不可行個(gè)體，促使不可行個(gè)體向可行區(qū)域移動(dòng)，有利于加快種群收斂，求得最優(yōu)解。本文通過比較所提算法與4種對(duì)比算法求解基準(zhǔn)測(cè)試問題的結(jié)果對(duì)比證明了所提算法的有效性和優(yōu)越性。本節(jié)將介紹基準(zhǔn)測(cè)試問題、性能指標(biāo)以及仿真結(jié)果對(duì)比分析。

4.1 基準(zhǔn)測(cè)試問題

為了測(cè)試所提算法的有效性和優(yōu)越性，選取了類型Ⅱ約束測(cè)試問題C2-DTLZ2的約束和F2型動(dòng)態(tài)多目標(biāo)函數(shù)測(cè)試問題結(jié)合組成的基準(zhǔn)測(cè)試問題DC2-F2，該測(cè)試問題同實(shí)際問題相似。其中，類型Ⅱ約束表示如下：

()]}

(32)

F2目標(biāo)函數(shù)表示如下：

(sin(()-+1π2))()=(1+)sin(π2)

(33)

式中，()表示約束和目標(biāo)函數(shù)在時(shí)刻的數(shù)量。

4.2 性能指標(biāo)

在本小節(jié)中，介紹了反向世代距離(IGD)，和平均反向世代距離(MIGD)，可以同時(shí)衡量算法所得的Pareto最優(yōu)解集的收斂性和多樣性。

(34)

由公式(34)可知，所得Pareto最優(yōu)前沿的IGD值越小，該解集越靠近真實(shí)前沿、分布越均勻。

4.3 仿真結(jié)果分析

為了驗(yàn)證本文提出的DCTAEA針對(duì)DMCMOPs的有效性和優(yōu)越性，將DCTAEA與以下4種優(yōu)化算法進(jìn)行對(duì)比：

1) NSGA-II：第二代非支配排序遺傳算法；

2) MOEA/D：一種基于分解的多目標(biāo)進(jìn)化算法；

3) CTAEA：用于約束多目標(biāo)優(yōu)化的雙檔案進(jìn)化算法；

4) D-TAEA：動(dòng)態(tài)雙檔案進(jìn)化算法。

考慮DMCMOPs面臨的主要問題為目標(biāo)函數(shù)和約束的時(shí)變和數(shù)量變化問題，而時(shí)變性已在公式(32)～(33)體現(xiàn)，只需設(shè)置目標(biāo)函數(shù)和約束數(shù)量()的變化：

(35)

上式表示優(yōu)化問題以=1時(shí)刻為初始，種群經(jīng)過300次的迭代進(jìn)化后，依次經(jīng)歷4次動(dòng)態(tài)變化。動(dòng)態(tài)變化的頻率由參數(shù)決定，=25表示種群每進(jìn)化25代，環(huán)境發(fā)生一次動(dòng)態(tài)變化。設(shè)置種群的個(gè)體數(shù)量為300，每個(gè)算法獨(dú)立運(yùn)行31次，求得反向時(shí)代距離的平均值，獲得種群在整個(gè)動(dòng)態(tài)變化過程中的IGD軌跡。

本文提出的DCTAEA及其4種對(duì)比算法在=25時(shí)求解DMCMOPs獲得IGD軌跡如圖9所示。從圖中可以看出，本文所提算法DCTAEA 在大部分時(shí)間都顯示出最佳性能，能在每次動(dòng)態(tài)變化后經(jīng)過種群進(jìn)化獲得最小的IGD值，并且其IGD動(dòng)態(tài)變化軌跡最平緩，在每次種群進(jìn)化過程中IGD保持持續(xù)變小趨勢(shì)，不會(huì)發(fā)生劇烈變化。所提算法通過動(dòng)態(tài)自適應(yīng)懲罰機(jī)制可以更好地同時(shí)應(yīng)對(duì)目標(biāo)函數(shù)和約束時(shí)變及數(shù)量的變化，因此相比僅針對(duì)目標(biāo)函數(shù)動(dòng)態(tài)變化的D-TAEA顯示出較大優(yōu)勢(shì)。同時(shí)，由于CTAEA不能隨著變化對(duì)CA和DA重構(gòu)，所以其應(yīng)對(duì)優(yōu)化問題目標(biāo)函數(shù)和約束的時(shí)變及數(shù)量動(dòng)態(tài)變化反應(yīng)較慢。而NSGA-II和MOEA/D作為普通優(yōu)化問題求解算法，沒有動(dòng)態(tài)應(yīng)對(duì)機(jī)制，求解DMCMOPs效果較差。這意味著本文所提算法能有效應(yīng)對(duì)動(dòng)態(tài)優(yōu)化問題的目標(biāo)函數(shù)和約束時(shí)變且數(shù)量變化帶來的影響，特別是引入的動(dòng)態(tài)自適應(yīng)懲罰機(jī)制使得算法增強(qiáng)了應(yīng)對(duì)約束的動(dòng)態(tài)變化的能力，在求解DMCMOPs時(shí)能快速收斂，求得的帕累托前沿面更加靠近真實(shí)的帕累托前沿面。此外，注意到在第一次動(dòng)態(tài)變化發(fā)生后，DCTAEA 的優(yōu)勢(shì)并不明顯，這是因?yàn)榇藭r(shí)目標(biāo)函數(shù)數(shù)量較少，其他算法也具有較快收斂速度。然而，隨著目標(biāo)函數(shù)的增多，DCTAEA優(yōu)勢(shì)逐漸顯現(xiàn)。

圖9 τt=25時(shí)整個(gè)進(jìn)化過程IGD的軌跡

圖10和圖11也顯示了所提算法相對(duì)其他算法的有效性和優(yōu)越性。然而，可以發(fā)現(xiàn)D-TAEA經(jīng)過一定的進(jìn)化步數(shù)能達(dá)到和所提算法相同的IGD指標(biāo)值，DCTAEA不再獲得全程優(yōu)勢(shì)。這是因?yàn)殡S著增大，即優(yōu)化問題發(fā)生動(dòng)態(tài)變化的間隔增大，算法有更加充足的時(shí)間應(yīng)對(duì)變化。但是本文所提算法依然具有收斂速度最快的優(yōu)勢(shì)，從而能更好地應(yīng)對(duì)DMCMOPs。

圖10 τt=50時(shí)整個(gè)進(jìn)化過程IGD的軌跡

圖11 τt=100時(shí)整個(gè)進(jìn)化過程IGD的軌跡

5 結(jié)束語

為了提高無人機(jī)集群在復(fù)雜動(dòng)態(tài)環(huán)境下的執(zhí)行協(xié)同搜索跟蹤任務(wù)的效率，克服傳統(tǒng)優(yōu)化問題模型面對(duì)目標(biāo)函數(shù)和約束存在復(fù)雜動(dòng)態(tài)變化不適用的難題，本文構(gòu)建了目標(biāo)函數(shù)和約束時(shí)變且數(shù)量變化的動(dòng)態(tài)優(yōu)化問題模型。為了求解該問題，提出了基于動(dòng)態(tài)自適應(yīng)懲罰機(jī)制的動(dòng)態(tài)約束雙檔案進(jìn)化算法所提算法可以隨著環(huán)境變化自適應(yīng)重建種群，加快種群適應(yīng)新的環(huán)境，引入自適應(yīng)懲罰函數(shù)機(jī)制，整合不可行個(gè)體的目標(biāo)函數(shù)值和違反約束的懲罰值獲得修正的目標(biāo)函數(shù)值，動(dòng)態(tài)調(diào)整不可行解的約束違反值和目標(biāo)函數(shù)的比重，實(shí)現(xiàn)有價(jià)值不可行解的利用，促使種群進(jìn)入可行區(qū)域并向帕累托前沿面收斂。仿真結(jié)果表明，與第二代非支配排序遺傳算法的動(dòng)態(tài)版本、基于分解的多目標(biāo)進(jìn)化算法、約束雙檔案進(jìn)化算法和動(dòng)態(tài)雙檔案進(jìn)化算法相比，本文所提算法具有優(yōu)越性，能使種群在新的環(huán)境下更快收斂。