摘要： 針對(duì)蟻群算法在復(fù)雜環(huán)境下難以收斂、最優(yōu)值差的問題，提出了一種改進(jìn)蟻群算法。引入修正策略，提出兩種局部修正方法以減少無效路徑。提出一種自適應(yīng)信息素更新機(jī)制，將初始信息素與螞蟻所釋放的信息素區(qū)分揮發(fā)；針對(duì)每次迭代螞蟻所釋放的信息素，通過設(shè)計(jì)時(shí)變揮發(fā)因子的變化律單獨(dú)揮發(fā)，得到自適應(yīng)揮發(fā)強(qiáng)度的信息素?fù)]發(fā)機(jī)制。最后，將算法應(yīng)用到不同復(fù)雜環(huán)境，與已有改進(jìn)蟻群算法對(duì)比分析，研究結(jié)果說明改進(jìn)算法在有效時(shí)間、平均距離、最短距離的優(yōu)越性。

關(guān)鍵詞： 蟻群算法；改進(jìn)蟻群算法；全局優(yōu)化；路徑規(guī)劃

中圖分類號(hào)： TP18;TP29文獻(xiàn)標(biāo)識(shí)碼： A

Complex Environment Path Planning Based on an Improved Ant Colony Algorithm

YANG Junqi， LIU Feiyang， ZHANG Hongwei

（School of Electrical Engineering and Automation， Henan Key Laboratory of Intelligent Detection and Control of Coal Mine Equipment， Henan Polytechnic University， Jiaozuo 454003， China）

Abstract：This paper proposes an improved ant colony algorithm to solve the problem of slow and poor convergence. First， a correction strategy is introduced， which includes two local correction methods to reduce invalid paths. Second， an adaptive pheromone updating mechanism is developed to distinguish and volatilize the initial pheromone from the pheromone released. For the pheromone released in each iteration， a change law of time-varying volatilization factor is designed to volatilize independently and obtain pheromone volatilization mechanism with adaptive volatilization intensity. Finally， the proposed algorithm is applied to mobile robot path planning. Compared with the existing improved ant colony algorithms， the results show that the improved algorithm is excellent in terms of effective time， average distance and shortest distance.

Keywords： ant colony algorithm; improved ant colony algorithm; global optimization; path planning

0 引言

蟻群算法是一種群體智能仿生算法［15］，具有并行處理、分布式計(jì)算、魯棒性強(qiáng)等優(yōu)點(diǎn)，主要解決路徑規(guī)劃問題以及NP難問題，但仍有收斂速度慢、易停滯、有可能陷入局部優(yōu)化等缺點(diǎn)。為了提高算法性能，研究人員做了一些改進(jìn)［620］。Hou等［6］擴(kuò)大輪盤賭算法加速收斂，設(shè)計(jì)自適應(yīng)S型衰減曲線優(yōu)化啟發(fā)函數(shù)。Tian等［9］采用多步搜索策略替代單步搜索策略，以提高算法性能。文獻(xiàn)［1112］通過調(diào)整網(wǎng)絡(luò)中的初始信息素含量，提升了算法的性能以及收斂速度。文獻(xiàn)［13］設(shè)計(jì)了一種改進(jìn)蟻群算法，將原有的二維平面搜索路線空間擴(kuò)展到三維空間。文獻(xiàn)［14］在蟻群算法中引入Q-Learning，使蟻群具有自學(xué)習(xí)能力，用以解決矩陣排樣問題。文獻(xiàn)［1718］從增強(qiáng)搜索能力的角度改進(jìn)蟻群算法，提升了算法的收斂速度。

