基于改進(jìn)烏鴉搜索算法的無(wú)人艇新型路徑規(guī)劃策略

林蔚青 林秀芳 陳國(guó)童 黃惠

doi： 10.11835/j.issn.1000-582X.2023.216

收稿日期：2023-03-25

網(wǎng)絡(luò)出版日期：2023-07-19

基金項(xiàng)目：國(guó)家自然科學(xué)青年基金資助項(xiàng)目（52105053）；福建省自然科學(xué)基金資助項(xiàng)目（2022J011125）；閩江學(xué)院人才引進(jìn)資助項(xiàng)目（MJY20029）。

Foundation：Supported by the National Natural Science Youth Foundation of China（52105053）， the Natural Science Foundation of the Science and Technology Department of Fujian Province（2022J011125）， and Talent Introduction Foundation of Minjiang University（MJY20029）.

作者簡(jiǎn)介：林蔚青（1979—），男，高級(jí)工程師，主要從事智能優(yōu)化算法及海洋工程研究，（E-mail）linweiqing2024@163.com。

通信作者：林秀芳，女，副教授，（E-mail）xiufang_lin2010@163.com。

摘要：鑒于無(wú)人艇的實(shí)際航行需求，所規(guī)劃的路徑應(yīng)滿足順滑性和經(jīng)濟(jì)性要求，為此提出一種基于改進(jìn)烏鴉搜索算法和新型路徑擬合方法的路徑規(guī)劃策略。文中提出一種新型路徑擬合方法，用于優(yōu)化轉(zhuǎn)向點(diǎn)的數(shù)量并對(duì)轉(zhuǎn)向點(diǎn)進(jìn)行圓弧過(guò)渡處理，從而縮短路徑長(zhǎng)度，并保證無(wú)人艇在航速穩(wěn)定的情況下實(shí)現(xiàn)轉(zhuǎn)向，在此基礎(chǔ)上提出一種改進(jìn)的烏鴉搜索算法，用于優(yōu)化路徑轉(zhuǎn)向點(diǎn)的位置。算法的改進(jìn)主要體現(xiàn)在3個(gè)方面：采用反向?qū)W習(xí)策略以提高初始種群質(zhì)量及多樣性；提出一種動(dòng)態(tài)變化的意識(shí)概率以提高算法局部和全局的搜索能力；采用萊維飛行策略以改善搜索的方向性和有效性。仿真結(jié)果表明，所提出的新型路徑擬合方法優(yōu)于B樣條曲線擬合方法和直線段擬合方法。迭代計(jì)算和方差分析結(jié)果表明：在優(yōu)化新型擬合路徑方面，所提出的改進(jìn)烏鴉搜索算法相較于標(biāo)準(zhǔn)烏鴉搜索算法、差分進(jìn)化算法和遺傳算法具有更高的收斂精度和魯棒性，能更高效地處理無(wú)人艇路徑規(guī)劃的實(shí)際問題。

關(guān)鍵詞：無(wú)人艇；路徑規(guī)劃；烏鴉搜索算法；反向?qū)W習(xí)；意識(shí)概率

中圖分類號(hào)：TP273????????? 文獻(xiàn)標(biāo)志碼：A??????? ????? 文章編號(hào)：1000-582X（2024）05-087-11

A new path planning strategy for unmanned surface vehicle based on improved crow searching algorithm

LIN Weiqing1， LIN Xiufang2， CHEN Guotong1， HUANG Hui3

（1. College of Information and Mechanical & Electrical Engineering， Ningde Normal University， Ningde， Fujian 352000， P. R. China; 2. College of Physics & Electronic Information Engineering， Minjiang University， Fuzhou 350108， P. R. China; 3. College of Mechanical Engineering and Automation， Fuzhou University， Fuzhou 350108， P. R. China）

Abstract： Becaused of the actual navigation requirements of unmanned surface vehicles， the planned path should meet the criteria of smoothness and economy. Therefore， a novel path planning strategy based on an improved crow search algorithm combining straight lines and circular arc turns is proposed. A new path fitting method is introduced to optimize the number of turning points and address the issue of arc transition at turning points. This method overcomes the problem of frequent direction adjustments caused by B-spline curve paths for unmanned surface vehicles， while ensuring that they can achieve steering while maintaining a stable speed， thereby improving navigation stability and economy. Based on this， an improved crow search algorithm is introduced to optimize the location of path turning points. The improvement of the algorithm is mainly reflected in three aspects： the use of a reverse learning strategy to optimize the quality and the diversity of the initial population， the proposal of a dynamically changing awareness probability to improve the global search ability of the initial segment and the local search ability of the final segment of the algorithm， and the utilization of the Levy flight strategy to improve the directionality and the effectiveness of the search. The simulation results show that the proposed new path fitting method is superior to the B-spline curve fitting method and the straight line segment fitting method. Building on this fitting method， the improved crow search algorithm， the standard crow search algorithm， the differential evolution algorithm， and the genetic algorithm are used to optimize the location of the path turning point. Iterative calculation and variance analysis results demonstrate that the proposed improved crow search algorithm exhibits higher convergence accuracy and robustness compared to the other three algorithms， effectively addressing practical problems in unmanned surface vehicle path planning.

