多目標(biāo)車輛路徑問題的粒子群優(yōu)化算法研究

郭森,秦貴和,2,張晉東,于赫,盧政宇,于佳欣

(1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,130012,長春;2.吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,130012,長春;3.吉林大學(xué)軟件學(xué)院,130012,長春)

?

多目標(biāo)車輛路徑問題的粒子群優(yōu)化算法研究

郭森1,秦貴和1,2,張晉東1,于赫1,盧政宇1,于佳欣3

(1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,130012,長春;2.吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,130012,長春;3.吉林大學(xué)軟件學(xué)院,130012,長春)

針對(duì)粒子群算法(PSO)及其變種在約束多目標(biāo)等復(fù)雜問題優(yōu)化過程中所遇到的易陷入局部最優(yōu)和收斂性問題,提出了一種基于動(dòng)態(tài)學(xué)習(xí)和突變因子的粒子群算法(DSPSO)。首先,通過分析粒子群群體的學(xué)習(xí)機(jī)制,采用動(dòng)態(tài)的學(xué)習(xí)策略,使粒子自適應(yīng)動(dòng)態(tài)調(diào)整認(rèn)知成分和社會(huì)成分在迭代更新中的權(quán)重,以引導(dǎo)自身向最優(yōu)解的方向探索,有效改善了群體的收斂速度;其次,通過引入階梯突變因子的概念,使粒子在陷入局部最優(yōu)時(shí)進(jìn)行試探跳躍,階梯突變賦予粒子突破更新步長限制的能力,使粒子在當(dāng)前位置速度矢量方向上的二維空間鄰域內(nèi)進(jìn)行試探尋優(yōu),當(dāng)發(fā)現(xiàn)更優(yōu)解時(shí)則跳出當(dāng)前局部最優(yōu);最后,通過在BenchMark基準(zhǔn)函數(shù)測(cè)試集中典型函數(shù)上的實(shí)驗(yàn),證明了DSPSO的求解精度和收斂速度均優(yōu)于對(duì)比算法。在多目標(biāo)車輛路徑問題實(shí)例優(yōu)化中,解的可接受率和成功率分別為0.91和0.66,遠(yuǎn)優(yōu)于對(duì)比算法中最優(yōu)解的0.16和0.11,體現(xiàn)了所提改進(jìn)算法在車輛路徑問題中的優(yōu)越性。

車輛路徑問題;多目標(biāo)優(yōu)化;粒子群

基于群體行為的群體智能算法由于在多向性和全局性等層面的優(yōu)越性,使其對(duì)Pareto非支配解集前沿的形狀和連續(xù)性相對(duì)不敏感,是目前應(yīng)用研究較為理想的隨機(jī)優(yōu)化策略。基于隨機(jī)優(yōu)化技術(shù)的遺傳算法、蟻群算法等多目標(biāo)優(yōu)化算法[1-2]和結(jié)合粒子群算法、神經(jīng)網(wǎng)絡(luò)等機(jī)制的融合算法[3-5],在約束多目標(biāo)求解Pareto最優(yōu)解集中取得了良好的效果。

粒子群算法是1995年由Kennedy等提出的啟發(fā)式方法,最初用來解決連續(xù)解空間上的優(yōu)化問題。隨后,提出了基于離散空間的粒子群優(yōu)化算法(BPSO),并應(yīng)用于0-1規(guī)劃的離散問題上[6]。文獻(xiàn)[7]對(duì)連續(xù)PSO直接離散化,在更新過程中進(jìn)行近似取整,將改進(jìn)的BPSO應(yīng)用于高維整數(shù)規(guī)劃問題,得到了穩(wěn)定性較高的解,且很少產(chǎn)生陷入搜索停滯的情形。文獻(xiàn)[8]將PSO應(yīng)用于多目標(biāo)旅行商(MOTSP)問題中,文獻(xiàn)[9]將PSO用于車輛路徑問題(VRP)的優(yōu)化中,均取得了良好的優(yōu)化結(jié)果。此外,粒子群算法在約束優(yōu)化、動(dòng)態(tài)優(yōu)化、多目標(biāo)優(yōu)化等領(lǐng)域[10-11]都取得了廣泛的研究與應(yīng)用,但是粒子群及其變種算法在解決復(fù)雜問題時(shí)普遍具有收斂性和易陷入局部最優(yōu)的問題。

