一種改進(jìn)的粒子群算法在交通分配上的應(yīng)用

李曉君,趙曉蕾,趙洪鑾,3,宿夢(mèng)夢(mèng),鄒 煒

(1.山東建筑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山東 濟(jì)南 250101;2.山東建筑大學(xué) 建筑城規(guī)學(xué)院,山東 濟(jì)南 250101;3.天津城建大學(xué) 理學(xué)院,天津 300384)

0 引 言

交通擁堵加劇導(dǎo)致的出行成本大幅提高、交通事故增加、環(huán)境污染和能源消耗等問題愈發(fā)嚴(yán)重,緩解交通擁堵成為當(dāng)下亟待解決的難題。目前緩解交通擁堵的有效途徑是結(jié)合智能交通系統(tǒng)(ITS)智能技術(shù)和動(dòng)態(tài)交通分配(DTA)模型對(duì)交通流量進(jìn)行合理管理和分配。

動(dòng)態(tài)交通分配模型是ITS的核心,交通分配是動(dòng)態(tài)交通分配的基礎(chǔ),其求解常用粒子群算法。粒子群優(yōu)化算法(PSO)是Eberhart和Kennedy[1]基于鳥類的覓食行為提出的一種隨機(jī)搜索算法,是基于群體的啟發(fā)式優(yōu)化算法。粒子群算法在具有原理簡(jiǎn)單、沒有變異等復(fù)雜操作且能應(yīng)用于大多數(shù)優(yōu)化問題的求解等優(yōu)點(diǎn)的同時(shí),也存在迭代后期收斂速度慢、精度低和易陷入局部最優(yōu)等問題。針對(duì)這些問題,研究者設(shè)計(jì)了不同的改進(jìn)策略。Wang等[2]將自適應(yīng)學(xué)習(xí)策略引入粒子群算法,同時(shí)加入潛在預(yù)測(cè)策略來預(yù)測(cè)候選粒子在各個(gè)維度引導(dǎo)種群的能力,以此提高算法的收斂速度;張曉莉等[3]使用神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的非線性作用函數(shù)作為權(quán)重建立模型,提高了算法的穩(wěn)定性及收斂速度;楊紅[4]將天牛須搜索算法與粒子群優(yōu)化算法結(jié)合,并利用Logistic混沌映射對(duì)粒子速度及位置進(jìn)行初始化,有效提高了算法的精度;李榮雨[5]將布谷鳥算法中的萊維飛行策略引入到粒子群算法,利用萊維飛行進(jìn)一步更新個(gè)體的位置,有效提高了算法的優(yōu)化性能;梁田等[6]將基于相似度及聚集度分析的萊維飛行引入粒子群算法,能夠有效幫助粒子逃離局部最優(yōu)。

該文使用舍棄速度項(xiàng)的簡(jiǎn)化粒子群算法對(duì)用戶最優(yōu)的交通分配模型進(jìn)行求解,簡(jiǎn)化的粒子群算法可以有效避免迭代后期速度過于發(fā)散導(dǎo)致的收斂速度慢等問題;同時(shí),使用自適應(yīng)線性慣性權(quán)重來消除粒子慣性分量的不良影響;此外,為了避免迭代后期陷入局部最優(yōu)的問題,通過萊維飛行機(jī)制來改變粒子位置,幫助粒子脫離局部最優(yōu),以此提高算法精度。

1 粒子群算法

1.1 標(biāo)準(zhǔn)粒子群算法

標(biāo)準(zhǔn)粒子群算法的核心是速度和位置更新公式,如式(1)、式(2)所示。

(1)

(2)

Shi等[7]在粒子的速度更新公式中加入慣性因子ω,更改后的公式如式(3)所示。

(3)

隨后,Shi等[8]又更改固定權(quán)重為線性遞減慣性權(quán)重,其給出的慣性權(quán)重公式如式(4)所示。

(4)

式中,ωmax和ωmin分別表示最大和最小加權(quán)系數(shù),經(jīng)實(shí)驗(yàn)確定,慣性權(quán)重取值在[0.4,0.9]上時(shí)算法性能較好,故ωmax一般取0.9,ωmin一般取0.4;tmax表示最大迭代次數(shù),t表示當(dāng)前迭代數(shù)。

標(biāo)準(zhǔn)粒子群算法的步驟如下所述:

Step1:初始化。隨機(jī)初始化粒子速度和位置。

Step3:更新。根據(jù)公式(1)和(2)更新粒子的位置和速度。

Step5:將各個(gè)粒子的適應(yīng)度值與全局最優(yōu)位置gbest的適應(yīng)度值進(jìn)行比較,若有比當(dāng)前最優(yōu)位置gbest好的粒子,即有粒子的適應(yīng)度值要優(yōu)于gbest的適應(yīng)度值,則存儲(chǔ)該粒子位置,并將該粒子的位置作為新的gbest。

