蟻群算法在移動機器人路徑規劃中的應用綜述

張松燦，普杰信，司彥娜，孫力帆

1.河南科技大學 信息工程學院，河南 洛陽471023

2.河南科技大學 電氣工程學院，河南 洛陽471023

1 引言

路徑規劃是移動機器人自主導航最關鍵的一個環節，也是機器人領域的研究熱點[1]。其主要目的是在有障礙物的工作環境中，依據一定的性能指標（行走路徑最短、規劃時間最短及能耗最少等），在模型空間中找到一條從起始位置到目標位置的安全無碰撞的最優或次優路徑[2]。

經過幾十年的發展，國內外學者提出了許多富有成效的路徑規劃方法，如A*算法[3]、人工勢場法[4]、神經網絡[5]、遺傳算法[6-7]、模糊邏輯[8]、粒子群優化算法[9]等。這些方法在移動機器人路徑規劃中取得較好的效果，但面對復雜環境時依然存在一定的缺陷。

蟻群算法是模擬自然界中螞蟻群體覓食行為而提出的一種啟發式搜索算法，具有正反饋、并行計算、魯棒性好等特點，因此許多學者將蟻群算法用于機器人的路徑規劃并取得較好的效果[10-21]。蟻群算法具有較快的收斂速度，但也存在算法搜索停滯和易陷入局部最優等問題。針對這些問題，許多學者對蟻群算法的結構設計、運行機制、參數優化等進行深入研究并提出了許多改進策略。

本文主要討論蟻群算法在移動機器人路徑規劃中的研究進展。首先介紹蟻群算法的工作原理及缺陷分析；然后根據算法的運行機理，從單蟻群、多蟻群及融合蟻群算法等方面分析各種改進策略，旨在為蟻群算法在移動機器人路徑規劃的進一步研究提供依據；最后對蟻群算法在移動機器人路徑規劃的未來研究與發展進行了展望。

2 蟻群算法的工作原理及缺陷分析

2.1 蟻群算法的工作原理

Ant System（螞蟻系統）是意大利學者Dorigo M等受自然界中螞蟻種群的覓食行為特征啟發而設計的一種智能仿生優化算法[22]。Ant System是基本蟻群算法，為其他蟻群算法提供了基本框架，其基本結構如圖1所示。

圖1 螞蟻系統的基本結構

蟻群算法用于機器人路徑規劃時主要由初始化、解構建和信息素更新三部分組成。

步驟1 初始化。包括信息素初始化，啟發信息初始化，以及種群規模、信息素揮發率等參數初值的設置。

步驟2 解構建。解構建是蟻群算法迭代運行的基礎，是算法最關鍵的環節，主要內容是在問題空間依據狀態轉移規則如何構建候選解。當用于路徑規劃時，解構建主要是根據狀態轉移規則選擇下一路徑點，最終形成完整路徑。

步驟3 信息素更新。解構建完成后需要進行信息素更新，信息素更新包括兩個環節。（1）信息素揮發，用于降低路徑上的信息素，減小信息素對未來螞蟻行為的影響，增加算法的探索能力；（2）信息素釋放，螞蟻在其所經過的路徑上釋放信息素，加強對螞蟻未來選擇該路徑的影響，增強算法的開發能力。

步驟4 重復步驟2和步驟3，直到滿足終止條件。

螞蟻系統對所有的路徑都進行信息素更新，既具有較好的優化能力，又能保持良好的種群多樣性，但是由于缺乏對最優路徑的開發，降低了算法的收斂速度。

2.2 蟻群算法的缺陷分析

蟻群算法在機器人路徑規劃領域得到了廣泛的應用，但是存在收斂速度慢、易陷入局部最優、早熟收斂等問題，分析原因如下：

（1）收斂速度慢。蟻群算法中信息素初值相同，選擇下一個節點時傾向于隨機選擇。雖然隨機選擇能探索更大的任務空間，有助于找到潛在的全局最優解，但是需要較長時間才能發揮正反饋的作用，導致算法初期收斂速度較慢。

