基于Maklink圖和布谷鳥搜索算法的施工水域路徑規(guī)劃

張波菲　謝新連　何傲

摘要：為提高船舶在復雜施工水域通行的安全性，提出一種基于Maklink圖和布谷鳥搜索（cuckoo search， CS）算法的船舶路徑規(guī)劃方法。利用改進的Maklink圖構(gòu)建施工水域環(huán)境模型;設置變量參數(shù)并用改進的CS算法對模型進行求解，其中采用基于Dijkstra算法得到的最短路徑長度作為種群個體的適應度值;采用3個衡量算法性能的指標——優(yōu)化性能指標、時間性能指標和動態(tài)性能指標，對多種算法進行分析比較。結(jié)果表明，采用指數(shù)型自適應步長和線性自適應發(fā)現(xiàn)概率對CS算法進行改進，能提高其在路徑規(guī)劃中的搜索效率和迭代速度，并可以保證求出一定精度內(nèi)的近似最優(yōu)解，顯示出該算法的優(yōu)越性。

關(guān)鍵詞：船舶避障; 智能交通; 布谷鳥搜索（CS）算法; 性能指標; 施工水域; Maklink圖

中圖分類號：? U675.73

文獻標志碼：A

Path planning? in construction waters based on Maklink

graph and cuckoo search algorithm

ZHANG Bofei， XIE Xinlian， HE Ao

（Logistics Research Institute， Dalian Maritime University， Dalian 116026， Liaoning， China）

Abstract：

In order to improve the navigation safety of ships in complex construction waters，? a ship path planning method based on the Maklink graph and the cuckoo search （CS） algorithm is proposed. The construction waters environment model is constructed by the improved Maklink graph; the variable parameters are set and the model is solved by the improved CS algorithm. The shortest path length calculated by the Dijkstra algorithm is used as the fitness value of the population individual. Three performance indexes for measuring the algorithm performance are used to analyze and compare many algorithms， where three performance indexes are the optimization performance index， the time performance index and the dynamic performance index， respectively. The results show that the improvement of the CS algorithm by the exponential adaptive step size and the linear adaptive discovery probability can improve its search efficiency and iteration speed in path planning， and can guarantee to obtain the approximate optimal solution within a certain precision， which shows the superiority of the algorithm.

Key words：

ship obstacle avoidance; intelligent transportation; cuckoo search （CS） algorithm; performance index; construction waters; Maklink graph

0 引 言

隨著港口和航道的通航密度迅速增加，船舶呈現(xiàn)大型化、專業(yè)化、高速化的發(fā)展趨勢，海上交通環(huán)境越來越復雜。同時，由于需求的增加和沿海城市經(jīng)濟的快速發(fā)展，海上和沿海區(qū)域的開發(fā)利用（如跨海大橋、海底隧道、海上鉆井平臺、各類水工設施等）越來越頻繁，這就對船舶通行安全產(chǎn)生了一定的影響。為提高船舶在施工水域通行的安全性，對通行船舶進行智能誘導，使船舶安全地避開施工區(qū)域的障礙物顯得尤為重要。

路徑規(guī)劃是船舶智能誘導系統(tǒng)的重要組成部分，其主要目的是在已知船舶準確位置和周圍環(huán)境信息的情況下，尋找出一條從起點到終點的滿足一定要求的航行路徑，使船舶在通行過程中能夠安全可靠地避開所有障礙物并且使路徑盡可能地短。路徑規(guī)劃在機器人領(lǐng)域、航天領(lǐng)域以及船舶避碰領(lǐng)域都有廣泛的應用。根據(jù)被規(guī)劃目標對象對環(huán)境信息掌握的程度不同，可分為全局路徑規(guī)劃和局部路徑規(guī)劃兩種類型。在全局路徑規(guī)劃中，已知全部環(huán)境信息，通常采用路線圖方法（包括可視圖法[1]、Voronoi圖法[2]、Maklink圖法[3]和隨機路線圖法等）或者柵格法構(gòu)建模型，隨后采用啟發(fā)式或智能算法（如蟻群算法[4]（ant colony algorithm， ACA）、遺傳算法[5]（genetic algorithm， GA））求解;在局部路徑規(guī)劃方面，由于（基于傳感器的）環(huán)境信息是未知的，所以通常采用更為簡潔且靈活的人工勢場法[6]。

