張波菲　謝新連　何傲

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

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

中圖分類號(hào)：? U675.73

文獻(xiàn)標(biāo)志碼：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ā)展趨勢(shì)，海上交通環(huán)境越來(lái)越復(fù)雜。同時(shí)，由于需求的增加和沿海城市經(jīng)濟(jì)的快速發(fā)展，海上和沿海區(qū)域的開發(fā)利用（如跨海大橋、海底隧道、海上鉆井平臺(tái)、各類水工設(shè)施等）越來(lái)越頻繁，這就對(duì)船舶通行安全產(chǎn)生了一定的影響。為提高船舶在施工水域通行的安全性，對(duì)通行船舶進(jìn)行智能誘導(dǎo)，使船舶安全地避開施工區(qū)域的障礙物顯得尤為重要。

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

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

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

1.1 Maklink圖

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

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

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

M個(gè)障礙物，第i個(gè)障礙物Oi有n個(gè)頂點(diǎn)，則障礙物Oi可表示為

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

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

1.2 改進(jìn)的Maklink圖

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

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

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

步驟1 選取凹多邊形的一個(gè)頂點(diǎn)，連接與該頂點(diǎn)相鄰的兩個(gè)頂點(diǎn)，如果連線沒(méi)有穿過(guò)凹多邊形，則該頂點(diǎn)為一個(gè)凹頂點(diǎn)，遍歷所有的頂點(diǎn)找出所有的凹頂點(diǎn)。

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

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

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

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

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

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

2 改進(jìn)的CS算法

2.1 CS算法簡(jiǎn)介

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

假設(shè)CS算法中

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

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

式中：α為優(yōu)化問(wèn)題的步長(zhǎng)，通常取0.01;⊕為點(diǎn)對(duì)點(diǎn)乘法;

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

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

式中：

[WTHX]γ[WTBX]為服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)向量，

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

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

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

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

式中：Γ為標(biāo)準(zhǔn)的Gamma函數(shù);β通常取1.5。

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

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

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

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

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

2.2 改進(jìn)的CS算法

2.2.1 指數(shù)型自適應(yīng)步長(zhǎng)

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

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

步長(zhǎng)函數(shù)為

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

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

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

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

3 數(shù)學(xué)建模及算法性能指標(biāo)設(shè)計(jì)

在圖3的基礎(chǔ)上用改進(jìn)的CS算法和其他多種算法進(jìn)行求解比較，首先將Maklink圖中每條鏈接線上的點(diǎn)當(dāng)作變量，設(shè)定解得可行域：

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

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

通過(guò)變量r可以確定鏈接線上節(jié)點(diǎn)的坐標(biāo)，然后用Dijkstra算法計(jì)算得到當(dāng)前從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度，將這個(gè)值作為不同算法的個(gè)體適應(yīng)度值，最后通過(guò)不斷迭代尋優(yōu)得到最優(yōu)路線。

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

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

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

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

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

（2）時(shí)間性能指標(biāo)。定義算法的時(shí)間性能指標(biāo)如下：

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

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

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

4 算例仿真及算法比較

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

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

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

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

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

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

施工水域環(huán)境模型如圖4a所示，即目標(biāo)水域有5片施工水域，其頂點(diǎn)x坐標(biāo)值分別為（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坐標(biāo)值分別為（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。設(shè)置起止點(diǎn)坐標(biāo)分別為（10 m，130 m）、（150 m，50 m）。每種算法實(shí)驗(yàn)10次，記錄每次的結(jié)果以及它們的最小值和平均值，最終結(jié)果見(jiàn)表3。用上文提出的3種算法性能指標(biāo)進(jìn)行分析，結(jié)果見(jiàn)表4。

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

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

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

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

5 結(jié) 論

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

參考文獻(xiàn)：

[1]陳超， 唐堅(jiān). 基于可視圖法的水面無(wú)人艇路徑規(guī)劃設(shè)計(jì)[J].中國(guó)造船， 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]. 中國(guó)航海， 2017， 40（3）： 9-13. DOI： 10.3969/j.issn.1000-4653.2017.03.003.

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

[6]劉春陽(yáng)， 程億強(qiáng)， 柳長(zhǎng)安. 基于改進(jìn)勢(shì)場(chǎng)法的移動(dòng)機(jī)器人避障路徑規(guī)劃[J]. 東南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2009， 39（S1）： 116-120.

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

基金項(xiàng)目：

國(guó)家重點(diǎn)研發(fā)計(jì)劃（ 2017YFC0805309）; 中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金（3132016358）

作者簡(jiǎn)介：

張波菲（1994—），女，河北秦皇島人，碩士研究生，研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理，（E-mail）1063465140@qq.com;

謝新連（1956—），男，遼寧大連人，教授，博導(dǎo)，博士，研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理，（E-mail）xxlian@dlmu.edu.cn