Keywords： unmanned surface vehicle; path planning; crow search algorithm; opposition-based learning; awareness probability

近年來(lái)，無(wú)人艇在科學(xué)考察、海洋監(jiān)測(cè)和國(guó)防維權(quán)等方面的應(yīng)用日漸廣泛，無(wú)人艇的相關(guān)技術(shù)也越來(lái)越受到重視。無(wú)人艇的自動(dòng)駕駛技術(shù)是無(wú)人艇核心技術(shù)之一，它主要包含信息采集、信息處理、自主決策、底層控制和船岸通信等方面內(nèi)容。自主決策主要體現(xiàn)在路徑規(guī)劃上，通過(guò)信息處理和各種數(shù)學(xué)算法生成一條自動(dòng)航行路線，包括路徑信息和航速信息，路徑規(guī)劃不僅關(guān)系到無(wú)人艇的運(yùn)行效率，還影響到無(wú)人艇的航行安全。路徑規(guī)劃已經(jīng)成為無(wú)人艇自動(dòng)駕駛的關(guān)鍵技術(shù)之一，受到了海內(nèi)外眾多學(xué)者的關(guān)注[1]。無(wú)人艇的路徑規(guī)劃主要涉及路徑擬合和路徑點(diǎn)位置的全局規(guī)劃2個(gè)方面的技術(shù)問題。

目前無(wú)人艇路徑基本采用直線段擬合方案[2]和B樣條曲線擬合方案[3]，這2種方案的路徑點(diǎn)分別是直線段轉(zhuǎn)向點(diǎn)和曲線采樣點(diǎn)，其中直線段擬合路徑方案存在折角轉(zhuǎn)彎的問題，即無(wú)人艇在轉(zhuǎn)向點(diǎn)處進(jìn)行轉(zhuǎn)向時(shí)，需提前將航速降為零，再進(jìn)行轉(zhuǎn)向，這無(wú)疑影響無(wú)人艇航行的順滑性和經(jīng)濟(jì)性；而基于B樣條曲線的航行路徑，則需要無(wú)人艇在航行過(guò)程中不停地調(diào)整行駛方向，對(duì)無(wú)人艇的方向定位儀器和自動(dòng)航行裝備的靈敏度和可靠度要求非常高。

對(duì)于路徑點(diǎn)的全局規(guī)劃，傳統(tǒng)算法主要包括可視圖法[4-5]、格柵法[6]、A*算法[7]等?？梢晥D法由于需要不斷重構(gòu)可視圖，存在搜索效率低和組合爆炸等問題[8]。格柵法中的網(wǎng)格大小影響搜索精度，網(wǎng)格太大則精度不足，網(wǎng)格太小則需要比較大的存儲(chǔ)空間，搜索時(shí)間較長(zhǎng)。A*算法可以處理復(fù)雜環(huán)境下的路徑規(guī)劃問題，但存在大量繞彎路徑是該算法的一個(gè)主要問題。隨著智能優(yōu)化算法的提出和廣泛應(yīng)用，有部分學(xué)者已將智能優(yōu)化算法應(yīng)用到無(wú)人艇路徑規(guī)劃中，如粒子群算法[9-11]、遺傳算法[12-14]、灰狼算法[15]等。

烏鴉搜索算法（crow search algorithm，CSA）是由Askarzadeh[16]提出的一種受烏鴉智能行為啟示而產(chǎn)生的群體智能優(yōu)化算法，該算法具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)少和收斂速度快等特點(diǎn)。實(shí)驗(yàn)仿真結(jié)果表明在解決多種工程問題方面，CSA的優(yōu)化結(jié)果優(yōu)于遺傳算法、粒子群算法與和聲搜索算法，已經(jīng)在一些領(lǐng)域取得了較好的應(yīng)用成果。Askarzadeh等[17]使用CSA精確預(yù)測(cè)火力發(fā)電廠的輸入-輸出特性，研究結(jié)果表明CSA的性能優(yōu)于粒子群算法、遺傳算法、蜂群算法和最小二乘法。王麗婷等[18]利用CSA對(duì)支持向量機(jī)進(jìn)行參數(shù)優(yōu)化，仿真結(jié)果表明，與遺傳算法和粒子群算法相比，CSA具有更佳的尋優(yōu)能力和更快的尋優(yōu)速度。然而，由于標(biāo)準(zhǔn)CSA搜索方式過(guò)于簡(jiǎn)單，導(dǎo)致有時(shí)搜索出現(xiàn)算法早熟和收斂精度不足等問題。因此，不少學(xué)者相繼提出了一些CSA的改進(jìn)措施。例如，Lin等[19]針對(duì)建筑物減震控制中的模糊控制器設(shè)計(jì)問題，提出一種實(shí)值和虛值混合編碼的帶變異操作的CSA，證明了這種改進(jìn)CSA的收斂精度和魯棒性都優(yōu)于遺傳算法；劉雪靜等[20]提出了一種二次貪心變異型CSA，并證明了這種改進(jìn)的CSA比二進(jìn)制人工蜂群算法更適合求解聯(lián)盟背包問題；樊英等[21]利用改進(jìn)的二進(jìn)制CSA對(duì)車載網(wǎng)絡(luò)頻譜分配問題進(jìn)行優(yōu)化，結(jié)果表明二進(jìn)制CSA解決了原始CSA收斂速度慢、不穩(wěn)定和易陷入局部最優(yōu)等問題。

