改進蟻群算法在路徑規(guī)劃中的應用

摘 要：針對傳統(tǒng)蟻群算法在機器人路徑規(guī)劃時存在收斂速度慢、易陷入局部最優(yōu)等問題，提出了一種基于自適應歸檔更新的蟻群算法。根據(jù)路徑性能指標建立多目標性能評估模型，對最優(yōu)路徑進行多指標優(yōu)化；采用路徑方案歸檔更新策略進行路徑方案的更新和篩選，提高算法的收斂速度；當搜索路徑進入不可行區(qū)域時，采用自適應路徑補償策略轉(zhuǎn)移不可行路徑節(jié)點，構(gòu)造可行路徑，減少死鎖螞蟻數(shù)量；若算法無法避開障礙或者進入停滯狀態(tài)，則進行種群重新初始化，增加物種多樣性，避免算法陷入局部最優(yōu)。仿真實驗表明，改進后的算法收斂速度更快、收斂精度更高、穩(wěn)定性更好。

關鍵詞：蟻群算法；路徑規(guī)劃；多目標評估模型；歸檔更新；自適應路徑補償

中圖分類號：TP242.6 文獻標志碼：A 文章編號：1001-3695（2022）11-014-3292-06

doi： 10.19734/j.issn.1001-3695.2022.04.0189

Application of improved ant colony algorithm in path planning

Yang Beichen， Yu Su

（School of Electronic amp; Electronical Engineering， Shanghai University of engineering Science， Shanghai 201620， China）

Abstract：This paper proposed an ant colony algorithm based on adaptive archive updating to address the problems of the traditional ant colony algorithm in path planning， such as the tendency to fall into local optimum and slow convergence speed. It established the multi-objective performance evaluation model to optimize the optimal path based on path performance indicators. It used the archive updating strategy to update and filter path schemes， increased the convergence speed of the algorithm. It used the adaptive path compensation strategy to transfer the infeasible path nodes and constructed feasible paths to reduce the number of deadlocked ants when the search path entered the infeasible region. It performed the population reinitialization to increase species diversity and prevented the algorithm from falling into a local optimum， if the algorithm was unable to avoid obstacles or entered a stagnant state. The simulation results prove that the improved algorithm has faster convergence speed， higher convergence accuracy and better stability.

Key words：ant colony; route planning; multi-objective evaluation model; archive update; adaptive path compensation

基金項目：上海市科學技術委員會基金資助項目（17511110204）；國家科技部“十二五”支撐計劃資助項目（2015BAF10B00）

作者簡介：楊北辰（1994-），男，江蘇徐州人，碩士研究生，主要研究方向為機器人路徑規(guī)劃；余粟（1972-），女（通信作者），上海人，教授，碩導，碩士，主要研究方向為智能算法和移動機器人（yusu@sues.edu.cn）.

0 引言

隨著移動機器人在運輸、農(nóng)業(yè)、軍事和醫(yī)療等領域的廣泛應用，移動機器人的相關研究受到了越來越多的關注［1］。路徑規(guī)劃是移動機器人研究領域中的重要組成部分，其主要任務是構(gòu)建一條從初始位置到達目標位置的無碰撞路徑，同時滿足一些限制條件，如速度、轉(zhuǎn)向和安全距離等因素。與傳統(tǒng)基于先驗知識的路徑方法相比，具有智能路徑規(guī)劃算法的機器人能夠自動計算出可行的軌跡，在一定程度具有移動自主權(quán)［2］。

目前，已經(jīng)存在很多算法［3，4］應用在移動機器人路徑規(guī)劃中。隨著研究的深入，一些群智能優(yōu)化算法［5～7］也逐漸應用在路徑規(guī)劃中。群體智能優(yōu)化算法組織結(jié)構(gòu)分布式、行為主體獨立簡單、系統(tǒng)整體智能化等特點，在路徑規(guī)劃研究中比傳統(tǒng)算法更有優(yōu)勢。

其中，Dorigo等人［8］最早提出的傳統(tǒng)蟻群算法（ant colony system，ACS）具有算法結(jié)構(gòu)較為簡單、適應性較強、魯棒性較強等優(yōu)勢，更適用于機器人的路徑規(guī)劃研究。但是蟻群算法也存在著收斂速度較慢、容易陷入局部最優(yōu)等缺陷。因此，研究傳統(tǒng)蟻群算法并進行改進優(yōu)化，對移動機器人的路徑規(guī)劃研究有著非常重要的意義［9，10］。

