改進蟻群算法在機器人路徑規劃中的應用

何雅穎，范昕煒

中國計量大學 質量與安全工程學院，杭州310018

機器人路徑規劃是指根據已知障礙環境，自行規劃出一條從起始點到達終止點無碰撞的最優路徑[1]。其中傳統方法包括柵格法、A*算法[2]、人工勢場算法[3]等。隨著智能群算法的發展，遺傳算法[4]、粒子群算法[5]、蟻群算法等也開始應用于路徑規劃中。

蟻群算法（Ant Colony Optimization，ACO）是由意大利學者Dorigo等[6]提出的一種仿生螞蟻覓食的智能群算法，具有正反饋、并行性、強魯棒性和較好適應性的特點，但同時也具有易陷入局部最優、收斂速度較慢和易陷入死鎖等問題。其中信息素對算法結果具有重要影響，不少學者通過信息素不同的設置方式來優化算法。文獻[7]提出非均勻信息素分布劃定起點到終點兩個點為頂點的矩形區域為有利區域，提高該區域的初始值。該方法能有效防止螞蟻在初期向目標點反方向搜索，但是區域內信息素并沒有差別，改進效果有限。文獻[8]提出雙層蟻群算法，先通過外層算法求取最優解延伸其解空間，后利用內層算法進行局部尋優，如果在此空間內找到更優路徑則執行信息素二次更新。該方法雖然提高了最優解的可能性，但是僅限于有限空間探索，算法可能陷入局部最優。文獻[9]引入了最優解與最差解改進信息素更新規則，增強當前最優路徑的信息素，減弱最差路徑的信息素。該方法有效加快了收斂速度，但同時也減少了種群的多樣性，不利于最優解的獲取。文獻[10]提出在算法搜索過程中加入人工勢場局部搜索尋優算法，將人工勢場中力因素轉換為局部擴散信息素，算法有效減少了交叉路徑與螞蟻“迷失”數量，提高了蟻群對障礙物的預避障能力，但算法結構設計較為復雜，環境適應能力有待提高。文獻[11]將遺傳算法與蟻群算法相融合，提出利用遺傳算法生成初始路徑，將較優路徑作為蟻群算法初始信息素的參考信息，減少初期算法盲目性，后利用蟻群算法對初始路徑進一步優化。該改進算法能避免局部最優，但算法運行時間較長。

綜上所述，信息素的設置能有效提高收斂速度，但同時也有可能降低算法尋優能力，不利于獲取最優解。為平衡尋求最優解與算法收斂速度，提出改進的蟻群算法，其中包括：對初始信息素進行非均勻分配，提高收斂速度；提出局部分塊優化策略優化子區域路徑提高求解質量；利用信息素增強因子保留更優解，避免陷入局部最優；引入反向學習對信息素進行優化，改進狀態選擇概率，提高算法全局尋優能力。

1 相關知識

1.1 蟻群算法

1.1.1轉移概率

在t時刻螞蟻m從節點i到節點j由式（1）計算轉移概率并根據輪盤賭法則對下一路徑點進行選擇。

式中，τij(t)為路徑(i,j)間的信息素含量，α為信息素啟發因子，ηij(t)為期望啟發項，通過式（2）計算可得；d(i,j)為路徑(i,j)間的歐式距離，β為期望啟發式因子。α和β分別代表信息素、期望啟發項的重要程度。allowedm表示螞蟻m所有下一可行節點集合。

1.1.2信息素更新

每只螞蟻在行走過程中都會留下一定量的信息素，隨著迭代次數的增加，信息素不斷地增加，同時也在不斷揮發。所有螞蟻完成一次迭代后，會對殘留信息素進行更新，根據式（3）、（4）更新信息素。

