基于象群－蟻群算法改進的小車路徑規劃

柏語蔓，于蓮芝

（上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引 言

科技發展推動著智能移動機器人領域迅速發展，該領域需要多類技術相互融合［1］，其中路徑規劃是該領域研究的核心問題［2］。智能機器人在實際使用中能否高效、安全完成任務，主要取決于路徑規劃是否合理。目前主流的路徑規劃算法主要有人工勢場法［3］、模糊邏輯算法［4］、模擬退火算法［5］、蟻群算法等。

在眾多路徑規劃算法中，蟻群算法有較好的全局優化能力、魯棒性、并行性［6］，適合復雜環境中的路徑規劃問題。該算法由MarcoDorigo在1992 年提出［7］，這是一種模仿螞蟻覓食的智能路徑規劃算法。模仿螞蟻通過釋放信息素尋找最優覓食路徑，多輪覓食之后，根據正反饋機制選出信息素濃度最高路線為最優路徑。

其中，螞蟻種群數量、信息素揮發速度、信息素影響因子、啟發式影響因子這些參數值選取過大或者過小都會直接影響路徑搜索的隨機性，進而影響算法收斂速度和全局搜索能力。隨機性較弱時，算法的搜索速度加快，但會導致全局搜索能力降低，結果為局部最優。當算法隨機性較強時，降低蟻群算法正反饋作用，算法收斂速度變慢，拖慢運行效率。所以如何選擇合適的參數是蟻群算法改進的重點。

針對蟻群算法在路徑規劃應用中存在的問題，目前主流的對蟻群算法的改進方案有：

（1）單一蟻群算法的改進［8］：單個蟻群算法通過改進算法結構、優化參數、設置信息素初始值和調整信息素更新原則等方式，提高算法的尋優能力。該改進方案雖然在一定程度上改進了蟻群算法的運行速度、減少陷入局部最優解的可能，但由于大部分參數改動都是需要人為去設定參數，存在算法不靈活的問題。

（2）多蟻群優化算法［8］：采用不同算法結構、運行機制的螞蟻群去尋找最優路徑，一般主流的運行機制是順序和并行。該改進方案是通過增加蟻群的多樣性，來提高結果為最優解的可能性。其中順序運行機制需要設置相遇判斷準則，而并行運行機制需要制定種群間信息交換機制，并且相遇判斷準則和信息交換機制的設計直接影響整個算法的優化結果，甚至會降低蟻群算法的性能。

（3）融合蟻群算法［8］：通過融合其它優化算法，從初始信息素值、狀態轉移規則、算法參數、初始路這4 個方面優化蟻群算法。該方案可以大大降低蟻群算法的迭代次數，提高尋優速度。通過大量的文獻表明，該類改進方案相對于前兩種方案具有更強的尋優能力。但是，由于算法的復雜程度增加，會在一定程度上增加算法的運行時間。

本文選用第三類改進方案，將貪婪算法和象群算法融入到蟻群算法之中。針對蟻群算法初始信息素值相同導致的初次迭代過于隨機，影響算法的迭代速度的問題，本文在蟻群算法之前加入貪婪算法，選出次優路徑，以此為依據設置初始信息素值。針對蟻群算法憑借經驗設計參數，導致參數設計不當影響算法性能的現象，本文將象群算法融入到蟻群算法之中，并在象群算法的基礎上加入評價函數，為蟻群算法選取合適的算法參數，以此降低算法迭代次數，提升蟻群算法尋優能力。最后將改進后的蟻群算法帶入到已知運行環境的機器人小車路徑規劃實驗中，在創建的運行環境柵格圖的基礎上，用MATLAB 進行改進后和初始蟻群算法的路徑規劃對比仿真實驗，根據實驗數據分析改進后的算法優劣。

1 柵格法創建環境模型

本文研究的是基于蟻群算法的全局路徑規劃，即已知環境中障礙物信息。在該情況下，對全局環境進行建模是路徑規劃的基礎和前提。環境模型需要包含環境中所有的已知信息，并且該環境模型描述的方式要方便計算機去存儲和運算，滿足環境信息隨機器人位置變換而隨時更新的要求。同時，在環境模型上搜索的最優路徑，能讓移動機器人在實際運行中少與障礙物發生碰撞。由于柵格法能夠滿足環境建模的要求，并且易于創建便于維護，因此本文選擇柵格法創建環境模型。

柵格法用坐標系表示機器人運動環境。首先在運行環境邊界找一點為坐標原點，并創建坐標系，劃分運行環境為等大小的柵格，障礙物等比例映射到柵格圖中，進行障礙物標注，由黑白兩色分別標記柵格圖中的障礙物和自由柵格。

在路徑規劃仿真實驗中，一般不考慮移動機器人的大小和形狀，只將其看作一個質點，為了避免實際實驗中移動機器人與障礙物發生碰撞，在進行柵格法創建環境模型時，一般會膨脹處理柵格中的障礙物，即將障礙物的邊長擴大半個柵格的長度，以此提高移動機器人在實際運動中的安全性。柵格法創建的環境模型如圖1 所示。

