一種改進(jìn)的自組織映射算法求解旅行商問題

管 琳，張 博，黃冬梅（河北農(nóng)業(yè)大學(xué)理學(xué)院，河北保定 071000）

一種改進(jìn)的自組織映射算法求解旅行商問題

管 琳，張 博，黃冬梅
（河北農(nóng)業(yè)大學(xué)理學(xué)院，河北保定 071000）

目前，沒有求解旅行商問題的非常有效的方法。提出了一種求解該問題的LNSOM算法，在自組織映射算法的基礎(chǔ)上，改進(jìn)了學(xué)習(xí)率和鄰域函數(shù)變量。利用matlab 2011軟件進(jìn)行求解，其中5個(gè)旅行商問題實(shí)例的結(jié)果優(yōu)于MSTSP和SETSP算法，另外，10個(gè)實(shí)例的平均誤差為1.445 6 %。實(shí)驗(yàn)結(jié)果表明，新算法的誤差更小，并保持了SOM算法較低的計(jì)算復(fù)雜度。

旅行商問題；自組織映射；學(xué)習(xí)率；鄰域函數(shù)

0 引言

旅行商問題，即TSP（traveling salesman problem）是一個(gè)典型的組合優(yōu)化問題，其要求很簡(jiǎn)單：在n個(gè)城市的集合中，找出一條經(jīng)過每個(gè)城市各一次，最終回到起點(diǎn)的最短路徑。TSP沒有限定路徑的方向，所以其旅行方案數(shù)為(n≥4)種[1]。由于TSP問題難以求解，所以至今尚未找到非常有效的求解方法。

由于TSP問題代表了一類組合優(yōu)化問題，在實(shí)際工程中有許多應(yīng)用，如計(jì)算機(jī)聯(lián)網(wǎng)、電子地圖、交通誘導(dǎo)、電氣布線、VLSI單元布局、ATM分組交換網(wǎng)等。鑒于其重要的工程與理論價(jià)值，TSP常作為算法性能研究的典型算例，但求其最優(yōu)解的代價(jià)是指數(shù)級(jí)的，因此，對(duì)其近似解的研究一直是算法設(shè)計(jì)的一個(gè)重要課題[2]。

近些年，智能計(jì)算也被應(yīng)用于求解TSP的問題上，主要有遺傳算法、螞蟻算法、免疫算法、神經(jīng)網(wǎng)絡(luò)算法等。文獻(xiàn)[3-5,8]都是在SOM算法的基礎(chǔ)上融合了其他方法來求解TSP問題，取得了一定的成果。另外，2003年Frederico提出的SETSP (SOM Efficiently applied in the TSP) 算法[6]，以及2006年白艷萍提出的MSTSP (Modified SOM applied to the TSP) 算法[7]也得到了不錯(cuò)的結(jié)果。本文改進(jìn)了SOM算法的學(xué)習(xí)率和鄰域函數(shù)，并將仿真結(jié)果與SETSP及MSTSP兩個(gè)算法作比較。

1 自組織映射網(wǎng)絡(luò)

自組織映射網(wǎng)絡(luò)（Self-organizing Map，即SOM）是由Kohonen教授提出的一種競(jìng)爭(zhēng)式學(xué)習(xí)網(wǎng)絡(luò)，能將任意維輸入模式在輸出層映射成一維或二維離散圖形，并保持其拓?fù)浣Y(jié)構(gòu)不變。在無教師示教的情況下，通過對(duì)輸入模式的自組織學(xué)習(xí)，在競(jìng)爭(zhēng)層將分類結(jié)果表示出來。此外，網(wǎng)絡(luò)通過對(duì)輸入模式的反復(fù)學(xué)習(xí)，可以使連接權(quán)矢量空間分布密度與輸入模式的概率分布趨于一致[5]。

SOM的學(xué)習(xí)算法由兩部分組成，分別是獲勝神經(jīng)元的選擇和網(wǎng)絡(luò)權(quán)系數(shù)的更新。

1.1 獲勝神經(jīng)元的選擇

設(shè)X＝(x1, x2, …, xn)T表示輸入信號(hào)，Wi＝(wi1, wi2, …, win)T表示連接輸入信號(hào)和神經(jīng)元i的所有連接權(quán)值，則獲勝神經(jīng)元j可以表示為οj=max{οi}=max{f (X,Wi)}。這里，f是預(yù)先確定的判定函數(shù)，也是神經(jīng)元的輸出函數(shù)。通常f取f(X,Wi)=?||X?Wi||，其中‖X ?Wj‖是歐氏距離。

1.2 網(wǎng)絡(luò)權(quán)系數(shù)的更新

1984年Kohonen提出了一個(gè)權(quán)值修正公式[9]