針對傳統(tǒng)蟻群算法存在的缺陷和不足，國內(nèi)外學者提出了許多改進方案。何雅穎等人［11］通過引入反向?qū)W習信息素，改進算法的轉(zhuǎn)移概率，增強了算法的搜索能力；Zhao等人［12］提出一種歷史經(jīng)驗引導的信息素更新方法，利用學習自動機根據(jù)搜索歷史自適應地選擇合適的信息素，提高搜索效率，增強優(yōu)化質(zhì)量；陳禮琪［13］利用柵格地圖法改變蟻群算法的轉(zhuǎn)移概率，加入死區(qū)判斷策略，可以有效地減少“無效螞蟻”的數(shù)量，提高了算法的收斂速度；楊周等人［14］將蟻群算法與動態(tài)窗口算法進行結(jié)合，使用動態(tài)評價函數(shù)對局部路徑方向進行引導，幫助算法擺脫局部陷阱；張松燦等人［15］利用種群相似度對種群內(nèi)個體的多樣性進行度量，并根據(jù)優(yōu)化過程中種群相似度的變化情況自適應地調(diào)整蟻群算法的參數(shù)和信息素更新策略，從而提高算法的優(yōu)化性能；Liu等人［16］重新設計了全局信息素更新機制和信息素揮發(fā)系數(shù)，提出了一種自適應信息素波動系數(shù)更新機制，根據(jù)迭代次數(shù)動態(tài)調(diào)整信息素波動系數(shù)適應算法，使該算法在后期也能保持較強的全局搜索能力。

針對以上蟻群算法在路徑規(guī)劃中存在的問題，本文提出一種基于自適應歸檔更新的蟻群算法。通過建立多目標路徑性能評估模型，從多個約束角度構(gòu)建安全可靠的最優(yōu)路徑；采用路徑方案存檔更新策略代替?zhèn)鹘y(tǒng)蟻群算法的信息素更新方式，通過路徑的性能評估值來進行路徑方案的更新，提高最優(yōu)解的質(zhì)量和算法的收斂速度；使用自適應路徑修補策略轉(zhuǎn)移不可行路徑節(jié)點，構(gòu)造可行路徑，減少死鎖螞蟻數(shù)量；若算法無法避開障礙物或者陷入停滯狀態(tài)，對種群重新初始化，提高物種多樣性，避免算法陷入局部陷阱。

1 傳統(tǒng)蟻群算法路徑規(guī)劃

1.1 模擬環(huán)境

通過柵格法建立二維模擬環(huán)境，對環(huán)境中的不規(guī)則障礙物進行膨脹處理，統(tǒng)一成規(guī)則矩形，柵格地圖如圖1所示。S和E分別代表起點和目標點，黑色區(qū)域為障礙物區(qū)域，白色區(qū)域為可行區(qū)域，機器人R可以在八個相鄰的方向上移動。

1.2 傳統(tǒng)蟻群算法

傳統(tǒng)蟻群算法（ant colony system，ACS）中，每只螞蟻會根據(jù)路徑節(jié)點信息素的濃度和它們自身的偏好來選擇一條覓食路徑［17］。螞蟻選擇不同路徑的概率函數(shù)如下：

其中：α是信息素權(quán)重，α越大，信息素對蟻群的影響越大；β是啟發(fā)函數(shù)權(quán)重，β越大，啟發(fā)函數(shù)對蟻群的影響越大；τij（t）是信息素濃度函數(shù)；ηij（t）是啟發(fā)函數(shù)，表示螞蟻從i到j的可能性；allowedk是蟻群下一步可移動節(jié)點合集；dij為節(jié)點i到j的距離。

每次迭代結(jié)束，蟻群在經(jīng)過的路徑留下的信息素會進行衰減，用揮發(fā)系數(shù)ρ（0lt;ρlt;1）來進行螞蟻信息素的負反饋控制，更新信息素。

其中：N為蟻群數(shù)量；Q為信息素增量系數(shù)；Lk為螞蟻本次搜索經(jīng)過的路徑長度。

2 多目標路徑性能評估模型

在路徑規(guī)劃的研究過程中，傳統(tǒng)智能算法能夠在模擬環(huán)境中尋找到最短路徑，但是容易出現(xiàn)偽最優(yōu)路徑的情況，因為著重追求路徑長度的最短可能造成移動機器人與障礙物過近、部分路徑過于曲折等危險情況。因此，移動機器人的路徑規(guī)劃不能追求單純意義上的最短路徑，應當結(jié)合實際情況，考慮更多方面的路徑因素。

目前，移動機器人規(guī)劃的約束因素主要有路徑安全性、移動成本以及路徑性能三個方面。路徑安全性主要包括避免移動機器人與障礙物發(fā)生碰撞和風險最小化；移動成本通常包括路徑長度和轉(zhuǎn)彎次數(shù)。路徑的性能主要通過移動過程中的能耗進行體現(xiàn)。其中，某些約束因素（如路徑最短）是路徑規(guī)劃的研究目標，是評判路徑優(yōu)劣的基礎；而一些因素是路徑規(guī)劃研究中可行性評判標準，如避障性能和風險最小化，能夠確保最短路徑的可行性。當實際應用環(huán)境中機器人不能與障礙物發(fā)生碰撞時，避障性能就是一個重要的約束；當機器人必須要穿過障礙物時，風險最小化也會是一個重要約束。因此實際的應用環(huán)境不同，采用的約束種類不同。