車輛路徑問題是典型的組合優(yōu)化問題,考慮距離、時(shí)間和費(fèi)用成本等多目標(biāo)約束條件下的車輛路徑優(yōu)化,是一種類多峰問題。本文從分析粒子群算法本身的學(xué)習(xí)機(jī)制入手,通過動(dòng)態(tài)學(xué)習(xí)方式進(jìn)行種群的迭代更新,讓粒子自適應(yīng)調(diào)整更新過程中認(rèn)知成分和社會(huì)成分的比重,并采用突變機(jī)制賦予粒子突破更新步長限制的能力,以跳出局部最優(yōu)解。文中選取其他5種改進(jìn)的粒子群算法作對(duì)比,并通過BenchMark基準(zhǔn)測(cè)試函數(shù)和多目標(biāo)的有容量限制的車輛調(diào)度問題(CVRP)驗(yàn)證了本文改進(jìn)算法的有效性。

1 標(biāo)準(zhǔn)PSO算法

經(jīng)典標(biāo)準(zhǔn)PSO算法[12]中,粒子群中的粒子迭代更新公式為

(1)

式中:ω為經(jīng)典線性模型;pid和pgd分別為粒子群中個(gè)體局部最優(yōu)和全局最優(yōu)位置;c1、c2為學(xué)習(xí)因子常量;r1、r2為兩個(gè)0與1之間的隨機(jī)數(shù);c1r1(pid-xid)、c2r2(pgd-xid)分別為粒子更新過程中的認(rèn)知成分和社會(huì)成分,c1r1、c2r2決定著每個(gè)個(gè)體對(duì)個(gè)體最優(yōu)和全局最優(yōu)的信任程度。當(dāng)c1r1較大時(shí)粒子更加信任個(gè)體極值,受個(gè)體極值的影響較大,將會(huì)更多的向個(gè)體極值靠近,此時(shí)有利于粒子在局部尋優(yōu),提高開發(fā)能力;反之,當(dāng)c2r2較大時(shí)粒子會(huì)更加信任當(dāng)前全局最優(yōu)值,受全局最優(yōu)值影響較大,粒子將會(huì)向全局最優(yōu)值移動(dòng),有利于粒子全局尋優(yōu)過程的進(jìn)行,增強(qiáng)其探索能力,同時(shí)有利于算法的收斂。

2 改進(jìn)PSO算法及VRP問題模型

2.1 改進(jìn)的PSO算法

(2)

(3)

θ0∈[0,1]為一常數(shù),當(dāng)隨機(jī)數(shù)φ大于Pb時(shí),適當(dāng)降低社會(huì)成分在速度更新中的比重,此時(shí)粒子受個(gè)體極值的引導(dǎo)較大,反之則減少認(rèn)知成分在速度更新中的比重,粒子更多向全局最優(yōu)值學(xué)習(xí)。Pb的處理機(jī)制為[14]

(4)

式中:T、t分別為種群最大迭代次數(shù)和當(dāng)前迭代次數(shù),在迭代初期對(duì)學(xué)習(xí)概率影響較大,使得粒子更傾向于向全局最優(yōu)學(xué)習(xí),使群體較快收斂,迭代對(duì)學(xué)習(xí)概率的影響逐漸減小,粒子更多向個(gè)體極值學(xué)習(xí),這有利于種群多樣性的保持;fit(xi)為當(dāng)前解xi的適應(yīng)度計(jì)算函數(shù);h1為粒子當(dāng)前位置適應(yīng)度與全局最優(yōu)位置適應(yīng)度的近似程度;h2為迭代次數(shù)的改變對(duì)學(xué)習(xí)概率的影響;m、n分別取值為0.15和0.30[13]。

