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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

代價(jià)函數(shù)可以定義為城市之間的最短距離,2個(gè)狀態(tài)之間的代價(jià)函數(shù)值是由C(sj(k,d).si(k,d))給定的一個(gè)正數(shù)。在多狀態(tài)粒子優(yōu)化算法中,速度一旦被更新,那么將會(huì)執(zhí)行每個(gè)粒子每一維的當(dāng)前狀態(tài)更新到下一狀態(tài)。令當(dāng)前狀態(tài)是圓心,更新的速度值作為圓的半徑,在圓內(nèi)的任何狀態(tài)都被定義為內(nèi)部狀態(tài)集合的一個(gè)成員。在內(nèi)部狀態(tài)集合中使用公式(4)來隨機(jī)選擇下一個(gè)狀態(tài)。給定內(nèi)部狀態(tài)集合(有j個(gè)要素),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),使用一個(gè)隨機(jī)函數(shù),在更新解階段,方程(4)可能導(dǎo)致一個(gè)重復(fù)的狀態(tài)存在。在具體的一個(gè)迭代過程中,一個(gè)粒子的解由14維向量組成{s5,s3,s14,s11,s2,s8,s9,s13,s12,s10,s1,s4,s6,s7}。很明顯,在此解中無重復(fù)狀態(tài)。這種解符合“維-維”更新機(jī)制。更新完每個(gè)狀態(tài)之后,更新的新解會(huì)是一個(gè)14維向量{s4,s7,s8,s11,s13,s8,s5,s12,s13,s10,s1,s8,s12,s9}。

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

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

對(duì)于內(nèi)部和外部狀態(tài),有j個(gè)內(nèi)部集合Ii(k,d)=(Ii1((k,d),…,Iij(k.d))),l個(gè)外部集合Oi(k,d)=(Oi1((k,d),…,Oil(k.d)))。基于當(dāng)前狀態(tài)和當(dāng)前狀態(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)))。隨機(jī)從Valid_Ii集合中選擇下一個(gè)狀態(tài),如果Valid_Ii中的剩余元素不存在,那么下一狀態(tài)就要隨機(jī)的從Valid_Oi中選取。在每個(gè)粒子的迭代過程中都需要這個(gè)過程,當(dāng)所有粒子更新完畢,迭代停止。很明顯,從Valid_Ii集合或者從Valid_Ii集合中的SDS和下一狀態(tài)能夠成功產(chǎn)生可行解,因?yàn)槊總€(gè)狀態(tài)只有一次機(jī)會(huì)被選中作為下一個(gè)狀態(tài)。

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

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

4 實(shí)驗(yàn)及分析

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

(6)

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

地理距離g_dist可以化為

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

(11)

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

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

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

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

圖3 誤差比較Fig.3 Error comparison

圖4 運(yùn)行時(shí)間比較Fig.4 Running time comparison

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

5 結(jié) 論

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

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

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

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

[ 4 ]趙志剛,黃樹運(yùn),王偉倩. 基于隨機(jī)慣性權(quán)重的簡(jiǎn)化粒子群優(yōu)化算法[J]. 計(jì)算機(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 ]王立國(guó),魏芳潔. 結(jié)合遺傳算法和蟻群算法的高光譜圖像波段選擇[J]. 中國(guó)圖象圖形學(xué)報(bào), 2013, 18(2):235-242.

[ 9 ]王春峰,李剛,趙欣. 基于模擬退火算法的VaR-GARCH模型[J]. 系統(tǒng)工程學(xué)報(bào), 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,聶玉峰. 一種融合差分進(jìn)化的量子粒子群優(yōu)化算法[J]. 計(jì)算機(jī)仿真, 2016,33(2):313-316.

[14]劉桂紅,趙亮,孫勁光,等. 一種改進(jìn)粒子群優(yōu)化算法的Otsu圖像閾值分割方法[J]. 計(jì)算機(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]. 計(jì)算機(jī)應(yīng)用, 2017,37(3):750-754,781.

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