綜合考慮路徑規(guī)劃過程中存在的多種約束因素，本文建立一種多目標路徑性能評估模型，從四個角度對路徑進行評估優(yōu)化，公式如下：

2.1 路徑長度指數(shù)

最短路徑是最優(yōu)路徑的基礎要素，是評估路徑的最重要參考指標。在實際應用中，路徑長度指數(shù)會直接影響移動機器人的運行時間，建立的長度指數(shù)Clength如下：

其中：n為路徑經(jīng)過的節(jié)點數(shù)量；Xi為路徑上第i個節(jié)點；（xi，yi）為Xi的坐標值；d（Xi，Xi+1）為Xi到Xi+1的歐氏距離；LSE為當前路徑總長度；dSE為路徑位置S到目標位置E的距離。最優(yōu)路徑越長，路徑長度指數(shù)越大，從而直觀上對路徑進行判斷。為了方便研究，所有評估指數(shù)的公式都采用歸一化方式建立。

2.2 路徑風險指數(shù)

Crisk為機器人所在環(huán)境中的風險指數(shù)，是移動機器人路徑安全的保障，公式如下：

其中：M為環(huán)境中危險區(qū)域的數(shù)量，Ldz為危險區(qū)域內(nèi)的路徑長度，dm為危險區(qū)域的長度。經(jīng)過危險區(qū)域的路徑越長，移動機器人風險指數(shù)越高。

2.3 路徑轉(zhuǎn)向指數(shù)

Cturn為機器人在環(huán)境中的轉(zhuǎn)向指數(shù)，指數(shù)越大，路徑越曲折，能耗增多；相反，指數(shù)越小，路徑越平滑，路徑穩(wěn)定性越好。

其中：K為路徑上經(jīng)過的節(jié)點數(shù)量，CTk為節(jié)點Xk的轉(zhuǎn)向指數(shù)。

2.4 路徑懲罰指數(shù)

Cpenalty為懲罰指數(shù)，用來判斷路徑是否在可行區(qū)域內(nèi)，并對進入非可行區(qū)域的路徑進行標記懲罰，計算公式如下：

其中：P為懲罰系數(shù)，懲罰系數(shù)的選擇與可行路徑的判斷指標相關。上述Clength、Crisk和Cturn三個評價指標為路徑規(guī)劃的優(yōu)化指標，指標取值皆為［0，1］。此時，可行路徑的判斷指標的取值在［0，3］。Lin feasible為路徑在非可行區(qū)域的路徑長度，路徑越長，機器人消耗越大；LSE為路徑總長度。

在實際應用中，機器人在不同環(huán)境下對不同的優(yōu)化指數(shù)的權(quán)重不同，如環(huán)境中的障礙物較多時，避障是路徑規(guī)劃的主要研究重點；當機器人需要經(jīng)過危險區(qū)域時，風險最小是路徑規(guī)劃的研究重點。此外，性能評估指數(shù)可能會與最短路徑產(chǎn)生沖突，例如，減少最短路徑長度會增加碰撞的風險，而減少碰撞的風險將會增加路徑的長度。因此，需要構(gòu)建安全性和最短路徑的平衡關系。本文采用加權(quán)的方法平衡各個性能參數(shù)，改進后多目標評估函數(shù)如下：

其中：λl、λr、λt和λp分別為各個路徑評估指數(shù)的權(quán)重。

3 改進蟻群算法

3.1 路徑方案歸檔更新策略

傳統(tǒng)蟻群算法是模擬螞蟻覓食行為的啟發(fā)式算法，在尋找食物源的過程中，螞蟻會在經(jīng)過的路徑留下信息素，而前面螞蟻留下的信息素會為后面的螞蟻提供路徑引導，指引螞蟻接下來的行進方向，因此，合理分配信息素對蟻群算法的運行有著極其重要的作用。而傳統(tǒng)蟻群算法中的信息素采用均勻分配機制，而且信息素按照固定的揮發(fā)速率進行揮發(fā)，不利于凸顯最優(yōu)解的優(yōu)勢，導致算法收斂速度較慢。目前針對信息素分配方式的優(yōu)化研究有很多，如文獻［12，13，16，18］。但是上述研究主要是優(yōu)化信息素的合理分配，通過建立不均勻的信息素分配機制，加快算法收斂速度來提高搜索效率，但并未從根本上解決信息素給最優(yōu)路徑帶來不穩(wěn)定影響，缺乏與實際環(huán)境的匹配，存在一定的局限性。

為了從根本上解決上述問題，本文提出一種方案歸檔更新策略來替代傳統(tǒng)的信息素更新方式。通過改變算法結(jié)構(gòu)構(gòu)建路徑方案存儲空間，并進行歸檔篩選，匹配最優(yōu)路徑方案。

3.1.1 路徑方案歸檔

