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

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

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

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

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

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

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

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

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

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

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

11、絡(luò)結(jié)構(gòu)為一維環(huán)形結(jié)構(gòu)（如圖1所示），將輸入空間中的城市位置作為激勵(lì)學(xué)習(xí)網(wǎng)絡(luò)，通過(guò)由SOM所實(shí)現(xiàn)的從城市位置到網(wǎng)絡(luò)輸出的拓?fù)浔Ｐ蛴成?，即：在輸入空間中相鄰的城市其所激活的網(wǎng)絡(luò)上的神經(jīng)元也相鄰，獲得TSP問(wèn)題的解。SOM通過(guò)競(jìng)爭(zhēng)、合作、自適應(yīng)機(jī)制學(xué)習(xí)輸入空間到神經(jīng)元的拓?fù)浔Ｐ蛴成洌渲?，基于歐氏距離最小的競(jìng)爭(zhēng)機(jī)制表現(xiàn)為在競(jìng)爭(zhēng)中獲勝的神經(jīng)元為 (1)其中，表示神經(jīng)元的總數(shù)。建立在網(wǎng)絡(luò)結(jié)構(gòu)基礎(chǔ)上的合作機(jī)制表現(xiàn)在：獲勝神經(jīng)元及其鄰域神經(jīng)元的修正強(qiáng)度（即鄰域函數(shù)為高斯函數(shù)）為 (2)而自適應(yīng)學(xué)習(xí)機(jī)制表現(xiàn)在神經(jīng)元依其修正強(qiáng)度以如下公式進(jìn)行的修正上： (3)其中為n時(shí)刻神經(jīng)元j與輸入結(jié)點(diǎn)的連接權(quán)矢量，為神經(jīng)元

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

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

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

15、一個(gè)一一對(duì)應(yīng)的關(guān)系，因此從這組虛擬城市TSP問(wèn)題的最優(yōu)解中無(wú)法獲得真實(shí)城市的TSP問(wèn)題的最優(yōu)解。由此可見(jiàn)，用標(biāo)準(zhǔn)SOM算法所獲得的是虛擬城市TSP問(wèn)題的最優(yōu)解，該最優(yōu)解實(shí)際上僅是真實(shí)城市TSP問(wèn)題解的一個(gè)輪廓，我們稱(chēng)其為原TSP問(wèn)題的總體最優(yōu)解。從這一點(diǎn)上看，SOM求解TSP問(wèn)題是非常有特點(diǎn)的：所獲得的解是虛擬城市TSP問(wèn)題的全局最優(yōu)解，也稱(chēng)是真實(shí)城市TSP問(wèn)題的總體最優(yōu)解。注意到我們的目標(biāo)是尋找真實(shí)城市TSP問(wèn)題的全局最優(yōu)解，而非其總體最優(yōu)解。本文試圖將總體尋優(yōu)和局部尋優(yōu)有機(jī)結(jié)合起來(lái)，即在很好利用SOM進(jìn)行總體尋優(yōu)的潛力基礎(chǔ)上，通過(guò)嵌入局部尋優(yōu)的機(jī)制，從而獲得真實(shí)城市TSP問(wèn)題的全局最優(yōu)解，

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

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

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

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

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

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

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

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

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

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

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

27、0702.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.23642.

28、0846rat19519511.9212.248.3511.1911.487.135.55757.8338kroA2002006.575.725.612.74793.2617pcb44244210.4511.078.0010.168.437.436.53438.195511組實(shí)例的平均偏離率4.58004.42555.34003.85454.50823.13092.58733.6466pr100210027.607.088.755.933.48095.0090pcb1173117311.389.877.53038.5804d1655165515.1811.358.951

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

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

31、全局最優(yōu)的解。實(shí)驗(yàn)表明，盡管ISOM算法很簡(jiǎn)單，在求解精度上它已經(jīng)超越了如KNIES、SETSP、Budinich和ESOM這樣典型的SOM算法，同時(shí)算法還保持了較低的計(jì)算復(fù)雜度，且解還具有良好的穩(wěn)健性。參考文獻(xià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., Jnger, M. an

32、d 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, G. The vehi

33、cle 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 Intractability: A

34、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 Science and

35、 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 search performan

36、ce 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. Neural computat

37、ion 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 salesman prob

38、lem. 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 efficient approac

39、h 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-424.19 Leung,

40、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, 26: 194-201

41、.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 Christopher M. Bishop

42、, Markus Svensn 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.作 者 簡(jiǎn) 介張軍英，女，1961年11月生，博士、教授、博導(dǎo)，西安電子科技大學(xué)學(xué)科帶頭人，IEEE會(huì)

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

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

45、n 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) based approaches

46、 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 solution for a TSP probl

47、em. 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 together in the w

48、hole 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 more easy to be foun

49、d. 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 Budinich, and the ESOM

50、. 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 Zhang, Bin ZhouTra

51、veling 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 applications. From the

52、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 optima