上述方法雖然性能有了改進(jìn)，但對(duì)于復(fù)雜的環(huán)境模型仍會(huì)出現(xiàn)收斂慢、結(jié)果差的問題。如文獻(xiàn)［15］，雖然增大了螞蟻的視野、提高了算法的收斂結(jié)果，但對(duì)于更加復(fù)雜的環(huán)境，螞蟻視野有限，難以跳出局部最優(yōu)陷阱。文獻(xiàn)［20］利用歷史路徑整合螞蟻路徑，達(dá)到螞蟻間通信的目的，從而減少曲折路徑。但上述結(jié)果對(duì)于更加復(fù)雜的環(huán)境，由于螞蟻數(shù)量有限、歷史路徑不能覆蓋整個(gè)環(huán)境模型，會(huì)出現(xiàn)難以收斂、最短路徑結(jié)果不好的問題。本文基于文獻(xiàn)［20］整合歷史路徑的思路，提出了一種修正策略，該策略能夠修正螞蟻路徑，減少曲折路線信息素的干擾，最終提升算法收斂速度和收斂結(jié)果。此外，本文提出了一種自適應(yīng)揮發(fā)強(qiáng)度的信息素?fù)]發(fā)機(jī)制，增強(qiáng)了算法性能。修正策略修正曲折路線后，減少曲折路線對(duì)螞蟻的干擾，增強(qiáng)算法的收斂速度。同時(shí)該路徑上信息素濃度會(huì)增強(qiáng)，降低了螞蟻的搜索性，而設(shè)計(jì)的信息素更新機(jī)制中揮發(fā)強(qiáng)度與信息素濃度正相關(guān)，解決了局部路徑信息素濃度過高的問題。

針對(duì)蟻群算法復(fù)雜環(huán)境難以收斂的問題，引入修正策略和自適應(yīng)揮發(fā)強(qiáng)度的信息素更新機(jī)制。主要工作包括：1）引入修正策略，解決螞蟻路線曲折路徑過多的問題；2）設(shè)計(jì)了一種全新的信息素更新機(jī)制，使得信息素?fù)]發(fā)強(qiáng)度與信息素濃度正相關(guān)，增強(qiáng)算法魯棒性和搜索能力；3）用改進(jìn)蟻群算法解決復(fù)雜環(huán)境路徑規(guī)劃問題，并且與基本蟻群算法和文獻(xiàn)［15］、［20］在不同復(fù)雜環(huán)境下對(duì)比分析，證明本文算法性能優(yōu)秀。

1 問題描述

1.1 環(huán)境建模

多柵格地圖法是對(duì)路徑規(guī)劃最普遍的方法。首先，對(duì)真實(shí)環(huán)境進(jìn)行取樣，膨脹化處理取樣圖形，使之占滿整個(gè)柵格，令所有觸碰到障礙物的柵格全部按照障礙物處理。如圖1所示，環(huán)境空間被分割為兩個(gè)部分，白色網(wǎng)格為可達(dá)空間，黑色網(wǎng)格為不可達(dá)空間。按照從左到右、從上到下的排序方式，對(duì)環(huán)境空間網(wǎng)格進(jìn)行排序。此外，根據(jù)障礙物數(shù)量和大小可分割成不同維度的環(huán)境模型，節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移方向若無障礙物，則8個(gè)方向均可達(dá)。如圖2中的節(jié)點(diǎn)5，因節(jié)點(diǎn)6、8不可達(dá)，則節(jié)點(diǎn)9因障礙物遮擋不可達(dá)。

1.2 基本蟻群算法

假設(shè)m只螞蟻在具有n節(jié)點(diǎn)的網(wǎng)絡(luò)中尋找食物，根據(jù)狀態(tài)轉(zhuǎn)移概率公式選擇前進(jìn)路徑。用Pij表示某只螞蟻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的轉(zhuǎn)移概率，即

Pijt=τijtαηijtβ∑l∈allowediτiltαηiltβ， l∈allowedi0， lallowedi（1）

