任務(wù)主體二元約束下作戰(zhàn)任務(wù)分解EVA方法

劉 乾, 魯云軍, 陳克斌, 韓夢(mèng)瑤, 郭 亮

(國(guó)防科技大學(xué)信息通信學(xué)院, 湖北 武漢 430010)

0 引 言

作戰(zhàn)任務(wù)通常是宏觀的、籠統(tǒng)的,不便于下級(jí)作戰(zhàn)部隊(duì)理解和執(zhí)行。任務(wù)分解就是把宏觀的作戰(zhàn)任務(wù)細(xì)化成若干具體、明確的子任務(wù),使作戰(zhàn)任務(wù)、作戰(zhàn)目標(biāo)更為清晰明確[1]。任務(wù)分解是對(duì)復(fù)雜任務(wù)求解的一種簡(jiǎn)化過程,通過合理的任務(wù)分解能夠降低任務(wù)復(fù)雜度,提高任務(wù)執(zhí)行效率。

目前作戰(zhàn)任務(wù)分解方法主要有:① 以定性分析為主的任務(wù)層次分解法[2],按照一定的分解標(biāo)準(zhǔn),將總體作戰(zhàn)任務(wù)定性分解為特定的、層次分明的、相互獨(dú)立的子任務(wù),形成由多層級(jí)子任務(wù)構(gòu)成的任務(wù)分解方案。文獻(xiàn)[3]中通過組合運(yùn)用目標(biāo)分解、功能分解、作戰(zhàn)域分解和地形區(qū)域分解等方法對(duì)登陸作戰(zhàn)使命任務(wù)進(jìn)行了多次定性分解,并提出當(dāng)任務(wù)分解粒度確定時(shí),使命分解得到的任務(wù)分解結(jié)果是類似的。在此基礎(chǔ)上,文獻(xiàn)[1]將作戰(zhàn)力量作為影響任務(wù)分解的重要因素,提出了執(zhí)行主體類型為標(biāo)準(zhǔn)的分解方法,并以此為依據(jù)對(duì)空間信息支援任務(wù)進(jìn)行分解,構(gòu)建了空間信息支援任務(wù)分解結(jié)構(gòu)圖。該類方法分解結(jié)果帶有較大主觀色彩,存在較大的隨機(jī)性和不確定性;② 以定量分析為主的任務(wù)模塊分解法,按照模塊內(nèi)強(qiáng)聚合、模塊間弱耦合的聚類標(biāo)準(zhǔn),將離散型多任務(wù)集合聚類為數(shù)量較少的任務(wù)模塊。文獻(xiàn)[4]引入關(guān)聯(lián)內(nèi)聚系數(shù)和重用內(nèi)聚系數(shù)來綜合描述任務(wù)關(guān)聯(lián)程度,將其作為計(jì)算任務(wù)粒度的變量,并以任務(wù)粒度衡量定性分解子任務(wù)集中子任務(wù)間的耦合程度對(duì)其進(jìn)行量化分解。文獻(xiàn)[5]基于密度峰聚類(density peaks clustering, DPC)方法將任務(wù)集映射成全局任務(wù)引導(dǎo)樹,并提取出中心子任務(wù),而后借鑒圖劃分理論從互聯(lián)性和緊密性兩方面定義任務(wù)關(guān)聯(lián)程度,對(duì)全局任務(wù)引導(dǎo)樹的進(jìn)行聚類,生成任務(wù)模塊。文獻(xiàn)[6]圍繞協(xié)同作戰(zhàn)中任務(wù)分解的優(yōu)化問題,從時(shí)間、邏輯和功能3個(gè)角度對(duì)作戰(zhàn)任務(wù)之間協(xié)同關(guān)系進(jìn)行描述,構(gòu)建了任務(wù)協(xié)同相關(guān)度的量化模型。文獻(xiàn)[7]則在設(shè)計(jì)結(jié)構(gòu)矩陣(design structure matrix, DSM)[8-10]的基礎(chǔ)上提出任務(wù)結(jié)構(gòu)矩陣(task structure matrix, TSM),以任務(wù)間信息流強(qiáng)度作為衡量任務(wù)關(guān)聯(lián)度的量化指標(biāo)。該類方法分解結(jié)果較為客觀、科學(xué),可控性強(qiáng),但是方法應(yīng)用是以已知子任務(wù)集和子任務(wù)間時(shí)序/邏輯/信息傳輸?shù)汝P(guān)系的基礎(chǔ)上按照任務(wù)關(guān)聯(lián)強(qiáng)度進(jìn)行的聚類,本質(zhì)上規(guī)避了子任務(wù)集合的生成問題,實(shí)際應(yīng)用性并不強(qiáng)[11-12];以智能規(guī)劃為主的任務(wù)分解方法[13-16],通常將任務(wù)分解、任務(wù)分配、資源調(diào)度等任務(wù)規(guī)劃問題進(jìn)行統(tǒng)一求解,最典型的就是層次任務(wù)網(wǎng)絡(luò)(hierarchical task network, HTN)方法,即一種基于分層抽象和領(lǐng)域知識(shí)的問題求解方法[17]。其任務(wù)分解過程依靠引入領(lǐng)域知識(shí)構(gòu)建的分解復(fù)雜任務(wù)的方法模型來實(shí)現(xiàn),文獻(xiàn)[18]提出了一種考慮時(shí)間和空間約束的層次任務(wù)網(wǎng)絡(luò)規(guī)劃算法用于解決航母艦載機(jī)準(zhǔn)備、起飛和降落方案生成。針對(duì)這類簡(jiǎn)單任務(wù),HTN方法具備較大的優(yōu)勢(shì),但是面對(duì)復(fù)雜作戰(zhàn)任務(wù)領(lǐng)域時(shí)經(jīng)驗(yàn)豐富的領(lǐng)域?qū)＜铱赡軣o法依靠其領(lǐng)域知識(shí)提供任務(wù)分解方法[19-20]。因此，考慮到領(lǐng)域知識(shí)對(duì)復(fù)雜作戰(zhàn)任務(wù)分解的限制,文獻(xiàn)[21]提出了基于目標(biāo)、組織和規(guī)則(objective organization rule, OOR)框架進(jìn)行任務(wù)細(xì)化的方法和步驟,將其替代領(lǐng)域?qū)＜抑R(shí)引入HTN規(guī)劃。由于HTN規(guī)劃過程中,復(fù)雜任務(wù)分解方法的不唯一性[22],分解結(jié)果存在較大的多樣性,無形中提高了HTN優(yōu)化解搜索的復(fù)雜性,使得搜索過程變成一個(gè)多項(xiàng)式復(fù)雜程度的非確定性問題(non-deterministic polynominal complete problem, NPC)[23]。

