針對群橋水域航路規(guī)劃問題的PSO算法選比研究*

關(guān)宏旭　徐言民　楊　柯　劉　強(qiáng)　王　巖

(武漢理工大學(xué)航運(yùn)學(xué)院　內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室　武漢　430063)

針對群橋水域航路規(guī)劃問題的PSO算法選比研究*

關(guān)宏旭徐言民楊柯劉強(qiáng)王巖

(武漢理工大學(xué)航運(yùn)學(xué)院內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室武漢430063)

摘要：針對群橋水域航路規(guī)劃問題，分析了群橋水域特征，建立了簡化的群橋水域航路代價(jià)模型，分別運(yùn)用標(biāo)準(zhǔn)PSO算法、權(quán)重改進(jìn)PSO和學(xué)習(xí)因子改進(jìn)PSO算法對該問題進(jìn)行求解，并對不同改進(jìn)方法的收斂速度和最優(yōu)適應(yīng)度值進(jìn)行了對比分析，得出了異步變化學(xué)習(xí)因子PSO算法在幾種改進(jìn)策略中表現(xiàn)最優(yōu)的結(jié)論，并應(yīng)用算例進(jìn)行驗(yàn)證，確定了后期深入研究群橋水域航路規(guī)劃問題的方法.

關(guān)鍵詞：群橋水域；航路規(guī)劃；PSO算法；參數(shù)改進(jìn)

關(guān)宏旭(1987- )：男,碩士，助理實(shí)驗(yàn)師，主要研究領(lǐng)域?yàn)橥ê桨踩Ｕ稀⒋瑯蚍雷病⒆詣涌刂?/p>

0引言