其中，allowedi為i節(jié)點(diǎn)下一步允許選擇的節(jié)點(diǎn)集。α為信息素啟發(fā)因子，β為啟發(fā)函數(shù)啟發(fā)因子，τijt為t時(shí)刻節(jié)點(diǎn)i到節(jié)點(diǎn)j的信息素濃度。考慮t時(shí)刻節(jié)點(diǎn)i到節(jié)點(diǎn)j的如下常量啟發(fā)函數(shù)ηijt=ηij=1dij，其中dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的歐式距離。記蟻群路徑網(wǎng)絡(luò)啟發(fā)矩陣為η=ηij∈Rn×n。

螞蟻完成一次循環(huán)后信息素濃度的更新規(guī)則：

τijt=1-ρτijt+Δτijt

其中，0<ρ<1為信息素?fù)]發(fā)系數(shù)，1-ρ是信息素殘留系數(shù)。記信息素矩陣τt=τijt∈Rn×n。Δτijt為節(jié)點(diǎn)i到節(jié)點(diǎn)j的信息素增加量，即所有M只螞蟻經(jīng)節(jié)點(diǎn)i到節(jié)點(diǎn)j釋放的信息素之和，那么

Δτijt=∑Mk=1Δτkijt（2）

這里Δτkijt=QLkt為螞蟻k釋放的信息素，其中Q為信息素強(qiáng)度系數(shù)，Lkt為螞蟻k所走路徑的長度。

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

2.1 引入修正策略

螞蟻迭代中，因初期環(huán)境模型初始信息素濃度一致，導(dǎo)致式（1）中僅有啟發(fā)信息對(duì)螞蟻前進(jìn)起指導(dǎo)作用。所以，在復(fù)雜環(huán)境中，初期螞蟻路徑會(huì)出現(xiàn)許多如圖3所示的曲折路線，誤導(dǎo)螞蟻爬行，影響算法收斂。因此，本文引入修正策略能夠修正曲折路徑，加快螞蟻在復(fù)雜環(huán)境收斂速度（見圖4）。如圖3所示的3×3環(huán)境模型中移動(dòng)，初始地為1，目的地為78a98d07a5021a90d6a6776c7389e820fab0c0a1a69314278ba15794470f81253。某只螞蟻在初次迭代搜索出的路徑為1→5→3→2→4→7，此時(shí)最短路徑為1→4→7，多行路徑為5→3→2。

2.1.1 節(jié)點(diǎn)修正

設(shè)某只螞蟻搜索到的路徑節(jié)點(diǎn)表示為集合Θpath，pathn為該螞蟻搜索到路徑的節(jié)點(diǎn)n，該節(jié)點(diǎn)下一步可轉(zhuǎn)移的節(jié)點(diǎn)集合為allowpathn，I表示Θpath與allowpathn交集后的集合，Li為I中的節(jié)點(diǎn)i與節(jié)點(diǎn)n在路徑Θpath上的長度，即

I=Θpath∩allowpathn（3）

Li=length（i-n）（4）

其中，i為節(jié)點(diǎn)，且i∈I，length為計(jì)算節(jié)點(diǎn)i到節(jié)點(diǎn)pathn的長度。

給定路線圖3和節(jié)點(diǎn)n=1修正策略示意圖4，易知Θpath= 5，3，2，4，7和allowpathn=2，4，5，則由式（3）可得I=2，4，5。利用式（4）得L2≈3.828、L4≈5.242、L5≈1.414，易知L4為最大值，其所對(duì)應(yīng)的節(jié)點(diǎn)為i=4，則節(jié)點(diǎn)1到節(jié)點(diǎn)4之間的路徑長度最長。由于節(jié)點(diǎn)1可直接到達(dá)節(jié)點(diǎn)4，此時(shí)刪除節(jié)點(diǎn)1～4之間的所有節(jié)點(diǎn)2，3，5，即完成對(duì)節(jié)點(diǎn)1的修正。

2.1.2 取直修正

螞蟻搜索出的路徑因全局性能力不足，會(huì)導(dǎo)致路徑中出現(xiàn)一些如圖5所示的曲折路徑。

