分組教學蟻群算法改進及其在機器人路徑規劃中應用

蒲興成，宋欣琳

（1.重慶郵電大學 計算機科學與技術學院，重慶 400065;2.重慶郵電大學 理學院，重慶 400065）

路徑規劃是機器人導航基礎技術之一[1-4]。傳統路徑規劃算法有Dijkstra 算法[5]，A*算法[6]等，這些算法是基于圖搜索路徑規劃算法。隨著算法理論發展，基于智能優化路徑規劃算法被廣泛應用于移動機器人路徑避障與導航。所謂智能優化算法就是通過模擬自然界中種群各種自發行為來獲得優化問題最優解。蟻群算法作為經典智能優化算法，因其正反饋性和并行性等優勢，被廣泛應用于移動機器人路徑規劃問題中[7-9]。但同時，該算法也存在收斂速度慢和易陷入局部最優等缺陷。

針對上述蟻群算法存在的缺陷，許多學者基于標準蟻群算法做出了大量改進工作。蟻群算法改進大致分為兩大類。一類是針對蟻群算法自身模型進行改進[10-14]。Gao 等[10]提出一種新的路徑搜索策略。該策略將蟻群分為兩部分，并將這兩部分分別置于環境起點與終點。該算法通過雙向搜索尋找最優路徑，從而提高收斂速度和精度。在Lin 等[11]針對環境中U 型障礙死鎖問題，設計一個自適應啟發式函數，避免螞蟻路徑搜索的初始盲目性和后期單一性。Li 等[12]通過添加自適應函數改變蟻群狀態轉移概率，并結合精英螞蟻和交叉選擇路徑節點，有效提高算法收斂速度。Pu 等[13]提出一種信息素增量計算方法，提高了算法收斂速度。梁凱等[14]為有效提高路徑規劃精度，提出一種基于中心節點替換平滑算法。另一類就是在蟻群算法的基礎上，結合其他算法的優勢彌補蟻群算法的不足[15-20]。Qin[15]提出一基于生物免疫系統行為自適應蟻群算法，這種混合算法能增加可行解的多樣性。Yu[16]合粒子群與蟻群算法的特點，賦予蟻群一個“粒子”特性，通過粒子群算法改變蟻群位置，從而提高蟻群算法收斂速度。Dai 等[17]利用A*算法改善蟻群算法適應度函數，從而有效提高蟻群算法路徑搜索能力。Zhu 等[18]利用人工勢場算法改進蟻群算法適應度函數。這種改進算法能同時兼顧負反饋與自適應度函數的調節，因而該方法能大大加快算法收斂速度。Wu等[19]提出了一種混合蟻群算法，該算法通過對可行路徑交叉變異，增加了解的多樣性，為帶時間窗車輛路由問題解決提供了新的思路。Tao 等[20]結合模糊控制，分階段調整蒸發速率改進蟻群算法，以保證蟻群的全局搜索能力。

雖然上述各種改進策略能在一定程度上改善蟻群算法本身不足，但蟻群算法收斂速度慢和易陷入局部最優缺陷仍難以根本解決。此外，基于改進蟻群算法機器人路徑規劃過多依賴控制參數調整。針對上述問題，本文提出一種基于分組教學優化算法[21]（group teaching optimization algorithm,GTOA）的改進蟻群算法，并將改進算法應用于機器人路徑規劃。GTOA 是一種啟發式隨機群智能算法，該算法模擬課堂教學過程中教師與學生互動影響，從而提升種群整體優化能力，使所有進化個體更快收斂到全局最優解。該算法所需控制參數不涉及優化過程本身，能簡化算法初始設置步驟。GTOA 這一特性可以很好彌補蟻群算法缺點。因此，將蟻群算法與分組教學優化算法相結合，通過改進信息素更新策略和死鎖回退策略，并引入路徑簡化算子，可以有效解決蟻群算法收斂速度慢和易陷入局部最優自身缺陷。數值對比實驗證明該改進算法能有效提高收斂速度以及移動機器人路徑搜索能力。