綜上所述可知:一是定性方法依賴指揮員的歷史經(jīng)驗(yàn)和領(lǐng)域?qū)＜抑R(shí),存在大量的不確定性,僅可用于簡(jiǎn)單戰(zhàn)術(shù)級(jí)任務(wù);二是多數(shù)定量方法僅考慮了任務(wù)和任務(wù)關(guān)系因素,忽略了任務(wù)主體的能力因素限制,與任務(wù)分解實(shí)際并不相符;三是忽略了任務(wù)主體結(jié)構(gòu)特征,無法控制分解結(jié)果中子任務(wù)數(shù)量,子任務(wù)數(shù)量與任務(wù)主體下屬任務(wù)個(gè)體數(shù)量不匹配。為此,本文立足現(xiàn)有方法缺陷與不足,綜合考慮任務(wù)主體能力因素和結(jié)構(gòu)特征等二元約束,提出一種由子任務(wù)集提取(extraction, E)、約束檢驗(yàn)(verification, V)、子任務(wù)集調(diào)整(adjustment, A)等步驟遞進(jìn)循環(huán)形成的任務(wù)分解EVA方法。

1 任務(wù)分解問題描述及求解框架

1.1 問題描述

本文研究的作戰(zhàn)任務(wù)分解是在已知目標(biāo)任務(wù)和任務(wù)主體的基礎(chǔ)上,依據(jù)任務(wù)主體能力屬性和結(jié)構(gòu)特征將目標(biāo)任務(wù)分解成一定數(shù)量的子任務(wù),同時(shí)按照一定順序關(guān)系執(zhí)行子任務(wù),能夠達(dá)成任務(wù)目標(biāo)。

因此任務(wù)分解問題可描述為:已知任務(wù)主體S={S1,S2,…,Sn},其能力屬性矩陣C=[C1,C2,…,Cn],Cn表示任務(wù)個(gè)體Sn的k維能力向量,目標(biāo)任務(wù)為T,若存在T0={T1,T2,…,Tm},且其能力需求矩陣RC0=[RC1,RC2,…,RCm],RCm表示任務(wù)Tm的k維能力需求向量,使得S中任務(wù)個(gè)體按照某種時(shí)序關(guān)系完成T0中所有子任務(wù)后能夠達(dá)成T,那么T0就是T的一個(gè)任務(wù)分解結(jié)果。同時(shí)T0還需滿足如下兩條約束:

約束 1子任務(wù)能力可支持約束,即分解結(jié)果中各子任務(wù)的能力需求都能夠被任務(wù)主體下屬某任務(wù)個(gè)體所滿足,任務(wù)分解結(jié)果中不存在無法執(zhí)行的子任務(wù)。即對(duì)于T0={T1,T2,…,Tm}和S={S1,S2,…,Sn},應(yīng)滿足?j∈m,?i∈n,RCjh≤Cih,h∈(1,k)。

約束 2子任務(wù)數(shù)量可支持約束,即分解結(jié)果中子任務(wù)數(shù)量不能大于任務(wù)主體下屬任務(wù)個(gè)體的數(shù)量。由于任務(wù)主體的任務(wù)分解結(jié)果是其下級(jí)任務(wù)個(gè)體的任務(wù)分解對(duì)象,每個(gè)任務(wù)個(gè)體僅能受領(lǐng)一個(gè)目標(biāo)任務(wù),因此需從任務(wù)主體結(jié)構(gòu)特征角度限制任務(wù)分解結(jié)果中子任務(wù)數(shù)量。即對(duì)于T0={T1,T2,…,Tm},應(yīng)滿足m≤n,其中n表示任務(wù)主體下屬任務(wù)個(gè)體數(shù)量,m表示分解結(jié)果中子任務(wù)數(shù)量。

1.2 EVA方法框架

依據(jù)上述任務(wù)分解描述,作戰(zhàn)任務(wù)分解應(yīng)包括:依據(jù)目標(biāo)任務(wù)生成子任務(wù)集,判斷子任務(wù)集是否滿足任務(wù)主體二元約束,以及在不滿足約束時(shí)對(duì)子任務(wù)集進(jìn)行調(diào)整等步驟?？紤]到上述問題之間的內(nèi)在關(guān)聯(lián)性,本文在任務(wù)主體二元約束限制下,設(shè)計(jì)了作戰(zhàn)任務(wù)分解EVA方法框架，其流程圖如圖1所示。

步驟 1子任務(wù)集提取(E)

步驟 1.1全局作戰(zhàn)任務(wù)空間構(gòu)建。確定作戰(zhàn)任務(wù)層級(jí),并對(duì)不同層級(jí)任務(wù)進(jìn)行結(jié)構(gòu)化建模,設(shè)計(jì)其結(jié)構(gòu)化描述要素,形成層次化樹狀結(jié)構(gòu)的任務(wù)空間。

步驟 1.2目標(biāo)任務(wù)分解樹提取。依據(jù)任務(wù)描述模型對(duì)目標(biāo)任務(wù)進(jìn)行結(jié)構(gòu)化描述,通過匹配方法確定目標(biāo)任務(wù)在全局任務(wù)空間的位置,并提取以目標(biāo)任務(wù)為根節(jié)點(diǎn),與其直接相連的下一層級(jí)任務(wù)為葉子節(jié)點(diǎn)的任務(wù)分解樹,將分解樹的最底層葉子節(jié)點(diǎn)集合作為子任務(wù)集。

