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

《应用自我组织类神经网路於24913.docx》由会员分享，可在线阅读，更多相关《应用自我组织类神经网路於24913.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、應用自我組織類神經網路於最長不相交路徑問題Evaluation Warning: The document was created with Spire.Doc for .NET.1應用自我組織類神經網路於最長不相交路徑問題The Study of the Largest Non-Crossing Route Problem Using Self-Organizing Neural Networks陳昭榮Chao-Ronng CChenn國立臺北科科技大學學電機工工程系摘要自我組織類類神經網網路具有有拓樸特特性，可可用來很很有效率率的求解解銷售員員旅行問問題。本本文提出出一新的的研究問問題，為

2、為對於平平面上的的一群節節點，除除了起點點外每一一節點恰恰好經過過一次之之不相交交封閉路路徑，求求出最長長距離之之路徑。針針對此問問題，本本文提出出數個與與兩線段段相交有有關的定定理，及及改進原原先用以以求解銷銷售員旅旅行問題題自我組組織之方方法，用用於求解解此一最最大化不不相交封封閉路徑徑之問題題。由數數個實例例之模擬擬結果證證明可用用以得到到不錯之之解答。關鍵詞：類類神經網網路、自自我組織織法、銷銷售員旅旅行問題題、最長長不相交交路徑問問題。投稿受理時時間：991年33月155日審查通通過時間間：911年5月月10日日ABSTRRACTTSelf-orgganiizinng nneurra

3、l nettworrk hhas thee toopollogiicall chharaacteerissticcs tthatt caan bbe eeffeectiivelly uusedd inn soolviing thee trraveelinng ssaleesmaan pprobblemm. Thiis ppapeer ppropposees aa noovell prrobllem of opttimiizinng tthe nonn-crrosssingg clloseed rroutte iin wwhicch eeachh noode, exxceppt ffor the

4、e sttarttingg poointt, iis oonlyy viisitted oncce sso tthatt thhe ttotaal vvisiitinng llenggth is maxximiizedd. Somme ttheooremms oof tthe intterssecttionn off twwo llinees aare revviewwed in thee paaperr. Andd, tthe sellf-oorgaanizzingg neetwoork alggoriithmm off soolviing thee trraveelinng ssalees

5、maan pprobblemm iss moodiffiedd too soolvee thhe pprobblemm. Simmulaatioon rresuultss shhow thaat tthe proopossed alggoriithmm haas ggoodd peerfoormaancees oon tthe opttimiizattionn off thhe ttripp-leengtth.Keywoordss : Arttifiiciaal NNeurral Nettworrk, Sellf-OOrgaanizzingg Meethood, Traavellingg Sa

6、alessmann Prrobllem, Laargeest Nonn-Crrosssingg Rooutee Prrobllem.612壹、簡介近年來，研研究人員員渴望能能發展出出比目前前電腦更更聰明的的機器來來服務人人類，因因此類神神經網路路成為熱熱中之研研究方向向之一。它它是一個個相當年年輕的科科學，在在19887年才才辦第一一屆ICCNN研研討會，119899年辦第第一屆IIJCNNN研討討會，119900年IEEEE之之Neuurall Neetwoork創創刊。但但與類神神經網路路相關之之研究近近幾年來來在各領領域之刊刊物均可可看到。關關於類神神經網路路應用於於解最佳佳化問題題，在

7、各各工程領領域皆有有不錯之之突破，使使得最佳佳化問題題在減少少執行時時間、節節省使用用記憶體體上皆有有不錯之之成果。類神經網路路有下列列幾項之之優點：(1) 俱平平行處理理能力，故故速度快快，可作作即時輸輸出。(2) 知識或或資料是是分散的的儲存在在大量的的加權值值中，故故對神經經鍵局部部傷害不不致影響響整體功功能。(3) 具學習習能力，可可以自行行由例子子中尋找找規則性性而具專專門知識識。(44) 有有保持菁菁華（aabsttracctioon）的的能力。當當接受足足夠訓練練後，雖雖然輸入入不完整整或有雜雜訊的資資料，亦亦能由其其中特性性，得知知其原來來面貌。類神經網路路之分類類，若依依學習

