量子近似優(yōu)化算法在指揮控制組織任務(wù)規(guī)劃中的應(yīng)用

張毅軍 慕曉冬 劉瀟文 王星宇 東晨 吳田宜 李凱

1) (火箭軍工程大學(xué)研究生院,西安 710025)

2) (火箭軍工程大學(xué),西安 710025)

3) (國(guó)防科技大學(xué)信息通信學(xué)院,西安 710106)

4) (空軍工程大學(xué)信息與導(dǎo)航學(xué)院,西安 710077)

指揮控制組織中的任務(wù)規(guī)劃問(wèn)題可以映射為變量較多、求解難度較大的組合優(yōu)化問(wèn)題.采用傳統(tǒng)具有啟發(fā)性列表規(guī)劃方法解決這一問(wèn)題面臨求解時(shí)間復(fù)雜度高、實(shí)時(shí)響應(yīng)性較差等問(wèn)題.本文針對(duì)指揮控制組織中任務(wù)規(guī)劃問(wèn)題提出一種基于量子近似優(yōu)化算法的量子線路求解方案.首先將任務(wù)規(guī)劃問(wèn)題轉(zhuǎn)化為組合優(yōu)化中的精確覆蓋問(wèn)題,通過(guò)構(gòu)建相應(yīng)的數(shù)學(xué)模型推導(dǎo)出精確覆蓋問(wèn)題的量子近似優(yōu)化算法對(duì)應(yīng)的末態(tài)哈密頓量表達(dá)式;設(shè)計(jì)了基于量子近似優(yōu)化算法的量子線路,采用動(dòng)量梯度下降法算法對(duì)量子邏輯門中的參數(shù)進(jìn)行優(yōu)化,并利用本源量子開(kāi)發(fā)的量子軟件開(kāi)發(fā)環(huán)境進(jìn)行仿真實(shí)驗(yàn).仿真結(jié)果表明:該量子線路方案可以用于求解任務(wù)規(guī)劃問(wèn)題,同時(shí)降低了算法的時(shí)間復(fù)雜度,一定程度上提升了資源利用率,為進(jìn)一步應(yīng)用量子算法求解指揮控制組織中的任務(wù)規(guī)劃問(wèn)題打下基礎(chǔ).

1 引言

指揮控制(command and control,C2)組織是軍事領(lǐng)域面向特定的使命任務(wù),為實(shí)現(xiàn)作戰(zhàn)資源有序利用,通過(guò)多種關(guān)聯(lián)關(guān)系有機(jī)結(jié)合戰(zhàn)場(chǎng)上各單元而形成的作戰(zhàn)組織實(shí)體[1].C2 組織通過(guò)構(gòu)建平臺(tái)與任務(wù)之間的執(zhí)行關(guān)系、決策實(shí)體與平臺(tái)之間的指揮控制關(guān)系、各個(gè)決策實(shí)體之間的協(xié)作關(guān)系等實(shí)現(xiàn)面向任務(wù)的組織結(jié)構(gòu)設(shè)計(jì)[2].其中,平臺(tái)與任務(wù)之間執(zhí)行關(guān)系（即任務(wù)規(guī)劃問(wèn)題）是C2 組織設(shè)計(jì)中的首要環(huán)節(jié),屬于涉及變量最多、求解難度最大的組合優(yōu)化問(wèn)題.

