請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52709
標題: | 以類神經網路為基的最短迴圈求解系統 Neural Network Models For Finding The Shortest Cycle In Complete Graphs |
作者: | Ching-Min Tsao 曹靖民 |
指導教授: | 楊烽正(Feng-Cheng Yang) |
關鍵字: | 最短迴圈問題,類神經網路,多層感知器,卷積神經網路,遞歸神經網路, Shortest circuit problem,Neural Network,Multilayer perceptron,Convolutional Neural Network,Recurrent neural network, |
出版年 : | 2020 |
學位: | 碩士 |
摘要: | 本研究首先依照圖論的定義以及過往對最短迴圈問題的研究,定義一適合類神經網路使用的最短迴圈問題格式。據此,自行產出訓練及測試資料,再以多層感知器、卷積神經網路、遞歸神經網路等經典的神經網路架構為基礎,開發不同的最短迴圈求解系統,在已知各節點間距離的情況下,目標是讓系統求算出最短距離的迴圈。為達到此目的,使用已知最佳解的訓練資料對網路的權重進行訓練。訓練過程中,用初始網路權重計算對輸入距離矩陣的輸出結果,通過設定的誤差函數計算輸出結果與已知最佳解之間的誤差,並使用選定的優化器,通過誤差函數值更新網路權重。反覆的更新網路權重,直到網路的計算結果與最佳解之間的誤差值收斂,得到求解系統的最佳網路權重。為了計算系統的求解效能,使用不重複的距離矩陣測試資料,對系統進行測試,並紀錄系統求算序列與最佳解是否相同。結果顯示以類神經網路為基礎的最短迴圈雖然具有優於貪婪法的求解效力,但最終求解品質都不足以作為一個有效的求解演算法。 This research first defines a shortest circuit problem format suitable for neural networks based on the definition of graph theory and previous research on the shortest circuit problem. With the defined shortest circuit problem format we self-produce training and test data, and then develop different shortest loop solving systems based on classic neural network architectures such as multilayer perceptrons, convolutional neural networks, and recurrent neural networks. With all distances between nodes are known, the goal is to let the system calculate the shortest distance circuit. To achieve this goal, the weights of the network are trained by training data with known best solution. During the training process, the initial network weight is used to calculate the output result of the input distance matrix, the error between the output result and the known best solution is calculated through loss function, and the selected optimizer is used to update network weights through loss function. The network weights are updated repeatedly until the error value between the network calculation results and the optimal solution converges, and the optimal network weight for the solution system is obtained. In order to calculate the solution performance of the system, test the system using non-repetitive distance matrix test data, and record whether the system output sequence is the same as the best solution. The results show that although the shortest circuit result based on the neural networks has better solution efficiency than the greedy method, the final solution quality is not enough for it to be an effective solution algorithm. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52709 |
DOI: | 10.6342/NTU202002523 |
全文授權: | 有償授權 |
顯示於系所單位: | 工業工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-0608202012334500.pdf 目前未授權公開取用 | 2.64 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。