（2）局部最優問題。蟻群算法具有正反饋的特點，初始時刻環境中的信息素完全相同，螞蟻幾乎按隨機方式完成解的構建，這些解必然會存在優劣之分。在信息素更新時，蟻群算法在較優解經過的路徑上留下更多的信息激素，而更多的信息激素又吸引了更多的螞蟻，這個正反饋的過程迅速地擴大初始的差異，引導整個系統向最優解的方向進化。雖然正反饋使算法具有較好的收斂速度，但是如果算法開始得到的較優解為次優解，那么正反饋會使次優解很快占據優勢，使算法陷入局部最優，且難以跳出局部最優。

（3）優化能力問題。蟻群算法中參數眾多并且具有一定的關聯性，雖然蟻群算法在很多領域都有廣泛應用，但是參數選擇更多是依賴經驗和試錯，不恰當的初始參數會減弱算法的尋優能力。當進行路徑規劃時，為避免形成環形路徑或者重復訪問某些節點在算法中設置禁忌表，但是禁忌表很容易造成“死鎖”現象，減少種群中的有效螞蟻數量，降低算法的優化效率。

（4）種群多樣性與收斂速度的矛盾。種群多樣性對應于候選解在問題空間的分布。個體分布越均勻，種群多樣性就越好，得到全局最優解的概率就越大，但是尋優時間就越長；個體分布越集中，種群多樣性就越差，不利于發揮算法的探索能力。正反饋加快了蟻群算法的收斂速度，卻使算法較早地集中于部分候選解，因此正反饋降低了種群的多樣性，也不利于提高算法的全局尋優能力。

3 單蟻群算法的改進研究

許多學者對上述問題進行了深入研究，尋求降低其復雜度及深度的改進優化算法。改進算法主要從結構改進、參數選取與優化、信息素初始化與更新規則等方面提高算法的優化能力，為后續算法的改進提供理論基礎。

3.1 蟻群算法的結構改進

針對基本蟻群算法存在的問題，許多學者從算法框架和結構上提出了許多富有成效的改進措施，如Ant Colony System[23-24]（蟻群系統，ACS）、Max-Min Ant System（最大最小螞蟻系統，MMAS）[25]、Ant System with elitist strategy（帶精英策略的螞蟻系統，ASelite）[26]、Ant system with elitist strategy and ranking（基于排序的螞蟻系統，ASrank）[26]等經典改進算法，這些改進算法有效地提升了優化能力，但是采用一種固定模式去更新信息素和概率轉移規則，缺乏靈活性，未能解決算法的早熟收斂問題。除此之外，針對具體應用場合，許多學者借鑒已有改進策略提出了許多新的改進方法。

陳雄等[27]在蟻群算法中引入信息素限定措施，并提出了自適應信息素揮發系數的方法來解決蟻群算法中的停滯現象，顯著提高了算法的搜索能力。Dorigo等提出了元啟發式蟻群優化算法（Ant Colony Optimization Meta Heuristic，ACO-MH），為求解復雜問題提供了通用算法框架[28]。為了解決ASelite算法易陷入局部最優解的缺陷，文獻[29]將ASelite算法與插入、交換算子融合，提出混合精英螞蟻系統HEAS（Hybrid Elite Ant System），在增強最優路徑信息素的同時，還減少最差路徑上的信息素，既實現了較好的尋優效果，又能有效地逃離局部最優。文獻[30]在基本蟻群算法中引入精英螞蟻策略和最大最小螞蟻機制，更新精英螞蟻的信息素，在尋優能力和收斂速度之間保持了較好的平衡。文獻[31]在蟻群算法中加入回退和死亡策略，增加螞蟻到達目標位置的概率，減小無效螞蟻對信息素的影響，提高了算法的優化能力。文獻[32]借鑒增強學習中的概念提出了Ant-Q 算法，采用偽隨機比例狀態轉移規則構造候選解，在進行全局信息素更新中強化精英螞蟻對信息素的影響，加快算法的收斂。文獻[33]針對多無人機協調軌跡規劃提出了一種新的最大-最小自適應蟻群優化方法，設置最小信息素和最大信息素路徑，并成功地用于多無人機協調軌跡重規劃。