圖1 柵格地圖Fig.1 Raster map

在柵格圖中可見，每一塊柵格都會由序號i和坐標（x，y）共同去表示。序號是用從1 開始的自然數按照從左到右、從上到下的方式去逐一標注每一塊柵格，坐標是用創建的XOY坐標系，來表示每一個柵格的坐標。序號和坐標之間的轉換關系為：

式中：mod表示的余數；ceil表示的整數；N表示每列柵格數。

2 蟻群算法改進

2.1 初始信息素改進

由于初始信息素濃度相同會導致螞蟻初次搜索路徑過于隨機，從而使算法收斂速度減慢。因此本文通過差異化設置柵格圖各塊信息素濃度的方式，使初始信息素濃度按一定規則分布，降低蟻群初次迭代的隨機性，以此縮短收斂時間，提高蟻群算法的效率。

本文選用最佳優先搜索算法（Best－ First Search，BFS），在蟻群算法運行之前選擇一條次優路徑。BFS 算法是一種啟發式搜索算法［9］，有別于窮舉類型的搜索算法，不需要逐個搜索所有的點，運行效率更高，更適合復雜、面積較大的運行環境，適合用作尋找環境中的次優路徑。BFS 找出的次優路徑如圖2 所示。

圖2 次優路徑圖Fig.2 Suboptimal path diagram

以BFS 算法選擇的路徑結果為依據，初始化路徑中的信息素濃度。初始信息素濃度以次優路徑為中心向兩邊呈標準正態分布，如公式（2）：

式中：x表示點到次優路徑的垂直距離，a的值為次優路徑信息素濃度值。

2.2 參數改進

在蟻群算法中，參數對算法結果的準確度起著至關重要的作用。原始蟻群算法是憑借實驗者的經驗來選取參數值［10］，使用象群算法較強的尋優能力選取蟻群算法中的重要參數。象群算法（Elephant Herding Optimization，EHO）［11］是一種新元啟發式優化算法，較其它優化算法公式簡單、便于理解，具有收斂速度快尋優能力強等優點。

象群優化算法是根據象群的游牧行為啟發得來的［12］。大象成群生活由多個氏族在一位最優秀母象女部長的領導下組成，每個氏族由母象和她的小象或某些有血緣關系的母象和小象組成，氏族里也會選出優秀的母象擔任族長，成年后公象會離開群體獨自生活，雖然公象遠離其家族，但其可以通過低頻振動與家族中的大象保持聯系。

為了使用大象的放牧行為解決各種全局優化問題，對其做以下理想化規則。

（1）一個象群部落由多個氏族和一個最優母象女族長組成，每個氏族都有固定數量的大象。

（2）每代中每個氏族都會選出一個優秀女族長，并有固定數量公象離開，且產生其相同數量的新小象。

象群算法分為兩個階段，分別是氏族更新階段和分離階段。具體過程如下：

2.2.1 氏族更新階段

氏族里每頭大象的位置都會受到女族長的影響，對于氏族ci中的大象j，位置更新如公式（3）：

式中：φ∈［0，1］為比例因子；為氏族ci中大象j的新位置；xci，j為氏族ci中大象j的舊位置；xbest，ci為氏族ci女族長；r∈［0，1］ 為隨機數。

女族長位置更新位置如公式（4）：

式中：δ∈［0，1］為xcenter，ci對xbest，ci的影響因子，xbest，ci為氏族ci的中心位置。其中，xcenter，ci，d的表達式如公式（5）：

式中：d∈［1，D］ 為維度；D為最大維度；nci為氏族ci的大象總數。

2.2.2 分離階段

為了模擬成年后的公象離開群體獨自生活這一過程，并獲得更大搜索能力，假設適應度最差的大象個體，在每代中執行分離算子，如公式（6）：

式中：xmax和xmin分別為大象個體位置上界和下界，xworst，ci為ci氏族中最差大象個體。

改進方案是將信息素揮發速度、信息素影響因子、啟發式影響因子和螞蟻種群數量這4 個參數，作為象群的位置信息，創建一個四維的坐標矩陣。由象群算法不斷迭代更新象群位置，選出最優的母象位置，同時設計評價函數來鑒定所選參數的合理性，以此使象群算法得出的參數值可以更好的適應蟻群算法。

設計評價函數的目的，是評估象群算法選取參數是否適合蟻群算法。所以評價函數設計過程需要考慮到蟻群算法的幾個重要性能指標。這些指標分別為尋優能力、穩定性、收斂速度、運算時間，該評價函數設計如公式（7）～（9）：