為優(yōu)化路徑，以下提出一種取直修正策略。假設(shè)螞蟻只能在橫向、縱向、斜向的搜索方向爬行，以圖5a為例，螞蟻所搜路徑中的某一段為123。顯然，節(jié)點(diǎn)2是造成曲折路徑的主要原因，若螞蟻路徑修正為143，則減少了路徑的曲折路線。圖5a中，13符合取直修正，若節(jié)點(diǎn)13連線之間存在障礙物，則13因障礙物遮擋不可直達(dá)，此時(shí)這兩節(jié)點(diǎn)無法取直修正，選擇其他節(jié)點(diǎn)繼續(xù)進(jìn)行修正策略。

2.2 修正策略的執(zhí)行步驟

在改進(jìn)算法的設(shè)計(jì)中，若對(duì)每一次迭代產(chǎn)生的路徑都進(jìn)行修正策略，則會(huì)花費(fèi)較多時(shí)間。當(dāng)蟻群算法收斂以后，則不必再進(jìn)行路徑修正，因此定義參數(shù)N0限定修正策略執(zhí)行次數(shù)以降低算法時(shí)間。

改進(jìn)算法入口參數(shù)為某只螞蟻搜索路徑Θpath和環(huán)境模型矩陣G，返回優(yōu)化后的路徑Θ′path。算法如下：

步驟1：初始化參數(shù)。計(jì)算矩陣G的鄰接矩陣D，定義計(jì)數(shù)器c1=1、c2=3。

步驟2：while（1）循環(huán)，為節(jié)點(diǎn)修正。若c1小于路徑Θpath長度，從鄰接矩陣D中找出螞蟻下一步可選擇節(jié)點(diǎn)allowpath（c1）。由式（3）、（4）得Li、I，并得出imax使得Limax最大。從路徑Θpath中刪除c1-imax節(jié)點(diǎn)；若c1等于路徑Θpath長度，令c1=1退出該循環(huán)，完成節(jié)點(diǎn)修正。

步驟3：while（1）循環(huán)，遍歷節(jié)點(diǎn)X，為取直修正外層循環(huán)。若c1+2、c2皆等于路徑Θpath長度，則退出該層循環(huán)。否則進(jìn)入步驟4。

步驟4：while（1）循環(huán)，遍歷節(jié)點(diǎn)Y，為取直修正內(nèi)層循環(huán)。若c2等于路徑Θpath長度，則令c1=c1+1進(jìn)入步驟3；否則，進(jìn)入步驟5。

步驟5：判斷X、Y是否符合2.1.2小節(jié)中的取直方式。若不符合，則令c2=c2+1進(jìn)入步驟4；若符合，則按照2.1.2小節(jié)修正Θpath，令c2=c1+2并進(jìn)入步驟3。

步驟6：Θ′path=Θpath，結(jié)束算法。

2.3 修正策略效果

在30×30環(huán)境模型中，圖6為某條路徑修正示意圖，虛線為未修正路徑，實(shí)線為修正后路徑。從圖6中可以看出經(jīng)修正后減少了許多曲折路線，從而降低了螞蟻的爬行距離。如坐標(biāo)0.5，29.5經(jīng)節(jié)點(diǎn)修正后的路徑為0.5，29.5-0.5，28.5，右側(cè)虛線多行路徑被修正，坐標(biāo)9.5，13.5、12.5，12.5、13.5，12.5等同樣為節(jié)點(diǎn)修正。在取直修正部分，坐標(biāo)3.5，21.5和3.5，19.5符合圖5b縱向取直，采用取直修正，坐標(biāo)組合1.5，13.5與6.5，13.5、7.5，13.5與9.5，13.5等，都符合圖5中的取直方式，因此用取直路徑替代原路徑。

2.4 自適應(yīng)揮發(fā)強(qiáng)度的信息素更新機(jī)制

在基本蟻群算法中，信息素?fù)]發(fā)因子ρ決定信息素留在一條路徑上的時(shí)間和強(qiáng)度，合適的信息素?fù)]發(fā)機(jī)制很大程度上影響螞蟻的搜索效率，本文提出了一種自適應(yīng)揮發(fā)強(qiáng)度的信息素更新機(jī)制。