上述措施主要是針對基本蟻群算法的結構改進，有效增強算法的尋優能力，加快收斂速度，避免早熟收斂。從本質上來說，加大迭代過程中最優解的利用[32]、弱化最差解的影響[29]能顯著改善算法的收斂情況，但是也帶來局部最優問題。為此，算法改進時還應考慮局部最優問題，常見解決方法包括限定信息素的范圍[25]、改進信息素更新[27]、改變狀態轉移規則[23-24，32]及加入擾動項[29]等。算法結構的改進有助于深入理解蟻群算法的運行機制，為進一步的改進優化提供理論基礎，但是已有模型的普適性并不強，需針對具體應用去改進算法結構。此外，蟻群算法僅僅是根據螞蟻的覓食行為啟發而來，然而螞蟻群體還有其他復雜的行為可以借鑒，如：偵查、筑巢等[21]，將這類行為與覓食行為相結合，有望建立新的算法結構，進一步提升算法的優化效率。

3.2 蟻群算法的參數優化

算法參數對蟻群算法的尋優性能具有重要的影響，由于蟻群算法參數多且參數之間存在緊密的耦合作用，確定最優的算法參數成為一個極其復雜的問題。雖然有文獻給出參數選取和優化方法，但是大多是依經驗而定，缺乏理論依據。

Duan 等[34]分析了蟻群算法各個參數對優化性能的影響，通過實驗得出各個參數的最優取值范圍，給出了參數設置的三步優化方案。文獻[27]分析了信息素揮發系數對蟻群算法優化能力的影響，提出自適應信息素揮發系數，提高了算法的全局搜索能力。為了避免陷入局部最優，Jiao 等[35]提出一種用于路徑規劃的多態蟻群優化算法，采用自適應狀態轉移策略和自適應信息素更新策略確保信息素強度與啟發信息在算法迭代過程中的相對重要性。江明等[36]按照設定的參數變化規律自適應調整信息素揮發系數來提高算法的全局尋優能力，避免算法陷入局部最優。Sahu 等[14]提出一種自適應蟻群優化算法用于機器人的路徑規劃，在計算信息素增量時考慮每只螞蟻走過的路徑長度與所用時間，在最優路徑與規劃時間之間做到均衡。針對相鄰柵格的啟發權值差異不明顯導致搜索效率較低的問題，文獻[37]根據柵格到目標點的位置調整狀態轉移中的啟發信息項，不僅提高了搜索速度，而且保持了選擇的多樣性，但是該調整方法與目標點位置有關，缺乏靈活性。Akka等[18]改進了狀態轉移公式，優先選擇具有更多出口的鄰節點作為下一節點，增強了種群的多樣性，避免算法過早收斂。卜新蘋等[38]以非均勻環境模型為基礎，在狀態轉移規則中引入目標距離和障礙物距離等啟發式信息，提出一種距離啟發搜索和信息素混合更新的蟻群算法，使得算法具有較好的適應性和更快的收斂速度。文獻[12]把A*算法概念引入到蟻群算法中，將節點處的估計值作為啟發信息，提高了算法收斂速度。文獻[39]改進了信息素初始化方法，動態調整信息素啟發因子與期望啟發因子，有效減少了螞蟻前期到達最優路徑的迭代次數，但是動態調整策略需要人為確定算法的運行情況，缺乏靈活性，而信息素初始化的改進能加快算法前期的搜索效率，但是卻加大算法早熟的風險。劉振等[40]提出一種多粒度蟻群算法，對每個螞蟻都設置不同的窗口寬度，并根據尋優情況自適應改變蟻群規模，所提算法應用于UAV的多機協同路徑規劃，能有效規避突發威脅，提高規劃效率。