C2 組織中的任務(wù)規(guī)劃問(wèn)題需要在充分考慮平臺(tái)資源、位置,任務(wù)資源、位置等制約因素前提下,優(yōu)化平臺(tái)與任務(wù)、平臺(tái)與平臺(tái)之間的各種關(guān)系.這屬于大規(guī)模組合優(yōu)化問(wèn)題的范疇,也是NP 問(wèn)題.解決此類問(wèn)題一般主要采用具有啟發(fā)性的列表規(guī)劃方法進(jìn)行求解.這些方法包括動(dòng)態(tài)層級(jí)規(guī)劃算法(dynamic level scheduling,DLS)[3]、多維動(dòng)態(tài)列表規(guī)劃算法 (multidimensional dynamic list scheduling,MDLS)[4]、多優(yōu)先級(jí)列表動(dòng)態(tài)規(guī)劃算法 (multi-PRI list dynamic scheduling,MPLDS)[5].這些方法通常都是以整個(gè)任務(wù)完成時(shí)間最短或者以資源的充分利用為目標(biāo)求解問(wèn)題.以MDLS和MPLDS方法為例,兩種方法的時(shí)間復(fù)雜度為其中m為平臺(tái)數(shù)量,n為任務(wù)數(shù)量.而C2 組織中的任務(wù)規(guī)劃問(wèn)題往往對(duì)時(shí)間要求較高,特別是在戰(zhàn)時(shí),需要復(fù)雜度更低的算法來(lái)解決.隨著量子計(jì)算機(jī)硬件的發(fā)展,一些在經(jīng)典超級(jí)計(jì)算機(jī)上都很難模擬的量子算法現(xiàn)在可以在量子計(jì)算機(jī)上運(yùn)行[7].如文獻(xiàn)[8-13]顯示,目前,量子近似優(yōu)化算法(quantum approximate optimization algorithm,QAOA)[14]有望在量子計(jì)算機(jī)上實(shí)現(xiàn),其理論基礎(chǔ)已被谷歌、IBM、本源量子等研究機(jī)構(gòu)在量子計(jì)算機(jī)上進(jìn)行了實(shí)驗(yàn)驗(yàn)證.它是一種用于解決組合優(yōu)化問(wèn)題的啟發(fā)式混合量子經(jīng)典算法,由愛(ài)德華·法希等首次提出,可以看作是絕熱量子計(jì)算的時(shí)間離散化[15].QAOA 最初主要應(yīng)用于最大切割問(wèn)題的求解,被證明對(duì)求解速度相對(duì)于現(xiàn)有經(jīng)典算法而言具有指數(shù)級(jí)加速[16-18].近年來(lái)研究成果表明[19-24],QAOA可以用來(lái)求解精確覆蓋問(wèn)題.精確覆蓋問(wèn)題本質(zhì)屬于NP 問(wèn)題[25],在經(jīng)典計(jì)算機(jī)上需要指數(shù)級(jí)時(shí)間開(kāi)銷;而對(duì)于量子計(jì)算機(jī)來(lái)說(shuō),只需要多項(xiàng)式級(jí)時(shí)間開(kāi)銷就可以求解.這為C2 組織任務(wù)規(guī)劃問(wèn)題求解提供了一定的理論借鑒.為了縮短任務(wù)規(guī)劃問(wèn)題的求解時(shí)間,采用QAOA 求解C2 組織中的任務(wù)規(guī)劃問(wèn)題是一種有意義的且可行的方法.

本文通過(guò)對(duì)C2 組織中的任務(wù)規(guī)劃問(wèn)題進(jìn)行分析和簡(jiǎn)化,將該問(wèn)題映射成為一個(gè)組合優(yōu)化中的精確覆蓋問(wèn)題;在上述構(gòu)建問(wèn)題數(shù)學(xué)模型的基礎(chǔ)上,推導(dǎo)出QAOA 對(duì)應(yīng)的末態(tài)哈密頓量表示形式;設(shè)計(jì)適用于求解C2 組織中的任務(wù)規(guī)劃問(wèn)題的QAOA 對(duì)應(yīng)量子線路;通過(guò)采用經(jīng)典優(yōu)化算法對(duì)量子線路參數(shù)進(jìn)行優(yōu)化,采用本源量子開(kāi)發(fā)的pyQPanda 量子軟件開(kāi)發(fā)環(huán)境在Python3 中進(jìn)行仿真,并對(duì)結(jié)果進(jìn)行分析討論.

2 C2 組織中的任務(wù)規(guī)劃問(wèn)題的轉(zhuǎn)化