在路徑規(guī)劃領(lǐng)域，盡管柵格法應用更為廣泛，但相較于Maklink圖法來說，存在復雜環(huán)境下環(huán)境信息存儲量大、精度不高、決策效率低的缺點。因此，本文采取Maklink圖法構(gòu)建環(huán)境模型。在以往的路徑規(guī)劃研究中，對構(gòu)建好的Maklink模型求解方法眾多，有ACA[4]、GA[5]、人工魚群算法[7]（artificial fish swarm algorithm， AFSA）、螢火蟲算法[8]等，但大多存在無法求得最優(yōu)解、求解成功率低、計算時間長等缺點。布谷鳥搜索（cuckoo search， CS）算法[9]模擬了布谷鳥尋巢產(chǎn)卵的行為，具有參數(shù)少、易于實現(xiàn)、尋優(yōu)能力強等特點。本文提出的改進的CS算法可以求解出最優(yōu)解，并且計算時間較短，用于求解路徑規(guī)劃模型有一定的優(yōu)越性。

1 船舶航行環(huán)境建模

1.1 Maklink圖

在進行路徑規(guī)劃時，必須對被規(guī)劃船舶所在的環(huán)境空間進行合理的描述，即環(huán)境建模。

Maklink圖是基于自由空間法的環(huán)境建模方法，它首先把環(huán)境空間內(nèi)的障礙物抽象為二維平面內(nèi)的各種多邊形，然后利用圖論的知識在這個空間內(nèi)建立連通圖，最后在連通圖中完成路徑規(guī)劃。

自由空間法把模型中的障礙物以其頂點表示，對實驗環(huán)境空間進行如下假設：環(huán)境空間內(nèi)存在

M個障礙物，第i個障礙物Oi有n個頂點，則障礙物Oi可表示為

整個環(huán)境可表示為W={B，O1，…，OM}，式中B表示環(huán)境邊界。構(gòu)建的施工水域示意圖見圖1。

隨后進行Maklink圖的構(gòu)建，鏈接線滿足4個條件：（1）鏈接線的兩端必須分別為兩個多邊形障礙物的兩個頂點或者其中一個為障礙物頂點而另一個在環(huán)境邊界上;（2）每個多邊形障礙物的每個頂點的外角都被一條或多條鏈接線分成兩個或多個銳角;（3）鏈接線不能穿越空間內(nèi)的任何障礙物;（4）每個自由凸區(qū)域至少有2條鏈接線作為邊界。

1.2 改進的Maklink圖

Maklink圖本身也有一定的局限性，為此在研究中結(jié)合實際的施工水域通行情況，對Maklink圖進行改進。

首先，用Maklink圖法畫出的航行通道也許并不能滿足通行條件，因此利用船寬對鏈接線的繪制進行限制。在畫當前頂點與所有其他障礙物頂點的連線之前，計算出該頂點與其他障礙物的最短距離，它可能是該點與障礙物某一頂點的連線長度（如圖2a）或者是該點到障礙物某一邊的垂線長度（如圖2b）。當最短距離不能滿足船舶通行條件時，把該區(qū)域設為不可通行區(qū)域，構(gòu)建連通圖時不再連接該連線的中點。

其次，當目標區(qū)域存在凹多邊形時，通常無法畫出正確有效的全局連通圖。事實上，凹多邊形障礙物在海上航行時是時常存在的，尤其存在于復雜的施工水域或者海上捕魚作業(yè)區(qū)。在對凹多邊形進行連通圖構(gòu)建時，可以把凹多邊形劃分為多個凸多邊形，本文給出一種分解凹多邊形的方法：

步驟1 選取凹多邊形的一個頂點，連接與該頂點相鄰的兩個頂點，如果連線沒有穿過凹多邊形，則該頂點為一個凹頂點，遍歷所有的頂點找出所有的凹頂點。

步驟2 選取一個凹頂點，連接該頂點與其他所有不與其相鄰的頂點，按線段長度從小到大排列，組成集合A。

步驟3 選取集合A中的第一條線段，檢查該線段與凸多邊形的頂點產(chǎn)生的兩個內(nèi)角。若2 個內(nèi)角均小于180°，則保留該連線，進入步驟5; 若某個外角大于180°，則將該連線放入該頂點的候選連線集合B中。

