仿生智能算法群橋水域航路規劃應用研究＊

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

（武漢理工大學航運學院1） 內河航運技術湖北省重點實驗室2） 武漢 430063）

0 引 言

仿生智能計算是人工智能領域的一個新興的重要分支，近年來，仿生智能計算無論是在理論還是在應用方面均取得了很多突破性的進展，極大的促進了相關領域研究發展.仿生智能計算是一種模擬自然界生物“優勝劣汰”思想的算法，算法本身具有自適應、自組織和自學習特點，能夠解決傳統計算中難以解決的非線性復雜問題.人工智能算法由于其優越性，逐漸被引入航路規劃研究領域.粒子群、蟻群等智能算法在無人機、機器人、導彈航路規劃問題中表現出了極大的優越性，引起了研究人員的廣泛關注.本文在介紹粒子群、人工蜂群、人工魚群算法的基礎上，分別運用以上3種仿生智能算法對群橋水域航路規劃問題進行了求解，并對結果進行了對比.

1 仿生智能算法簡介

1.1 PSO算法

PSO算法是由Eberhart博士和Kennedy博士于1995年提出的一種可以實現全局優化的隨機優化算法.PSO算法首先隨機初始化一群粒子，在每次迭代中，粒子通過跟蹤個體極值點和全局最優解，從而求得全局最優值［1－2］.

1.2 ABC算法

ABC算法是由土耳其學者Karaboga提出的一種模擬蜜蜂群體尋找優良蜜源的仿生智能計算方法.ABC算法解的進化由覓食蜂、觀察蜂和偵查蜂3種蜜蜂共同完成［3－4］.

1.3 人工魚群算法

AFSA算法是受魚群行為的啟發，由國內李曉磊博士于2002年提出的一種基于動物行為的群體智能優化算法，其中覓食行為、聚群行為、追尾行為和隨機行為與尋優命題的解決有著較密切的關系［5－6］.

2 群橋水域航路規劃模型

2.1 群橋水域特征簡要分析

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

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

根據群橋水域特征分析可知，橋梁間距小和通航孔交錯是群橋水域主要特征.本文旨在探索不同改進方法的PSO算法在群橋水域航路規劃問題的適應性，因此可以將群橋水域建模為一系列距離較近并且縱向間距相等的圓形多障礙物航行水域.考慮到船舶自身大小，將障礙物半徑按照船舶大小向外拓展，船舶可以看成一個質點.船舶航行時需考慮燃油、障礙物等信息，航路規劃的主要任務就是尋找一條從起始點（xs，ys）到目標點（xf，yf）路徑最短且與障礙物無碰撞的路徑.本文首先將航路規劃問題轉化為D維函數優化問題，見圖1.

圖1 坐標轉換關系圖

在圖1中，將原坐標轉換為以起始點和目標點連線為橫軸的新坐標系X′OY′，θ為坐標系XOY與X′OY′的夾角.轉換關系為

將起始點與目標點連線分為d＋1份，在每個等分點做橫軸的垂線，從起始點到目標點按順序去各垂線上任一點組成一個機器人路徑序列點，用路徑點縱坐標組成的向量y＝ （ys，y1，y2，…，yd，yf）即可確定一條惟一路徑.同時，為了計算方便，將坐標進行量綱一的量化.

本文以路徑最短和障礙物威脅最小為日指標，障礙物威脅最小可參考文獻［8］所采用的威脅計算模型，故目標函數可設為

式中：J為航路跟蹤代價；J1為障礙物威脅代價；J2為航路長度代價，wt為航路上各點威脅代價；wl為每條邊的長度，k為不同航路代價所占得比重，本文取0.5，起始點坐標（5，15），目標點坐標（95，60）.

當船舶沿著航路Lij航行時，N個威脅源對其產生的總威脅代價為

為了簡化計算，把每條邊分成5段，取其中的5個點來計算這條邊所受到的威脅代價，見圖2.若障礙物中心與該邊的距離小于安全半徑，則威脅代價可以按照下式計算.

式中：Lij為連接點i，j邊的長度；d0.1，k為Lij邊上的1／10分點距第k個障礙物中心的距離.

圖2 障礙物威脅代價示意圖

3 模型求解

3.1 PSO算法

設置PSO算法種群數量為30，粒子維數為20，迭代次數為500，對所建立的模型求解3次，選取其中最優的解，結果見圖3、圖4.

