平台聚类编组问题作为军事指挥控制(command and control, C2)组织资源调度中的重点研究问题之一, 一直受到国内外研究人员的广泛关注^[1,2]. 现代战术行动中, 多平台协同编组是实现高效资源调度与动态任务分配的核心环节. 面对复杂战场环境中实时变化的平台位置、通信能力与任务优先级, 如何快速生成最优聚类方案以提升协同效能, 已成为军事运筹领域的关键挑战. 传统方法如k-means++^[3]或模拟退火算法虽能提供可行解, 但其计算复杂度随平台数量呈指数增长(O(2ⁿ)), 在大规模场景下面临严重的局部最优陷阱与收敛速度瓶颈. 例如, 当平台规模超过50时, 经典算法的聚类误差率骤增, 且无法满足分钟级规划需求. 这一矛盾在动态权重调整、异构资源匹配及硬性约束(如通信链路稳定性)的军事场景中尤为突出.

C2组织中的任务规划问题^[4,5]需要在充分考虑平台资源及其位置、任务资源及其位置等因素约束的前提下, 优化平台与任务、平台与平台之间的关联关系, 这属于大规模组合优化问题的范畴. 此类问题的求解通常基于启发式列表规划方法, 包括动态级别调度^[6]、多维动态列表调度(multidimensional dynamic list scheduling, MDLS)^[7]、多优先级列表动态调度(multipri list dynamic scheduling, MPLDS)^[8]等方法. 这些方法通常以最小化整体任务完成时间或最大化资源利用率为优化目标. 以MDLS和MPLDS方法为例, 两者的时间复杂度均为$ O\left(m{n}^{2}\right) $^[7–9], 其中$ m $为平台数量, $ n $为任务数量. 相比之下, C2组织中的任务规划问题往往对时间要求更高, 尤其在战时场景下, 亟需复杂度更低的算法进行求解. 随着量子计算机硬件的发展, 一些在经典超级计算机上难以模拟的量子算法现已能在量子计算机上运行^[10–16].

近年来, 量子近似优化算法^[17–19](quantum approximation optimization algorithm, QAOA)凭借其对组合优化问题的指数级加速潜力, 为突破此类瓶颈提供了新范式. QAOA最初主要应用于最大切割问题的求解, 被证明在求解速度上相对于现有经典算法具有指数级加速优势^[20–22]. 近年来研究成果^[23–28]表明, QAOA可以用来求解精确覆盖问题. 精确覆盖问题本质上属于NP问题, 在经典计算机上需要指数级时间开销; 而对于量子计算机来说, 只需要多项式级时间开销就可以求解. 这为C2组织任务规划问题求解提供了一定的理论借鉴. 为了缩短任务规划问题的求解时间, 采用QAOA求解C2组织中的任务规划问题, 是一种有理论意义且实践可行的方法.

由于战术行动中平台聚类编组问题涉及的平台种类和规模有限, 但对实时性要求较高, 所以本文选用新兴的变分量子算法QAOA. 该算法不仅适用于解决最大切割问题, 还可以用于解决组合优化问题. Zhang等^[29]针对NP完全问题中的最小顶点覆盖问题, 通过构建对应的伊辛模型推导出问题哈密顿量, 并基于该哈密顿量设计了QAOA量子线路的求解方案. 仿真结果表明, 该方案能够在多项式时间内以高概率获得较优解. Brandhofer等^[30]将股票投资组合问题投资组合优化问题转化为二元二次优化问题, 并采用不同版本的QAOA对其进行详细研究, 取得了良好的效果. 2021年, Koretsky等^[31]针对电力系统机组组合优化问题, 以最小化满足电力负荷的成本为目标函数, 采用QAOA进行优化计算, 并选用经典的最小优化器对QAOA进行扩展. Vikstål等^[32]针对目前航空公司面临的航班分配问题, 通过数学模型演变将航班分配问题映射为精确覆盖问题, 采用变分混合量子经典QAOA求解, 并利用航空公司实际数据对算法进行了验证.

在上述研究的启发下, 针对战术行动中的平台聚类编组问题, 本文提出一种基于QAOA的量子增强求解方法. 该方法将问题拆分为两阶段求解: 第1阶段将问题建模为整数背包问题, 通过量子伊辛模型与QAOA量子线路优化参数, 生成任务簇对应的平台簇集合; 第2阶段基于精确覆盖问题构建量子模型, 利用QAOA筛选符合条件的平台簇组合; 最终整合两阶段结果, 在基于Python 3框架下的量子软件开发环境和量子计算云服务平台中完成实验, 输出平台聚类的较优解.