步驟4 檢查該頂點的所有候選連線集合B中是否存在外角大于180°的情況。若存在，則返回步驟3;若不存在，則進入步驟5。

步驟5 檢查是否已經(jīng)遍歷所有的凹頂點，若是則結(jié)束，否則返回步驟2。

通過以上方法畫出的連線可以把凹多邊形進行分解，隨后繪制Maklink圖。由于此時分解的凸多邊形是相互連接的，用原有步驟無法畫出可行的連通圖，所以需要適當?shù)乜s小凸多邊形，使其不再相連?？s小方法為對凸多邊形的每條邊進行平移，距離選取為船寬的1/10。此時，凸多邊形之間有著狹窄的通道，但受不可通行區(qū)域的約束，整片多個凸多邊形可以近似為整體的凹多邊形，如圖2c所示。

利用上述方法畫出施工水域的全局連通圖，如圖3所示：點劃線是Maklink線，黑實線為通過相鄰Maklink線的中點連線得到的無向網(wǎng)格圖;在連通圖的右下角是一個分解后的凹多邊形;鏈接線的中點5與7，由于船寬限制未進行連接。

2 改進的CS算法

2.1 CS算法簡介

CS算法是一種元啟發(fā)式算法，于2009年由Yang和Deb提出，通過模擬自然界中布谷鳥繁殖行為來實現(xiàn)迭代搜索，即將自己的蛋產(chǎn)在其他鳥類的巢穴并由宿主負責孵化，這種繁殖方式獨特且有攻擊性。在某些情況下，宿主會發(fā)現(xiàn)巢穴中表現(xiàn)異常的蛋，并會將其拋出或者遺棄該巢穴。為便于描述這種行為，Yang和Deb提出3種規(guī)則：（1）布谷鳥隨機選取一個巢穴產(chǎn)卵，在一個巢穴只產(chǎn)下一個卵;（2）具有最好的卵的巢穴會保留到下一代;（3）巢穴的數(shù)量是固定的，布谷鳥的卵被發(fā)現(xiàn)的概率是Pa，宿主發(fā)現(xiàn)后會拋棄該卵或者拋棄該巢穴，即巢穴以一定概率被取代。

假設CS算法中

[WTHX]X[WTBX]（t）i=（x（t）i1，x（t）i2，…，x（t）in）T表示第i個巢穴在第t代中的位置，n為優(yōu)化問題的維數(shù)即單個解中參數(shù)的個數(shù)。新一代巢穴位置

[WTHX]X[WTBX]（t+1）i由萊維飛行更新，其公式為

式中：α為優(yōu)化問題的步長，通常取0.01;⊕為點對點乘法;

[WTHX]L[WTBX]（λ）為服從參數(shù)λ（1<λ<3）的萊維分布產(chǎn)生的一個隨機搜索向量，經(jīng)過簡化和傅里葉變換后得到的冪次形式的概率密度函數(shù)為

為保證最優(yōu)個體不被替代，對式（2）進行改進：

式中：

[WTHX]γ[WTBX]為服從標準正態(tài)分布的隨機數(shù)向量，

[WTHX]X[WTBX]（t）best是當前所有巢穴中的最優(yōu)個體，因此當

[WTHX]X[WTBX]（t）i為最優(yōu)個體時，下一代不會發(fā)生改變。

為便于計算萊維分布的隨機值，Yang和Deb采用了Mantegna算法來模擬萊維飛行，巢穴位置更新公式為

式中：μ和v為符合正態(tài)分布的隨機數(shù)，μ～N（0，δ2μ），v～N（0，1），其中參數(shù)δμ的計算公式為

式中：Γ為標準的Gamma函數(shù);β通常取1.5。

在符合規(guī)則（3）的情況下，對被發(fā)現(xiàn)的巢穴進行替換稱為隨機遷移，其公式為

式中：r1、r2為服從[0，1]內(nèi)平均分布的隨機變量;

[WTHX]X[WTBX]（t）j、

[WTHX]X[WTBX]（t）k為隨機選中的兩個個體;H為階躍函數(shù)。

CS算法在經(jīng)過萊維飛行和隨機遷移后，評價當前所有巢穴的適應度值，記錄最優(yōu)的個體然后完成一次迭代。萊維飛行和隨機遷移分別代表全局搜索和局部搜索，通過兩者的結(jié)合CS算法可以有效控制種群的多樣性，優(yōu)化效果好。