8、方方式來分分，可分分成監督督式(ssupeerviisedd)學習習及非監監督式(unssupeerviisedd)學習習兩種。常常見的監監督式類類神經網網路有多多層認知知網路(mullti-layyer perrcepptroon)和和Hoppfieeld網網路。在在學習過過程中，多多組訓練練樣本循循序的被被輸入網網路中，每每組訓練練樣本包包括一個個輸入向向量及一一個理想想輸出向向量。這這類網路路能比較較實際輸輸出及理理想輸出出，得到到一個差差值（eerroor），此此差值會會由後往往前一層層一層傳傳遞，加加權值則則依某種種學習法法則來調調整。這這個動作作持續到到差值小小於容忍忍值，於於是學

9、習習完成。常見的非監監督式類類神經網網路有KKohoonenn自我組組織網路路和Caarpeenteer/GGrosssbeerg網網路。訓訓練樣本本裡不包包括理想想輸出向向量。這這時網路路被希望望能自行行由輸入入向量歸歸納出訓訓練樣本本的規則則性或相相關性，並並產生一一個合理理的輸出出。貳、自我組組織網路路自我組織網網路(SSelff- OOrgaanizzingg Maap, SOMM)由TT. KKohoonenn在19980年年提出此此網路架架構11。其其基本原原理可溯溯自大腦腦結構的的特性，大大腦中相相似功能能的腦細細胞具有有聚集在在一起之之特性，例例如人類類大腦中中有專司司視覺、聽

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

11、而定。具具有網網路拓撲撲以及及鄰近近區域的觀念念。3.網路路連結：輸出層層神經元元與輸入入層相連連結的加加權值所所構成的的向量，表表示兩者者間映射射之函數數關係。當當網路學學習完成成後，其其相臨近近之神經經元會具具有相似似的加權權值。圖一自我我組織映映射圖網網路架構構自我組織演演算法的的主要目目標，就就是以特特徵映射射的方式式，將任任意維度度的輸入入向量，映映射至一一維或二二維的特特徵映射射圖上。也也就是說說，其特特徵映射射可以視視為一種種將輸入入高維空空間以非非線性的的投影方方式，轉轉換成神神經元所所構成的的矩陣空空間。這這種投影影方式，可可以將輸輸入向量量間的鄰鄰近關係係，以二二維或一一維

12、的方方式表現現出來。詳詳細之演演算法及及特性，見見於參考考文獻3-44。參、問題之之數學模模型及定定理對於路徑距距離問題題，一般般來說，可可以用一一n個節點點之系統統來說明明。假設設節點分分別標示示為A,B,CC,.，而而其距離離分別為為dAB, dAC, .,dBC, .，其中中距離採採用歐基基里得距距離，即即任何兩兩點X(x1,x2)與Y(y11,y2)之距距離為ddXY =。本文研究之之問題是是要獲得得一恰好好經過每每一節點點一次且且回到原原來起始始點之封封閉路徑徑。要求求出不相相交且最最長距離離之路徑徑。路徑徑總長度度之定義義為：若若路徑之之走法為為B,FF,E,G,.,W之序序列，則

13、則總長度度為d = dBF + ddFE+.+dWWB。3本文研究之之問題與與著名的的銷售售員旅行行問題(Trraveelinng SSaleesmaan PProbblemm, TTSP)5-9性性質相似似，但最最佳化之之目標恰恰好相反反。銷售售員旅行行問題為為求出最最短之總總路徑長長度，本本文研究究之問題題為求出出最長之之總路徑徑長度，且且路徑不不相交為為本問題題外加之之限制條條件。因因此本文文之問題題與TSSP問題題在求解解之性質質類似。為為對於一一n個節點點之最長長不相交交路徑問問題，共共有n!/22n個不同同的封閉閉路徑，為為無法得得到真正正的最佳佳化解，稱稱為一完全非非決定性性多項