本文以最小化整個(gè)任務(wù)流程完成時(shí)間為優(yōu)化目標(biāo)構(gòu)建模型,用P表示平臺(tái)集合,用A表示任務(wù)集合.用Fap=1 表示p平臺(tái)執(zhí)行a任務(wù),用Fap=0 表示p平臺(tái)沒(méi)有執(zhí)行a任務(wù).用Cp=1 表示p平臺(tái)被選中執(zhí)行任務(wù),用Cp=0 表示p平臺(tái)沒(méi)有被選中執(zhí)行任務(wù).Tap表示p平臺(tái)執(zhí)行a任務(wù)所用的時(shí)間.Tp表示p平臺(tái)執(zhí)行完分配的任務(wù)所用時(shí)間.T表示指揮控制組織系統(tǒng)完成所有任務(wù)所用時(shí)間.需要說(shuō)明的是,為更好構(gòu)建模型,對(duì)平臺(tái)資源進(jìn)行了約束,假設(shè)所選平臺(tái)都可以獨(dú)立完成任務(wù).C2 組織任務(wù)規(guī)劃通用模型如下所示:

其中目標(biāo)函數(shù)是最小化整個(gè)任務(wù)流程完成時(shí)間,約束條件(2)式確保每一個(gè)任務(wù)都有且僅有一個(gè)平臺(tái)執(zhí)行,約束條件(3)式限制Fap和Cp的取值范圍.

準(zhǔn)確高效地求解上述模型是實(shí)現(xiàn)C2 組織任務(wù)規(guī)劃的關(guān)鍵.為提高模型求解效率、縮短問(wèn)題求解時(shí)間,實(shí)現(xiàn)任務(wù)盡可能及時(shí)準(zhǔn)確被執(zhí)行,將問(wèn)題轉(zhuǎn)化為在確保所有任務(wù)被執(zhí)行的前提下,在已有的平臺(tái)執(zhí)行方案中選出滿足(2)式和(3)式約束條件的解決方案.而這些已有的平臺(tái)執(zhí)行方案都是從經(jīng)過(guò)優(yōu)化的平臺(tái)執(zhí)行方案數(shù)據(jù)庫(kù)中隨機(jī)選取的,將問(wèn)題轉(zhuǎn)化成一個(gè)精確覆蓋問(wèn)題不僅可以確保所有任務(wù)被執(zhí)行,還可以減少平臺(tái)需求數(shù)量,提升平臺(tái)利用率.

3 基于QAOA 的C2 任務(wù)規(guī)劃問(wèn)題求解

根據(jù)文獻(xiàn)[26,27]論述的研究?jī)?nèi)容,大部分的NP 完全問(wèn)題和NP 問(wèn)題(包括精確覆蓋問(wèn)題)都可以生成對(duì)應(yīng)的經(jīng)典伊辛模型.而根據(jù)文獻(xiàn)[25,28]論述的研究?jī)?nèi)容,經(jīng)典伊辛模型可以通過(guò)定義旋轉(zhuǎn)算子的方式轉(zhuǎn)化為量子伊辛模型,而通過(guò)量子伊辛模型可以描述量子系統(tǒng)的哈密頓量.這樣就可以將求解NP 問(wèn)題與求解量子伊辛模型對(duì)應(yīng)的哈密頓量的本征態(tài)或最小能量狀態(tài)聯(lián)系起來(lái),使采用QAOA進(jìn)行求解問(wèn)題成為可能.本文將精確覆蓋問(wèn)題的量子伊辛模型對(duì)應(yīng)的哈密頓量表示如下:

Hc為目標(biāo)哈密頓量(也是QAOA 對(duì)應(yīng)的末態(tài)哈密頓量),n和j分別表示第n個(gè)和第j個(gè)量子比特位,它們的取值范圍為 1≤n,j≤N;和表示作用在第n個(gè)量子比特位和第j個(gè)量子比特位上的泡利Z算符;Gnj和qn為相關(guān)系數(shù),屬于常量.

3.1 任務(wù)規(guī)劃問(wèn)題對(duì)應(yīng)的伊辛模型