Step6:判斷粒子是否達(dá)到最優(yōu)或是否達(dá)到最大迭代次數(shù),若達(dá)到條件,則終止迭代,否則執(zhí)行Step3。

1.2 簡(jiǎn)化的粒子群算法

胡旺等[9]提出了簡(jiǎn)化的粒子群算法,算法舍棄了粒子群的速度項(xiàng),僅以粒子的位置項(xiàng)來控制粒子進(jìn)化方向,可以有效避免迭代后期粒子速度過大時(shí)出現(xiàn)的粒子過于發(fā)散的問題,且通過實(shí)驗(yàn)證明,簡(jiǎn)化的粒子群算法更加高效。

式(2)和式(3)簡(jiǎn)化合并后可得到簡(jiǎn)化粒子群算法的位置更新公式,也是該算法的核心公式:

(5)

該文使用簡(jiǎn)化的粒子群算法,同時(shí)引入自適應(yīng)的線性慣性權(quán)重,以此減弱權(quán)重份量對(duì)算法求解質(zhì)量的影響。此外,為了提高粒子群在迭代后期的搜索能力、有效改善或避免粒子群陷入局部最優(yōu),引入萊維飛行策略,通過萊維飛行來改變粒子位置。具體的改進(jìn)策略將在下面的章節(jié)進(jìn)行介紹。

2 粒子群算法改進(jìn)

2.1 自適應(yīng)慣性權(quán)重

在算法迭代前期,慣性權(quán)重應(yīng)取較大值,粒子可以在更大范圍內(nèi)進(jìn)行搜索,以快速確定全局最優(yōu)位置所在區(qū)域;在算法迭代后期,慣性權(quán)重應(yīng)取較小值,通過小范圍內(nèi)的搜索來獲取精度更高的解。因此,權(quán)重呈現(xiàn)在迭代前期保持較大數(shù)值、迭代中期可以迅速遞減且在迭代后期保持較小,即呈“倒S”形變化,是一種比較理想的慣性權(quán)重選取方案。

Sigmoid函數(shù)常被用作神經(jīng)網(wǎng)絡(luò)的激活函數(shù),其定義為:

(6)

Sigmoid函數(shù)是一種典型的S型函數(shù),其圖像如圖1所示。

圖1 Sigmoid函數(shù)

文獻(xiàn)[10-11]使用的非線性動(dòng)態(tài)遞減的慣性權(quán)重和聯(lián)合進(jìn)化離散度的非線性動(dòng)態(tài)自適應(yīng)慣性權(quán)重因子如式(7)、式(8)所示:

(7)

式中,rand為[0,1]間的隨機(jī)數(shù)。

ω=ωmax+(ωmin-ωmax)·

(8)

式中,b表示阻尼因子,一般取值為[0,1],k(t)為種群進(jìn)化離散度參數(shù)。

根據(jù)式(7)、式(8)和Sigmoid函數(shù)對(duì)權(quán)重公式進(jìn)行改進(jìn),改進(jìn)后的公式如式(9)所示:

(9)

式中的系數(shù)通過多次實(shí)驗(yàn)所得,當(dāng)系數(shù)分別為10和5時(shí),權(quán)重ω的變化如圖2所示,滿足對(duì)系數(shù)呈現(xiàn)先大后小的預(yù)期。

迭代2 000次時(shí),權(quán)重ω的變化如圖2所示。

圖2 自適應(yīng)慣性權(quán)重變化曲線

2.2 萊維飛行

萊維飛行是一種服從重尾分布的隨機(jī)游走的過程,它可以用更短的距離和更少的步數(shù)來搜索更大的面積。萊維飛行在優(yōu)化領(lǐng)域應(yīng)用廣泛,當(dāng)算法陷入局部最優(yōu)時(shí),可以用萊維飛行的公式重新調(diào)整粒子的位置來逃離局部最優(yōu)。

萊維飛行軌跡如圖3所示。

圖3 萊維飛行軌跡

基于萊維飛行策略的位置更新公式如式(10)所示。

(10)

式中,a表示步長(zhǎng)因子,其值大于0;?表示點(diǎn)對(duì)點(diǎn)乘法。

目前生成服從萊維分布隨機(jī)數(shù)常用的方法是Mantegna方法,其生成隨機(jī)步長(zhǎng)s的方法如式(11)所示。

(11)

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

為了驗(yàn)證改進(jìn)算法的性能,選擇Sphere、Rastrigin、Griewank和Ackley四個(gè)測(cè)試函數(shù)對(duì)改進(jìn)的算法(SNL-PSO)與權(quán)重固定的粒子群算法、標(biāo)準(zhǔn)粒子群算法和使用非線性隨機(jī)性權(quán)重并引入萊維飛行的粒子群算法進(jìn)行對(duì)比,函數(shù)的取值范圍、理論最優(yōu)解和定義如表1所示。

表1 測(cè)試函數(shù)取值范圍、最優(yōu)值及定義