本文采用BenchMark基準(zhǔn)函數(shù)測(cè)試集中的典型函數(shù)來測(cè)試常量θ0的最優(yōu)取值區(qū)間,選取Sphere、Rosenbrock兩個(gè)單峰函數(shù)及Restrigin、Schwefel兩個(gè)多峰函數(shù),將學(xué)習(xí)因子常量θ0在區(qū)間[0,1]中均勻取11組值,分別執(zhí)行100次,得到4個(gè)測(cè)試函數(shù)上的平均運(yùn)行結(jié)果,如圖1所示。

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

(c)Griewank函數(shù) (d)Schwefel函數(shù)圖1 動(dòng)態(tài)學(xué)習(xí)因子常量在測(cè)試函數(shù)中的運(yùn)行結(jié)果

2.1.2 避免陷入局部最優(yōu)解的輔助機(jī)制 由粒子群算法的優(yōu)化機(jī)制可知,粒子在進(jìn)行一步更新后,當(dāng)且僅當(dāng)此次更新后所得解優(yōu)于個(gè)體極值,該解才能被采納,成為新的個(gè)體最優(yōu)值,否則該解對(duì)整個(gè)種群的進(jìn)化無效,粒子將在原個(gè)體極值基礎(chǔ)上重新進(jìn)行一步更新。當(dāng)粒子陷入局部最優(yōu)時(shí),以當(dāng)前的更新步長難以發(fā)現(xiàn)該局部最優(yōu)解以外的全局最優(yōu)解。

本文采用階梯突變的機(jī)制,引入突變因子σ,賦予粒子突破當(dāng)前更新機(jī)制限制的能力。當(dāng)群體陷入局部最優(yōu)時(shí),通過調(diào)整粒子的更新步長和前進(jìn)方向,讓粒子在當(dāng)前個(gè)體最優(yōu)解速度矢量方向上進(jìn)行階梯試探。本文采用調(diào)整權(quán)重因子的方法實(shí)現(xiàn)該突變機(jī)制,當(dāng)發(fā)現(xiàn)種群陷入局部最優(yōu)時(shí),在當(dāng)前迭代數(shù)的基礎(chǔ)上調(diào)整權(quán)重因子w的大小,即

ω=ω±kσ,k=1,2,3,…,n

(5)

式中:σ為突變因子,采用線性慣性權(quán)重模型[12]在當(dāng)前迭代數(shù)下的單步步長;k為突變階梯;n為階梯上限。當(dāng)粒子陷入局部最優(yōu)時(shí),突變階梯k從1開始取值進(jìn)行突變,此時(shí)權(quán)重因子分別進(jìn)行一次正向和反向的突變,并進(jìn)行一次更新過程,若一次突變后仍不能發(fā)現(xiàn)更優(yōu)解,則增大突變階梯值,此時(shí)權(quán)重因子將隨之產(chǎn)生更大幅度的突變,粒子將會(huì)跳向原本正常更新機(jī)制中所不可能行進(jìn)到的位置進(jìn)行尋優(yōu),若在某次突變過程中發(fā)現(xiàn)比當(dāng)前最優(yōu)解更好的解,停止突變,粒子則跳出當(dāng)前局部最優(yōu)位置,行進(jìn)到該突變位置處繼續(xù)尋優(yōu)過程。若突變階梯值達(dá)到上限值n后仍不能跳出當(dāng)前局部最優(yōu)值,終止該突變操作,還原權(quán)重因子到突變前的狀態(tài),將突變階梯值k取為1,繼續(xù)先前迭代過程至迭代數(shù)上限,結(jié)束該尋優(yōu)過程。

2.2 多目標(biāo)的車輛路徑問題

多目標(biāo)優(yōu)化問題可描述為

(6)

式中:x為決策變量;y為目標(biāo)向量;M為約束條件集合所決定的可行解域。

車輛路徑問題是指通過配送中心調(diào)度,為一系列配送點(diǎn)配送貨物,通過合理安排配送路線,達(dá)到最優(yōu)配送的目的,問題描述如下。

有一個(gè)配送中心站,配備有K輛配送車,裝載容量為hk(k=1,2,…,K),有L個(gè)配送點(diǎn)要求配送貨物,各配送點(diǎn)的貨物需求量為ei(i=1,2,…,L),且maxei≤maxhk,求滿足需求的最優(yōu)配送路線。