上述研究通常是根據蟻群算法的優化特征進行參數優化，如文獻[27，36]采用的動態調整信息素揮發系數、文獻[35]采用的自適應信息素更新等，這些改進策略將算法參數由固定不變模式改為動態調整模式，用較小的計算負擔提高算法的優化性能，降低算法對參數的敏感性，但是這些動態調整通常是人為設定的參數變化規律或者引入新的參數來劃分不同的運行過程，然而算法的迭代優化過程與設定的參數變化規律是否相吻合并沒有得到保證，使得這類改進缺乏適應性。也有學者通過改進狀態轉移規則[18，37-38]，在保持種群多樣性基礎上加快算法的收斂速度。

3.3 信息素初始化方法的改進

傳統蟻群算法均勻初始化信息素值，該方法簡單易行，但在算法初期存在搜索的盲目性，用于路徑規劃時容易出現死鎖現象，影響算法的收斂速度與優化能力。為解決這一問題，許多學者采用不均勻分配初始信息素的方式，加強先驗路徑信息指導全局尋找最優路徑能力。不均勻分配初始信息素的方法可以分為兩類：

（1）根據任務和最優路徑的特征進行信息素初始化。文獻[41]根據下一節點中鄰接的障礙柵格個數提出了一種非均勻信息素初始化方法，即下一節點離障礙物越近，那么該路線的初始信息素越小，反之就越大，指導螞蟻快速行進和安全避障，加快算法收斂速度。王曉燕等[42]根據零點定理提出不均衡分配初始信息素的方法，不同位置的柵格賦予不同的初始信息素，降低蟻群搜索的盲目性，提高算法的搜索效率，然而該方法將起點與終點組成的矩形區域作為有利區域，區域內的信息素依然相同，改進效果有限，也不適用于復雜地圖。李龍澍等[43]在已經明確起點和終點相對位置的情況下，依據起點與終點之間的方向，對每條路徑上的初始信息素進行區分優化，越朝向終點位置的地方初始信息素濃度越高，引導螞蟻朝著正確的大方向行進，縮減搜索初期的時間消耗。文獻[44]采用當前節點、下一個節點以及起點與終點之間的距離等因素計算信息素初值，得到了不均勻分布的初始信息素。

（2）其他優化算法得到的初始路徑作為信息素初值的參考。文獻[45]利用粒子群算法得到的初始結果去初始化蟻群算法的信息素分布，采用分布式技術實現螞蟻之間的并行搜索。文獻[46]將遺傳算法得到的路徑信息作為一部分初始信息素，與原信息素疊加共同構成信息素初值，取得較好的尋優效果。人工勢場法模型簡單，實時性強，有學者將其用于信息素的初始化。王芳等[47]將人工勢場法的規劃結果作為先驗知識，對蟻群初始到達的柵格進行鄰域信息素的初始化，并通過構建勢場導向權改變螞蟻概率轉移函數，提高了路徑搜索效率。羅德林等[48]利用機器人受到的虛擬人工勢場力及機器人與目標之間的距離構造機器人避障和移動的綜合啟發信息，將蟻群算法和人工勢場法進行有效的結合，提高了常規蟻群算法對最優路徑的搜索效率。

上述兩類信息素初始化改進方法有效地減少算法初期由于盲目搜索導致的路徑交叉、效率低下等問題。基于任務和最優路徑特征的改進方法，計算量小，縮減搜索初期的時間消耗，但是其適應性依賴于環境的特征及任務要求，當環境比較復雜時，其效果并不明顯。第二種改進措施能有效改善信息素的初始分布，但是需要消耗一定的預處理時間進行初始路徑規劃，并不適用于實時應用場合。此外，上述兩類改進策略能改變信息素初值的分布，尤其是傾向于最優路徑的不均勻分布，雖然加快了算法的收斂速度，但是在正反饋的作用下會使蟻群算法更容易陷入局部最優，同時降低了種群的多樣性，不利于得到全局最優解。

3.4 信息素更新規則的改進

信息素更新是蟻群算法最重要的一個環節，包括全局信息素更新和局部信息素更新。這兩種更新都包括信息素揮發和信息素增強。信息素揮發有助于探索問題空間的未知區域，降低陷入局部最優的概率。信息素增強主要是強化螞蟻所經過路徑上的信息素值，增大對后續螞蟻的吸引力。信息素增強需要考慮對哪些路徑進行信息素增強，是全部路徑，還是最優路徑或次優路徑等。

