应用自我组织类神经网路於

1、臺北科技大學學報第三十五之二期.應用自我組織類神經網路於最長不相交路徑問題 PAGE 52：.； PAGE 531應用自我組織類神經網路於最長不相交路徑問題The Study of the Largest Non-Crossing Route Problem Using Self-Organizing Neural Networks陳昭榮Chao-Rong Chen國立臺北科技大學電機工程系摘要自我組織類神經網路具有拓樸特性，可用來很有效率的求解銷售員游览問題。本文提出一新的研讨問題，為對於平面上的一群節點，除了起點外每一節點恰好經過一次之不相交封閉路徑，求出最長距離之路徑。針對此問題，本文提

2、出數個與兩線段相交有關的定理，及改進原先用以求解銷售員游览問題自我組織之方法，用於求解此一最大化不相交封閉路徑之問題。由數個實例之模擬結果證明可用以得到不錯之解答。關鍵詞：類神經網路、自我組織法、銷售員游览問題、最長不相交路徑問題。投稿受理時間：91年3月15日審查通過時間：91年5月10日ABSTRACTSelf-organizing neural network has the topological characteristics that can be effectively used in solving the traveling salesman problem. This pa

3、per proposes a novel problem of optimizing the non-crossing closed route in which each node, except for the starting point, is only visited once so that the total visiting length is maximized. Some theorems of the intersection of two lines are reviewed in the paper. And, the self-organizing network

4、algorithm of solving the traveling salesman problem is modified to solve the problem. Simulation results show that the proposed algorithm has good performances on the optimization of the trip-length.Keywords : Artificial Neural Network, Self-Organizing Method, Traveling Salesman Problem, Largest Non

5、-Crossing Route Problem.2壹、簡介近年來，研讨人員盼望能發展出比目前電腦更聰明的機器來服務人類，因此類神經網路成為熱中之研讨方向之一。它是一個相當年輕的科學，在1987年才辦第一屆ICNN研討會，1989年辦第一屆IJCNN研討會，1990年IEEE之Neural Network創刊。但與類神經網路相關之研讨近幾年來在各領域之刊物均可看到。關於類神經網路應用於解最正确化問題，在各工程領域皆有不錯之突破，使得最正确化問題在減少執行時間、節省运用記憶體上皆有不錯之成果。類神經網路有以下幾項之優點：(1) 俱平行處理才干，故速度快，可作即時輸出。(2) 知識或資料是分散的儲存

6、在大量的加權值中，故對神經鍵部分傷害不致影響整體功能。(3) 具學習才干，可以自行由例子中尋找規則性而具專門知識。(4) 有坚持菁華abstraction的才干。當接受足夠訓練後，雖然輸入不完好或有雜訊的資料，亦能由其中特性，得知其原來容颜。類神經網路之分類，假设依學習方式來分，可分成監督式(supervised)學習及非監督式(unsupervised)學習兩種。常見的監督式類神經網路有多層認知網路(multi-layer perceptron)和Hopfield網路。在學習過程中，多組訓練樣本循序的被輸入網路中，每組訓練樣本包括一個輸入向量及一個理想輸出向量。這類網路能比較實際輸出及理想輸

7、出，得到一個差值error，此差值會由後往前一層一層傳遞，加權值則依某種學習法則來調整。這個動作持續到差值小於容忍值，於是學習完成。常見的非監督式類神經網路有Kohonen自我組織網路和Carpenter/Grossberg網路。訓練樣本裡不包括理想輸出向量。這時網路被希望能自行由輸入向量歸納出訓練樣本的規則性或相關性，並產生一個合理的輸出。貳、自我組織網路自我組織網路(Self- Organizing Map, SOM)由T. Kohonen在1980年提出此網路架構1。其根本原理可溯自大腦結構的特性，大腦中类似功能的腦細胞具有聚集在一同之特性，例如人類大腦中有專司視覺、聽覺、味覺等區塊，也