2.2 改進的CS算法

2.2.1 指數(shù)型自適應步長

在傳統(tǒng)的CS算法中，計算新的巢穴位置用到的步長α是固定的，不會隨著迭代次數(shù)的增加而發(fā)生改變，因此無法平衡迭代過程中的全局搜索與局部搜索，影響搜索效率，導致最終結(jié)果不夠好。為提高搜索效率，得到更優(yōu)的計算結(jié)果，采用自適應步長進行改進。

在搜索初始階段，算法需要大的步長，使種群個體以較大的變化在可行域內(nèi)搜索，從而加強算法的全局搜索能力;而在算法后期階段，應當采用較小的步長，以加強算法的局部搜索能力并且使計算結(jié)果穩(wěn)定收斂。本文采取指數(shù)型自適應步長。首先，引入一個變形的正態(tài)分布函數(shù)：

步長函數(shù)為

式中：α（t）為當前步長;α（t+1）是下一次迭代步長;Tmax為最大迭代次數(shù)?？梢钥闯觯涸谒惴ǖ跗?，步長緩慢減小，利于快速搜索，加快迭代速度;在算法迭代后期，步長迅速減小，利于提高解的精度。

2.2.2 線性自適應發(fā)現(xiàn)概率

發(fā)現(xiàn)概率Pa決定種群個體是否被替換，也影響算法的搜索效率，因此合適的Pa可以有效地提高收斂速度。為使發(fā)現(xiàn)概率隨迭代次數(shù)的增加而減小，并且使適應度值大的個體被發(fā)現(xiàn)的概率小于適應度值小的個體被發(fā)現(xiàn)的概率，本文提出如下發(fā)現(xiàn)概率函數(shù)：

式中：P（t）a，i表示經(jīng)過t次迭代后第i個巢穴被發(fā)現(xiàn)的概率;Pa，max和Pa，min分別表示發(fā)現(xiàn)概率的最大值和最小值;fi表示當前第i個巢穴的適應度值;fbest和fworst分別表示當前迭代中最好和最壞的適應度值?？梢钥闯觯S著迭代的進行，適應度值越大的個體被發(fā)現(xiàn)的概率越小，保證了前期搜索的范圍更大，不容易陷入局部最優(yōu)解，后期收斂速度減小以便進行局部尋優(yōu)，易于找到最優(yōu)解。

3 數(shù)學建模及算法性能指標設計

在圖3的基礎上用改進的CS算法和其他多種算法進行求解比較，首先將Maklink圖中每條鏈接線上的點當作變量，設定解得可行域：

式中：r1，r2，…，rn為優(yōu)化問題的變量;n為優(yōu)化問題的維數(shù)，即路徑節(jié)點的總數(shù)。

隨后任一鏈接線上的節(jié)點坐標可以由其端點坐標（x1，y1）和（x2，y2）確定。該點坐標（x′，y′）可用變量r表示為

通過變量r可以確定鏈接線上節(jié)點的坐標，然后用Dijkstra算法計算得到當前從起點到終點的最短路徑長度，將這個值作為不同算法的個體適應度值，最后通過不斷迭代尋優(yōu)得到最優(yōu)路線。

為定量評估算法的優(yōu)越性，本文提出3種性能指標。

（1）優(yōu)化性能指標。為評估算法的精確度并體現(xiàn)算法的整體搜索能力，采用平均相對誤差EMR作為優(yōu)化性能指標之一。

式中：是算法多次計算結(jié)果的平均值;Ctrue是路徑優(yōu)化問題的實際最優(yōu)值，當最優(yōu)值不能確定時，用已知最優(yōu)值代替。指標EMR衡量了整體優(yōu)化效果：其值越大說明與實際值的差值越大;其值越小說明算法優(yōu)化性能越好，結(jié)果越準確。

為反映算法的波動性，采用均方誤差EMS作為另一個優(yōu)化性能指標：

式中：N表示實驗次數(shù);Ci為第i次實驗的結(jié)果。EMS指標值越小表示算法波動性越小，優(yōu)化結(jié)果越好。

（2）時間性能指標。定義算法的時間性能指標如下：