雖然CSA及其改進(jìn)算法已在多領(lǐng)域得到成功應(yīng)用，但鮮有將該算法用于無(wú)人艇路徑優(yōu)化方面的研究。文中基于優(yōu)化設(shè)計(jì)的思想，在選中某種優(yōu)化指標(biāo)的基礎(chǔ)上，對(duì)CSA進(jìn)行算法改進(jìn)，用于優(yōu)化無(wú)人艇路徑點(diǎn)的全局規(guī)劃，此外，針對(duì)上述無(wú)人艇路徑擬合方案的缺陷，提出采用直線與圓弧轉(zhuǎn)彎結(jié)合的新型擬合路徑方法，最終形成了一種基于改進(jìn)CSA的無(wú)人艇新型路徑規(guī)劃策略，以期能高效處理無(wú)人艇航行路徑的實(shí)際規(guī)劃問題。

1 新型路徑擬合方法

針對(duì)直線段擬合路徑方案與B樣條曲線擬合路徑方案的缺陷，文中所提出的新型擬合路徑擬合方法在轉(zhuǎn)向點(diǎn)處將采用圓弧轉(zhuǎn)向路徑，以解決折角轉(zhuǎn)彎造成的速度損失問題；在非轉(zhuǎn)向部分路徑則采用直線段擬合，以解決曲線路徑帶來(lái)的頻繁轉(zhuǎn)向問題；對(duì)轉(zhuǎn)向點(diǎn)進(jìn)行優(yōu)化處理，以減少無(wú)人艇變向次數(shù)。

步驟1：按路徑點(diǎn)形成初始路徑（S， P1， P2， …， Pn-1， G）。黑色區(qū)域?yàn)檎系K物，如圖1所示，P1、P2、P3、P4、P5、P6、P7為路徑轉(zhuǎn)向點(diǎn)。

步驟2：優(yōu)化路徑轉(zhuǎn)向點(diǎn)。由于存在部分多余的轉(zhuǎn)向點(diǎn)，故需從起始點(diǎn)開始依次與后續(xù)轉(zhuǎn)向點(diǎn)進(jìn)行連線，直至與障礙物干涉。如圖2中的線段SP4與障礙物干涉了，此時(shí)應(yīng)將前一點(diǎn)P3作為新的第二個(gè)轉(zhuǎn)向點(diǎn)，如圖3所示；接下來(lái)將作為新的起點(diǎn)，重新與后續(xù)轉(zhuǎn)向點(diǎn)進(jìn)行連線，直至與障礙物干涉，如圖4中的線段，此時(shí)則將前一點(diǎn)P5作為新第二個(gè)轉(zhuǎn)向點(diǎn)所示，以此類推，最后得到新的路徑，見圖5所示。

步驟3：將新的轉(zhuǎn)向點(diǎn)進(jìn)行圓弧過(guò)渡，依據(jù)推薦的無(wú)人艇的轉(zhuǎn)彎半徑r，將轉(zhuǎn)向點(diǎn)改成圓弧過(guò)渡，圓弧半徑為r，圓弧轉(zhuǎn)化結(jié)果見圖6所示。

為了驗(yàn)證所提出的新型路徑擬合方案的效果，將其與直線段擬合路徑方案和B樣條曲線擬合路徑方案進(jìn)行比較，結(jié)果如圖7所示。由圖可見，新型擬合路徑的長(zhǎng)度最短，路徑比較順滑，因此可以減少路徑轉(zhuǎn)彎帶來(lái)的速度損失，如果無(wú)人艇轉(zhuǎn)彎半徑足夠大，則不需要對(duì)航速進(jìn)行調(diào)整即可實(shí)現(xiàn)無(wú)人艇的平穩(wěn)轉(zhuǎn)向，從而保證航行的經(jīng)濟(jì)性。

2 基于改進(jìn)烏鴉搜索算法的無(wú)人艇路徑規(guī)劃

鑒于新型路徑擬合方法只是優(yōu)化路徑點(diǎn)數(shù)量并處理轉(zhuǎn)向點(diǎn)圓弧過(guò)渡的問題，而全局路徑點(diǎn)的位置也是決定路徑優(yōu)劣的關(guān)鍵因素之一，為此在新型路徑擬合方法的基礎(chǔ)上提出一種改進(jìn)的CSA（improved CSA，ICSA），用于解決路徑點(diǎn)位置的優(yōu)化問題。

2.1 標(biāo)準(zhǔn)CSA