隨著沿江省市經(jīng)濟(jì)的高速發(fā)展，大量跨江橋梁呈集群化建設(shè)，以近距離多橋梁為特征的群橋河段已在多處水域形成.2013，2014年武漢、南京長江大橋接連發(fā)生3起橋梁船撞事故，導(dǎo)致船舶沉沒，橋墩受損，群橋水域的形成已經(jīng)對水域通航構(gòu)成了嚴(yán)重威脅.據(jù)統(tǒng)計(jì)，駕引人員失誤是造成橋梁船撞事故的主要原因，因此進(jìn)行群橋水域航路規(guī)劃并最終實(shí)現(xiàn)橋區(qū)船舶自主航行是解決橋梁船撞問題的根本方法.目前航路規(guī)劃研究方法種類較多，研究方向主要集中在無人機(jī)、機(jī)器人、導(dǎo)彈航路規(guī)劃研究領(lǐng)域[1-3]，但未涉及群橋水域的船舶航路規(guī)劃.本文采用粒子群((particleswarmoptimization,PSO)算法及其改進(jìn)方法對群橋水域航路規(guī)劃問題作了初步研究，并對各種改進(jìn)方法進(jìn)行對比分析，確定了后期研究所使用的算法.

1群橋水域航路規(guī)劃模型

1.1群橋水域特征簡要分析

群橋水域通常具有橋梁間距小的特點(diǎn)，以長江武漢段為例，到2015年，60km的江面上將擁有11座跨江大橋，其中白沙洲到天興洲不足23km的武漢江面上就擁有橋梁7座，平均橋梁間隔約3km，橋梁間距較小；由于橋梁跨度、結(jié)構(gòu)不同，不同橋梁通航孔也可能會不在同一軸線；橋梁通常建設(shè)在航道斷面相對狹窄處，可航水域受限制；群橋河段輪渡、汽渡、游船等交通流也會對船舶正常通航造成影響；同時(shí)，由于橋墩挑流作用，群橋水域水流變化較為復(fù)雜[4].綜上所述，群橋水域具有橋梁間距小、通航孔交錯(cuò)、水流變化顯著,以及交通流復(fù)雜等特點(diǎn)，船舶操縱難度急劇加大，極易誘發(fā)船-橋碰撞、船-船碰撞事故.

1.2群橋水域航路規(guī)劃簡化模型

根據(jù)群橋水域特征分析可知，橋梁間距小和通航孔交錯(cuò)是群橋水域主要特征.本文旨在探索不同改進(jìn)方法的PSO算法在群橋水域航路規(guī)劃問題的適應(yīng)性，因此可以將群橋水域建模為一系列距離較近并且縱向間距相等的圓形多障礙物航行水域.考慮到船舶自身大小，將障礙物半徑按照船舶大小向外拓展，船舶可以看成一個(gè)質(zhì)點(diǎn).船舶航行時(shí)需考慮燃油、障礙物等信息，航路規(guī)劃的主要任務(wù)就是尋找一條從起始點(diǎn)(xs,ys)到目標(biāo)點(diǎn)(xf,yf)路徑最短且與障礙物無碰撞的路徑.本文首先將航路規(guī)劃問題轉(zhuǎn)化為D維函數(shù)優(yōu)化問題，將原坐標(biāo)轉(zhuǎn)換為以起始點(diǎn)和目標(biāo)點(diǎn)連線為橫軸的新坐標(biāo)系X′OY′，θ為坐標(biāo)系XOY與X′OY′的夾角.轉(zhuǎn)換關(guān)系為：

將起始點(diǎn)與目標(biāo)點(diǎn)連線分為d+1份，在每個(gè)等分點(diǎn)做橫軸的垂線，從起始點(diǎn)到目標(biāo)點(diǎn)按順序去各垂線上任一點(diǎn)組成一個(gè)機(jī)器人路徑序列點(diǎn)，用路徑點(diǎn)縱坐標(biāo)組成的向量y=(ys，y1，y2，…，yd，yf)即可確定一條惟一路徑.

本文以路徑最短和障礙物威脅最小為指標(biāo)，障礙物威脅最小可按照文獻(xiàn)[5]所采用的威脅計(jì)算模型，故目標(biāo)函數(shù)可設(shè)為

minJ=kJ1+(1-k)J2

式中：J為航路跟蹤代價(jià)；J1為障礙物威脅代價(jià)；J2為航路長度代價(jià)；wt為航路上各點(diǎn)威脅代價(jià)；wl為每條邊的長度;k為不同航路代價(jià)所占得比重，取0.5.

本文為計(jì)算方便，對坐標(biāo)進(jìn)行量綱一的量化處理，初步選定船舶長度為100m，用橫向、縱向距離除以船舶長度即可實(shí)現(xiàn)量綱一的量化.起始點(diǎn)坐標(biāo)(5，15)，目標(biāo)點(diǎn)坐標(biāo)(95，60)，障礙物設(shè)置為4座連續(xù)橋梁，共計(jì)14個(gè)橋墩，橋墩中心(15，15，15，15，55，55，55，55，80，80，80，35，35，35；27，47，67，15，35，55，75，30，55，85，60，35，15)，橋墩安全水域半徑[5，5，5，5，6，6，6，6，8，8，8，7，7，7].

2改進(jìn)PSO算法航路規(guī)劃

2.1權(quán)重改進(jìn)方法及其對比分析

慣性權(quán)重是PSO算法[6-8]最重要的參數(shù)，慣性權(quán)重的大小直接影響PSO算法的全局和局部搜索能力[9]，針對權(quán)重的改進(jìn)，一般有線性遞減權(quán)重、自適應(yīng)權(quán)重和隨機(jī)權(quán)重3種.

1) 線性遞減權(quán)重法在考慮實(shí)際優(yōu)化問題時(shí)，往往希望先采用全局搜索，使搜索空間快速收斂于某一區(qū)域，然后采用局部精細(xì)搜索以獲得高精度的解，因此可以采用線性變化的權(quán)重，讓慣性權(quán)重從最大值線性減小到最小值，慣性權(quán)重隨算法迭代次數(shù)的變化公式為：

式中：wmax，wmin分別為權(quán)重最大和最小值；t為當(dāng)前迭代步數(shù)；tmax為最大迭代步數(shù)，經(jīng)過試驗(yàn)，取ωmax=0.9,ωmin=0.4結(jié)果較為理想.