式中：a為經(jīng)多次實驗得到的算法最終收斂的迭代次數(shù)的平均值;t0為算法迭代一次所需的時間。該指標反映了算法整體的收斂速度。當Tmax相同時，Etime越小表示算法所需時間越少，計算速度越快。

（3）動態(tài)性能指標。為反映算法的動態(tài)性能，即算法內(nèi)部迭代時的收斂情況，本文提出如下動態(tài)性能指標：

式中：C（t）j表示經(jīng)第t次迭代后第j個個體的計算結(jié)果;M表示種群規(guī)模。動態(tài)性能指標實際是將每次迭代過程中單位個體的計算結(jié)果與實際最優(yōu)值之差與當次迭代時間相乘，并進行累計的結(jié)果。該指標越小表示算法在迭代過程中的波動越小，尋優(yōu)速度越快。

4 算例仿真及算法比較

4.1 改進的CS算法仿真結(jié)果

為驗證本文算法在處理施工水域路徑規(guī)劃問題中的有效性，在CPU為Intel core i5-8265u并且內(nèi)存為8 GB的計算機上進行仿真，仿真軟件為MATLAB 2019a。經(jīng)多次仿真后，改進的CS算法的參數(shù)選擇如下：種群大小為20，最大發(fā)現(xiàn)概率為0.5，最小發(fā)現(xiàn)概率為0.25。

構(gòu)建Maklink環(huán)境模型后，在圖3的基礎上進行路徑優(yōu)化，結(jié)果見圖4a。在施工水域環(huán)境模型不變的情況下，通過改變起點規(guī)劃出另外2條路徑，3個起點的坐標分別為（10 m，130 m）、（50 m，160 m）、（20 m，20 m），對應的終點坐標分別為（150 m，50 m）、（160 m，10 m）、（180 m，180 m），分別標記為實驗1、2、3。為進一步驗證算法的準確性，在不改變3條路徑起止點的情況下，改變施工水域環(huán)境模型，分別標記為實驗4、5、6，仿真結(jié)果見圖4b。

記錄規(guī)劃出的路徑長度，再根據(jù)障礙物的頂點計算出實際的最短路徑長度，最終的實驗結(jié)果見表1。由表1可以看出，采用本文改進的算法，每次的實驗結(jié)果可以固定收斂到最優(yōu)值。

4.2 與其他智能算法的比較與分析

為驗證本文算法在處理路徑規(guī)劃問題上的優(yōu)越性，除與傳統(tǒng)的CS算法對比外，還選取模擬退火（simulated annealing， SA）算法、GA、粒子群優(yōu)化（particle swarm optimization， PSO）算法、ACA、免疫算法[10]（immune algorithm， IA）、 AFSA和量子遺傳算法（quantum genetic algorithm， QGA）作為對比算法，每種算法的參數(shù)設置見表2。為更好地對比各算法的優(yōu)劣，將迭代次數(shù)統(tǒng)一設置成100次。在SA算法中通過對溫度值變化的設定，外部迭代次數(shù)也近似為100次。

施工水域環(huán)境模型如圖4a所示，即目標水域有5片施工水域，其頂點x坐標值分別為（10 40 90 40）、（50 110 90）、（140 140 160 190 185）、（10 30 70 60 40）、（130 130 180 180 140 140 180 180），y坐標值分別為（120 140 120 70）、（140 140 125）、（100 140 160 140 100）、（40 90 60 30 20）、（20 80 80 60 60 40 40 20），單位都為m。設置起止點坐標分別為（10 m，130 m）、（150 m，50 m）。每種算法實驗10次，記錄每次的結(jié)果以及它們的最小值和平均值，最終結(jié)果見表3。用上文提出的3種算法性能指標進行分析，結(jié)果見表4。

從表3和表4可以看出：改進的CS算法誤差為0，即每次得到的都是全局最優(yōu)值;CS算法、SA算法和PSO算法表現(xiàn)較好，精確度較高，尤其PSO算法也多次計算出最優(yōu)值，但總體來說穩(wěn)定性較差;ACA

也每次收斂到固定值，穩(wěn)定性較好，但只能得到較優(yōu)結(jié)果而無法得到最優(yōu)結(jié)果。