標(biāo)準(zhǔn)CSA是依據(jù)烏鴉的智能覓食行為啟發(fā)提出來(lái)的。算法中的烏鴉會(huì)記住自己儲(chǔ)藏食物的位置，同時(shí)會(huì)跟蹤其余烏鴉，并偷取它們的食物，而被跟蹤的烏鴉有一定的概率發(fā)現(xiàn)自己被跟蹤了，一旦發(fā)現(xiàn)，則將跟蹤自己的烏鴉帶到其他隨機(jī)位置。依據(jù)烏鴉的覓食原理，將每一只烏鴉位置作為一個(gè)解，假設(shè)種群規(guī)模為N，初代烏鴉群的位置（初始解）用表示，表示初代烏鴉記住的藏匿食物最佳位置，且。烏鴉i在第t次迭代時(shí)的位置為，食物的儲(chǔ)藏位置為，跟蹤被發(fā)現(xiàn)的意識(shí)概率為PA，假設(shè)烏鴉i隨機(jī)選擇烏鴉j進(jìn)行跟蹤，根據(jù)意識(shí)概率可將位置分為以下2種情況：

1）烏鴉j未發(fā)現(xiàn)被跟蹤，則烏鴉i找到烏鴉j的食物儲(chǔ)藏點(diǎn)；

2）烏鴉j發(fā)現(xiàn)被跟蹤，則烏鴉j將烏鴉i帶到隨機(jī)位置。

烏鴉i的位置更新方法見式（1）和式（2）。

；??? （1）

。??? （2）

式中：ri、rj為[0，1]之間的隨機(jī)數(shù)；為烏鴉i在第t次迭代中的飛行長(zhǎng)度。lf一般取為2，依據(jù)文獻(xiàn)[16-20]，當(dāng)lf=2時(shí)搜索邊界涵蓋了所有的相鄰區(qū)域；當(dāng)lf<2時(shí)，搜索邊界則較小，增加了烏鴉i停在烏鴉i和烏鴉j之間的概率；當(dāng)lf>2時(shí)，搜索邊界則較大，增加了烏鴉i越過(guò)烏鴉j的概率，故將參數(shù)l設(shè)定為2；PA為烏鴉j發(fā)現(xiàn)被跟蹤的概率，為解的適應(yīng)度。

依據(jù)標(biāo)準(zhǔn)CSA的原理，將CSA的優(yōu)化步驟如下。

步驟1：隨機(jī)產(chǎn)生初始種群，及初始記憶中的儲(chǔ)藏位置

步驟2：依據(jù)式（1）和式（2）對(duì)烏鴉位置進(jìn)行更新。

步驟3：判斷是否在可行域范圍內(nèi)，如果是，則允許更新位置，否則保持位置不變。

步驟4：計(jì)算解對(duì)應(yīng)的適應(yīng)度值

步驟5：更新記憶中的食物儲(chǔ)藏位置，表示第t次迭代中第i只烏鴉的記憶中儲(chǔ)藏位置對(duì)應(yīng)的適應(yīng)度函數(shù)值，具體更新策略為

（3）

步驟6：判斷是否滿足算法收斂條件，如果不滿足，則重復(fù)執(zhí)行步驟2～步驟5，直至達(dá)到收斂條件。

2.2 改進(jìn)的CSA

由于CSA調(diào)節(jié)參數(shù)少，易陷入局部解和收斂精度低。故從以下3個(gè)方面提出改進(jìn)方案。

1）利用反向?qū)W習(xí)算法[22]優(yōu)化初始種群。初始種群的優(yōu)劣對(duì)算法的優(yōu)化精度和收斂速度影響較大，多樣性較好的初始種群對(duì)提升算法性能有很大幫助，而通過(guò)隨機(jī)方式產(chǎn)生種群可能會(huì)造成初始種群分布不均，影響種群的多樣性，通過(guò)反向?qū)W習(xí)對(duì)初始種群進(jìn)行優(yōu)化，能有效提高初始種群的有效性。下面為具體的反向?qū)W習(xí)優(yōu)化方法。

假設(shè)隨機(jī)初始種群，，n為種群數(shù)量，D為解向量的維度，，，則按式（4）計(jì)算反向種群：

。??? （4）

通過(guò)組合種群選擇n個(gè)適應(yīng)度較大的烏鴉位置作為新的初始種群。

2）采用動(dòng)態(tài)意識(shí)概率替代固定意識(shí)概率。由于標(biāo)準(zhǔn)CSA的意識(shí)概率PA是按固定概率50%來(lái)設(shè)定，故搜索過(guò)程比較僵化，考慮到初期搜索時(shí)需要保證樣本的多樣性，需增加全局搜索能力，故需減小PA值；后期搜索時(shí)需保證收斂速度，故要增大PA值?；谝陨峡紤]，所提出的動(dòng)態(tài)意識(shí)概率需滿足以下3個(gè)條件。

條件1：動(dòng)態(tài)意識(shí)概率必須在規(guī)定的最大和最小概率之間變化。

條件2：動(dòng)態(tài)意識(shí)概率須隨著迭代次數(shù)的增加而減小。

條件3：在搜索初始階段PA值應(yīng)大于50%，在搜索后期PA值應(yīng)小于50%。

基于以上的3個(gè)條件，提出了一種動(dòng)態(tài)意識(shí)概率公式，為