文獻[44]除正常的信息素更新外，引入最好與最差解概念，強化最好解所在路徑上的信息素，減小最差解路徑上的信息素，加快算法的收斂速度。柳長安等[37]參考狼群分配原則對信息素進行更新，增大局部最優路徑的信息素量，同時去除局部最差路徑上螞蟻釋放的信息素，避免算法陷入局部最優，但是該方法縮小了算法的搜索空間，影響了算法的探索能力。針對蟻群算法中螞蟻之間協作不足的問題，黃國銳等[49]通過建立信息素擴散模型，提出一種基于信息素擴散的蟻群算法，使相距較近的螞蟻個體之間能更好地進行協作，有效提高算法的收斂速度和尋優能力。文獻[50]將粒子群算法的局域搜索和全局搜索機制與蟻群算法的信息素更新策略相結合，有效解決了蟻群算法的搜索停滯與早熟收斂問題。趙娟平等[51]用差分演化算法進行信息素的更新，同時在信息素更新環節加入了混沌擾動因子以增強算法的隨機性能，使其有效跳出局部最優點和避免算法停滯。曾明如等[52]提出一種自動調整步長參數的多步長蟻群算法，根據多步長蟻群算法的特點，設計了局部信息素更新策略對路徑節點之間的柵格節點進行信息素更新，使得改進算法更高效，提高了機器人的路徑規劃性能。顧軍華等[53]提出了一種多步長改進蟻群算法，在狀態轉移概率規則中加入拐點參數，改善了路徑的平滑度，設計了新的信息素獎懲機制，有效地避免局部最優，提高算法的收斂速度。文獻[10]提出了一種自由步長的蟻群算法，并設計了相應的局部信息素更新規則，仿真表明該算法尋得的路徑更短，收斂性更好。文獻[54]改進了蟻群算法的全局信息素更新策略和信息素增量計算方法，提高算法的運行效率，減小了陷入局部最優的可能性。陳超等[55]改進蟻群算法的啟發函數和信息素更新方式來提高三維場景下移動機器人路徑規劃的實時性。

文獻[37，44]采用強化最優解的引導作用、減小最差解路徑上的信息素來加快算法的收斂速度，但是降低了算法的探索能力，不利于最優解的獲取。文獻[50-51]借鑒其他智能算法的運行機制改進蟻群算法的更新規則，有效解決了蟻群算法早熟收斂問題，但是算法結構復雜，耗時更多。前述改進措施通常將螞蟻的移動步長局限于單個柵格，規劃的路徑較長、平滑性較差等。文獻[52，56]采用多步長或者可視范圍內自由步長[10]的蟻群算法，這類方法能提高路徑的平滑度，進一步減小路徑長度，但是信息素更新規則需要進一步展開研究，同時還引入了新的碰撞判斷問題。

4 多蟻群優化算法的研究與發展

蟻群算法由初始化、解構建和信息素更新三部分組成，每一部分對算法都有重要的影響。目前大多數單蟻群算法的改進都是從這幾方面展開，以解決收斂速度和多樣性的矛盾，但是這種改進是一種折中方案，未能充分發揮蟻群算法的優化效率。與此同時，一些學者對蟻群算法的架構組成、信息交換模式等展開研究，提出多蟻群優化算法。采用多個蟻群的合作既能保持種群的多樣性，又能提高蟻群算法的優化能力。

在多蟻群優化算法中，蟻群個數大多采用兩個，采用更多的蟻群個數并不能顯著提升優化性能反而增加了運行時間。根據多蟻群算法中各個蟻群的特征，可分為同構多蟻群算法和異構多蟻群算法。為了充分發揮蟻群算法的優化性能，大多采用異構多蟻群算法，即各個蟻群算法結構不同。同時多蟻群算法中各個蟻群的運行機制也有所不同。根據各個蟻群的運行機制，可將多蟻群優化算法分為以下兩種。

4.1 基于順序運行的多蟻群算法

