論文題目基于泛化競爭和局部滲透機制的自組織網(wǎng)TSP問題求解方

1、論文題目：基于泛化競爭和局部滲透機制的自組織網(wǎng)TSP問題求解方法論文作者：張軍英，周斌詳細工作單位：西安電子科技大學計算機學院城市及郵政編碼：陜西 西安 710071摘 要 旅行商問題(TSP)是組合優(yōu)化中最典型的NP完全問題之一，具有很強的工程背景和應用價值。本文在分析了標準SOM(self-organizing map)算法在求解TSP問題的不足和在尋求總體最優(yōu)解上的潛力的基礎上，引入泛化競爭和局部滲透這兩個新的學習機制，提出了一種新的SOM算法，叫滲透的SOM(Infiltrative SOM, ISOM)。通過泛化競爭和局部滲透策略的協(xié)同作用：總體競爭和局部滲透并舉、先傾向總體競爭后傾

2、向局部滲透、在總體競爭基礎上的局部滲透，實現(xiàn)了在總體路徑尋優(yōu)指導下的局部路徑優(yōu)化，從而使所得路徑盡可能接近最優(yōu)解。通過對TSPLIB中14組TSP實例的測試結果及與如KNIES、SETSP、Budinich和ESOM等類SOM算法的比較，表明該算法既簡單解的質量又得到了很大提高，同時還保持了解的良好的穩(wěn)健特性。關鍵詞： TSP問題；組合優(yōu)化；自組織映射；全局優(yōu)化；總體優(yōu)化；局部優(yōu)化論文題目：基于泛化競爭和局部滲透機制的自組織網(wǎng)TSP問題求解方法論文作者：張軍英，周斌論文相關的背景：旅行商問題(TSP)是組合優(yōu)化中最典型的NP難問題，特別對于大規(guī)模TSP問題的求解，無論是理論上還是應用上，都有極

3、其重要的意義。本項研究，既看到了該問題研究的難度，同時也注意到了由于其困難使對這一問題的解決在理論上和方法上的巨大潛力。我們注意到：(1)要獲得TSP問題全局最優(yōu)解是及其困難的；(2)用標準自組織網(wǎng)絡(SOM)求解TSP問題可以獲得對問題的總體最優(yōu)解，因此，我們在標準SOM的基礎上創(chuàng)造性地引入了泛化競爭機制和局部滲透機制，通過這兩個機制的協(xié)調和競爭，即總體競爭和局部滲透并舉、先傾向總體競爭后傾向局部滲透、在總體競爭基礎上的局部滲透，實現(xiàn)了在基于標準SOM學習的總體路徑尋優(yōu)指導下的局部路徑優(yōu)化，從而使得所得的路徑盡可能接近最優(yōu)解。通過對TSPLIB中14組TSP實例（其中有的實例城市數(shù)達1600

4、多個）的測試實驗結果表明，本文所提出的算法簡單，在解的質量上已超越了如KNIES、SETSP、Budinich和ESOM等類SOM算法，同時算法還保持了較低的計算復雜度和解的良好的穩(wěn)健特性。該項研究受到我們負責的國家自然科學基金項目的支持。本論文的內容全部是作者原創(chuàng)的科研成果；署名無爭議；引用他人成果已注明出處；未公開發(fā)表過。特此聲明。基于泛化競爭和局部滲透機制的自組織網(wǎng)TSP問題求解方法*該項研究受到國家自然科學基金項目（編號：60574039）和中意雙邊科技合作項目支持（編號：20062517）張軍英，周斌(西安電子科技大學計算機學院，西安， 710071)摘 要 旅行商問題(TSP)是組

5、合優(yōu)化中最典型的NP完全問題之一，具有很強的工程背景和應用價值。本文在分析了標準SOM(self-organizing map)算法在求解TSP問題的不足和在尋求總體最優(yōu)解上的潛力的基礎上，引入泛化競爭和局部滲透這兩個新的學習機制，提出了一種新的SOM算法，叫滲透的SOM(Infiltrative SOM, ISOM)。通過泛化競爭和局部滲透策略的協(xié)同作用：總體競爭和局部滲透并舉、先傾向總體競爭后傾向局部滲透、在總體競爭基礎上的局部滲透，實現(xiàn)了在總體路徑尋優(yōu)指導下的局部路徑優(yōu)化，從而使所得路徑盡可能接近最優(yōu)解。通過對TSPLIB中14組TSP實例的測試結果及與如KNIES、SETSP、Budi