由圖3、圖4可知，標準PSO算法航路規劃結果較為理想，規劃航路平滑，不存在突跳點.在100代左右穩定收斂.

圖3 PSO算法航路規劃示意圖

圖4 標準PSO算法收斂曲線圖

3.2 ABC算法

設置種群數量大小為30，維數為20，設置蜜源數量為15，偵查蜂最大探測次數設置為100，最大迭代次數為500，運行3次，取最優解，結果見圖5.

圖5 ABC算法航路規劃示意圖

圖6 ABC算法航路規劃迭代曲線圖

由圖5和圖6可知，ABC算法在求解上述模型時，也能找到最優解，但在實際迭代過程中，容易出現因陷入局部最優解而出現規劃失敗的現象，ABC算法310代開始收斂，400代左右穩定收斂，并且人工蜂群算法收斂速度相對較慢.

3.3 AFSA算法

目前，AFSA算法在求解多維函數極值問題方面應用還較少，但這并不影響AFSA算法具有的對初始值要求低、不需要問題的嚴格機理模型，甚至不需要問題的精確描述就可以求解的特點.為了探索AFSA算法的適應性，本文先對問題維數進行了簡化處理，然后依次增加問題維數，對不同參數組合進行試驗，最終確定了魚群數量30、問題維數20、人工魚個體感知半徑2.5、游動步長設置0.7、擁擠度因子0.5、最大嘗試次數30的參數組合，算法結果見圖7、圖8.

圖7 AFSA算法航路規劃示意圖

圖8 AFSA算法收斂曲線圖

由圖7、圖8可以看出，AFSA算法雖然也能找到全局最優解，但是精度不高；AFSA算法在計算本問題時，其計算速度較慢，完成500次迭代時間大約為30min，并且規劃失敗概率較大；算法在370代左右穩定收斂.

3.4 對比研究

仍然采取上節中各算法的參數取值，同時對3種算法分別運行3次，選取各自最優解進行對比分析，結果見圖9～11.

由圖9、圖11可知，PSO算法在109代左右已經穩定收斂，最優適應值為三者最小，PSO算法無論是在最優適應度值還是在收斂速度方面，其表現都是三者中最優的；ABC算法最優適應度值較AFSA算法略好，但算法在470代才穩定收斂，收斂速度明顯不如PSO算法；AFSA算法在求解成功率方面明顯低于其他2種算法，計算耗時較長，參數較多，參數對算法精度和收斂性影響較大.因此，為了提高算法在航路規劃領域的適應性，ABC算法應該主要考慮對其收斂速度進行優化，AFSA算法應考慮對其計算速度、參數數目和尋優精度方面進行改善.

圖9 智能算法航路規劃對比示意圖

圖10 智能算法最優個體適應度值對比圖

圖11 仿生智能算法收斂速度對比圖

4 結束語

本文介紹了PSO，ABC和AFSA三種仿生智能算法，并針對群橋水域航路規劃問題進行了建模研究，證明三種算法均能運用于航路規劃研究；分析了三種仿生智能算法在解決該類問題時的優缺點，并明確了ABC和AFSA算法后期的優化方向，為群橋水域航路規劃研究提供了新的研究方法.

［1］SCOTT H J.Improving particle swarm optimization path planning through inclusion of flight mechanics［D］.Iowa：Iowa State University，2010.

［2］劉慧卓，楊金孝，王泰然，等.改進粒子群算法在三維航路規劃中的應用［J］.火力與指揮控制，2013（11）：141－143.

［3］楊小東，劉 波.人工蜂群算法加速收斂技術研究［J］.計算機技術與發展，2014（4）：25－28.

［4］GORKEMLI K D，CELAL B O.A comprehensive survey：artificial bee colony （ABC）algorithm and applications［J］.Artificial Intelligence Review，2014（8）：21－57.

［5］王培崇，雷鳳君，錢 旭.改進人工魚群算法及其收斂性分析［J］.科學技術與工程，2013（3）：616－620.

［6］王培崇.人工魚群算法研究綜述［J］.中國民航飛行學院學報，2013（4）：22－26.

［7］羅偉林，甘浪雄，鄒早建.橋墩附近流場分布及對通航船舶的影響［J］.中國航海，2014（1）：66－70.

［8］韓 超，王 贏.一種基于改進PSO的無人機航路規劃方法［J］.艦船電子工程，2014（4）：49－53.