基于改進(jìn)蟻群算法的無(wú)人船路徑規(guī)劃研究

王 成，任 佳，張 育

（海南大學(xué)信息與通信工程學(xué)院，海南?？?570228）

作為水面智能體的典型代表，無(wú)人船（Unmanned Surface Vehicles，USV）可自主完成水面和水下目標(biāo)偵察、搜索、探測(cè)和監(jiān)視等任務(wù)［1-2］，受到了廣泛關(guān)注，路徑規(guī)劃［3］是無(wú)人船進(jìn)行水域作業(yè)的前提和保障.

目前適用于無(wú)人船路徑規(guī)劃的算法主要有遺傳算法［4］、粒子群算法［5］、蟻群算法［6-7］和人工勢(shì)場(chǎng)法［8］等.相較于其他智能優(yōu)化算法，蟻群算法應(yīng)用于路徑規(guī)劃時(shí)具有并行搜索、魯棒性強(qiáng)、簡(jiǎn)單易實(shí)現(xiàn)等特點(diǎn)，但存在著初期搜索效率低、收斂速度慢和易陷入局部最優(yōu)等缺點(diǎn)，因此許多學(xué)者從信息素的更新、啟發(fā)式信息值等方面對(duì)蟻群算法進(jìn)行了改進(jìn)，提出改進(jìn)的蟻群算法［9］.曹新亮［10］等針對(duì)蟻群算法在路徑規(guī)劃過(guò)程中出現(xiàn)的收斂速度慢的缺陷，對(duì)各點(diǎn)初始信息素濃度進(jìn)行差異化設(shè)置，避免尋優(yōu)的盲目性，提高了算法的收斂速度，但該算法僅從一個(gè)方向?qū)ο伻核惴ㄟM(jìn)行改進(jìn)，并沒(méi)有解決蟻群算法陷入死鎖路徑的問(wèn)題.朱艷［11］等針對(duì)蟻群算法收斂速度慢，容易陷入局部最優(yōu)的問(wèn)題，自適應(yīng)調(diào)整啟發(fā)函數(shù)，引入方向信息，提高算法效率，動(dòng)態(tài)調(diào)整權(quán)重系數(shù)改變目標(biāo)點(diǎn)的方向信息在螞蟻移動(dòng)過(guò)程中的影響，該算法不僅可以提高收斂速度，而且在改善解的質(zhì)量方面也取得了較好的效果，但仍然存在算法前期搜索效率低的問(wèn)題.王曉燕［12］等結(jié)合人工勢(shì)場(chǎng)法構(gòu)造啟發(fā)信息，提高了算法的收斂速度，根據(jù)起點(diǎn)和終點(diǎn)的編號(hào)對(duì)初始信息素濃度進(jìn)行不均勻分配，避免了蟻群算法前期搜索的盲目性，自適應(yīng)調(diào)整信息素?fù)]發(fā)系數(shù)，提高了全局搜索能力，由于采用人工勢(shì)場(chǎng)法構(gòu)建起發(fā)信息，增加了算法的運(yùn)行時(shí)間，對(duì)于蟻群算法陷入死鎖路徑的問(wèn)題沒(méi)有進(jìn)行改進(jìn).屈鴻［13］等在螞蟻陷入死鎖時(shí)，對(duì)當(dāng)前柵格的信息素濃度進(jìn)行懲罰，再令螞蟻退到上一個(gè)柵格，可以降低螞蟻進(jìn)入死鎖的概率，但此改進(jìn)會(huì)增加路徑長(zhǎng)度，無(wú)法得到最有解.白建龍［14］等針對(duì)易陷入局部最優(yōu)問(wèn)題，利用搜索的歷史信息改善解的多樣性，從而獲得最優(yōu)路徑，但該算法未考慮算法前期收斂速度慢的問(wèn)題.Luo Q［15］等構(gòu)建分配不均勻的初始信息素，改進(jìn)全局信息素更新的方法，引入動(dòng)態(tài)懲罰方法解決死鎖問(wèn)題，但該算法降低了每次迭代過(guò)程中最優(yōu)解的正反饋引導(dǎo)作用.