步驟 2約束檢驗(yàn)(V)

按照先檢驗(yàn)約束1(子任務(wù)能力可支持約束),再檢驗(yàn)約束2(子任務(wù)數(shù)量可支持約束)的串行檢驗(yàn)思路,若不滿足約束1,則轉(zhuǎn)入步驟3.1;若滿足約束1,不滿足約束2,則轉(zhuǎn)入步驟3.2,而后分解結(jié)束;若約束1和約束2都滿足,則分解結(jié)束。

步驟 3子任務(wù)集調(diào)整(A)

步驟 3.1子任務(wù)集細(xì)化調(diào)整。針對(duì)不滿足約束1的子任務(wù)提取以它為根節(jié)點(diǎn)的任務(wù)分解樹,將該樹的葉子節(jié)點(diǎn)集合替代根節(jié)點(diǎn)融入原始子任務(wù)集,并轉(zhuǎn)入步驟2。

步驟 3.2子任務(wù)集量化調(diào)整。以任務(wù)模塊內(nèi)關(guān)聯(lián)程度高、任務(wù)模塊間關(guān)聯(lián)程度低為優(yōu)化目標(biāo),以任務(wù)模塊數(shù)量可支持和任務(wù)模塊能力可支持作為約束條件,構(gòu)建子任務(wù)集量化調(diào)整模型并求解。

2 子任務(wù)集提取

按照上述求解策略,為構(gòu)建全局作戰(zhàn)任務(wù)空間,首先需要對(duì)任務(wù)進(jìn)行描述,確定任務(wù)層級(jí)和不同層級(jí)任務(wù)的描述要素,而后依據(jù)不同層級(jí)任務(wù)間的父子關(guān)系,建立全局任務(wù)空間,并以此為依據(jù),匹配確定目標(biāo)任務(wù)在全局任務(wù)空間中的位置,獲取目標(biāo)任務(wù)分解樹,進(jìn)而完成目標(biāo)任務(wù)的子任務(wù)集提取。

2.1 全局作戰(zhàn)任務(wù)空間構(gòu)建

依據(jù)美軍通用聯(lián)合任務(wù)清單(universal joint task list,UJTL)[24]將作戰(zhàn)任務(wù)劃分為由高至低的聯(lián)合作戰(zhàn)任務(wù)、基本作戰(zhàn)任務(wù)和戰(zhàn)術(shù)行動(dòng)任務(wù)3類,并以3類作戰(zhàn)任務(wù)為基礎(chǔ)進(jìn)行描述。

聯(lián)合作戰(zhàn)任務(wù)描述模型。聯(lián)合作戰(zhàn)任務(wù)是復(fù)雜任務(wù),由聯(lián)合作戰(zhàn)部隊(duì)負(fù)責(zé)執(zhí)行,處于作戰(zhàn)任務(wù)空間的最頂層。因此,聯(lián)合作戰(zhàn)任務(wù)描述模型表示為TS/B/T=〈任務(wù)序號(hào),任務(wù)內(nèi)容,任務(wù)尺度,任務(wù)類型,任務(wù)層級(jí),任務(wù)能力需求,子任務(wù)序號(hào)〉,其中TS、TB、TT分別表示戰(zhàn)略層、戰(zhàn)役層、戰(zhàn)術(shù)層聯(lián)合作戰(zhàn)任務(wù)。

基本作戰(zhàn)任務(wù)描述模型。基本作戰(zhàn)任務(wù)是聯(lián)合作戰(zhàn)任務(wù)的子任務(wù),是戰(zhàn)術(shù)行動(dòng)任務(wù)的父任務(wù),處于作戰(zhàn)任務(wù)空間的中間層,由各軍種各層級(jí)作戰(zhàn)力量負(fù)責(zé)執(zhí)行。基本作戰(zhàn)任務(wù)描述模型表示為TF=〈任務(wù)序號(hào)，任務(wù)內(nèi)容，任務(wù)尺度，任務(wù)類型，任務(wù)能力需求，父任務(wù)序號(hào)，子任務(wù)序號(hào)〉。

戰(zhàn)術(shù)行動(dòng)任務(wù)描述模型。戰(zhàn)術(shù)行動(dòng)任務(wù)是子任務(wù),處于作戰(zhàn)任務(wù)空間的最底層,通常對(duì)應(yīng)軍事行動(dòng)中的戰(zhàn)術(shù)行動(dòng),通常不可再分解。因此,戰(zhàn)術(shù)行動(dòng)任務(wù)描述模型表示為TA=〈任務(wù)序號(hào)，任務(wù)內(nèi)容，任務(wù)尺度，任務(wù)類型，任務(wù)能力需求，父任務(wù)序號(hào)〉。

作戰(zhàn)任務(wù)空間是層次化樹狀結(jié)構(gòu),主體按照“聯(lián)合作戰(zhàn)任務(wù)→基本作戰(zhàn)任務(wù)→戰(zhàn)斗行動(dòng)任務(wù)”的順序逐級(jí)細(xì)化生成的一個(gè)全局作戰(zhàn)任務(wù)樹,為目標(biāo)任務(wù)分解樹生成提供全局任務(wù)搜索空間。由于任務(wù)主體指揮層次的多樣性,使得任務(wù)空間逐級(jí)細(xì)化過程中又存在多種分解模式,分解模式的選擇主要由任務(wù)主體指揮層級(jí)結(jié)構(gòu)特點(diǎn)所決定,具體如圖2所示。