。??? （5）

根據(jù)式（1）和式（2）可知，PA值越大越傾向于全局搜索，越小則越傾向于局部搜索，但考慮到搜索初始階段也要有一定的局部搜索能力，故將PAmax設(shè)定為0.7～0.9；同時(shí)也要保證搜索后期也有一定的全局搜索能力，故將PAmin設(shè)定為0.1～0.3。由于文中僅是驗(yàn)證所提出的動(dòng)態(tài)意識(shí)概率的有效性，則初步選定PAmax=0.8，PAmin=0.2。為了驗(yàn)證式（5）的有效性，將PA與迭代次數(shù)t的函數(shù)關(guān)系表達(dá)如圖8所示。

從圖8中的曲線變化規(guī)律可知，迭代次數(shù)t=1時(shí)，PA為最大值0.8，t=100時(shí)，PA為最小值0.2；PA隨迭代次數(shù)增加而減?。坏螖?shù)t<46，PA均小于0.5，按式（2）進(jìn)行搜索的概率提高了，從而提高了全局搜索能力；當(dāng)?shù)螖?shù)t≥46，PA則開始超過(guò)0.5，按式（1）進(jìn)行搜索的概率提高了，從而提高了收斂速度，增強(qiáng)了局部搜索能力。依據(jù)以上分析，該動(dòng)態(tài)意識(shí)概率滿足了上述的3個(gè)條件要求，對(duì)CSA的改進(jìn)有一定的可行性。

3）采用萊維飛行改進(jìn)隨機(jī)搜索。萊維飛行是服從萊維分布的隨機(jī)搜索路徑，是一種短距離搜索和偶爾長(zhǎng)距離的跳變相間的隨機(jī)搜索方式，它能夠增加種群多樣性和擴(kuò)大搜索范圍，常用于改進(jìn)粒子群、布谷鳥算法等。

萊維飛行位置更新公式為

，??? （6）

式中：為步長(zhǎng)因子，通常根據(jù)式（7）來(lái)計(jì)算；表示點(diǎn)對(duì)點(diǎn)的乘積；s為步長(zhǎng)。

，??? （7）

式中：為當(dāng)前最優(yōu)解位置；為常數(shù)，通常取0.1，隨機(jī)步長(zhǎng)s借助Levy飛行的生成過(guò)程，滿足

，??? （8）

式中，μ、v服從參數(shù)為、的正態(tài)分布

，??? （9）

，??? （10）

。??? （11）

式中：取常數(shù)1.5；為常數(shù)1。

2.3 基于ICSA的路徑規(guī)劃優(yōu)化步驟

在新型路徑擬合方法的基礎(chǔ)上，ICSA對(duì)路徑規(guī)劃的優(yōu)化按以下步驟進(jìn)行。

步驟1：隨機(jī)產(chǎn)生初始種群。

1）在起始點(diǎn)S與終點(diǎn)G之間產(chǎn)生m個(gè)縱向等間距分布的隨機(jī)路徑點(diǎn)，與起始點(diǎn)S和終點(diǎn)G組合成為一條初始路徑=（S，P1，P2，…，Pm-1，G）=（p1，p2，…，pn），依次產(chǎn)生N條隨機(jī)路徑，進(jìn)而產(chǎn)生初始種群。

2）依據(jù)新型路徑擬合方法對(duì)路徑上的路徑點(diǎn)進(jìn)行優(yōu)化，形成新型擬合路徑。

3）基于新型擬合路徑計(jì)算路徑長(zhǎng)度，直接將路徑長(zhǎng)度作為適應(yīng)度值f（）使用，的適應(yīng)度值f（）的計(jì)算見式（12），其中為

，??? （12）

式中：為第t次迭代中的第i條路徑；為第t次迭代中的第i條路徑中的第j個(gè)轉(zhuǎn)向點(diǎn)；ρ為懲罰因子；為兩相鄰轉(zhuǎn)向點(diǎn)與之間的障礙物長(zhǎng)度。

步驟2：利用反向?qū)W習(xí)算法對(duì)初始種群進(jìn)行優(yōu)化，對(duì)初始種群P（t=1）、對(duì)應(yīng)的適應(yīng)度值f（）和儲(chǔ)藏位置M（t=1）進(jìn)行更新。

步驟3：設(shè)定迭代次數(shù)t=1。

步驟4：依據(jù)式（5）計(jì)算動(dòng)態(tài)意識(shí)概率PA。

步驟5：根據(jù)式（1）和式（6）將烏鴉位置更新為

步驟6：判斷是否在可行域范圍內(nèi)，如果是，則允許更新位置，否則保持位置不變。

步驟7： 依據(jù)步驟1中的式（2）和式（3）產(chǎn)生新型擬合路徑，再依據(jù)式（12）計(jì)算適應(yīng)度值f（）。

步驟8：依據(jù)式（3）更新烏鴉的食物儲(chǔ)藏位置

步驟9：迭代次數(shù)增加1，即t=t+1。