其中rj和ri分別是獲勝神經(jīng)元j及相鄰神經(jīng)元i的位置向量，α(t)和σ(t)都是隨時(shí)間而遞減的函數(shù)。在獲勝神經(jīng)元鄰域范圍內(nèi)的神經(jīng)元都會(huì)受到激勵(lì)，它們的連接權(quán)值都將被調(diào)整。鄰域半徑隨著時(shí)間逐漸減小。

1.3 TSP問題的自組織映射網(wǎng)絡(luò)

文獻(xiàn)[7]構(gòu)造了一個(gè)二層的自組織映射網(wǎng)絡(luò)求解TSP問題。輸入層有兩個(gè)神經(jīng)元，分別代表TSP問題中城市的位置坐標(biāo)，輸出層由m個(gè)神經(jīng)元（節(jié)點(diǎn)）組成一個(gè)閉合路徑。通過Kohonen自組織學(xué)習(xí)算法，使得路徑上的節(jié)點(diǎn)向距離最近的城市移動(dòng)。每次輸入一個(gè)城市進(jìn)行學(xué)習(xí)，離城市最近的節(jié)點(diǎn)成為獲勝節(jié)點(diǎn)。由下式來計(jì)算獲勝節(jié)點(diǎn)J

其中xi表示城市的坐標(biāo)，yj表示環(huán)節(jié)點(diǎn)的坐標(biāo)，|| . ||表示Euclidean距離。

獲勝節(jié)點(diǎn)和它的鄰域按照下面的公式向相應(yīng)城市移動(dòng)

α 和σ 是學(xué)習(xí)率和鄰域函數(shù)變量，d = min{| j ?J |, m ? | j ?J |}表示在環(huán)上節(jié)點(diǎn)j 和 J 的距離，| . | 代表絕對(duì)值，m代表節(jié)點(diǎn)數(shù)。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定時(shí)，每個(gè)城市均對(duì)應(yīng)于一個(gè)獲勝節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)構(gòu)成的閉合回路就是TSP的遍歷路徑，同時(shí)可以求出近似解。

2 算法改進(jìn)

2.1 學(xué)習(xí)率和鄰域函數(shù)變量的改進(jìn)

自組織映射網(wǎng)絡(luò)的學(xué)習(xí)過程分為兩個(gè)階段。第一階段為粗學(xué)習(xí)和粗調(diào)整階段。在這一階段內(nèi)，各隨機(jī)方向的連接權(quán)矢量朝著輸入模式的方向進(jìn)行調(diào)整，并大致確定了各輸入模式在競(jìng)爭(zhēng)層中所對(duì)應(yīng)的映射位置。一般此階段的學(xué)習(xí)率大于0.5。一旦各輸入模式有了相對(duì)的映射位置后，則轉(zhuǎn)入第二階段——精學(xué)習(xí)和細(xì)調(diào)整階段。在這一階段內(nèi)，網(wǎng)絡(luò)學(xué)習(xí)集中在對(duì)較小范圍內(nèi)的連接權(quán)進(jìn)行調(diào)整，學(xué)習(xí)率應(yīng)隨著學(xué)習(xí)的進(jìn)行而不斷減小。一般此階段學(xué)習(xí)率的初始值選為0.5[5]。

SOM有兩個(gè)更新參數(shù)，學(xué)習(xí)率α 和鄰域函數(shù)變量σ 。1990年Kohonen又建議了一個(gè)指數(shù)的參數(shù)更新公式[10]

這里，k是迭代次數(shù)，τ1和τ2是指數(shù)時(shí)間常數(shù)，α0= 1, σ0= 10 , τ1= 20 , τ2= 10 。公式(4)、公式(5)的參數(shù)更新過程如圖1、圖2所示。

文獻(xiàn)[7]中的MSTSP算法建議采用的參數(shù)更新公式如下

k是迭代次數(shù), σ0= 10。公式（7）有一定的局限性，σ 隨著迭代次數(shù)的增加而減小，但是如果k等于100，那么σ = 0，則無法再進(jìn)行迭代了。

圖1 SOM算法的學(xué)習(xí)率Fig. 1 Learning rate of SOM

圖2 SOM算法的鄰域函數(shù)變量Fig. 2 Neighborhood function variance of SOM

本文提出一種新的參數(shù)更新公式：

其中k是迭代次數(shù)，T取常數(shù)，與運(yùn)算時(shí)間有關(guān)，一般可以取為迭代次數(shù)的倍數(shù)。本文取k的最大迭代次數(shù)為60，T = 1 000，σ0= 10。公式(8)、公式(9)的參數(shù)更新過程如圖3、圖4所示。

圖3 學(xué)習(xí)率Fig. 3 Learning rate

圖4 鄰域函數(shù)變量Fig. 4 Neighborhood function variance