6、nich和ESOM等類SOM算法的比較，表明該算法既簡單解的質量又得到了很大提高，同時還保持了解的良好的穩(wěn)健特性。關鍵詞： TSP問題；組合優(yōu)化；自組織映射; 全局優(yōu)化；總體優(yōu)化；局部優(yōu)化中圖法分類號：TP18 文獻表示碼：A 文章編號：1 引 言作為在VLSI芯片設計1、網(wǎng)絡路由2,3、車輛選路4等領域有著廣泛應用的旅行商問題(Traveling Salesman Problem, TSP)5，是NP完全問題中的最為典型的問題6。解決它對于解決所有NP完全問題具有重要的理論意義7，所以長期以來一直吸引著眾多領域的研究人員對其進行研究和算法改進。TSP問題要求找到經(jīng)過每個城市、每個城市只經(jīng)過一

7、次、且路徑最短的Hamilton回路。對于一個城市的TSP問題，由于該問題一共存在條可能的路徑，用窮舉的辦法顯然是不現(xiàn)實的。譬如，用窮舉搜索法對的TSP問題進行求解，即使采用每秒計算1億次的超級計算機也需要運行年8。可喜的是，一些智能優(yōu)化算法可用于獲取TSP問題的次優(yōu)解，如模擬退火9、遺傳算法10、禁忌搜索算法11、蟻群算法12和神經(jīng)網(wǎng)路方法13,14等。本文則研究基于SOM神經(jīng)網(wǎng)絡的TSP問題求解方法。1985年，Hopfield 和 Tank13首次將神經(jīng)網(wǎng)絡方法應用于TSP問題的求解，從而開創(chuàng)了運用神經(jīng)網(wǎng)絡方法求解TSP問題的先河。目前，求解TSP問題的神經(jīng)網(wǎng)絡方法可分為Hopfield

8、類算法13和SOM類算法14,15-19。盡管Hopfield類算法能解決小規(guī)模的和某些中等規(guī)模的TSP問題20，但對普通的中等規(guī)模問題或者大規(guī)模的TSP問題，Hopfield類算法仍不能勝任21。SOM類算法則不同，它能以較小的計算代價解決大規(guī)模的TSP問題19。SOM類算法相對模擬退火、蟻群算法等算法而言，其計算復雜度大幅降低而解的質量僅有所下降14，因此，以提高TSP問題解的質量為目標對SOM類算法進行改進已經(jīng)和正在吸引大量的研究工作15-19。本文在傳統(tǒng)SOM14算法的基礎上，通過引入泛化競爭和局部滲透這兩個新的策略，提出了一種新的SOM算法，稱為滲透的SOM(Infiltrative

9、 SOM, ISOM)算法。該算法以輸入城市為中心，強化距其遠的神經(jīng)元之間的總體競爭作用，強化距其近的神經(jīng)元向輸入城市的局部滲透作用，并以學習初期更強調總體競爭、學習末期更強調局部滲透、學習過程中總體競爭和局部滲透相結合的學習機制，實現(xiàn)了一種先總體后局部的優(yōu)化策略。同時，該算法結合傳統(tǒng)SOM學習策略總體路徑尋優(yōu)的特點，以及新策略在局部路徑優(yōu)化上的優(yōu)勢，實現(xiàn)了總體優(yōu)化與局部優(yōu)化的融合，獲得了高質量的全局優(yōu)解。針對來自TSPLIB3的14組TSP實例的實驗結果顯示，ISOM算法得到了對應于這14組數(shù)據(jù)的11個最接近最優(yōu)的解，其中對應實例lin105的結果就是最優(yōu)解，并且ISOM算法以最小的平均偏離