方案歸檔的方法能夠?qū)⑼瓿上伻核阉髯顑?yōu)路徑過程中的路徑信息進行存儲，記錄在方案存儲區(qū)中，如圖2所示，每個路徑解決方案標記為Xi（i=1，…，k）。其中，每個解決方案由多個路徑評估變量組成，評估變量m越多，解決方案數(shù)學維度越大。此時，每一個解決方案可以表示為Xi={xmi，m=1，…，M}。在每次迭代結(jié)束時，添加大量新生成的解決方案并刪除相同數(shù)量的最差解決方案，從而完成路徑方案更新，替代傳統(tǒng)蟻群算法的信息素更新功能。解決方案的存檔數(shù)量能夠保持不變，但是路徑性能隨著方案更新越來越優(yōu)秀。在存檔中，所有解決方案都是根據(jù)其路徑性能優(yōu)劣進行分類排序，即Xi在所有解決方案中排在第i位，算法運行結(jié)束后的X1為最優(yōu)路徑方案Xbest=X1。

3.1.2 路徑方案更新

改進算法在每次迭代循環(huán)中使用n只螞蟻搜索最優(yōu)路徑，在每次迭代過程中每只螞蟻都會尋找到一個解決方案。為了更新存儲方案中的最優(yōu)路徑方案，采用隨機選擇概率的方式從原存檔方案中選擇一個解決方案作為基礎參考方案，記為Xbase，若新的方案的路徑性能優(yōu)于參考方案，則新的方案替代原本的參考方案。路徑更新如圖3所示。

每次迭代循環(huán)中基礎對比方案選擇概率的公式如下：

其中：δi為方案Xi的權(quán)重；q為算法參數(shù)，q值越大，選擇參考方案的概率越相似，q值越小，路徑較優(yōu)方案的選擇概率越大，更有利于算法中最優(yōu)路徑方案的更新。

為了提高新的路徑方案的抗擾動能力，在確定參考方案Xbase后，采用高斯突變策略構(gòu)造新的路徑方案，其中，高斯函數(shù)平均值為ηmi=xmi，標準差為σmi。此時，新的解決方案為

其中：當路徑方案維度為m時；σmi表示其他解決方案與參考方案性能差距的平均值；δ為收斂參數(shù)，影響算法收斂速度，δ值越大，算法收斂速度越慢。

3.2 自適應路徑補償策略

蟻群在路徑搜索時，可能會在地圖中的不可行區(qū)域構(gòu)造新的路徑方案，甚至新的路徑可能會超過地圖的邊界。通常這種問題的解決方式是將非可行區(qū)域內(nèi)的路徑點轉(zhuǎn)移到可行區(qū)域或者地圖環(huán)境中的隨機區(qū)域，但是也不能確保之后路徑的可行性，因此，這種方案的穩(wěn)定性較低，不適合在實際環(huán)境中應用。為了解決這種問題，減少蟻群尋找可行路徑的困難，本文提出一種自適應路徑補償策略，通過分析路徑的各個特征屬性，將不可行路徑節(jié)點轉(zhuǎn)移到可行區(qū)域內(nèi)進行路徑補償，提高可行路徑的數(shù)量。

在搜索過程中，路徑補償策略能夠自適應地為不可行區(qū)域中的路徑方案選擇最合適的修補方法。修補方法主要分為三種：a）隨機移動，將不可行區(qū)域中的路徑節(jié)點隨機移動到可行路徑區(qū)域中；b）上移，將不可行區(qū)域中的路徑節(jié)點轉(zhuǎn)移到y(tǒng)軸正方向上最近的一個可行節(jié)點；c）下移，將不可行區(qū)域中的路徑節(jié)點轉(zhuǎn)移到y(tǒng)軸負方向上最近的一個可行節(jié)點。

修補策略示意圖如圖4所示，其中，灰色柵格為不可行區(qū)域，空白柵格為可行區(qū)域，（a）為進入不可行區(qū)域的一段路徑，（b）～（d）分別代表上述C1、C2和C3三種路徑修補方式，將不可行路徑中的節(jié)點轉(zhuǎn)移到可行區(qū)域內(nèi)，構(gòu)造新的有效路徑。

圖4中，三種路徑修補方式都能將不可行路徑轉(zhuǎn)移到可行區(qū)域內(nèi)，但第一種方式的路徑明顯優(yōu)于其他兩種，因此，選擇合適的修補方式尤為重要。而修補方式的選擇取決于之前哪種方式能夠提高路徑的適應度值，即積累先驗經(jīng)驗Etj，計算公式為

其中：ft和ft－1分別為算法在第t次和t－1次迭代過程中的最佳適應度值，本文中f（X）=FC。在迭代次數(shù)為t時，路徑修補方式j的選擇概率為

其中：J為路徑補償方式的種類；本文中取J=3，Ej=1。

在算法初始階段，當蟻群陷入不可行區(qū)域時，算法會隨機選擇一種路徑補償方式進行修正，隨著時間的推移，在每一次迭代過程中，每種方式的先驗經(jīng)驗Etj不斷更新，不同修補方式的選擇概率也發(fā)生變化。如果修補后的路徑方案均不能優(yōu)于選擇的基礎方案Xbase，則所有方式的選擇概率重新初始化，回到最初階段。通過這種方式，改進算法能夠在進化過程中的不同階段自適應選擇高效路徑修補方式。

