基於GPU的量子啟發式QUBO問題求解器之實作與效能評估;GPU-Based Implementation and Performance Evaluation of a Quantum-Inspired Solver for QUBO Problems

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/98566

Please use this identifier to cite or link to this item: https://ir.lib.ncu.edu.tw/handle/987654321/98566

Title:	基於GPU的量子啟發式QUBO問題求解器之實作與效能評估;GPU-Based Implementation and Performance Evaluation of a Quantum-Inspired Solver for QUBO Problems
Authors:	李俊賢;LI, JYUN-SIAN
Contributors:	資訊工程學系
Keywords:	多樣自適大規模搜尋;統一計算設備架構;二次無約束二元最佳化;組合最佳化;圖形加速器;量子啟發演算法;Diverse Adaptive Bulk Search;Compute Unified Device Architecture;Quadratic Unconstrained Binary Optimization;Combinatorial Optimization;Graphics Processing Unit;Quantum-Inspired Algorithm
Date:	2025-08-14
Issue Date:	2025-10-17 12:56:01 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究目的在針對一個稱為「多樣自適大規模搜尋（Diverse Adaptive Bulk Search, DABS）」的「二次無約束二元最佳化（Quadratic Unconstrained Binary Optimization, QUBO）」問題求解器進行以GPU之「統一計算設備架構（Compute Unified Device Architecture, CUDA）」為基礎的實作及效能評估，也就是比較DBAS在 CPU 與 GPU 上實作並執行的效能差異。DABS 為一種受量子退火(quantum annealing)概念影響的量子啟發(quantum-inspired)演算法框架，結合多樣化解池、多策略探索與批次更新機制，具備強大的全域搜尋能力與平行化潛力，適合用於解決困難的組合最佳化(combinatorial optimization)問題。為發揮 DABS 在平行運算上的優勢，本研究採用 CUDA 技術實現多區塊(block)的並行結構，並依據DABS所設計之 LSA（Local Search Algorithm）與 GAO（Genetic Algorithm Operation）兩種探索策略進行解空間的多樣化導引。實驗部份以數組標準 QUBO 測試資料進行驗證，分析解題時間（Time to Solution, TTS）、加速比與解品質等指標。雖然本研究實作之 GPU 版本求解器實作在某些案例中未能完全達成 DABS原始論文中所報導之最佳解品質與執行時間，但相較於 CPU版本實作與著名的CPU版本Gurobi求解器，本研究所實作的求解器能在大多數測試案例中產生更佳的解，並顯著縮短求解時間，展現 GPU 在量子啟發式搜尋上的潛力與實用性，未來可應用於更大規模之組合最佳化問題求解。;This study aims to implement and evaluate the performance of a quantum-inspired solver known as Diverse Adaptive Bulk Search (DABS) for Quadratic Unconstrained Binary Optimization (QUBO) problems using GPU’s Compute Unified Device Architecture (CUDA). The main objective is to compare the performance differences of DABS when executed on CPU and GPU platforms. DABS is a quantum-inspired algorithm framework influenced by the concept of quantum annealing, which integrates a diverse solution pool, multi-strategy exploration, and batch updating mechanisms. These characteristics endow DABS with strong global search capabilities and high parallelization potential, making DABS suitable for solving intractable combinatorial optimization problems. To leverage the advantages of parallel computing, we utilized a multi-block CUDA architecture and implemented two DABS search strategies, namely the Local Search Algorithm (LSA) and the Genetic Algorithm Operation (GAO), to guide the exploration and exploitation of the solution space. A set of standard QUBO benchmark instances was used for experimental validation, focusing on metrics such as the Time to Solution (TTS), speedup ratio, and solution quality. Although the GPU implementation of DABS in this study did not fully achieve the best performance reported in the original DABS paper for certain cases, it outperformed both the CPU implementation of DABS and the well-known CPU-based Gurobi solver in most benchmark instances. It significantly reduced the TTS, demonstrating the potential and practicality of GPUs in quantum-inspired search, showing promise for solving large-scale combinatorial optimization problems in the future.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	10	View/Open

社群 sharing

Loading...