针对战术行动中的平台聚类编组问题, 本文将其拆解为两个关联子问题分步求解: 首先, 基于资源供需约束, 将问题建模为整数背包问题, 筛选出满足各任务簇需求的平台簇组合(图1); 其次, 结合平台唯一归属与全集覆盖约束, 将其转化为精确覆盖问题, 从候选组合中选出全局最优分簇方案. 两阶段分别解决资源匹配与集合划分问题, 最终整合生成平台聚类的较优解(图2).

针对整数重量的背包问题, 可以构建一个经典伊辛模型$ {H}^{\prime}_{1} $:

其中$ {x}_{{{e}^{\prime}}} $为一个布尔变量, 当第$ {e}^{\prime} $个物体在背包中, $ {x}_{{{e}^{\prime}}} $=1, 当第$ {e}^{\prime} $个物体不在背包中, $ {x}_{{{e}^{\prime}}} $= 0; $ {k}^{\prime} $为整数, 当$ 1\leqslant {k}^{\prime}\leqslant {W}^{\prime} $且$ {k}^{\prime} $等于背包总重量时, $ {x}_{{{k}^{\prime}}} $= 1, 否则, $ {x}_{{{k}^{\prime}}} $= 0.

对于战术行动中平台聚类编组问题, 设任意一个任务簇$ \left\{t1, t2, \cdots , tn\right\}\in T $, 其中$ t1,\; t2,\; \cdots ,\; tn $为该任务簇包含的任务种类, n为任务簇包含的任务种类数量. 设该任务簇需求的作战资源为$ \left\{r1, r2, \cdots , r12\right\}\in r $, 其中$ r1,\; r2,\; \cdots ,\; r12 $分别代表12种作战资源类型, 设各作战资源类型对应的数量为$ {N}_{r1},\; {N}_{r2},\; \cdots ,\; {N}_{r12} $. 设平台集合为$ \left\{p1, p2, \cdots , p23\right\}\in p $, 其中$ p1,\; p2,\; \cdots ,\; p23 $为平台个数, 设每个平台提供的作战资源为$ \left\{R1, R2, \cdots , R12\right\}\in R $, 每个平台提供的作战资源对应的数量为$ N_{i}^{R1}, N_{i}^{R2},\; \cdots ,\; N_{i}^{R12} $, 其中$ i\in \left\{p1, p2, \cdots , p23\right\} $. 参照(1)式, 将平台看作物体, 将平台所提供的作战资源看作重量, 设定一个背包, 不同之处是这个背包设定了最低装载重量, 而背包的上限装载重量根据本文实际问题具体设定, 这样就可以构建一个针对平台聚类问题的经典伊辛模型$ {H}_{1} $:

其中, $ a=\left\{{a}_{r1}, {a}_{r2}, \cdots , {a}_{r12}\right\} $为实际问题中平台簇提供各种作战资源的上限取值, $ k1,\; k2,\; \cdots ,\; k12 $为整数, 当$ {N}_{r1}\leqslant k1\leqslant {a}_{r1},\; {N}_{r2}\leqslant k2\leqslant {a}_{r2},\; \cdots , {N}_{r12}\leqslant k12\leqslant {a}_{r12} $且$ k1,\; k2,\; \cdots ,\; k12 $分别等于平台簇提供的各种作战资源数量时, $ x_{k1}^{r1},\; x_{k2}^{r2},\; \cdots , \; x_{k12}^{r12} $分别等于1, 否则, $ x_{k1}^{r1},\; x_{k2}^{r2},\; \cdots ,\; x_{k12}^{r12} $分别等于0, e表示平台集合p中的任意一个平台, $ {x}_{e} $为一个布尔变量, 当平台e在背包中时, $ {x}_{e} $= 1, 当平台e不在背包中时, $ {x}_{e}=0 $, $ w_{e}^{R1},\; w_{e}^{R2},\; \cdots ,\; w_{e}^{R12} $表示平台e分别提供作战资源$ R1,\; R2,\; \cdots ,\; R12 $的数量.

基于精确覆盖问题可以描述为: 对于一个集合$ {U}^{\prime}=\left\{1, 2, \cdots , {n}^{\prime}\right\} $, 集合$ {V}^{\prime}_{i} $是集合$ {U}^{\prime} $的任意子集合, 即$ {V}^{\prime}_{i}\subseteq {U}^{\prime} $, 它们之间关系可以表示为

