徐言民 楊 柯 高如江 金 城 陳 敏

(武漢理工大學(xué)航運(yùn)學(xué)院 武漢 430063)

基于混合PSO算法的簡(jiǎn)化群橋水域航路規(guī)劃研究*

徐言民 楊 柯 高如江 金 城 陳 敏

(武漢理工大學(xué)航運(yùn)學(xué)院 武漢 430063)

針對(duì)群橋水域航路規(guī)劃問題，分析了群橋水域特征，建立了群橋水域航路代價(jià)模型，分別運(yùn)用基于自然選擇的PSO、基于雜交思想的PSO和基于模擬退火的PSO對(duì)該問題進(jìn)行了求解.通過與標(biāo)準(zhǔn)PSO算法規(guī)劃結(jié)果對(duì)比，發(fā)現(xiàn)3種混合算法均能快速找到最優(yōu)解，并且精度較高，得出了3種混合PSO算法在解決群橋水域航路規(guī)劃問題方面均優(yōu)于標(biāo)準(zhǔn)PSO算法的結(jié)論.

群橋水域；航路規(guī)劃；標(biāo)準(zhǔn)PSO算法；混合PSO算法

隨著沿江省市經(jīng)濟(jì)的高速發(fā)展，大量跨江橋梁呈集群化建設(shè)，以近距離多橋梁為特征的群橋河段已在多處水域形成.目前，橋梁船撞事故時(shí)有發(fā)生，群橋水域航路規(guī)劃問題研究必要性日益凸顯.現(xiàn)有航路規(guī)劃研究方法種類較多，研究方向主要集中在無(wú)人機(jī)、機(jī)器人、導(dǎo)彈航路規(guī)劃研究領(lǐng)域[1-2]，未涉及群橋水域的船舶航路規(guī)劃問題.本文采用了3種混合PSO算法對(duì)群橋水域航路規(guī)劃問題作了對(duì)比研究，為后期開展群橋水域航路規(guī)劃研究奠定了基礎(chǔ).

1 群橋水域航路規(guī)劃簡(jiǎn)化模型

群橋水域具有橋梁間距小、通航孔交錯(cuò)、水流變化顯著[3]，以及交通流復(fù)雜等特點(diǎn)，船舶操縱難度急劇加大，極易誘發(fā)船-橋碰撞、船-船碰撞事故.本文旨在探索3種混合PSO算法對(duì)于群橋水域航路規(guī)劃問題的適應(yīng)性，因此可以將群橋水域簡(jiǎn)化建模為一系列距離較近并且縱向間距相等的圓形多障礙物航行水域.考慮到船舶自身大小，將障礙物半徑按照船舶大小向外拓展，船舶可以看成一個(gè)質(zhì)點(diǎn)，暫時(shí)不考慮船舶操縱性，在后期研究中可以考慮增加船舶操縱性約束條件對(duì)最優(yōu)航路加以約束.船舶航行時(shí)需考慮燃油、障礙物等信息，航路規(guī)劃的主要任務(wù)就是尋找一條從起始點(diǎn)(xs,ys)到目標(biāo)點(diǎn)(xf,yf)路徑最短且與障礙物無(wú)碰撞的路徑.本文首先將航路規(guī)劃問題轉(zhuǎn)化為多維函數(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è)路徑序列點(diǎn)，用路徑點(diǎn)縱坐標(biāo)組成的向量y=(ys，y1，y2，…，yd，yf)即可確定一條惟一路徑.

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

當(dāng)船舶沿著航路Lij航行時(shí)(見圖1)，船舶的航路長(zhǎng)度代價(jià)J1計(jì)算模型為

取相應(yīng)的路徑點(diǎn)計(jì)算產(chǎn)生的礙航代價(jià)，N個(gè)障礙物對(duì)其產(chǎn)生的總礙航代價(jià)J2為

若障礙物中心與該邊的距離小于安全半徑，則礙航代價(jià)可以按照下式計(jì)算.

圖1 障礙物礙航代價(jià)示意圖

綜上所述，本文群橋水域航路規(guī)劃代價(jià)函數(shù)可建立為

