基于異構(gòu)雙種群全局視野蟻群算法的移動機(jī)器人路徑規(guī)劃研究

收稿日期：2021-12-14；修回日期：2022-01-17

作者簡介：馬飛宇（1998-），男（通信作者），安徽宿州人，碩士研究生，主要研究方向為機(jī)器視覺與跨媒體信息處理（s191201006@stu.cqupt.edu.cn）；瞿中（1972-），男，重慶人，教授，博導(dǎo)，博士，主要研究方向為數(shù)字圖像處理、云計算和物聯(lián)網(wǎng)技術(shù)等．

摘 要：針對蟻群算法中存在的算法收斂速度慢、逼近最優(yōu)解能力不足等問題，提出一種基于異構(gòu)雙種群全局視野的蟻群算法，并將其應(yīng)用于移動機(jī)器人路徑規(guī)劃領(lǐng)域。首先，研究基于異構(gòu)蟻群的并行結(jié)構(gòu)，通過差異化種群的相互協(xié)作提高蟻群算法的收斂速度和規(guī)劃最優(yōu)路徑的能力；然后，研究具有全局視野的自適應(yīng)步長，解決蟻群算法因局部視野導(dǎo)致無法搜索到最優(yōu)步長的問題；最后，研究信息素初始化以及信息素更新方式，改進(jìn)傳統(tǒng)蟻群算法運行初期搜索無序性以及信息素更新不合理等問題。實驗結(jié)果表明，該算法在逼近最優(yōu)解能力和提高收斂速度等方面較對比方法有著顯著提高，在測試的幾種仿真地圖中，平均路徑長度優(yōu)化了12%，平均迭代次數(shù)和平均運行時間分別減少了67%和82%。

關(guān)鍵詞：蟻群算法； 路徑規(guī)劃； 全局視野； 雙種群； 自適應(yīng)步長

中圖分類號：TP242"" 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2022）06-018-1705-05

doi：10.19734/j.issn.1001-3695.2021.12.0632

Research on path planning of mobile robot based on heterogeneous dual population

and global vision ant colony algorithm

Ma Feiyu， Qu Zhong

（School of Software Engineering， Chongqing University of Posts amp; Telecommunications， Chongqing 400065， China）

Abstract：Aiming at the problems of slow algorithm convergence and insufficient ability to approach the optimal solution in the ant colony algorithm， this paper proposed an ant colony algorithm based on heterogeneous dual-population and global vision， and applied to the field of mobile robot path planning. Firstly， the algorithm studied the parallel structure based on heterogeneous ant colonies， improved the convergence speed and the ability to plan the optimal path by collaboration through differentiated populations. Then， the algorithm studied the adaptive step size with global field of view， and solved the problem that the ant colony algorithm could not search for the optimal step size due to the local field of view. Finally， the algorithm studied the pheromone initialization and updated methods， improved the search disorder and unreasonable pheromone update in the initial stage of the traditional ant colony algorithm. The experimental results show that the algorithm has a significant improvement over the comparison methods in terms of approaching the optimal solution ability and improving the convergence speed. In the several simulation maps tested， the average path length is optimized by 12%， and the average number of iterations and average running time are reduced by 67% and 82% respectively.

Key words：ant colony algorithm; path planning; global view; dual populations; adaptive step size

隨著自動化技術(shù)、傳感器技術(shù)、計算機(jī)技術(shù)等多學(xué)科技術(shù)的不斷發(fā)展，移動機(jī)器人技術(shù)在軍事、工業(yè)、農(nóng)業(yè)、醫(yī)療等領(lǐng)域得到了廣泛應(yīng)用，并逐漸發(fā)展出自主規(guī)劃、自主運行等特點［1］。路徑規(guī)劃是移動機(jī)器人能夠?qū)崿F(xiàn)任務(wù)規(guī)劃的關(guān)鍵技術(shù)之一，旨在符合多種約束條件的情況下，規(guī)劃出從起始點到目標(biāo)點的可行路徑。動態(tài)規(guī)劃、模擬退火算法、遺傳算法、粒子群算法、神經(jīng)網(wǎng)絡(luò)和蟻群算法等都是比較常見的路徑規(guī)劃算法，其中蟻群算法具有較強(qiáng)的全局尋優(yōu)能力和良好的魯棒性，在路徑規(guī)劃領(lǐng)域得到了廣泛應(yīng)用。

