一種改進多狀態(tài)的粒子群算法在TSP中的應(yīng)用

李 航, 滕 琳, 殷守林(沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034)

0 引 言

粒子群優(yōu)化算法(PSO)[1-3]是基于數(shù)量的隨機優(yōu)化技術(shù),它模擬群體行為執(zhí)行任務(wù),如鳥群和魚類的行為,以發(fā)現(xiàn)基于目標函數(shù)的最佳解決方案。目前,不僅粒子群優(yōu)化算法得到廣泛應(yīng)用,而且其他的人工智能算法也陸續(xù)被提出,如魚群算法[4]、布谷鳥算法[5]、狼群算法[6]、模擬退火算法[7]、蟻群算法[8]等。 傳統(tǒng)的PSO主要用于尋找連續(xù)優(yōu)化問題的解決方案。 后來,又提出了一種被稱為二進制粒子群優(yōu)化算法,可以允許PSO算法在離散二進制變量中運行[9]。目前,就收斂速度,局部最優(yōu),計算時間和局部測量方面,提出了很多改進的PSO算法[10-14]。 但是,為了從多角度解決優(yōu)化離散問題,提出了多態(tài)粒子群(MSPSO)[15]。 然而,MSPSO算法的局限性是經(jīng)常產(chǎn)生不可行的解,并且需要繁瑣的步驟來將不可行解轉(zhuǎn)換為可行解。

程等[16]提出了改進局部搜索混沌離散粒子群優(yōu)化算法,基于輪盤賭選擇原理,給每段路徑設(shè)定一個合理的優(yōu)秀系數(shù),以提高短邊被選擇的概率,從而有利于提高算法的尋優(yōu)能力和收斂速度;為了進一步提高解的精確性,在算法機制中添加了局部搜索策略,通過調(diào)整每個城市在給定鄰域內(nèi)的城市路徑,提高算法的局部搜索能力;另外,在算法的迭代公式中加入了混沌序列來提高粒子的隨機性和多樣性,增強了算法的全局搜索能力。但是這種方法收斂速度較慢。而李等[17]將伊藤算法中的漂移和波動算子運用于粒子群算法中的學(xué)習(xí)因子,將牛頓力學(xué)中的加速度因子映射粒子群算法的慣性權(quán)重來改進粒子群算法。仍然存在一定的誤差。針對以上問題,文中提出了一個基于規(guī)則策略的多態(tài)粒子群算法,多狀態(tài)的粒子群可以產(chǎn)生更加準確的優(yōu)化解,并且為了說明其有效性,采用TSP問題來驗證。結(jié)果表明新算法可以獲得較好的解,比傳統(tǒng)粒子群算法具有更快的收斂速度。

1 粒子群優(yōu)化算法

在傳統(tǒng)粒子群優(yōu)化算法中,通過模擬鳥類行為來發(fā)現(xiàn)最優(yōu)解,粒子群優(yōu)化算法需要粒子群體活動,使用它們的位置對優(yōu)化問題的可能解決方案進行編碼。粒子可以通過使用共同的相鄰信息有效地獲得解決方案。通過這些信息,每個粒子將其當前位置與其近鄰的最佳位置進行比較。粒子群優(yōu)化算法的偽碼如下所示:

初始化粒子種群；對每個粒子執(zhí)行評價函數(shù)；while不滿足結(jié)束條件do更新種群局部pbest和全局gbest最優(yōu)解；更新粒子的速度和位置；再對更新的粒子執(zhí)行評價函數(shù)；end while輸出最優(yōu)解．

其中pbest和gbest定義為局部和全局最優(yōu)解。

考慮函數(shù)最小值問題。初始化階段,在搜索空間內(nèi),隨機定義I個粒子的位置,并給每個粒子分配初始速度。一個粒子的位置表達式定義為si(d)(i=1,2,3,…,I;d=1,2,3,…,D),同時它也代表一個解。通過計算目標函數(shù)si(k)獲得每個粒子的函數(shù)值,k代表迭代次數(shù)。每個粒子更新的速度和位置公式為

其中:c1和c2分別是感知和社交系數(shù);r1和r2是0到1之間的隨機數(shù);ω稱為慣性權(quán)重,用來調(diào)節(jié)先前的粒子速度對當前粒子速度的影響。

2 多狀態(tài)粒子群優(yōu)化算法