步驟10：判斷t是否大于總迭代次數(shù)T，如果否，則轉(zhuǎn)入步驟4繼續(xù)進(jìn)行優(yōu)化，反之，則輸出最優(yōu)路徑（最優(yōu)的食物儲(chǔ)藏位置）和相應(yīng)結(jié)果。

依據(jù)上述步驟，基于ICSA的路徑規(guī)劃優(yōu)化流程如圖9所示。

3 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證文中所提出的ICSA的性能和新型路徑擬合方法的可行性，選擇在Matlab仿真環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，采用2個(gè)場(chǎng)景進(jìn)行驗(yàn)證，實(shí)驗(yàn)的仿真區(qū)域尺寸為500×500，起點(diǎn)坐標(biāo)為[10， 10]，終點(diǎn)坐標(biāo)為[490， 490]，單位均為km。假設(shè)無(wú)人艇航速為60 km/h，且轉(zhuǎn)彎半徑為40 km，在這種前提下即可保證無(wú)人艇在轉(zhuǎn)向時(shí)速度仍然維持不變。為了驗(yàn)證所提出的改進(jìn)烏鴉搜索算法及其動(dòng)態(tài)意識(shí)概率的有效性，將ICSA分為ICSA1和ICSA2，其中ICSA1的改進(jìn)方面包括采用反向?qū)W習(xí)算法優(yōu)化初始種群，以及采用萊維飛行策略改進(jìn)隨機(jī)搜索；ICSA2則在ICSA1的基礎(chǔ)上，增加了動(dòng)態(tài)意識(shí)概率以替換標(biāo)準(zhǔn)CSA的固定意識(shí)概率。同時(shí)還采用了差分進(jìn)化算法（difference methods，DE）、遺傳算法（genetic algorithm，GA）和標(biāo)準(zhǔn)烏鴉搜索算法（CSA）進(jìn)行仿真實(shí)驗(yàn)。在這些優(yōu)化算法中均令式（12）中的懲罰因子ρ=200、種群數(shù)N=100、最大迭代次數(shù)T=200，算法的其余參數(shù)見表1所示。由于這些算法都屬于隨機(jī)優(yōu)化算法，因此對(duì)每個(gè)算法都進(jìn)行了20次實(shí)驗(yàn)。

針對(duì)ICSA2優(yōu)化得到的最優(yōu)路徑點(diǎn)，分別采用新型路徑擬合方法、B樣條曲線路徑擬合方法、直線段路徑擬合方法進(jìn)行路徑擬合，結(jié)果如圖10所示。由圖可見，相較于另外2種擬合方案，利用新型路徑擬合方法得到的路徑長(zhǎng)度明顯更短，轉(zhuǎn)向點(diǎn)數(shù)量更少，同時(shí)也能保證路徑的順滑性，更能滿足無(wú)人艇航行的實(shí)際需求。

20次實(shí)驗(yàn)中各算法優(yōu)化得到的最佳無(wú)人艇路徑見圖11所示。從圖11（a）中可知，ICSA1和DE優(yōu)化的路徑包含有4個(gè)轉(zhuǎn)向點(diǎn)，其余3個(gè)算法的路徑都只有3個(gè)轉(zhuǎn)向點(diǎn)；從圖11（b）中可知，ICSA1、ICSA2和GA優(yōu)化的路徑包含2個(gè)轉(zhuǎn)向點(diǎn)，CSA和DE優(yōu)化的路徑則有3個(gè)轉(zhuǎn)向點(diǎn)。

為了進(jìn)一步進(jìn)行比較，將不同算法優(yōu)化得到的路徑長(zhǎng)度的最優(yōu)值、平均值、最差值和標(biāo)準(zhǔn)差列入表2中，并利用箱線圖（見圖12）確定最有效的算法。由表2可見，ICSA2對(duì)應(yīng)的4個(gè)指標(biāo)都是最小值，尤其是路徑長(zhǎng)度的平均值明顯小于另外4種算法。另外在圖12中，ICSA2的箱線圖最小值和中間值明顯小于其余4種算法。這說(shuō)明與另外4種算法相比，ICSA2的魯棒性和收斂精度最高，證明了ICSA2在優(yōu)化無(wú)人艇新型擬合路徑方面的性能最好，同時(shí)也驗(yàn)證了所提出的動(dòng)態(tài)意識(shí)概率的有效性。

為了驗(yàn)證ICSA2與另外4種算法是否在性能方面存在顯著的差異，采用了方差分析法，設(shè)定顯著性水平，分析結(jié)果見表3所示。表中SS表示離均平方和，df表示自由度，MS表示均方，F(xiàn)值等于組內(nèi)MS除以組間MS。在分析結(jié)果中如果P值小于顯著水平，則證明確實(shí)存在顯著差異。表3中ICSA與另外3種算法比較的P值遠(yuǎn)小于0.05，表明ICSA2與ICSA1、CSA、GA、DE這4個(gè)算法之間都存在著統(tǒng)計(jì)學(xué)意義上的顯著差異。

