請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/90039完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳中平 | zh_TW |
| dc.contributor.advisor | Chung-Ping Chen | en |
| dc.contributor.author | 張書平 | zh_TW |
| dc.contributor.author | Shu-Ping Chang | en |
| dc.date.accessioned | 2023-09-22T17:09:47Z | - |
| dc.date.available | 2023-11-09 | - |
| dc.date.copyright | 2023-09-22 | - |
| dc.date.issued | 2023 | - |
| dc.date.submitted | 2023-08-09 | - |
| dc.identifier.citation | [1] Larranaga, P., et al., Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial intelligence review, 1999. 13: p. 129-170.
[2] Finnila, A.B., et al., Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 1994. 219(5): p. 343-348. [3] Mohimani, H., M. Babaie-Zadeh, and C. Jutten, A fast approach for overcomplete sparse decomposition based on smoothed L0 norm. IEEE Transactions on Signal Processing, 2008. 57(1): p. 289-301. [4] Neumaier, A., Solving ill-conditioned and singular linear systems: A tutorial on regularization. SIAM review, 1998. 40(3): p. 636-666. [5] Von Neumann, J. and H.H. Goldstine, Numerical inverting of matrices of high order. 1947. [6] Demmel, J.W., On condition numbers and the distance to the nearest ill-posed problem. Numerische Mathematik, 1987. 51: p. 251-289. [7] Cline, A.K., et al., An estimate for the condition number of a matrix. SIAM Journal on Numerical Analysis, 1979. 16(2): p. 368-375. [8] Young, N., An introduction to Hilbert space. 1988: Cambridge university press. [9] Peretuset, SquareWave, SquareWave.gif, Editor. 2010: Wikimedia Commons. [10] 苑家瑜, 利用高階多項式模擬及邊界條件改善內插法的誤差, in 光電工程學研究所. 2021, 國立臺灣大學. p. 1-70. [11] Margalit, D., J. Rabinoff, and L. Rolen, Interactive linear algebra. Georgia Institute of Technology, 2017. [12] Golub, G., Numerical methods for solving linear least squares problems. Numerische Mathematik, 1965. 7(3): p. 206-216. [13] Hoerl, A.E. and R.W. Kennard, Ridge Regression: Applications to Nonorthogonal Problems. Technometrics, 1970. 12(1): p. 69-82. [14] Louizos, C., M. Welling, and D.P. Kingma, Learning Sparse Neural Networks through L0 Regularization. ArXiv, 2017. abs/1712.01312. [15] Papadimitriou, C.H. and K. Steiglitz, Combinatorial optimization: algorithms and complexity. 1998: Courier Corporation. [16] Lovász, L., Review of the book by Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Operations Research Letters, 2005. 33(4): p. 437-440. [17] Jünger, M., G. Reinelt, and G. Rinaldi, The traveling salesman problem. Handbooks in operations research and management science, 1995. 7: p. 225-330. [18] Applegate, D.L., et al., The traveling salesman problem. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2006: p. 1-5. [19] Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 1998. 45(5): p. 753-782. [20] 劉文義, 以 k-opt 為基礎之分支切面法求解旅行銷售員問題. 2010, National Cheng Kung University Department of Industrial and Information …. [21] Johnson, D.S. and L.A. McGeoch, The traveling salesman problem: A case study in local optimization. Local search in combinatorial optimization, 1997. 1(1): p. 215-310. [22] Glover, F., Future paths for integer programming and links to artificial intelligence. Computers & operations research, 1986. 13(5): p. 533-549. [23] Blum, C. and A. Roli, Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys, 2003. 35(3): p. 268-308. [24] Wolpert, D.H. and W.G. Macready, No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1997. 1(1): p. 67-82. [25] Abdel-Basset, M., L. Abdel-Fatah, and A.K. Sangaiah, Chapter 10 - Metaheuristic Algorithms: A Comprehensive Review, in Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications, A.K. Sangaiah, M. Sheng, and Z. Zhang, Editors. 2018, Academic Press. p. 185-231. [26] Kirkpatrick, S., C.D. Gelatt, and M.P. Vecchi, Optimization by Simulated Annealing. Science, 1983. 220(4598): p. 671-680. [27] Blocho, M., Chapter 4 - Heuristics, metaheuristics, and hyperheuristics for rich vehicle routing problems, in Smart Delivery Systems, J. Nalepa, Editor. 2020, Elsevier. p. 101-156. [28] Diaby, M., The traveling salesman problem: a linear programming formulation. arXiv preprint cs/0609005, 2006. [29] Reinelt, G., TSPLIB—A traveling salesman problem library. ORSA journal on computing, 1991. 3(4): p. 376-384. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/90039 | - |
| dc.description.abstract | 組合最佳化問題有許多工業應用，例如IC佈局、工業排程調度、異構體分析等，然而，組合最佳化是在一個有限的解集合中尋找最佳解的問題，其時間複雜度會呈階乘性成長，這類型的問題屬於NP-hard或NP-complete，隨著維度增加窮舉法便是不可行的，其中最知名的組合最佳化問題便是旅行商人問題(Travelling Salesman Problem; TSP)。
模擬退火演算法提供了能夠使用隨機搜索方向來脫離局部最小值的組合求解器，我們提出了一種不同於以往的熱退火啟發式演算法，是基於非線性規劃將組合問題建構成一個函數最佳化問題，再利用梯度下降(gradient descent)的求解器，可以將收斂速度大大提高到與梯度下降搜索相同的水平，當中還包含一個新的熱退火啟發正則化約束函數，用於通過逐漸增加函數凸性來放大全局最小值來逃避局部最小值。 我們試著將熱退火啟發式連續非拘束最佳化演算法(Annealing-inspired Continuous Unconstrained Optimization; ACUO)應用於不同城市數的旅行商人問題 (TSP)，在實驗結果中表明，演算法的運算為多項式時間複雜度，相較於窮舉求解法階乘時間複雜度，大幅加速了收斂時間，且對於高維旅行商人問題能夠有效解決，在50個城市的旅行商人問題中僅有5%的相對誤差。 | zh_TW |
| dc.description.abstract | Combinatorial optimization problem has various industrial applications, such as IC layout, industrial scheduling, isomer analysis, etc. However, the combinatorial optimization problem is to find the best solution in a limited solution set, and its time complexity grows exponentially. This type of problem is NP-hard or NP-complete. As the dimensions increase, the exhaustive method is not feasible. One of the most well-known combinatorial optimization problems is the Traveling Salesman Problem (TSP).
Simulated Annealing Algorithm provides a combinatorial solver capable of escaping local minima using random search directions. We propose a novel annealing-inspired heuristic algorithm that approaches the combinatorial problem as a function optimization problem based on nonlinear programming. We use a gradient-descent(GD) based solver to greatly improve the convergence rate to the same level as GD search. Also included a new annealing-inspired regularization constraint function for escaping local minima by gradually increased convexity to zoom in on the global minima. We attempted to apply the Annealing-inspired Continuous Unconstrained Optimization (ACUO) to the Traveling Salesman Problem (TSP) with different numbers of cities. The experiment results show that the algorithm operates in polynomial time complexity, which is a great improvement compared to the factorial time complexity of exhaustive method. It especially accelerates the convergence time and effectively solves high-dimensional TSP instances. For a TSP with 50 cities, the relative error is only 5%. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-09-22T17:09:47Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2023-09-22T17:09:47Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | 口試委員會審定書 i
致謝 ii 中文摘要 iv ABSTRACT v CONTENTS vi LIST OF FIGURES ix LIST OF TABLES xi Chapter 1 緒論 1 1.1 前言 1 1.2 研究動機 1 1.3 論文架構 3 Chapter 2 研究背景 4 2.1 病態系統(ill-conditioned system) 4 2.1.1 線性方程與數值計算 4 2.1.2 二元線性方程例子 4 2.1.3 病態系統特性 5 2.1.4 條件數(Condition number) 6 2.2 向量空間與基底 8 2.2.1 希爾伯特空間(Hilbert space)與泛函分析 8 2.2.2 正交基底 9 2.2.3 傅立葉分析 10 2.3 數值方法解線性方程 11 2.3.1 最小平方近似(Least Square Approximation) 11 2.3.2 梯度下降法(Gradient Descent) 12 2.3.3 正則化最小平方法(Regularized Least Square) 14 2.3.4 正則項範數(N-norm Regularization Term) 14 2.4 組合最佳化問題(Combinatorial Optimization Problem) 16 2.4.1 旅行商人問題(Travelling Salesman problem) 17 2.4.2 通用啟發式演算法(Metaheuristic Algorithm) 18 2.4.3 模擬退火法(Simulated Annealing) 19 Chapter 3 研究方法 22 3.1 非線性整數規劃(Nonlinear Integer Programming) 22 3.1.1 在無約束最佳化中使用路線長作為成本函數 22 3.1.2 利用正則化將限制條件加入最佳化函數 23 3.2 熱退火啟發正則項(annealing-inspired regularization term) 25 3.2.1 二元離散變量視為連續變量 25 3.2.2 利用傾向病態系統的啟發式方法選擇λ1 25 3.2.3 變數平方替換 26 3.2.4 使用正則化函數合併傾向於二元值的約束條件 26 3.2.5 熱退火啟發法：緩慢降低 σ 嘗試逃離局部極小值 29 3.2.6 Final Algorithm：熱退火啟發式連續非拘束最佳化(ACUO) Pseudo Code 30 Chapter 4 實驗結果與討論 31 4.1 演算法時間複雜度評估 31 4.2 參數調整測試結果 34 4.2.1 參數 λ1調整的結果比較 34 4.2.2 參數 λ2 調整的結果比較 36 4.2.3 參數 σk 調整的結果比較 39 4.3 尋找隨機分布城市最短路徑結果 40 4.4 TSPLIB測試集結果與比較 44 4.5 演算法程式碼結構 46 Chapter 5 結論與為來展望 60 5.1 結論 60 5.2 未來展望 60 REFERENCE 62 | - |
| dc.language.iso | zh_TW | - |
| dc.title | 利用熱退火啟發式連續非拘束最佳化演算法解決組合問題 | zh_TW |
| dc.title | Using Annealing-inspired Continuous Unconstrained Optimization Algorithm to Solve Combinatorial Problem | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 111-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 姚嘉瑜;楊健生;孫允武;孫建文 | zh_TW |
| dc.contributor.oralexamcommittee | Chia-Yu Yao;Chien-Sheng Yang;Yun-Wu Sun;Chien-Wen Sun | en |
| dc.subject.keyword | 模擬退火法,旅行商人問題,組合最佳化問題,病態系統,梯度下降, | zh_TW |
| dc.subject.keyword | Simulated Annealing,Travelling Salesman Problem,Combinatorial Optimization Problem,Ill-conditioned System,Gradient-descent, | en |
| dc.relation.page | 64 | - |
| dc.identifier.doi | 10.6342/NTU202302620 | - |
| dc.rights.note | 同意授權(限校園內公開) | - |
| dc.date.accepted | 2023-08-10 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 生醫電子與資訊學研究所 | - |
| dc.date.embargo-lift | 2028-08-01 | - |
| 顯示於系所單位： | 生醫電子與資訊學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-111-2.pdf 目前未授權公開取用 | 3.62 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。