傳統(tǒng)蟻群算法存在收斂速度慢、易陷入局部最優(yōu)解等問題。針對這些問題，Stützle等人［2］提出了最大最小螞蟻系統(tǒng)，通過在每代最優(yōu)的螞蟻路徑上更新信息素來加快蟻群算法的收斂速度。Fatemidokht等人［3］提出限定信息素允許值的上下界，采用路徑平滑機(jī)制，結(jié)合局部最優(yōu)路徑信息素進(jìn)行更新。Li等人［4］通過改進(jìn)狀態(tài)轉(zhuǎn)移方程和蟻群的信息素更新方式提高蟻群的收斂速度，并在數(shù)據(jù)集上進(jìn)行了實驗驗證。Ajeil等人［5］根據(jù)螞蟻年齡動態(tài)設(shè)置信息素更新值的大小。

本文提出基于異構(gòu)雙種群全局視野蟻群算法，使螞蟻在不同地圖環(huán)境中進(jìn)行搜索時均可采用最大步長，并重新設(shè)計具有全局信息和方向性約束的概率選擇函數(shù)，提高蟻群算法逼近最優(yōu)解的能力。同時，通過差異化雙種群設(shè)計提高蟻群算法的探索多樣性，并通過設(shè)計信息素動態(tài)更新函數(shù)和基于刺激概率的初始信息素分布改進(jìn)信息素更新方式。最后通過實驗確定算法的最優(yōu)參數(shù)組合，并在不同的地圖環(huán)境中進(jìn)行仿真實驗，證明本文提出的蟻群算法在相關(guān)性能指標(biāo)上有顯著提高。

1 相關(guān)工作

1.1 環(huán)境建模

常見的環(huán)境建模方法包括網(wǎng)格法、幾何圖法和拓?fù)鋱D法?；诰W(wǎng)格法的環(huán)境建模方式可以降低建模的復(fù)雜性、減少計算量，是一種被廣泛采用的環(huán)境建模方法，故本文采用網(wǎng)格模型來展示機(jī)器人的運動環(huán)境。

假設(shè)機(jī)器人在其中移動的空間是一個有限的區(qū)域，在二維平面上有多個大小不同的障礙物。以左上角為原點，搜索地圖時通過水平x軸和垂直y軸展開。矩形環(huán)境的劃分如下：x和y軸均平分為m個網(wǎng)格，網(wǎng)格單元通過二進(jìn)制信息表示，以0表示可以通行的自由網(wǎng)格，以1表示障礙物網(wǎng)格。

每個網(wǎng)格的長度是坐標(biāo)的單位長度，在XOY坐標(biāo)系中，將網(wǎng)格按照從左到右、從上到下的方式進(jìn)行編碼，則網(wǎng)格編碼（i）與坐標(biāo)（x， y）間的關(guān)系可以表示為

xi=mod（i－1，Nx）+0.5

yi=inti－1Ny+0.5

（1）

其中：Nx是每行的行數(shù);Ny是每列的列數(shù)。圖1是一個二維空間環(huán)境下的20×20網(wǎng)格模型，黑色網(wǎng)格表示障礙物，白色部分表示可以通行的自由區(qū)域。

1.2 自由步長蟻群算法

傳統(tǒng)蟻群算法是一種模擬進(jìn)化算法，人們發(fā)現(xiàn)螞蟻群體之間和螞蟻同環(huán)境之間的交互是依賴一種被稱之為信息素的化學(xué)物質(zhì)實現(xiàn)的，螞蟻在行進(jìn)過程中通過信息素進(jìn)行信息交互，而信息素會不斷揮發(fā)，高濃度的信息素會不斷吸引更多的螞蟻沿最短路徑行進(jìn)，這種根據(jù)其他螞蟻所釋放的化學(xué)物質(zhì)來影響螞蟻群體路徑選擇的行為方式正是蟻群算法的靈感來源。