8、就是腦神經細胞有 物以類聚的特性，自我組織映射圖網路模拟這種特性，其輸出處理單元會相互影響，當網路學習完成後，其輸出處理單元相鄰近者會具有类似的功能，也就是具有类似的連結加權值，所以可以用在群聚分析上來作資料的分類。自我組織法的網路架構如圖一2所示，主要元件包括以下三項：1.輸入單元：為網路的輸入變數、訓練樣本的輸入向量，或稱特徵向量，其神經元數目依待解決問題而定。2.輸出單元：為網路的輸出變數，即訓練樣本的分類，其神經元數目依問題複雜情況而定。具有網路拓撲以及鄰近區域的觀念。3.網路連結：輸出層神經元與輸入層相連結的加權值所構成的向量，表示兩者間映射之函數關係。當網路學習完成後，其相臨近之神

9、經元會具有类似的加權值。圖一自我組織映射圖網路架構自我組織演算法的主要目標，就是以特徵映射的方式，將恣意維度的輸入向量，映射至一維或二維的特徵映射圖上。也就是說，其特徵映射可以視為一種將輸入高維空間以非線性的投影方式，轉換成神經元所構成的矩陣空間。這種投影方式，可以將輸入向量間的鄰近關係，以二維或一維的方式表現出來。詳細之演算法及特性，見於參考文獻3-4。參、問題之數學模型及定理對於路徑距離問題，普通來說，可以用一n個節點之系統來說明。假設節點分別標示為A,B,C,.，而其距離分別為dAB, dAC, .,dBC, .，其中距離採用歐基里得距離，即任何兩點X(x1,x2)與Y(y1,y2)之距

10、離為dXY =。本文研讨之問題是要獲得一恰好經過每一節點一次且回到原來起始點之封閉路徑。要求出不相交且最長距離之路徑。路徑總長度之定義為：假设路徑之走法為B,F,E,G,.,W之序列，則總長度為d = dBF + dFE+.+dWB。3本文研讨之問題與著名的銷售員游览問題(Traveling Salesman Problem, TSP)5-9性質类似，但最正确化之目標恰好相反。銷售員游览問題為求出最短之總路徑長度，本文研讨之問題為求出最長之總路徑長度，且路徑不相交為本問題外加之限制條件。因此本文之問題與TSP問題在求解之性質類似。為對於一n個節點之最長不相交路徑問題，共有n!/2n個不同的封閉

11、路徑，為無法得到真正的最正确化解，稱為一完全非決定性多項式 Complete Nondeterministic Polynomial, NP-complete之問題，因其求解所需之時間隨著節點數目之添加而成指數之成長。為了以數學模型表示本研讨問題，所經過路徑之關係，运用Unxn矩陣來表示，當第x節點為路徑序列之第i個經過之節點時，元素ux,i之值設為1，否則設為0。以下限制條件之(1)、(2)和(3)表示每行及每列都恰好有一個1，其餘為0。即除起始點外，每個節點恰好經過一次。對於限制條件四之判斷方法，將在定理三及定理四說明。綜合以上說明，本文研讨之議題以矩陣元素型態表示如下：Maximize

12、F(U)=dxy ux,i uy,i+1Subject to ：(1) ux,i 0,1 , x = 1,2,.,n , i = 1,2,.,n(2) = 1 x = 1,2,.,n(3) = 1 i = 1,2,.,n(4) 路徑中恣意兩條線段不可交錯。其中：n為節點總數目。dxy 為節點 x, y 之歐基里得距離。ux,i 表示第x節點為路徑序列之第i個經過之節點關係。令uy,n+1 uy,1。為了方便說明本文所提出之演算法，先行提出以下數個與兩線段相交性質相關之定理及說明。定理一：在路徑中任何有交錯之兩條線段，必定可以改成不交錯之兩條線段，但距離將較短。4證明：如圖二所示，假设原來路徑包

13、含AB與CD但交錯，可以改為AC和BD且不交錯。由三角形中任兩邊之和大於第三邊之性質，可得(AB+CD) (AC+BD)，故得證。 A C D B圖二 定理一證明表示圖定理二：交錯線段之改善方法藉由定理一之改變方式，可以將此交錯線段改進成為不交錯線段。說明：如圖二中，假設A點和D點之路徑間有M個神經元，則利用定理一所得之改善結果，即使仍與其他線段交錯，但此交錯線間之神經元數目必定減少。因此繼續运用定理一之方法，必定可以將此交錯線改進為不交錯線。定理三：設恣意四點A,B,C,D，其座標值分別為(a1, a2), (b1, b2), (c1, c2), 及(d1, d2)。假设座標值符合以下情形之