當(dāng)前構(gòu)建面向任務(wù)主體的作戰(zhàn)任務(wù)空間的方法主要包括兩種:一是以成熟的聯(lián)合作戰(zhàn)任務(wù)清單和任務(wù)主體指揮層級(jí)為基礎(chǔ),從聯(lián)合作戰(zhàn)任務(wù)清單中提取出任務(wù)主體可能承擔(dān)的所有使命任務(wù),而后將上述使命任務(wù)作為該任務(wù)主體的全局作戰(zhàn)任務(wù)空間中的頂層根任務(wù),提取出該根節(jié)點(diǎn)任務(wù)的所有葉子節(jié)點(diǎn)任務(wù),并利用上述3類作戰(zhàn)任務(wù)描述模型對(duì)上述各類型任務(wù)進(jìn)行形式化描述,而后依據(jù)任務(wù)主體指揮層次特征,搭建符合任務(wù)主體指揮層級(jí)特點(diǎn)的全局作戰(zhàn)任務(wù)空間;二是在缺乏成熟的聯(lián)合作戰(zhàn)任務(wù)清單的情況下,需要利用專家知識(shí)與歷史經(jīng)驗(yàn)從任務(wù)主體作戰(zhàn)想定、演習(xí)方案等相關(guān)文書中抽取出相應(yīng)數(shù)據(jù),依托條令條例進(jìn)行文本數(shù)據(jù)規(guī)范,再采用任務(wù)描述模型進(jìn)行形式化描述,最后結(jié)合任務(wù)主體的指揮層次特征構(gòu)建全局作戰(zhàn)任務(wù)空間,其基本思路如圖3所示。由于當(dāng)前我軍尚無成熟的聯(lián)合作戰(zhàn)任務(wù)清單,因此在具體實(shí)施過程中,需要大量依靠專家和指揮人員的知識(shí)和經(jīng)驗(yàn),利用基于人工智能的文本信息抽取工具,從大量作戰(zhàn)文書文檔資料中抽取出所需的作戰(zhàn)任務(wù)數(shù)據(jù)信息,這也是全局作戰(zhàn)任務(wù)空間構(gòu)建的關(guān)鍵。

2.2 目標(biāo)任務(wù)分解樹提取

該方法主要解決從龐大的任務(wù)空間中快速找出與目標(biāo)任務(wù)匹配度最高的作戰(zhàn)任務(wù)。依據(jù)任務(wù)執(zhí)行主體層級(jí)結(jié)構(gòu)特征確定任務(wù)分解模式,并以此為基礎(chǔ)提取出與其直接相連的下一層級(jí)任務(wù),生成目標(biāo)任務(wù)的任務(wù)分解樹,實(shí)現(xiàn)針對(duì)特定作戰(zhàn)任務(wù)的快速分解。具體流程如下:

步驟 1讀取全局作戰(zhàn)任務(wù)空間中聯(lián)合作戰(zhàn)任務(wù)列表的任務(wù)集TJ,基本作戰(zhàn)任務(wù)列表的任務(wù)集TF,戰(zhàn)術(shù)行動(dòng)任務(wù)列表的任務(wù)集TA;

步驟 2將目標(biāo)任務(wù)存儲(chǔ)在集合A中,任務(wù)匹配結(jié)果存儲(chǔ)在集合B中,任務(wù)分解樹的任務(wù)集存儲(chǔ)在集合C中,初始情況下集合A是多任務(wù)集合,集合B和C均為空;

步驟 3從集合A中隨機(jī)選擇一項(xiàng)目標(biāo)任務(wù),判斷其任務(wù)類型,并按照相應(yīng)作戰(zhàn)任務(wù)描述模型進(jìn)行建模,設(shè)為T0;

步驟 4將T0與相應(yīng)類型的任務(wù)集進(jìn)行對(duì)照比對(duì),依次按照任務(wù)層級(jí)、任務(wù)類型、任務(wù)內(nèi)容的優(yōu)先順序進(jìn)行比對(duì),檢查任務(wù)集中是否存在與T0完全相同或匹配度較高的任務(wù)T1,若存在,將任務(wù)T1存入集合B中,并轉(zhuǎn)入步驟6,否則轉(zhuǎn)入步驟5;

步驟 5匹配搜索任務(wù)無法完成,返回由指揮人員進(jìn)行人工干預(yù),并從集合A中刪除任務(wù)T0;

步驟 6依據(jù)任務(wù)執(zhí)行主體結(jié)構(gòu)特征,確定任務(wù)分解模式,從全局作戰(zhàn)任務(wù)空間中提取與任務(wù)T1存在子代關(guān)系的作戰(zhàn)任務(wù)集,存入集合C;

步驟 7輸出集合C,并按照任務(wù)集中任務(wù)間父子關(guān)系生成目標(biāo)任務(wù)的雙層任務(wù)分解樹并保存,清空集合B和C,刪除集合A中的任務(wù)T0;

步驟 8如果集合A為空集,表示匹配搜索完成,否則繼續(xù)進(jìn)行搜索,轉(zhuǎn)入步驟3。

上述匹配方法的關(guān)鍵是對(duì)兩個(gè)作戰(zhàn)任務(wù)進(jìn)行對(duì)照比較,判斷兩個(gè)作戰(zhàn)任務(wù)的匹配程度。這個(gè)問題通?？刹捎萌斯てヅ?、機(jī)器學(xué)習(xí)語義識(shí)別匹配、人工智能等方法,由于不是本文的重點(diǎn),在這里不做贅述。

3 子任務(wù)集調(diào)整建模

按照上述求解策略,需對(duì)不滿足任務(wù)主體二元約束的子任務(wù)集進(jìn)行調(diào)整,包括細(xì)化調(diào)整和量化調(diào)整,其中細(xì)化調(diào)整可采用第2.2節(jié)所提出的任務(wù)分解樹提取方法。本節(jié)重點(diǎn)研究子任務(wù)集量化調(diào)整建模。

3.1 符號(hào)說明

為準(zhǔn)確描述子任務(wù)集量化調(diào)整問題,先定義如下符號(hào):T表示所有子任務(wù)的集合;RT表示T中相互關(guān)聯(lián)的子任務(wù)所構(gòu)成的任務(wù)集合,即關(guān)聯(lián)性任務(wù)集合;IT表示T中相互獨(dú)立的子任務(wù)所構(gòu)成的集合,即獨(dú)立性任務(wù)集合;RCi表示子任務(wù)Ti的能力需求矢量,RCij表示子任務(wù)Ti的第j項(xiàng)能力需求值;μk是第k項(xiàng)能力需求的權(quán)重;S表示任務(wù)主體;n表示任務(wù)主體下屬任務(wù)個(gè)體數(shù)量;Ci表示任務(wù)個(gè)體Si的能力向量,Cij表示任務(wù)個(gè)體Ci的第j項(xiàng)能力屬性值。