定義初始信息素?fù)]發(fā)為

σijt=1-ρσijt-1（5）

其中，t=，…，n，σij0為初始信息素值，σijt為初始信息素在第t次迭代時(shí)的值。記σt=σijt∈Rn×n為揮發(fā)后的初始信息素矩陣。螞蟻所釋放的信息素因子隨迭代次數(shù)的變化律設(shè)計(jì)為

ρt=ε-t-t0+ρ0，t>00，t=0（6）

其中，ρ0和t0是常量參數(shù)，參數(shù)ε>1確保ρt是關(guān)于t的單調(diào)減函數(shù)。

在式（2）中，表示Δτt=Δτijt∈Rn×n，且隨迭代次數(shù)而形成的信息素矩陣集定義為

Αt=Δτ Δτ2，Δτ3，…，Δτt。

對(duì)于任意給定Δτk∈At，結(jié)合（6）式給出t時(shí)刻信息素?fù)]發(fā)公式：

ζk=1-ρt-kΔτk（7）

其中，ζk為揮發(fā)后的信息素矩陣。則揮發(fā)后信息素矩陣集為

Βt=ζ ζ2，ζ3，…，ζt

對(duì)于當(dāng)前迭代時(shí)間t，依據(jù)式（2）、（5）和（7），構(gòu)造如下全局信息素更新律：

τt=σt+∑t-1i=1ζi+Δτt

其中，σt為揮發(fā)后的初始信息素矩陣，∑t-1i=1ζi為揮發(fā)后螞蟻釋放的信息素矩陣之和，Δτt表示螞蟻此次迭代釋放的信息素矩陣。

改進(jìn)蟻群算法的流程如圖7所示，其中k為當(dāng)前迭代次數(shù)，i為當(dāng)前螞蟻，K為最大迭代次數(shù)，M為螞蟻數(shù)量，N0為改進(jìn)算法限制參數(shù)。

3 仿真

為驗(yàn)證算法性能，引入文獻(xiàn)［15］、［20］和基本蟻群算法與本文算法對(duì)比。算法運(yùn)行環(huán)境為：Windows10 64bit；處理器AMD Ryzen 7 5800H；主頻3.2GHz；內(nèi)存16GB；仿真平臺(tái)Matlab R2022a。

3.1 實(shí)驗(yàn)參數(shù)測定

蟻群算法中的主要參數(shù)耦合性很強(qiáng)，近年來沒有理想的理論分析方法來確定這些參數(shù)，主要采用多次調(diào)試的方法，實(shí)驗(yàn)基本參數(shù)如表1所示，其中K為預(yù)設(shè)的算法最大迭代次數(shù)。在算法執(zhí)行時(shí)，初始化執(zhí)行次數(shù)N0=K且算法全過程執(zhí)行修正策略，獲得收斂時(shí)的迭代次數(shù)t0，之后令N0=t0；時(shí)變揮發(fā)律ρt的參數(shù)ρ0，t0，ε測定方法采用多次調(diào)試的方法，其中ε調(diào)整揮發(fā)律的曲率，ρ0，t0為調(diào)整揮發(fā)律初值的參數(shù)。值得說明的是：當(dāng)N0>t0時(shí)，算法整體運(yùn)行時(shí)間會(huì)增加，但更能保障算法收斂速度和質(zhì)量；當(dāng)N0<t0時(shí)，運(yùn)行時(shí)間減小，但算法質(zhì)量會(huì)有所影響。

3.2 30×30復(fù)雜環(huán)境分析

圖8為30×30復(fù)雜環(huán)境實(shí)驗(yàn)結(jié)果，其中圖8a為4種算法最短路徑圖，圖8b為4種算法60次最短距離迭代曲線，可知基本蟻群算法在60次迭代過程中最小路徑長度波動(dòng)下降，波動(dòng)幅度較大且難以收斂。

