超強啟發異類蟻群算法的機器人導航路徑規劃

劉 欽

（鄭州財稅金融職業學院，河南 鄭州450048）

1 引言

在物流倉儲中，自動導引小車（Automatic Guided Vehicle，AGV）代替人工進行物料運輸與分揀成為發展趨勢，而AGV運輸路徑長度、平滑性與小車工作效率緊密相連［1］，因此研究AGV導航路徑規劃問題對提高小車工作效率具有重要意義。

根據對工作環境的掌握程度，機器人導航路徑規劃分為全局路徑規劃和局部路徑規劃，研究的是靜態環境下全局路徑規劃問題。從研究時間上講，前期出現的路徑規劃方法有柵格法［2］、可視圖法［3］、人工勢場法［4］等，當前研究熱點為智能算法應用于路徑規劃，方法有人工魚群算法［5］、粒子群算法［6］、遺傳算法［7］等。以上方法針對不同環境下路徑規劃問題具有較好效果，但都存在各自缺陷，比如柵格法和自由空間法環境實行性差，環境改變時需重新建模；人工勢場法存在局部極值和目標不可達問題；智能算法普遍問題是算法自身尋優深度與尋優廣度之間的矛盾，因此機器人路徑規劃仍需進行深入研究。

以柵格環境下機器人路徑規劃為研究課題，提出了開創型螞蟻主導的超強啟發式異類蟻群算法。在傳統蟻群算法基礎上，提出了由開創型螞蟻、傳統型螞蟻、守舊型螞蟻組成的異類蟻群算法；在信息素更新方面，提出了超強啟發式信息素更新方法，實現了規劃路徑短且耗時少的目的。

2 柵格建模與蟻群算法

2.1 柵格環境模型

柵格環境建模法原理簡單，易于實現。使用一定大小的柵格將工作區域進行劃分，當柵格中存在障礙物時將柵格屬性賦值為1，當柵格中不存在障礙物時將柵格屬性賦值為0，這樣就將抽象的工作環境建模為機器可識別的0-1矩陣［8］。

如圖1所示的，真實工作環境，使用柵格法建立的0-1矩陣為：

圖1 真實工作環境Fig.1 Real Working Environment

2.2 蟻群算法

蟻群算法是模擬蟻群覓食行為而提出的算法，最初被應用于解決旅行商問題［9］。記蟻群規模為m，t時刻螞蟻k從城市i向城市j轉移的概率為：

蟻群算法在運行過程中，信息素的更新包括兩個方面：一是螞蟻在行走過程中會留下信息素，二是信息素隨著時間推移不斷揮發，路徑上信息素全局更新方法為［10］：

式中：ρ∈(0,1)-信息素揮發因子所有螞蟻在城市ij間遺留的信息素螞蟻k在城市ij間遺留的信息素；Q-常數，代表信息素總量；Lk-螞蟻k的路徑長度。

3 超強啟發式異類蟻群算法

3.1 異類蟻群

由基本蟻群算法可知，所有螞蟻均按照式（1）選擇下一節點，即蟻群中所有螞蟻為同一類螞蟻，但是按照達爾文生物進化理論，種群中個體越多樣則種群的生存、進化和尋優能力越強，基于這一思想，提出了由異類螞蟻組成的異類蟻群算法，共由以下三類螞蟻組成。

（1）開創型螞蟻。此類螞蟻進行路徑規劃時具有開創性，完全不參考其他螞蟻在路徑上遺留的信息素，只根據下一節點與目標點距離進行概率選擇，即：

（2）守舊型螞蟻。此類螞蟻路徑規劃時比較保守，遵照“前人”傳統進行路徑規劃，即完全按照信息素的引導進行節點選擇，方法為：

（3）傳統型螞蟻。此類螞蟻按照傳統的節點選擇方式進行路徑規劃，節點轉移概率如式（5）所示。

蟻群中的三類螞蟻，守舊型螞蟻完全按照“前人”傳統進行路徑規劃，不具有創新性，路徑的創新和路徑多樣性主要依靠開創型螞蟻和傳統型螞蟻，因此異類蟻群算法尋優性能與各類螞蟻數量比例相關性極大，后文將對各類螞蟻數量比例設置進行實驗。

3.2 超強啟發式信息素更新方法

信息素的全局更新方法有兩種：（1）當所有螞蟻完成路徑規劃后，對所有螞蟻經過的所有路徑進行信息素更新；（2）當所有螞蟻完成路徑規劃后，對最優路徑上的信息素進行更新。第一種信息素更新方法問題在于，對所有螞蟻走過的路徑均進行信息素更新，不僅浪費了算法時間，而且很多路徑不具備參考價值。第二種信息素更新方法問題在于，只對最優路徑信息素進行更新，當算法陷入局部最優時，這種信息素更新方式會將算法牢牢地困在局部最優；其次，這種信息素更新方法只起到了“獎勵先進”的作用，卻未對“后進”路徑進行懲罰。