3.2 任務(wù)關(guān)聯(lián)程度量化

針對(duì)RT和IT的任務(wù)特征,分別引入任務(wù)支持度和任務(wù)相似度對(duì)兩類任務(wù)的關(guān)聯(lián)程度進(jìn)行量化描述。

任務(wù)支持度是衡量RT中任務(wù)間關(guān)聯(lián)程度的量化指標(biāo),可由任務(wù)間的信息支持度、態(tài)勢(shì)支持度來綜合計(jì)算。例如,如果任務(wù)T1是任務(wù)T2的前置任務(wù),記任務(wù)T1信息態(tài)勢(shì)輸出變量out1=(io1,so1),任務(wù)T2信息態(tài)勢(shì)輸入變量in2=(ii2,si2),則任務(wù)T1對(duì)任務(wù)T2的支持度如下:

md12=αfi(io1,ii2)+βfs(so1,si2)

(1)

式中：fi為信息支持函數(shù);fs為態(tài)勢(shì)支持函數(shù);α、β為支持權(quán)重;md12=md21,mdii=0。

任務(wù)模塊內(nèi)支持度:若某關(guān)聯(lián)性任務(wù)模塊由m個(gè)關(guān)聯(lián)性任務(wù)構(gòu)成,則任務(wù)模塊內(nèi)支持度為

(2)

任務(wù)模塊間支持度：如果某兩個(gè)關(guān)聯(lián)性任務(wù)模塊內(nèi)任務(wù)數(shù)量分別為m和n,則任務(wù)模塊間支持度為

(3)

任務(wù)相似度：衡量IT中任務(wù)間關(guān)聯(lián)程度的量化指標(biāo),可由IT中各任務(wù)能力需求矢量的相似接近程度計(jì)算。即IT中任務(wù)Ti和任務(wù)Tj的相似度可表示為RCi和RCj的加權(quán)閔可夫斯基距離dij，表達(dá)式為

(4)

式中:p表示階數(shù),通常取值p=1,2或+∞。依式(4)可得IT的加權(quán)閔可夫斯基距離矩陣(dij)N×N,歸一化處理后得到歸一化矩陣(sdij)N×N,其中sdii=0,N是獨(dú)立性任務(wù)集中子任務(wù)數(shù)量。

任務(wù)模塊內(nèi)相似度:假設(shè)某獨(dú)立性任務(wù)模塊由n項(xiàng)子任務(wù)構(gòu)成,則任務(wù)模塊內(nèi)相似度為

(5)

任務(wù)模塊間相似度：如果某兩個(gè)獨(dú)立性任務(wù)模塊內(nèi)任務(wù)數(shù)量分別為p和q,則任務(wù)模塊間相似度為

(6)

3.3 目標(biāo)函數(shù)

子任務(wù)集調(diào)整是以調(diào)整后任務(wù)模塊內(nèi)關(guān)聯(lián)程度最大,任務(wù)模塊間關(guān)聯(lián)程度最小作為優(yōu)化目標(biāo)。假設(shè)RT和IT兩類任務(wù)集中初始子任務(wù)數(shù)量為I和J,量化調(diào)整后任務(wù)模塊數(shù)量分別為P和Q,則其目標(biāo)函數(shù)可表示為

(7)

式中:MDm是RT量化調(diào)整后任務(wù)模塊內(nèi)部支持度;MDij是RT量化調(diào)整后任務(wù)模塊間支持度;SDn是IT量化調(diào)整后任務(wù)模塊內(nèi)部相似度;SDij是IT量化調(diào)整后任務(wù)模塊間相似度;i≠j。

3.4 約束條件

(1) 任務(wù)模塊能力可支持,即對(duì)于任意任務(wù)模塊都存在至少一個(gè)任務(wù)執(zhí)行個(gè)體,使得個(gè)體能力向量滿足任務(wù)模塊能力需求。

(8)

式中:RCXrh表示RT任務(wù)集中任務(wù)模塊Xr的第h項(xiàng)能力需求值;RCYsh表示IT任務(wù)集中任務(wù)模塊Ys的第h項(xiàng)能力需求值。

若RT的任務(wù)模塊Xr有t個(gè)子任務(wù),IT的任務(wù)模塊Ys有g(shù)個(gè)子任務(wù),則任務(wù)模塊的第h項(xiàng)能力需求值如下:

(9)

RT中任務(wù)模塊的能力需求是取模塊內(nèi)子任務(wù)單項(xiàng)能力需求的最大值,IT中任務(wù)模塊的能力需求是取模塊內(nèi)子任務(wù)單項(xiàng)能力需求的累加值。

(2) 任務(wù)模塊數(shù)量可支持,即子任務(wù)集量化調(diào)整后生成的任務(wù)模塊數(shù)量不多于任務(wù)執(zhí)行主體下屬執(zhí)行個(gè)體數(shù)量:

P+Q≤N

(10)

(3) 任務(wù)模塊不重疊,即任意子任務(wù)只能隸屬于一個(gè)任務(wù)模塊,不能同時(shí)屬于多個(gè)任務(wù)模塊。

(4) 任務(wù)模塊不為空,即任意任務(wù)模塊中至少應(yīng)包含一個(gè)子任務(wù),不能為空。

4 模型求解

子任務(wù)集調(diào)整模型求解是多目標(biāo)優(yōu)化問題,其求解算法通常是一種多目標(biāo)優(yōu)化算法[25]。非支配排序遺傳算法Ⅱ(non-dominated sorfing genetic algorithm-Ⅱ, NSGA-Ⅱ)由于計(jì)算速度快,能夠保持種群個(gè)體多樣性等優(yōu)點(diǎn),已經(jīng)成為目前較常用的低維多目標(biāo)優(yōu)化算法[20]。該方法采用了精英保留策略對(duì)非支配排序產(chǎn)生的最佳個(gè)體進(jìn)行保留。在保留過程中會(huì)產(chǎn)生大量相同或相似個(gè)體覆蓋整個(gè)種群,容易造成早熟。該算法采用了固定的交叉、變異概率,而固定交叉概率會(huì)影響優(yōu)秀個(gè)體的存在、固定變異概率會(huì)影響個(gè)體的多樣性。

