《(组织设计）应用自我组织类神经网路於》由会员分享，可在线阅读，更多相关《(组织设计）应用自我组织类神经网路於（8页珍藏版）》请在金锄头文库上搜索。
1、應用自我組織類神經網路於最長不相交路徑問題1應用自我組織類神經網路於最長不相交路徑問題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 paper proposes a novel problem of opt
3、imizing 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 algorithm of solving the traveling
4、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-Crossing Route Problem.512壹、簡介近年來，
5、研究人員渴望能發展出比目前電腦更聰明的機器來服務人類，因此類神經網路成為熱中之研究方向之一。它是一個相當年輕的科學，在1987年才辦第一屆ICNN研討會，1989年辦第一屆IJCNN研討會，1990年IEEE之Neural Network創刊。但與類神經網路相關之研究近幾年來在各領域之刊物均可看到。關於類神經網路應用於解最佳化問題，在各工程領域皆有不錯之突破，使得最佳化問題在減少執行時間、節省使用記憶體上皆有不錯之成果。類神經網路有下列幾項之優點：(1) 俱平行處理能力，故速度快，可作即時輸出。(2) 知識或資料是分散的儲存在大量的加權值中，故對神經鍵局部傷害不致影響整體功能。(3) 具學習能
6、力，可以自行由例子中尋找規則性而具專門知識。(4) 有保持菁華（abstraction）的能力。當接受足夠訓練後，雖然輸入不完整或有雜訊的資料，亦能由其中特性，得知其原來面貌。類神經網路之分類，若依學習方式來分，可分成監督式(supervised)學習及非監督式(unsupervised)學習兩種。常見的監督式類神經網路有多層認知網路(multi-layer perceptron)和Hopfield網路。在學習過程中，多組訓練樣本循序的被輸入網路中，每組訓練樣本包括一個輸入向量及一個理想輸出向量。這類網路能比較實際輸出及理想輸出，得到一個差值（error），此差值會由後往前一層一層傳遞，加權值
7、則依某種學習法則來調整。這個動作持續到差值小於容忍值，於是學習完成。常見的非監督式類神經網路有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)之距離為dXY =。本文研究之問題是要獲得一恰好經過每一節點一次且回
10、到原來起始點之封閉路徑。要求出不相交且最長距離之路徑。路徑總長度之定義為：若路徑之走法為B,F,E,G,.,W之序列，則總長度為d = dBF + dFE+.+dWB。3本文研究之問題與著名的銷售員旅行問題(Traveling Salesman Problem, TSP)5-9性質相似，但最佳化之目標恰好相反。銷售員旅行問題為求出最短之總路徑長度，本文研究之問題為求出最長之總路徑長度，且路徑不相交為本問題外加之限制條件。因此本文之問題與TSP問題在求解之性質類似。為對於一n個節點之最長不相交路徑問題，共有n!/2n個不同的封閉路徑，為無法得到真正的最佳化解，稱為一完全非決定性多項式 （Comp
11、lete Nondeterministic Polynomial, NP-complete）之問題，因其求解所需之時間隨著節點數目之增加而成指數之成長。為了以數學模型表示本研究問題，所經過路徑之關係，使用Unxn矩陣來表示，當第x節點為路徑序列之第i個經過之節點時，元素ux,i之值設為1，否則設為0。下列限制條件之(1)、(2)和(3)表示每行及每列都恰好有一個1，其餘為0。即除起始點外，每個節點恰好經過一次。對於限制條件四之判斷方法，將在定理三及定理四說明。綜合以上說明，本文研究之議題以矩陣元素型態表示如下：Maximize F(U)=dxy ux,i uy,i+1Subject to ：(
12、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證明：如圖二所示，若原來路徑包含AB與CD但交錯，可以改為AC和BD且不交錯。由三角形中任兩邊之和
13、大於第三邊之性質，可得(AB+CD) (AC+BD)，故得證。 A C D B圖二 定理一證明示意圖定理二：（交錯線段之改善方法）藉由定理一之改變方式，可以將此交錯線段改進成為不交錯線段。說明：如圖二中，假設A點和D點之路徑間有M個神經元，則利用定理一所得之改善結果，即使仍與其他線段交錯，但此交錯線間之神經元數目必定減少。因此繼續使用定理一之方法，必定可以將此交錯線改進為不交錯線。定理三：設任意四點A,B,C,D，其座標值分別為(a1, a2), (b1, b2), (c1, c2), 及(d1, d2)。若座標值符合下列情形之一時，則AB與CD兩條線段必定不相交。(1) MIN (c1,d1
14、) 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點之座標值分別代入f2(x,y)，及將C,D點之座標值分別代入f1(x,
15、y)。令分別得到a,b,c及d值。則若ab 0且cd 0，則表示兩線段相交，否則表示兩線段不相交。說明：利用不等式之性質，若將在直線兩側之兩點分別代入f(x,y)，必定一為正數，一為負數，故乘積必為負數。若將在同一側之兩點代入，則同為正數或同為負數，故乘積必為正數。 A(a1, a2) C(c1, c2) D(d1, d2) B(b1, b2)圖三 兩線交錯之檢查示意圖肆、自我組織類神經網路演算法本文提出之演算法分成兩階段執行，第一階段為使用自我組織類神經網路演算法求出一封閉路徑。第二階段則為判斷此路徑是否有任何兩條線交錯之情形；若有交錯之情形，則以定理二所提出之方法將交錯除去，並經比較求出最長距離之路徑。第一階段使用之方法，參考相關之文獻5-9，經整理與改進得到下列演算法：步驟一：讀入N個節點之座標值為(xi1,xi2), i=1,2,.,N。設定減少率值，及試驗次數Z。步驟二：設定G之初始值；隨機改變節點之順序，訂定一與節點數目相同神經元之自我組織類神經網路；隨機產生均