由于上述文獻(xiàn)在利用蟻群算法實(shí)現(xiàn)全局路徑規(guī)劃時(shí)，仍在一些弊端，因此筆者針對(duì)蟻群算法存在的前期搜索效率低、收斂速度慢等問(wèn)題進(jìn)行了以下改進(jìn)：對(duì)初始信息素進(jìn)行不均勻分配，避免前期盲目搜素；在信息素濃度更新規(guī)則加入權(quán)重因子，增強(qiáng)了當(dāng)前最優(yōu)解對(duì)后代螞蟻的指導(dǎo)作用，加快了算法的收斂；對(duì)死鎖點(diǎn)的信息素濃度進(jìn)行懲罰，減少后續(xù)死亡螞蟻的數(shù)量.

1 路徑規(guī)劃模型

1.1 環(huán)境建模在進(jìn)行無(wú)人船路徑規(guī)劃前，需要對(duì)任務(wù)環(huán)境進(jìn)行建模，以便于把任務(wù)環(huán)境中安全區(qū)域及障礙物清晰地表示出來(lái)，筆者研究無(wú)人船全局路徑規(guī)劃.設(shè)定障礙物都是靜止不動(dòng)，因?yàn)闁鸥穹ū硎竞?jiǎn)單，易于在編程中實(shí)現(xiàn).為了簡(jiǎn)化無(wú)人船的任務(wù)環(huán)境，采用柵格法對(duì)任務(wù)環(huán)境進(jìn)行建模，0表示安全區(qū)域，1表示障礙物，將任務(wù)環(huán)境表示為方形地圖，柵格法由邊長(zhǎng)單位為1的小正方形組成，安全區(qū)域表示為白色，障礙物表示為黑色，圖1為二維電子地圖，圖2為對(duì)應(yīng)的二維柵格地圖.

圖1 二維電子地圖

圖2 二維環(huán)境柵格圖

為了便于后期對(duì)環(huán)境信息的表征，對(duì)柵格進(jìn)行編號(hào)，順序從上往下，從左往右.由于螞蟻所在柵格位置為柵格的序號(hào)，而在計(jì)算柵格間距離時(shí)，利用柵格點(diǎn)中心位置坐標(biāo)，因此柵格號(hào)與坐標(biāo)之間的關(guān)系

其中，a為小柵格的邊長(zhǎng)，n為小柵格的序號(hào)，M M為柵格的總行數(shù)，ceil為向上取余函數(shù)，mod為余函數(shù)，“/”為簡(jiǎn)單除法，保留小數(shù).圖3為圖2對(duì)應(yīng)的柵格序號(hào)圖.

圖3 柵格對(duì)應(yīng)序號(hào)圖

1.2 建立目標(biāo)函數(shù)在保證無(wú)人船航行安全的前提下，進(jìn)行航線的路徑規(guī)劃，需先建立目標(biāo)函數(shù)

其中，L為無(wú)人船的航線距離，N為無(wú)人船航線所穿過(guò)的柵格數(shù)，d n（n=1，2，…，N）為所在柵格的中心點(diǎn)，l(d n，d n+1)為無(wú)人船從點(diǎn)d n到點(diǎn)d n+1的直線距離.

2 基于改進(jìn)蟻群算法的路徑規(guī)劃算法

2.1 傳統(tǒng)蟻群算法蟻群算法是根據(jù)螞蟻覓食行為所研究出來(lái)的一種智能仿生算法.由初始起點(diǎn)，螞蟻會(huì)在覓食經(jīng)過(guò)的路徑上留下信息素，當(dāng)螞蟻第一次走到一個(gè)分岔路口時(shí)，會(huì)隨機(jī)選擇路徑并留下信息素，信息素濃度與路徑長(zhǎng)短成反比，路徑越長(zhǎng)信息素濃度越低，螞蟻會(huì)優(yōu)先選擇信息素濃度較高的路徑，形成一種正反饋現(xiàn)象，較長(zhǎng)路徑上的信息素濃度會(huì)越來(lái)越低，甚至消失，較短路徑上的信息素濃度越來(lái)越高.最終會(huì)找到最優(yōu)路徑.