1 基于分組教學優化蟻群算法改進

1.1 標準蟻群算法

蟻群算法作為群智能優化算法中經典算法之一，最早由意大利學者Dorigo 等[22-23]于20 世紀90年代提出。螞蟻覓食主要依據尋路途中分泌的信息素濃度決定自己爬行方向。距離越短的路徑，相同時間里螞蟻經過的數量越多，路徑信息素濃度就越高，蟻群就更有可能選擇該路徑。蟻群算法就是通過模擬螞蟻覓食行為尋找最優路徑。在標準蟻群算法中，螞蟻根據隨機狀態轉移概率[23]選擇下一路徑節點，隨機狀態轉移概率公式為

式中：α是信息素啟發因子，控制路徑信息素的相對重要性；β是期望啟發式因子，控制路徑節點距離的相對重要性；τij(t)是t時刻i、j兩點間的信息素濃度；dij是i、j兩點間歐氏距離；ηij(t)是i、j兩點間距離倒數。所有螞蟻完成一次尋路后，需對螞蟻經過的所有路徑進行信息素更新[23]：

式中：ρ是信息素揮發系數；Δτij是本次尋路 后i、j兩點間信息素更新的增量；Q是常數，代表信息素強度；Lk是第k只螞蟻在本次尋路中爬行過的路徑長度；Pathk是第k只螞蟻在本次迭代中搜索到的可行路徑節點。

1.2 蟻群算法的改進

傳統蟻群算法在迭代前期，路徑上信息素濃度差別不大，螞蟻在選擇下一爬行節點時概率幾乎是隨機的。在迭代后期，某些路徑節點信息素濃度過高，螞蟻大概率選擇相同節點爬行。這直接導致了蟻群算法收斂速度慢和易陷入局部最優問題產生。針對這兩個主要不足，本文結合分組教學優化算法優點改進標準蟻群算法，即賦予蟻群一個代表尋路能力參數，將該參數用于優化傳統蟻群算法適應度函數，從而改善蟻群全局路徑規劃能力，避免算法陷入局部最優。另一方面，由于分組教學優化算法除了種群參數需要設置以外，算法中個體優化不依賴于其他參數調整，因此與分組教學優化算法結合的改進蟻群算法也能加快算法收斂速度。此外，改進死鎖回退策略，既能夠保證每一次迭代單個個體都能進行路徑搜索操作，也能提高地圖實時更新能力。同時，將U 型死鎖位置標記為障礙，能避免算法發生停滯。值得一提的是，為使算法性能更優，本文進一步改進了信息素更新策略，將標準蟻群算法固定參數調整為與蟻群搜索相關動態參數，有針對性地引導蟻群尋找最優路徑；路徑簡化算子的引進，能有效將路徑上的冗余轉角簡化為直線路徑，實現提高路徑優化精度的目標。下面將結合分組教學、蟻群回退機制、信息素更新策略和路徑簡化算子等方面具體介紹改進策略。

1.2.1 基于分組教學優化算法蟻群算法改進

GTOA[21]是一種啟發式隨機群智能算法，該算法具有較強自適應尋優能力。基于此，為提高蟻群算法全局優化能力和收斂速度，本文在蟻群算法的基礎上引進GTOA。為避免蟻群適應度函數只單純受到達目標點的距離控制，導致蟻群算法易陷入局部最優，先為蟻群添加一個代表尋路能力的自適應參數（以下將該參數簡稱為“尋路能力”）。此外，在教學階段，通過比較GTOA 評價函數，螞蟻按照改進后的適應度函數與隨機狀態轉移概率選擇下一路徑節點，最后完成種群整合等。下面將逐一給出具體操作。

1) 基于改進評價函數的分組教學優化算法

評價函數主要用于評估螞蟻在路徑搜索過程中表現，為使GTOA 適用于蟻群算法，需將GTOA評價函數修改成蟻群個體與路徑長度相關函數，修改后的評價函數為

