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

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

1、應用自我組織類神經網路於最長不相交路徑問題1應用自我我組織類類神經網網路於最最長不相相交路徑徑問題The Stuudy of thee Laargeest Nonn-Crrosssingg Rooutee Prrobllem Usiing Sellf-OOrgaanizzingg Neeuraal NNetwworkks陳昭榮Chaoo-Roong Cheen國立臺北北科技大大學電機機工程系系摘要自我組織織類神經經網路具具有拓樸樸特性，可可用來很很有效率率的求解解銷售員員旅行問問題。本本文提出出一新的的研究問問題，為為對於平平面上的的一群節節點，除除了起點點外每一一節點恰恰好經過過一次之之不相

2、交交封閉路路徑，求求出最長長距離之之路徑。針對此此問題，本本文提出出數個與與兩線段段相交有有關的定定理，及及改進原原先用以以求解銷銷售員旅旅行問題題自我組組織之方方法，用用於求解解此一最最大化不不相交封封閉路徑徑之問題題。由數數個實例例之模擬擬結果證證明可用用以得到到不錯之之解答。關鍵詞：類神經經網路、自我組組織法、銷售員員旅行問問題、最最長不相相交路徑徑問題。投稿受理理時間：91年年3月115日審查通通過時間間：911年5月月10日日ABSTTRACCTSelff-orrganniziing neuurall neetwoork hass thhe ttopoologgicaal cchar

3、ractteriistiics thaat ccan be efffecttiveely useed iin ssolvvingg thhe ttravveliing sallesmman proobleem. Thhis papper prooposses a nnoveel pprobblemm off opptimmiziing thee noon-ccrosssinng cclossed rouute in whiich eacch nnodee, eexceept forr thhe sstarrtinng ppoinnt, is onlly vvisiitedd onnce so

4、thaat tthe tottal vissitiing lenngthh iss maaximmizeed. Soome theeoreems of thee innterrsecctioon oof ttwo linnes aree reevieewedd inn thhe ppapeer. Annd, thee seelf-orgganiizinng nnetwworkk allgorrithhm oof ssolvvingg thhe ttravveliing sallesmman proobleem iis mmodiifieed tto ssolvve tthe proobleem

5、. Siimullatiion ressultts sshoww thhat thee prropoosedd allgorrithhm hhas goood pperfformmancces on thee opptimmizaatioon oof tthe triip-llenggth.Keywwordds : Arrtifficiial Neuurall Neetwoork, Seelf-Orgganiizinng MMethhod, Trraveelinng SSaleesmaan PProbblemm, LLarggestt Noon-CCrosssinng RRoutte PPro

6、bblemm.552壹、簡介介近年來，研研究人員員渴望能能發展出出比目前前電腦更更聰明的的機器來來服務人人類，因因此類神神經網路路成為熱熱中之研研究方向向之一。它是一一個相當當年輕的的科學，在在19887年才才辦第一一屆ICCNN研研討會，119899年辦第第一屆IIJCNNN研討討會，119900年IEEEE之之Neuurall Neetwoork創創刊。但但與類神神經網路路相關之之研究近近幾年來來在各領領域之刊刊物均可可看到。關於類類神經網網路應用用於解最最佳化問問題，在在各工程程領域皆皆有不錯錯之突破破，使得得最佳化化問題在在減少執執行時間間、節省省使用記記憶體上上皆有不不錯之成成果。類

7、神經網網路有下下列幾項項之優點點：(11) 俱俱平行處處理能力力，故速速度快，可可作即時時輸出。(2) 知識識或資料料是分散散的儲存存在大量量的加權權值中，故故對神經經鍵局部部傷害不不致影響響整體功功能。(3) 具學習習能力，可可以自行行由例子子中尋找找規則性性而具專專門知識識。(44) 有有保持菁菁華（aabsttracctioon）的的能力。當接受受足夠訓訓練後，雖雖然輸入入不完整整或有雜雜訊的資資料，亦亦能由其其中特性性，得知知其原來來面貌。類神經網網路之分分類，若若依學習習方式來來分，可可分成監監督式(suppervviseed)學學習及非非監督式式(unnsuppervviseed)

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

