以類神經網路為基的最短迴圈求解系統

Neural Network Models For Finding The Shortest Cycle In Complete Graphs

曹靖民(Ching-Min Tsao)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202002523

摘要

本研究首先依照圖論的定義以及過往對最短迴圈問題的研究，定義一適合類神經網路使用的最短迴圈問題格式。據此，自行產出訓練及測試資料，再以多層感知器、卷積神經網路、遞歸神經網路等經典的神經網路架構為基礎，開發不同的最短迴圈求解系統，在已知各節點間距離的情況下，目標是讓系統求算出最短距離的迴圈。為達到此目的，使用已知最佳解的訓練資料對網路的權重進行訓練。訓練過程中，用初始網路權重計算對輸入距離矩陣的輸出結果，通過設定的誤差函數計算輸出結果與已知最佳解之間的誤差，並使用選定的優化器，通過誤差函數值更新網路權重。反覆的更新網路權重，直到網路的計算結果與最佳解之間的誤差值收斂，得到求解系統的最佳網路權重。為了計算系統的求解效能，使用不重複的距離矩陣測試資料，對系統進行測試，並紀錄系統求算序列與最佳解是否相同。結果顯示以類神經網路為基礎的最短迴圈雖然具有優於貪婪法的求解效力，但最終求解品質都不足以作為一個有效的求解演算法。

關鍵字

最短迴圈問題 ； 類神經網路 ； 多層感知器 ； 卷積神經網路 ； 遞歸神經網路

並列摘要

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.

並列關鍵字

Shortest circuit problem ； Neural Network ； Multilayer perceptron ； Convolutional Neural Network ； Recurrent neural network

參考文獻

Bland, R. and D. Shallcross (1989). "Large travelling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation." Operations Research Letters 8: 125-128.

Croes, A. G. (1958). "A Method for Solving Traveling-Salesman Problems." Operations Research 6: 791-812.

Dantzig, G. and R. Ramser (1959). "The Truck Dispatching Problem." Management Science 6: 80-91.

Dorigo, M. and L. M. Gambardella (1997). "Ant Colonies for the Traveling Salesman Problem." Bio Systems 43: 73-81.

Fukushima, K. (1980). "Neocognitron: a self organizing neural network model for a mechanism of pattern recognition unaffected by shift in position." Biol Cybern 36(4): 193-202.