一種求解旅行商問題的改進(jìn)粒子群算法

羅金炎

(閩江學(xué)院 數(shù)學(xué)系， 福建 福州 350108)

旅行商問題(TSP)是組合優(yōu)化領(lǐng)域中經(jīng)典的NP難問題[1]，具有很強(qiáng)的現(xiàn)實(shí)意義.由于在許多領(lǐng)域都有廣泛的應(yīng)用，如計(jì)算機(jī)網(wǎng)絡(luò)設(shè)計(jì)、通信節(jié)點(diǎn)設(shè)置、集成電路布線、物流配送等，因而一直以來是研究熱點(diǎn)，為解決實(shí)際問題，廣大研究者提出了許多求解算法(精確式或啟發(fā)式).精確式算法能夠得到問題最優(yōu)解，但是需要與問題維數(shù)成指數(shù)級(jí)增長的時(shí)間成本，所能夠求解的問題規(guī)模非常有限.啟發(fā)式算法也稱作近似算法，它以犧牲找到最優(yōu)解的保證為代價(jià)，在合理的時(shí)間內(nèi)找到近似解甚至最優(yōu)解，其求解復(fù)雜度多是多項(xiàng)式階數(shù)的.隨著人工智能的發(fā)展，許多智能優(yōu)化算法應(yīng)用于TSP問題的求解，取得了較好結(jié)果.比如神經(jīng)網(wǎng)絡(luò)算法[2]、模擬退火算法[3]、禁忌搜索算法[4]、遺傳算法[5]、蟻群算法[6]、粒子群算法[7]等.這些智能優(yōu)化算法求解TSP問題，大多采用二進(jìn)制編碼求解0-1整數(shù)規(guī)劃問題的思路進(jìn)行尋優(yōu).本文利用等式約束規(guī)劃問題K-T點(diǎn)的一個(gè)充分條件，將TSP問題的線性等式約束非線性規(guī)劃進(jìn)行降維使之轉(zhuǎn)化為無約束極大極小優(yōu)化問題.并基于基因調(diào)節(jié)原理運(yùn)用外推技巧來改進(jìn)粒子群算法，新的算法通過利用不同位置粒子的差異來引導(dǎo)外推方向，采用滿足有限平方和準(zhǔn)則的動(dòng)態(tài)調(diào)節(jié)因子并在速度項(xiàng)中添加高斯擾動(dòng)，來提高算法的尋優(yōu)效率.數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了本文提出算法的有效性并具有較好的收斂效率.

1 等式約束規(guī)劃問題K-T點(diǎn)的一個(gè)充分條件

規(guī)劃問題

(1)

定理1[9]： 若x*∈Rn是方程組

的解，且M(x*)非奇異，則x*是上述規(guī)劃問題(1)的K-T點(diǎn).即

其中λ=-[M(x*)]TQ(x*).

2 TSP問題模型分析

TSP問題一般性描述為：給定n個(gè)城市以及任意兩個(gè)城市之間的距離，尋求一條經(jīng)過所有城市的最短訪問路徑，每個(gè)城市必須訪問且只能訪問一次.其圖論描述為：給定圖G=(V,A),其中V為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的弧集，已知各個(gè)頂點(diǎn)連接距離，要求一條長度最短的Hamilton回路.設(shè)dij為城市i與j之間的距離，即弧(i,j)的長度 (i≠j)，當(dāng)i=j時(shí)cij為足夠大的數(shù).引入決策變量

那么TSP問題的數(shù)學(xué)模型可表示為[7]:

(2)

其中上述模型可進(jìn)一步松弛為如下連續(xù)問題[8]：

(3)

因是線性規(guī)劃模型，線性規(guī)劃的可行解集是一個(gè)凸集，最優(yōu)解通常在邊界上取得，即在x=0或x=1上取得，所以式(3)等價(jià)于式(2).為便于分析，上述模型可以進(jìn)一步整理為如下線性等式約束的非線性規(guī)劃問題的矩陣形式:

(4)

其中：CT=(c11,c12,…,c1n,c21,c22,…,c2n,…,cn1,cn1,…,cnn)，x=(x11,x12,…,x1n,x21,x22,…,x2n,…,xn1,xn1,…,xnn).

令m=2n，k=n2，則

f:Rk→R，

p=k-m.

這里g(x)=Ax-b，則有g(shù)(x)=(Ax-b)=A.文獻(xiàn)[9]中指出約束函數(shù)g(x)在點(diǎn)x*的frechet導(dǎo)數(shù)g(x*)需要有一個(gè)m階子塊是非奇異的(即秩A=m)，記

根據(jù)定理1，可將上述求解等式約束規(guī)劃問題(4)轉(zhuǎn)化為求解非線性方程組：

或

(5)

應(yīng)用無約束優(yōu)化方法求解非線性方程組(5)時(shí)，通常可以將其轉(zhuǎn)換為求解:

(6)

當(dāng)p=2時(shí)，此為非線性最小二乘問題；當(dāng)p=∞ 時(shí)，此為無約束極大極小優(yōu)化問題:

(7)

極大極小問題(7)為非光滑優(yōu)化問題，應(yīng)用PSO算法可以有效求解此類問題[10]，可以不必構(gòu)造可微光滑函數(shù)，以式(7)為粒子的適應(yīng)度函數(shù)，函數(shù)值越小表示適應(yīng)度越高.

3 改進(jìn)的粒子群算法設(shè)計(jì)

3.1 粒子群算法[11]

粒子群算法與其他進(jìn)化類算法相似, 采用“群體”與“進(jìn)化”的概念, 同時(shí)依據(jù)個(gè)體的適應(yīng)值大小進(jìn)行操作. 不同的是, 粒子群算法不像其他進(jìn)化算法那樣對于個(gè)體使用進(jìn)化算子, 而是將每個(gè)個(gè)體看作是在搜索空間中的一個(gè)沒有質(zhì)量和體積的粒子, 并在搜索空間中以一定的速度飛行.每個(gè)粒子的飛行速度由其本身的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)調(diào)整．經(jīng)典粒子群算法根據(jù)公式(8)進(jìn)行迭代更新，粒子在解空間內(nèi)不斷跟蹤個(gè)體極值和鄰域極值進(jìn)行搜索, 直到滿足迭代停止條件, 即達(dá)到規(guī)定的迭代次數(shù)或滿足規(guī)定的誤差標(biāo)準(zhǔn).

(8)

(9)

其中:w為慣性權(quán)重； rand()為均勻分布在(0,1)之間的隨機(jī)數(shù)；c1和c2為學(xué)習(xí)因子．粒子的速度vi被最大速度Vmax所限制，即若vi>Vmax，則令vi=Vmax，而若vi<-Vmax，也令vi=Vmax.

3.2 粒子群算法位置更新公式的改進(jìn)

x3i=x1i+α(x1i-x2i)

(10)

其中α為調(diào)節(jié)因子，它決定調(diào)節(jié)的幅度，一般不能過大取大于零的小正數(shù)，來確保f(x3)

利用不同位置粒子的差異來引導(dǎo)外推方向.在由粒子群算法產(chǎn)生新位置時(shí)，再依據(jù)算法位置更新公式(9)產(chǎn)生另一個(gè)虛擬位置(在粒子尚未達(dá)到最優(yōu)點(diǎn)時(shí)，對連續(xù)函數(shù)來說在附件存在更優(yōu)的點(diǎn))：

(11)

其中rand()為[0,1]內(nèi)服從均勻分布的隨機(jī)數(shù).

根據(jù)外推技巧由式(10)和式(11)有：

(12)

