搜索

x
中国物理学会期刊

量子近似优化算法求解战术聚类编组问题

CSTR: 32037.14.aps.75.20251690

Quantum approximate optimization algorithm for the tactical clustering and grouping problems

CSTR: 32037.14.aps.75.20251690
PDF
HTML
导出引用
  • 针对战术行动中平台聚类编组的复杂约束问题, 本文提出一种基于量子近似优化算法(quantum approximation optimization algorithm, QAOA)的两阶段量子增强求解方法. 首先, 将问题拆分为资源匹配与平台归属两个关联子问题: 第1阶段基于整数背包问题构建量子伊辛模型, 设计QAOA量子线路并优化参数, 生成满足任务簇资源需求的候选平台簇集合; 第2阶段以精确覆盖问题为框架, 构建对应的量子模型并优化求解, 筛选满足平台唯一归属且全集覆盖的全局最优分簇方案. 通过经典问题向量子伊辛模型的映射, 结合参数化量子线路与经典优化器协同优化, 实现复杂约束下平台聚类的高效求解. 实验在基于Python 3框架的量子软件开发环境及量子计算云服务平台中完成, 结果表明, 所提方法在平台分配效率上较传统算法显著提升, 且在时间复杂度上明显优于其他传统算法. 与传统的多维动态列表规划法和多优先级列表动态规划法相比, 时间复杂度由 O(n^2) 降低到 O(5n+5k) .

     

    To address the challenge of complex multi-resource constraints in platform grouping for tactical operations, this study develops a quantum-enhanced solution optimization framework using the quantum approximate optimization algorithm (QAOA). By decomposing the problem into sequential phases of resource matching and cluster optimization, and leveraging a hybrid quantum-classical approach, the framework is designed to efficiently generate optimal platform grouping schemes. As shown in figure, first, the problem was decomposed into two interrelated subproblems: resource matching and platform assignment. A quantum Ising model was formulated for the integer knapsack problem, and a QAOA quantum circuit was designed. Parameter optimization was then performed to generate candidate platform clusters that satisfy task cluster resource requirements; second, leveraging the exact set cover problem as a framework, a corresponding quantum model was formulated and optimally solved using hybrid quantum-classical optimization. This process identified the globally optimal clustering scheme that ensures both platform uniqueness and complete set coverage; finally, an efficient solution for platform clustering under complex constraints was developed by reformulating the classical problem into a quantum Ising model and integrating a parameterized quantum circuit with classical optimizers through hybrid quantum-classical optimization. The experiments were conducted in a Python 3-based quantum software development environment and quantum computing cloud service platform. The experimental results demonstrate that the proposed quantum-enhanced optimization framework significantly outperforms traditional algorithms in platform allocation efficiency, with the time complexity reduced from O(n^2) to O(5n+5k) compared to conventional multi-dimensional dynamic list programming and multi-priority list dynamic programming methods, illustrating a distinct advantage. The study confirms that the QAOA-based framework can effectively address complex platform clustering and grouping problems in tactical operations, thereby laying a foundation for the application of quantum computing in command-and-control and resource optimization domains.

     

    目录

    /

    返回文章
    返回