一種求解旅行商問題的改進粒子群算法

羅金炎

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

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

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

規(guī)劃問題

(1)

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

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

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

2 TSP問題模型分析

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

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

(2)

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

(3)

因是線性規(guī)劃模型，線性規(guī)劃的可行解集是一個凸集，最優(yōu)解通常在邊界上取得，即在x=0或x=1上取得，所以式(3)等價于式(2).為便于分析，上述模型可以進一步整理為如下線性等式約束的非線性規(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.文獻[9]中指出約束函數(shù)g(x)在點x*的frechet導數(shù)g(x*)需要有一個m階子塊是非奇異的(即秩A=m)，記

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

或

(5)

應用無約束優(yōu)化方法求解非線性方程組(5)時，通?？梢詫⑵滢D(zhuǎn)換為求解:

(6)

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

(7)

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

3 改進的粒子群算法設計

3.1 粒子群算法[11]

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

(8)

(9)

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

3.2 粒子群算法位置更新公式的改進

x3i=x1i+α(x1i-x2i)

(10)

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

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

(11)

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

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

(12)

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

(13)

3.3 求解TSP的改進粒子群算法具體步驟

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

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

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

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

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

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

(14)

步驟9：如果m

(15)

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

4 仿真實驗

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

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

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

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

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

4.2 算法性能比較

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

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

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

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

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

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

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

5 結(jié) 論

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

[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] 張盛意,蔡之華,占志剛,等.基于改進模擬退火的遺傳算法求解0-1背包問題[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].控制與決策，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].重慶建筑工程學院學報，1990,12(1)：49-55.

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

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

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

[13] 聶贊坎,徐宗本.隨機逼近及自適應算法[M].北京：科學出版社，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問題的改進果蠅優(yōu)化算法[J].計算機工程與應用,2016,52(6):144-149.