9、roossbbergg網路。訓練樣樣本裡不不包括理理想輸出出向量。這時網網路被希希望能自自行由輸輸入向量量歸納出出訓練樣樣本的規規則性或或相關性性，並產產生一個個合理的的輸出。貳、自我我組織網網路自我組織織網路(Sellf- Orgganiizinng MMap, SOOM)由由T. Kohhoneen在119800年提出出此網路路架構1。其基本本原理可可溯自大大腦結構構的特性性，大腦腦中相似似功能的的腦細胞胞具有聚聚集在一一起之特特性，例例如人類類大腦中中有專司司視覺、聽覺、味覺等等區塊，也也就是腦腦神經細細胞有 物以以類聚的特性性，自我我組織映映射圖網網路模仿仿這種特特性，其其輸出處處理單

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

11、成成的向量量，表示示兩者間間映射之之函數關關係。當當網路學學習完成成後，其其相臨近近之神經經元會具具有相似似的加權權值。圖一自自我組織織映射圖圖網路架架構自我組織織演算法法的主要要目標，就就是以特特徵映射射的方式式，將任任意維度度的輸入入向量，映映射至一一維或二二維的特特徵映射射圖上。也就是是說，其其特徵映映射可以以視為一一種將輸輸入高維維空間以以非線性性的投影影方式，轉轉換成神神經元所所構成的的矩陣空空間。這這種投影影方式，可可以將輸輸入向量量間的鄰鄰近關係係，以二二維或一一維的方方式表現現出來。詳細之之演算法法及特性性，見於於參考文文獻33-4。參、問題題之數學學模型及及定理對於路徑徑距離

12、問問題，一一般來說說，可以以用一nn個節點點之系統統來說明明。假設設節點分分別標示示為A,B,CC,.，而而其距離離分別為為dAB, dAC, .,dBC,.，其中中距離採採用歐基基里得距距離，即即任何兩兩點X(x1,x2)與Y(yy1,y2)之距距離為ddXY=。本文研究究之問題題是要獲獲得一恰恰好經過過每一節節點一次次且回到到原來起起始點之之封閉路路徑。要要求出不不相交且且最長距距離之路路徑。路路徑總長長度之定定義為：若路徑徑之走法法為B,F,EE,G,.,W之之序列，則則總長度度為d=dBF+ dFEE+.+dWWB。3本文研究究之問題題與著名名的銷銷售員旅旅行問題題(TTravveli

13、ing Sallesmman Proobleem, TSPP)55-9性質相相似，但但最佳化化之目標標恰好相相反。銷銷售員旅旅行問題題為求出出最短之之總路徑徑長度，本本文研究究之問題題為求出出最長之之總路徑徑長度，且且路徑不不相交為為本問題題外加之之限制條條件。因因此本文文之問題題與TSSP問題題在求解解之性質質類似。為對於於一n個節點點之最長長不相交交路徑問問題，共共有n!/22n個不同同的封閉閉路徑，為為無法得得到真正正的最佳佳化解，稱稱為一完全非非決定性性多項式式 （CCompplette NNonddeteermiinissticc Poolynnomiial, NPP-coompll

14、etee）之問問題，因因其求解解所需之之時間隨隨著節點點數目之之增加而而成指數數之成長長。為了以數數學模型型表示本本研究問問題，所所經過路路徑之關關係，使使用Unnxn矩陣來來表示，當當第x節點為為路徑序序列之第第i個經過過之節點點時，元元素ux,ii之值設設為1，否否則設為為0。下下列限制制條件之之(1)、(22)和(3)表表示每行行及每列列都恰好好有一個個1，其其餘為00。即除除起始點點外，每每個節點點恰好經經過一次次。對於於限制條條件四之之判斷方方法，將將在定理理三及定定理四說說明。綜合以上上說明，本本文研究究之議題題以矩陣陣元素型型態表示示如下：Maxiimizze FF(U)=dxy

15、ux,iiuy,ii+1Subjjectt too ：(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) 路徑中中任意兩兩條線段段不可交交錯。其中：nn為節點點總數目目。dxy 為節點點 x, y 之歐基基里得距距離。ux,ii 表示示第x節點為為路徑序序列之第第i個經過過之節點點關係。令uy,n+1uy,1。為了方便便說明本本文所提提出之演演算法，先先行提出出下列數數個與兩兩線段相相交性質質相關之之定理及及說明。定理一：在路徑徑中任何何有交錯錯之兩條

16、條線段，必必定可以以改成不不交錯之之兩條線線段，但但距離將將較短。4證明：如如圖二所所示，若若原來路路徑包含含AB與與CD但但交錯，可可以改為為AC和和BD且且不交錯錯。由三三角形中中任兩邊邊之和大大於第三三邊之性性質，可可得(AAB+CCD) (AC+BD)，故得得證。 A C DD B圖二 定理一一證明示示意圖定理二：（交錯錯線段之之改善方方法）藉藉由定理理一之改改變方式式，可以以將此交交錯線段段改進成成為不交交錯線段段。說明：如如圖二中中，假設設A點和和D點之之路徑間間有M個個神經元元，則利利用定理理一所得得之改善善結果，即即使仍與與其他線線段交錯錯，但此此交錯線線間之神神經元數數目必定