14、式式 （CCompplette NNonddeteermiinissticc Poolynnomiial, NPP-coomplletee）之問問題，因因其求解解所需之之時間隨隨著節點點數目之之增加而而成指數數之成長長。為了以數學學模型表表示本研研究問題題，所經經過路徑徑之關係係，使用用Unxn矩陣來來表示，當當第x節點為為路徑序序列之第第i個經過過之節點點時，元元素ux,ii之值設設為1，否否則設為為0。下下列限制制條件之之(1)、(22)和(3)表表示每行行及每列列都恰好好有一個個1，其其餘為00。即除除起始點點外，每每個節點點恰好經經過一次次。對於於限制條條件四之之判斷方方法，將將在定理

15、理三及定定理四說說明。綜合以上說說明，本本文研究究之議題題以矩陣陣元素型型態表示示如下：Maximmizee F(U)=dxy ux,ii uy,ii+1Subjeect to ：(1) uux,ii 00,1 , xx = 1,22,.,nn , ii = 1,22,.,nn(2) = 11 xx = 1,22,.,nn(3) = 11 ii = 1,22,.,nn(4) 路路徑中任任意兩條條線段不不可交錯錯。其中：n為為節點總總數目。dxy 為為節點 x, y 之之歐基里里得距離離。ux,i 表示第第x節點為為路徑序序列之第第i個經過過之節點點關係。令令uy,n+1 uy,1。為了方便說說

16、明本文文所提出出之演算算法，先先行提出出下列數數個與兩兩線段相相交性質質相關之之定理及及說明。定理一：在在路徑中中任何有有交錯之之兩條線線段，必必定可以以改成不不交錯之之兩條線線段，但但距離將將較短。4證明：如圖圖二所示示，若原原來路徑徑包含AAB與CCD但交交錯，可可以改為為AC和和BD且且不交錯錯。由三三角形中中任兩邊邊之和大大於第三三邊之性性質，可可得(AAB+CCD) (AC+BD)，故得得證。 A C D BB圖二 定定理一證證明示意意圖定理二：（交交錯線段段之改善善方法）藉由定理一之改變方式，可以將此交錯線段改進成為不交錯線段。說明：如圖圖二中，假假設A點點和D點點之路徑徑間有MM

17、個神經經元，則則利用定定理一所所得之改改善結果果，即使使仍與其其他線段段交錯，但但此交錯錯線間之之神經元元數目必必定減少少。因此此繼續使使用定理理一之方方法，必必定可以以將此交交錯線改改進為不不交錯線線。定理三：設設任意四四點A,B,CC,D，其其座標值值分別為為(a1, a2), (bb1, b2), (cc1, c2), 及(d1, d2)。若若座標值值符合下下列情形形之一時時，則AAB與CCD兩條條線段必必定不相相交。(1) MMIN (c1,d1) MAAX (a1,b1)(2) MMIN (a1,b1) MAAX (c1,d1)(3) MMIN (c2,d2) MAAX (a2,b2

18、)(4) MMIN (a2,b2) MAAX (c2,d2)其中MINN與MAXX分別表表示取最最小值和和最大值值。定理四：本定理理為完整整之判斷斷兩線段段是否相相交之方方法。圖圖三中設設A,BB,C,D之座座標值同同定理三三。則AAB與CCD之直直線方程程式分別別如下：f1(x,y) = (xx-a1)(b2-a2)- (y-a2)(b1-a1)= 0f2(x,y) = (xx-c1)(d2-c2)- (y-c2)(d1-c1) = 0將A,B點點之座標標值分別別代入ff2(x,y)，及及將C,D點之之座標值值分別代代入f1(x,y)。令令分別得得到a,b,c及d值。則則若ab 00且cd

19、00，則表表示兩線線段相交交，否則則表示兩兩線段不不相交。說明：利用用不等式式之性質質，若將將在直線線兩側之之兩點分分別代入入f(x,y)，必必定一為為正數，一一為負數數，故乘乘積必為為負數。若若將在同同一側之之兩點代代入，則則同為正正數或同同為負數數，故乘乘積必為為正數。 A(a1, a2) CC(c1, c2) D(dd1, d2) B(bb1, b2)圖三 兩兩線交錯錯之檢查查示意圖圖肆、自我組組織類神神經網路路演算法法本文提出之之演算法法分成兩兩階段執執行，第第一階段段為使用用自我組組織類神神經網路路演算法法求出一一封閉路路徑。第第二階段段則為判判斷此路路徑是否否有任何何兩條線線交錯之

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

