應用自我組織類神經網路於最長不相交路徑問題應用自我組織類神經網路於最長不相交路徑問題TheStudyoftheLargestNon-CrossingRouteProblemUsingSelf-OrganizingNeuralNetworks陳昭榮Chao-RongChen國立臺北科技大學電機工程系摘要自我組織類神經網路具有拓樸特性，可用來很有效率的求解銷售員旅行問題。本文提出一新的研究問題，為對於平面上的一群節點，除了起點外每一節點恰好經過一次之不相交封閉路徑，求出最長距離之路徑。針對此問題，本文提出數個與兩線段相交有關的定理，及改進原先用以求解銷售員旅行問題自我組織之方法，用於求解此一最大化不相交封閉路徑之問題。由數個實例之模擬結果證明可用以得到不錯之解答。關鍵詞：類神經網路、自我組織法、銷售員旅行問題、最長不相交路徑問題。投稿受理時間：91年3月15日審查通過時間：91年5月10日ABSTRACTSelf-organizingneuralnetworkhasthetopologicalcharacteristicsthatcanbeeffectivelyusedinsolvingthetravelingsalesmanproblem.Thispaperproposesanovelproblemofoptimizingthenon-crossingclosedrouteinwhicheachnode,exceptforthestartingpoint,isonlyvisitedoncesothatthetotalvisitinglengthismaximized.Sometheoremsoftheintersectionoftwolinesarereviewedinthepaper.And,theself-organizingnetworkalgorithmofsolvingthetravelingsalesmanproblemismodifiedtosolvetheproblem.Simulationresultsshowthattheproposedalgorithmhasgoodperformancesontheoptimizationofthetrip-length.Keywords:ArtificialNeuralNetwork,Self-OrganizingMethod,TravelingSalesmanProblem,LargestNon-CrossingRouteProblem.壹、簡介近年來，研究人員渴望能發展出比目前電腦更聰明的機器來服務人類，因此類神經112應用自我組織類神經網路於最長不相交路徑問題網路成為熱中之研究方向之一。它是一個相當年輕的科學，在1987年才辦第一屆ICNN研討會，1989年辦第一屆IJCNN研討會，1990年IEEE之NeuralNetwork創刊。但與類神經網路相關之研究近幾年來在各領域之刊物均可看到。關於類神經網路應用於解最佳化問題，在各工程領域皆有不錯之突破，使得最佳化問題在減少執行時間、節省使用記憶體上皆有不錯之成果。類神經網路有下列幾項之優點：(1)俱平行處理能力，故速度快，可作即時輸出。(2)知識或資料是分散的儲存在大量的加權值中，故對神經鍵局部傷害不致影響整體功能。(3)具學習能力，可以自行由例子中尋找規則性而具專門知識。(4)有保持菁華（abstraction）的能力。當接受足夠訓練後，雖然輸入不完整或有雜訊的資料，亦能由其中特性，得知其原來面貌。類神經網路之分類，若依學習方式來分，可分成監督式(supervised)學習及非監督式(unsupervised)學習兩種。常見的監督式類神經網路有多層認知網路(multi-layerperceptron)和Hopfield網路。在學習過程中，多組訓練樣本循序的被輸入網路中，每組訓練樣本包括一個輸入向量及一個理想輸出向量。這類網路能比較實際輸出及理想輸出，得到一個差值（error），此差值會由後往前一層一層傳遞，加權值則依某種學習法則來調整。這個動作持續到差值小於容忍值，於是學習完成。常見的非監督式類神經網路有Kohonen自我組織網路和Carpenter/Grossberg網路。訓練樣本裡不包括理想輸出向量。這時網路被希望能自行由輸入向量歸納出訓練樣本的規則性或相關性，並產生一個合理的輸出。貳、自我組織網路自我組織網路(Self-OrganizingMap,SOM)由T.Kohonen在1980年提出此網路架構[1]。其基本原理可溯自大腦結構的特性，大腦中相似功能的腦細胞具有聚集在一起之特性，例如人類大腦中有專司視覺、聽覺、味覺等區塊，也就是腦神經細胞有『物以類聚』的特性，自我組織映射圖網路模仿這種特性，其輸出處理單元會相互影響，當網路學習完成後，其輸出處理單元相鄰近者會具有相似的功能，也就是具有相似的連結加權值，所以可以用在群聚分析上來作資料的分類。自我組織法的網路架構如圖一[2]所示，主要元件包括下列三項：1.輸入單元：為網路的輸入變數、訓練樣本的輸入向量，或稱特徵向量，其神經元數目依待解決問題而定。2.輸...