式（3）中ρ為揮發系數，Δτij為本次迭代中路徑(i,j)的信息素增量，W為螞蟻總數，為本次迭代中第m只螞蟻在路徑(i,j)留下的信息素。式（4）中值的計算采用的更新方式為蟻周模型，除此之外還有蟻量模型和蟻密模型。式中Q是一個常數，表示信息素強度值，Lm表示第m只螞蟻在本次迭代中所走路徑總長度。

1.2 反向學習

反向學習的概念于2005年由Tizhoosh[12]提出，后被成功用于算法的進化，解決優化問題。以下為反向解定義。

定義1假設x是一維空間的一個實數，x∈[a,b]，因此x反向解為[13]：

定義2假設P=(x1,x2,…,xD)為D維空間中一點，其中xi∈[ai,bi],?i∈{1,2,…,D},則其反向解為Pˉ=

2 改進蟻群算法

2.1 非均勻初始信息素分布

蟻群算法中，螞蟻主要根據柵格間信息素的差異尋求最優路徑，而在傳統的蟻群算法中，初始信息素采用的是均勻分布，因此每只螞蟻的狀態轉移概率只取決于期望啟發項，而柵格間期望啟發項差異較小，因此初期算法由于缺少信息素引導具有盲目性，且搜索速度較慢，最終影響解的質量與收斂速度[14]。因此對初始化信息素進行非均勻分布處理，提高柵格間信息素的差異能有效提高搜索效率。為避免改進后的初始信息素過度或者錯誤引導后續螞蟻探索最優解，信息素的非均勻分布僅針對區域進行差異處理而非單個柵格點，即只提高有利區域內的初始信息素，降低算法陷入局部最優的可能。由于最優路徑多集中于起點S至目標點E的連線附近區域，其區域范圍受障礙物影響，以起點S和目標點E連線作x軸，以連線中點作為原點建立坐標系，以起點至終點距離dSE為長軸，全局優選區域距離ddiff為短軸建立橢圓，其計算公式如式（8）。在該橢圓內的區域為全局優選區域R，并提高優選區域R內的路徑點初始信息素，而不在該范圍內的路徑點則保持原初始信息素值τ0。非均勻初始信息素分布規則如式（7）所示：

式（7）中τ0為信息素初始值，C為全局優選區域信息素增量。式（8）中ddiff與地圖障礙物有關，ξ為環境障礙物占比，ξ越高，則ddiff越大，全局優選區域范圍更廣；r和c分別表示矩陣地圖的行數與列數。

2.2 改進信息素更新規則

信息素的更新包括對原有路徑上信息素的揮發與新增路徑信息素的積累，因此提出局部信息素分塊優化策略對信息素的更新規則進行了改進。

在傳統蟻群算法中，所有的螞蟻完成當前迭代后將對螞蟻路徑進行更新。路徑的好壞評價取決于全局路徑的長度，而忽略了對局部區域路徑的評價。圖1中實線路徑與虛線路徑分別代表歷史最優路徑和當前迭代最優路徑，橫坐標x∈[0,5]時，當前迭代最優路徑更短；而在x∈[5,20]時，歷史最優路徑更短，因此提出局部信息素分塊優化策略。算法初期并不知道路徑將會經過哪些路徑點，無法利用具體坐標作為分割依據，因此將矩陣地圖按x坐標以一定間隔步長n縱向切割均勻劃分為多個區域，n越小容易造成路徑曲折較多，不利于尋求最佳路徑，n較大則達不到分塊優化的效果。如圖1所示矩陣地圖被以步長n=5劃為4個區域，有多個點都經過同一切分線時，以最后經過點作為終止點。隨后引入精英螞蟻[15]的策略，當所有螞蟻完成當前迭代后，對各區域內的最優局部路徑信息素進行更新。全局最優路徑本質上是由各個局部最優路徑組合而成的，對局部最優路徑信息素的更新旨在引導后續螞蟻行駛至該區域內的路徑選擇，一旦螞蟻行駛至該區域最優路徑附近則能通過此策略更大概率選擇最優路徑點。但局部區域路徑優劣如果僅從區域內路徑長度考慮，很容易導致區域內水平方向的路徑被認為是最優而非更接近終點的路徑，因此路徑長度考慮其路徑段與起點和終點的總距離，如式（9）所示。同時由于非均勻初始化信息素的改進，對局部路徑長度的選擇也更有利。