蟻群算法采用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)節(jié)點(diǎn)的位置，如果螞蟻k現(xiàn)位于i點(diǎn)，通過(guò)式（3）以q0的概率選擇螞蟻k的下一個(gè)節(jié)點(diǎn)j，否則利用式（4）計(jì)算轉(zhuǎn)移到每個(gè)點(diǎn)的概率，最后利用輪盤(pán)賭去選擇下一個(gè)節(jié)點(diǎn)j，

其中，式（3）中q為（0，1）內(nèi)的隨機(jī)數(shù)，q0為（0，1）之間的概率系數(shù)，在此需根據(jù)需求自行設(shè)置.C為螞蟻可以選擇的下一個(gè)節(jié)點(diǎn)j的集合；下一個(gè)節(jié)點(diǎn)j的選擇范圍為當(dāng)前節(jié)點(diǎn)周?chē)?個(gè)節(jié)點(diǎn)中的可行性點(diǎn)，j為根據(jù)式（4）所計(jì)算出來(lái)的下一個(gè)點(diǎn)，τij為螞蟻從i點(diǎn)移動(dòng)到j(luò)點(diǎn)的信息素濃度；α為信息素激勵(lì)因子；β為期望啟發(fā)因子；ηij為螞蟻從i點(diǎn)移動(dòng)到j(luò)點(diǎn)的啟發(fā)程度；arg max函數(shù)為[τij]α[ηij]β取到最大值的點(diǎn)的集合，d ij為螞蟻所在的i點(diǎn)到下一點(diǎn)j點(diǎn)的直線距離，d jE為下一點(diǎn)j到終點(diǎn)E的距離.

螞蟻在追尋信息素尋找路徑的同時(shí)，會(huì)殘留新的信息素，因此路徑上的信息素會(huì)揮發(fā)殘留疊加，在t+1時(shí)刻時(shí)，路徑上信息素濃度進(jìn)行更新

其中，ρ為信息素?fù)]發(fā)系數(shù)，m為螞蟻的總數(shù)量，為螞蟻k新增的信息素濃度，可得到

其中，Q為信息素強(qiáng)度，L k為螞蟻k走的路徑總長(zhǎng)度.

2.2 改進(jìn)蟻群算法

2.2.1 改進(jìn)初始信息素由于螞蟻在進(jìn)行覓食行為之前，沒(méi)有經(jīng)過(guò)所搜索的路徑，傳統(tǒng)蟻群算法的信息素濃度的初始值在每條路徑上都為0，螞蟻在前期進(jìn)行路徑搜素時(shí)，存在一定的盲目性，容易造成收斂速度慢，浪費(fèi)搜索路徑的時(shí)間，兩點(diǎn)之間直線最短.因此起點(diǎn)到終點(diǎn)的最短路徑為此兩點(diǎn)的之間距離即d SE.在此根據(jù)起點(diǎn)S、所在點(diǎn)i、下一個(gè)目標(biāo)點(diǎn)j及終點(diǎn)E之間的距離，由于路徑的長(zhǎng)度不同，代表著信息素濃度的初始值進(jìn)行了不均勻的分配，使得對(duì)于較短路徑上的信息素濃度偏高，避免了算法初期的盲目性，進(jìn)一步提高了搜索速度，具體實(shí)現(xiàn)

其中，d SE為起點(diǎn)S到終點(diǎn)E之間的直線距離，d Si為起點(diǎn)S到所在點(diǎn)i之間的直線距離，d ij為所在點(diǎn)i到下一個(gè)節(jié)點(diǎn)j的直線距離，d jE為下一個(gè)節(jié)點(diǎn)j到終點(diǎn)E之間的直線距離，由式（1）可得.