21、每一一個神經經元之距距離，並並求出距距離最近近之神經經元，設設為jcc，公式式如下所所示。Di,j = ,j=1,22,3,.,RDi,jcc = MINN Di,j i=1,2,33,.,NN步驟四：新新增神經經元。如如果有兩兩個以上上不同節節點之最最接近神神經元為為同一個個時，則則增加神神經元個個數。其其座標值值與原來來之神經經元相同同，且各各自為某某一節點點之獲勝勝者。5步驟五：刪刪除神經經元。若有任何一一個神經經元在三三次完整整節點最最近距離離比較中中，都不不曾是任任一節點點之最近近神經元元時，則則刪除此此一神經經元。步驟六：移移動節點點i之最接接近神經經元jcc及其鄰鄰近之神神經元，

22、其其中令nn值為鄰鄰近神經經元j與jc之相相鄰個數數，在考考慮環狀狀連結情情形下，n值指定如下：n = MMIN ( |jc-j|, jc-j+R, j-jc+RR)座標W之移移動公式式如下所所示：wj1 = wj1 + f (GG, nn) * (xxi1-wj1)wj2 = wj2 + f (GG, nn) * (xxi2-wj2)其中f (G, n) = expp(-n2/G2)/ (11)步驟七：當當每一神神經元對對應之節節點不再再改變時時，輸出出此神經經元所對對應節點點順序，即即節點之之路徑，至至步驟八八。否則則，減少少G值，公公式如下下：G = GG * (1-a)，回到到步驟三三

23、。步驟八：計計算此路路徑長度度，並與與目前所所獲得之之最長不不相交長長度比較較，若較較小則到到步驟十十二。若若長度較較大則此此階段結結束，進進入第二二階段。第二階段為為判斷第第一階段段所獲得得之路徑徑是否有有任何兩兩條線段段交錯之之情形，若若有交錯錯時則以以定理二二之方法法改進為為不交錯錯路徑。由由於所選選取之隨隨機初值值如例子子一圖四四所示，為為一不相相交之均均勻分佈佈圓周之之神經元元，故所所獲得之之路徑，產產生兩條條線段相相交之比比率相當當低。第第二階段段演算法法如下：步驟九：利利用定理理三及定定理四之之性質作作檢查。若若路徑中中無任何何兩線段段交錯，則則到步驟驟十。否否則執行行步驟十十一

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

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

26、例中設設定G初初始值為為5.00，減少少率=0.1，試試驗次數數共2000次。圖四例一一之數據據及神經經元之隨隨機初始始路徑(o:節節點，xx:神經經元)在第一階段段之執行行中，神神經元所所構成之之路徑之之漸進圖圖如圖五五所示。經過200次試驗所得之結果，將所得到之不交叉路徑之長度，以質方圖(histogram)表示如圖六所示。而所獲得最長之不交叉路徑，長度為153.5，如圖七所示。(a)學學習5次次後(b)學學習155次後圖五例一一路徑之之學習漸漸進圖路徑長度圖六例一一之質方方圖圖七例一一獲得最最長之不不相交路路徑例子二：本例中使用用一166個節點點，且近近似正方方格之資資料。設設定初始始值

27、G= 5，減減少率= 00.055，及試試驗次數數共10000次次。所獲獲得最長長不相交交路徑之之結果，為為1855.5，如如圖八所所示。其其路徑長長度之質質方圖如如圖九所所示。7圖八 例例二獲得得最長之之不相交交路徑路徑長度圖九例二二之質方方圖例子三：本例中使用用一隨機機產生330個節節點為數數據。設設定減少少率=0.1，及及試驗次次數共5500次次。獲得得最長不不相交路路徑之結結果為2216.62，如如圖十所所示。圖十例三三獲得最最長之不不相交路路徑綜合本演算算法及以以上三個個例子之之結果，可可獲得以以下結論論：1.利用用自我組組織類神神經網路路來求解解最大不不相交路路徑問題題，為一一可得