圖1 信息素分塊優化Fig.1 Pheromone block optimization

因為局部更新只是針對局部區域，缺乏全局信息素引導，所以對每個區域內最優路徑更新后，再對螞蟻的全局信息素進行更新。鑒于此前已經對局部最優路徑進行了更新，為了避免信息素重復疊加，只對全局最優路徑信息素進行更新。局部最優路徑更新規則與全局最優路徑更新規則相同，如式（9）和式（10）所示。

式中，當計算局部最優路徑信息素時，Lbest為各個區域內最優路徑長度，Ldist為各局部區域內最優路徑段長度，Lds為路徑段第一個路徑點到起點距離，Lde為路徑段最后一個路徑點到終點距離。在計算全局最優路徑信息素時，Lds和Lds都為0，則Lbest為全局最優路徑長度。

如果只對最優路徑進行更新，隨著迭代次數增加，最優路徑上的信息素累積越來越多，高濃度的信息素含量會導致即使迭代后期出現了比歷史更優路徑，這條新路徑上釋放的信息素仍然遠遠少于現有最優路徑上的信息素，容易陷入局部最優且可能在迭代收斂時丟失該解[16]。針對該問題，在信息素更新規則中引入信息素增強因子r，當出現比歷史更優的路徑時，通過增強因子提高此路徑上的信息素，如式（11）所示。增強因子r隨著當前迭代次數Nc的改變而發生改變，初期r值較小，避免信息素過量疊加防止算法陷入局部最優，后期值較大，加快收斂，如式（12）。

式中，Nmax為迭代總數，Lbest為當前局部區域或全局最優路徑，L為歷史最優路徑。

2.3 改進狀態轉移概率

反向學習的主要思想在于對一個可行解，同時評估其反向解，對比后選擇較優解。蟻群算法的正反饋機制不適用于完全解[17]，因此反向學習更適用于擴展蟻群算法解空間而非評估反向解，通過反向學習增加解空間覆蓋率達到提高求解質量的效果。文獻[12]提出基于反向學習的蟻群系統用于解決TSP問題，文獻[16]提出反向蟻群優化算法解決故障診斷監控參數優化問題。

參考以上文獻，引入反向信息素改進蟻群算法狀態轉移概率，用于路徑規劃尋求最優解。根據反向學習的定義，反向信息素計算如下式：

此時的信息素τij為局部和全局更新完畢后的信息素，分布優化策略已結束，因此式（13）中Lgbest為全局最優路徑長度。第一次迭代過程中不會產生Lgbest，因此第一次迭代時的值為初始信息素。其中確定反向信息素的值為初始信息素τij(0)和最優路徑長度Lgbest，因為信息素的積累由初始信息素和最優路徑長度共同決定。

當螞蟻m在t時刻進行路徑點選擇時，其轉移概率為：

式中，λc為反向概率，λc∈(0,1)，λ為隨機數；當λ<λc時，使用反向信息素計算選擇概率，當λ>λc時，選擇概率為原公式計算值。d(j,e)為下一節點j到終點e的歐氏距離。

3 改進蟻群算法的應用步驟

步驟1建立矩陣柵格地圖，設置起始位置起點S與目標點E；初始化參數，包括信息素啟發因子α，期望啟發式因子β，揮發系數ρ，螞蟻總數W，迭代總數Nmax，信息素強度值Q，反向概率λc，信息素初始值τ0與初始信息素增量C。

步驟2初始信息素非均勻處理。通過式（8）確定ddiff，計算全局優選區域R的范圍，并根據式（7）對初始信息素非均勻處理得出τij(0)。