2) 自適應(yīng)權(quán)重法為了平衡PSO算法的全局搜索能力和局部改良能力，還可采用非線性的動態(tài)慣性權(quán)重系數(shù)公式，其表達(dá)是如下.

式中：wmax，wmin分別為w的最大值和最小值；f為粒子當(dāng)前的目標(biāo)函數(shù)值；favg和fmin分別為當(dāng)前所有微粒的平均目標(biāo)值和最小目標(biāo)值.

3) 隨機(jī)權(quán)重法將標(biāo)準(zhǔn)PSO算法中的w設(shè)定為服從某種隨機(jī)分布的隨機(jī)數(shù)，在進(jìn)化初期接近最好點(diǎn)，隨機(jī)權(quán)重可能產(chǎn)生相對小的w值，加快算法的收斂速度，如果在初期找不到最好點(diǎn)，w線性遞減可能使得算法最終收斂不到此最優(yōu)點(diǎn)，隨機(jī)w可以克服這種局限.隨機(jī)權(quán)重的計(jì)算公式為：

式中：N(0,1)為標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù).

4) 權(quán)重改進(jìn)PSO算法流程權(quán)重改進(jìn)PSO算法與標(biāo)準(zhǔn)PSO算法相比較，都是多出了權(quán)重更新步驟，權(quán)重更新后才更新粒子的速度及位置，其余步驟與標(biāo)準(zhǔn)PSO算法相同.3種權(quán)重改進(jìn)的PSO算法流程圖見圖1.

圖1　權(quán)重改進(jìn)PSO算法流程圖

5) 航路規(guī)劃結(jié)果對比分析對于以上3種改進(jìn)方法，分別運(yùn)行3次，選擇其中最優(yōu)結(jié)果，對比情況見圖2～3.

圖2　權(quán)重改進(jìn)PSO航路規(guī)劃對比圖

圖3　 權(quán)重改進(jìn)PSO算法收斂曲線對比圖

對比上述結(jié)果可知，本文3種權(quán)重改進(jìn)方法都能迅速找到精確解，分別從收斂速度和最優(yōu)適應(yīng)2個(gè)方面進(jìn)行分析，結(jié)果見表1.

表1　權(quán)重改進(jìn)PSO算法優(yōu)化結(jié)果對比

由表1可見，自適應(yīng)權(quán)重變化收斂速度最快，67代即開始收斂；線性權(quán)重遞減方法適應(yīng)度值最優(yōu)，總體來說，3種改進(jìn)方法在解決簡化航路規(guī)劃問題總體差異不是太大，都能迅速找到最優(yōu)解，收斂速度均優(yōu)于標(biāo)準(zhǔn)PSO算法.

2.2學(xué)習(xí)因子改進(jìn)方法及其對比分析

在標(biāo)準(zhǔn)PSO算法中，學(xué)習(xí)因子c1和c2對PSO算法收斂能力影響較大[10]，通常取值2.在實(shí)際應(yīng)用中，常見的學(xué)習(xí)因子變化方案有同步變化和異步變化2種方式.

2) 異步變化學(xué)習(xí)因子2個(gè)學(xué)習(xí)因子在優(yōu)化過程中，其變化不同步，這樣使得在優(yōu)化初始階段，粒子具有較大的自我學(xué)習(xí)能力和較小的社會學(xué)習(xí)能力，加強(qiáng)全局搜索能力，而在優(yōu)化后期，粒子具有較強(qiáng)的社會學(xué)習(xí)能力和較小的自我學(xué)習(xí)能力，有利于收斂到全局最優(yōu)解.學(xué)習(xí)因子的變化公式為

式中：c1,int,c2,int分別為c1和c2的初始值；c1,fin、c2,fin分別為c1和c2的迭代終值，經(jīng)過試驗(yàn)，以下參數(shù)設(shè)置效果較好.

c1,int=2.5，c1,fin=0.5；

c2,int=0.5，c2,fin=2.5.