c1和c2均設(shè)置為2,固定權(quán)重的粒子群算法的權(quán)重值設(shè)置為0.9,維度D設(shè)置為30,粒子種群數(shù)N設(shè)置為80,迭代次數(shù)G設(shè)置為1 000,仿真實(shí)驗(yàn)結(jié)果如表2～表5所示。

表2 Sphere函數(shù)仿真結(jié)果

表3 Rastrigin函數(shù)仿真結(jié)果

表4 Griewank函數(shù)仿真結(jié)果

表5 Ackley函數(shù)仿真結(jié)果

四個(gè)測(cè)試函數(shù)的仿真結(jié)果曲線如圖4所示。

(a)Sphere函數(shù) (b)Rastrigin函數(shù)

從Sphere、Rastrigin、Griewank和Ackley四個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真結(jié)果中可以看出,使用帶有隨機(jī)性慣性權(quán)重并引入萊維飛行機(jī)制的粒子群算法精度有所提升,但收斂度和穩(wěn)定性改動(dòng)不大,而在此基礎(chǔ)上舍棄速度項(xiàng)的粒子算法精度有明顯提升。同時(shí),從四個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真結(jié)果曲線中也不難看出,改進(jìn)后算法的收斂度和穩(wěn)定性也明顯優(yōu)于其他兩種算法。

3 交通分配

3.1 用戶最優(yōu)交通分配模型

基于最優(yōu)控制理論的交通分配模型,根據(jù)交通流量分配目標(biāo)的不同可以分為用戶最優(yōu)模型和系統(tǒng)最優(yōu)模型,前者以出行者的出行成本最小為目標(biāo),后者以系統(tǒng)總成本最小為目標(biāo),由于前者更能反映當(dāng)下出行者擇路行為,該文建立并求解用戶最優(yōu)模型。

用戶最優(yōu)模型數(shù)學(xué)表示如式(12)所示:

(12)

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

3.2.1 仿真案例路網(wǎng)圖

文獻(xiàn)[12-16]分別使用了不同改進(jìn)策略的粒子群算法求解動(dòng)態(tài)交通分配問題,實(shí)驗(yàn)結(jié)果證明相比傳統(tǒng)的數(shù)值算法,粒子群算法有更優(yōu)越的求解性能。該文使用上述的改進(jìn)粒子群算法對(duì)圖5所示的算例進(jìn)行仿真實(shí)驗(yàn)。

圖5 算例模型

圖中僅有(1,12)一個(gè)OD對(duì),共十條路徑,路段上的數(shù)字表示車流量為0時(shí)在該路段的運(yùn)行時(shí)間,路徑的集合可用如下的矩陣表示:

(13)

使用經(jīng)典BPR阻抗函數(shù)作為路段阻抗函數(shù),其公式如下:

(14)

3.2.2 仿真結(jié)果

當(dāng)總交通流量為2 000時(shí),分別使用標(biāo)準(zhǔn)粒子群算法和改進(jìn)后算法進(jìn)行交通分配得到的各個(gè)路徑上的分配結(jié)果如表6所示。

表6 交通量分配結(jié)果

分配后得到的各個(gè)路徑上的阻抗時(shí)間如圖6所示。

圖6 各個(gè)路徑上的阻抗時(shí)間

由圖6可以看出,改進(jìn)后的粒子群算法的分配曲線波動(dòng)更小,更加平緩,且多數(shù)路徑上的阻抗時(shí)間都有所降低。

由表6可得,相對(duì)于標(biāo)準(zhǔn)的粒子群算法,改進(jìn)后的粒子群算法對(duì)各個(gè)路徑上的車輛分配更加均衡,且各個(gè)路徑上的時(shí)間波動(dòng)相比較于標(biāo)準(zhǔn)的粒子群算法更加穩(wěn)定,可以有效避免某個(gè)路徑上車輛過多而導(dǎo)致車輛擁堵現(xiàn)象的發(fā)生。實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)后的算法在交通分配上的可行性和有效性。

4 結(jié)束語

簡(jiǎn)單介紹了標(biāo)準(zhǔn)粒子群算法和簡(jiǎn)化的粒子群算法,并在簡(jiǎn)化粒子群算法中引入了整體呈現(xiàn)下降趨勢(shì)的帶有隨機(jī)性的慣性權(quán)重和萊維飛行策略,以此來提高算法精度和提高算法的收斂性。通過測(cè)試函數(shù)模擬發(fā)現(xiàn),改進(jìn)后的算法收斂速度更快且解的精度更高。

而后,將改進(jìn)后的算法應(yīng)用于單一OD對(duì)多路徑路網(wǎng)的用戶最優(yōu)模型的求解上。對(duì)于算法中其他參數(shù)初始值的設(shè)置對(duì)算法性能的影響、萊維飛行概率的調(diào)整以及將算法更好地應(yīng)用于大規(guī)模路網(wǎng)上的動(dòng)態(tài)交通分配模型求解上仍需要做進(jìn)一步研究。