一种用于解决最优特征选择与下一版本发布问题的量子退火方法

《Entropy》：A Quantum Annealing Approach for Solving Optimal Feature Selection and Next Release Problems

　　

搜索式软件工程（Search-based software engineering, SBSE）处理软件工程中的关键优化问题，包括下一版本发布问题（next release problem, NRP）和特征选择问题（feature selection problem, FSP）。传统的启发式方法和整数线性规划（integer linear programming, ILP）方法对于中小规模问题效果良好，但随着实例规模扩大，计算成本不断增加。研究人员研究了量子退火（quantum annealing, QA）作为多目标SBSE问题的优化子程序。研究人员提出了两种基于QA的算法，分别针对不同的问题规模。对于小规模问题，研究人员将多目标优化（multi-objective optimization, MOO）重新表述为单目标优化（single-objective optimization, SOO），使用基于惩罚的映射进行量子处理。对于超出当前硬件容量的大规模问题，研究人员采用了一种由最大能量影响（maximum energy impact, MEI）引导的分解策略，将问题划分为更小的子QUBO（Quadratic Unconstrained Binary Optimization, QUBO），并将QA与最速下降法相结合进行局部搜索。应用于NRP和FSP，研究人员的方法与启发式算法NSGA-II、IBEA和MOEA/D，以及基于ILP的ε约束法（ε-constraint）进行了基准测试。实验结果表明，尽管研究人员的方法产生的非支配解少于ε约束法，但执行时间大幅减少。与进化基线相比，研究人员的方法在能够编码的实例上以更低的运行时间实现了具有竞争力的解质量。基于惩罚的QUBO公式在约束密集的FSP实例上无法达到可行区域，限制了该方法当前的适用性。QA是一个有前景但硬件仍然受限的多目标SBSE工作流组件，而非经典求解器的全面替代品。

研究背景：软件工程中的搜索式软件工程（Search-based software engineering, SBSE）将关键决策问题建模为搜索优化，尤其是下一版本发布问题（next release problem, NRP）和特征选择问题（feature selection problem, FSP）。传统方法包括启发式多目标进化算法（multi-objective evolutionary algorithm, MOEA）和精确整数线性规划（integer linear programming, ILP），在中小规模实例上有效，但随规模增大计算成本急剧上升，甚至无法在合理时间内找到可行解。因此，需要高效新方法。量子退火（quantum annealing, QA）利用量子隧穿和叠加态探索解空间，已在组合优化中展现潜力，但尚未被系统应用于SBSE的多目标问题。本研究旨在探索QA作为优化子程序在NRP和FSP中的适用性，并评估其与经典方法的性能对比。

研究人员开展了什么：提出了两种基于QA的算法：针对小规模问题的多目标量子退火（Multi-Objective Quantum Annealing, MOQA）和针对大规模问题的经典-量子混合退火（Classical–Quantum Hybrid Annealing, CQHA）。MOQA通过加权聚合将多目标优化（multi-objective optimization, MOO）转为单目标优化（single-objective optimization, SOO），并利用惩罚项将约束编码为二次无约束二进制优化（Quadratic Unconstrained Binary Optimization, QUBO）模型，在D-Wave量子退火器上采样。CQHA采用最大能量影响（maximum energy impact, MEI）方法将大规模QUBO分解为多个子QUBO，分别由量子退火器求解，再通过组合和最速下降局部搜索得到最终解。实验使用来自ReleasePlanner项目的NRP数据集（MSWord, RP, Baan等）和SPLOT Search仓库的FSP数据集（WebPortal, Drupal, BerkeleyDB, ERS, E-Shop, toybox,