28、到到接近最最佳值之之方法。由由參考文文獻55-9或質方方圖可得得到證明明，且最最大優點點為執行行速度相相當快。2.在本本文方法法中，a 為一介介於0和和1間之之參數，改改變值可以以使收斂斂時間增增快或減減慢。一一般而言言，當值接近近0時，需需費較多多時間但但效果較較好。此此外，由由公式(1)可可知，當當G 時，所所有f (G,n) 之之值為 1/；當G 00時，ff (GG,n) 僅僅有jcc 節點點不為00值，為為1/。3.本文文研究之之題目在在實務應應用方面面，如：電力電電纜公司司要作電電線絕緣緣老化試試驗時，已已知在一一空地上上設置如如圖八之之電桿，則則應如何何佈線可可使電纜纜線長度度最

29、長且且沒有交交錯，以以避免短短路之設設計方法法。4.本研研究議題題可以更更擴充為為，已知知節點數數目，8應應如何安安排節點點位置，以以獲得最最大之不不相交路路徑。陸、結論本文提出一一最大化化不相交交路徑問問題之描描述及數數學模型型。並提提出一些些相關之之定理與與一解題題之演算算法。由由實際例例子中發發現，自自我組織織演算法法除了可可用以求求解最短短路徑問問題外，應應用於求求解最長長路徑問問題亦可可得到不不錯之結結果。在求解此最最佳化路路徑之問問題方面面，使用用基因法法則、模模擬退火火法或HHopffielld類神神經網路路等方法法相信亦亦可以有有相當不不錯之結結果。期期望有更更多人針針對此一一

30、問題提提出不同同之演算算法來求求解此一一具挑戰戰性之問問題。參考文獻1KKohoonenn, TTeuvvo, Seelf-orgganiizattionn annd aassoociaativve mmemoory, Spprinngerr, 119888.2JJangg, JJ. SS., Neuuro-Fuzzzy andd Sooft Commputtingg, 全全華圖書書，19997。3林林昇甫、洪洪成安，神神經網路路入門與與圖樣辨辨識，全全華書局局，822年9月月。4LLipppmann, Riccharrd PP. An inttrodducttionn too coompuu

31、tinng wwithh neeuraal nnetss, IEEEE AASSPP Maag. pp. 4-222, Apprill 19987.5AAngeeniool, B., ett all. ,Seelf-orgganiizinng ffeatturee maaps andd thhe ttravvelllingg saalessmann prrobllem, NNeurral Nettworrks, Vool. 1, pp.2899-2993, 19888.6KKitaaorii, KK.; Murrakooshii, HH.; Funnakuubo, N , A nnew app

32、proaach to sollve thee trraveelinng ssaleesmaan pprobblemm byy ussingg thhe iimprroveed KKohoonenns sellf-oorgaanizzingg feeatuure mapp , Prooc. off thhe IIEEEE IEECONN 211st Intternnatiionaal CConffereencee , Voll. 2 , ppp. 13884-113888, 19995.7KKim, S.-J.; KKim, J.-H.; CChoii, HH.-MM.,An effficiie

33、ntt allgorrithhm ffor traavellingg saalessmann prrobllemss baasedd onn seelf-orgganiizinng ffeatturee maaps , Seccondd IEEEE Intternnatiionaal CConffereencee onn Fuuzzyy Syysteems, Vol.2, pp. 10085-10990, 19993.8MMatssuyaama, Y.,Commpettitiive sellf-oorgaanizzatiion andd coombiinattoriial opttimiiza

34、ttionn: aappllicaatioons to traavellingg saalessmann prrobllem , IJCCNN Intternnatiionaal JJoinnt CConffereencee onn Neeuraal NNetwworkks, Voll. 33, ppp. 8199-8224, 19990.9CCochhranne, E.MM.; Cocchraane, J.C., Expplorringg coompeetittionn annd cco-ooperratiion forr soolviing thee Euucliideaan ttravvelllingg saalessmann prrobllem by usiing sellf-oorgaanizzingg maap , NNintth IInteernaatioonall Coonfeerennce on Arttifiiciaal NNeurral Nettworrks, Vool. 1, pp. 1880 -1855, 119999.