步驟3路徑點選擇。將W只螞蟻放置于起點處，初始化禁忌表、路徑點、路徑長度，并將起點加入禁忌表中。根據式（14）和（15）計算每一只螞蟻下一路徑點選擇概率，通過輪盤賭選擇下一個節點，并將該節點加入禁忌表中。

步驟4判斷螞蟻是否到達了終點，如果沒有，則返回到步驟3直至到達目標點為止。否則執行步驟5。

步驟5局部信息素分塊更新。當所有螞蟻完成當前迭代后，對所有地圖進行分塊處理，并分別計算每個區域的最佳局部路徑，按式（9）、（10）和（11）分別對每個區域進行信息素更新，此時Lbest為每個區域最優局部解。當出現更優解時，按照式（12）計算增強因子并代入式（11）中進行計算，L為每個區域歷史最優路徑。

步驟6全局信息素更新。在局部區域信息素更新完畢后，按式（9）、（10）和（11）對全局信息素進行更新。此時Lbest為全局最優解。當出現更優解時，按照式（11）計算增強因子并代入式（11）中進行計算，L為全局歷史最優路徑。

步驟7反向信息素更新。按照式（13）對反向信息素進行更新，式中Lbest為全局最優解。

步驟8判斷是否達到最大迭代數。如果達到最大迭代數則輸出當前最優全局路徑，如果沒有，則清空禁忌表，并將迭代次數加1，重復步驟3到步驟7，直到達到最大迭代數。

4 模擬實驗和分析

為驗證改進蟻群算法的有效性，在MATLAB 2018b上進行仿真實驗，操作系統為Win10（64 bit）操作系統，CoreTMi5-10210U處理器，16 GB運行內存。仿真實驗采用兩組對比實驗，分別為20×20、30×30的柵格地圖，并在相同地圖下將本文改進蟻群算法與傳統蟻群算法、文獻[8]算法結果進行對比分析。

4.1 參數選取

蟻群算法參數多利用經驗值取值，并利用多次對比結果選取最佳參數，但算法參數還涉及局部分塊優化的步長n，因此基于以上參數，取分割步長n=1,2,…,c（c為地圖的列數）在隨機20×20、30×30地圖上進行實驗。其余仿真參數設置為：α=1,β=7,ρ=0.2,W=50,Nmax=

從20×20仿真結果圖2（a）來看，n∈[4,6]時，即將地圖分為4~5個區域效果較好，當n較小時，迭代次數比不分塊更高，算法信息素分布分散，難收斂，無法找到較優值，因此路徑長度也比不分塊更長。隨著n的增加，雖然迭代收斂次數有時能較快收斂，但是算法也容易陷入局部最優。從30×30的仿真結果圖2（b）也可以看出這一點，當n∈[4,7]時，對應將地圖分為4~5效果較好，n過長或過短都將影響收斂與最終結果，造成收斂速度與局部最優解的矛盾。基于此，對20×20和30×30都分為4塊，20×20地圖取n=5，30×30地圖取n=6。

圖2 n取值對結果的影響Fig.2 Influence of n value on results

4.2 20×20地圖實驗仿真

在20×20柵格地圖下，分別對傳統蟻群算法、文獻[8]、本文改進算法進行仿真，路徑仿真分別如圖3和圖4所示。最終實驗數據如表1所示：傳統算法路徑規劃長度為32.866，文獻[8]規劃長度為33.452，本文改進算法規劃長度為28.038。本文算法較另外兩種算法路徑規劃長度更短，拐點更少，對比傳統算法與文獻[8]算法，路徑長度分別縮短了14.6%和16.2%，拐點分別減少66.6%和75.0%。傳統蟻群算法收斂次數為21次，文獻[8]為5次，本文改進算法收斂次數為12次。雖然文獻[8]收斂次數為5，但是其求解質量明顯低于本文改進算法，這也說明本文在算法收斂速度與求解全局最優解上平衡得更好。傳統蟻群算法在迭代后期丟失最優解，最后收斂為局部最優值，而由于本文引入了增強因子r避免了這一問題，保留了最優解，避免了陷入局部最優。