14、一時，則AB與CD兩條線段必定不相交。(1) MIN (c1,d1) MAX (a1,b1)(2) MIN (a1,b1) MAX (c1,d1)(3) MIN (c2,d2) MAX (a2,b2)(4) MIN (a2,b2) MAX (c2,d2)其中MIN與MAX分別表示取最小值和最大值。定理四：本定理為完好之判斷兩線段能否相交之方法。圖三中設A,B,C,D之座標值同定理三。則AB與CD之直線方程式分別如下：f1(x,y) = (x-a1)(b2-a2)- (y-a2)(b1-a1)= 0f2(x,y) = (x-c1)(d2-c2)- (y-c2)(d1-c1) = 0將A,B點之座

15、標值分別代入f2(x,y)，及將C,D點之座標值分別代入f1(x,y)。令分別得到a,b,c及d值。則假设ab 0且cd 0，則表示兩線段相交，否則表示兩線段不相交。說明：利用不等式之性質，假设將在直線兩側之兩點分別代入f(x,y)，必定一為正數，一為負數，故乘積必為負數。假设將在同一側之兩點代入，則同為正數或同為負數，故乘積必為正數。 A(a1, a2) C(c1, c2) D(d1, d2) B(b1, b2)圖三 兩線交錯之檢查表示圖肆、自我組織類神經網路演算法本文提出之演算法分成兩階段執行，第一階段為运用自我組織類神經網路演算法求出一封閉路徑。第二階段則為判斷此路徑能否有任何兩條線交錯

16、之情形；假设有交錯之情形，則以定理二所提出之方法將交錯除去，並經比較求出最長距離之路徑。第一階段运用之方法，參考相關之文獻5-9，經整理與改進得到以下演算法：步驟一：讀入N個節點之座標值為(xi1,xi2), i=1,2,.,N。設定減少率值，及試驗次數Z。步驟二：設定G之初始值；隨機改變節點之順序，訂定一與節點數目一样神經元之自我組織類神經網路；隨機產生均勻分佈於一圓周之神經元，設初始值座標(wj1,wj2), j=1,2,.,N，令神經元總數目R=N。步驟三：計算每一節點i與每一個神經元之距離，並求出距離最近之神經元，設為jc，公式如下所示。Di,j = ,j=1,2,3,.,RDi,jc

17、 = MIN Di,j i=1,2,3,.,N步驟四：新增神經元。假设有兩個以上不同節點之最接近神經元為同一個時，則添加神經元個數。其座標值與原來之神經元一样，且各自為某一節點之獲勝者。5步驟五：刪除神經元。假设有任何一個神經元在三次完好節點最近距離比較中，都不曾是任一節點之最近神經元時，則刪除此一神經元。步驟六：移動節點i之最接近神經元jc及其鄰近之神經元，其中令n值為鄰近神經元j與jc之相鄰個數，在考慮環狀連結情形下，n值指定如下：n = MIN ( |jc-j|, jc-j+R, j-jc+R)座標W之移動公式如下所示：wj1 = wj1 + f (G, n) * (xi1-wj1)wj

18、2 = wj2 + f (G, n) * (xi2-wj2)其中f (G, n) = exp(-n2/G2)/ (1)步驟七：當每一神經元對應之節點不再改變時，輸出此神經元所對應節點順序，即節點之路徑，至步驟八。否則，減少G值，公式如下：G = G * (1-)，回到步驟三。步驟八：計算此路徑長度，並與目前所獲得之最長不相交長度比較，假设較小則到步驟十二。假设長度較大則此階段結束，進入第二階段。第二階段為判斷第一階段所獲得之路徑能否有任何兩條線段交錯之情形，假设有交錯時則以定理二之方法改進為不交錯路徑。由於所選取之隨機初值如例子一圖四所示，為一不相交之均勻分佈圓周之神經元，故所獲得之路徑，產生

19、兩條線段相交之比率相當低。第二階段演算法如下：步驟九：利用定理三及定理四之性質作檢查。假设路徑中無任何兩線段交錯，則到步驟十。否則執行步驟十一。 步驟十：由步驟八可知此路徑長度比原先最大長度長，儲存最長路徑距離和連結順序。到步驟十二。步驟十一：將交錯線段改進為不交錯線段。利用定理二之方法，將交錯線段改進為不交錯線段。計算新路徑之總長度。以路徑長度作最大化之比較，儲存最長路徑距離和連結順序。步驟十二：回到步驟二產生另一隨機初始值重新執行，直到完成試驗次數。然後輸出最長路徑及其長度。第二階段之演算法，可利用以下方法提高效率：61.判斷任何兩線段能否交錯之方法，先利用定理三之方法，可加快判斷速度。在