如前所述,求出問(wèn)題的解,必須滿足(2)式和(3)式的約束,所以以(2)式和(3)式為基礎(chǔ)推導(dǎo)該問(wèn)題對(duì)應(yīng)的伊辛模型.首先在(2)式兩邊同時(shí)減1;然后在(2)式兩邊同時(shí)進(jìn)行平方;最后在所有任務(wù)上進(jìn)行累加運(yùn)算,可以得出如下表達(dá)式:

其中|P|表示平臺(tái)集合P的數(shù)量,|A|表示任務(wù)集合A的數(shù)量.如果(5)式等于0,那么所有約束條件都能得到滿足.下面用旋轉(zhuǎn)變量Sp ∈{-1,1}代替Cp ∈{0,1},公式如下:

而后將(6)式代入(5)式,并將(5)式展開(kāi),可以得出如下表達(dá)式:

如果用泡利旋轉(zhuǎn)算子替換(11)式中的旋轉(zhuǎn)變量,就可以得到形如 (4)式的精確覆蓋問(wèn)題的量子伊辛模型對(duì)應(yīng)的哈密頓量表達(dá)式.此表達(dá)式中的常量只改變哈密頓量的整體相位,而對(duì)哈密頓量對(duì)應(yīng)的本征態(tài)或最小能量狀態(tài)沒(méi)有影響.

3.2 基于QAOA 算法的求解思路

首先我們需要制備一個(gè)初態(tài),即一個(gè)均勻分布的量子疊加態(tài)|+〉?N;然后需要以HC和HB兩個(gè)哈密頓量為生成元制備兩個(gè)酉變換,它們分別為

(15)式中 (γ*,β*)為參數(shù)γ和β經(jīng)過(guò)優(yōu)化后所取得數(shù)值.

基于QAOA 的任務(wù)規(guī)劃問(wèn)題求解過(guò)程如圖1所示,主要由量子處理器和經(jīng)典處理器兩部分組成.經(jīng)典處理器部分為輔助模塊,主要采用經(jīng)典優(yōu)化方法對(duì)參數(shù)γ和β進(jìn)行優(yōu)化,輔助量子處理器部分完成對(duì)酉變化中參數(shù)γ和β取值的調(diào)整;量子處理器部分為主體模塊,主要采用QAOA 算法進(jìn)行量子態(tài)演化和問(wèn)題求解.

圖1 QAOA 實(shí)現(xiàn)框架示意圖Fig.1.Schematic diagram of the QAOA implementation.

3.3 基于QAOA 的量子線路設(shè)計(jì)方案

與經(jīng)典計(jì)算相對(duì)應(yīng),量子計(jì)算機(jī)通過(guò)量子線路來(lái)執(zhí)行程序.為了使QAOA 在量子軟件開(kāi)發(fā)環(huán)境中運(yùn)行,需要設(shè)計(jì)相應(yīng)的量子線路.

本文設(shè)計(jì)的QAOA 量子線路主要包含三個(gè)環(huán)節(jié),如圖2所示.首先是制備量子初態(tài)|+〉?N,主要通過(guò)給每個(gè)量子比特作用一個(gè)H門來(lái)實(shí)現(xiàn).然后實(shí)現(xiàn)以HC和HB兩個(gè)哈密頓量為生成元,得到兩個(gè)酉變換乘積的累積U(γ,β),

圖2 基于QAOA 的4 個(gè)量子比特量子線路圖Fig.2.Four-qubit quantum circuit based on QAOA.

(16)式中k代表演化的步數(shù),兩個(gè)酉變換之間的乘積代表每一步對(duì)應(yīng)的量子線路;βi和γi為每一步對(duì)應(yīng)的參數(shù).一般演化的步數(shù)越大,量子線路得到的效果就越好.最后采用計(jì)算基進(jìn)行測(cè)量.其中第一部分和第三部分都比較容易實(shí)現(xiàn),下面重點(diǎn)推導(dǎo)第二部分的量子線路.

對(duì)于以HB為生成元、參數(shù)為βi的酉變換,將哈密頓量HB的值代入,可以推導(dǎo)出一組 RX 門操作.推導(dǎo)如下:

對(duì)于以HC為生成元,參數(shù)為γi的酉變換,將哈密頓量HC的值代入,可以推導(dǎo)出 CNOT門和RZ 門的組合操作以及一組 RZ 門單獨(dú)操作.推導(dǎo)如下:

如圖2所示,環(huán)節(jié)2 為演化步數(shù)為1 時(shí)對(duì)應(yīng)的量子線路圖.如果演化步數(shù)為k時(shí),對(duì)應(yīng)的第二部分量子線路重復(fù)k次.

4 仿真結(jié)果與分析

4.1 迭代次數(shù)的優(yōu)化與分析

本文對(duì)6 種平臺(tái)12 種任務(wù)的C2 組織任務(wù)規(guī)劃問(wèn)題進(jìn)行實(shí)驗(yàn)研究,問(wèn)題相關(guān)信息在表1中詳細(xì)列出.在整個(gè)實(shí)驗(yàn)過(guò)程中,為了使QAOA 得到理想的結(jié)果,在經(jīng)典計(jì)算部分必須能夠取得較優(yōu)的(γ*,β*)數(shù)值.這部分通常采用的經(jīng)典優(yōu)化算法有梯度下降算法、Broyden-Fletcher-Goldfarb-Shanno(BFGS)算法[29]、Nelder-Mead 算法[30]和貝葉斯優(yōu)化算法[31],采用動(dòng)量梯度下降法,在Python3 運(yùn)行環(huán)境下實(shí)現(xiàn).為了得到較優(yōu)的 (γ*,β*),我們?cè)诮?jīng)典優(yōu)化過(guò)程中分別將迭代次數(shù)設(shè)置為10,20,30,40,50,60,70,80,90和100 進(jìn)行計(jì)算,并對(duì)結(jié)果進(jìn)行對(duì)比分析.

表1 平臺(tái)對(duì)應(yīng)可執(zhí)行任務(wù)分配方案Table 1.Platforms corresponding executable mission allocation.

圖3所示為迭代次數(shù)為10,20,30,40,50,60,70,80,90和100 情況下,演化步數(shù)k從2 至12,目標(biāo)函數(shù)對(duì)應(yīng)的損失值（因?yàn)槟繕?biāo)函數(shù)對(duì)應(yīng)的損失值趨近于負(fù)的const,所以目標(biāo)函數(shù)絕對(duì)值越大表示得到的 (γ*,β*) 數(shù)值越優(yōu),取得正確解的概率越大）.水平坐標(biāo)分別表示迭代次數(shù)和演化步數(shù),縱坐標(biāo)表示目標(biāo)函數(shù)對(duì)應(yīng)的損失值.圖3中結(jié)果顯示在演化步數(shù)相同的情況下,迭代次數(shù)為50 對(duì)應(yīng)的損失值的絕對(duì)值普遍高于其他迭代次數(shù)對(duì)應(yīng)的損失值的絕對(duì)值.這是因?yàn)殡S著迭代次數(shù)增大,算法在計(jì)算的過(guò)程中出現(xiàn)了過(guò)擬合現(xiàn)象.如圖4所示為在演化步數(shù)為12 時(shí),迭代次數(shù)分別為50,60,70,80,90和100 對(duì)應(yīng)損失值的曲線圖.而在迭代次數(shù)相同的情況下,隨著演化步數(shù)增加,對(duì)應(yīng)損失值的絕對(duì)值也隨之增加,這與相關(guān)理論完全吻合.所以,在接下來(lái)的實(shí)驗(yàn)中,將迭代次數(shù)設(shè)置為50 進(jìn)行實(shí)驗(yàn)研究.

圖3 不同迭代次數(shù)和演化步數(shù)對(duì)應(yīng)的損失值Fig.3.Loss values corresponding to different iterations and evolution steps.

圖4 演化步數(shù)為12,迭代次數(shù)分別為50-100 對(duì)應(yīng)的損失值Fig.4.The corresponding loss values with 12 evolution steps and 50-100 iterations,respectively.

4.2 仿真結(jié)果分析

