簡易檢索 / 詳目顯示

回結果列表
研究生： 陳昱廷
Chen, Yu-Ting
論文名稱： 基於神經網路輔助之數位退火暖啟動策略於 QUBO 最佳化中的應用
Neural Network aided Warm-Start Strategy for Digital Annealing in QUBO Optimization
指導教授： 舒宇宸
Shu, Yu-Chen
學位類別： 碩士
Master
系所名稱： 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年： 2026
畢業學年度： 114
語文別： 英文
論文頁數： 86
中文關鍵詞： 二次無約束二元最佳化 、數位退火 、暖啟動 、神經網路初始化 、局部搜尋 、組合最佳化
外文關鍵詞： Quadratic unconstrained binary optimization, digital annealing, warm start, neural-network initialization, local search, combinatorial optimization
相關次數： 點閱：3  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 二次無約束二元最佳化（Quadratic Unconstrained Binary Optimization, QUBO）是一類具 NP-hard 特性的組合最佳化問題，廣泛應用於排程、製造與資源分配等領域。雖然數位退火器能在大規模 QUBO 問題上取得高品質解，但求解時間仍可能成為主要瓶頸。因此，本研究提出一個神經網路導向的暖啟動框架，以提升 QUBO 最佳化的計算效率。

    本方法首先由 QUBO 矩陣萃取人工設計特徵，並以輕量化神經網路預測各位元取值為一的機率。接著，透過閾值法與伯努利抽樣產生候選二元解，再利用 best-improvement one-flip 局部搜尋進行改善，最後選取能量最低的候選解，作為富士通數位退火器的暖啟動初始解。

    本研究使用仁寶 Quantix GPU Annealer 產生監督式學習所需的高品質參考解，並以富士通數位退火器比較冷啟動與暖啟動的求解表現。首先，以 50 個變數的 Compal QUBO 進行小規模驗證，結果顯示兩種設定皆取得相同的最終目標函數值，且求解時間相近。主要實驗則在 3000 個變數的 Compal QUBO 與 synthetic subset-sum QUBO 上進行，並比較 beam-1 與 beam-4 兩種設定。

    完整暖啟動時間包含特徵建構、張量轉換、神經網路推論、候選解生成、局部搜尋，以及 Digital Annealer 求解時間。在此評估方式下，Compal QUBO 於 beam-1 與 beam-4 的端到端加速比分別約為 1.39 倍與 1.46 倍；synthetic subset-sum QUBO 則分別約為 1.09 倍與 1.15 倍。

    四組主要實驗中，暖啟動總時間皆低於對應的冷啟動求解時間中位數，且兩者皆維持相同的最佳最終目標函數值。整體而言，實驗結果顯示，結合候選解抽樣與局部搜尋的神經網路導向暖啟動方法，可有效提升大規模退火式 QUBO 最佳化的端到端效率，同時維持解的品質。

    Quadratic Unconstrained Binary Optimization (QUBO) is a fundamental NP-hard problem with broad applications in combinatorial optimization. Although digital annealers can obtain high-quality solutions for large-scale QUBO instances, their runtime may still become a bottleneck. This work proposes a neural-guided warm-start framework that predicts bit-wise probabilities from handcrafted QUBO features, generates binary candidates through thresholding and Bernoulli sampling, refines them using best-improvement one-flip local search, and submits the lowest-energy candidate to the Fujitsu Digital Annealer.

    Experiments are conducted on Compal and synthetic subset-sum QUBO instances. A 50-dimensional Compal instance is used as a small-scale sanity check, for which cold-start and warm-start executions show nearly identical solve times and the same final objective value. The main experiments are performed on 3000-dimensional instances under beam-1 and beam-4 settings.

    Including the measured warm-start preprocessing time, the proposed method achieves end-to-end speedups of approximately 1.39 times and 1.46 times on the Compal instance, and 1.09 times and 1.15 times on the subset-sum instance, under beam-1 and beam-4, respectively. In all four main experiments, the total warm-start runtime is lower than the corresponding cold-start median, while the same reported best final objective value is preserved.

    These results indicate that neural-guided initialization, combined with candidate sampling and local-search refinement, can improve the end-to-end efficiency of large-scale annealing-based QUBO optimization.

    Abstract i 摘 要 ii 誌 謝 iii Contents iv List of Tables vii List of Figures viii Chapter 1 Introduction 1 1.1 Background on Quadratic Unconstrained Binary Optimization 1 1.2 Annealing-Based Optimization 2 1.3 Machine Learning for Combinatorial Optimization 4 1.4 Motivation and Contribution 5 Chapter 2 Preliminaries 7 2.1 Quadratic Unconstrained Binary Optimization 7 2.2 Subset-Sum Problem as a QUBO Instance 8 2.3 Annealing-Based Solving Process 9 2.4 Fujitsu Digital Annealer 11 2.5 Compal Quantix GPU Annealer 13 2.6 Binary Local Search 16 2.7 ReLU and Sigmoid 18 Chapter 3 Proposed Method 20 3.1 Overview 20 3.2 Bit-Wise Feature Construction 24 3.3 Neural Predictor Architecture 27 3.3.1 Bit-wise Projection MLP 32 3.3.2 Global Mean Pooling 33 3.3.3 Prediction Head MLP 34 3.3.4 Probability Output 35 3.4 Loss Function and Training Objective 35 3.5 Candidate Generation 38 3.6 Local Search Refinement 39 Chapter 4 Numerical Experiments 42 4.1 Data Representation and Learning Setup 43 4.1.1 Compal QUBO Data Generation 44 4.1.2 Permutation Augmentation 45 4.1.3 Feature Construction 47 4.1.4 Synthetic Subset-Sum QUBO Data 49 4.1.5 Supervised Learning Setup 52 4.1.6 Training Hyperparameters 53 4.2 Warm-Start Annealing Protocol 54 4.3 Evaluation Objective 55 4.4 Warm-Start Performance 57 4.4.1 Summary of the Main 3000-Dimensional Results 58 4.4.2 Detailed Solve-Time Statistics 59 4.4.3 Warm-Start Preprocessing Time 62 4.4.4 Discussion of the Main Results 63 4.4.5 Small-Scale Sanity Check 64 4.5 Effect of Beam Size and Bernoulli Candidate Sampling 65 4.6 Subset-Sum QUBO Experiment 67 4.7 Discussion 68 Chapter 5 Conclusion 70 5.1 Conclusion 70 Bibliography 74

    [1] Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, and Yang Wang. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28:58–81, 2014.

    [2] Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2:5, 2014.

    [3] C. H. Ou, Y.-C. Lin, W.-Y. Chen, and W.-C. Wu. Solving the cruise passenger itinerary scheduling problem using quantum-inspired computing. In Proceedings of IEEE QCNC, 2025.

    [4] P.-K. Yang and J.-H. Lin. A generic method of pose generation in molecular docking via quadratic unconstrained binary optimization. In Proceedings of FedCSIS, volume 40, pages 69–71, 2024.

    [5] P.-H. Fang, Y.-S. Chen, J.-S. Wu, and P. Yu. Inverse reticle optimization with quantum annealing and hybrid solvers. IEEE Access, 12:33069–33078, 2024.

    [6] Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer, 1972.

    [7] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.

    [8] Emile Aarts and Jan Korst. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. John Wiley & Sons, 1988.

    [9] Aleta Berk Finnila, Maria A. Gomez, C. Sebenik, C. Stenson, and Jimmie D. Doll. Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 219(5-6):343–348, 1994.

    [10] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al. Quantum annealing with manufactured spins. Nature, 473(7346):194–198, 2011.

    [11] M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura, and H. G. Katzgraber. Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics, 7:48, 2019.

    [12] J. R. Jiang, Y.-C. Shu, and Q.-Y. Lin. Benchmarks and recommendations for quantum, digital, and GPU annealers in combinatorial optimization. IEEE Access, 12:125014–125031, 2024.

    [13] Holger H. Hoos and Thomas Stützle. Stochastic Local Search: Foundations and Applications. Elsevier, 2004.

    [14] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems, 28, 2015.

    [15] Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, 30, 2017.

    [16] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021.

    [17] James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey. In Proceedings of IJCAI, pages 4475–4482, 2021.

    [18] Naeimeh Mohseni, Peter L. McMahon, Tim Byrnes, Andrew D. King, and Masoud Mohseni. Ising machines as hardware solvers of combinatorial optimization problems. Nature Reviews Physics, 4(6):363–379, 2022.

    [19] Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted Boltzmann machines. In Proceedings of the 27th International Conference on Machine Learning, pages 807–814, 2010.

    [20] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359–366, 1989.

    [21] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56):1929–1958, 2014.

    [22] Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.

    [23] Elizabeth D. Dolan and Jorge J. Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201–213, 2002.

    [24] Iain Dunning, Swati Gupta, and John Silberholz. What works best when? A systematic evaluation of heuristics for max-cut and QUBO. INFORMS Journal on Computing, 30(3):608–624, 2018.

    QR CODE