車輛路徑問題(VRP)比多旅行商(MTSP)問題[14]的約束條件嚴(yán)格,求解復(fù)雜,且具有實(shí)際意義。最優(yōu)配送是指配送路線的最優(yōu)化如距離最短等,本文采用多目標(biāo)模型來處理車輛路徑問題,考慮車輛配送路線中的距離最短、時(shí)間最短和費(fèi)用最少3個(gè)目標(biāo),各目標(biāo)距離、時(shí)間、費(fèi)用的計(jì)算公式為

(7)

(8)

(9)

式中:i為車輛編號(hào);Sei為車輛i在配送任務(wù)中的總路程;j為兩個(gè)配送點(diǎn)間路段的編號(hào);H為路段總數(shù);Leij為i車路線中的j路段長度;Tei為完成i車路線所需的時(shí)間;Veij為i車j路段上的平均行駛速度;weij為i車j路段單位距離的收費(fèi)標(biāo)準(zhǔn);u為單位距離耗油費(fèi)用。

本文建立的多目標(biāo)函數(shù)模型為

miny=f(x)={g1(x),g2(x),g3(x)}

(10)

g1(x)=S;g2(x)=T;g3(x)=Q

(11)

為盡可能減少算法計(jì)算量以降低算法的復(fù)雜度,在計(jì)算最終配送路線的優(yōu)化程度時(shí),采用如下權(quán)重模型[15]統(tǒng)一各目標(biāo)值量綱

(12)

式中:G為配送路線的最終近似度;gi(x)*為第i個(gè)目標(biāo)在單目標(biāo)約束下最優(yōu)配送路線的理想值;ωi為單目標(biāo)所占比重;N為目標(biāo)總數(shù)。G越高,配送路線就越理想。求解DSPSO算法的多目標(biāo)車輛路徑問題fit(x)=G(x),則可得求解過程如下。

開始

2. 初次計(jì)算各粒子的適應(yīng)度;

3. 計(jì)算pbest、gbest并確定多目標(biāo)最終相似度G;

4. loop

5. 計(jì)算學(xué)習(xí)概率Pb;

6. 確定動(dòng)態(tài)學(xué)習(xí)因子對(duì)<θ1,θ2>;

8. 計(jì)算各粒子的適應(yīng)度;

9. 更新各粒子的pbest及最終相似度G′;

10. ifG′>G

11. 更新全局最優(yōu)解gbest并更新G,G=G′;

12. else ifG=G′

13. Forj=1 ton

14. 進(jìn)行一次階梯突變,更新w,重新計(jì)算G′;

15. ifG′>G

16. 更新pbest、gbest、G,G=G′

17. 還原w到突變前的值,終止突變;

18. end if

19. 如果迭代次數(shù)達(dá)最大迭代數(shù),跳出循環(huán);

20. end loop

結(jié)束

3 實(shí)驗(yàn)結(jié)果與分析

3.1 Benchmark測(cè)試函數(shù)

為了檢驗(yàn)本文算法的有效性,采用Benchmark基準(zhǔn)函數(shù)測(cè)試集中的典型函數(shù)進(jìn)行測(cè)試,選取4個(gè)單峰問題函數(shù)和4個(gè)多峰問題函數(shù),如表1所示。實(shí)驗(yàn)環(huán)境為:AMD Athlon處理器,主頻2.70 GHz,2.0 GB內(nèi)存,Win7環(huán)境下搭建Microsoft VS 2013。

實(shí)驗(yàn)中ω采用文獻(xiàn)[12]的經(jīng)典線性模型,遞變區(qū)間為[0.4,0.9],粒子個(gè)體數(shù)為40,函數(shù)維數(shù)為30,動(dòng)態(tài)學(xué)習(xí)因子常量取值0.2,最大迭代數(shù)為10 000,并選取帶慣性權(quán)重的粒子群算法PSO-w[16]、標(biāo)準(zhǔn)PSO算法SPSO[12]、帶收斂因子的PSO算法PSO-x[17]、組合學(xué)習(xí)策略PSO算法CPSO[13]、平均最優(yōu)信息的PSO算法[18]AVGPSO 5種粒子群變體算法進(jìn)行測(cè)試比較。此5種算法與本文改進(jìn)算法參數(shù)設(shè)置一致,每個(gè)算法在每一基準(zhǔn)函數(shù)上分別運(yùn)行60次,統(tǒng)計(jì)各算法在各基準(zhǔn)函數(shù)上運(yùn)行的最優(yōu)值(BR)、標(biāo)準(zhǔn)差(SD)、達(dá)到可接受解的成功次數(shù)(SN)及成功率(SR)等,如表2所示。