10、最優(yōu)率(偏離最優(yōu)路徑長度的百分率)3.4558%勝過其余典型的類SOM算法，如KNIES算法15,16、SETSP算法17、Budinich算法18以及ESOM算法19，表明了所提算法的有效性。2 基于標準SOM求解TSP的基本原理和存在問題2.1 SOM求解TSP問題的基本原理圖1 一維環(huán)形SOM的結構SOM作為一種從輸入空間到輸出空間的拓撲保序映射22，已被廣泛應用于高維數(shù)據(jù)的聚類分析、降維和在低維空間中的可視化表示，其網(wǎng)絡結構通常選為線性結構、柵格結構、立方體結構等。根據(jù)TSP問題要求找出最短Hamilton回路的要求，Kohonen14提出的運用SOM求解TSP問題的基本思想是，設置網(wǎng)

11、絡結構為一維環(huán)形結構（如圖1所示），將輸入空間中的城市位置作為激勵學習網(wǎng)絡，通過由SOM所實現(xiàn)的從城市位置到網(wǎng)絡輸出的拓撲保序映射，即：在輸入空間中相鄰的城市其所激活的網(wǎng)絡上的神經(jīng)元也相鄰，獲得TSP問題的解。SOM通過競爭、合作、自適應機制學習輸入空間到神經(jīng)元的拓撲保序映射，其中，基于歐氏距離最小的競爭機制表現(xiàn)為在競爭中獲勝的神經(jīng)元為 (1)其中，表示神經(jīng)元的總數(shù)。建立在網(wǎng)絡結構基礎上的合作機制表現(xiàn)在：獲勝神經(jīng)元及其鄰域神經(jīng)元的修正強度（即鄰域函數(shù)為高斯函數(shù)）為 (2)而自適應學習機制表現(xiàn)在神經(jīng)元依其修正強度以如下公式進行的修正上： (3)其中為n時刻神經(jīng)元j與輸入結點的連接權矢量，為神經(jīng)元

12、j與獲勝神經(jīng)元i之間在映射空間中的距離，為學習率。實際上，在用SOM求解TSP問題的過程中，每輸入一個城市，通過競爭使與其最近的神經(jīng)元獲勝，該神經(jīng)元及其鄰域神經(jīng)元依據(jù)修正強度以移位量移向該輸入城市，這一過程不斷進行，最終通過合作半徑和學習率隨迭代次數(shù)的不斷減?。?(4) (5)實現(xiàn)學習過程的最終收斂。顯然，用一維環(huán)形SOM進行TSP問題的求解有如下的優(yōu)越性：一維環(huán)形結構的網(wǎng)絡結構與TSP問題要求找最短Hamilton路徑在結構上有很好的匹配；一維環(huán)形結構的SOM易于構建，如下式 (6)其中表示鄰域函數(shù)中興奮神經(jīng)元與獲勝神經(jīng)元在輸出空間中的距離。與之相反，其它一些映射方法，如同樣用于數(shù)據(jù)聚類的G

13、TM23，就很難做出類似的結構。2.2 直接用標準SOM算法求解TSP問題的主要問題和潛力盡管一維環(huán)形SOM網(wǎng)絡在求解TSP問題上有其相當?shù)暮侠硇?，但本文認為標準SOM算法所獲得的實際上是TSP問題的總體最優(yōu)解而非全局最優(yōu)解。眾所周知，SOM具有很好的拓撲保序特性，即輸入空間中樣本的距離和鄰近特性在輸出空間中將得到盡可能的保留。這一性質當用兩維柵格作為輸出空間時，常常用于數(shù)據(jù)的聚類和可視化分析。然而，仿真實驗表明，網(wǎng)絡對低密度數(shù)據(jù)區(qū)表達有過，而對高密度數(shù)據(jù)區(qū)表達不足22，這也就是為什么在數(shù)據(jù)聚類分析過程中通常用比數(shù)據(jù)聚類數(shù)目多得多的神經(jīng)元所構成的SOM實現(xiàn)對數(shù)據(jù)的聚類。 (a) (b)圖2 (

14、a) lin105的城市位置和最優(yōu)路徑 (b) lin105用105個神經(jīng)元的環(huán)形SOM求解所獲得的收斂結果用環(huán)形SOM進行TSP問題求解也存在同樣的問題。這里用105個神經(jīng)元的環(huán)形SOM求解lin105 (示于圖2(a)中)所獲得的收斂結果示于圖2(b)中。在圖2中，三角表示TSP問題中的城市位置，圓點表示SOM收斂后的神經(jīng)元位置。從圖2(b)中可以看到，(1) SOM收斂到了一組虛擬城市(即神經(jīng)元，用圓點表示)上，這些虛擬城市的位置并不是真實城市(即輸入城市，用三角形表示)的位置；(2) SOM所給出的收斂路徑是這組虛擬城市TSP問題的最優(yōu)解；(3) 這組虛擬城市與真實城市之間似乎難于建立