從圖1和圖3的對(duì)比可以看到，Kohonen建議的學(xué)習(xí)率在前30次時(shí)減小得非?？?，在第40次迭代時(shí)取值已接近0.1，這可能使得公式（2）的值很小，也就是說獲勝節(jié)點(diǎn)以及它的鄰域位置的改變量很小。如果此時(shí)節(jié)點(diǎn)還沒有靠近城市位置，就有可能導(dǎo)致迭代結(jié)束了，但此時(shí)的節(jié)點(diǎn)還沒有覆蓋城市位置。改進(jìn)后的學(xué)習(xí)率在前30次迭代時(shí)變化較快，從1減小至0.5左右，這是粗學(xué)習(xí)和粗調(diào)整階段，大致確定了節(jié)點(diǎn)對(duì)應(yīng)的城市位置；而30次以后的變化率比前一階段小，這是精學(xué)習(xí)和細(xì)調(diào)整階段，最終確定了獲勝節(jié)點(diǎn)對(duì)應(yīng)的城市位置。

從圖2和圖4的對(duì)比可以看到，Kohonen建議的鄰域函數(shù)變量的值在迭代20次時(shí)就接近于1，迭代40次以后接近于0，那么鄰域函數(shù)的值則趨近于0，從而使獲勝節(jié)點(diǎn)以及它的鄰域的位置改變量幾乎為0，因此可能導(dǎo)致節(jié)點(diǎn)還沒有找到相應(yīng)的城市位置時(shí)就停止不動(dòng)了。改進(jìn)后的鄰域函數(shù)變量通過實(shí)驗(yàn)?zāi)軌虮ＷC節(jié)點(diǎn)收斂到城市位置，對(duì)于城市規(guī)模較大的實(shí)例也適用。

2.2 改進(jìn)后的算法

本文提出了一種求解TSP問題的LNSOM (imoproved learning rate and neighborhood function varience of SOM) 算法。

(1) 輸入：確定城市位置坐標(biāo)，隨機(jī)排列城市的輸入順序，城市個(gè)數(shù)記作n，迭代次數(shù)記作k，獨(dú)立運(yùn)算次數(shù)記作j。

(2) 輸出層，即網(wǎng)絡(luò)初始化：輸出層初始化為一個(gè)具有m個(gè)節(jié)點(diǎn)（m = 2n）的圓形閉合路徑，圓心位于城市坐標(biāo)的重心處，半徑取n個(gè)城市橫坐標(biāo)平均值的五分之一，節(jié)點(diǎn)的坐標(biāo)作為輸入層與輸出層的連接權(quán)值。

(3) 網(wǎng)絡(luò)訓(xùn)練過程

(3.1) 參數(shù)更新——按照公式(8)，公式(9)更新學(xué)習(xí)率αk和鄰域函數(shù)變量σk；

(3.2) 競(jìng)爭(zhēng)——通過競(jìng)爭(zhēng)，選擇離第i個(gè)城市歐式距離最近的節(jié)點(diǎn)，記作獲勝節(jié)點(diǎn)J；

(3.3) 鄰域更新——用公式(2)和公式(3)更新獲勝節(jié)點(diǎn)和它的鄰域；

(3.4) i: = i+1, 如果i ＜ n+1, 轉(zhuǎn)向(3.2)；否則, k: = k+1轉(zhuǎn)向(3.1)；

(3.5) 當(dāng)k ＞ kmax時(shí), 轉(zhuǎn)向 (1)，j: = j+1；當(dāng)j = jmax時(shí)，轉(zhuǎn)向(4)。

(4) 網(wǎng)絡(luò)測(cè)試過程：取獨(dú)立運(yùn)算j次中最好的解作為連接權(quán)值，再進(jìn)行一次運(yùn)算，結(jié)束。

LNSOM算法計(jì)算復(fù)雜度分析：每一個(gè)城市平均計(jì)算的鄰域節(jié)點(diǎn)數(shù)為0.3m ，在一次迭代中需要計(jì)算0.3mn次。隨著鄰域函數(shù)變量的減小，每個(gè)城市需要計(jì)算的鄰域節(jié)點(diǎn)數(shù)也在減少，而且減少的速度很快，如圖4所示。因此，LNSOM算法保持了SOM算法具有的較低計(jì)算復(fù)雜度的特點(diǎn)。

3 實(shí)驗(yàn)結(jié)果與分析