3.3 種群重新初始化

在尋找最優(yōu)路徑的過程中，若蟻群進入不可行區(qū)域或者陷入局部陷阱，此時，為了擺脫當前困境，重新尋找可行路徑，對種群進行重新初始化，在保障種群多樣性的同時，避免陷入局部最優(yōu)，從而達到種群多樣性收斂速度的平衡關系。當蟻群最優(yōu)解的適應度f高于懲罰系數(shù)P（P=3）時，代表本次最優(yōu)路徑為非可行路徑，將對種群重新初始化，初始化公式如下：

其中：lup和ldown分別為搜索環(huán)境的上邊界和下邊界。

3.4 改進算法流程

輸入：模擬環(huán)境、算法參數(shù)和評估函數(shù)FC=f（X）。

輸出：最優(yōu)路徑X1、 f（X1）。

a）隨機生成k條路徑方案。

b）計算每條路徑的適應度值，并進行排序。

c）根據(jù)式（17）（18）計算對比方案的選擇概率PXbase。

d）根據(jù)高斯變異策略（19）構(gòu)造n條路徑。

e）判斷路徑是否都在可行區(qū)域內(nèi)，并使用路徑補償策略修補不可行區(qū)域內(nèi)的節(jié)點路徑，構(gòu)造有效路徑。

f）在存檔空間中加入新的路徑方案Xnew，并刪除相同數(shù)量的路徑。

g）若遇到死鎖問題，對種群進行重新初始化。

h）每一次迭代循環(huán)都按照適應度值重新排序，直至到達最大迭代次數(shù)，此時，算法停止運行，輸出結(jié)果。

3.5 改進算法復雜度分析

表1為本文不同算法的復雜度對比，將本文改進算法與文［12］算法，傳統(tǒng)蟻群算法（ACS）、灰狼優(yōu)化算法（GWO）和麻雀搜索算法（SSA）進行對比分析，不同算法的時間復雜度均為Nc·m·n，從而驗證本文改進蟻群算法未增加算法的時間復雜度。

4 仿真實驗與分析

為了驗證本文改進蟻群算法的有效性，在Windows 10，MATLAB 2016b上進行實驗，將本文改進算法與傳統(tǒng)蟻群算法以及文獻［12］算法進行對比研究，基本參數(shù)設置如表2所示。

4.1 權(quán)重系數(shù)選擇

在多目標評估模型中，不同的性能指數(shù)的重要性存在區(qū)別，因此很難確定權(quán)重系數(shù)的具體值。為了方便研究，假定本文路徑經(jīng)過修補策略之后，路徑都在可行區(qū)域內(nèi)，此時，λp=0，主要研究其他三個路徑權(quán)重的影響。本文設置三個權(quán)重系數(shù)中的一個值設為1，另外兩個系數(shù)為0，來分析參數(shù)值對路徑的影響。同時，根據(jù)實驗結(jié)果建立以最短路徑指數(shù)為基準的平衡參數(shù)：λl=1；λr=min Clength/max Crisk；λt=min Clength/min Cturn。實驗結(jié)果如表3所示。

如表3所示，三個權(quán)重系數(shù)重要性有所不同，在應用平衡參數(shù)后，三個單目標權(quán)重系數(shù)區(qū)別較小，評估函數(shù)區(qū)別趨于平衡，有利于路徑評估。

4.2 改進策略有效性分析

本文通過引入方案歸檔更新策略和自適應路徑補償策略來提高蟻群算法在路徑規(guī)劃中的搜索能力。本節(jié)主要對改進蟻群算法的有效性進行驗證，文中的自適應路徑補償策略是以方案歸檔更新策略為基礎，因此，建立三種不同策略方案：a）ACS；b）ACS+歸檔更新策略；c）ACS+歸檔更新策略+自適應路徑補償策略。在相同的模擬環(huán)境中，分別進行10次重復實驗，實驗結(jié)果如表4所示。

4.2.1 歸檔更新策略分析

由表4可知，方案b）的最短路徑長度和收斂次數(shù)比方案a）分別減少了4.5%和26%，算法運算時間縮短了23%。傳統(tǒng)蟻群算法中，通過路徑上信息素的含量選擇可行路徑。在算法初期，信息素的分布較為均勻，螞蟻選擇不同路徑的概率差別較小，使得螞蟻選擇的路徑較多。而且，螞蟻會在經(jīng)過的路徑上留下新的信息素，導致路徑上的信息素不會有較大區(qū)別，因此，螞蟻無法快速選擇最優(yōu)路徑，影響算法收斂速度。在方案歸檔更新策略中，從第一代螞蟻開始，通過計算螞蟻路徑評估性能，將性能較好的路徑作為最優(yōu)路徑，此時的最優(yōu)路徑很有可能優(yōu)于傳統(tǒng)算法的第一代最優(yōu)路徑；隨著新路徑方案的產(chǎn)生，替代較差路徑，不斷更新方案存檔中的路徑方案，提高算法收斂速度。傳統(tǒng)蟻群算法需要通過信息素的不斷更新來催動螞蟻路徑尋找最優(yōu)路徑，而方案歸檔更新策略能夠直接對路徑進行篩選，并不斷更新最優(yōu)路徑，省去了傳統(tǒng)算法中信息素對路徑選擇的控制，因此，算法能夠較快收斂，得到性能較好的最優(yōu)路徑。