15、一個一一對應的關系，因此從這組虛擬城市TSP問題的最優(yōu)解中無法獲得真實城市的TSP問題的最優(yōu)解。由此可見，用標準SOM算法所獲得的是虛擬城市TSP問題的最優(yōu)解，該最優(yōu)解實際上僅是真實城市TSP問題解的一個輪廓，我們稱其為原TSP問題的總體最優(yōu)解。從這一點上看，SOM求解TSP問題是非常有特點的：所獲得的解是虛擬城市TSP問題的全局最優(yōu)解，也稱是真實城市TSP問題的總體最優(yōu)解。注意到我們的目標是尋找真實城市TSP問題的全局最優(yōu)解，而非其總體最優(yōu)解。本文試圖將總體尋優(yōu)和局部尋優(yōu)有機結合起來，即在很好利用SOM進行總體尋優(yōu)的潛力基礎上，通過嵌入局部尋優(yōu)的機制，從而獲得真實城市TSP問題的全局最優(yōu)解，

16、這就是本文的目的所在。3 ISOM算法3.1 泛化競爭機制和局部滲透機制實際上，用標準SOM算法求解TSP問題的過程為：隨機初始化神經(jīng)元（虛擬城市）的位置，并由真實城市不斷激勵得到獲勝神經(jīng)元，神經(jīng)元依據(jù)學習算法不斷向真實城市移位，最終收斂到神經(jīng)元的位置不再移動為止。然而這樣的學習過程僅僅能夠得到原TSP問題的總體最優(yōu)解，而非全局最優(yōu)解。為盡可能獲得真實城市TSP問題的最優(yōu)解，本節(jié)在標準SOM學習算法的基礎上，提出了兩個新的學習機制：泛化競爭和局部滲透，并將其融入標準SOM的學習算法中。從TSP問題的求解要求看，(1)當輸入城市與獲勝神經(jīng)元之間的距離較大時（表明盡管該神經(jīng)元獲勝，但仍不一定將該城

17、市映射到該神經(jīng)元上），應使獲勝神經(jīng)元及其鄰域神經(jīng)元向輸入城市的位移量減少，從而允許各個神經(jīng)元更加公平地參與競爭，我們稱這一機制為泛化競爭機制；(2) 當輸入城市與獲勝神經(jīng)元之間的距離較小時（表明應該將城市映射到該神經(jīng)元上），應使獲勝神經(jīng)元及其鄰域神經(jīng)元向輸入城市的位移量增大，從而弱化其他神經(jīng)元對當前輸入城市的競爭而強化獲勝神經(jīng)元及其鄰域神經(jīng)元對當前輸入城市的競爭，我們稱這一機制為局部滲透機制。以上位移量的減少或增大均相對標準的SOM算法而言。泛化競爭是使各個神經(jīng)元處于更為公平競爭的機制，而局部滲透則是使獲勝神經(jīng)元及其鄰域神經(jīng)元具有更為優(yōu)越的局部競爭能力的機制，前者強化總體尋優(yōu)，后者強化局部尋優(yōu)

18、。3.2 泛化競爭和局部滲透的實現(xiàn)為實現(xiàn)泛化競爭和局部滲透機制，我們引入滲透半徑作為輸入城市與獲勝神經(jīng)元之間距離大小的判斷門限，一旦它們之間的距離大于，則采用泛化競爭機制；反之則采用局部滲透機制。為此，將神經(jīng)元向輸入城市的移位由原來的調整為，即將式(3)調整為如下的公式： (7)其中，用于神經(jīng)元權值移位量的調節(jié)，并按式(8)取值： (8) (a) (b)圖3 TSP問題求解的泛化競爭機制和局部滲透機制(a) 泛化競爭機制；(b) 局部滲透機制其中為輸入空間中輸入城市到獲勝神經(jīng)元的歐氏距離。顯然，這樣的設置將使時所乘的系數(shù)Z的數(shù)值較小，從而保證獲勝神經(jīng)元及其鄰域神經(jīng)元以較小的移位量移向輸入城市，