式中：Fitk(s) 為將當前大象k的位置矩陣作為參數，運行蟻群算法后的適應值；ω1、ω2、ω3、ω4為尋優能力、穩定性、收斂速度和運算時間各指標對應的權值，權值相加為1；Lk(s) 為使用當前大象位置作為參數的蟻群算法的尋優能力；f為正態分布函數；Llocal表示此時蟻群算法的最優解；Sk(s) 為此時蟻群算法穩定性；Lstd為每次迭代所得最短距離方差；Ek(s) 表示此時蟻群算法尋找到最優解所需迭代次數；Tk(s) 表示此次蟻群算法運算時間。

2.3 算法實現

該算法的主要實現步驟如下：

Step 1使用柵格法創建環境模型；

Step 2貪心算法選出次優路徑，并根據路徑選擇結果，初始化各節點之間的信息素濃度；

Step 3初始化象群算法，給各個大象隨機選取初始位置和速度，并為比例因子φ和影響因子δ賦值；

Step 4將每個大象的位置信息作為參數帶入蟻群算法中，計算在各參數下運行蟻群算法獲得的Llocal、Lstd、Ek、Tk。

Step 5將步驟4 中每個大象對應的Lk(s)、Sk(s)、Ek(s) 和Tk(s) 值帶入適應度函數中，算出各個大象的適應度值；

Step 6比較各大象的適應度值，選取適應度最優的大象為族長，同時選出適應度最差的大象；

Step 7用公式（4）更新族長的位置，用公式（5）更新適應度較差大象的位置，用公式（3）更新其余大象的位置；

Step 8判斷象群算法的迭代次數是否達到設定的最大值，若為最大值，就將未更新位置前族長的位置輸出；否則，回到步驟4；

Step 9用輸出的最優位置為參數，帶入到蟻群算法中，用蟻群算法選出最優路徑，得到全局最優解。

改進后蟻群算法流程如圖3 所示：

圖3 改進后蟻群算法流程圖Fig.3 Flow chart of improved ant colony algorithm

3 仿真結果與分析

本文選用的仿真環境為MATLAB2018b，環境模型為20*20 的柵格。對比改進前后的蟻群算法的仿真結果，驗證改進算法的可行性和優越性。

在信息素加強系數都為1 的情況下，根據文獻［13］給出的傳統蟻群算法參數，其中螞蟻的數量為40、信息素揮發速度為0.3、信息素影響因子為5、啟發式影響因子為2。通過象群算法改進后的蟻群算法參數選擇見表1，次優路徑的信息素濃度值為8。將兩種情況，進行100 次迭代，20 次重復實驗，比較兩者的性能。表2 給出了運行20 次象群算法后選取最佳優化結果所對應的優化蟻群算法參數。

表1 算法參數表Tab.1 Algorithm parameter

表2 優化參數值Tab.2 Optimized parameter values

由圖4、5 結果顯示，采用傳統蟻群算法和改進后的蟻群算法，在路徑規劃上結果具有一定差異。通過對比圖6、7 的結果（即改進前后的收斂曲線）可以看出，改進后的蟻群算法結果更優，收斂更快，且算法運行穩定性更高。因此，可以預測該改進方案在復雜的運行環境中優勢會更加明顯。

圖4 傳統蟻群算法仿真結果Fig.4 Simulation results of traditional ant colony algorithm

圖5 改進后蟻群算法仿真結果Fig.5 Simulation results of the improved ant colony algorithm

圖6 傳統蟻群算法收斂曲線圖Fig.6 Convergence curve of traditional ant colony algorithm

圖7 改進后蟻群算法收斂曲線圖Fig.7 Convergence curve of improved ant colony algorithm

傳統蟻群算法和改進后蟻群算法的仿真數據對比結果見表3。從這些數據中可以清晰看出，在路徑長度上，改進算法路徑更優，且其到達收斂時的迭代次數遠遠少于改進之前。改進的蟻群算法運行時間長于傳統蟻群算法，是因為該時間包含了象群算法的運行時間，由于在移動小車運行前進行路徑規劃，所以滿足本文實驗要求。從20 次實驗路徑長度的平均值和方差可以看出，改進后的算法更加穩定。由此證明，使用象群算法選擇參數，在算法收斂速度、穩定性和結果精確度上會優于憑借經驗選取參數。

表3 仿真結果對比Tab.3 Comparison table of simulation results

4 結束語

本文研究了基于蟻群算法改進的移動機器人路徑規劃，改進措施針對蟻群算法在尋優時收斂速度不夠快［14］，并且因參數選擇不當而導致結果陷入局部最優解的情況［15］。在使用柵格法創建環境地圖的基礎上，使用貪婪算法找到次優路徑，以此為依據初始化信息素濃度，提高蟻群算法的收斂速度；加入象群算法解決蟻群算法憑借經驗選擇參數的問題，同時用蟻群算法的各項指標設置了象群算法的適應度函數，讓象群朝著適應度值高的位置移動，以此選出適合的蟻群算法參數，解決蟻群算法因為參數選擇不當而導致的局部最優解問題。仿真結果證明，該改進方案是具有可行性的，并且有助于蟻群算法快速選取全局最優路徑。