順序運行的多蟻群算法通常是將一個蟻群分為兩個部分，分別置于起點與終點，順序執行各個蟻群算法；或者是按照分層設計的思想將多個蟻群置于不同的規劃層，每一層執行不同的功能。這兩種設計方法一般是通過信息素矩陣進行種群間的信息交換。

王沛棟等[57-58]通過螞蟻的折返搜索策略完成了最優路徑搜索，增強螞蟻搜索的多樣性，避免算法停滯；通過優化禁忌表提高螞蟻的搜索能力，利用雙向螞蟻群體的不同搜索策略提高算法收斂速度。文獻[17]提出一種用于機器人路徑規劃的雙層蟻群算法，利用精英蟻群算法獲得初始無碰路徑，然后采用基于蟻群算法的轉折點優化方法對初始路徑從路徑長度、平滑性以及安全性等方面進一步優化，實驗表明該算法能有效地得到無碰最優路徑。許凱波等[59]設計了基于雙層蟻群算法的機器人路徑規劃方法，每次迭代時將基本蟻群算法找到的最優路徑向外擴展一定的距離構造一個小環境，采用蟻群算法在此空間內進行尋優，如果找到更優的路徑，則更新路徑并執行信息素二次更新策略，雖然提升了尋優性能，但是限制了算法的探索能力，不利于獲取最優解。朱慶保等[60]將蟻群分為兩個部分，分別置于起點與終點，蟻群對向移動，利用螞蟻相遇判斷準則快速構建可行路徑，加快尋路時間。文獻[61]設計了新的螞蟻相遇判斷準則，通過控制方向相反的兩組螞蟻同時進行路徑搜索，充分發揮蟻群的合作性，提高了算法尋優速度。文獻[62]提出基于改進蟻群算法的多批次協同三維航跡規劃算法，引入螞蟻子群間多約束條件下的協同進化策略，有效解決了多無人機多批次協同三維航跡規劃。

4.2 基于并行運行的多蟻群算法

在并行運行的多蟻群算法中，各個蟻群同時運行，蟻群間的信息交換策略是并行多蟻群優化算法的關鍵，包括信息交換的內容、方式、頻率以及交換時機等。

Ellabib 等[63]提出了多蟻群算法的信息交換策略并按照搜索多樣性對各種交換策略進行了評估。文獻[64]提出了并行蟻群算法的信息交流策略，各種群自適應地選擇信息交換對象，根據解的分布情況自適應地確定信息交流的時間，以取得收斂速度和多樣性之間的平衡；信息交換后，根據信息素均勻度采用自適應更新策略進行信息素更新，避免了蟻群算法的早熟和局部收斂。張鵬等[65]利用蟻群間的相似度自適應選擇最互補的蟻群進行信息交換，以加強蟻群間的協作，增強算法逃離局部最優的能力。Lee[66]設計了一個異構蟻群組成的路徑規劃器（HAB-PP），不同種類的蟻群有不同的可視范圍與運動速度，并修改了狀態轉移規則和信息素更新方法，仿真結果驗證了算法的有效性。

在多蟻群算法中，每個種群可采用不同的類型，具有不同的狀態轉移規則和信息素更新機制，經過種群間的信息交換，既能保持蟻群的多樣性，又可改善算法的優化效率。文獻[17，59]所設計的雙層蟻群算法雖然提升了算法的尋優能力，但是卻需要一定的時間進行二次優化，導致優化效率不高。文獻[60-61]將螞蟻分組同時進行相向搜索路徑，螞蟻相遇則構成一條路徑，但是需要設計合適的相遇判斷準則，否則無法找到完整路徑，復雜環境下的規劃效果并不理想。并行運行的多蟻群算法[64-65]能有效平衡收斂速度和種群多樣性之間的矛盾，有利于跳出局部最優，但信息交換策略需要正確設計與優化，不合適的信息交換策略反而會惡化蟻群算法的性能。

5 融合蟻群算法的研究與發展

融合蟻群算法主要是蟻群算法與其他優化算法相混合，彌補蟻群算法的不足，提高算法的優化性能。大量文獻表明，融合蟻群算法更易于獲得全局最優解，避免局部最優，有效平衡算法收斂速度和種群多樣性的矛盾。根據優化方法的功能可將融合蟻群算法分為三類。

