請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/95559完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 管希聖 | zh_TW |
| dc.contributor.advisor | Hsi-Sheng Goan | en |
| dc.contributor.author | 胡祐誠 | zh_TW |
| dc.contributor.author | Yu-Cheng Hu | en |
| dc.date.accessioned | 2024-09-11T16:30:24Z | - |
| dc.date.available | 2024-09-12 | - |
| dc.date.copyright | 2024-09-11 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-07-29 | - |
| dc.identifier.citation | [1] Kato, T. (1950). On the adiabatic theorem of quantum mechanics. Journal of the Physical Society of Japan, 5(6), 435-439.
[2] Rubbmark, J. R., Kash, M. M., Littman, M. G., & Kleppner, D. (1981). Dynamical effects at avoided level crossings: A study of the Landau-Zener effect using Rydberg atoms. Physical Review A, 23(6), 3107. [3] Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680. [4] Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C., & Doll, J. D. (1994). Quantum annealing: A new method for minimizing multidimensional functions. Chemical physics letters, 219(5-6), 343-348. [5] Smith, A. E., Coit, D. W., Baeck, T., Fogel, D., & Michalewicz, Z. (1997). Penalty functions. Handbook of evolutionary computation, 97(1), C5. [6] Bertsekas, D. P., & Scientific, A. (2005). Nonlinear Programming 2nd Edition Solutions Manual. [7] Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning, 3(1), 1-122. [8] Birgin, E. G., & Martínez, J. M. (2014). Practical augmented Lagrangian methods for constrained optimization. Society for Industrial and Applied Mathematics. [9] Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in physics, 2, 74887. [10] Date, P., Patton, R., Schuman, C., & Potok, T. (2019). Efficiently embedding QUBO problems on adiabatic quantum computers. Quantum Information Processing, 18, 1-31. [11] Glover, F., Kochenberger, G., & Du, Y. (2019). Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4or, 17(4), 335-371. [12] Takehara, K., Oku, D., Matsuda, Y., Tanaka, S., & Togawa, N. (2019, September). A multiple coefficients trial method to solve combinatorial optimization problems for simulated-annealing-based ising machines. In 2019 IEEE 9th International Conference on Consumer Electronics (ICCE-Berlin) (pp. 64-69). IEEE. [13] Goh, S. T., Gopalakrishnan, S., Bo, J., & Lau, H. C. (2020). A hybrid framework using a qubo solver for permutation-based combinatorial optimization. arXiv preprint arXiv:2009.12767. [14] Yonaga, K., Miyama, M. J., & Ohzeki, M. (2020). Solving inequality-constrained binary optimization problems on quantum annealer. arXiv preprint arXiv:2012.06119. [15] Ohzeki, M. (2020). Breaking limitation of quantum annealer in solving optimization problems under constraints. Scientific reports, 10(1), 3126. [16] Jain, S. (2021). Solving the traveling salesman problem on the d-wave quantum computer. Frontiers in Physics, 9, 760783. [17] Verma, A., & Lewis, M. (2022). Penalty and partitioning techniques to improve performance of QUBO solvers. Discrete Optimization, 44, 100594. [18] Ayodele, M. (2022, April). Penalty weights in qubo formulations: Permutation problems. In European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar) (pp. 159-174). Cham: Springer International Publishing. [19] McGeoch, C. C. (2022). Adiabatic quantum computation and quantum annealing: Theory and practice. Springer Nature. [20] Djidjev, H. N. (2023). Logical qubit implementation for quantum annealing: augmented Lagrangian approach. Quantum Science and Technology, 8(3), 035013. [21] Djidjev, H. N. (2023). Quantum annealing with inequality constraints: the set cover problem. Advanced Quantum Technologies, 6(11), 2300104. [22] Cellini, L., Macaluso, A., & Lombardi, M. (2023). QAL-BP: An augmented lagrangian quantum approach for bin packing problem. arXiv preprint arXiv:2309.12678. [23] Jiang, J. R., & Chu, C. W. (2023). Classifying and benchmarking quantum annealing algorithms based on quadratic unconstrained binary optimization for solving NP-hard problems. IEEE Access. [24] Getting Started with D-Wave Solvers. URL:https://docs.dwavesys.com/docs/latest/doc_getting_started.html | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/95559 | - |
| dc.description.abstract | 通常為了解決變數多的NP問題，會需要花費非常多的時間去求解，但我們可以利用啟發式演算法來在合理的時間範圍內求得進似解，其中著名的模擬退火就是其中之一，另一個利用了量子現象的次經驗演算法來求解NP問題的著名方法則是量子退火。但是這兩個演算法能夠解決的問題有限制，只能求解沒有限制條件的問題，不過大部分的NP問題都含有限制條件，所以必須要預處理問題將其轉化成無限制條件問題，在本論文中，我們將有約束的問題轉化為二次無約束二進制優化（QUBO）問題或伊辛模型問題，然後通過模擬退火和量子退火找到可行解。我們採用了三種方法來選擇QUBO問題中適當的約束(懲罰)項參數(係數)，第一個方法是懲罰法，第二個是增廣拉格朗日法，第三個則是解決前面兩種會有的潛在缺陷而提出的自適應增廣拉格朗日法。我們在模擬退火和量子退火機器上測試了這三種方法在三種類型問題上的解：隨機 QUBO 問題、旅行推銷員問題和背包問題。通過分析找到可行解所需的迭代次數、可行解與最優解之間的差距以及找到最優解的概率來評估這三種方法的性能。結果發現，自適應增廣拉格朗日方法的性能優於其他兩種方法。 | zh_TW |
| dc.description.abstract | Typically, it would take a considerable amount of time to solve nondeterministic polynomial (NP) time problems with many variables. Heuristic algorithms can be used to obtain approximate solutions within a reasonable time frame. Among these, the well-known simulated annealing is one classical method. Another method that utilizes quantum property to solve NP problems is quantum annealing. These two algorithms can only solve problems without constraints, but most NP problems do involve constraints. Therefore, it is necessary to preprocess the problems to transform them into unconstrained ones. In this thesis, we transform constrained problems into quadratic unconstrained binary optimization (QUBO) problems or Ising model problems, and then find feasible solutions via simulated and quantum annealing. We employ three methods for choosing suitable parameters (coefficients) of constraint (penalty) terms in the QUBO problems. The first method is the penalty method, the second is the augmented Lagrangian method, and the third is the adaptive augmented Lagrangian method proposed to address potential flaws in the first two methods. We tested the three methods for finding solutions on simulated annealing and quantum annealing machines for three different kinds of problems: random QUBO problems, the traveling salesman problem, and the knapsack problem. The performance of the three methods is evaluated by analyzing the number of iterations to find a feasible solution, the gap between the feasible solution and the optimal solution, and the probability of finding the optimal solution. It is found that the adaptive augmented Lagrangian method has a better performance than the other two methods. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-09-11T16:30:24Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-09-11T16:30:24Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | 口試委員審定書 i
Acknowledgements iii 摘要 iv Abstract v Contents vii List of Figures x List of Tables xii Denotation xiii Chapter 1 Introduction 1 Chapter 2 Quadratic Unconstrained Binary Optimization Problems 4 2.1 Travelling Salesman Problem 6 2.1.1 Formulation of Travelling Salesman Problem 6 2.1.2 The Instances of TSP 7 2.2 Knapsack Problem 8 2.2.1 Formulation of Knapsack Problem 9 2.2.2 The Instances of Knapsack Problem 9 Chapter 3 Annealing Solvers 10 3.1 Simulated Annealing 10 3.2 Quantum Annealing 12 3.2.1 Adiabatic Quantum Computing and Landau-Zener Transition 13 3.2.2 D-Wave Quantum Annealer 16 Chapter 4 Methods for Choosing Suitable Coefficients of Constraint Terms in QUBO problems 20 4.1 Penalty Method 21 4.2 Lagrangian Multiplier Method 22 4.2.1 Dual Ascent 22 4.2.2 Augmented Lagrangian Method 24 4.2.3 Pseudocode of the Augmented Lagrangian Method 25 4.3 Adaptive Augmented Lagrangian Method 26 4.3.1 Pseudocode of the Adaptive Augmented Lagrangian Method 26 Chapter 5 Addressing QUBO Problems via Annealing Solver 28 5.1 QUBO form of TSP 28 5.2 Saving on the Consumption of Computational Resources in TSP 29 5.3 Two Different Encoding Methods for the Knapsack Problem 31 5.3.1 One-Hot Encoding 31 5.3.2 Log Encoding 32 5.3.3 Augmented Lagrangian form of KP 33 5.4 Comparison of Two Encoding Methods 34 Chapter 6 Benchmarking Methods on Three Different QUBO Problems 36 6.1 Set up Three Different QUBO Problems 37 6.2 Set up the parameters of initial input, methods and solver 38 6.3 The Flowchart of Benchmarking methods 40 6.4 Comparison between the Penalty Method and Augmented Lagrangian Method 41 6.5 Comparison between the Augmented Lagrangian Method and Adaptive Augmented Lagrangian Method 45 6.6 Further Merits of the Adaptive Augmented Lagrangian Method 50 Chapter 7 Summary 53 7.1 Summary of Solvers 53 7.2 Summary of Parameter Tuning Methods 54 7.3 Outlook and Future Work 55 References 56 Appendix 59 A.1 Derivation of QUBO Model to Ising Model 59 A.2 The Relation between Original Problem and Dual Problem 61 A.3 Prove the Convergence of the Augmented Lagrangian Method 67 | - |
| dc.language.iso | en | - |
| dc.subject | 模擬退火 | zh_TW |
| dc.subject | 增廣拉格朗日懲罰法 | zh_TW |
| dc.subject | 懲罰法 | zh_TW |
| dc.subject | NP問題 | zh_TW |
| dc.subject | 易辛模型 | zh_TW |
| dc.subject | 量子退火 | zh_TW |
| dc.subject | Quantum Annealing | en |
| dc.subject | QUBO | en |
| dc.subject | Ising Model | en |
| dc.subject | NP Problem | en |
| dc.subject | Penalty Method | en |
| dc.subject | Augmented Lagrangian Method | en |
| dc.subject | Simulated Annealing | en |
| dc.title | 透過自適應增強拉格朗日方法自動調整二次無約束二元最佳化形式的限制項參數 | zh_TW |
| dc.title | Auto Parameter Tuning of Constraint Terms in Quadratic Unconstrained Binary Optimization Form via the Adaptive Augmented Lagrangian Method | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 112-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 鄭皓中;張慶瑞;江振瑞 | zh_TW |
| dc.contributor.oralexamcommittee | Hao-Chung Cheng;Ching-Ray Chang;Jehn-Ruey Jiang | en |
| dc.subject.keyword | 模擬退火,量子退火,易辛模型,NP問題,懲罰法,增廣拉格朗日懲罰法, | zh_TW |
| dc.subject.keyword | Simulated Annealing,Quantum Annealing,QUBO,Ising Model,NP Problem,Penalty Method,Augmented Lagrangian Method, | en |
| dc.relation.page | 69 | - |
| dc.identifier.doi | 10.6342/NTU202401226 | - |
| dc.rights.note | 同意授權(限校園內公開) | - |
| dc.date.accepted | 2024-07-31 | - |
| dc.contributor.author-college | 理學院 | - |
| dc.contributor.author-dept | 物理學系 | - |
| dc.date.embargo-lift | 2029-07-25 | - |
| 顯示於系所單位： | 物理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-112-2.pdf 未授權公開取用 | 21.05 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。