為了解決離散優(yōu)化問題,在多狀態(tài)粒子優(yōu)化算法中,每個粒子的向量或者維度都要表示成狀態(tài)。為了詳細描述多狀態(tài)粒子優(yōu)化算法,在TSP問題中選擇Burmal 4函數(shù)作為一個例子,如圖1所示。

在Burmal 4中,所有城市都可以被描述成狀態(tài)集合,如圖2所示。黑點代表狀態(tài),圓心代表當前速度,半徑代表當前狀態(tài)被處理過的速度值。這3個元素在每個粒子的每一維中都存在,在pbest和gbest更新之后,多狀態(tài)粒子優(yōu)化算法將會發(fā)生轉(zhuǎn)變。在多狀態(tài)粒子優(yōu)化算法中,速度的計算方式是不同于傳統(tǒng)粒子群算法,因為在新的算法中,pbesti(k,d)和si(k,d)是狀態(tài)的形式。對于傳統(tǒng)粒子群,一個粒子有3個運動分量:慣性向量,認知向量和社交向量。這3個分量的作用分別是,慣性向量使得粒子朝著它自己的運動軌跡偏斜,認知向量使粒子回到最初的最優(yōu)解位置,社交向量使粒子朝著全局最優(yōu)解的粒子位置處運動。然而,在多狀態(tài)粒子優(yōu)化算法中,速度的值是先前速度的總和。代價函數(shù)是一個多項式表達式。

圖1 Burmal 4函數(shù)Fig.1 Burmal 4 function

圖2 狀態(tài)表示Fig.2 State expression

因此,可以推導(dǎo)出速度方程為

代價函數(shù)可以定義為城市之間的最短距離,2個狀態(tài)之間的代價函數(shù)值是由C(sj(k,d).si(k,d))給定的一個正數(shù)。在多狀態(tài)粒子優(yōu)化算法中,速度一旦被更新,那么將會執(zhí)行每個粒子每一維的當前狀態(tài)更新到下一狀態(tài)。令當前狀態(tài)是圓心,更新的速度值作為圓的半徑,在圓內(nèi)的任何狀態(tài)都被定義為內(nèi)部狀態(tài)集合的一個成員。在內(nèi)部狀態(tài)集合中使用公式(4)來隨機選擇下一個狀態(tài)。給定內(nèi)部狀態(tài)集合(有j個要素),Ii(k,d)=(Ii1((k,d),…,Iij(k.d)))。

si(k+1,d)=random(Ii1((t,d),…,Ii,j(t.d)))

(4)

為了更新多狀態(tài)粒子優(yōu)化算法中的狀態(tài),使用一個隨機函數(shù),在更新解階段,方程(4)可能導(dǎo)致一個重復(fù)的狀態(tài)存在。在具體的一個迭代過程中,一個粒子的解由14維向量組成{s5,s3,s14,s11,s2,s8,s9,s13,s12,s10,s1,s4,s6,s7}。很明顯,在此解中無重復(fù)狀態(tài)。這種解符合“維-維”更新機制。更新完每個狀態(tài)之后,更新的新解會是一個14維向量{s4,s7,s8,s11,s13,s8,s5,s12,s13,s10,s1,s8,s12,s9}。

3 改進的多狀態(tài)粒子優(yōu)化算法

改進的多狀態(tài)粒子優(yōu)化算法與傳統(tǒng)多狀態(tài)粒子優(yōu)化算法有相似的準則,但是在新算法中引進了一個基于策略的狀態(tài)轉(zhuǎn)變機制。基于策略的狀態(tài)轉(zhuǎn)變機制從根本上消除了傳統(tǒng)多狀態(tài)粒子優(yōu)化算法的限制,即產(chǎn)生的所有解都是可行的。為了執(zhí)行這種策略,應(yīng)該先知道內(nèi)部狀態(tài)和外部狀態(tài)的所有元素信息,另外,引入一個被選擇的狀態(tài)(用SDS表示),它包括所有被選擇作為下一狀態(tài)的元素。給定h個元素組成的被選擇的狀態(tài)Ti(k,d)=(Ti1((k,d),…,Tih(k.d))),里面所有元素被標記,這是由于之前已經(jīng)被選擇過,所有元素被選擇作為下一狀態(tài)時候是無效的。