因此,本文在NSGA-Ⅱ算法基礎(chǔ)上,引入任務(wù)分解粒度、改進(jìn)型的精英保留策略和交叉、變異概率動(dòng)態(tài)調(diào)整策略,提出一種改進(jìn)NSGA-Ⅱ(improved NSGA-Ⅱ, INSGA-Ⅱ)用于模型求解以降低算法求解復(fù)雜度,避免算法早熟,保證解的多樣性。

4.1 任務(wù)分解粒度

通常記為ω,且ω∈[0, 1],若任務(wù)支持度(相似度)mdij≥ω(sdij≥ω),則表示兩任務(wù)間具有很強(qiáng)的關(guān)聯(lián)性,可視為一個(gè)任務(wù)整體[26]。當(dāng)ω=0時(shí),表示子任務(wù)集中所有子任務(wù)是一個(gè)任務(wù)整體;當(dāng)ω=1時(shí),表示子任務(wù)集中每一個(gè)子任務(wù)都是一個(gè)獨(dú)立的任務(wù)個(gè)體。在種群初始化之前,利用任務(wù)分解粒度ω對(duì)RT任務(wù)集的支持度矩陣、IT任務(wù)集的相似度矩陣進(jìn)行降階處理,即設(shè)定任務(wù)分解粒度ω,將支持度mdij≥ω或相似度sdij≥ω的任務(wù)Ti、Tj合并。

4.2 改進(jìn)的精英保留策略

改進(jìn)的精英保留策略是在傳統(tǒng)精英保留策略的基礎(chǔ)上,只保留經(jīng)過非支配層排序后的第一支配層的全部個(gè)體,對(duì)其他支配層個(gè)體不再按照支配層級(jí)由高到低進(jìn)行保留,而是均按照一定的比例進(jìn)行保留,并確保所保留的個(gè)體數(shù)量與初始種群個(gè)體數(shù)量相同。改進(jìn)的精英保留策略能夠保證生成的子代種群的多樣性,避免算法過早收斂[27]。針對(duì)改進(jìn)的精英保留策略本文設(shè)計(jì)了如下不同支配層級(jí)子代保留數(shù)量的計(jì)算公式:

(11)

式中:K表示父代和子代合并后的種群經(jīng)過非支配層排序后支配層的數(shù)量;mi表示第i層支配層應(yīng)保留的個(gè)體數(shù)量;m0表示第一層支配層后代的數(shù)量;m表示初始種群的染色體數(shù)量。如果在經(jīng)過多次交叉、變異計(jì)算后第一支配層級(jí)個(gè)體數(shù)量大于初始種群中染色體數(shù)量時(shí),則采用傳統(tǒng)精英保留策略,對(duì)第一支配層內(nèi)個(gè)體進(jìn)行擁擠度計(jì)算,僅保留第一支配層中較優(yōu)的m個(gè)個(gè)體。

4.3 交叉、變異概率動(dòng)態(tài)調(diào)整策略

交叉和變異是種群進(jìn)化的關(guān)鍵。交叉概率高容易產(chǎn)生新的個(gè)體,但高適應(yīng)度的個(gè)體也容易被破壞,交叉概率低難以搜索到高適應(yīng)度的個(gè)體。變異概率高能夠提高算法局部搜索速度,保持種群多樣性,避免早熟,變異概率低能夠保持種群的穩(wěn)定性收斂快。傳統(tǒng)方法通過人為設(shè)定固定的交叉概率和變異概率,但無法適應(yīng)種群進(jìn)化的動(dòng)態(tài)變化性[28]。

交叉概率動(dòng)態(tài)調(diào)整策略。在種群進(jìn)化初期,種群多樣性好,故只需要較低的交叉概率保持種群多樣性,隨著代數(shù)增加,種群中相同/相似個(gè)體數(shù)量不斷增加,需要逐步提高交叉概率保證種群多樣性。交叉概率是隨著進(jìn)化代數(shù)增加不斷增加。其計(jì)算公式如下:

(12)

變異概率動(dòng)態(tài)調(diào)整策略。在種群進(jìn)化初期,可以通過加大變異概率,提高算法的搜索速度,隨著代數(shù)不斷增加,種群個(gè)體都擁有比較高的適應(yīng)度,因此需要降低變異概率,保持種群的穩(wěn)定性,提高收斂速度。變異概率是隨著進(jìn)化代數(shù)增加而不斷降低。其計(jì)算公式如下:

(13)

式中:PC 0和PM 0表示初始交叉概率和變異概率；GEN表示設(shè)定的遺傳代數(shù);gen表示當(dāng)前的遺傳代數(shù);α和β均為常量,分別取1.5和0.05。

4.4 染色體編碼方式

考慮到目標(biāo)函數(shù)存在的4項(xiàng)約束條件,為簡(jiǎn)化求解過程降低約束檢驗(yàn)的復(fù)雜性,本文采用實(shí)數(shù)編碼方式,假設(shè)子任務(wù)集數(shù)量為I,任務(wù)模塊數(shù)量為J,則染色體基因長(zhǎng)度為I,且按照子任務(wù)編號(hào)由小到大進(jìn)行排序,如果某基因元素的取值為a,則表明該基因代表的子任務(wù)將聚類到第a個(gè)任務(wù)模塊。為解決染色體編碼的非冗余性,在按照子任務(wù)編號(hào)順序逐一編碼時(shí),設(shè)定當(dāng)iJ時(shí)只能在實(shí)數(shù)集{1,2,…,J}中取任意值。若I=8,J=3,則按照上述方法隨機(jī)生成的染色體編碼示例如表1表示。