2.2.2 改進(jìn)信息素更新機(jī)制傳統(tǒng)蟻群算法中路徑上信息素濃度的更新主要是由隨時(shí)間揮發(fā)后剩余的部分和螞蟻經(jīng)過(guò)后新增的信息素組成，存在搜索效率低的問(wèn)題.為了提高搜索效率，采用“優(yōu)勝劣汰”的思想引用權(quán)重因子h，當(dāng)所有螞蟻進(jìn)行完一次迭代之后，會(huì)對(duì)所有路徑上的信息素進(jìn)行更新，此時(shí)的路徑長(zhǎng)短不一，把螞蟻所走的路徑中最優(yōu)解L best與螞蟻此次所走的路徑長(zhǎng)度L k之間的比值作為權(quán)重因子h，由式（9）可得，路徑越短，權(quán)重因子h越大，信息素增加的越多.根據(jù)式（10）對(duì)所有路徑上的信息素濃度進(jìn)行更新，較短路徑上信息素增加越多，會(huì)增強(qiáng)較優(yōu)解對(duì)后續(xù)迭代的引導(dǎo)作用，較長(zhǎng)路徑上信息素增加越少，可以減少較差解對(duì)后續(xù)迭代的誤導(dǎo)作用，因此可以加快算法收斂到全局最優(yōu)的速度.

2.2.3 解決死鎖問(wèn)題死鎖問(wèn)題即在尋找路徑的過(guò)程中，當(dāng)前所在節(jié)點(diǎn)周?chē)鷽](méi)有可選擇的可行節(jié)點(diǎn)，且當(dāng)前節(jié)點(diǎn)并非終點(diǎn).傳統(tǒng)蟻群算法在螞蟻進(jìn)入死鎖之后，僅僅殺死陷入死鎖點(diǎn)的螞蟻，減少螞蟻數(shù)量，并沒(méi)有對(duì)死鎖點(diǎn)的信息素進(jìn)行任何懲罰，這樣后續(xù)還是會(huì)有一定數(shù)量的螞蟻進(jìn)入此點(diǎn)，螞蟻數(shù)量大量減少，使得解決問(wèn)題的多樣性降低，無(wú)法保障算法迭代尋優(yōu)的后期解的多樣性.因此為了避免螞蟻陷入死鎖點(diǎn)，引入懲戒因子μ，對(duì)死鎖點(diǎn)的信息素濃度進(jìn)行懲罰，計(jì)算死亡螞蟻的數(shù)量mn，進(jìn)入死鎖點(diǎn)的螞蟻數(shù)量越多，μ越大，對(duì)該死鎖點(diǎn)的懲罰也就越大，后續(xù)進(jìn)入此死鎖點(diǎn)的螞蟻數(shù)量就會(huì)大大減少，增加了解決問(wèn)題的多樣性，對(duì)死鎖點(diǎn)信息素的懲罰

2.3 改進(jìn)蟻群算法流程本文算法具體流程如下：

步驟1根據(jù)無(wú)人船任務(wù)環(huán)境的起始點(diǎn)和終點(diǎn)，確定無(wú)人船的工作區(qū)域；

步驟2初始化各個(gè)參數(shù).起始點(diǎn)S的位置，終點(diǎn)E的位置，螞蟻數(shù)量m，信息素激勵(lì)因子α，期望啟發(fā)因子β，信息素?fù)]發(fā)系數(shù)ρ，最大迭代次數(shù)K，當(dāng)前迭代次數(shù)k，迭代次數(shù)閾值k0，信息素強(qiáng)度Q，死鎖時(shí)懲戒因子μ等相關(guān)參數(shù)；

步驟3根據(jù)柵格法對(duì)無(wú)人船的工作區(qū)域進(jìn)行建模；

步驟4計(jì)算初始信息素，根據(jù)式（8）計(jì)算初始信息素τij(0)；