蟻群中每個螞蟻根據(jù)相關(guān)的啟發(fā)式信息，如節(jié)點的可見性和節(jié)點間的信息素強(qiáng)度，從當(dāng)前節(jié)點i移動到未訪問節(jié)點j，若有多個未訪問節(jié)點，螞蟻k根據(jù)轉(zhuǎn)移概率函數(shù)選擇下一個網(wǎng)格，如式（2）所示。

pkij（t）=（τij（t））α（ηij（t））β∑sallowed（i）（τis（t））α（ηis（t））β j∈allowed（i）

0otherwise（2）

其中：pkij（t）表示在時間t螞蟻k從節(jié)點i到j(luò)的轉(zhuǎn)移概率;allowed（i）表示當(dāng)前網(wǎng)格i的8個相鄰自由網(wǎng)格的集合；τij（t）表示t時刻節(jié)點i到j(luò)之間的信息素濃度；α和β是權(quán)重系數(shù)，分別表示信息素和可見性的相對重要性；ηij（t）表示節(jié)點j相對于i的可見度的啟發(fā)函數(shù)，如式（3）所示。

ηij（t）=1dij（3）

其中：dij表示節(jié)點i和j之間的歐氏距離，如式（4）所示。

dij=（xj－xi）2+（yj－yi）2（4）

在自然界中，螞蟻之間使用信息素通信，且信息素會隨著時間逐步揮發(fā)。在蟻群算法中信息素的更新規(guī)則如式（5）和（6）所示。

τij=（1－ρ）τij+Δτij 0lt;ρlt;1（5）

Δτij=∑mk=1Δτkij（6）

其中：ρ表示信息素的蒸發(fā)系數(shù)；Δτij表示一個周期內(nèi)螞蟻k在路徑上釋放的信息素濃度，可以定義為式（7）。

Δτkij（k）=Q1Lk if ant k used edge（i，j） in its tour

0otherwise（7）

其中：Q1是常數(shù);Lk表示螞蟻k找到的路徑長度。

傳統(tǒng)蟻群算法中螞蟻的每一次搜索范圍往往為相鄰網(wǎng)格，即搜索步長為1。而Zeng等人［6］提出的自由步長蟻群算法，即螞蟻在一次迭代中可以搜索更大步長的路徑，大大加快了蟻群的收斂速度。

如圖2所示，傳統(tǒng)蟻群算法從起點S搜索到終點E的路徑，找到的最短路徑可能是路徑①，但實際最短路徑是②。自由步長使尋找最短路徑的算法不再受限，增加了網(wǎng)格選擇的多樣性，提高了蟻群算法的搜索性能。

1.3 雙種群蟻群算法

雙種群蟻群算法在傳統(tǒng)蟻群算法的基礎(chǔ)上引入了種群間的交流學(xué)習(xí)機(jī)制，讓兩個種群之間可以達(dá)到很好的優(yōu)勢互補(bǔ)，使算法性能得到了進(jìn)一步提升，所以近年來更多的學(xué)者將注意力轉(zhuǎn)移到雙種群和多種群的研究上。

針對雙種群蟻群算法研究的核心在于解的交流策略和信息素更新策略上，一些有代表性的工作有Zhu等人［7］提出通過信息熵來決定種群之間的交流策略，平衡子種群中解的多樣性和收斂性；Mavrovouniotis等人［8］提出用于解決動態(tài)TSP的多種群蟻群算法，每個種群并行運行并將最優(yōu)解共享給所有種群，從而提高算法解的質(zhì)量；Huang等人［9］引入了聚類方法和交互式機(jī)制用于改進(jìn)種群間的交流方式。

雙種群交流中種群的選擇往往有同構(gòu)種群和異構(gòu)種群兩種。文獻(xiàn)［8］的研究表明，由于在探索解的多樣性上具有更大的優(yōu)勢，異構(gòu)種群的表現(xiàn)一般優(yōu)于同構(gòu)種群。

2 基于異構(gòu)雙種群的全局視野蟻群算法

2.1 異構(gòu)雙種群并行結(jié)構(gòu)