基于以上兩種信息素全局更新方法存在的問題，這里提出了超強啟發式信息素更新方法，思路為：按照適應度值對路徑進行排序，將排名靠前的1/3路徑作為“先進”進行獎勵，將排名靠后的1/10路徑作為“后進”進行懲罰。這種信息素更新方法既起到了“獎勵先進、懲罰后進”的作用，同時選出了具有參考價值的前1/3路徑進行信息素更新，達到對螞蟻進行路徑規劃具有超強啟發作用。路徑上信息素的獎懲力度隨路徑優劣程度自適應變化，獎勵路徑的信息素增量為：

懲罰路徑上的信息素懲罰量為：

式中：Δχij(t)-所有螞蟻在路徑ij上的信息素懲罰量螞蟻k在路徑ij上的信息素懲罰量。

綜合式（6）（7），得到超強啟發式信息素更新方法為：

3.3 超強啟發式異類蟻群算法流程

根據蟻群中三類螞蟻的節點選擇方法和超強啟發式信息素更新原理，制定超強啟發式異類蟻群算法流程，如圖2所示。

圖2 增強啟發式異類蟻群算法Fig.2 Hyper-Heuristic Heterogeneous Ant Colony Algorithm

4 實驗分析與驗證

4.1 三類蟻群規模確定

超強啟發式異類蟻群算法中包含三類螞蟻，各類螞蟻數量的比例對算法性能影響較大。這里使用Matlab中的兩個基準測試函數確定三類螞蟻數量比例，包括Sphere函數和Griewank函數。其中Sphere函數維度為30，搜索空間為[-100,100]，Griewank函數維度為30，搜索空間為[-600,600]。

超強啟發式異類蟻群算法參數設置為：種群規模m=100，信息素啟發因子α=1，啟發信息啟發因子β=1，揮發系數ρ=0.3，信息素總量Q=1，最大迭代次數Nmax=100。

為了分析三類螞蟻數量比例對異類蟻群算法尋優性能的影響，設置了四種數量分配方法：（1）三類螞蟻等量分配，各占比1/3；（2）以開創型螞蟻為主導的異類蟻群算法，將開創型螞蟻設置為1/2，守舊型和傳統型各占比1/4；（3）以守舊型螞蟻為主導的異類蟻群算法，將守舊型螞蟻設置為1/2，開創型和傳統型各占比1/4；（4）以傳統型螞蟻為主導的異類蟻群算法，將傳統型螞蟻設置為1/2，開創型和守舊型各占比1/4。算法最大迭代次數設置為500次，每種算法對兩個測試函數獨立尋優20次。函數平均值隨迭代次數變化曲線，如圖3所示。

圖3 不同數量比例的尋優結果Fig.3 Optimizing Result of Different Quantity Proportion

由圖3可以看出，對于Sphere函數和Griewank函數兩種基準測試函數，開創型螞蟻主導的異類蟻群算法具有最快的收斂速度和最高的尋優精度，傳統型和守舊型主導的異類蟻群算法尋優能力相對較差。這是因為開創型螞蟻僅以路徑最小為路徑規劃的唯一標準，不受種群內傳統的影響，帶動整個種群具有較強的創新能力。而傳統型和守舊型的創新能力較差，導致以此兩類螞蟻為主導的蟻群算法尋優能力相對較弱。因此將開創型螞蟻為主導的異類蟻群算法應用于機器人路徑規劃。

4.2 機器人路徑規劃

圖4 不同環境下的最優路徑Fig.4 Optimal Path under Different Environment

統計兩種算法在簡單和復雜環境下20次路徑規劃的最優路徑長度、平均路徑長度、路徑長度方差、最優路徑耗時等參數，結果，如表1所示。

表1 路徑規劃結果Tab.1 Path Planning Result

由圖4可知，在簡單和復雜環境下，異類蟻群算法規劃的最優路徑均優于傳統蟻群算法，由表1中數據可知，在簡單和復雜環境下，異類蟻群算法規劃的路徑平均長度遠遠短于傳統蟻群算法，且路徑長度方差也遠遠小于傳統蟻群算法，說明異類蟻群算法不僅規劃的路徑優于傳統蟻群算法，而且算法性能穩定，路徑質量整體好于傳統蟻群算法。另外，異類蟻群算法尋到最優路徑耗時不足傳統蟻群算法耗時的1/3，說明異類蟻群算法尋優速度遠遠高于傳統蟻群算法。這是因為異類蟻群算法中包含三類螞蟻，種群多樣性有利于種群的進化、尋優；其次，以開創型螞蟻為主導，可以拋開蟻群“傳統”對螞蟻個體的桎梏，增強整個種群的尋優能力；再者，對較優路徑獎懲、對較差路徑懲罰的信息素超強啟發式更新方法，使傳統螞蟻和守舊螞蟻快速向開創型螞蟻搜索的較優路徑靠攏，極大地提高了算法收斂速度。

5 結論

提出了基于超強啟發式異類蟻群算法的柵格環境下機器人路徑規劃方法，通過分析與實驗，可以得出結論：（1）由不同類螞蟻組成的異類蟻群算法具有更高的尋優精度和尋優穩定性；（2）超強啟發式信息素更新方法使傳統型螞蟻和守舊型螞蟻迅速向開創型螞蟻搜索的較優路徑靠近，極大地提高了算法收斂速度。