表1 8個(gè)維度為30的Benchmark基準(zhǔn)測(cè)試函數(shù)

表2 6種對(duì)比算法在Benchmark測(cè)試函數(shù)上的運(yùn)行結(jié)果

由表2可得,單峰函數(shù)中Noise函數(shù)由于其持續(xù)的擾動(dòng)特性,本文算法無法獲得較為理想的解。AVGPSO算法在迭代初期開始就引入平均信息,而本文算法的動(dòng)態(tài)學(xué)習(xí)引導(dǎo)是一個(gè)逐漸調(diào)整的過程,調(diào)整較緩慢,故在相同迭代數(shù)下AVGPSO優(yōu)于本文算法。在求解精度和穩(wěn)定性上,本文算法明顯優(yōu)于其他對(duì)比算法。

為了檢驗(yàn)各算法的特性,本文采用迭代數(shù)來反映各算法的收斂性,避免由于編程技巧的不同而對(duì)收斂時(shí)所用CPU時(shí)間產(chǎn)生的影響,對(duì)單峰函數(shù)采集各算法在測(cè)試函數(shù)上每迭代200次后的優(yōu)化值,最大迭代數(shù)為4 000,多峰函數(shù)每500次迭代采集一次優(yōu)化結(jié)果,最大迭代次數(shù)為10 000,根據(jù)執(zhí)行60次的平均結(jié)果數(shù)據(jù),在MATLAB上進(jìn)行擬合,收斂性對(duì)比如圖2、3所示。

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

(c)Schwefel P2.22函數(shù) (d)Noise函數(shù)圖2 4個(gè)單峰函數(shù)上各對(duì)比算法的收斂性對(duì)比

(a)Ackley函數(shù) (b)Griewank函數(shù)

(c)Rastrigin函數(shù) (d)Schwefle函數(shù)圖3 4個(gè)多峰函數(shù)上各對(duì)比算法的收斂性對(duì)比

由圖2、3可知,單峰函數(shù)中極值點(diǎn)處即為最優(yōu)解。相比其他對(duì)比算法,本文算法中采用的自適應(yīng)引導(dǎo)能夠使粒子在較少迭代數(shù)內(nèi)求得更好的最優(yōu)解,即使粒子群體更快速收斂到極值點(diǎn)。多峰函數(shù)具有多個(gè)極值點(diǎn),過快的收斂會(huì)因?yàn)樵缡於沽Ｗ酉萑刖植孔顑?yōu)或者跳過全局最優(yōu)位置,本文突變機(jī)制有效增加了種群的多樣性,防止種群陷入局部最優(yōu)而失去全局探索能力,在保證種群收斂的前提下能探索獲得更好的全局最優(yōu)解。

3.2 車輛調(diào)度實(shí)例驗(yàn)證

為了驗(yàn)證本文改進(jìn)算法在多目標(biāo)車輛路徑問題上的處理能力,本文選取VRP數(shù)據(jù)庫中的E-n22-k4實(shí)例,該實(shí)例共有22個(gè)配送點(diǎn),一個(gè)為配送中心(編號(hào)1),其余為待配送點(diǎn),各點(diǎn)坐標(biāo)位置及配送需求如表3所示。