在上述条件基础上, 求出一个子集$ {Q}^{\prime} $, 该子集由若干个$ {V}^{\prime}_{i} $组成, 这些$ {V}^{\prime}_{i} $子集之间不相交并且并集为集合$ {U}^{\prime} $. 针对该问题可以构建一个经典伊辛模型$ {H}^{\prime}_{2} $:

其中, $ {a}^{\prime} $表示集合$ {U}^{\prime} $中任意元素, $ {x}^{\prime}_{i} $为一个布尔变量, 当集合$ {V}^{\prime}_{i} $中含有元素$ {a}^{\prime} $时, $ {x}^{\prime}_{i}=1 $, 当集合$ {V}^{\prime}_{i} $中没有含有元素$ {a}^{\prime} $时, $ {x}^{\prime}_{i}=0 $.

对于平台聚类问题, 设通过(2)式获得的平台分簇的集合为$ Q=\left\{{V}_{1}, {V}_{2}, \cdots , {V}_{{{N}_{q}}}\right\} $, 其中$ {N}_{q} $为获得集合的数量. 将平台集$ p=\left\{p1, p2, \cdots , p23\right\} $作为总集合, 结合(4)式, 可以计算推导出求解问题较优解对应的伊辛模型$ {H}_{2} $:

其中, a表示平台集p中任意元素, $ {x}_{i} $为一个布尔变量, 当集合$ {V}_{i} $中含有元素a时, $ {x}_{i}=1 $, 当集合$ {V}_{i} $中没有含有元素a时, $ {x}_{i}=0 $.

背包问题与精确覆盖问题均属于典型的NP完全问题, 如果想采用量子算法解决这些NP完全问题, 就需要首先建立起NP完全问题与量子算法之间的联系. 根据文献[29, 33]相关内容, 一个NP完全问题对应的经典伊辛模型与该问题对应的量子伊辛模型之间是有联系的, 通过选择合适的旋转算子, 利用问题的经典伊辛模型可以推导出与之对应的量子伊辛模型. 在量子绝热系统中, 问题的量子伊辛模型可以表示出量子系统对应的哈密顿量, 而哈密顿量在演化过程中逐渐趋于量子能量最低对应的本征态, 这样可以建立起问题经典伊辛模型与量子哈密顿量对应的本征态之间的联系. 而QAOA就是通过初态哈密顿量和末态哈密顿量构造的酉变换进行交替量子演化求出问题的较优解, 所以如果可以求出问题对应的哈密顿量就为QAOA提供了技术支撑.

对于战术平台中聚类编组问题, 本文已经分别构建了两个子问题对应的经典伊辛模型. 下面先详细计算推导第1阶段子问题的经典伊辛模型对应的哈密顿量.

根据伊辛模型$ {H}_{1} $组成结构, 发现其主要由两种结构的计算表达组成, 所以可以先对伊辛模型$ {H}_{1} $中部分计算表达式进行计算推导(前12项), 再扩展到整个伊辛模型$ {H}_{1} $中, 这样可以简化计算推导过程. 在伊辛模型$ {H}_{1} $中, 提取第1项表达式如下:

根据(6)式, 定义一个旋转变量$ s_{k1}^{r1}\in \left\{1, -1\right\} $, 则可以得到如下表达式:

将(7)式代入(6)式中, 经过计算推导可以得到如下表达式:

在(8)式中, $ {\left({a}_{r1}-{N}_{r1}+1\right)}^{2}/4+{N}_{r1}-{a}_{r1} $是一个常数, 可以用const表示, 设$ {A}_{r1}=\left({a}_{r1}-{N}_{r1}- 1\right) $, 加之$ s_{k}^{r1}s_{j}^{r1} $的系数具有对称性, 则(8)式可以进一步简化为

经过分析, 在伊辛模型$ {H}_{1} $公式中前12个表达式都是形如(6)式, 所以可以采用上述同样的计算推理过程, 将剩下的11个表达式也转化为(9)式的形式. 具体结果如下:

其中, $ 4\leqslant b\leqslant 14 $取整数, $ s_{k}^{ra}(2\leqslant a\leqslant 11,\; a $取整数)与$ s_{j}^{rb}(2\leqslant b\leqslant 12,\; b $取整数)均为取值范围为$ \{-1, 1\} $的对应旋转变量. 变量$ A_{rb} = (a_{rb}-N_{rb}-1) (2 \leqslant b \leqslant 12)$, b取整数和$ {({{a}_{rb}}-{{N}_{rb}}+1)}^{2}/4+ {N}_{rb}- {a}_{rb} $$ (2\leqslant b\leqslant 12) $ a取整数, 等均为常数, 可以用const表示.

在伊辛模型$ {H}_{1} $中, 在未转化部分继续提取第13项表达式如下:

同理, 根据(11)式, 定义两个旋转变量$ s_{k1}^{r1}\in \left\{1,-1\right\} $, $ {s}_{e}\in \left\{1, -1\right\} $, 则可以得到如下表达式:

将(12)式、(13)式代入(11)式中, 经过计算推导可以得到:

式中, $ {\left(\displaystyle\sum\nolimits_{k={N}_{r1}}^{{a}_{r1}}k-\displaystyle\sum\nolimits_{e\in p}w_{e}^{R1}\right)}^{2}/4 $为一个常数, 可以用const表示, 设${B}_{r1}=\left(\displaystyle \sum \nolimits_{k={N}_{r1}}^{{a}_{r1}}k-\sum\nolimits_{e\in p}w_{e}^{R1}\right) $, 加之$ s_{k}^{r1}s_{j}^{r1} $与$ {s}_{e}{s}_{\alpha } $的系数具有对称性, 则(14)式可化为

同理, 在伊辛模型$ {H}_{1} $公式中后12个表达式均形如(15)式, 可以采用上述同样的计算推理过程将其余11个表达式也转化为(15)式的形式. 具体结果如下:

其中, 16 ≤ A ≤ 26, A取整数, 2 ≤ b ≤ 12, b取整数.

同时, $ s_{k}^{ra}(2\leqslant a\leqslant 12,\; a$取整数) 和$ s_{j}^{rb}(2\leqslant b\leqslant 12,\;b $取整数)以及$ {s}_{\alpha },\; {s}_{e} $均为取值范围为$ \left\{1, -1\right\} $的对应旋转变量, 变量$ {B}_{rb}=\left(\displaystyle\sum\nolimits_{k={N}_{rb}}^{{a}_{rb}} k - \displaystyle\sum\nolimits_{e\in p} w_{e}^{Rb}\right) $, 2 ≤ b ≤ 12, b取整数和$ \left(\displaystyle\sum\nolimits_{k={N}_{rb}}^{{a}_{rb}} k-\displaystyle\sum\nolimits_{e\in p} w_{e}^{Rb}\right)^{2} / 4 $, 2 ≤ b ≤ 12等均为常数, 可以用const表示.

经过上述计算推导, 可以将伊辛模型$ {H}_{1} $对应的量子伊辛模型$ {H}_{27} $写成如下形式:

最后, 将(17)式中的旋转变量转化为对应的泡利Z算子, 因为公式中的常数项只会改变哈密顿量的整体相位, 而对哈密顿量对应的本征态或最小能量状态没有影响, 所以可以去掉常数项, 这样就可以将哈密顿量表达简化为

在计算推导出第1阶段子问题对应的哈密顿量后, 接着在经典伊辛模型((5)式)的基础上, 详细计算推导第2阶段子问题对应的哈密顿量. 根据伊辛模型$ {H}_{2} $组成结构, 定义一个旋转变量$ {s}_{i}\in \left\{1, -1\right\} $, 则可以得到如下表达式:

将(19)式代入(5)式中, 经过计算推导可以得到如下表达式:

式中, $ {\Big(1-\dfrac{1}{2}{N}_{q}\Big)}^{2} $是一个常数, 可以用const表示, $ {s}_{i}{s}_{j} $的系数具有对称性, 则(20)式可以进一步简化为

同理, 根据(21)式, 将式中的旋转变量转化为对应的泡利Z算子, 因为式中的常数项只对量子系统的整体状态和相位产生影响, 不影响量子系统的哈密顿量本征态或最小能量状态, 所以可以将常数项去掉, 这样就得到对应的哈密顿量表达形式:

设量子系统的初始基态为均匀分布的量子叠加态$ {\left| +\right\rangle }^{\otimes N} $, 与其对应的哈密顿量为$ \displaystyle\sum\nolimits_{n=1}^{N}\sigma _{n}^{X} $, 用$ {H}_{\text{B}} $表示, 设量子系统的末态对应的哈密顿量为$ {H}_{\text{C}} $. 量子线路中两个酉变换可以表示为