不同策略方案迭代曲線如圖5所示，方案a）中，螞蟻經(jīng)過較長迭代后得到最優(yōu)路徑，但是隨著最優(yōu)路徑信息素的迅速提高，其他路徑上的信息素含量不斷揮發(fā)，螞蟻搜索能力降低，不會繼續(xù)尋找其他潛在最優(yōu)路徑，而此時的最優(yōu)路徑中甚至會出現(xiàn)局部路徑較差的情況。方案b）和c）中，初始的路徑方案較多，經(jīng)過多個路徑方案更新后，算法能夠較快收斂，得到最優(yōu)路徑。

4.2.2 自適應路徑補償策略分析

圖6為在10次重復實驗中，三種方案中死螞蟻數(shù)量統(tǒng)計。可以明顯看出方案c）中死鎖螞蟻數(shù)量遠少于其他兩種方案。方案a）中，受到信息素均勻分布和障礙物的影響，螞蟻在初期很容易陷入局部陷阱，導致死鎖螞蟻數(shù)量較多；方案b）中，在路徑方案更新階段，路徑方案產(chǎn)生變異，容易導致部分節(jié)點陷入障礙物區(qū)域，存在部分死鎖螞蟻，但數(shù)量低于方案a）。方案c）是對方案b）的優(yōu)化，將方案b）中的無效死鎖路徑轉(zhuǎn)移到可行路徑中，減少死鎖螞蟻。由表4中死鎖螞蟻的數(shù)量可以明顯看出，自適應路徑修補策略針對方案b）中的死鎖路徑進行了有效修正，修正準確率達到66%，驗證了自適應修補策略的有效性。

4.2.3 改進算法個體分布情況分析

為了研究本文改進算法的蟻群分布情況，列出蟻群在不同迭代時刻的個體分布，如圖7所示。本文改進算法中，蟻群主要分為搜索蟻和變異蟻兩類。搜索蟻主要負責螞蟻前期的路徑探索，搜索蟻的數(shù)量越多，尋找到可行路徑的數(shù)量越多；變異通過高斯變異提高對重點區(qū)域的搜索功能，變異蟻的數(shù)量越多，算法搜索能力越強，可行路徑的性能越好。

圖5中，由于方案歸檔更新策略，搜索蟻和變異蟻的數(shù)量隨著迭代次數(shù)的增加而發(fā)生動態(tài)變化。在算法初期，探索蟻的數(shù)量較多，算法搜索能力較強，收斂到一條較優(yōu)路徑，變異蟻在這時也發(fā)揮作用，提高對次優(yōu)路徑的搜索，提高算法多樣性，避免陷入局部最優(yōu)。在算法中期，兩種螞蟻數(shù)量趨于平衡，變異蟻數(shù)量增多，繼續(xù)提高次優(yōu)路徑的搜索，加快算法收斂。在算法后期，變異蟻發(fā)揮主要作用，繼續(xù)尋找次優(yōu)路徑，優(yōu)化局部路徑。因此，改進算法既能加快算法收斂，又能保持物種多樣性，有效平衡收斂速度和物種多樣性的矛盾。

4.3 不同算法實驗對比

為了驗證本文改進算法的有效性，建立20×20和40×40的模擬環(huán)境，將ACS、文獻［12］算法和本文改進算法在模擬環(huán)境中進行對比實驗。

4.3.1 20×20模擬環(huán)境

20×20模擬環(huán)境中的實驗結(jié)果如圖8、9所示。

在20×20環(huán)境地圖中，傳統(tǒng)蟻群算法收斂速度較慢，容易陷入局部陷阱，主要原因是：傳統(tǒng)蟻群算法信息素分布較為平均，最優(yōu)路徑的反饋能力較差；啟發(fā)信息對路徑的引導僅限于下一局移動節(jié)點，移動方向與最優(yōu)路徑方向關聯(lián)較低，容易獲得局部最優(yōu)路徑，且隨著算法運行，局部路徑信息素增多，易陷入局部陷阱。PSO算法搜索隨機性較強，無法快速收斂，路徑搜索能力低于其他算法。本文改進算法的收斂速度明顯優(yōu)于傳統(tǒng)算法和文獻［12］算法，最優(yōu)路徑分別比傳統(tǒng)算法和文獻［12］算法縮短了6.8%和4.7%，收斂速度分別比傳統(tǒng)算法和文獻［12］算法加快了48%和19%。雖然文獻［12］算法對信息素進行了重新分配，自適應調(diào)整信息素的分布，但最短路徑仍高于本文改進算法。本文改進蟻群算法通過方案歸檔存儲策略，保存較優(yōu)路徑方案，并通過變異策略優(yōu)化局部路徑，不斷更新較優(yōu)路徑，舍棄較差路徑，使得算法收斂速度加快，收斂精度提高，穩(wěn)定性更高。表5中，本文改進算法的標準差均低于其他三種算法，表明本文改進算法具有較高收斂精度。由此，驗證了本文改進算法在簡單環(huán)境具有較強的路徑搜索能力，同時保持較快的收斂速度和較高的收斂精度。