文獻(xiàn)［15］使螞蟻從8搜索方向擴(kuò)大到16搜索方向，具有更強(qiáng)的局部搜索能力，增強(qiáng)了螞蟻跳出局部最優(yōu)的能力，但16搜索方向?qū)τ诟鼜?fù)雜環(huán)境仍有局限性，如圖8a中多行的坐標(biāo)（27.5，1.5）為曲折路線，所以迭代曲線具有波動(dòng)性，且難以收斂。文獻(xiàn)［20］利用螞蟻間通信的方式，使得螞蟻能夠利用歷史路徑跳出局部陷阱，但螞蟻的歷史路徑是有限的，當(dāng)歷史路徑中沒有跳出局部陷阱的路徑時(shí)，那么螞蟻間通信的方式則不能解決局部陷阱問題，例如圖8a文獻(xiàn)［20］的路徑中（3.5，23.5）至（3.5，20.5）。因此，文獻(xiàn)［20］雖然有效降低了迭代曲線的波動(dòng)性，但是對(duì)于復(fù)雜環(huán)境仍難以收斂。

本文提出的修正策略和自適應(yīng)揮發(fā)強(qiáng)度的信息素更新機(jī)制，使算法具有修正曲折路徑的能力，減少了曲折路徑所產(chǎn)生的信息素干擾，從而使算法在復(fù)雜環(huán)境中迭代曲線波動(dòng)小、收斂快。

3.3 算法魯棒性測試

圖9a和圖10a為20×20和40×40復(fù)雜環(huán)境，結(jié)合圖8a的實(shí)驗(yàn)環(huán)境，進(jìn)行4種算法的實(shí)驗(yàn)。由圖8a、圖9a和圖10a可知，基本蟻群算法在3種情況下曲折路徑較多，算法難以收斂。圖10b表明：隨著環(huán)境模型復(fù)雜度的增大，文獻(xiàn)［15］相比于基本蟻群算法的優(yōu)越性則變差，迭代曲線已經(jīng)沒有明顯優(yōu)勢，其主要原因是16方向的螞蟻搜索范圍有限，使得16搜索方向與8搜索方向性能差距縮小，以致收斂曲線變化趨勢幾乎一致。

圖9b說明，文獻(xiàn)［20］在20×20復(fù)雜環(huán)境能夠收斂，但是本文算法收斂速度比之更快，且收斂結(jié)果一致。隨著環(huán)境模型復(fù)雜度升高，如圖8b中30×30復(fù)雜環(huán)境，文獻(xiàn)［20］中螞蟻的歷史路徑對(duì)環(huán)境模型的覆蓋度不足，導(dǎo)致螞蟻通信性降低，因此會(huì)出現(xiàn)一定的波動(dòng)。本文算法在迭代次數(shù)為10時(shí)仍能收斂，且收斂質(zhì)量強(qiáng)于文獻(xiàn)［20］。對(duì)于圖10a中更加復(fù)雜的40×40環(huán)境，文獻(xiàn)［20］的性能則進(jìn)一步變差，圖10b中迭代曲線波動(dòng)性更大，更加難以收斂，而本文算法則在15次達(dá)到收斂，收斂值小于文獻(xiàn)［20］最小值。

綜上，在4種算法中，從收斂速度考慮基本蟻群算法與文獻(xiàn)［15］都不能收斂，文獻(xiàn)［20］能在20×20環(huán)境下收斂，而更加復(fù)雜的環(huán)境則不能收斂，算法魯棒性較差。本文算法在3種測試環(huán)境下都能夠收斂且魯棒性較好。從收斂值角度考慮，本文算法<文獻(xiàn)［20］<文獻(xiàn)［15］<基本蟻群算法。因此，對(duì)于收斂速度和收斂值，本文算法>文獻(xiàn)［20］>文獻(xiàn)［15］>基本蟻群算法。