其中$ {H}_{\text{C}} $为要解决问题对应的哈密顿量((18)式和(22)式), $ {\gamma }_{i} $为参数; $ {H}_{\text{B}} $为$ \displaystyle\sum\nolimits_{n=1}^{N}\sigma _{n}^{X} $, 即所谓的混合哈密顿量, $ {\beta }_{i} $为参数.

根据量子演化原理, 将酉变换$ U\left({H}_{\text{C}}, {\gamma }_{i}\right) $和$ U\left({H}_{\text{B}}, {\beta }_{i}\right) $交替作用在量子初始叠加态$ {\left| +\right\rangle }^{\otimes N} $上, 实现量子系统的演化, 得到如下量子态形式:

其中$ \gamma =\left({\gamma }_{1}, {\gamma }_{2}, \cdots , {\gamma }_{k}\right) $, $ \beta =\left({\beta }_{1}, {\beta }_{2}, \cdots , {\beta }_{k}\right) $, k为交替演化次数.

量子态演化完毕后, 计算$ {H}_{\text{C}} $在$ \left| {\psi }_{k}\left(\gamma , \beta \right)\right\rangle $上的期望值, 并利用标准计算基$ \left| 0\right\rangle $或者$ \left| 1\right\rangle $对量子态$ \left| {\psi }_{k}\left(\gamma , \beta \right)\right\rangle $进行测量:

通过(25)式可以分析得出, 当$ {F}_{k}\left(\gamma , \beta \right) $表示的期望值越小, 表示能量越低的哈密顿量$ {H}_{\text{C}} $本征值对应的本征态出现的概率越高, 该本征态对应问题较优解. $ {H}_{\text{C}} $的最小化期望值所对应的参数$ \gamma $和$ \beta $取值可以表示为

其中$ \left({\gamma }^{\ast }, {\beta }^{\ast }\right) $表示参数经过优化后所取得的数值.

图3为基于QAOA量子线路的求解思路图, 由量子处理器和经典处理器两部分组成, 量子处理器部分主要完成量子态演化和测量; 经典处理器部分主要辅助量子处理器部分完成对参数$ \gamma $和$ \beta $的优化和调整. 在基于QAOA量子线路的求解思路基础上, 接下来需要对两个子问题对应的量子线路进行设计构建.

针对第1阶段子问题, 下面详细构建和设计一个基于QAOA的量子增强求解方法. 量子态演化主要在初始哈密顿量$ {H}_{\text{B}} $和问题哈密顿量$ {H}_{\text{C}} $基础上, 实现(23)式中$ U\left({H}_{\text{C}}, {\gamma }_{i}\right) $和$ U\left({H}_{\text{B}}, {\beta }_{i}\right) $两个酉变换乘积的累积, 这里用$ U\left(\gamma , \beta \right) $来表示. 如(27)式所示, 两个酉变换之间的乘积与每一步的量子线路相对应, k代表演化的步数, $ {\gamma }_{i} $和$ {\beta }_{i} $为每一次演化对应的参数. 其中第1部分量子态制备和第3部分量子态测量较为容易实现, 在补充材料A (online)中推导了第2部分量子态演化对应的量子线路:

根据(27)式, 在$ U\left({H}_{\text{B}}, {\beta }_{i}\right) $和$ U\left({H}_{\text{C}}, {\gamma }_{i}\right) $对应的量子线路基础上, 可以设计构造出$ U\left(\gamma , \beta \right) $对应的量子线路, 结合量子态制备和量子态测量, 就可以生成一个针对第1阶段子问题的基于QAOA的量子增强求解方法. 具体的量子线路如图4所示, 第2部分为演化步数k = 1, 如果演化步数k > 1时, 对应的第2部分量子线路重复k次. 因此第1阶段使用了47个量子比特、电路深度为7k+2, 门操作次数为13k+2.