19、達到泛化競爭的目的；而當時所乘的系數(shù)Z的數(shù)值較大，從而保證獲勝神經(jīng)元及其鄰域神經(jīng)元以較大的位移量移向輸入城市，達到局部滲透的目的。我們將離輸入城市小于的區(qū)域稱為輸入城市的滲透區(qū)域。注意到當時，獲勝神經(jīng)元i及其鄰域神經(jīng)元僅以較小的移位量移向輸入城市，如圖3(a)所示，從而不過早建立獲勝神經(jīng)元與輸入城市之間的一一對應關系，而是允許其它神經(jīng)元參與進一步的競爭；當時，獲勝神經(jīng)元i及其鄰域神經(jīng)元將以較大的移位量移向輸入城市，如圖3(b)所示，這樣的位移極有可能造成獲勝神經(jīng)元及其鄰域神經(jīng)元向輸入城市以較大移位量移位（滲透）的現(xiàn)象：在獲勝神經(jīng)元i的鄰居神經(jīng)元i+1被拽向輸入城市的同時，也以較大步伐靠近了輸入

20、城市的鄰近城市；與此同時，由于城市與輸入城市離得很近，神經(jīng)元也被拽入。在接下來針對城市的競爭中，神經(jīng)元因其在城市的內從而將極有可能獲勝并與城市建立一一對應的映射關系。由此，的路徑很可能被選上。城市的情況也類似，城市到城市的路徑很可能被選擇而最終形成的路徑。以此類推，兩兩離得很近的城市將不斷地被映射成為路徑上的兩個相鄰神經(jīng)元，從而形成一條神經(jīng)元分布緊湊的路徑。在這個過程中，一連串神經(jīng)元是以遞進的方式逐步實現(xiàn)與一條子路徑的匹配的，“滲透”由此得名。3.3 總體尋優(yōu)基礎上的局部尋優(yōu)TSP問題與最短路問題不同，最短路問題的全局最優(yōu)路徑中每一局部路徑都是局部最優(yōu)的，但局部最優(yōu)路徑卻不保證解的全局最優(yōu)性。

21、TSP問題則復雜的多，其全局最優(yōu)路徑不能保證其局部路徑的局部最優(yōu)性，其局部最優(yōu)路徑也不能保證解的全局最優(yōu)性。TSP問題的這種復雜性，使得它成為較之最短路問題困難得多的問題：TSP的計算復雜度為，最短路問題的計算復雜度不超過，這里N為城市數(shù)。為此，我們提出對TSP問題的如下策略：先總體優(yōu)化后局部優(yōu)化、在總體優(yōu)化的基礎上進行局部優(yōu)化、使總體優(yōu)化與局部優(yōu)化有機結合以尋求全局最優(yōu)解的學習機制。為實現(xiàn)這一學習策略，顯然滲透區(qū)域應是隨時間由小到大逐步擴張的。為此，這里設 (9)其中和為常量，本文的實驗取，為一距離常量，其值選為神經(jīng)元初始化矩形框的對角線長度。這樣，我們求解TSP問題的滲透SOM算法的算法步

22、驟如下：Step 1: 確定神經(jīng)元數(shù)目(一般為二到三倍城市數(shù))，將神經(jīng)元有序分布在城市外圍的矩形框上；Step 2: 從輸入空間隨機取樣本作為輸入城市；Step 3: 依據(jù)式(1)確定時刻的獲勝神經(jīng)元；Step 4: 通過式(7)更新神經(jīng)元權值，其中和由公式(8)和(9)計算得到；Step 5: n+1àn，繼續(xù)Step 24直到鄰域函數(shù)寬度(其初值取)；Step 6:由已與城市建立一一映射關系的神經(jīng)元的順序確定訪問路徑。若有城市未被一一映射，回到Step1并增大神經(jīng)元數(shù)量。 (a) (b) 圖4 (a) 關于的曲線圖 (b) 關于的曲線圖圖4(a)示出了與之間的關系，可以看到大的對