借鑒文獻(xiàn)[9]的編碼機(jī)制,車輛調(diào)度的多目標(biāo)選取為距離S、時(shí)間T和費(fèi)用Q0。為了簡化問題,假定任兩個(gè)配送點(diǎn)間為單一路段,并用該兩點(diǎn)間的歐氏距離代表該路段的長度,得距離矩陣S0。根據(jù)表5中各個(gè)配送點(diǎn)位置坐標(biāo),為了盡可能模擬任意路段本身及其各種屬性的多變性和不確定性,本文采用生成隨機(jī)對(duì)稱矩陣V0、W0和U0的方式,矩陣分別代表S0中各路段上的平均行駛速度、道路收費(fèi)和油耗費(fèi)用,通過式(7)、(8)、(9)、(12)計(jì)算配送路線中的各單目標(biāo)值和最終近似度。

實(shí)驗(yàn)中慣性權(quán)重ω采用文獻(xiàn)[12]的經(jīng)典線性權(quán)重模型,動(dòng)態(tài)學(xué)習(xí)因子常量取值0.2,種群大小為60,迭代數(shù)為200,配送車輛K=4,單車限載容量為6 000,使用本文算法對(duì)各單目標(biāo)進(jìn)行多車單目標(biāo)優(yōu)化,如圖4所示。

(a)無容量車載軌跡圖 (b)有容量車載軌跡圖

(c)時(shí)間最短軌跡圖 (d)費(fèi)用最少軌跡圖圖4 單目標(biāo)優(yōu)化最優(yōu)路徑軌跡圖

各單目標(biāo)最優(yōu)值及最優(yōu)配送路線如下。

距離S:394.433

車1路線:1→12→5→4→2→3→8→1

車2路線:1→17→20→14→1

車3路線:1→13→10→6→7→9→11→1

車4路線:1→16→19→21→22→18→15→1

表3 各配送點(diǎn)坐標(biāo)位置及配送需求

時(shí)間T:5.702

車1路線:1→6→7→2→3→8→10→15→1

車2路線:1→16→19→21→22→18→1

車3路線:1→17→20→14→1

車4路線:1→4→5→9→12→11→13→1

費(fèi)用Q:356.271

車1路線:1→13→15→18→19→21→22→1

車2路線:1→17→20→14→1

車3路線:1→12→3→2→5→4→1

車4路線:1→16→7→9→6→8→10→11→1

上述單目標(biāo)最優(yōu)值為多目標(biāo)優(yōu)化時(shí)的各單目標(biāo)理想值,對(duì)比5種變種粒子群算法與本文改進(jìn)算法在多目標(biāo)優(yōu)化實(shí)例上的效果。實(shí)驗(yàn)中粒子群種群大小為60,迭代數(shù)為200,配送車輛數(shù)為4,單車載容量為6 000,每個(gè)算法分別運(yùn)行70次,將相似度大于0.5的優(yōu)化結(jié)果稱為可接受解,大于0.6為成功解。分別計(jì)算各算法獲得可接受解與成功解的次數(shù)及最優(yōu)解,可接受率/成功率記為R1/R2,最優(yōu)相似度記為S,最優(yōu)相似度解對(duì)應(yīng)的各單目標(biāo)值(距離/時(shí)間/費(fèi)用)記為B,結(jié)果如表4所示。

表4 各對(duì)比算法在實(shí)例上的運(yùn)行結(jié)果對(duì)比

本文改進(jìn)算法最優(yōu)配送路線如下。

車1路線:1→4→5→9→7→2→3→8→15→1

車2路線:1→12→14→20→22→1

車3路線:1→6→10→11→16→13→1

車4路線:1→18→21→19→17→1

在相同實(shí)驗(yàn)環(huán)境下,各參數(shù)設(shè)置:粒子種群大小為60,迭代數(shù)為100,配送車輛數(shù)為4,車載容量為6 000。將5種對(duì)比算法及本文改進(jìn)算法DSPSO分別在該實(shí)例上運(yùn)行400次,采集每次運(yùn)行所得最終近似度,如圖5～7所示。

(a)PSO-w運(yùn)行結(jié)果 (b)SPSO運(yùn)行結(jié)果圖5 PSO-w和SPSO對(duì)比算法運(yùn)行結(jié)果

(a)PSO-x運(yùn)行結(jié)果 (b)CPSO運(yùn)行結(jié)果圖6 PSO-x和CPSO對(duì)比算法運(yùn)行結(jié)果