式中：xk(t) 為螞蟻k在t時刻尋路能力，minLk為螞蟻k尋找到最短路徑長度。由評價函數可知，螞蟻個體搜索到的路徑長度越短，個體評價就越高，因此，該個體通過學習獲得尋路能力越強。

2) 基于改進適應度函數的蟻群算法

為提升蟻群全局優化能力，本文結合GTOA 教學階段[13]來影響蟻群中螞蟻個體尋路能力xk(t)。首先，按照螞蟻尋路能力高低，將蟻群劃分為精英和普通子群，將尋路能力最高螞蟻升級為教師螞蟻。然后，基于GTOA 模仿課堂教與學思想，在教師階段，針對精英子群和普通子群采用不同學習方式，通過向教師螞蟻學習以增強個體尋路能力。不僅如此，在學習階段，每只螞蟻在每一輪迭代中通過自學和隨機向蟻群另一只螞蟻學習，達到增強個體尋路能力目的，并通過比較評價函數確定螞蟻在教學階段后的最終尋路能力。結合螞蟻到目標點距離dij以及螞蟻尋路能力xk(t)，蟻群算法適應度函數 ηij(t)進一步改進為

改進適應度函數通過xk(t)自適應調整蟻群路徑選擇概率。當蟻群距終點較遠時，dij較大，蟻群路徑選擇概率差異較大。xk(t)可以縮小各條路徑被選擇概率，避免算法陷入局部最優。當蟻群接近終點時，dij較小，路徑選擇概率趨近相同。xk(t)可以擴大各條路徑選擇概率，加快蟻群算法收斂，同時也保證蟻群算法求解的多樣性。

3) 種群整合

經過GTOA 教學階段學習，螞蟻個體間尋路能力在各個子群都具備一定差異。根據螞蟻尋路能力降序排列將兩個子群整合，并重新劃分子群，用于下一輪迭代。以此保證在每次迭代中，同時提升精英子群和普通子群螞蟻尋路能力，最終提升整個蟻群尋路能力。蟻群重新整合劃分后，選擇尋路能力最強螞蟻作為下一輪迭代教師螞蟻，其選擇公式為

此外，在分組教學過程中某些螞蟻尋路能力過高或過低，或致使算法陷入局部最優。因此對螞蟻尋路能力值設置一個閾值區間 [Antmin,Antmax]，將超過此閾值區間螞蟻個體尋路能力值設置為該區間邊界值。

1.2.2 蟻群回退機制

傳統蟻群算法無法規避U 型障礙，導致算法易陷入停滯狀態，因此可在該類障礙處用回退機制避免此類問題。Lin 等[11]過建立額外全局和局部禁忌表來標記可能產生死鎖節點位置。任紅格等[24]提出直接讓陷入死鎖螞蟻“死亡”，即跳過此輪迭代搜索過程，直接返回起點。上述回退機制存在計算量大或者可行解減少等問題。為克服此缺陷，本文提出一種新回退機制，即當螞蟻陷入U型障礙時，將該螞蟻所處節點直接標記為地圖上障礙節點并實時更新地圖，然后將螞蟻回退到路徑上一節點重新進行路徑選擇，重復此操作直到另一可達節點出現時結束回退。通過回退機制將U型障礙填充為矩形障礙，從而避免后續螞蟻再次陷入同一U 型障礙，因此能提高算法收斂速度。

1.2.3 信息素更新改進策略