步驟5根據(jù)無(wú)人船工作區(qū)域的起始點(diǎn)，初始化m個(gè)螞蟻的位置為無(wú)人船工作區(qū)域的起始點(diǎn)；

步驟6規(guī)劃螞蟻路徑，根據(jù)偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則式（3），結(jié)合式（4），確定螞蟻下一點(diǎn)j的位置；

步驟7然后把節(jié)點(diǎn)j添加到禁忌表中，并判斷路徑點(diǎn)j是否是死鎖點(diǎn)，若是則執(zhí)行步驟8，否則返回步驟6，知道下一個(gè)路徑點(diǎn)j為無(wú)人船執(zhí)行任務(wù)的終點(diǎn)，則執(zhí)行步驟9；

步驟8螞蟻進(jìn)入死鎖狀態(tài)，計(jì)算進(jìn)入死鎖狀態(tài)的螞蟻數(shù)量，根據(jù)式（11）對(duì)死鎖路徑的最后兩步進(jìn)行信息素懲罰；

步驟9當(dāng)所有螞蟻完成一個(gè)循環(huán)后，根據(jù)式（6）和（10）對(duì)搜索路徑進(jìn)行全局信息素更新；

步驟10搜索完成，判斷是否達(dá)到最大迭代次數(shù)，若k≠K，使k=k+1，清空禁忌表，跳轉(zhuǎn)到步驟3，繼續(xù)循環(huán)執(zhí)行；若k=K，則輸出最優(yōu)解，算法結(jié)束.

具體算法流程如圖4所示.

圖4 算法流程圖

3 仿真與分析

3.1 實(shí)驗(yàn)環(huán)境與條件假設(shè)為驗(yàn)證該算法的可行性和有效性，進(jìn)行了大量的仿真實(shí)驗(yàn)，并與傳統(tǒng)蟻群算法和文獻(xiàn)［15］提出了算法進(jìn)行了對(duì)比，驗(yàn)證了該算法的優(yōu)越性.仿真環(huán)境如下：Windows10 64位，處理器Intel（R）Core（TM）i7-8750U，主頻2.2 GHz，內(nèi)存16 GiB；仿真軟件：MatlabR2019b.

無(wú)人船的工作環(huán)境采用文獻(xiàn)［15］的工作環(huán)境，障礙物為工作環(huán)境中的靜態(tài)船舶、暗礁以及狹窄水域等，工作環(huán)境大小為30×30，起始點(diǎn)坐標(biāo)為（0.5，0.5），終點(diǎn)坐標(biāo)為（29.5，29.5），工作環(huán)境的柵格圖中小柵格的邊長(zhǎng)為1.

本文算法、傳統(tǒng)蟻群算法和文獻(xiàn)［15］中提出的算法在仿真時(shí)的螞蟻數(shù)量都為50只，最大迭代次數(shù)都是100次；

本文算法和文獻(xiàn)［15］提出的算法中的懲戒因子取值均為0.2.

3.2 仿真實(shí)驗(yàn)與結(jié)果分析蟻群算法參數(shù)選取合適與否直接關(guān)系到算法的效果，目前還沒(méi)有一種最合適的方法去直接確定參數(shù)的最優(yōu)組合.首先采用文獻(xiàn)［15］中設(shè)定的參數(shù)在文獻(xiàn)［15］的仿真環(huán)境下進(jìn)行仿真實(shí)驗(yàn)與文獻(xiàn)［15］以及傳統(tǒng)蟻群算法做對(duì)比，圖5～7為本次實(shí)驗(yàn)3種算法的結(jié)果對(duì)比，圖8中紅色虛線為傳統(tǒng)蟻群算法的規(guī)劃路徑，藍(lán)色實(shí)線為文獻(xiàn)［15］的規(guī)劃路徑，黑點(diǎn)為本文算法的規(guī)劃路徑，為了避免偶然情況，重復(fù)100次實(shí)驗(yàn)，平均結(jié)果如表1所示.