3.4 統(tǒng)計(jì)數(shù)據(jù)分析

表2為4種算法30次重復(fù)實(shí)驗(yàn)所得統(tǒng)計(jì)數(shù)據(jù)?？梢钥闯?，隨著復(fù)雜度的升高，4種算法的平均運(yùn)行時(shí)間都有所提升，具體順序?yàn)楸疚乃惴?gt;文獻(xiàn)［20］>文獻(xiàn)［15］>原算法，但是只關(guān)注整體平均運(yùn)行時(shí)間并不能有效說明算法的性能。將算法第一次搜索到最短長度時(shí)的迭代次數(shù)記為有效迭代次數(shù)，所花費(fèi)的時(shí)間記為有效時(shí)間，從有效時(shí)間的角度更能說明算法的時(shí)間效率。從表2中可以看出，算法在3種環(huán)境模型下的有效時(shí)間為本文算法<文獻(xiàn)［20］<文獻(xiàn)［15］<原算法。因此，從有效時(shí)間角度考慮算法性能，本文算法最佳。

此外，在平均長度和最短長度方面，本文算法在3種不同的環(huán)境模型下都具有較好的魯棒性。值得一提的是：文獻(xiàn)［15］對(duì)于20×20模型，因其螞蟻搜索方向?yàn)?6方向，因此在一些特殊情況下的路線可以比8搜索方向的路徑更短，但是對(duì)于更加復(fù)雜的模型，文獻(xiàn)［15］則效果不佳。

4 結(jié)論

改進(jìn)的蟻群算法在復(fù)雜環(huán)境路徑規(guī)劃問題中，難以收斂且收斂結(jié)果差。本文針對(duì)該問題引入修正策略和自適應(yīng)信息素更新機(jī)制，解決復(fù)雜環(huán)境模型中收斂難、收斂結(jié)果差的問題;然后，介紹了參數(shù)的測定方法。最后，通過與文獻(xiàn)［15］、［20］以及基本蟻群算法在不同環(huán)境模型的對(duì)比實(shí)驗(yàn)，證明了改進(jìn)蟻群算法具有較好的適應(yīng)性和魯棒性，以及較快的收斂速度和較好的收斂結(jié)果。此外，本文引入的修正策略具有時(shí)間復(fù)雜度較高的不足，如何尋找時(shí)間復(fù)雜度更低的路徑優(yōu)化策略是下一步值得考慮的問題。

參考文獻(xiàn)：

［1］DORIGO M， MANIEZZO V， COLORNI A. Positive feedback as a search strategy［J］. Technical Report， 199 1（1）：91016.

［2］WANG Y H， GAO D M， WANG X D. Shortest path planning based on improved ant colony algorithm［J］. ASP Transactions on Computes， 202 1（3）：611.

［3］AKKA K， KHABER F. Mobile robot path planning using an improved ant colony optimization［J］. International Journal of Advanced Robotic Systems， 2018， 15（3）：17.

［4］BULLNHEIMER B， HARTL R F， STRAUSS C. An improved ant system algorithm for the vehicle routing problem［J］， Annals+BOL2NiImws8kmiTPx1vvQ== of Operations Research， 1999， 89：319328.

［5］CARO D. Antnet： distributed stigmergetic control for communications networks［J］. Journal of Artificial Intelligent Research， 1999， 9（1）： 317365.

［6］HOU W B， XIONG Z H， WANG C S， et al. Enhanced ant colony algorithm with communication mechanism for mobile robot path planning［J］. Robotics and Autonomous Systems， 2022，148： 103949.

［7］LU L C， YUE T W. Mission-oriented ant-team ACO for min-max MTSP［J］. Applied Soft Computing， 2018， 76：436444.

［8］MIAO C W， CHEN G Z， YAN C L， et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm［J］. Computers & Industrial Engineering， 202 156：107230.