圖13為ICSA2、ICSA1、CSA、GA和DE這5種算法的優(yōu)化迭代圖。由圖可知：ICSA2優(yōu)化的路徑最短；ICSA1相較于ICSA，采用反向?qū)W習(xí)算法對(duì)初始種群進(jìn)行優(yōu)化后，提高了種群質(zhì)量，同時(shí)采用了萊維飛行策略對(duì)隨機(jī)搜索進(jìn)行改進(jìn)，提高了隨機(jī)搜索的方向性，進(jìn)而提高了搜索精度；與CSA1相比，ICSA2由于利用了動(dòng)態(tài)意識(shí)概率，提高了搜索初始階段的全局搜索能力和搜索末段的局部搜索能力，從而提高了搜索的效率和精度。

4 結(jié)? 論

為了解決無(wú)人艇路徑規(guī)劃中的2個(gè)關(guān)鍵技術(shù)問題，實(shí)現(xiàn)路徑的擬合和路徑點(diǎn)位置的全局規(guī)劃，提出了一種基于改進(jìn)烏鴉搜索算法的無(wú)人艇新型路徑規(guī)劃策略。

1）提出了一種直線與圓弧轉(zhuǎn)彎相結(jié)合的新型無(wú)人艇路徑擬合方法，對(duì)路徑點(diǎn)數(shù)量進(jìn)行優(yōu)化，精簡(jiǎn)了多余的轉(zhuǎn)向點(diǎn)，依據(jù)無(wú)人艇轉(zhuǎn)彎半徑要求，對(duì)轉(zhuǎn)向點(diǎn)進(jìn)行圓弧過(guò)渡處理，從而形成了一條短而順滑的路徑。

2）在無(wú)人艇新型路徑擬合方法的基礎(chǔ)上，提出了一種改進(jìn)的烏鴉搜索算法，實(shí)現(xiàn)了轉(zhuǎn)向點(diǎn)位置的全局優(yōu)化。主要從3個(gè)方面進(jìn)行了優(yōu)化算法改進(jìn)：首先，引入了反向?qū)W習(xí)策略對(duì)初始種群進(jìn)行優(yōu)化；然后，提出了一種隨迭代次數(shù)而動(dòng)態(tài)變化的意識(shí)概率，以提升迭代初期的全局搜索能力和后期的局部搜索能力；最后，采用了萊維飛行策略對(duì)隨機(jī)搜索進(jìn)行改進(jìn)。

3）仿真結(jié)果表明：所提出的新型路徑擬合方法優(yōu)于傳統(tǒng)的B樣條曲線路徑擬合方法和直線段路徑擬合方案，提高了航行路徑的經(jīng)濟(jì)性和順滑性。方差分析結(jié)果表明所提出的改進(jìn)烏鴉搜索算法相較于標(biāo)準(zhǔn)烏鴉搜索算法、遺傳算法和差分進(jìn)化算法，在優(yōu)化新型擬合路徑方面有更強(qiáng)的魯棒性和更高的收斂精度，能進(jìn)一步縮短無(wú)人艇的航行距離，可進(jìn)一步改善無(wú)人艇自動(dòng)航行的穩(wěn)定性和經(jīng)濟(jì)性，為無(wú)人艇自動(dòng)航行路徑中的關(guān)鍵問題提供了一種有效的解決方案。

所設(shè)定的意識(shí)概率的最大值PAmax和最小值PAmin對(duì)動(dòng)態(tài)意識(shí)概率值有直接影響，故下一步將針對(duì)意識(shí)概率的最大值和最小值對(duì)烏鴉搜索算法性能的影響做進(jìn)一步研究，同時(shí)對(duì)烏鴉搜索算法做進(jìn)一步改進(jìn)；另外由于海上的障礙物并非都是靜止不動(dòng)的，故后期研究方向?qū)⑨槍?duì)具有動(dòng)態(tài)避障要求的全局路徑規(guī)劃。此外，后期研究中還將考慮使用模擬船進(jìn)一步驗(yàn)證路徑規(guī)劃策略的有效性。

參考文獻(xiàn)

［1］? 吳博， 熊勇， 文元橋. 基于速度障礙原理的無(wú)人艇自動(dòng)避碰算法[J]. 大連海事大學(xué)學(xué)報(bào)， 2014， 40（2）： 13-16.

Wu B， Xiong Y， Wen Y Q. Automatic collision avoidance algorithm for unmanned surface vessel based on velocity obstacles[J]. Journal of Dalian Maritime University， 2014， 40（2）： 13-16. （in Chinese）

［2］? Shah B C， Gupta S K. Long-distance path planning for unmanned surface vehicles in complex marine environment[J]. IEEE Journal of Oceanic Engineering， 2020， 45（3）： 813-830.

［3］? Wang Z， Li G F， Ren J. Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm[J]. Computer Communications， 2021， 166（17）： 49-56.

［4］? Niu H L， Lu Y， Savvaris A， et al. An energy-efficient path planning algorithm for unmanned surface vehicles[J]. Ocean Engineering， 2018， 161： 308-321.

［5］? Bertsekas D P. Robust shortest path planning and semicontractive dynamic programming[J]. Naval Research Logistics （NRL）， 2019， 66（1）： 15-37.