下面针对第2阶段子问题, 也设计构建一个基于QAOA的量子增强求解方法. 在4.1节中对基于QAOA的量子线路主要组成部分已经进行了详细说明, 其中量子态制备和量子态测量部分对应的量子线路结构基本相同, 这里只对量子态演化部分对应的量子线路进行详细计算推导. 量子态演化部分对应的酉变换形如(27)式, 其中$ {H}_{\text{B}} $为初始态哈密顿量, 等于$ \displaystyle\sum\nolimits_{n=1}^{N}\sigma _{n}^{X} $, 所以对于$ U\left({H}_{\text{B}}, {\beta }_{i}\right) $这样以$ {H}_{\text{B}} $为生成元, $ {\beta }_{i} $为参数的酉变换参照之前的计算推导可以得到补充材料(A3)式的形式. $ {H}_{\text{C}} $为末态哈密顿量, 这里具体形式为

对于$ U\left({H}_{\text{C}}, {\gamma }_{i}\right) $这样以$ {H}_{\text{C}} $为生成元, $ {\gamma }_{i} $为参数的酉变换, 可以通过CNOT量子逻辑门和RZ量子逻辑门的组合操作或者RZ量子逻辑门的单独操作在量子线路中实现. 具体的计算推导过程见补充材料B (online).

以酉变换$ U\left({H}_{\text{C}}, {\gamma }_{i}\right) $对应的量子线路为基础, 结合量子态制备与量子态测量的量子线路构成, 就可以构造出一个针对第2阶段子问题的基于QAOA的量子增强求解方法. 具体的量子线路如图5所示, 与图4采用相似简化, 图中第2部分为演化步数k = 1, 如果演化步数k > 1时, 对应的第2部分量子线路重复k次. 因此第2阶段使用了$ {N}_{q} $个量子比特、电路深度为15k +2, 门操作次数为21k +2.

本实验主要是在基于Python3框架下的量子软件开发环境和量子计算云服务平台中完成的, 实验所用平台数据共涉及9类平台, 23个平台, 任务簇数4个, 各平台包含的具体资源属性类型有12种, 同类型的不同平台采用不同字符进行表示. 总共使用了47+N_q个量子比特, 电路深度为22k+4, 门操作次数为34k+4.

本文两个阶段子问题对应的基于QAOA的量子增强求解方法中待优化参数均为$ \left(\gamma , \beta \right) $, 在经典优化过程中, 将迭代次数分别设置为10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 对参数$ \left(\gamma , \beta \right) $展开调整优化并对结果进行对比分析. 接下来将对两个基于QAOA的量子增强求解方法的参数优化过程进行具体分析说明.

图6(a), (b)分别显示了两个基于QAOA的量子增强求解方法在实验过程中将迭代次数设置为10, 20, 30, 40, 50, 60, 70, 80, 90, 100的情况下, 演化步数设置为2—10时, 目标函数对应的损失值数值. 在演化步数相同的情况下, 从图6(a)可以分析得出, 将迭代次数设置为60时, 其对应的损失值的绝对值数值最大; 而从图6(b)分析得出, 将迭代次数设置为50时, 其对应的损失值的绝对值数值最大. 通过分析, 判断其原因主要是在经典优化算法优化过程中, 随着迭代次数的不断增加出现了过拟合现象. 在图6(a)中, 当迭代次数超过60后, 过拟合现象变得越来越严重, 优化结果变得也越来越差; 而在图6(b)中, 当迭代次数超过50后, 过拟合现象变得越来越明显. 在迭代次数相同的情况下, 无论是在图6(a)还是在图6(b)中, 随着演化步数的增加, 各个迭代次数对应下损失值的绝对值也都随之不断增大, 这种现象与量子线路相关理论是一致的.

图7为演化步数为10时, 迭代次数分别为60—100和50—100时, 两个基于QAOA的量子增强求解方法在实验过程中对应损失值的曲线图. 从图7(a)中可以明显看出, 当迭代次数设置为60时, 相较于其他情况其损失值的绝对值为最大取值(–6.38), 随着迭代次数不断增加, 分别取到70, 80, 90, 100时, 对应损失值的绝对值不断曲折下降. 同样从图7(b)可以明显看出, 当迭代次数设置为50时, 其损失值的绝对值取到最大值(–7.41), 随着迭代次数不断增至100时, 对应损失值的绝对值出现曲折下降现象. 因此, 在接下来的实验过程中, 针对两个阶段子问题将迭代次数分别设置为60和50, 并开展相关实验.

本文的目标是在将战役模拟演习项目的某次战术行动中作战任务细化分割为4个任务簇的基础上, 结合该次战术行动的作战平台实际情况, 实现可为每个任务簇提供所需作战资源的平台分簇. 将平台聚类编组问题转化为两个子问题后, 总的基于QAOA的量子增强求解方法流程图见图8.