本文主要利用本源量子開(kāi)發(fā)的pyQPanda 量子軟件開(kāi)發(fā)環(huán)境在Python3 中對(duì)上述設(shè)計(jì)的量子線路進(jìn)行仿真實(shí)現(xiàn).圖5表示的是在迭代次數(shù)為50 情況下,2 至12 指定演化步數(shù)對(duì)應(yīng)的問(wèn)題正確解概率.圖5顯示隨著演化步數(shù)的增加,問(wèn)題正確解概率隨著增大,在演化步數(shù)為12 時(shí)取得了最大值(89%).圖6顯示了迭代次數(shù)為50,演化步數(shù)為12 對(duì)應(yīng)的測(cè)量結(jié)果.從結(jié)果可以得出,本文中提出的基于QAOA 的求解方案可以用于求解C2 組織中任務(wù)規(guī)劃問(wèn)題.

圖5 迭代次數(shù)為50,演化步數(shù)為2 至12 對(duì)應(yīng)的問(wèn)題正確解概率Fig.5.The accuracy of the QAOA with 50 iterations and 2-12 evolution steps.

圖6 迭代次數(shù)為50,演化步數(shù)為12 對(duì)應(yīng)的測(cè)量結(jié)果Fig.6.Results with 50 iterations and 12 evolution steps.

4.3 基于QAOA 的求解方案復(fù)雜度分析

采用了動(dòng)量梯度下降法對(duì)量子線路中的參數(shù)進(jìn)行優(yōu)化,屬于啟發(fā)式策略優(yōu)化方法.結(jié)合文獻(xiàn)[32]的研究?jī)?nèi)容和本文仿真實(shí)驗(yàn)設(shè)計(jì),提出的基于QAOA 的量子線路求解方案的時(shí)間復(fù)雜度為O[poly(k)],其中k為上述中的演化步數(shù).而傳統(tǒng)的求解算法時(shí)間復(fù)雜度為,其中m為平臺(tái)數(shù)量,n為任務(wù)數(shù)量.所以,隨著平臺(tái)和任務(wù)數(shù)量的增加,基于QAOA 的量子線路求解方案的時(shí)間復(fù)雜度要優(yōu)于傳統(tǒng)求解算法時(shí)間復(fù)雜度.

5 結(jié)論

本文根據(jù)C2 組織中的任務(wù)規(guī)劃問(wèn)題特點(diǎn),將其轉(zhuǎn)化成組合優(yōu)化中的精確覆蓋問(wèn)題.通過(guò)理論推導(dǎo)提出了一種基于QAOA 算法的量子線路求解方案,并利用經(jīng)典優(yōu)化算法對(duì)量子邏輯門中的參數(shù)進(jìn)行優(yōu)化,在本源量子開(kāi)發(fā)的pyQPanda 量子軟件開(kāi)發(fā)環(huán)境中進(jìn)行仿真編譯.仿真結(jié)果表明,本文提出的基于QAOA 的量子線路設(shè)計(jì)及方法可以有效求解C2 組織中的任務(wù)規(guī)劃問(wèn)題,為提高任務(wù)規(guī)劃問(wèn)題的求解速度提供了理論支撐.經(jīng)過(guò)分析,本文所采用的QAOA 算法是一種普適的方法.實(shí)際中能轉(zhuǎn)化為組合優(yōu)化中的精確覆蓋問(wèn)題的實(shí)際問(wèn)題都可以嘗試采用本文的求解方案進(jìn)行求解.下一步將通過(guò)采用一些群智能算法[33]進(jìn)一步優(yōu)化適用于求解任務(wù)規(guī)劃問(wèn)題的QAOA 算法設(shè)計(jì)與實(shí)現(xiàn),在降低經(jīng)典計(jì)算部分復(fù)雜度的同時(shí)提高參數(shù)的優(yōu)化效果;另一方面對(duì)量子線路中的量子邏輯門進(jìn)行優(yōu)化,在降低演化步數(shù)的同時(shí)提高計(jì)算的正確率.

感謝國(guó)防科技大學(xué)信息通信學(xué)院劉雍講師、王勛講師的討論和幫助.