3) 學(xué)習(xí)因子改進(jìn)PSO算法流程同樣，學(xué)習(xí)因子改進(jìn)PSO算法與標(biāo)準(zhǔn)PSO算法相比較，也只是多出學(xué)習(xí)因子更新的步驟，在學(xué)習(xí)因子更新之后才更新粒子的速度及位置，算法其余步驟與標(biāo)準(zhǔn)PSO算法相同.學(xué)習(xí)因子改進(jìn)的PSO算法流程圖見圖4.

圖4　學(xué)習(xí)因子改進(jìn)PSO算法流程圖

4) 航路規(guī)劃結(jié)果對比分析分別運(yùn)行2種改進(jìn)方法3次，選擇其中最優(yōu)結(jié)果，對比情況見圖5～6.

圖5　學(xué)習(xí)因子改進(jìn)PSO航路規(guī)劃對比圖

圖6　學(xué)習(xí)因子改進(jìn)粒子算法收斂曲線對比圖

對比上述結(jié)果可知，針對本文所要解決的問題，2種改進(jìn)方法都能迅速找到精確解，分別從收斂速度和最優(yōu)適應(yīng)2個(gè)方面進(jìn)行分析，結(jié)果見表2.

表2　學(xué)習(xí)因子改進(jìn)PSO算法優(yōu)化結(jié)果對比

由表2可見，在解決群橋水域航路規(guī)劃問題時(shí)，異步變化學(xué)習(xí)因子PSO算法無論是在收斂速度還是適應(yīng)度值方面都表現(xiàn)出了極大的優(yōu)越性.

3改進(jìn)PSO算法航路規(guī)劃對比

3.1對比結(jié)果分析

進(jìn)過上述論述，針對PSO法權(quán)重、學(xué)習(xí)因子一共有5種改進(jìn)方法，對于這5種改進(jìn)方法，最后再各自運(yùn)行3次，并對結(jié)果進(jìn)行對比分析，規(guī)劃結(jié)果及適應(yīng)度值見圖7～8.

圖7　參數(shù)改進(jìn)PSO航路規(guī)劃對比圖

圖8　參數(shù)改進(jìn)PSO算法收斂曲線對比圖

圖9　參數(shù)改進(jìn)PSO算法適應(yīng)度值及收斂代數(shù)對比

圖9為適應(yīng)度值及收斂代數(shù)對比.由圖9可知，從收斂速度來講，異步學(xué)習(xí)因子、同步學(xué)習(xí)因子、線性權(quán)重PSO算法收斂速度較快；從最優(yōu)適應(yīng)度值來說，異步學(xué)習(xí)因子和線性權(quán)重遞減PSO算法適應(yīng)度值最優(yōu).可以看出，異步學(xué)習(xí)因子變化PSO算法無論是在收斂速度還是適應(yīng)度值方面都表現(xiàn)較為優(yōu)異.

3.2算例分析

異步學(xué)習(xí)因子變化PSO算法在進(jìn)行航路規(guī)劃時(shí)，結(jié)果較為理想，為了驗(yàn)證該結(jié)論，在已建立的模型基礎(chǔ)上，選擇障礙物坐標(biāo)[15 15 15 15 55 55 55 55 35 35 35;7 27 47 67 15 35 55 75 60 35 15]、障礙物安全半徑[5 5 5 5 6 6 6 6 7 7 7]、起點(diǎn)[5,10]和目標(biāo)點(diǎn)[75,65]的數(shù)據(jù)組合，采用異步學(xué)習(xí)因子變化PSO對模型求解，其規(guī)劃結(jié)果及收斂曲線分別見圖10～11.

由圖10～11可知，異步學(xué)習(xí)因子變化PSO算法能夠找到最優(yōu)解，精度較高；算法在23代左右即開始穩(wěn)定收斂，收斂速度較快，表明異步學(xué)習(xí)因子變化PSO算法在解決該類問題時(shí)表現(xiàn)優(yōu)異，證明了本文結(jié)論的正確性.

圖10　異步學(xué)習(xí)因子變化PSO算法航路規(guī)劃示意圖

