仿生智能算法群橋水域航路規(guī)劃應(yīng)用研究＊

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

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

0 引 言

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

1 仿生智能算法簡介

1.1 PSO算法

PSO算法是由Eberhart博士和Kennedy博士于1995年提出的一種可以實(shí)現(xiàn)全局優(yōu)化的隨機(jī)優(yōu)化算法.PSO算法首先隨機(jī)初始化一群粒子，在每次迭代中，粒子通過跟蹤個(gè)體極值點(diǎn)和全局最優(yōu)解，從而求得全局最優(yōu)值［1－2］.

1.2 ABC算法

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

1.3 人工魚群算法

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

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

2.1 群橋水域特征簡要分析

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

2.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)化問題，見圖1.

圖1 坐標(biāo)轉(zhuǎn)換關(guān)系圖

在圖1中，將原坐標(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）即可確定一條惟一路徑.同時(shí)，為了計(jì)算方便，將坐標(biāo)進(jìn)行量綱一的量化.

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

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

當(dāng)船舶沿著航路Lij航行時(shí)，N個(gè)威脅源對(duì)其產(chǎn)生的總威脅代價(jià)為

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

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

圖2 障礙物威脅代價(jià)示意圖

3 模型求解

3.1 PSO算法

設(shè)置PSO算法種群數(shù)量為30，粒子維數(shù)為20，迭代次數(shù)為500，對(duì)所建立的模型求解3次，選取其中最優(yōu)的解，結(jié)果見圖3、圖4.

由圖3、圖4可知，標(biāo)準(zhǔn)PSO算法航路規(guī)劃結(jié)果較為理想，規(guī)劃航路平滑，不存在突跳點(diǎn).在100代左右穩(wěn)定收斂.

圖3 PSO算法航路規(guī)劃示意圖

圖4 標(biāo)準(zhǔn)PSO算法收斂曲線圖

3.2 ABC算法

設(shè)置種群數(shù)量大小為30，維數(shù)為20，設(shè)置蜜源數(shù)量為15，偵查蜂最大探測次數(shù)設(shè)置為100，最大迭代次數(shù)為500，運(yùn)行3次，取最優(yōu)解，結(jié)果見圖5.

圖5 ABC算法航路規(guī)劃示意圖

圖6 ABC算法航路規(guī)劃迭代曲線圖

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

3.3 AFSA算法

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

圖7 AFSA算法航路規(guī)劃示意圖

圖8 AFSA算法收斂曲線圖

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

3.4 對(duì)比研究

仍然采取上節(jié)中各算法的參數(shù)取值，同時(shí)對(duì)3種算法分別運(yùn)行3次，選取各自最優(yōu)解進(jìn)行對(duì)比分析，結(jié)果見圖9～11.

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

圖9 智能算法航路規(guī)劃對(duì)比示意圖

圖10 智能算法最優(yōu)個(gè)體適應(yīng)度值對(duì)比圖

圖11 仿生智能算法收斂速度對(duì)比圖

4 結(jié)束語

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

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

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

［3］楊小東，劉 波.人工蜂群算法加速收斂技術(shù)研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，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ìn)人工魚群算法及其收斂性分析［J］.科學(xué)技術(shù)與工程，2013（3）：616－620.

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

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

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