基于混合PSO算法的簡化群橋水域航路規劃研究*

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

(武漢理工大學航運學院 武漢 430063)

基于混合PSO算法的簡化群橋水域航路規劃研究*

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

(武漢理工大學航運學院 武漢 430063)

針對群橋水域航路規劃問題，分析了群橋水域特征，建立了群橋水域航路代價模型，分別運用基于自然選擇的PSO、基于雜交思想的PSO和基于模擬退火的PSO對該問題進行了求解.通過與標準PSO算法規劃結果對比，發現3種混合算法均能快速找到最優解，并且精度較高，得出了3種混合PSO算法在解決群橋水域航路規劃問題方面均優于標準PSO算法的結論.

群橋水域；航路規劃；標準PSO算法；混合PSO算法

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

1 群橋水域航路規劃簡化模型

群橋水域具有橋梁間距小、通航孔交錯、水流變化顯著[3]，以及交通流復雜等特點，船舶操縱難度急劇加大，極易誘發船-橋碰撞、船-船碰撞事故.本文旨在探索3種混合PSO算法對于群橋水域航路規劃問題的適應性，因此可以將群橋水域簡化建模為一系列距離較近并且縱向間距相等的圓形多障礙物航行水域.考慮到船舶自身大小，將障礙物半徑按照船舶大小向外拓展，船舶可以看成一個質點，暫時不考慮船舶操縱性，在后期研究中可以考慮增加船舶操縱性約束條件對最優航路加以約束.船舶航行時需考慮燃油、障礙物等信息，航路規劃的主要任務就是尋找一條從起始點(xs,ys)到目標點(xf,yf)路徑最短且與障礙物無碰撞的路徑.本文首先將航路規劃問題轉化為多維函數優化問題.將原坐標轉換為以起始點和目標點連線為橫軸的新坐標系X′OY′，θ為坐標系XOY與X′OY′的夾角.轉換關系為

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

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

當船舶沿著航路Lij航行時(見圖1)，船舶的航路長度代價J1計算模型為

取相應的路徑點計算產生的礙航代價，N個障礙物對其產生的總礙航代價J2為

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

圖1 障礙物礙航代價示意圖

綜上所述，本文群橋水域航路規劃代價函數可建立為

以船長L為單位，建立坐標系，本文起始點坐標(5，15)，目標點坐標(95，60)，障礙物設置為4座連續橋梁，共計14個橋墩，橋墩中心(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算法航路規劃

2.1 基于雜交思想的PSO算法

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

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

式中：p為0到1之間的隨機數.子代的速度為

設定種群數量為30，粒子維數20，迭代500次，根據實驗，選取權重0.7，雜交比例為0.9，雜交池大小比例為0.2時算法效果較好，求解航路規劃結果如圖2，3所示.

圖2 基于雜交思想的PSO算法航路規劃結果

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

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

2.2 基于自然選擇的PSO算法

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

圖4 基于自然選擇的PSO算法航路規劃結果

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

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

2.3 基于模擬退火的PSO算法

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

在本文中其他2種混合PSO算法設置同樣的種群大小、粒子維數和迭代步數，經過試驗，選擇學習因子2.05和退火常數為0.5組合結果較為理想，航路規劃結果如圖6，7所示.

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

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

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

3 混合PSO算法對比研究

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

圖8 混合PSO航路規劃對比圖

圖9 混合PSO算法收斂曲線對比圖

圖10 混合PSO算法收斂速度

對比上述結果可知，與標準PSO算法相比，3種混合PSO算法無論是在收斂速度還是最優適應度值方面，均表現出了一定的優越性，3種改進算法最優適應度值均優于標準PSO算法，最優適應度值方面，基于雜交思想的PSO算法最優適應度值最小，模擬退火次之；收斂速度方面，模擬退火PSO的收斂速度最快，基于雜交思想的PSO次之.綜合考慮，基于雜交思想的PSO和模擬退火PSO算法結果較為理想.

4 結 束 語

本文對針對群橋水域規劃問題，建立了具有群橋水域的簡化航路規劃模型，運用基于雜交思想、自然選擇思想和模擬退火思想PSO算法分別對模型進行了求解，并對混合PSO算法和標準PSO算法規劃結果和收斂速度進行了對比研究，三種混合PSO算法收斂速度和最優適應度值均優于標準PSO算法，綜合來說，基于雜交思想的PSO算法和基于模擬退火的PSO算法在收斂速度和最優適應度值表現較優，可以考慮應用該兩種方法開展后期研究.

[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]馬瀟瀟，張 寧.蟻群算法在巡航導彈航路規劃中的應用[J].艦船電子工程，2013(3)：38-39,130.

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

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

[5]徐玉杰.粒子群算法的改進及應用[D].南京：南京師范大學，2013.

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

[7]張干清，龔憲生.變量相關情況下基于雜交GA-PSO算法的結構協同優化[J].機械工程學報，2012(15)：113-125.

[8]鄭申海，胡小兵，鄭滿滿，等.改進粒子群和模擬退火混合算法及其應用[J].計算機技術與發展，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

*國家自然科學基金項目(批準號：51109173)、中央高校基本科研業務費專項資金項目(批準號：2013-II-019)資助

U612.1

10.3963/j.issn.2095-3844.2015.03.001

徐言民(1976- )：男，博士，教授，主要研究領域為通航安全保障、船橋防撞、自動控制