標題: 類神經網路於旅行銷售員問題之應用
Application of Neural Networks in Solving Travelling Salesman Problems
作者: 林武龍
Wu-Lung Lin
石至文
Chih-Wen Shih
應用數學系所
關鍵字: 類神經網路;旅行銷售員問題;組合最佳化問題;neural network;travelling salesman problems;combinatorial optimization problems
公開日期: 2002
摘要: 本論文係在研究短暫混沌性的類神經網路(transiently chaotic neural network TCNN)的計算方法來解答著名的旅行銷售員問題(travelling salesman problems),當短暫混沌性的類神經網路的演變結果遞減趨於穩定時即可找出目標函數(objective function)的最小值。本論文首先探討兩個目標函數的性質,接著以最新近的TCNN之混沌行為與迭代的收斂理論進行一連串的數值實驗,這個實驗也發現TCNN可以由原來的嚴格遞增輸出函數(strictly increasing output function)衍生成分段線性輸出函數(piecewise linear output function),這顯示用嚴格遞增輸出函數與分段線性輸出函數的計算結果相似,此外,並分別說明成功與失敗兩種數值實驗,最後則提出解組合最佳化問題(combinatorial optimization problems)的缺點和可改進之部分供未來研究者參考。
This thesis studies the uses of a transiently chaotic neural network (TCNN) as a computational method in solving the well known travelling salesman problems. The task of this omputation is to locate the minimum of an objective function, which is attained as the evolutions of the neural networks settle down. Properties of two objective functions adopted in previous studies are investigated. By applying the recent theory on the chaotic behaviors and convergence of iterations of the TCNN, we perform a series of numerical experiments. The experiments are also extended to the TCNN with a piecewise linear output function. It is demonstrated that such a piecewise linear output function with saturations works equally well as the strictly increasing output used in previous studies. Both successful and unsuccessful numerical examples will be illustrated. We also mention some insufficiencies of this computation method in solve combinatorial optimization problems and hope to provide further improvements.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT910507022
http://hdl.handle.net/11536/70954
Appears in Collections:Thesis