對于內(nèi)部和外部狀態(tài),有j個內(nèi)部集合Ii(k,d)=(Ii1((k,d),…,Iij(k.d))),l個外部集合Oi(k,d)=(Oi1((k,d),…,Oil(k.d)))?；诋斍盃顟B(tài)和當前狀態(tài)的更新速度,用公式(5)選擇下一狀態(tài):

(5)

其中,O是空集,Valid_Ii(k,d)=(Ii(k,d)-(Ii(k,d)∩Ti(k,d))),Valid_Oi(k,d)=(Oi(k,d)-(Oi(k,d)∩Ti(k,d)))。隨機從Valid_Ii集合中選擇下一個狀態(tài),如果Valid_Ii中的剩余元素不存在,那么下一狀態(tài)就要隨機的從Valid_Oi中選取。在每個粒子的迭代過程中都需要這個過程,當所有粒子更新完畢,迭代停止。很明顯,從Valid_Ii集合或者從Valid_Ii集合中的SDS和下一狀態(tài)能夠成功產(chǎn)生可行解,因為每個狀態(tài)只有一次機會被選中作為下一個狀態(tài)。

改進的多狀態(tài)粒子優(yōu)化算法偽代碼如下所示:

輸入：I是粒子數(shù)目，D是最大維數(shù)，每個粒子的當前位置si(k，d)(i=1，2，3…，I；d=1，2，3，…，D)，每個粒子的當前速度vi(k+1，d)(i=1，2，3…，I；d=1，2，3，…，D)；粒子個數(shù)初始化為1；repeat初始化SDS的元素個數(shù)；維數(shù)=1；repeat 基于當前狀態(tài)和更新的速度產(chǎn)生一個圓，來確定所有內(nèi)部和外部集合中的元素位置；從內(nèi)部集合中移除所有SDS的元素。if 內(nèi)部集合中還有元素存在；then 從Valid＿Ii集合中選擇任意一個狀態(tài)作為下一個狀態(tài)； 從Valid＿Oi集合中選擇任意一個狀態(tài)作為下一個狀態(tài)； 把被選擇的元素作為SDS中的一個元素； 維度++； Until維度數(shù)=D； 粒子++； Until粒子個數(shù)=I；輸出：產(chǎn)生的可行性解。

4 實驗及分析

實驗環(huán)境:MATLAB R2014b,RAM8.0G,64位windows 8.1操作系統(tǒng),CPU2.2GHz。從TSPLIB中選擇6個TSP標準實例:Burma 14、Ulysses 16、Ulysses 22、Bays 29、Eil 51、Berlin 52。在Eil 51和Berlin 52中的任何2個不同的城市定義為兩個點(u1,q1)和(u2,q2),它們之間的歐氏距離為

(6)

在Burma 14、Ulysses 16、Ulysses 22、Bays 29中的兩個城市也定義為2個點(u1,q1)和(u2,q2),但是這2個點被轉(zhuǎn)化成經(jīng)度和緯度,即(lat1,long1)和(lat2,long2),因此新的距離表達式為

地理距離g_dist可以化為

g_dist=floor((radian·acos(0.5×((1+g1)·g2-(1-g3)×g3))+1))

(11)

其中,floor(·)是把一個小于某個值轉(zhuǎn)化成最大的整數(shù),radian值是6 378.4,acos(·)反余弦函數(shù),g1,g2和g3分別是cos(long1-long2),cos(lat1-lat2)和cos(lat1+lat2)。

為了驗證新算法的有效性,與傳統(tǒng)粒子群算法以及ACPSO[16],ICPSO[17]作比較。參數(shù)設(shè)置:迭代次數(shù)iter=50,粒子個數(shù)par=104,感知系數(shù)與社交系數(shù)c1=c2=2,慣性權(quán)重ω=0.6,隨機數(shù)r1=r2=0.3。其他運行環(huán)境都相同。

解的適應(yīng)度值決定結(jié)果的好壞,運行50次之后,得到均值,最小值,最大值,標準差,誤差,運行時間,如表1所示。

表1 新算法與傳統(tǒng)粒子算法的比較值Tab.1 Comparison between new algorithm and traditional PSO

圖3 誤差比較Fig.3 Error comparison

圖4 運行時間比較Fig.4 Running time comparison

經(jīng)過上面分別對新算法和傳統(tǒng)粒子群算法的誤差曲線與運行時間比較,可以得知,新算法誤差小,而且能在很短時間內(nèi)達到收斂,所以新算法具有很好地優(yōu)化性能。