17、定減少。因此繼繼續使用用定理一一之方法法，必定定可以將將此交錯錯線改進進為不交交錯線。定理三：設任意意四點AA,B,C,DD，其座座標值分分別為(a1, a2), (bb1, b2), (cc1, c2), 及(d1, d2)。若座標標值符合合下列情情形之一一時，則則AB與與CD兩兩條線段段必定不不相交。(1) MINN (cc1,d1) MAAX (a1,b1)(2) MINN (aa1,b1) MAAX (c1,d1)(3) MINN (cc2,d2) MAAX (a2,b2)(4) MINN (aa2,b2) MAAX (c2,d2)其中MIIN與MAXX分別表表示取最最小值和和最大值值

18、。定理四：本定理理為完整整之判斷斷兩線段段是否相相交之方方法。圖圖三中設設A,BB,C,D之座座標值同同定理三三。則AAB與CCD之直直線方程程式分別別如下：f1(xx,y) = (xx-a1)(b2-a2)- (y-a2)(b1-a1)= 0f2(xx,y) = (xx-c1)(d2-c2)- (y-c2)(d1-c1) = 0將A,BB點之座座標值分分別代入入f2(x,y)，及及將C,D點之之座標值值分別代代入f1(x,y)。令令分別得得到a,b,c及d值。則則若ab 00且cd 00，則表表示兩線線段相交交，否則則表示兩兩線段不不相交。說明：利利用不等等式之性性質，若若將在直直線兩側側之

19、兩點點分別代代入f(x,y)，必必定一為為正數，一一為負數數，故乘乘積必為為負數。若將在在同一側側之兩點點代入，則則同為正正數或同同為負數數，故乘乘積必為為正數。 AA(a1, a2) CC(c1, c2) D(d1, d2) B(bb1, b2)圖三 兩線交交錯之檢檢查示意意圖肆、自我我組織類類神經網網路演算算法本文提出出之演算算法分成成兩階段段執行，第第一階段段為使用用自我組組織類神神經網路路演算法法求出一一封閉路路徑。第第二階段段則為判判斷此路路徑是否否有任何何兩條線線交錯之之情形；若有交交錯之情情形，則則以定理理二所提提出之方方法將交交錯除去去，並經經比較求求出最長長距離之之路徑。第一

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

21、,33,.,RRDi,jjc = MIIN DDi,jji=1,2,33,.,NN步驟四：新增神神經元。如果有有兩個以以上不同同節點之之最接近近神經元元為同一一個時，則則增加神神經元個個數。其其座標值值與原來來之神經經元相同同，且各各自為某某一節點點之獲勝勝者。5步驟五：刪除神神經元。若有任何何一個神神經元在在三次完完整節點點最近距距離比較較中，都都不曾是是任一節節點之最最近神經經元時，則則刪除此此一神經經元。步驟六：移動節節點i之最接接近神經經元jcc及其鄰鄰近之神神經元，其其中令nn值為鄰鄰近神經經元j與jc之相相鄰個數數，在考考慮環狀狀連結情情形下，n值指定如下：n = MINN ( |

22、jcc-j|,jcc-j+R,j-jc+RR)座標W之之移動公公式如下下所示：wj1 = wwj1 + f (GG, nn) * (xxi1-wj1)wj2 = wwj2 + f (GG, nn) * (xxi2-wj2)其中f (G, n) =expp(-n2/G2)/ (11)步驟七：當每一一神經元元對應之之節點不不再改變變時，輸輸出此神神經元所所對應節節點順序序，即節節點之路路徑，至至步驟八八。否則則，減少少G值，公公式如下下：G = GG * (1-a)，回到到步驟三三。步驟八：計算此此路徑長長度，並並與目前前所獲得得之最長長不相交交長度比比較，若若較小則則到步驟驟十二。若長度度較大則

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

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