傳統蟻群算法信息素更新策略中，螞蟻經過的所有路徑均采用相同的信息素更新強度。當蟻群完成一輪迭代后，所有可行路徑Lk信息素更新增量相同，這就導致傳統蟻群算法路徑搜索的盲目性增大，螞蟻無法快速鎖定長度更短的路徑。因此，在改進的信息素更新策略中，增加一個動態累加參數cij，增強蟻群尋找最優路徑的引導作用。cij用于記錄Lk成為當前最短路徑迭代輪數，即累加最優路徑信息素濃度，當Lk為當前最短路徑時，cij將加1。此外，將Lk分別與當前局部最優路徑Llocal和全局最優路徑Lglobal進行比較。根據比較結果，對可行路徑信息素濃度采用分級更新強度Q1和Q2。一般來講，Q2>Q1,本文中，Q2數值為Q1數值的兩倍。這樣能使得Lglobal路徑節點信息素增量更大，進一步擴大全局最優路徑在后續迭代中對蟻群路徑搜索引導作用，同時也能避免由于Q1導致的蟻群陷入局部最優。改進信息素具體更新為

改進信息素更新策略引導蟻群往最優路徑方向搜索，可以進一步加快算法收斂速度，增強算法性能。

1.2.4 路徑簡化算子

若路徑存在過多角度較小轉角，則機器人在移動過程中可能會出現失去平衡現象。此外，通過蟻群算法迭代規劃出的路徑如果存在大量轉角，該路徑就不一定是最優路徑。因此，如何消除冗余轉角是路徑規劃時必須考慮的一個問題。路徑簡化算子[17]根據三角形兩邊之和大于第三邊原理消除冗余轉角。改進路徑簡化算子根據路徑中相鄰3 個節點構成的夾角角度進行路徑簡化。若夾角內節點為可達節點，則將該轉角簡化為直線路徑。因此，路徑簡化算子不僅可以縮短路徑長度，而且可以增大轉角角度，讓機器人運動更加平滑。如圖1（a）與圖1（b）中分別為存在90°冗余轉角的兩種情況，圖1（c）中存在45°冗余轉角。通過簡化算子分別簡化為圖2（a）、圖2（b）和圖2（c）中的路徑。

圖1 3 種冗余轉角Fig.1 Three redundant corners

圖2 3 種冗余轉角簡化路段Fig.2 Three redundant corner simplified sections

為說明路徑簡化算子有效性，表1 給出了10 次對比實驗。根據表1 實驗數據可知，路徑簡化算子可以大幅度提高求解最優路徑精度。

表1 路徑簡化算子實驗數據Table 1 Experimental data of path simplification operator

1.3 基于GTOA 改進蟻群算法步驟與流程

基于GTOA 改進蟻群算法主要有如下7 步。

1)初始蟻群規模M，迭代次數K，參數 α,β等，將蟻群劃分為精英與普通兩個子群；

2)螞蟻個體向教師螞蟻學習，通過評價函數評估教師階段最終尋路能力；

3)根據隨機狀態轉移概率與改進后適應度函數，選擇下一路徑節點，并判斷是否需要啟動回退機制；

4)蟻群通過自學和隨機向一只螞蟻學習，通過評價函數確定學習階段最終尋路能力；

5)更新螞蟻經過路徑的信息素；

6)將兩個子群整合為一個種群，按照能力大小再次劃分為精英與普通兩個子群，選擇尋路能力最強螞蟻作為下一次迭代教師螞蟻；

7)判斷是否達到迭代終止條件：若達到迭代終止條件，則采用路徑簡化算子輸出最佳路徑；反之則跳轉至步驟2)繼續求解。

基于分組教學的改進 蟻群算法流程如圖3。

圖3 基于分組教學的改進蟻群算法流程Fig.3 Flow of improved ant colony algorithm based on group teaching

2 數值對比實驗

在數值對比實驗中，使用柵格法進行環境建模，將地圖中不規則障礙擴充為矩形障礙，將移動機器人抽象為一個點。將改進蟻群算法（group teaching ant colony algorithm,GTACO）與傳統蟻群算法（ant colony algorithm,ACO）、改進蟻群算法[24]（improved ant colony algorithm,I-ACO）、混合蟻群算法[25]（improved ant colony algorithm with shuffled frog leaping algorithm,IACO-SFLA）進行仿真模擬實驗對比，在求解精度（最優路徑長度）、收斂速度（迭代次數）和算法運行時間3 個方面驗證GTACO的優越性能。