(a)AVGPSO運(yùn)行結(jié)果 (b)DSPSO運(yùn)行結(jié)果圖7 AVGPSO和DSPSO的運(yùn)行結(jié)果

由表4可得,本文改進(jìn)算法在可接受率和成功率上優(yōu)于其他對(duì)比算法,且最優(yōu)相似度也遠(yuǎn)優(yōu)于其他對(duì)比算法。對(duì)比圖5～7可得,5種對(duì)比算法相似度聚集在0.1,而本文改進(jìn)算法則較多分布在[0.45,0.85]區(qū)間內(nèi),說明本文改進(jìn)算法在多目標(biāo)優(yōu)化問題中更接近真實(shí)Pareto邊界,體現(xiàn)了在多目標(biāo)優(yōu)化問題上的有效性。

4 結(jié) 論

針對(duì)粒子群及其變種算法易陷入局部最優(yōu)和收斂性問題,本文提出基于動(dòng)態(tài)學(xué)習(xí)策略的粒子群算法。將優(yōu)化過程中的迭代數(shù)和粒子個(gè)體極值與全局極值的近似度相結(jié)合,動(dòng)態(tài)調(diào)整社會(huì)成分和認(rèn)知成分在更新時(shí)的比重,引導(dǎo)粒子發(fā)現(xiàn)更優(yōu)解,有效改善了種群的收斂性。同時(shí),引入階梯突變因子,賦予粒子突破當(dāng)前更新步長的能力,有效避免粒子陷入局部最優(yōu),增強(qiáng)全局尋優(yōu)的能力。

通過Benchmark基準(zhǔn)測(cè)試函數(shù)集中的典型單峰和多峰函數(shù)測(cè)試,結(jié)果表明本文改進(jìn)算法較其他對(duì)比算法有更好的求解精度和穩(wěn)定性,且可在保證收斂的前提下調(diào)節(jié)算法的收斂速度。多目標(biāo)車輛路徑問題的實(shí)驗(yàn)表明,本文算法較其他對(duì)比算法能夠獲得更優(yōu)的配送路線,體現(xiàn)了在CVRP優(yōu)化問題上的良好性能。

[1] YUSUF I, BABA M S, IKSAN N. Applied genetic algorithm for solving rich VRP [J]. Applied Artificial Intelligence, 2014, 28(10): 957-991.

[2] ZHANG Changsheng, YIN Hao, ZHANG Bin. A novel ant colony optimization algorithm for large scale QoS-based service selection problem [J]. Discrete Dynamics in Nature and Society, 2013(6): 1104-1116.

[3] KENNEDY J, EBERHART R C. Particle swarm optimization [M]. Berlin, Germany: Springer, 2010: 760-766.

[4] CHATTERJEE S, SARKAR S, HORE S, et al. Particle swarm optimization trained neural network for structural failure prediction of multistoried RC buildings[M/OL]∥Neural Computing & Applications. [2015-12-12]. http: ∥link. springer. com/article/10.1007/s00521-016-2190-2.

[5] 許榕, 周東, 蔣士正, 等. 自適應(yīng)粒子群神經(jīng)網(wǎng)絡(luò)交通流預(yù)測(cè)模型 [J]. 西安交通大學(xué)學(xué)報(bào), 2015, 49(10): 103-108. XU Rong, ZHOU Dong, JIANG Shizheng, et al. A traffic forecasting model using adaptive particle swarm optimization trained neural network [J]. Journal of Xi’an Jiaotong University, 2015, 49(10): 103-108.

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

[7] PARSOPOULOS K E, VRAHATIS M N. Recent approaches to global optimization problems through particle swarm optimization [J]. Natural Computing, 2002, 1(2): 235-306.

[8] WANG Zutong, GUO Jiansheng, ZHENG Mingfa, et al. Uncertain multiobjective traveling salesman problem [J]. European Journal of Operational Research, 2015, 241(2): 478-489.

[9] LI Ning, ZOU Tong, SUN Debao. Particle swarm optimization for vehicle routing problem [J]. Journal of Systems Engineering, 2005, 19(6): 596-600.