圖11　異步學(xué)習(xí)因子變化PSO算法收斂曲線

4結(jié)束語

本文分別運(yùn)用PSO權(quán)重和學(xué)習(xí)因子改進(jìn)方法進(jìn)行了群橋水域簡化航路規(guī)劃，并對不同PSO改進(jìn)策略進(jìn)行了對比研究，在收斂速度方面，異步學(xué)習(xí)因子、同步學(xué)習(xí)因子、線性權(quán)重PSO算法收斂速度較快；在最優(yōu)適應(yīng)度值方面，異步學(xué)習(xí)因子變化PSO改進(jìn)適應(yīng)度值最優(yōu)；綜合來講，異步學(xué)習(xí)因子改進(jìn)PSO算法均表現(xiàn)優(yōu)異，并根據(jù)算例對結(jié)論的合理性進(jìn)行了驗(yàn)證，后期可考慮采用該種改進(jìn)方法進(jìn)一步開展群橋水域航路規(guī)劃研究.

參 考 文 獻(xiàn)

[1]HYONDONGO,SEUNGKEUNK,ANTONIOST.Coordinatedroad-networksearchrouteplanningbyateamofUAVs[J].InternationalJournalofSystemsScience，2014, 45(5): 825-840.

[2]ERGEZERH，LEBLEBICIOGLUK.3DPathplanningformultipleuavsformaximuminformationcollection[J].JournalofIntelligent&RoboticSystems，2014, 73(1-4): 737-762.

[3]李紅亮，宋貴寶，曹延杰.多反艦導(dǎo)彈攻擊多目標(biāo)協(xié)同航路規(guī)劃[J].系統(tǒng)工程與電子技術(shù)，2013(10)：2102-2109.

[4]艾萬政，劉虎，丁天明.圓形橋墩紊流范圍數(shù)值研究[J].武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2013(5)：1003-1006.

[5]韓超，王贏. 一種基于改進(jìn)PSO的無人機(jī)航路規(guī)劃方法[J].艦船電子工程，2014(4)：49-53.

[6]徐鶴鳴. 多目標(biāo)粒子群優(yōu)化算法的研究[D]. 上海：上海交通大學(xué)，2013.

[7]黃太安，生佳根，徐紅洋，等.一種改進(jìn)的簡化粒子群算法[J].計(jì)算機(jī)仿真，2013(2)：327-330，335.

[8]吳亞麗，徐麗青.一種基于粒子群算法的改進(jìn)多目標(biāo)文化算法[J].控制與決策，2012(8)：1127-1132.

[9]王俊偉，汪定偉.粒子群算法中慣性權(quán)重的實(shí)驗(yàn)與分析[J].系統(tǒng)工程學(xué)報(bào)，2005(2)：194-198.

[10]畢曉君，劉國安.種群分類粒子群改進(jìn)算法研究[J].哈爾濱工程大學(xué)學(xué)報(bào)，2008(9)：991-996.

中圖法分類號：U612.1

doi:10.3963/j.issn.2095-3844.2015.01.050

收稿日期：2014-11-19

ComparativeStudyonImprovedPSOAlgorithms
toShipRoutePlanninginMulti-bridgesWaterArea
GUANHongxuXUYanminYANGKeLIUQiangWANGYan

(School of Navigation,Wuhan University of Technology,Wuhan 430063,China)

(Hubei Inland Shipping Technology Key Laboratory,Wuhan 430063,China)

Abstract：To solve the problem of ship route planning in multi-bridges water area, the simply route cost model was established after analyzing the water features. Then, the PSO, ω improved PSO and c improved PSO algorithm are used to solve the model. Compared the convergence rates and optimal solutions of different improved PSO algorithms with each other, it concluded that the asynchronous change c PSO algorithm has the best performance, and a numerical example shows that this conclusion is reasonable, which lays the foundation for the further study on this question.

Key words：multi-bridges water area；route planning；PSO；parameters improved

*國家自然科學(xué)基金項(xiàng)目(51109173)、中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2013-Ⅱ-019)資助