一般地，在起初階段距離最優(yōu)解較遠(yuǎn)，調(diào)節(jié)幅度較大有利于加速進(jìn)化，而在后期距離最優(yōu)解較近時(shí)，調(diào)節(jié)幅度應(yīng)較小些.對多變量優(yōu)化問題，由于每個(gè)粒子的位置分量較多，容易出現(xiàn)某些分量非常接近甚至相同的兩個(gè)粒子，對此外推技巧將不起作用，在具體操作中需要在式(12)加上一個(gè)微小擾動(dòng).基于此(上述兩點(diǎn))，調(diào)節(jié)因子采用動(dòng)態(tài)遞減滿足隨機(jī)遞推算法[13]的數(shù)列因子，并在算法中的速度項(xiàng)部分添加高斯擾動(dòng).最后得到的位置公式為：

(13)

3.3 求解TSP的改進(jìn)粒子群算法具體步驟

步驟1：確定矩陣M和N，進(jìn)一步確定矩陣P和Q，利用式(7)作為適應(yīng)值函數(shù)；

步驟2：初始化種群N的粒子群，包括每個(gè)粒子的位置和速度，計(jì)算適應(yīng)值函數(shù)，并記錄粒子的個(gè)體歷史最優(yōu)位置和種群全局最優(yōu)位置；

步驟3：根據(jù)式(8)和式(13)分別更新粒子的速度和位置，計(jì)算位置更新后的適應(yīng)值函數(shù)，并與其個(gè)體歷史最優(yōu)值相比較，若更優(yōu)，則更新粒子的個(gè)體歷史最優(yōu)位置，否則不變；

步驟4：將粒子的個(gè)體歷史最優(yōu)與種群的全局最優(yōu)進(jìn)行比較，若更優(yōu)，則更新種群全局最優(yōu)位置，否則不變；

步驟5：如果滿足算法的終止條件|xk-xk-1|<ε，則輸出全局最優(yōu)解，否則轉(zhuǎn)到步驟3繼續(xù)執(zhí)行.

為確保產(chǎn)生整數(shù)解，繼續(xù)下面的步驟：

(14)

步驟9：如果m

(15)

步驟10：計(jì)算最優(yōu)路徑結(jié)果值，記錄迄今為止的最優(yōu)解.檢查是否達(dá)到最大迭代步數(shù)，若是則結(jié)束，否則轉(zhuǎn)步驟3.

4 仿真實(shí)驗(yàn)

4.1 算法有效性測試，10個(gè)城市的旅行商問題

為了驗(yàn)證算法的效果性能，先采用10節(jié)點(diǎn)的小樣本TSP問題對算法的有效性進(jìn)行驗(yàn)證，其節(jié)點(diǎn)位置如圖1所示.

圖1 10城市節(jié)點(diǎn)位置

算法進(jìn)行了50次實(shí)驗(yàn)，最大迭代次數(shù)100，均能得到最優(yōu)解，最快迭代次數(shù)為16次，得到的連續(xù)最優(yōu)解矩陣為:

圖2 算法搜尋到的最優(yōu)路徑

4.2 算法性能比較

為進(jìn)一步比較算法的性能，從TSPLIB標(biāo)準(zhǔn)庫(http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95)中選取部分經(jīng)典實(shí)例，使用Matlab 6.5編程，在CPU為AMD1.65 GHz內(nèi)存為2 GB的計(jì)算機(jī)上進(jìn)行仿真實(shí)驗(yàn).最大迭代次數(shù)為1 000，實(shí)驗(yàn)測試100次.分別與PSO[14]、改進(jìn)的FOA[15]進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表1和表2所示，OPT是已知最優(yōu)值.

表1 本文算法求解TSP算例的仿真結(jié)果

表2 算法求解不同TSP算例的比較結(jié)果