研究人員針對蟻群算法的優(yōu)化往往聚焦在加快算法收斂速度和提高算法搜索最優(yōu)解能力兩方面，而這兩者需要在一定程度上進(jìn)行權(quán)衡，在單一種群中提高算法搜索多樣性往往會降低算法的收斂速度，反之相同。蟻群算法本性具有良好的并行性，因此可以通過優(yōu)勢互補(bǔ)的種群來平衡算法的收斂速度和搜索最優(yōu)解能力［10］。本文通過建立異構(gòu)雙種群并行蟻群結(jié)構(gòu)，實現(xiàn)在提高蟻群算法收斂速度的同時提高獲取解的質(zhì)量，如圖3所示。

本文根據(jù)文獻(xiàn)［11］提出的社會群體搜索理論，將單個種群中每只螞蟻搜索得到的路徑質(zhì)量按照式（8）進(jìn)行評估，然后根據(jù)式（9）將種群中的螞蟻劃分為首領(lǐng)、中堅群體和追隨者。

xi=lengthilengthbest（8）

Ri=leader" if xigt;OT

ordinaryif LTlt;xilt;OT

outerif xilt;OT（9）

其中：Ri定義為個體i的群體;LT和OT分別為下限和上限;xi是本文定義的評估因子。

不同角色的螞蟻在行為模式上有所區(qū)別：首領(lǐng)是蟻群中最優(yōu)秀的個體，它們在進(jìn)行路徑搜索時只依賴個人意志而不借助種群的歷史信息；中堅群體是蟻群中的普通群體，在種群內(nèi)的地位僅次于首領(lǐng)，它們在進(jìn)行路徑搜索時將同時結(jié)合個人意志和種群歷史信息；追隨者是蟻群中的最底階層，它們在搜索路徑時只會依賴于種群的歷史信息。

不同角色的螞蟻針對算法的意義也不相同，首領(lǐng)將主要負(fù)責(zé)拓寬蟻群算法搜索的多樣性，提高算法逼近最優(yōu)解的能力；中堅群體用于保持算法收斂的穩(wěn)定性；追隨者用于加快算法收斂的速度。因此在兩個種群中，將不同階層的比例進(jìn)行差額配比，一個種群擁有較多的首領(lǐng)，負(fù)責(zé)探索更高質(zhì)量的解，另一個種群追隨者數(shù)量更多，則收斂速度更快。

當(dāng)兩個種群在一輪搜索結(jié)束后，借助遺傳算法中的交叉算子將兩者產(chǎn)生的最優(yōu)解進(jìn)行融合，若產(chǎn)生更優(yōu)路徑則反向更新至種群各自的信息素矩陣。

基于遺傳算子的路徑融合是一種局部搜索技術(shù)，如表1所示，其關(guān)鍵思想在于從不同種群找的最優(yōu)解（Path1和Path2）中選擇公共關(guān)鍵路徑點（P4和P10），比較公共關(guān)鍵路徑點間路徑的歐氏距離，從中選取最佳部分形成新路徑（NewPath）。

2.2 基于全局視野的自適應(yīng)步長

視野是指機(jī)器人在網(wǎng)格地圖中所有未被障礙物遮擋的網(wǎng)格，如圖4所示。通常認(rèn)為步長越大，路徑長度越短。而自由步長蟻群算法可以在一次迭代中搜索當(dāng)前視野中的所有網(wǎng)格，并從中選擇最合適的作為本次搜索結(jié)果，因此如何確定蟻群視野范圍的大小成為影響自由步長蟻群算法性能的關(guān)鍵。如果視野過小，則螞蟻無法一次搜索得到最短路徑；如果視野過大，在復(fù)雜地圖環(huán)境中，螞蟻的當(dāng)前視野范圍內(nèi)充斥著大量無法通行區(qū)域，降低了算法的搜索效率。

針對此問題，本文提出基于全局視野的自適應(yīng)步長蟻群算法：螞蟻的視野范圍采取當(dāng)前地圖環(huán)境下的最大視野范圍，即以當(dāng)前螞蟻所在網(wǎng)格為中心，地圖范圍內(nèi)與螞蟻具有直接連通性的所有網(wǎng)格，如圖5所示。采用全局視野的好處是針對不同復(fù)雜程度的地圖環(huán)境，螞蟻均可在一次搜索中采取最大步長，得到最短路徑，加快算法收斂速度。同時本文也注意到，算法在每次迭代中獲取螞蟻可通行區(qū)域的操作會增加算法的時間復(fù)雜度，因此將這部分工作放在算法的預(yù)處理中，避免全局視野對算法性能的影響。