图9表示迭代次数分别为60和50的情况下, 演化步数分别设置为2—10时, 两个阶段采用基于QAOA的量子增强求解方法分别取得对应问题较优解的概率. 图9(a)中较优解的概率值表示的是针对4个任务簇进行求解所得问题较优解的概率平均值. 从图9(a), (b)可以分析得出, 当演化步数逐渐增大时, 两个阶段取得对应问题较优解的概率都随之提升, 在演化步数为10时, 分别取得对应问题较优解的最大概率(71.3%和72.4%). 这个结果与量子线路相关理论和之前的实验结果都相吻合.

图10表示迭代次数分别为60和50的情况下, 演化步数设置为10时, 两个阶段采用基于QAOA的量子增强求解方法分别取得的测量结果. 为了便于表示, 这里将由0和1组成的解空间样本用十进制数字表示, 例如0101001用十进制表示为41. 图10(a)分别显示了第1, 2, 3和4任务簇对应的平台解空间样本, 在第1任务簇对应的平台解空间样本中, 问题的较优解272, 280和274等合并组成了问题较优解概率, 在第2任务簇对应的平台解空间样本中, 问题的较优解196, 197和204等合并组成了问题较优解概率, 在第3任务簇对应的平台解空间样本中, 问题的较优解33, 35和49等合并组成了问题较优解概率, 在第4任务簇对应的平台解空间样本中, 问题的较优解10, 26和42等合并组成了问题较优解概率. 图10(b)中, 问题的较优解557192, 1066000和2105604等合并组成了问题较优解概率. 从图10(a), (b)都可以看出, 问题较优解的概率明显高于其他解的概率. 从实验结果来看, 总体上可以表明本文提出的基于QAOA的量子增强求解方法可以解决战术行动中平台聚类编组问题.

与一些经典算法相比, 如多维动态列表规划法和多优先级列表动态规划法, 根据文献相关内容, 分析得出这两种算法时间复杂度约为$ O\left({n}^{2}\right) $, 而本文提出的基于QAOA的量子增强求解方法总的时间复杂为$ O\left(5 n+5 k\right) $. 主要由针对第1阶段子问题的基于QAOA的量子增强求解方法与针对第2阶段子问题的基于QAOA的量子增强求解方法组成. 这两种方法的计算过程都是由经典处理器部分和量子处理器部分组成, 经典处理部分主要采用动量梯度下降法对参数$ \gamma $和$ \beta $进行优化, 属于启发式策略优化方法, 其时间复杂度为$ O\left(n\right) $, 其中n为迭代次数. 量子处理部分主要消耗资源的是量子态的演化, 根据Zhou等^[33]的研究内容和本文实际设计的量子线路, 其时间复杂度为$ O\left(k\right) $, 其中k为演化步数, 因此这两种方法的时间复杂度都是$ O\left(n+k\right) $, 但由于在第1阶段子问题部分, 需要分别求解满足4个任务簇的平台簇, 所以该部分的时间复杂度为$ O\left(4 n+4 k\right) $, 而第2阶段子问题部分的时间复杂度为$ O\left(n+k\right) $, 因此本文提出的方法总的时间复杂度为$ O\left(5 n+5 k\right) $. 对于本文中具体计算的情况: 9种平台类型, 23个平台, 12种资源属性类型, 4组任务簇, MDLS算法的时间复杂度为$ O\left(23\times {4}^{2}\right)=O(368) $, 而本文基于QAOA的量子算法的时间复杂度为$ O\left(5\times 23+5\times 10\right)= O(165) $. 如表1所示, 在时间复杂度有较大幅度降低. 所以针对战术行动中平台聚类编组问题, 本文提出的基于QAOA的量子增强求解方法在时间复杂度方面明显优于一些经典算法.

针对战术行动中的平台聚类编组问题, 本文提出了一种基于QAOA的量子增强求解方法. 该方法将战术行动中平台聚类编组问题转化为两个相互关联的子问题, 并分别构建对应的基于QAOA的量子增强求解模型. 第1阶段子问题模型主要是为了寻找满足各任务分簇资源需求的平台组合(即平台簇); 第2阶段子问题模型则是为了在符合要求的平台簇中, 筛选出既能满足各任务簇的资源需求又互相不相交的平台簇集合. 实验结果表明, 所提出的方法可以有效解决战术行动中的平台聚类编组问题.