［9］XUE T， LIU L， LIU S， et al. Path planning of mobile robot based on improved ant colony algorithm for logistics［J］. Mathematical Biosciences and Engineering， 202 18（4）： 30343045.

［10］ 孔珊，仲昭林，張紀(jì)會(huì).多路徑選擇變速雙目標(biāo)物流配送路徑規(guī)劃［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2022， 19（1）：7480.

KONG S， ZHONG Z L， ZHANG J H. Bi-objective vehicle routing problems with path choice and variable speed［J］. Complex System and Complexity Science， 2022， 19（1）：7480.

［11］ 江明，王飛，葛愿，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究［J］.儀器儀表學(xué)報(bào)， 2019， 40（2）： 113121.

JIANG M， WANG F， GE Y， et al. Research on path planning of mobile robot based on improved ant colony algorithm［J］. Chinese Journal of Scientific Instrument， 2019， 40（2）： 113121.

［12］ 王曉燕，楊樂，張宇，等. 基于改進(jìn)勢場蟻群算法的機(jī)器人路徑規(guī)劃［J］.控制與決策， 2018， 33（10）： 17751781.

WANG X Y， YANG L， ZHANG Y， et al， et al. Robot path planning based on improved ant colony algorithm with potential field heuristic［J］. Control and Decision， 2018， 33（10）： 17751781.

［13］ 徐興，錢譽(yù)欽，趙蕓，等.基于改進(jìn)蟻群算法的立體倉庫三維空間路徑優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)， 202 27（1）： 207214.

XU X， QIAN Y Q， ZHAO Y， et al.3D spatial path optimization of stereo warehouse based on improved ant colony algorithm［J］.Computer Integrated Manufacturing Systems， 202 27（1）： 207214.

［14］ 徐小斐，陳婧，饒運(yùn)清，等.遷移蟻群強(qiáng)化學(xué)習(xí)算法及其在矩形排樣中的應(yīng)用［J］.計(jì)算機(jī)集成制造系統(tǒng)， 2020， 26（12）： 32363247.

XU X F， CHEN J， RAO Y Q， et al. Transfer ants reinforcement learning algorithm and its application on rectangular packing problem［J］. Computer Integratedf67f247836e8b897415174e7eead9e88 Manufacturing Systems， 202 36（7）： 15811591.

［15］ 徐菱，付文浩，江文輝，等.基于16方向24鄰域改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃［J］.控制與決策， 202 36（5）： 11371146.

XU L， FU W H， JIANG W H， et al. Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm［J］. Control and Decision， 202 36（5）： 11371146.

［16］ DEBORA D C， ALI E， HAMIDREZA A， et al. A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights［J］. Alexandria Engineering Journal， 2022， 61： 34033415.

［17］ 張恒，何麗，袁亮，等.基于改進(jìn)雙層蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃［J］.控制與決策， 2022， 37（2）： 303313.

ZHANG H， HE L， YUAN L， et al. Mobile robot path planning using improved double-layer ant colony algorithm［J］. Control and Decision， 2022， 37（2）： 303313.

［18］ 張瑋，馬焱，趙捍東，等.基于改進(jìn)煙花蟻群混合算法的智能移動(dòng)體避障路徑規(guī)劃［J］.控制與決策， 2019， 34（2）： 335343.

ZHANG W， MA Y， ZHAO H D， et al. Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm［J］. Control and Decision， 2019， 34（2）： 335343.

［19］ 鄧麗娟，張紀(jì)會(huì).混合蟻群算法求解雙目標(biāo)時(shí)間窗VRP［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2020，17（4）：7384.

DENG L J， ZHANG J H. A hybrid ant colony optimization for bi-objective VRP with time windows［J］. Complex System and Complexity Science， 2020， 17（4）： 7384.

［20］ HOU W B， XIONG Z H， WANG C S， et al. Enhanced ant colony algorithm with communication mechanism for mobile robot path planning［J］. Robotics and Autonomous Systems， 2022， 148：103949.

（責(zé)任編輯 李 進(jìn)）