為了加快蟻群算法的收斂速度，本文考慮在概率選擇函數(shù)中添加方向性約束函數(shù)。方向約束可以改善蟻群盲目搜索，加快算法收斂。如圖6所示，一只螞蟻從起始點向終點前進(jìn)，其中B、C、D、E、F、G都是螞蟻下一步可選擇的目標(biāo)點，但相較于D、G、E點，選擇B、C、D點可以更快到達(dá)終點。

重新設(shè)計后的概率選擇函數(shù)如式（10）所示。

Pkij（t）=（τij（t））α（ηij（t））βφij（t）∑sallowed（i）（τis（t））α（ηis（t））βφis（t） j∈allowed（i）

0otherwise（10）

其中：φij（t）表示方向性約束函數(shù)，如式（11）所示;ij表示當(dāng)前節(jié)點i到候選節(jié)點j的方向向量;ie表示從當(dāng)前節(jié)點i到目標(biāo)節(jié)點e的方向向量;Q2是常量;α表示信息素影響的權(quán)重因子;β表示啟發(fā)函數(shù)影響的權(quán)重因子。當(dāng)螞蟻在種群中屬于首領(lǐng)時，β為0，當(dāng)螞蟻在種群中屬于追隨者時，α為0，當(dāng)螞蟻在種群中屬于中堅群體時，α和β均不為0。

φij（t）=Q2cos－1ij·ie|ij|·|ie|+1（11）

方向性約束函數(shù)僅提高了更接近目標(biāo)點的區(qū)域被探索的概率，在少數(shù)情況下（如路徑搜索進(jìn)入死胡同時），螞蟻仍可以再次探索其他區(qū)域，未影響有效信息完整性。

通常步長越大，路徑長度越短。為了促進(jìn)螞蟻在選擇下一個網(wǎng)格時應(yīng)用大步長原則，就需要對概率選擇函數(shù)中的啟發(fā)函數(shù)進(jìn)行重新設(shè)計，如式（12）所示。

ηij（t）=dijdjE（12）

其中：dij表示當(dāng)前網(wǎng)格和下一個優(yōu)選網(wǎng)格間的歐氏距離；djE表示候選網(wǎng)格和目標(biāo)節(jié)點間的歐氏距離。

2.3 信息素更新方式

信息素用于模擬自然界中螞蟻釋放的信息素隨時間積累和揮發(fā)，空間模型中信息素的存量是影響螞蟻選擇路徑的關(guān)鍵信息。經(jīng)典蟻群算法在初始化信息素時不具有差異性，導(dǎo)致螞蟻在算法初期的無序搜索。因此提出基于刺激概率和位置信息的初始信息素分布，提高蟻群算法的收斂速度，如式（13）所示。

τij（0）=Q4eδsp－（dSi+diE）（13）

其中：Q4是常數(shù)；dSi表示從起始點到當(dāng)前節(jié)點的歐氏距離;diE表示從當(dāng)前節(jié)點到目標(biāo)節(jié)點的歐氏距離；δsp表示刺激概率。刺激概率（stimulating probability，SP）是衡量網(wǎng)格通行性的一種指標(biāo)，刺激概率的大小取決于圍繞網(wǎng)格的障礙物數(shù)量的大小，網(wǎng)格周圍的障礙物越少，概率越大。刺激概率可以根據(jù)式（14）計算。

δsp=C（8－Nobs－1，1）=（8－Nobs－1）?。?－Nobs－1－1）?。?4）

其中：Nobs表示當(dāng)前網(wǎng)格周圍障礙物的數(shù)量；因為二維空間網(wǎng)格中機(jī)器人是8自由度，所以（8-Nobs-1）表示除去障礙物和螞蟻來時路徑后的出口數(shù)量;C（a，b）表示數(shù)學(xué)組合，且C（a，b）=a！/［（a－b）！b！］。

當(dāng)螞蟻經(jīng)過某條路徑時將產(chǎn)生信息素，但其中包括一定數(shù)量的不良信息素，所以每次只在最佳螞蟻產(chǎn)生的最優(yōu)路徑上更新信息素，如式（15）所示。