從表2最優(yōu)值和平均值的對比可以看出:本文算法對于不同規(guī)模的TSP問題均能尋優(yōu)搜索到最優(yōu)路徑，充分反映了本文算法尋優(yōu)的有效性.本文算法的偏差均比其他2個(gè)算法小，表明本文算法具有良好的全局收斂能力，這是因?yàn)樗惴ㄋ俣软?xiàng)部分添加高斯擾動(dòng)能夠較好地避免算法陷入局部最優(yōu)而早熟;從平均迭代次數(shù)指標(biāo)上表明本文算法尋優(yōu)速度具明顯優(yōu)勢，這是因?yàn)樗惴ǖ膭?dòng)態(tài)調(diào)節(jié)因子序列滿足有限平方和準(zhǔn)則，其選取策略對于迭代序列的收斂行為起著關(guān)鍵作用.通過程序的仿真實(shí)驗(yàn)，本文算法解決部分實(shí)例的最優(yōu)路徑如圖3～圖5所示.

圖3 Bays29的最優(yōu)路徑

圖4 Berlin52的最優(yōu)路徑

圖5 Gr96的最優(yōu)路徑

5 結(jié) 論

利用等式約束問題K-T點(diǎn)的一個(gè)充分條件，將TSP問題的線性等式約束非線性規(guī)劃進(jìn)行降維使之轉(zhuǎn)化為無約束極大極小優(yōu)化問題，并基于基因調(diào)節(jié)原理運(yùn)用外推技巧來改進(jìn)粒子群算法，新的算法通過加強(qiáng)對進(jìn)化方向的引導(dǎo)，采用滿足有限平方和準(zhǔn)則的動(dòng)態(tài)遞減調(diào)節(jié)因子，并在速度項(xiàng)中添加高斯擾動(dòng)，提高了算法的尋優(yōu)效率，數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了本文提出算法的有效性并具有較好的收斂效果.

[1] GRECO F.Travelling Salesman Problem[M].Croatia:In-Teh,2008:36-39.

[2] LI M L,YI Z,ZHU M.Solving TSP by Using Lotka-Volterra Neural Networks[J].Neurocomputing,2009,72(16):3873-3880.

[3] 張盛意,蔡之華,占志剛,等.基于改進(jìn)模擬退火的遺傳算法求解0-1背包問題[J].微電子與計(jì)算機(jī)，2011,28(2)：61-64.

[4] GLOVER F.Future Paths for Integer Programming and Links to Artifical Intelligence[J].Computers and Operations Research,1986,13(5) ：533-549.

[5] 于瑩瑩,陳燕,李桃迎,等.改進(jìn)的遺傳算法求解旅行商問題[J].控制與決策，2014,29(8):1483-1488.

[7] HOPFIELD J J,TANK D W.“Neural” Computation of Decisions in Optimization Problems[J].Biological Cybernetics,1985,52(3):141-152.

[8] DANG C Y,XU L.A Lagrange Multiplier and Hopfield-Type Barrier Function Method for the Traveling Salesman Problem[J].Neural Computation,2001，14(2):303-324.

[9] 李澤民.最優(yōu)化問題的一種新途徑[J].重慶建筑工程學(xué)院學(xué)報(bào)，1990,12(1)：49-55.

[10] 張建科,李立峰,周暢,等.一類非線性極小極大問題的改進(jìn)粒子群算法[J].計(jì)算機(jī)應(yīng)用，2008,28(5)：1194-1196.

[11] 曾建潮,介倩,崔志華,等.微粒群算法[M].北京：科學(xué)出版社，2004：7-8.

[12] 王湘中,喻壽益,賀素良,等.一種強(qiáng)引導(dǎo)進(jìn)化型遺傳算法[J].控制與決策，2004,19(7)：705-798.

[13] 聶贊坎,徐宗本.隨機(jī)逼近及自適應(yīng)算法[M].北京：科學(xué)出版社，2003：23-28.

[14] MARINAKI S Y，MARINAKI M.A Hybrid Multi-Swarm Particle Swarm Optimization Algorithm for the Probabilistic Traveling Salesman Problem[J].Comput Oper Res,2010,37(3):432-442.

[15] 段艷明,肖輝輝.求解TSP問題的改進(jìn)果蠅優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(6):144-149.