25、計算速速度。2.利利用定理理二之方方法將交交錯線段段改進成成為不交交錯線段段，有時時相當耗耗時，故故可以在在符合一一些限制制下才考考慮，如如：長度度超過最最大長度度某一百百分比，或或交錯線線數目少少於三條條。在此此情況下下將被認認為改進進後較有有機會超超過原來來之最長長路徑。伍、實例例模擬及及討論本節中利利用三個個實例來來說明本本演算法法之應用用及結果果：例子一：本例中使使用一224個節節點，構構成兩個個正十二二邊形之之數據，如如圖四所所示。神神經元初初始值以以 xx 表表示。本本例中設設定G初初始值為為5.00，減少少率=0.1，試試驗次數數共2000次。圖四例例一之數數據及神神經元之之隨機

26、初初始路徑徑(o:節點，xx:神經經元)在第一階階段之執執行中，神神經元所所構成之之路徑之之漸進圖圖如圖五五所示。經過2200次次試驗所所得之結結果，將將所得到到之不交交叉路徑徑之長度度，以質質方圖(hisstoggramm)表示示如圖六六所示。而所獲獲得最長長之不交交叉路徑徑，長度度為1553.55，如圖圖七所示示。(a)學習55次後(b)學習115次後後圖五例例一路徑徑之學習習漸進圖圖路徑長度度圖六例例一之質質方圖圖七例例一獲得得最長之之不相交交路徑例子二：本例中使使用一116個節節點，且且近似正正方格之之資料。設定初初始值GG= 55，減少少率= 00.055，及試試驗次數數共10000

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

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

29、位置，以獲得最大之不相交路徑。陸、結論論本文提出出一最大大化不相相交路徑徑問題之之描述及及數學模模型。並並提出一一些相關關之定理理與一解解題之演演算法。由實際際例子中中發現，自自我組織織演算法法除了可可用以求求解最短短路徑問問題外，應應用於求求解最長長路徑問問題亦可可得到不不錯之結結果。在求解此此最佳化化路徑之之問題方方面，使使用基因因法則、模擬退退火法或或Hoppfieeld類類神經網網路等方方法相信信亦可以以有相當當不錯之之結果。期望有有更多人人針對此此一問題題提出不不同之演演算法來來求解此此一具挑挑戰性之之問題。參考文獻獻1Kohhoneen, Teuuvo, SSelff-orrgan

30、nizaatioon aand asssociiatiive memmoryy, SSpriingeer, 19888.2Janng, J. S., Neeuroo-Fuuzzyy annd SSoftt Coompuutinng, 全華圖圖書，119977。3林昇甫甫、洪成成安，神神經網路路入門與與圖樣辨辨識，全全華書局局，822年9月月。4Lipppmaan,RRichhardd P. An inttrodducttionn too coompuutinng wwithh neeuraal nnetss, IEEEE AASSPP Maag. pp.4-222, Apprill 19987

31、.5Anggeniiol, B., eet aal. ,SSelff-orrganniziing feaaturre mmapss annd tthe traavelllinng ssaleesmaan pprobblemm, Neuurall Neetwoorkss, VVol. 1, ppp.2889-2293, 19988.6Kittaorri, K.; Muurakkoshhi, H.; Fuunakkuboo, NN,A nnew appproaach to sollve thee trraveelinng ssaleesmaan pprobblemm byy ussingg thh

32、e iimprroveed KKohoonenns sellf-oorgaanizzingg feeatuure mapp, Prooc. off thhe IIEEEE IEECONN 211st Intternnatiionaal CConffereencee , Voll. 2 , ppp. 13884-113888,19995.7Kimm, SS.-JJ.; Kimm, JJ.-HH.; Chooi, H.-M.,Ann effficciennt aalgooritthm forr trraveelinng ssaleesmaan pprobblemms bbaseed oon sse

33、lff-orrganniziing feaaturre mmapss, Seccondd IEEEE Intternnatiionaal CConffereencee onn Fuuzzyy Syysteems, Vol.2, pp. 10085-10990, 19993.8Mattsuyyamaa,Y.,Coompeetittivee seelf-orgganiizattionn annd ccombbinaatorriall opptimmizaatioon: apppliccatiionss too trraveelinng ssaleesmaan pprobblemm, IJCCNN

34、Intternnatiionaal JJoinnt CConffereencee onn Neeuraal NNetwworkks, Voll. 33, ppp. 8199-8224, 19990.9Cocchraane, E.M.; Coochrranee, JJ.C.,Exxploorinng ccomppetiitioon aand co-opeerattionn foor ssolvvingg thhe EEucllideean traavelllinng ssaleesmaan pprobblemm byy ussingg seelf-orgganiizinng mmap, NNintth IInteernaatioonall Coonfeerennce on Arttifiiciaal NNeurral Nettworrks, Vool. 1, pp. 1880 -1855, 119999.