用机器学习自动调参,提升量子退火求解图划分问题的精度与效率。
Minimum Bisection Problem: Machine Learning-Based Penalty Parameter Tuning for Optimization on Quantum Annealers
- 基于图结构特征预测最优惩罚参数区间,实现自动化调参。
- 在4000节点图上,所有实例均获得平衡划分,且割值优于经典算法Metis。
- 适合研究量子优化、图划分及机器学习辅助计算的学者参考。
最小二分问题是一个基础且计算困难的图划分问题,广泛应用于并行计算、网络设计和大规模数据处理。将其转化为无约束二次布尔优化问题以用于量子退火时,解的质量高度依赖于强制平衡划分的惩罚参数。该参数的选择具有问题依赖性,通常依赖人工调参或启发式方法。本文提出一种专为最小二分问题设计的机器学习驱动的自动惩罚参数调优方法。首先推导出基于图特性的初始惩罚估计值,再利用两个梯度提升回归模型,从节点数、图密度和初始估计值中预测有效惩罚乘子区间的端点。最终惩罚值由预测区间确定,并用于构建D-Wave量子退火求解器的模型。模型在607个Erdős-Rényi图上校准,以Metis和Kernighan-Lin作为经典基准,在126个独立生成的实例(最多4000个节点)上评估。在实验设置下,预测惩罚使混合求解器在所有测试实例中均返回平衡划分,且割值始终低于Metis。
原文摘要 · Abstract (English)
The Minimum Bisection Problem is a fundamental, computationally hard graph partitioning problem with applications in parallel computing, network design, and large-scale data processing. When formulated as a Quadratic Unconstrained Binary Optimization problem for quantum annealing, solution quality depends critically on the penalty parameter that enforces balanced partitions. Selecting this parameter is problem-dependent and typically relies on manual tuning or heuristics. This paper proposes a machine learning-based approach for automatic penalty-parameter tuning developed specifically for the Minimum Bisection Problem. We first derive a graph-dependent initial penalty estimate and then use two Gradient Boosting Regressor models to predict the endpoints of an effective penalty-multiplier interval from the number of nodes, graph density, and the initial estimate. The final penalty is obtained from the predicted interval and used to construct the model solved by D-Wave's quantum annealing solvers. The models were calibrated on 607 Erdős-Rényi graphs, with Metis and Kernighan-Lin as classical references, and evaluated on 126 independently generated instances with up to 4000 nodes. Under the adopted experimental setup, the predicted penalties enabled the hybrid solver to return balanced partitions for all evaluation instances and lower cut values than Metis in every case.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。