從單次計算時間看，GA、ACA、CS算法計算速度較快，但從時間性能指標Etime和動態(tài)性能指標Ed 可以得出，GA的收斂性比PSO算法、CS算法和改進的CS算法的收斂性差，且后三者的收斂速度相差無幾，PSO算法略快于改進的CS算法。

總而言之，改進的CS算法在損失一定計算時間和收斂速度的情況下，可以使精度達到最大，求解出全局最優(yōu)值，表現(xiàn)較為優(yōu)秀。

5 結(jié) 論

本文在改進的Maklink圖的基礎上，提出基于布谷鳥搜索（CS）算法的路徑規(guī)劃方法，其中對CS算法進行了指數(shù)型自適應步長和線性自適應發(fā)現(xiàn)概率的改進，增加了算法前期的全局搜索能力和后期的局部搜索能力。將本文提出的算法與其他多種算法進行比較分析，通過優(yōu)化性能指標、時間性能指標、動態(tài)性能指標進行定量分析。實驗結(jié)果顯示，本文提出的算法具有較高的精度且搜索速度較快，具有一定的實用價值和優(yōu)越性。

參考文獻：

[1]陳超， 唐堅. 基于可視圖法的水面無人艇路徑規(guī)劃設計[J].中國造船， 2013， 54（1）： 129-135. DOI： 10.3969/j.issn.1000-4882.2013.01.017.

[2]GOWDA I G， KIRKPATRICK D G， LEE D T， et al. Dynamic Voronoi diagrams[J]. IEEE Transactions on Information Theory， 1983， 29（5）：724-731. DOI： 10.1109/TIT.1983.1056738.

[3]ZHOU Yiye， YAO Dengkai， SUN Qianrui， et al.Maklink graph in conflict-free airline network designing[C]//2016 4th International Conference on Machinery， Materials and Information Technology Applications， Advances in Computer Science Research. Atlantis Press， 2016，71： 385-389. DOI： 10.2991/icmmita-16.2016.180.

[4]陳曉， 戴冉， 陳昌源. 基于Maklink圖和蟻群算法的航線規(guī)劃[J]. 中國航海， 2017， 40（3）： 9-13. DOI： 10.3969/j.issn.1000-4653.2017.03.003.

[5]王飛， 王紅勇. 基于Maklink圖和遺傳算法的改航路徑規(guī)劃方法研究[J]. 交通運輸系統(tǒng)工程與信息， 2014， 14（5）： 154-160. DOI： 10.3969/j.issn.1009-6744.2014.05.023.

[6]劉春陽， 程億強， 柳長安. 基于改進勢場法的移動機器人避障路徑規(guī)劃[J]. 東南大學學報（自然科學版）， 2009， 39（S1）： 116-120.

[7]郭偉， 秦國選， 王磊， 等. 基于改進人工魚群算法和Maklink圖的機器人路徑規(guī)劃[J/OL]. 控制與決策： 1-8[2019-11-11]. DOI： 10.13195/j.kzyjc.2019.0030.

[8]FISTER I，? FISTER I， Jr， YANG Xinshe， et al. A comprehensive review of firefly algorithms[J]. Swarm and Evolutionary Computation， 2013， 13： 34-46. DOI： 10.1016/j.swevo.2013.06.001.

[9]YANG Xinshe， DEB S. Cuckoo search via lévy flights[C]//2009 Proceedings of the World Congress on Nature and Biologically Inspired Computing. IEEE， 2009： 210-214. DOI： 10.1109/NABIC.2009.5393690.

[10]KHAN M T， SILVA C W. Autonomous and robust multi-robot cooperation using an artificial immune system[J]. International Journal of Robotics and Automation， 2012， 27（1）： 60-75. DOI： 10.2316/Journal.206.2012.1.206-3536.

（編輯 趙勉）

收稿日期： 2019-09-20

修回日期： 2020-11-19

基金項目：

國家重點研發(fā)計劃（ 2017YFC0805309）; 中央高?；究蒲袠I(yè)務費專項資金（3132016358）

作者簡介：

張波菲（1994—），女，河北秦皇島人，碩士研究生，研究方向為交通運輸規(guī)劃與管理，（E-mail）1063465140@qq.com;

謝新連（1956—），男，遼寧大連人，教授，博導，博士，研究方向為交通運輸規(guī)劃與管理，（E-mail）xxlian@dlmu.edu.cn