23、應小的位移量，從而強化總體競爭，小的對應大的位移量，從而強化神經(jīng)元附近的局部滲透；圖4(b)示出了與之間的關系曲線，可以看到滲透區(qū)域的半徑是隨算法的運行不斷變化的：初始時半徑小，從而強化總體競爭，隨著算法的運行滲透半徑逐漸增加，從而強化局部滲透。我們就是在SOM中引入這樣的機制實現(xiàn)總體競爭和局部滲透并舉、先傾向總體競爭后傾向局部滲透、在總體競爭基礎上的局部滲透，從而實現(xiàn)在總體優(yōu)化的基礎上進行局部優(yōu)化、使總體優(yōu)化與局部優(yōu)化有機結合以尋求全局最優(yōu)解的學習策略的。相對標準SOM算法和目前已有的基于SOM的TSP問題求解方法14,15-19而言，上述算法的計算復雜度仍保持為二次。本文所提出的算法采用了

24、文獻17中已被證實有效的神經(jīng)元初始化方式：將神經(jīng)元有序地分布在城市外圍的矩形框上(如圖5(a)所示)。4 實驗與結果本文針對TSPLIB3中的TSP實例進行了大量的求解實驗，并與TSPLIB中公布的路徑長度及文獻16,17,29中所公布的其他方法所獲得的路徑長度進行了比較，以“偏離最優(yōu)率”（即所得路徑的長度超出TSPLIB公布的最優(yōu)路經(jīng)長度的百分率）作為評價解的質量的指標，越小表明解的質量越高。注意到TSPLIB公布的路徑長度由每條邊四舍五入取整后累加得到24，因而所有的路徑長度都是整數(shù)。然而很多文獻并沒有對任何長度值取整，為便于和同類方法作比較，本文在實驗中也不做取整處理。本文針對50到16

25、55個城市的14組TSP實例進行的實驗的結果及與其他方法的比較示于表1中，其中ISOM_20欄對應ISOM算法20次運行所得的平均路徑長度的值，ISOM欄為這些運行所獲得的最好結果的值，其它欄對應各個方法所得最好結果的值。表1中質量最好即最小的數(shù)值已經(jīng)用黑體標出。從表1可知，14組TSP實例中有11組可通過ISOM得到更優(yōu)的解，其中l(wèi)in105的最好解與TSPLIB公布的最優(yōu)路徑完全一致，如圖2(a)所示；對于其余3組數(shù)據(jù)，ISOM也得到了比較好的結果。因而，ISOM最終能以3.4558%這個最小的平均偏離最優(yōu)率展示其可行性和有效性。同時，ISOM運行20次的平均值也不差，從而可以看出該方法還

26、具有一定的穩(wěn)健性，即相對其他算法而言，本文算法每次運行都得到相對較好的路徑。我們對1002個城市、1173個城市和1165個城市的實驗結果已列于表中，然而，KG、KL、KD和SETSP方法，由于問題規(guī)模過大，文獻中已沒能給出他們方法對這個城市規(guī)模的實驗結果，既是與給出結果的Budinich方法和ESOM方法，用我們方法得到結果的性能也優(yōu)越很多，表明了我們方法的有效性。表1 7種方法求解14組TSP實例的結果實例名稱城市規(guī)模偏離最優(yōu)路徑的百分率（%）KGKLKDSETSPBudinichESOMISOMISOM_20eil51512.862.863.5002.56043.8

27、132st70702.331.513.671.601.702.091.32912.1104eil76765.484.986.494.235.323.893.45404.6264rd1001002.622.094.892.603.161.961.40963.4011lin1051051.291.982.181.301.710.250.02780.2420pr1071070.420.7310.830.411.321.480.22120.8731pr1361365.154.531.934.405.204.313.38203.6710pr1521521.290.940.891.

28、23642.0846rat19519511.9212.248.3511.1911.487.135.55757.8338kroA2002006.575.725.612.74793.2617pcb44244210.4511.078.0010.168.437.436.53438.195511組實例的平均偏離率4.58004.42555.34003.85454.50823.13092.58733.6466pr100210027.607.088.755.933.48095.0090pcb1173117311.389.877.53038.5804d1655165515.1811.3