[10]DUAN Peibo, ZHANG Changsheng, ZHANG Bin. A local stability supported parallel distributed constraint optimization algorithm[J/OL]. The Scientific World Journal. [2015-12-10]. http: ∥www. hindawi. com/journals/tswj/2014/734975/abs/.

[11]YIN Hao, ZHANG Changsheng, ZHANG Bin, et al. A hybrid multi-objective discrete particle swarm optimization algorithm for a SLA-aware service composition problem [J]. Mathematical Problems in Engineering, 2014, 89(1): 112-121.

[12]SHI Yuhui, EBERHART R C. Empirical study of particle swarm optimization [C]∥Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 1999: 1945-1950

[13]TAN Guanzheng, BAO Kun, RIMIRU R. A composite particle swarm algorithm for global optimization of multimodal functions [J]. Journal of Central South University, 2014, 21(5): 1871-1880.

[14]LI Jun, SUN Qirui, ZHOU Mengchu, et al. A new multiple traveling salesman problem and its genetic algorithm-based solution [C]∥The 2013 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ, USA: IEEE, 2013: 627-632.

[15]TANG Yaoping, YU Hong, WANG Wenmu, et al. Application of TSP model based multi-objective in Yongzhou city’s tourist routes [J]. Journal of Central South University of Forestry & Technology, 2011(10): 154-157.

[16]SHI Yuhui, EBERHART R C. A modified particle swarm optimizer [C]∥The IEEE International Conference on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 1998: 69-73.

[17]CLERC M. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization [C]∥Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 1999: 1951-1957.

[18]LI Zhuangkuo, MA Yannan, LIU Liang. Particle swarm optimization based on the average optimal information for vehicle routing problem [C]∥The 6th International Symposium on Computational Intelligence and Design. Piscataway, NJ, USA: IEEE, 2013: 51-54.

(編輯 趙煒)

A Novel Particle Swarm Optimization for Multi-Objective Vehicle Routing Problem

GUO Sen1,QIN Guihe1,2,ZHANG Jindong1,YU He1,LU Zhengyu1,YU Jiaxin3

(1. College of Computer Science and Technology, Jilin University, Changchun 130012, China; 2. Symbol Computation and Knowledge Engineer of Ministry of Education, Jilin University, Changchun 130012, China; 3. College of Software, Jilin University, Changchun 130012, China)

Considering the problems that particle swarm optimization (PSO) algorithm and its variants are easily to fall into local optimal solutions and convergence in the optimization process of complex constrained multi-objective problem, a novel PSO based on dynamic learning strategy and mutation factor (DSPSO) is proposed. First, through analyzing the learning mechanism of particle swarm, DSPSO introduces the dynamic learning strategy, enabling particles to adaptively adjust the weights of cognitive component and social component in the iteration renewal process and guide themselves to explore in the optimal direction, hence effectively accelerating the convergence rate. Second, by introducing the ladder mutation factor, when the particles are trapped in a local optimum, they are enabled to break the limit of update-step size to make tentative jumps in the two-dimensional spatial neighborhood of the velocity vector direction. When a better solution is found, the optimal solution would be updated. Finally, experiments are conducted on the typical functions of BenchMark, and the results show that the accuracy and convergence rate of DSPSO are better than the contrast algorithms. In the multi-objective vehicle routing problem optimization, the acceptable and success rates of the DSPSO solutions are 0.91 and 0.66, respectively, far outperform the results of 0.16 and 0.11 by comparison algorithm, reflecting the superiority of DSPSO in the multi-objective vehicle routing problem.

vehicle routing problem; multi-objective optimization; particle swarm optimization

2016-01-01。 作者簡介:郭森(1991—),男,碩士生;秦貴和(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(51205154);吉林省科技發(fā)展計(jì)劃資助項(xiàng)目(20140520073JH);吉林省重點(diǎn)科技攻關(guān)資助項(xiàng)目(2015020434);中央大學(xué)基礎(chǔ)研究基金資助項(xiàng)目(JCKY-QKJC14)。

時(shí)間:2016-07-14

10.7652/xjtuxb201609016

TP273

A

0253-987X(2016)09-0097-08

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160714.1117.004.html