5 結(jié) 論

針對傳統(tǒng)粒子群算法存在的不足,提出了新的多狀態(tài)粒子群算法,通過引進一個新的策略規(guī)則,避免了不可行解的產(chǎn)生。對于離散組合優(yōu)化問題,這個策略可以對每個粒子直接產(chǎn)生可行解,尤其在TSP問題中,有很好的詮釋,最后通過6種TSP實例來驗證新算法的有效性,結(jié)果表明新算法有較短的收斂時間和較低的誤差。

[ 1 ]殷守林,劉天華,李航. 基于模擬退火算法的卡爾曼濾波在室內(nèi)定位中的應(yīng)用研究[J]. 沈陽師范大學(xué)學(xué)報(自然科學(xué)版), 2015,33(1):86-90.

[ 2 ]胡旺,GARY G Y,張鑫. 基于Pareto熵的多目標粒子群優(yōu)化算法[J]. 軟件學(xué)報, 2014(5):1025-1050.

[ 3 ]胡云清. 求解VRP問題的混沌模擬退火螢火蟲算法[J]. 包裝工程, 2017(7):216-221.

[ 4 ]趙志剛,黃樹運,王偉倩. 基于隨機慣性權(quán)重的簡化粒子群優(yōu)化算法[J]. 計算機應(yīng)用研究, 2014(2):361-363,391.

[ 5 ]段其昌,唐若笠,徐宏英,等. 粒子群優(yōu)化魚群算法仿真分析[J]. 控制與決策, 2013(9):1436-1440.

[ 6 ]YIN S,LIU J,ZHANG Y,et al. Cucuoo Search Algorithm Based on Mobile Cloud Model[J]. Int Innov Comput Inf Control, 2016,12(6):1809-1819.

[ 7 ]吳虎勝,張鳳鳴,吳廬山. 一種新的群體智能算法[J]. 系統(tǒng)工程與電子技術(shù), 2013(11):2430-2438.

[ 8 ]王立國,魏芳潔. 結(jié)合遺傳算法和蟻群算法的高光譜圖像波段選擇[J]. 中國圖象圖形學(xué)報, 2013, 18(2):235-242.

[ 9 ]王春峰,李剛,趙欣. 基于模擬退火算法的VaR-GARCH模型[J]. 系統(tǒng)工程學(xué)報, 2003,18(1):1-7.

[10]KENNEDY J,EBERHART R C. A discrete binary version of the particle swarm algorithm[C]∥Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation, 1997 IEEE International Conference on. IEEE, 1997,5:4104-4108.

[11]MENG L,YIN S,HU X. An improved Mamdani Fuzzy Neural Networks Based on PSO Algorithm and New Parameter Optimization[J]. Indones J Electri Engin Compu Sci, 2015(1):201-206.

[12]SUN Y,YIN S,LIU J. Novel DV-hop Method Based on Krill Swarm Algorithm Used for Wireless Sensor Network Localization[J]. TELKOMNIKA (Telecommunication Computing Electronics and Control), 2016,14(4):1438-1445.

[13]張?zhí)m,聶玉峰. 一種融合差分進化的量子粒子群優(yōu)化算法[J]. 計算機仿真, 2016,33(2):313-316.

[14]劉桂紅,趙亮,孫勁光,等. 一種改進粒子群優(yōu)化算法的Otsu圖像閾值分割方法[J]. 計算機科學(xué), 2016,43(3):309-312.

[15]LIU T,YIN S. An improved particle swarm optimization algorithm used for BP neural network and multimedia course-ware evaluation[J]. Multimedia Tools & Applications, 2016:1-14.

[16]CHANG L Y,MOI S H,LIN Y D,et al. A comparative analysis of chaotic particle swarm optimizations for detecting single nucleotide polymorphism barcodes[J]. Artificial Intelligence in Medicine, 2016,73:23-33.

[17]程畢蕓,魯海燕,黃洋,等. 求解TSP的自適應(yīng)優(yōu)秀系數(shù)粒子群優(yōu)化算法[J]. 計算機應(yīng)用, 2017,37(3):750-754,781.

[18]李文,伍鐵斌,趙全友,等. 改進的混沌粒子群算法在TSP中的應(yīng)用[J]. 計算機應(yīng)用研究, 2015,32(7):2065-2067.