τij（t+1）=σiterτij（t）+Δτij，Δτkij（t）=Q5Lbest（15）

其中：n表示族群數(shù)量;Δτij表示添加的信息素量;Q5是常數(shù);Lbest表示最優(yōu)路徑的歐氏距離。同時，為了保證蟻群在搜索空間和收斂速度之間的平衡，本文引入重新設(shè)計的動態(tài)信息素蒸發(fā)函數(shù)σiter，如式（16）所示。

σiter=1－Q6e－1Nc（16）

其中：Q6表示常數(shù);Nc表示當(dāng)前迭代次數(shù)。信息素動態(tài)蒸發(fā)函數(shù)會隨著迭代次數(shù)的增加逐漸增大，以保證蟻群算法的全局搜索能力。為了避免蟻群搜索的局部最優(yōu)和過早停滯等現(xiàn)象，將信息素設(shè)置上下限［τmin，τmax］，如式（17）所示。

τij（t）=τmax" τij（t）gt;τmax

τij（t）τminlt;τij（t）lt;τmax

τminτij（t）lt;τmin（17）

由于本文采用自適應(yīng)步長的蟻群算法，對于路徑中的關(guān)鍵點網(wǎng)格信息素正常更新，而關(guān)鍵網(wǎng)格之間的節(jié)點螞蟻只作短暫停留，信息素留存量很少，以增強(qiáng)大步長網(wǎng)格對蟻群的吸引。

3 實驗仿真及分析

3.1 參數(shù)設(shè)置

算法中關(guān)鍵參數(shù)設(shè)置如下：螞蟻數(shù)量m=100，迭代次數(shù)n=50，α=1，β=1，Q2=10，Q3=1，Q4=0.1，ω1=3，ω2=2，ω3=1，ω4=15，Q6=0.8。LT和OT可以根據(jù)決策因子將螞蟻種群劃分為首領(lǐng)、中堅群體、追隨者三組，為了確定三組螞蟻的最佳數(shù)量配置，本文針對不同組LT和OT參數(shù)重復(fù)進(jìn)行10次實驗，實驗結(jié)果平均值如表2和3所示。由表2可知，當(dāng)LT和OT分別設(shè)為1.4和2時，算法逼近最優(yōu)解能力最好，設(shè)為廣度優(yōu)先種群參數(shù)；當(dāng)LT和OT分別為1.5和4時，算法迭代次數(shù)最短，設(shè)為深度優(yōu)先種群參數(shù)。

3.2 模塊實驗

為了驗證蟻群視野范圍對算法性能的影響以及本文提出的全局視野模塊的有效性，本節(jié)在其他參數(shù)都相同的情況下，針對改進(jìn)蟻群算法的單步視野版本、局部視野版本（步長為3）和全局視野版本在圖7所示的地圖環(huán)境中重復(fù)進(jìn)行10次實驗，實驗結(jié)果如表4所示。

由實驗結(jié)果可知，局部視野機(jī)制提高了蟻群算法的收斂速度及逼近最優(yōu)解能力，而全部視野進(jìn)一步放大了這種優(yōu)勢，并在實驗中得到了最優(yōu)的平均路徑長度和平均迭代次數(shù)。這是因為局部視野無法針對不同地圖環(huán)境匹配最優(yōu)步長，如圖7所示，全局視野機(jī)制使螞蟻A處在任意位置時均可探索除遮擋外的所有區(qū)域，在一次搜索中得到最優(yōu)路徑。

3.3 對比實驗

本節(jié)分別基于多種復(fù)雜地形圖進(jìn)行實驗，驗證本文提出的改進(jìn)蟻群算法的可行性和有效性。同時與傳統(tǒng)蟻群算法、文獻(xiàn)［11～14］算法進(jìn)行對比。所有算法均在2.6 GHz處理器，16 GB內(nèi)存運行的Windows 10計算機(jī)上基于Python實現(xiàn)。

3.3.1 20×20回廊地圖實驗

為了驗證本文提出的改進(jìn)蟻群算法的優(yōu)越性，在相同實驗條件下使用20×20回廊地圖模型進(jìn)行實驗，回廊地形空間狹小，容易陷入局部最優(yōu)，通過在20×20回廊地圖中進(jìn)行實驗驗證了算法的魯棒性。