在20×20 柵格地圖[24]中，將GTACO 與ACO、I-ACO、IACO-SFLA 進行比較。地圖中黑色柵格代表障礙物，白色柵格代表可達節點。地圖左上角為機器人起點，右下角為終點，尋找一條無碰撞的最優路徑。為確保對比實驗嚴謹，4 種算法所包含共同參數設定為相同值[24]，參數值設置如表2。實驗數據統計如表3。4 種算法迭代次數收斂曲線趨勢對比以及GTACO 最優路徑分別如圖4、圖5。

表2 對比實驗參數設置Table 2 Comparison experiment parameter settings

表3 4 種算法數據對比Table 3 Data comparison of four algorithms

圖4 4 種算法迭代曲線對比圖Fig.4 Comparison of iterative curves of four algorithms

圖5 GTACO 最優路徑圖Fig.5 GTACO optimal path planning

表3 和圖4、圖5 中實驗結果表明，ACO、I-ACO無法求解出最優路徑，IACO-SFLA 和GTACO 均能求解出從起點到終點最優路徑。其中GTACO能在較少的迭代次數中達到收斂狀態，相較于IACO-SFLA，GTACO 能在更短時間完成規定迭代次數并求解出最優路徑。

為進一步驗證GTACO 的優越性，采用更復雜40×40 柵格地圖。因實驗地圖規模變大，為使算法實驗效果達到最佳，擴大K和M的值為100。4 種算法最優路徑長度、迭代次數和運行時間對比如表4。4 種算法的迭代次數收斂曲線趨勢對比如圖6。圖7 為GTACO 最優路徑圖。表4 和圖6 中實驗結果表明，在對比實驗使用的4 種算法中，I-ACO、IACO-SFLA 與GTACO 在規定迭代次數中達到收斂狀態，且GTACO 較IACO-SFLA計算出的路徑精度更高，收斂速度更快，算法運行時間也更短。

表4 4 種算法數據對比Table 4 Data comparison of four algorithms

圖6 4 種算法迭代曲線對比圖Fig.6 Comparison of iterative curves of four algorithms

圖7 GTACO 最優路徑圖Fig.7 GTACO optimal path planning

表2～4 和圖4～7 表明，基于分組教學改進蟻群算法（GTACO）的移動機器人路徑規劃能力與基于ACO、I-ACO 和IACO-SFLA 移動機器人路徑規劃能力相比，無論在精確度還是在收斂速度方面都有改善。通過仿真模擬實驗驗證，本文提出的改進蟻群算法適用于移動機器人路徑規劃。

3 結束語

針對蟻群算法在移動機器人路徑規劃中存在收斂速度慢和易陷入局部最優問題，提出了一種基于分組教學優化改進蟻群算法。改進算法結合分組教學優化與蟻群算法優點，即利用分組教學優化算法的整體優化特性，通過蟻群中螞蟻個體之間相互影響，提高蟻群算法全局求解能力，避免算法過早陷入局部最優。該改進算法充分利用分組教學優化算法不依賴過多參數特性，避免路徑搜索能力不過于依賴多個參數，從而加速算法收斂速度。回退機制的改進能進一步避免算法在U 型障礙處陷入停滯，達到提高蟻群搜索可行解多樣性。此外，新的信息素更新策略能強化蟻群更趨向更短路徑，因此更能提高蟻群算法收斂速度。最后，路徑簡化算子能更進一步縮短蟻群路徑，增大轉彎角度，也更易于移動機器人平滑穩定運動。仿真對比實驗證明移動機器人能通過改進算法有效規劃可行路徑，縮短算法運行時間，即提高求解路徑精度和算法收斂速度。接下來，將進一步基于改進蟻群算法在障礙物不規則或受到隨機干擾時研究機器人路徑規劃。