5.1 優化方法用于信息素初始化、更新或狀態轉移規則的優化

劉建華等[67]在蟻群算法搜索過程中加入人工勢場局部搜索尋優算法，使蟻群傾向于具有高適應值的子空間搜索，減少盲目搜索引起的局部交叉路徑及“迷失”螞蟻的數量，提高了對障礙物的預避障能力。文獻[68]將路徑規劃分為兩步，首先采用遺傳算法生成初始路徑，將較優路徑作為蟻群算法信息素初始化的參考信息，減少蟻群算法搜索初期的盲目性，然后利用蟻群算法對初始路徑進一步優化，仿真結果表明改進算法能避免局部最優，加快算法的收斂速度。文獻[69]利用粒子群算法和遺傳算法的隨機、快速和全局性，通過粗略搜索獲得一系列次優解用于蟻群算法的初始信息素分布，然后利用蟻群算法獲取最優解。趙娟平等[51]采用帶有信息素下限的蟻群優化算法，結合差分演化算法實現信息素更新的概率型交替，提高算法的協作交流，既保證了算法的收斂速度又確保了算法的多樣性，在一定程度上防止陷入局部最優。

5.2 優化方法用于蟻群算法的參數優化

Mahi 等[70]設計了一種基于粒子群和蟻群的混合算法，用粒子群算法去優化蟻群算法的主要參數。王雪松等[71]提出一種基于圖知識遷移的蟻群算法參數選擇方法，能夠快速得到優化參數，提高了蟻群算法的適應能力。文獻[72]用節點間的采樣信息替代歐氏距離表示的啟發函數，并結合Voronoi 分割方法以增加多個海洋自主航行器（multiple Autonomous Marine Vehicles，AMV）自適應海洋采集任務的覆蓋面，減小了算法的優化時間。針對無人戰斗機的三維路徑規劃，Duan等[20]提出了一種混合蟻群優化和差分進化模型，將螞蟻種群分為幾個子種群，利用DE 的突變操作使得種群間的信息素分布更合理，在保持蟻群算法強魯棒性的同時，加快了全局收斂速度。

5.3 優化方法產生初始路徑

潘杰等[73]在蟻群算法中融入遺傳算子，利用交叉與變異操作來擴大解的搜索空間，提升解的全局性。文獻[74]將路徑規劃分為兩個階段，先由Dijkstra 算法規劃出次優路徑，再用蟻群算法優化這些次優路徑以獲得最優路徑。文獻[75]將問題求解分為兩個階段：第1 階段利用快速反向梯度法獲取可能的優化解；第2階段采用ACO算法進一步提高解的質量。杜振鑫等[76]提出一種基于蟻群算法和模擬退火算法的融合算法，每輪迭代后的路徑用模擬退火進行優化，使信息素釋放更好地反映路徑的質量；同時退火思想還用于信息素更新，有效避免算法早熟。針對自主水下機器人在全局路徑規劃時存在搜索效率低、時間較長等問題，潘昕等[77]提出了一種遺傳和蟻群算法的混合算法，提高了兩種基本算法的融合效率，在保持搜索精度的同時，有效提高算法的收斂速度。

蟻群算法與其他方法相融合，具有強魯棒性、尋優速度快、收斂性強等特點。雖然這些融合策略可以取長補短、優勢互補，有效提升蟻群算法的尋優能力，但是在一定程度上增加算法的復雜程度，同時也需要更多優化時間。

6 蟻群算法的改進總結與展望

6.1 蟻群算法的改進總結

蟻群算法在移動機器人路徑規劃中得到廣泛應用，為了進一步提升蟻群算法的全局尋優能力，許多學者提出了許多富有成效的改進措施，將上述的內容進行總結，如表1所示。

對蟻群算法改進時，除了提升全局優化能力外，還需要處理正反饋帶來的局部最優問題。避免陷入局部最優的常用方法是在算法中保持一定的隨機性或者添加擾動信息，這些措施在一定程度上能避免算法陷入局部最優，但是卻改變蟻群算法正常的迭代優化過程，降低了算法的收斂速度。為了便于對比分析，將常見的逃離局部極值方法總結，如表2所示。