以船長(zhǎng)L為單位，建立坐標(biāo)系，本文起始點(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 混合PSO算法航路規(guī)劃

2.1 基于雜交思想的PSO算法

PSO算法在迭代過程中通過跟蹤個(gè)體極值點(diǎn)和全局最優(yōu)解以達(dá)到求解函數(shù)最優(yōu)值的目標(biāo)[5-6]，借鑒遺傳算法中的雜交概念[7]，在每次迭代中，根據(jù)一定的雜交概率選取指定數(shù)量的粒子放入雜交池內(nèi)，池中的粒子隨機(jī)兩兩雜交，產(chǎn)生同樣數(shù)目的子代粒子(child)，并用子代粒子替換親代粒子(parent).子代位置由父帶位置進(jìn)行算術(shù)交叉得到：

child(x)=p×parent1(x)+(1-p)parent2(x)

式中：p為0到1之間的隨機(jī)數(shù).子代的速度為

設(shè)定種群數(shù)量為30，粒子維數(shù)20，迭代500次，根據(jù)實(shí)驗(yàn)，選取權(quán)重0.7，雜交比例為0.9，雜交池大小比例為0.2時(shí)算法效果較好，求解航路規(guī)劃結(jié)果如圖2，3所示.

圖2 基于雜交思想的PSO算法航路規(guī)劃結(jié)果

圖3 基于雜交思想的PSO算法收斂曲線

根據(jù)圖2和圖3可以看出，基于雜交思想的PSO算法同樣也能實(shí)現(xiàn)群橋水域航路規(guī)劃，并且精度較高，算法在60代左右開始收斂，106代左右穩(wěn)定收斂，穩(wěn)定性較高.

2.2 基于自然選擇的PSO算法

將自然選擇機(jī)理與粒子群算法相結(jié)合得到基于選擇PSO算法，其基本思想是在每次迭代過程中將整個(gè)粒子群按適應(yīng)值排序，用群體中最好的一半粒子的速度和位置替換最差的一半粒子位置和速度，同時(shí)保留原來(lái)每個(gè)個(gè)體所記憶的歷史最優(yōu)值.對(duì)于本文所建立的航路規(guī)劃模型，設(shè)定粒子種群數(shù)量為30，粒子維數(shù)20，迭代500次，結(jié)果如圖4，5所示.

圖4 基于自然選擇的PSO算法航路規(guī)劃結(jié)果

圖5 基于自然選擇的PSO算法收斂曲線

由圖4～5可知，基于自然選擇的PSO算法航路規(guī)劃結(jié)果較為理想，計(jì)算速度較快，能迅速找到最優(yōu)解，算法精度較高，航路較為平滑，算法在75代左右開始收斂，93代左右穩(wěn)定收斂，算法穩(wěn)定性高.

2.3 基于模擬退火的PSO算法

模擬退火算法在搜索過程中具有概率突跳的能力，能夠有效地避免搜索過程陷入局部極小解[8].模擬退火算法在退火過程中不但接受好的解，而且還以一定概率接受差的解，同時(shí)這種概率隨著溫度的下降而減小，最終收斂于全局最優(yōu)解.

在本文中其他2種混合PSO算法設(shè)置同樣的種群大小、粒子維數(shù)和迭代步數(shù)，經(jīng)過試驗(yàn)，選擇學(xué)習(xí)因子2.05和退火常數(shù)為0.5組合結(jié)果較為理想，航路規(guī)劃結(jié)果如圖6，7所示.

圖6 基于模擬退火的PSO算法航路規(guī)劃

圖7 基于模擬退火的PSO算法迭代曲線圖

由圖6，圖7可知，基于模擬退火的PSO算法也能迅速搜索到最優(yōu)解，算法在43代左右開始收斂，87代左右穩(wěn)定收斂于最優(yōu)解，穩(wěn)定性較高.

3 混合PSO算法對(duì)比研究

3種改進(jìn)方法分別借鑒遺傳、自然選擇和模擬退火的思想對(duì)PSO算法內(nèi)部迭代過程中生成下一代粒子的方式進(jìn)行修改，這種改進(jìn)方式并不會(huì)對(duì)標(biāo)準(zhǔn)PSO算法適用性產(chǎn)生影響.為了便于觀察，種群數(shù)量均設(shè)置為30，粒子維數(shù)為20，迭代步數(shù)設(shè)置為500步，將以上3種改進(jìn)方法和標(biāo)準(zhǔn)粒子群算法分別運(yùn)行3次，選擇其中最優(yōu)結(jié)果，對(duì)比情況如圖8，9，10所示.

圖8 混合PSO航路規(guī)劃對(duì)比圖

圖9 混合PSO算法收斂曲線對(duì)比圖

圖10 混合PSO算法收斂速度

對(duì)比上述結(jié)果可知，與標(biāo)準(zhǔn)PSO算法相比，3種混合PSO算法無(wú)論是在收斂速度還是最優(yōu)適應(yīng)度值方面，均表現(xiàn)出了一定的優(yōu)越性，3種改進(jìn)算法最優(yōu)適應(yīng)度值均優(yōu)于標(biāo)準(zhǔn)PSO算法，最優(yōu)適應(yīng)度值方面，基于雜交思想的PSO算法最優(yōu)適應(yīng)度值最小，模擬退火次之；收斂速度方面，模擬退火PSO的收斂速度最快，基于雜交思想的PSO次之.綜合考慮，基于雜交思想的PSO和模擬退火PSO算法結(jié)果較為理想.

4 結(jié) 束 語(yǔ)

本文對(duì)針對(duì)群橋水域規(guī)劃問題，建立了具有群橋水域的簡(jiǎn)化航路規(guī)劃模型，運(yùn)用基于雜交思想、自然選擇思想和模擬退火思想PSO算法分別對(duì)模型進(jìn)行了求解，并對(duì)混合PSO算法和標(biāo)準(zhǔn)PSO算法規(guī)劃結(jié)果和收斂速度進(jìn)行了對(duì)比研究，三種混合PSO算法收斂速度和最優(yōu)適應(yīng)度值均優(yōu)于標(biāo)準(zhǔn)PSO算法，綜合來(lái)說(shuō)，基于雜交思想的PSO算法和基于模擬退火的PSO算法在收斂速度和最優(yōu)適應(yīng)度值表現(xiàn)較優(yōu)，可以考慮應(yīng)用該兩種方法開展后期研究.

[1]ARNE A. BEDNAR N M, REINHARD M R. Improved 3D interpolation-based path planning for a fixed-wing unmanned aircraft[J]. Theory and Applications, 2013:1-13.

[2]馬瀟瀟，張 寧.蟻群算法在巡航導(dǎo)彈航路規(guī)劃中的應(yīng)用[J].艦船電子工程，2013(3)：38-39,130.

[3]羅偉林，甘浪雄，鄒早建.橋墩附近流場(chǎng)分布及對(duì)通航船舶的影響[J].中國(guó)航海，2014(1)：66-70.

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

[5]徐玉杰.粒子群算法的改進(jìn)及應(yīng)用[D].南京：南京師范大學(xué)，2013.

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

[7]張干清，龔憲生.變量相關(guān)情況下基于雜交GA-PSO算法的結(jié)構(gòu)協(xié)同優(yōu)化[J].機(jī)械工程學(xué)報(bào)，2012(15)：113-125.

[8]鄭申海，胡小兵，鄭滿滿，等.改進(jìn)粒子群和模擬退火混合算法及其應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013(7)：26-30.

Study on Ship Route Planning in Multi-bridges Water Area Based on Hybrid PSO Algorithms

XU Yanmin YANG Ke GAO Rujiang JIN Cheng CHEN Min

(SchoolofNavigation,WuhanUniversityofTechnology,Wuhan430063,China)

To solve the problem of ship route planning in multi-bridges water area, the route cost model was established after analyzing the water features. Then, the Hybrid based PSO, Natural Selection based PSO, and Simulated Annealing based PSO algorithm are used to solve the model. It turns out that all of the Hybrid PSO algorithms are better than the standard PSO algorithm, which lays the foundation for the further study on this question.

multi-bridges water area；route planning；PSO；hybrid PSO algorithms

2015-03-20

*國(guó)家自然科學(xué)基金項(xiàng)目(批準(zhǔn)號(hào)：51109173)、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(批準(zhǔn)號(hào)：2013-II-019)資助

U612.1

10.3963/j.issn.2095-3844.2015.03.001

徐言民(1976- )：男，博士，教授，主要研究領(lǐng)域?yàn)橥ê桨踩Ｕ?、船橋防撞、自?dòng)控制