［6］? 邢博聞， 楊柳， 胡慶松， 等. 無(wú)人船全覆蓋路徑規(guī)劃算法研究[J]. 兵器裝備工程學(xué)報(bào)， 2022， 43（9）： 28-33.

Xing B W， Yang L， Hu Q S， et al. Research of unmanned ship based on artificial bee colony method[J]. Journal of Ordnance Equipment Engineering， 2022， 43（9）： 28-33.

［7］? Long Y， Zuo Z M， Su Y X， et al. An A*-based bacterial foraging optimisation algorithm for global path planning of unmanned surface vehicles[J]. Journal of Navigation， 2020， 73（6）： 1247-1262.

［8］? 周利坤， 劉宏昭. 自適應(yīng)人工魚群算法在清罐移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 機(jī)械科學(xué)與技術(shù)， 2012， 31（7）： 1085-1089.

Zhou L K， Liu H Z. An adaptive artificial fish school algorithm for path planning of mobile tank-clearing robot[J]. Mechanical Science and Technology for Aerospace Engineering， 2012， 31（7）： 1085-1089. （in Chinese）

［9］? Ma Y， Hu M Q， Yan X P. Multi-objective path planning for unmanned surface vehicle with currents effects[J]. ISA Transactions， 2018， 75： 137-156.

［10］? Wang C， Mao Y S， Du K J. Simulation on local obstacle avoidance algorithm for unmanned surface vehicle[J]. International Journal of Simulation Modelling， 2016， 15（3）： 460-472.

［11］? Zhong J B， Li B Y， Li S X， et al. Particle swarm optimization with orientation angle-based grouping for practical unmanned surface vehicle path planning[J]. Applied Ocean Research， 2021， 111： 102658.

［12］? 謝沖沖， 李瑩. 基于改進(jìn)算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 重慶大學(xué)學(xué)報(bào)， 2021， 44（12）： 140-148.

Xie C C， Li Y. Path planning of mobile robots based on improved algorithm[J]. Journal of Chongqing University， 2021， 44（12）： 140-148. （in Chinese）

［13］? Kim H， Kim S H， Jeon M， et al. A study on path optimization method of an unmanned surface vehicle under environmental loads using genetic algorithm[J]. Ocean Engineering， 2017， 142： 616-624.

［14］? Guo H， Mao Z Y， Ding W J， et al. Optimal search path planning for unmanned surface vehicle based on an improved genetic algorithm[J]. Computers & Electrical Engineering， 2019， 79： 106467.

［15］? 劉志強(qiáng)， 何麗， 袁亮， 等. 采用改進(jìn)灰狼算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 西安交通大學(xué)學(xué)報(bào)， 2022， 56（10）： 49-60.

Liu Z Q， He L， Yuan L， et al. Path planning of mobile robot based on TGWO algorithm[J]. Journal of Xian Jiaotong University， 2022， 56（10）： 49-60. （in Chinese）

［16］? Askarzadeh A. A novel metaheuristic method for solving constrained engineering optimization problems： crow search algorithm[J]. Computers & Structures， 2016， 169： 1-12.

［17］? Askarzadeh A， Gharibi M. Accurate estimation of cost function parameters for thermal power plants using a novel optimization approach[J]. Energy Sources， Part A： Recovery， Utilization， and Environmental Effects， 2018， 40（19/24）： 2986-2999.

［18］? 王麗婷， 張金鑫， 張金華. 烏鴉搜索算法在SVM參數(shù)優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用， 2019， 55（21）： 214-219.

Wang L T， Zhang J X， Zhang J H. Application of crow search algorithm in SVM parameter optimization[J]. Computer Engineering and Applications， 2019， 55（21）： 214-219. （in Chinese）

［19］? Lin X F， Chen S M， Lin W Q. Modified crow search algorithm-based fuzzy control of adjacent buildings connected by magnetorheological dampers considering soil-structure interaction[J]. Journal of Vibration and Control， 2021， 27（1/2）： 57-72.

［20］? 劉雪靜， 賀毅朝， 吳聰聰. 求解集合聯(lián)盟背包問題的二次貪心變異烏鴉算法[J]. 微電子學(xué)與計(jì)算機(jī)， 2018， 35（11）： 13-19.

Liu X J， He Y C， Wu C C. Quadratic greedy mutated crow search algorithm for solving set-union knapsack problem[J]. Microelectronics & Computer， 2018， 35（11）： 13-19. （in Chinese）

［21］? 樊英， 張達(dá)敏， 陳忠云， 等. 基于改進(jìn)烏鴉算法的車載網(wǎng)絡(luò)頻譜分配方案[J]. 計(jì)算機(jī)科學(xué)， 2020， 47（12）： 273-278.

Fan Y， Zhang D M， Chen Z Y， et al. Spectrum allocation scheme of vehicular ad hoc networks based on improved crow search algorithm[J]. Computer Science， 2020， 47（12）： 273-278. （in Chinese）

［22］? Rahnamayan S， Tizhoosh H R， Salama M M A. Opposition-based differential evolution[J]. IEEE Transactions on Evolutionary Computation， 2008， 12（1）： 64-79.

（編輯? 詹燕平）