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

張波菲　謝新連　何傲

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

關鍵詞：船舶避障; 智能交通; 布谷鳥搜索（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 引 言

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

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

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

1 船舶航行環境建模

1.1 Maklink圖

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

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

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

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

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

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

1.2 改進的Maklink圖

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

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

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

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

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

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

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

步驟5 檢查是否已經遍歷所有的凹頂點，若是則結束，否則返回步驟2。

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

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

2 改進的CS算法

2.1 CS算法簡介

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

假設CS算法中

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

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

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

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

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

式中：

[WTHX]γ[WTBX]為服從標準正態分布的隨機數向量，

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

[WTHX]X[WTBX]（t）i為最優個體時，下一代不會發生改變。

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

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

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

在符合規則（3）的情況下，對被發現的巢穴進行替換稱為隨機遷移，其公式為

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

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

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

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

2.2 改進的CS算法

2.2.1 指數型自適應步長

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

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

步長函數為

式中：α（t）為當前步長;α（t+1）是下一次迭代步長;Tmax為最大迭代次數。可以看出：在算法迭代初期，步長緩慢減小，利于快速搜索，加快迭代速度;在算法迭代后期，步長迅速減小，利于提高解的精度。

2.2.2 線性自適應發現概率

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

式中：P（t）a，i表示經過t次迭代后第i個巢穴被發現的概率;Pa，max和Pa，min分別表示發現概率的最大值和最小值;fi表示當前第i個巢穴的適應度值;fbest和fworst分別表示當前迭代中最好和最壞的適應度值。可以看出，隨著迭代的進行，適應度值越大的個體被發現的概率越小，保證了前期搜索的范圍更大，不容易陷入局部最優解，后期收斂速度減小以便進行局部尋優，易于找到最優解。

3 數學建模及算法性能指標設計

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

式中：r1，r2，…，rn為優化問題的變量;n為優化問題的維數，即路徑節點的總數。

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

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

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

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

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

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

式中：N表示實驗次數;Ci為第i次實驗的結果。EMS指標值越小表示算法波動性越小，優化結果越好。

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

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

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

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

4 算例仿真及算法比較

4.1 改進的CS算法仿真結果

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

構建Maklink環境模型后，在圖3的基礎上進行路徑優化，結果見圖4a。在施工水域環境模型不變的情況下，通過改變起點規劃出另外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條路徑起止點的情況下，改變施工水域環境模型，分別標記為實驗4、5、6，仿真結果見圖4b。

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

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

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

施工水域環境模型如圖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次，記錄每次的結果以及它們的最小值和平均值，最終結果見表3。用上文提出的3種算法性能指標進行分析，結果見表4。

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

也每次收斂到固定值，穩定性較好，但只能得到較優結果而無法得到最優結果。

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

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

5 結 論

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

參考文獻：

[1]陳超， 唐堅. 基于可視圖法的水面無人艇路徑規劃設計[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圖和蟻群算法的航線規劃[J]. 中國航海， 2017， 40（3）： 9-13. DOI： 10.3969/j.issn.1000-4653.2017.03.003.

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

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

[7]郭偉， 秦國選， 王磊， 等. 基于改進人工魚群算法和Maklink圖的機器人路徑規劃[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

基金項目：

國家重點研發計劃（ 2017YFC0805309）; 中央高校基本科研業務費專項資金（3132016358）

作者簡介：

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

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