29、58.951910.045214組實例的平均偏離率6.06434.39933.45584.5534注：方法KL (KNIES_TSP_Local)、KG (KNIES_TSP_Global)、KD (KNIES_DECOMPOSE)的結果引自文獻16；SETSP (SOM efficiently applied to the TSP)的結果引自文獻17；Budinich (Budinichs SOM)和ESOM (Expending SOM)的結果引自文獻19。粗斜體數(shù)字說明該數(shù)值在同行數(shù)據(jù)中最小。 (a) (b) (c) (d) (e) (f)圖5 eil51的尋優(yōu)過程(a為初始化，b,c,

30、d為尋優(yōu)的中間過程，e為的尋優(yōu)結果，f為TSPLIB公布的最優(yōu)解)圖5給出了ISOM算法對eil51進行TSP問題的求解過程，由此可以看到本文的滲透機制的意義：基本上找出了最優(yōu)路徑上的凹槽路徑，從而最終所獲得的路徑是比較優(yōu)的。圖6 ISOM運行時間關于城市數(shù)的折線圖圖6給出了本文算法運行時間與城市數(shù)量的關系。從該圖可以看出，運行時間基本上是按照城市數(shù)量的二次關系遞增的，由此ISOM算法保持了SOM算法具有較低計算復雜度的優(yōu)良特點。5 結論本文提出了一種改進的SOM算法，該算法通過在標準SOM學習的基礎上引入新的學習機制：泛化競爭機制和局部滲透機制，實現(xiàn)了路徑的總體優(yōu)化與局部優(yōu)化的融合，從而能夠

31、找到更加接近全局最優(yōu)的解。實驗表明，盡管ISOM算法很簡單，在求解精度上它已經(jīng)超越了如KNIES、SETSP、Budinich和ESOM這樣典型的SOM算法，同時算法還保持了較低的計算復雜度，且解還具有良好的穩(wěn)健性。參考文獻：1 Dorigo, M. and Gambardella, L. M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1997, 1(1):53-66.2 Ascheuer, N., Jü

32、;nger, M. and Reinelt G. A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Computational Optimization and Applications. 2000, 17(1):61 84.3 Reinelt, G. TSPLIBA traveling salesman problem library. ORSA J. Comput. 1991, vol. 3, pp. 376-384.4 Laporte,

33、 G. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 1992, 59:345-358.5 Potvin, J.-Y. The traveling salesman problem: a neural network perspective. ORSA J. Comput. 1993, 5:328-348.6 Garey M. R., Johnson D. S. Computers and Intrac

34、tability: A guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman, 1979.7 Jiao Li-Cheng. Neural Computation. Xian: Xidian University Press, 1996, 195-196 (in Chinese)8 Wang Wei. Artficial Neural Network: theory and application. Beijing: Beijing University of Aeronautic and Astronautic

35、 Science and Technology Press, 1995(in Chinese)9 Kirkpatrick, S. G., Gelatt, Jr. C. D., and M. P. Vecchi. Optimization by simulated annealing. Science. 1983, 220:671 680.10 Goldberg, D. E. Genetic algorithms in search, optimization and machine learning. MA: Addisom-Wesley, 1989.11 Knox, J. Tabu sear

36、ch performance on the symmetric traveling salesman problem. Comput. Oper. Res. 1994, 21(8): 867-876.12 Baraglia, R. Hidalgo, JI. Perego, R. A Hybrid Heuristic for the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation. 2001,5 (6) :613-622.13 Hopfield, J. J. and Tank, D. W. Neu

37、ral computation of decisions in optimization problems. Biological Cybernetics, 1985, 52: 141-152.14 Kohonen, T. Self-organizing maps. New York: Springer-Verlag, 1997.15 Aras, N., Oommen B. J., and Altinel, ?. K. Kohonen network incorporating explicit statistics and its application to the traveling s

38、alesman problem. Neural Networks. 1999, 12 (9): 1273-1284.16 Aras, N., Altinel, ?. K., and Oommen, B. J. A. Kohonen-like decomposition method for the Euclidean traveling salesman problemKNIES_DECOMPOSE. IEEE Trans. on Neural Networks. 2003, 14(1):869-890.17 Vieira, F. C., and Neto, A. D. D. An effic

39、ient approach to the traveling salesman problem using self-organizing maps. International Journal of Neural Systems. 2003, 13(2): 59-66.18 Budinich, M. A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing. Neural computation. 1996, 8:416-42

40、4.19 Leung, K. S., Jin, H. D., and Xu, Z. B. An expanding self-organizing neural network for the traveling salesman problem. Neurocomputing, 2004, (62).?20 Abe, S. Convergence acceleration of the Hopfield neural network by optimization integration step sizes. IEEE Trans. Syst., Man, Cybern. B. 1996,