我們對(duì)LNSOM算法進(jìn)行了計(jì)算機(jī)仿真，利用matlab 2011a軟件得到了7個(gè)TSP實(shí)例的近似解，并與最優(yōu)解以及文獻(xiàn)[7]中MSTSP、SETSP算法的解進(jìn)行了比較，如表1所示（表1中的數(shù)據(jù)是TSP實(shí)例獨(dú)立運(yùn)行10次的最小值）。為了驗(yàn)證LNSOM算法的有效性，對(duì)另外10個(gè)實(shí)例進(jìn)行了計(jì)算機(jī)仿真，實(shí)驗(yàn)結(jié)果見表2（表2中的數(shù)據(jù)是TSP實(shí)例獨(dú)立運(yùn)行10次的統(tǒng)計(jì)結(jié)果）。其中4個(gè)實(shí)例得到了最優(yōu)解，其他6個(gè)實(shí)例也得到了較好的近似解。10個(gè)實(shí)例的平均誤差為1.445 6 % 。實(shí)驗(yàn)結(jié)果表明LNSOM算法在求解城市個(gè)數(shù)為200左右的TSP問題上是非常有效的。

實(shí)驗(yàn)數(shù)據(jù)來源：http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/。

表1 7個(gè)TSP實(shí)例的運(yùn)算結(jié)果（無單位）Tab. 1 Results of 7 TSP instances

表2 10個(gè)TSP實(shí)例的運(yùn)算結(jié)果（無單位）Tab.2 Results of 10 TSP instances

4 結(jié)論與展望

本文提出了一種改進(jìn)的SOM算法，通過改進(jìn)學(xué)習(xí)率和鄰域函數(shù)變量使得鄰域更新過程更加合理有效，從而能夠找到更好的近似解。實(shí)驗(yàn)表明，LNSOM算法在計(jì)算200個(gè)城市及以下規(guī)模的TSP問題上比SETSP和MSTSP算法的誤差更小，并且保持了較低的計(jì)算復(fù)雜度。

今后，可以嘗試將該算法應(yīng)用于求解大規(guī)模的TSP問題或者車輛路徑問題等。

[1] 胡運(yùn)權(quán). 運(yùn)籌學(xué)教程[M]. 北京： 清華大學(xué)出版社, 1998.

[2] 高海昌, 馮博琴, 朱利. 智能優(yōu)化算法求解TSP問題[J]. 控制與決策, 2006, 21(3)： 241-247.

[3] 張軍英, 周斌. 基于泛化競(jìng)爭(zhēng)和局部滲透機(jī)制的自組織網(wǎng)TSP問題求解方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(2)： 220-227.

[4] 吳婷, 陳玉旺, 汪燁. 基于極值動(dòng)力學(xué)的自組織優(yōu)化算法求解TSP問題[J]. 控制理論與應(yīng)用, 2010, 27(6)： 715-720.

[5] 聞新, 周露. Matlab神經(jīng)網(wǎng)絡(luò)應(yīng)用設(shè)計(jì)[M]. 北京： 科學(xué)出版社, 2002.

[6] 白艷萍. 人工神經(jīng)網(wǎng)絡(luò)在組合優(yōu)化與信息處理中的應(yīng)用[D]. 中北大學(xué)博士論文, 太原： 中北大學(xué), 2005： 68-73.

[7] BAI Y P, ZHANG W D, JIN Z. A new self-organizing maps strategy for solving the traveling salesman problem[J]. Chaos, Solitons & Fractals, 2006, 28： 1082-1089.

[8] BAI Y P, ZHANG W D. A new elastic net learning algorithm for travelling salesman problem[C]//International Symposium on Test and Measurement. International Academic Publishers World Publishing Corporation, 2005, 6： 5882-5888.

[9] Kohonen. Self-organization and associative memory[J]. Springer-Verlag, Berlin, 1984, 45： 256-260.

[10] Kohonen. The self-organizing map[J]. Proceedings of the IEEE, 1990, 78： 1464-1480.

An Improved Self-organizing Algorithm for Solving the Traveling Salesman Problem

GUAN Lin, ZHANG Bo, HUANG Dong-mei
(School of Science, Agriculture University of Hebei Province, Hebei 071000, P. R. China)

There are no effective corresponding solutions to the traveling salesman problems (TSP). To address the problems, a new algorithm by improving learning rate and neighborhood function variance of the self-organizing map (SOM) is presented. The solutions of five instances are better than MSTSP and SETSP in matlab2011. The average error is only 1.445 6 % of anthor ten. The new algorithm has the advantage of smaller error and maintaining low SOM algorithm computational complexity.

traveling salesman problem; self-organizing map; learning rate; neighborhood function variance

TP18

A

1001-4543(2012)01-0048-05

2012-11-28;

2012-02-09

管琳（1981－），女，河北保定人，講師，碩士，主要研究方向?yàn)樯窠?jīng)網(wǎng)絡(luò)算法與應(yīng)用，電子郵箱sxguanlin@hebau.edu.cn。

河北省軟科學(xué)計(jì)劃項(xiàng)目（No. 104572108）；河北農(nóng)業(yè)大學(xué)非生命課題（No. FS201008）；保定市科學(xué)技術(shù)研究與發(fā)展指導(dǎo)計(jì)劃軟科學(xué)項(xiàng)目（No. 11ZR004）