表1 染色體編碼示例

上述編碼方式能夠保證隨機(jī)生成的染色體滿足任務(wù)模塊數(shù)量可支持性和任務(wù)模塊不重疊的約束條件,因此隨機(jī)生成染色體后僅需檢驗(yàn)任務(wù)模塊能力可支持性和任務(wù)模塊不為空。

4.5 遺傳算子

交叉算子。采用“單點(diǎn)交叉”模式,在選擇交叉點(diǎn)時(shí),從兩個(gè)染色體起始位開始,當(dāng)?shù)谝淮纬霈F(xiàn)元素不同時(shí),以該基因點(diǎn)作為交叉點(diǎn),將基因點(diǎn)右側(cè)的部分染色體進(jìn)行交叉。該交叉算子能保證交叉后染色體始終滿足任務(wù)模塊不重疊、任務(wù)模塊不為空和任務(wù)模塊數(shù)量可支持性約束,還需檢驗(yàn)是否符合染色體編碼方式,且滿足任務(wù)模塊能力可支持性約束,如果不滿足,則將交叉點(diǎn)右移一位,繼續(xù)進(jìn)行交叉,直到滿足約束。如果始終無法滿足約束,則交叉失敗,重新隨機(jī)選擇染色體進(jìn)行交叉。

變異算子。鑒于染色體編碼的特殊性,在變異點(diǎn)選擇上,應(yīng)隨機(jī)選擇除起始點(diǎn)和任務(wù)模塊中僅有一個(gè)子任務(wù)的基因點(diǎn)之外的其他基因點(diǎn)作為變異點(diǎn)。在變異值選擇上,應(yīng)從基因元素定義域中隨機(jī)選擇除原始值以外的任意值,并檢驗(yàn)是否符合染色體編碼方式,且滿足任務(wù)模塊能力可支持性約束,如果某子代不符合約束或編碼方式,則隨機(jī)選擇其他子代,若都不符合,則重新選擇變異點(diǎn)。

4.6 改進(jìn)型NSGA-Ⅱ算法流程

步驟 1設(shè)定任務(wù)分解粒度ω,將支持度m dij≥ω或相似度s dij≥ω的任務(wù)Ti、Tj合并;

步驟 2種群初始化,種群規(guī)模為s;

步驟 3遺傳運(yùn)算,運(yùn)用交叉、變異概率動(dòng)態(tài)調(diào)整策略,對(duì)隨機(jī)選擇種群個(gè)體進(jìn)行交叉、變異;

步驟 4將初始種群與交叉子代、變異子代合并,運(yùn)用改進(jìn)的精英保留策略保留數(shù)量為s的個(gè)體作為第一代子代種群;

步驟 5將第一代子代種群按照步驟3和步驟4進(jìn)行循環(huán)操作,直至滿足遺傳結(jié)束條件。

5 仿真與分析

5.1 仿真實(shí)驗(yàn)

本節(jié)對(duì)上述子任務(wù)集量化調(diào)整模型及求解算法進(jìn)行實(shí)驗(yàn)分析。假設(shè)某任務(wù)主體S其下屬任務(wù)個(gè)體數(shù)量為6,能力維度為10,其能力屬性矩陣如表2所示。

表2 能力屬性矩陣

任務(wù)主體S受領(lǐng)作戰(zhàn)任務(wù)T,其子任務(wù)數(shù)量為19,且RT和IT中子任務(wù)數(shù)量分別為13和6。利用任務(wù)支持度和任務(wù)相似度計(jì)算公式,且假設(shè)加權(quán)閔式距離計(jì)算階數(shù)p=2,可得RT的支持度矩陣(mdij)13×13和IT的相似度矩陣(sdij),如表3和表4所示。假設(shè)ω=0.7,則RT={T1,T2,T3, (T4T10),T5, (T6T7), (T8T9),T11, (T12T13)},IT={(T14T17), (T15T18), (T16T19)},其任務(wù)能力需求矩陣如表5所示。

表3 支持度矩陣

表4 相似度矩陣

表5 任務(wù)能力需求矩陣

參數(shù)設(shè)置:種群規(guī)模為300,遺傳代數(shù)為20,交叉、變異比例初始值分別取0.8和0.007。仿真實(shí)驗(yàn)參數(shù)主要以文獻(xiàn)[29-30]中遺傳算法和NSGA-Ⅱ算法所指定的參數(shù)值為基礎(chǔ),通過調(diào)整算法參數(shù)值進(jìn)行了多次仿真實(shí)驗(yàn),綜合考慮算法計(jì)算速度和解集質(zhì)量等因素而確定。

仿真實(shí)驗(yàn)分別獨(dú)立運(yùn)行20次,取模塊內(nèi)支持度最大、模塊間支持度最小的染色體作為任務(wù)集RT的調(diào)整結(jié)果,取模塊內(nèi)相似度最大、模塊間相似度最小的染色體作為任務(wù)集IT的調(diào)整結(jié)果,如表6和表7所示。表6中SDinner、SDinter分別表示各模塊內(nèi)部相似度累加和、各模塊間相似度累加和，表7中MDinner、MDinter分別表示各模塊內(nèi)部支持度累加和、各模塊間支持度累加和。

表6 IT量化調(diào)整結(jié)果

表7 RT量化調(diào)整結(jié)果

仿真實(shí)驗(yàn)結(jié)果表明:運(yùn)用INSGA-Ⅱ算法求解多目標(biāo)優(yōu)化問題將生成一個(gè)優(yōu)化解集,解集中的每一個(gè)優(yōu)化解都是該多目標(biāo)優(yōu)化問題的最優(yōu)解。對(duì)于本文研究的雙目標(biāo)優(yōu)化模型,考慮到存在的任務(wù)模塊能力可支持、任務(wù)模塊數(shù)量可支持、任務(wù)模塊不重疊和任務(wù)模塊不為空等4個(gè)約束條件,對(duì)于獨(dú)立性任務(wù)集IT的量化調(diào)整結(jié)果僅存在一個(gè)最優(yōu)解,而對(duì)于關(guān)聯(lián)性任務(wù)集RT則存在多個(gè)最優(yōu)解。而在實(shí)際應(yīng)用上,需要指揮員考慮影響使命任務(wù)達(dá)成的關(guān)鍵性子任務(wù)、戰(zhàn)場(chǎng)對(duì)抗條件、作戰(zhàn)單元協(xié)同難易程度等多方面因素從最優(yōu)解中選取一個(gè)最優(yōu)解作為實(shí)際作戰(zhàn)任務(wù)分解方案。