圖5 最優(yōu)路徑的變化曲線

圖8 3種算法規(guī)劃的最優(yōu)全局路徑

由表1可知，本文算法在采用文獻(xiàn)［15］中設(shè)定的參數(shù)組合時(shí)，與文獻(xiàn)［15］找到的最優(yōu)路徑都為44.526 9，優(yōu)于傳統(tǒng)蟻群算法找到的最優(yōu)路徑45.112 7.在收斂次數(shù)方面，本文算法經(jīng)過(guò)43.8次迭代后才收斂，文獻(xiàn)［15］經(jīng)過(guò)30.6次迭代就收斂，文獻(xiàn)［15］在損失螞蟻數(shù)量方面也優(yōu)于本文算法.因此，合適的參數(shù)組合對(duì)算法的性能有著關(guān)鍵作用.

表1 3種算法在路徑規(guī)劃中的結(jié)果比較

為了更加有效地找到合適的參數(shù)組合，通過(guò)對(duì)參數(shù)設(shè)置不同值進(jìn)行仿真分析，選擇最優(yōu)的參數(shù)組合.

每個(gè)參數(shù)設(shè)置5個(gè)數(shù)值，同時(shí)保持其他參數(shù)不變，對(duì)每個(gè)參數(shù)的數(shù)值進(jìn)行100次仿真，對(duì)算法結(jié)果求平均值進(jìn)行對(duì)比，本文測(cè)試的參數(shù)為信息素激勵(lì)因子α、期望啟發(fā)因子β和信息素?fù)]發(fā)系數(shù)ρ，進(jìn)行仿真實(shí)驗(yàn)，α，β，ρ的默認(rèn)值設(shè)置為α=1.5，β=8，ρ=0.5，其他參數(shù)設(shè)置為K=100，m=50，k0=5，Q=10，μ=0.2.經(jīng)過(guò)多次仿真實(shí)驗(yàn)，由表2參數(shù)仿真結(jié)果對(duì)比可以看出本文參數(shù)最優(yōu)組合為α=1.5，β=10，ρ=0.3.

表2 本文改進(jìn)的蟻群算法測(cè)試參數(shù)仿真結(jié)果對(duì)比表

圖6 最優(yōu)路徑的平均值變化曲線

圖7 丟失螞蟻數(shù)量的平均值變化曲線

在經(jīng)過(guò)實(shí)驗(yàn)找到適合本文算法的參數(shù)組合后，再在文獻(xiàn)［15］的仿真環(huán)境下進(jìn)行仿真并于文獻(xiàn)［15］及傳統(tǒng)蟻群算法進(jìn)行對(duì)比.圖9～11為本次實(shí)驗(yàn)3種算法的結(jié)果對(duì)比，圖12中紅色虛線為傳統(tǒng)蟻群算法的規(guī)劃路徑，藍(lán)色實(shí)線為文獻(xiàn)［15］的規(guī)劃路徑，黑點(diǎn)為本文算法的規(guī)劃路徑，為了避免偶然情況，重復(fù)100次實(shí)驗(yàn)，平均結(jié)果如表3所示.

圖9 3種算法最優(yōu)路徑比較

圖10 3種算法收斂比較

圖11 3種算法丟失螞蟻數(shù)量

圖12 3種算法的規(guī)劃路徑

表3 工作環(huán)境中3種算法仿真結(jié)果對(duì)比