實驗結(jié)果如圖8所示，圖8（a）為五種算法的迭代收斂曲線。從圖中可以看出，在逼近最優(yōu)解能力方面，本文提出的改進(jìn)蟻群算法在所有對比方法中具有最好的逼近最優(yōu)解能力，針對回廊地圖搜索得到了最短路徑；在避免初期搜索盲目性方面，本文算法在所有對比方法中具有最好的針對性搜索能力，即在初次搜索得到的路徑最短；在算法收斂速度方面，本文提出的改進(jìn)蟻群算法在收斂速度上僅次于文獻(xiàn)［14］提出的算法，可以在較小的迭代次數(shù)時達(dá)到收斂。圖8（b）為五種算法得到的最優(yōu)路徑。

為了避免偶然性對實驗結(jié)果的影響，重復(fù)10次實驗，實驗結(jié)果平均值如表5所示。從表5可以看出，本文提出的改進(jìn)蟻群算法始終能夠保證最優(yōu)路徑，實驗得到的平均路徑長度為48.970 5，優(yōu)于其他四種算法。值得注意的是，本文提出的改進(jìn)蟻群算法基于異構(gòu)雙種群并行結(jié)構(gòu)，在相同時間內(nèi)可以迭代更多次數(shù)，其平均運行時間為0.2 s，是五種算法中最優(yōu)的。

3.3.2 40×40凹槽地圖實驗

為了驗證本文提出的改進(jìn)蟻群算法的優(yōu)越性，在相同的實驗條件下使用40×40凹槽地圖模型進(jìn)行實驗。

實驗結(jié)果如圖9所示，圖9（a）為五種算法的迭代收斂曲線。從圖中可以看出，在逼近最優(yōu)解能力和算法收斂速度方面，本文提出的改進(jìn)蟻群算法能夠以最少的收斂次數(shù)搜索得到最短路徑，在所有對比方法中具有最佳的逼近最優(yōu)解能力和最快的算法收斂速度；在避免初期搜索盲目性方面，本文算法具有更小的搜索盲目性。圖9（b）為五種算法得到的最優(yōu)路徑。

同時為了避免偶然性對實驗結(jié)果的影響，重復(fù)10次實驗，實驗結(jié)果平均值如表6所示。隨著地圖復(fù)雜度的增加，算法的平均迭代時間和平均運行時間均有不同程度的增加，且部分算法的逼近最優(yōu)解能力下降，這可能是因為算法沒有解決復(fù)雜地形下的死鎖和局部最優(yōu)問題。本文提出的改進(jìn)蟻群算法搜索得到的平均最優(yōu)路徑為50.526 9，且始終能夠保證最優(yōu)路徑；在平均迭代次數(shù)為11次，平均運行時間為1.1 s，均優(yōu)于其余算法。

通過對20×20回廊地圖和40×40凹槽地圖的實驗結(jié)果分析可知，得益于初始信息素分布及重新設(shè)計的概率選擇函數(shù)，改進(jìn)蟻群算法在搜索初期避免了盲目搜索，具有較強(qiáng)的尋優(yōu)能力，搜索得到的最優(yōu)路徑質(zhì)量隨算法迭代迅速提高。在搜索中后期，由于局部最優(yōu)問題，蟻群算法搜索得到的路徑長度下降速度減慢，傳統(tǒng)蟻群算法此時可能會逐步收斂，改進(jìn)蟻群算法由于信息素蒸發(fā)機(jī)制及異構(gòu)雙種群設(shè)計，仍然能夠進(jìn)一步逼近全局最優(yōu)解，異構(gòu)雙種群分別強(qiáng)調(diào)搜索多樣性和收斂速度，可以在算法搜索的廣度和深度之間取得更好的平衡，提高全局搜索和局部搜索能力。

4 結(jié)束語