20、利用定理四之不等式判別方法時，對於任不断線方程式建立後，可直接代入一切其他路徑之點，故亦可提高計算速度。2.利用定理二之方法將交錯線段改進成為不交錯線段，有時相當耗時，故可以在符合一些限制下才考慮，如：長度超過最大長度某一百分比，或交錯線數目少於三條。在此情況下將被認為改進後較有機會超過原來之最長路徑。伍、實例模擬及討論本節中利用三個實例來說明本演算法之應用及結果：例子一：本例中运用一24個節點，構成兩個正十二邊形之數據，如圖四所示。神經元初始值以 x 表示。本例中設定G初始值為5.0，減少率=0.1，試驗次數共200次。圖四例一之數據及神經元之隨機初始路徑(o:節點，x:神經元)在第一階段之

21、執行中，神經元所構成之路徑之漸進圖如圖五所示。經過200次試驗所得之結果，將所得到之不交叉路徑之長度，以質方圖(histogram)表示如圖六所示。而所獲得最長之不交叉路徑，長度為153.5，如圖七所示。(a)學習5次後(b)學習15次後圖五例一路徑之學習漸進圖路徑長度圖六例一之質方圖圖七例一獲得最長之不相交路徑例子二：本例中运用一16個節點，且近似正方格之資料。設定初始值G= 5，減少率= 0.05，及試驗次數共1000次。所獲得最長不相交路徑之結果，為185.5，如圖八所示。其路徑長度之質方圖如圖九所示。7圖八 例二獲得最長之不相交路徑路徑長度圖九例二之質方圖例子三：本例中运用一隨機產生3

22、0個節點為數據。設定減少率=0.1，及試驗次數共500次。獲得最長不相交路徑之結果為216.62，如圖十所示。圖十例三獲得最長之不相交路徑綜合本演算法及以上三個例子之結果，可獲得以下結論：1.利用自我組織類神經網路來求解最大不相交路徑問題，為一可得到接近最正确值之方法。由參考文獻5-9或質方圖可得到證明，且最大優點為執行速度相當快。2.在本文方法中， 為一介於0和1間之參數，改變值可以使收斂時間增快或減慢。普通而言，當值接近0時，需費較多時間但效果較好。此外，由公式(1)可知，當G 時，一切f (G,n) 之值為 1/；當G 0時，f (G,n) 僅有jc 節點不為0值，為1/。3.本文研讨之

23、題目在實務應用方面，如：電力電纜公司要作電線絕緣老化試驗時，知在一空地上設置如圖八之電桿，則應如何佈線可使電纜線長度最長且沒有交錯，以防止短路之設計方法。4.本研讨議題可以更擴充為，知節點數目，8應如何安排節點位置，以獲得最大之不相交路徑。陸、結論本文提出一最大化不相交路徑問題之描画及數學模型。並提出一些相關之定理與一解題之演算法。由實際例子中發現，自我組織演算法除了可用以求解最短路徑問題外，應用於求解最長路徑問題亦可得到不錯之結果。在求解此最正确化路徑之問題方面，运用基因法則、模擬退火法或Hopfield類神經網路等方法置信亦可以有相當不錯之結果。期望有更多人針對此一問題提出不同之演算法來求

24、解此一具挑戰性之問題。參考文獻1Kohonen, Teuvo, Self-organization and associative memory, Springer, 1988.2Jang, J. S., Neuro-Fuzzy and Soft Computing, 全華圖書，1997。3林昇甫、洪成安，神經網路入門與圖樣辨識，全華書局，82年9月。4Lippman, Richard P. An introduction to computing with neural nets, IEEE ASSP Mag. pp. 4-22, April 1987.5Angeniol, B., et al. ,Self-organizing feature maps and the travelling salesman problem, Neural Networks, Vol. 1, pp.289-293, 1988.6Kitaori, K.; Murakoshi, H.; Funakubo, N , A new approach to solve the traveling s