從圖10可以看出，在算法初期，在搜索環(huán)境較大，障礙分布比較密集的情況下，傳統(tǒng)蟻群路徑和PSO算法缺乏準確信息引導，無法快速收斂至最優(yōu)路徑；文獻［12］算法和本文改進算法都能快速收斂至最優(yōu)路徑，但本文改進算法優(yōu)于文獻［12］算法，迭代次數(shù)分別比傳統(tǒng)算法和文獻［12］算法縮短了55%和17%，最優(yōu)路徑分別比傳統(tǒng)算法和文獻［12］算法減少了8.3%和1.8%。雖然環(huán)境復雜程度增大，但是本文改進策略并未受到環(huán)境的影響，仍然保持較高的搜索效率，驗證了本文改進算法在復雜環(huán)境中的有效性和適用性。由表6可知，本文改進算法的標準差均低于其他三種算法，收斂精度相對較高，表明本文改進蟻群算法在復雜環(huán)境中也能保持較快的收斂速度和較高的收斂精度。

綜上，通過不同環(huán)境中的模擬實驗，驗證了本文改進算法的有效性和穩(wěn)定性，在不同環(huán)境中均能保持較快收斂速度和較高收斂精度。

4.4 算法多樣性分析

蟻群算法解的多樣性是指在每一次的迭代循環(huán)中螞蟻搜索到的不同路徑的數(shù)量，能夠直觀體現(xiàn)算法尋找最優(yōu)解的能力，搜索解多樣性越好，螞蟻搜索到的不同路徑數(shù)量越多，全局尋優(yōu)能力越強。

以最優(yōu)解的標準差為參考，建立多樣性函數(shù)DIV（N）如下：

其中：Lnk為螞蟻k在當前迭代循環(huán)n中搜索的路徑長度；Ln為所有螞蟻搜索路徑長度的平均長度。將本文改進算法與ACS、文獻［12］算法進行對比，結(jié)果如圖12所示。

由圖12可知，隨著迭代次數(shù)增加，傳統(tǒng)蟻群算法的DIV（N）值逐漸減小至0，這表明傳統(tǒng)蟻群算法無法保持較好的多樣性解，存在陷入停滯狀態(tài)的風險；文獻［12］和本文改進蟻群算法的DIV（N）值都能保持在穩(wěn)定值，但是本文改進算法的DIV（N）值高于文獻［12］算法，這表明本文改進蟻群算法具有更好的多樣性解，能夠有效避免算法陷入停滯狀態(tài)，具有較強的全局搜索性能。

5 結(jié)束語

針對傳統(tǒng)蟻群算法在機器人路徑規(guī)劃時存在收斂速度慢、易陷入局部最優(yōu)等問題，本文提出了一種基于自適應歸檔更新的改進蟻群算法。通過建立多目標路徑性能評估模型，在保證路徑最短的基礎上，對最優(yōu)路徑進行多指標優(yōu)化；采用路徑方案歸檔更新策略代替?zhèn)鹘y(tǒng)蟻群算法的信息素更新方式，提高了算法的收斂速度；使用自適應路徑修補策略以及種群重新初始化，提高物種多樣性，避免算法陷入局部最優(yōu)。通過不同算法的對比實驗，驗證了本文改進算法有效性和適用性。在接下來的研究中，會嘗試將本文改進蟻群算法應用在多機器人路徑規(guī)劃中，同時也會考慮與其他仿生算法進行結(jié)合，進一步對傳統(tǒng)蟻群算法進行改進。

參考文獻：

［1］陳德童，劉賢達，劉生偉. 基于雙向搜索改進A*算法的自動導引車路徑規(guī)劃 ［J］. 計算機應用，2021，41（S2）： 309-313. （Chen Detong，Liu Xianda，Liu Shengwei. Automatic guided vehicle path planning based on two-way search and improved A* algorithm ［J］. Computer Applications，2021，41（S2）： 309-313.）

［2］Kumar S，Sikander A. Optimum mobile robot path planning using improved artificial bee colony algorithm and evolutionary programming ［J］. Arabian Journal for Science and Engineering，2022，47（3）： 3519-3539.