近年來隨著人工智能產(chǎn)業(yè)的飛速發(fā)展，機(jī)器人相關(guān)技術(shù)的研究成為了人工智能領(lǐng)域的熱點之一。本文在分析蟻群算法研究現(xiàn)狀的基礎(chǔ)上，提出一種基于異構(gòu)雙種群全局視野的蟻群算法。通過差異化雙種群設(shè)計以及全局視野自適應(yīng)步長，提高蟻群算法的收斂速度和逼近最優(yōu)解能力；通過提出一種初始化信息素設(shè)置方式并改進(jìn)信息素更新方式，根據(jù)位置信息和地圖環(huán)境對信息素矩陣進(jìn)行初始化，減少蟻群搜索初期的無序性，加快蟻群收斂；最后，通過實驗和經(jīng)驗方法確定算法參數(shù)的最優(yōu)組合，借助不同地圖環(huán)境和其他算法進(jìn)行對比實驗，驗證算法的有效性和優(yōu)越性。

本文聚焦于蟻群算法進(jìn)行改進(jìn)以解決移動機(jī)器人路徑規(guī)劃問題，未來將進(jìn)一步考慮提高蟻群算法的多種群協(xié)作能力，以及進(jìn)一步探索社會群體搜索理論在蟻群算法中的應(yīng)用；同時，還可以進(jìn)一步探索如何將蟻群算法和其他智能算法，如遺傳算法、神經(jīng)網(wǎng)絡(luò)等進(jìn)行結(jié)合，完善路徑規(guī)劃算法的全局尋優(yōu)能力。

參考文獻(xiàn)：

[1]Zhang Mingyi， Liu Xilong， Xu De， et al. Vision-based target-following guider for mobile robot［J］.IEEE Trans on Industrial Electronics，2019，66（12）：9360-9371.

［2]Stützle T， Hoos H H. MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889-914.

［3]Fatemidokht H， Rafsanjani M K. F-Ant： an effective routing protocol for ant colony optimization based on fuzzy logic in vehicular Ad hoc networks［J］.Neural Computing and Applications，2018，29（11）：1127-1137.

［4]Li Jun， Xia Yuan， Li Bo， et al. A pseudo-dynamic search ant colony optimization algorithm with improved negative feedback mechanism［J］.Cognitive Systems Research，2020，62：1-9.

［5]Ajeil F H， Ibraheem I K， Azar A T， et al. Grid-based mobile robot path planning using aging-based ant colony optimization algorithm in static and dynamic environments［J］.Sensors，2020，20（7）：article No.1880.

［6]Zeng Mingru， Xi Lu， Xiao Aimin. The free step length ant colony algorithm in mobile robot path planning［J］.Advanced Robotics，2016，30（23）：1509-1514.

［7]Zhu Jingwei， Rui Ting， Liao Ming， et al. Multi-group ant colony algorithm based on simulated annealing method［J］.Journal of Shanghai University：English Edition，2010，14（6）：464-468.

［8]Mavrovouniotis M， Yang Shengxiang， Yao Xin. Multi-colony ant algorithms for the dynamic travelling salesman problem［C］//Proc of IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments.Piscataway，NJ：IEEE Press，2014：9-16.

［9]Huang Yongqing， Yang Shanlin， Liang Changyong. Improved interactive ant colony algorithm and its application［J］.Journal of Frontiers of Computer Science and Technology，2016，10（12）：1720-1728.

［10]Chen Jia， You Xiaoming， Liu Sheng， et al. Entropy-based dynamic heterogeneous ant colony optimization［J］.IEEE Access，2019，7：56317-56328.

［11]You Xiaoming， Liu Sheng， Zhang Chen. An improved ant colony system algorithm for robot path planning and performance analysis［J］.International Journal of Robotics and Automation，2018，33（5）：527-533.

［12]Dai Xiaolin， Long Shuai， Zhang Zhiwen， et al. Mobile robot path planning based on ant colony algorithm with A* heuristic method［J］.Frontiers in Neurorobotics，2019，13：article No.15.

［13]Luo Qiang， Wang Haibao， Zheng Yan， et al. Research on path planning of mobile robot based on improved ant colony algorithm［J］.Neural Computing and Applications，2020，32（6）：1555-1566.

［14]Xiong Ni， Zhou Xinzhi， Yang Xiuqing， et al. Mobile robot path planning based on time taboo ant colony optimization in dynamic environment［J/OL］.Frontiers in Neurorobotics.（2021-03-01）.https：//doi.org/10.3389/fnbot.2021.642733.