5.2 算法對(duì)比分析

為比較本文所提INSGA-Ⅱ算法優(yōu)勢(shì),選取NSGA-Ⅱ、基于分解的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm based on decomposition, MOEA/D)作為對(duì)比算法,圍繞第5.1節(jié)中任務(wù)集RT的量化調(diào)整過程進(jìn)行3組實(shí)驗(yàn),每組實(shí)驗(yàn)獨(dú)立運(yùn)行20次,分別取每組實(shí)驗(yàn)中最優(yōu)解的兩個(gè)優(yōu)化目標(biāo)MDinner和MDinter的平均值進(jìn)行比較分析,如表8所示。從表中可以看出在3組實(shí)驗(yàn)中,第3組實(shí)驗(yàn)中INSGA-Ⅱ算法與第2組實(shí)驗(yàn)中MOEA/D算法結(jié)果相同;第2組實(shí)驗(yàn)中INSGA-Ⅱ算法與第3組實(shí)驗(yàn)中MOEA/D算法結(jié)果接近,但相對(duì)較優(yōu)。從其他實(shí)驗(yàn)結(jié)果來看,INSGA-Ⅱ算法相比較NSGA-Ⅱ和MOEA/D算法均具有一定優(yōu)勢(shì)。

表8 各算法結(jié)果比較

以第1組實(shí)驗(yàn)為例,生成3種算法最優(yōu)解的散點(diǎn)分布圖(圖4)來看,在處理低維多目標(biāo)優(yōu)化問題上,MOEA/D和INSGA-Ⅱ算法在解集的分布性上均優(yōu)于NSGA-Ⅱ。而INSGA-Ⅱ算法在解集的收斂效果上要優(yōu)于MOEA/D和NSGA-Ⅱ算法。因此,決策者可結(jié)合戰(zhàn)場(chǎng)實(shí)際,從INSGA-Ⅱ算法生成的Pareto解集中選擇任務(wù)量化調(diào)整方案,以指導(dǎo)后續(xù)任務(wù)規(guī)劃工作。

5.3 算法性能分析

本文主要選取覆蓋率指標(biāo)(set coverage, SC)[31]和時(shí)間性能指標(biāo)對(duì)3類算法的性能進(jìn)行分析。其中SC解集覆蓋率指標(biāo)是比較各種算法產(chǎn)生的Pareto解集之間的支配關(guān)系。通常由兩個(gè)算法產(chǎn)生的Pareto解集的支配比例來衡量。3種算法的SC覆蓋率指標(biāo)如表9所示?？梢钥闯鯥NSGA-Ⅱ的覆蓋率指標(biāo)優(yōu)于另外兩種多目標(biāo)優(yōu)化算法,表明INSGA-Ⅱ算法具有較好的多樣性和收斂性,解集質(zhì)量較高。

表9 各算法覆蓋率指標(biāo)值

考慮到任務(wù)分解過程在作戰(zhàn)籌劃階段的時(shí)效性要求,分解算法的時(shí)耗指標(biāo)也是評(píng)價(jià)算法性能的重要指標(biāo)。本文采用箱圖形式統(tǒng)計(jì)分析3種算法的消耗時(shí)間,如圖5所示。其中，INSGA-Ⅱ平均耗時(shí)68.096 3 s、MOEA/D平均耗時(shí)77.797 8 s、NSGA-Ⅱ平均耗時(shí)73.859 1 s。從圖5中可知，INSGA-Ⅱ耗時(shí)較少,MOEA/D耗時(shí)較多。INSGA-Ⅱ算法比傳統(tǒng)NSGA-Ⅱ算法在時(shí)耗上降低了7.8%,其原因在于通過引入任務(wù)分解粒度ω減少了子任務(wù)數(shù)量,降低了算法的運(yùn)算量,同時(shí)通過運(yùn)用改進(jìn)的精英保留策略按比例保留子代數(shù)量,減少了傳統(tǒng)精英保留策略中擁擠度計(jì)算量。雖然單次運(yùn)行節(jié)省時(shí)間僅為5 s,但為避免局部最優(yōu)通常需要多次運(yùn)行取最優(yōu)解,因此計(jì)算60次后能節(jié)省5 min。

6 結(jié) 論

本文基于傳統(tǒng)分解方法缺陷,引入數(shù)量可支持性約束和能力可支持性約束,對(duì)任務(wù)分解問題進(jìn)行了描述與分析,提出了一種任務(wù)主體二元約束下作戰(zhàn)任務(wù)分解EVA方法,并圍繞子任務(wù)集提取和子任務(wù)集調(diào)整方法進(jìn)行設(shè)計(jì)。針對(duì)子任務(wù)集提取,設(shè)計(jì)了全局任務(wù)空間的結(jié)構(gòu)化描述方式和目標(biāo)任務(wù)分解樹提取方法;針對(duì)子任務(wù)集調(diào)整,構(gòu)建了子任務(wù)集量化調(diào)整數(shù)學(xué)模型,并引入任務(wù)分解粒度,提出一種基于改進(jìn)型精英保留策略和交叉、變異概率動(dòng)態(tài)調(diào)整策略的INSGA-Ⅱ算法;最后,通過仿真實(shí)驗(yàn)驗(yàn)證INSGA-Ⅱ相較于傳統(tǒng)多目標(biāo)優(yōu)化算法在解集收斂性、多樣性和時(shí)間性能上的優(yōu)勢(shì),能夠支撐指揮員依據(jù)戰(zhàn)場(chǎng)實(shí)際選擇合適的子任務(wù)集量化調(diào)整方案。