41、 26: 194-201.21 Smith, K. A. An argument for abandoning the traveling salesman problem as a neural network benchmark. IEEE Trans. on Neural Networks. 1996, 7(6): 1542 1544.22 Haykin, S. Neural networks: a comprehensive foundation. 2nd Edition. New Jersey: Prentice Hall, 1999, pp.444-460.23 Christoph

42、er M. Bishop, Markus Svensén and Christopher K. I. Williams. GTM: The generative topographic mapping. Neural Computation. 1998, 10(1): 215-234 24 Reinelt, G. TSPLIB95. Available from: rmatik.uni-heidelberg.de/groups/comopt/software/TSPLIB95/DOC.PS.作 者 簡 介張軍英，女，1961年11月生，博士、教授、博導，西

43、安電子科技大學學科帶頭人，IEEE會員, 中國電子學會高級會員。西安理工大學自動控制專業(yè)學士（1982年），西安電子科技大學計算機應用專業(yè)碩士（1985年），西安電子科技大學信號與信息處理專業(yè)博士（1998年）。受國家留學基金委選派在美國作訪問學者一年(2001-2002)，在香港中文大學做訪問學者(2004)，美國Virginia Tech大學訪問教授半年（2007）。目前主要從事智能計算、計算生物信息學、DNA微陣列數(shù)據(jù)分析、人工神經(jīng)網(wǎng)絡、模式識別、遺傳算法、智能信息處理和圖像處理等方面的研究工作，已發(fā)表學術論文60余篇。通信地址：710071 陜西 西安 西安電子科技大學 161信箱；電

44、話88201531；Email: jyzhang。周斌，男，1982年生，碩士。西安電子科技大學 計算機應用專業(yè)學士（2005），西安電子科技大學計算機應用專業(yè)碩士（2007）。目前主要從事組合優(yōu)化問題求解、人工神經(jīng)網(wǎng)絡等方面的研究。電話 Email: notzhou。Self Organizing Map with Generalized and Localized Parallel Competitions for the TSPJunying Zhang, Bin Zhou(School of Computer Science and

45、Engineering, Xidian University, Xian 710071, China)Abstract As one of the most typical NP-complete combinational optimization problems, TSP (Traveling Salesman Problem), which has a diversity of applications in real world, has attracted extensive research interest. Recently, Self-Organizing Map (SOM

46、) based approaches to this problem has been paid great attention for its simplicity and novelty. By analyzing drawbacks of standard SOM algorithm for solving TSP problem, it was found that the standard SOM has a great potential for finding overall optimal solution rather than globally optimal soluti

47、on for a TSP problem. Based on this, the paper proposes a new SOM algorithm for solving TSP problem, the infiltrative SOM (ISOM), by introducing two new learning schemes, competition generalization and local infiltration. By the collaboration of the two learning schemes in that both the schemes work

48、 together in the whole learning process and initial learning focuses more on overall optimization, which is conducted by the competition generalization, while the afterward learning focuses more on local optimization, which is conducted by the local infiltration, the near-optimal solution is much mo

49、re easy to be found. Experiments on public TSPLIB data show that not only the quality of the solutions is higher, but also the solutions are more robust, by the proposed method compared with those by several typical SOM-based methods such as the KNIES algorithms, the SETSP, the SOM developed by Budi

50、nich, and the ESOM. Keywords: traveling salesman problem; combinational optimization; self-organizing map; global optimization; overall optimization; local optimizationBackground of the paperTitle: Self Organizing Map with Generalized and Localized Parallel Competitions for the TSP Authors: Junying

51、Zhang, Bin ZhouTraveling salesman problem (TSP) is one of the most typical NP-hard combinatorial optimization problems, which has various applications in diversity of fields. Developing algorithms for solving such TSPs, especially large scale TSPs, is of a great significance in both theory and appli

52、cations. From the notice that solving this problem is of great difficulty, brings great challenges, and posseses much potential in theory, methods and algorithms, it is seen that (a) it is extremely difficult and even impossible for developing an algorithm for finding the globally optimal solution of a large scale TSP problem in an acceptable time and space; (b) the overall opti