由表3可以看出，傳統(tǒng)蟻群算法最優(yōu)路徑長(zhǎng)度為45.112 7，在仿真100次的情況下，平均迭代51.9次后才能找到最優(yōu)路徑，且在平均迭代92.5次后能收斂，最終收斂路徑長(zhǎng)度卻為46.458 3，極其不穩(wěn)定且丟失螞蟻數(shù)量多.文獻(xiàn)［15］算法和本文算法找到的最優(yōu)路徑均為44.526 9.在仿真100次的情況下，文獻(xiàn)［15］算法僅有3次最后收斂到最優(yōu)路徑，初期搜索效率的高低即為首次獲得最優(yōu)航行代價(jià)對(duì)應(yīng)的迭代次數(shù)的大小，文獻(xiàn)［15］算法在迭代16.5次后找到最優(yōu)路徑，本文算法僅迭代5.1次后便找到最優(yōu)路徑，尋優(yōu)能力提高了近三倍，解決了初期搜索效率低的問(wèn)題.收斂速度取決于全局收斂到最優(yōu)解的平均迭代次數(shù)，文獻(xiàn)［15］算法在迭代30.6次后收斂于45.468 3，本文算法在14.4次迭代后便可收斂，且收斂路徑為44.975 4，優(yōu)于文獻(xiàn)［15］算法，提高了算法的收斂速度.文獻(xiàn)［15］算法丟失螞蟻數(shù)量為336.2，本文算法丟失螞蟻數(shù)量為122.2，丟失螞蟻數(shù)量?jī)H占文獻(xiàn)［15］算法的三分之一，增加了方案的多樣性.在運(yùn)行時(shí)間方面，比傳統(tǒng)蟻群算法短了1.8 s，比文獻(xiàn)［15］算法節(jié)省約4 s.

綜上所述，本文算法與文獻(xiàn)［15］算法和傳統(tǒng)蟻群算法在2種環(huán)境進(jìn)行對(duì)比.在改變初始信息素濃度之后，加快螞蟻的尋優(yōu)速度；對(duì)于信息素濃度更新，加入權(quán)重因子可以加快螞蟻的收斂速度.文獻(xiàn)［15］算法對(duì)于信息素濃度的更新，是對(duì)最優(yōu)解增加信息素濃度、最壞解減少信息素濃度，其他路徑上信息素濃度不變，容易導(dǎo)致陷入局部最優(yōu)，找不到最優(yōu)解.對(duì)于死鎖問(wèn)題，文獻(xiàn)［15］算法對(duì)鎖死路徑最后兩步的信息素濃度進(jìn)行懲罰，減少了螞蟻經(jīng)過(guò)此路徑的概率.本文算法將鎖死路徑最后一步信息素濃度置0，在減少丟失螞蟻數(shù)量方面比文獻(xiàn)［15］算法有顯著效果，增加解的多樣性.因此，本文算法與其他算法相比，具有較大優(yōu)越性和實(shí)用性.

4 結(jié)束語(yǔ)

在解決無(wú)人船進(jìn)行水上作業(yè)時(shí)，如何規(guī)劃出一條初始點(diǎn)到終點(diǎn)的最優(yōu)路徑，在分析傳統(tǒng)蟻群算法的基礎(chǔ)上，針對(duì)搜索效率低、收斂速度慢等問(wèn)題，提出了一種改進(jìn)的蟻群算法，該算法具有以下優(yōu)點(diǎn)：

1）首先利用起點(diǎn)、當(dāng)前所在點(diǎn)、下一節(jié)點(diǎn)及終點(diǎn)所在位置，設(shè)置非均勻分布的初始信息素濃度，解決了初期搜索效率低的問(wèn)題；

2）引入權(quán)重因子，對(duì)信息素濃度更新公式進(jìn)行改進(jìn)，路徑越短，信息素濃度增加越多，加快了算法收斂到全局最優(yōu)的速度；

3）對(duì)于陷入鎖死路徑，使鎖死點(diǎn)信息素濃度置0，懲罰倒數(shù)第二步信息素濃度，減少了丟失螞蟻數(shù)量，增加了解的多樣性.

將本文算法與其他算法進(jìn)行比較，驗(yàn)證了該算法的有效性和優(yōu)越性，希望本文算法可以對(duì)后續(xù)進(jìn)行無(wú)人船路徑規(guī)劃算法研究的工作者帶來(lái)一定的幫助.下一步的工作重點(diǎn)為研究動(dòng)態(tài)避障算法，進(jìn)一步提高算法路徑規(guī)劃的能力.