6.2 蟻群算法未來的研究與展望

蟻群算法具有隱含并行性、正反饋、強魯棒性及易與其他智能方法相結合等優點，自提出以來在眾多領域得到了廣泛應用。但是與遺傳算法、粒子群算法等方法相比，蟻群算法的研究還遠不成熟，實際應用方面也尚未挖掘出其真正潛力，還有很多富有挑戰性的課題亟待解決，主要體現在以下幾個方面：

（1）蟻群算法的理論研究

蟻群算法作為一種概率搜索算法，從數學上對其正確性和可靠性進行證明比確定性算法更困難。已有方法過于復雜且要求嚴格，尋找新的理論分析方法是一個亟待解決的問題。此外，蟻群算法的參數設置與優化、信息素分配策略等大多憑借經驗或依靠實驗人為確定，缺少數學證明和普適性，這些問題有待深入研究。

表1 蟻群算法提升全局尋優能力的方法及優缺點

表2 蟻群算法逃離局部極值的方法及優缺點

（2）蟻群算法的多樣性與收斂速度研究

多樣性與收斂速度本質上對應于蟻群算法中的探索與利用。已有許多學者嘗試解決種群的多樣性和算法收斂速度的矛盾，但是收斂速度受諸多因素影響且與問題密切相關，種群多樣性的準確描述也有待進一步研究，因此如何解決種群多樣性與收斂速度的矛盾值得深入研究與討論。

（3）蟻群算法的集成研究

利用算法的互補性，將蟻群算法與其他優化方法相融合，解決蟻群算法的缺陷。由于優化算法類型多，特點不一，新智能算法也不斷涌現，如何選擇合適的融合算法，設計相應的融合策略及運行機制，充分發揮各自優勢，需要深入的研究與分析。此外融合算法雖然能取得較好的優化效果，但是融合策略及運行機制缺乏必要的理論基礎，對此進行研究有助于融合算法的發展。

（4）多蟻群算法的進一步研究

多蟻群算法已在移動機器人路徑規劃中得到了應用，但是依然有許多需要進一步研究的內容。采用多蟻群算法，既能獲得比單蟻群更好的多樣性，又可以提高蟻群的優化能力。單蟻群算法改進時側重于算法的結構設計、參數優化等，而多蟻群算法的研究側重于算法的整體架構設計與群間的協調優化。因此在進行多蟻群算法的研究時，除已有的單蟻群優化策略外，還需要深入研究多蟻群的整體框架與運行機制、蟻群特征、蟻群間的信息交換策略等對優化性能的影響，這也是蟻群算法未來的一個重要研究內容。

（5）擴展蟻群算法的應用范圍

在高維空間、多機器人協同等領域應用移動機器人時也需要進行路徑規劃，而這些場合具有不同的特點與需求，如何將蟻群算法有效運用在這些場合需要深入研究。此外，機器人的工作環境復雜多變，如何提高蟻群算法在動態環境甚至極端環境時的路徑規劃實時性和規劃效率也是今后的重要研究內容。

7 結束語

本文介紹了蟻群算法的工作機制，分析了蟻群算法缺陷的原因。針對蟻群算法在移動機器人路徑規劃中存在的局部最優、收斂速度慢等問題，從蟻群算法結構、參數選取及優化、信息素優化等方面對已有改進方法進行總結分析。為了充分發揮蟻群算法的優化能力，對多蟻群優化算法在移動機器人路徑規劃的應用進行了分類比較與分析。由于單一算法難以解決復雜的優化問題，融合蟻群算法可以取長補短、優勢互補，有效平衡算法收斂速度和種群多樣性的矛盾，提升其尋優能力，按照優化方法在融合算法中的作用對其進行分類分析與總結。最后從蟻群算法的理論研究、算法智能融合、多蟻群算法研究以及應用范圍等方面對蟻群算法在移動機器人路徑規劃未來的研究內容和研究熱點進行了展望。