圖3 20×20環境下四種算法仿真結果Fig.3 Simulation results of four algorithms in 20×20 environment

圖4 各算法路徑收斂曲線Fig.4 Convergence curve of each algorithm path

表1 20×20環境下各個算法結果對比Table 1 Comparison of results of various algorithms in 20×20 environment

為進一步驗證各個改進環節的有效性，分別對每個環節改進和本文整體改進在20×20柵格地圖下進行獨立實驗，實驗結果如表2所示。初始化與分塊策略這一改進環節對比傳統蟻群算法有效減少了迭代次數，同時找到了更優解。反向學習信息素的引入對比傳統算法也有效提高了算法的全局尋優能力，避免陷入了局部最優，但也由于缺乏信息素引導，導致迭代次數較多。而本文的改進方法綜合以上步驟，結合了收斂速度的提升與全局尋優能力上的改進，能在較少的迭代次數內找到更優解，同時曲線更平滑，路徑拐點數更少。

表2 20×20環境下各改進環節結果對比Table 2 Comparison of results of improvement steps in 20×20 environment

4.3 30×30地圖實驗仿真

在30×30復雜環境下，實驗仿真結果如圖5和圖6所示。隨著地圖的復雜度增加，三種算法收斂迭代次數都有所增加，傳統蟻群算法收斂曲線波動較大，算法穩定性較差，且依然陷入了局部最優。文獻[8]雖然對比傳統算法結果更優，但由于該算法僅針對于最優解拓展出來的小區域進行局部優化，缺少全局探索，因此也陷入局部最優。最終實驗數據如表3所示，綜合指標來看，本文改進算法在復雜環境下也有不錯效果。最優路徑長度上來看，本文改進算法路徑長度對比傳統蟻群算法和文獻[8]分別縮短了14.1%和7.9%，拐點個數減少63.3%和60.0%，迭代次數減少23.0%和39.3%。在30×30地圖上也對各個步驟的改進進行了驗證，如表4，其結果與20×20地圖結果類似，再一次驗證了本文算法的有效性與優越性。

圖5 30×30環境下四種算法仿真結果Fig.5 Simulation results of four algorithms in 30×30 environment

圖6 各算法路徑收斂曲線Fig.6 Convergence curve of each algorithm path

表3 30×30環境下各個算法結果對比Table 3 Comparison of results of various algorithms in 30×30 environment

表4 30×30環境下各改進環節結果對比Table 4 Comparison of results of improvement steps in 30×30 environment

5 結束語

本文針對傳統蟻群算法存在易陷入局部最優、收斂速度慢等不足，提出改進蟻群算法。首先根據地圖的障礙物占比以及矩陣地圖大小構建全局優選區域，對初始信息素進行差異化處理，提高區域內信息素初始濃度而非具體柵格點信息素濃度，避免陷入局部最優的同時提高了收斂速度；利用局部信息素分塊優化策略對矩陣地圖進行分塊處理，分別對各個子區域進行尋優并更新最優路徑信息素，后對全局路徑進行尋優，更新最優路徑信息素。為避免只更新最優路徑信息素，丟失更優解，在信息素更新公式中引入增強因子，保留更優解，避免收斂于次優解。最后應用反向學習優化信息素，改進狀態選擇概率，拓展了解空間，提高了全局搜索能力。實驗結果表明，改進后的算法明顯提高了收斂速度，尋優能力更強。對初始化非均勻分布的處理、信息素更新規則的改進以及反向學習在蟻群路徑規劃上的應用對比傳統算法均有明顯的改進，進一步驗證了算法的有效性與優越性。