［3］陳繼清，譚成志，莫榮現(xiàn)，等. 基于人工勢場的A*算法的移動機器人路徑規(guī)劃 ［J］. 計算機科學，2021，48（11）： 327-333. （Chen Jiqing，Tan Chengzhi，Mo Rongxian，et al. Path planning of mobile robots based on A* algorithm based on artificial potential field ［J］. Computer Science，2021，48（11）： 327-333.）

［4］劉惟恒，鄭辛，鄧志紅. 基于歸一化人工勢場算法的固定翼無人機群動態(tài)航跡規(guī)劃 ［J］. 中南大學學報： 英文版，2021，28（10）： 3159-3172. （Liu Weiheng，Zheng Xin，Deng Zhihong. Dynamic tra-jectory planning of fixed-wing UAV swarms based on normalized artificial potential field algorithm ［J］. Journal of Central South University： English，2021，28（10）： 3159-3172.）

［5］宋玉龍，王磊，武欣嶸，等. 基于模擬退火自適應粒子群算法的WSN拓撲抗毀性方法研究 ［J］. 信息網(wǎng)絡安全，2021，21（6）： 89-96. （Song Yulong，Wang Lei，Wu Xinrong，et al. Research on WSN topology invulnerability method based on simulated annealing adaptive particle swarm optimization ［J］. Information Network Security，2021，21（6）： 89-96.）

［6］劉雙雙，黃宜慶. 多策略蟻群算法在機器人路徑規(guī)劃中的應用 ［J］. 計算機工程與應用，2022，58（6）： 278-286. （Liu Shuangshuang，Huang Yiqing. Application of multi-strategy ant colony algorithm in robot path planning ［J］. Computer Engineering and Applications，2022，58（6）： 278-286.）

［7］Zhang Zhi，He Rong，Yang Kun. A bioinspired path planning approach for mobile robots based on improved sparrow search algorithm ［J］. Advances in Manufacturing，2021，10： 114-130.

［8］Dorigo M，Maniezzo V. Ant system： optimization by a colony of coope-rating agents ［J］. IEEE Trans on SMC-Part B，1996，26（1）： 29-41.

［9］Xue Jiankai，Shen Bo. A novel swarm intelligence optimization approach： sparrow search algorithm ［J］. Systems Science amp; Control Engineering，2020，8（1）： 22-34.

［10］Zhao Jiabo，You Xiaoming，Duan Qianqian，et al. Multiple ant colony algorithm combining community relationship network ［J］. Arabian Journal for Science and Engineering，2022，47（8）：11-16.

［11］何雅穎，范昕煒. 改進蟻群算法在機器人路徑規(guī)劃中的應用 ［J］. 計算機工程與應用，2021，57（16）： 276-282. （He Yaying，F(xiàn)an Xinwei. Application of improved ant colony algorithm in robot path planning ［J］. Computer Engineering and Applications，2021，57（16）： 276-282.）

［12］Zhao Haitong，Zhang Changsheng. An ant colony optimization algorithm with evolutionary experience-guided pheromone updating strategies for multi-objective optimization ［J］. Expert Systems with Applications，2022，201（9）：117151 .

［13］陳禮琪. 基于改進蟻群算法的無人機路徑規(guī)劃 ［J］. 計算機與數(shù)字工程，2022，50（3）：538-543. （Chen Liqi. UAV path planning based on improved ant colony algorithm ［J］. Computer and Digital Engineering，2022，50（3）： 538-543.）

［14］楊周，劉海濱. 基于改進蟻群與動態(tài)窗口法的AGV動態(tài)路徑規(guī)劃 ［J］. 計算機工程與應用，2022，58（6）： 287-295. （Yang Zhou，Liu Haibin. AGV dynamic path planning based on improved ant colony and dynamic window method ［J］. Computer Enginee-ring and Applications，2022，58（6）： 287-295.）

［15］張松燦，普杰信，司彥娜，等. 基于種群相似度的自適應改進蟻群算法及應用 ［J］. 計算機工程與應用，2021，57（8）： 70-77. （Zhang Songcan，Pu Jiexin，Si Yanna，et al. Adaptive improved ant colony algorithm and application based on population similarity ［J］. Computer Engineering and Applications，2021，57（8）： 70-77.）

［16］Liu Xiangde，Tang Wen. Logistics robot path planning based on adaptive ant colony algorithm ［C］// Proc of the 6th Information Techno-logy and Mechatronics Engineering Conference.2022： 552-557.

［17］張毅，李奎，黃超. 基于改進蟻群算法的二維碼移動機器人路徑規(guī)劃方法 ［J］. 重慶郵電大學學報： 自然科學版，2021，33（3）： 491-497. （Zhang Yi，Li Kui，Huang Chao. A two-dimensional code mobile robot path planning method based on improved ant colony algorithm ［J］. Journal of Chongqing University of Posts and Telecommunications： Natural Science，2021，33（3）： 491-497.）

［18］Zhang Yi，Pang Dashuai. Research on path planning of mobile robot based on improved ant colony algorithm ［C］// Proc of the 6th Information Technology and Mechatronics Engineering Conference. 2022： 558-563.