廖 錚，楊奇燊，林生杰，鄭曉云，王治坤

（北京理工大學珠海學院，廣東 珠海519000）

蟻群算法是一種元啟發(fā)式的智能搜索算法，與另外的一些模擬式的進化型算法一樣，具有智能的特性。蟻群算法自被意大利學者DORⅠGO[1]于1996年提出，引起了許多研究者的關注。蟻群算法最初是被應用于商旅行問題，取得的效果尚好，但是因為其具有易收斂的缺點，仍需改進。隨著蟻群算法的發(fā)展和改進，因蟻群算法具有易與其他優(yōu)化算法結合的優(yōu)點，蟻群算法逐漸被應用于多個領域。本文首先從蟻群算法原理出發(fā)，再從蟻群算法在機器人中的應用及其發(fā)展趨勢進行描述。

1 原始蟻群算法的基本原理

算法最初期的應用在TSP類型的問題時，主要由初始、信息素更新2部分組成。以簡單的兩點間的距離問題為例，分別取A、B兩點。蟻群路徑圖如圖1所示。

圖1 蟻群路徑圖

第一步，在初始時，從A點到B點的3條路徑上并沒有任何信息素物質影響螞蟻的路徑方向，所以初始時螞蟻路過3條路徑的概率是相同的，3條路徑路過的螞蟻初始時是一樣的。第二步，螞蟻在不斷經過3條道路的過程中，會散發(fā)出一種能夠吸引其他螞蟻的物質——信息素，可以吸引其他螞蟻過來，不斷集中走這一條路。第三步，在初始時，假設螞蟻每分鐘經過的路程相同。由于2是3條道路上路程最短的，則在相同的時間內，螞蟻路過2路上的數(shù)量是最多的，并且因為數(shù)量最多，所以可以散發(fā)更多的信息素，可以吸引更多的螞蟻走2路上，因此，2路上的信息素變得越來越濃密。第四步，經過一段時間的循環(huán)，螞蟻在選擇1、2、3路上的時候會更多地選擇第2路，因為2路上的信息素含量遠大于1、3路的信息素含量，所以推斷出：經過時間的推移，1、3路上基本沒有螞蟻經過，2路上的螞蟻是最多的。

基本的蟻群算法原理核心由下列3條公式組成[2]：

經典的蟻群規(guī)劃模型有3種經典模型，王穎等[3]詳細說明了蟻群算法的3種模型，3種模型分別為cycle system、quantity system、dentisy system。以下是3種模型：

對上述3種經典模型進行了仿真實驗，可得在求解商旅行的問題中，ant cycle system性能是最佳的。

2 蟻群算法的改進與發(fā)展

蟻群算法到現(xiàn)階段位置有2個比較需要改進的缺點，分別為算法的收斂度太短和局部空間尋優(yōu)快。針對這2個缺陷，大部分學者利用蟻群算法的信息素傳播原理，對信息素規(guī)則進行修改。因為信息素的調整策略對算法的收斂性和求解效率具有很大影響的。

有很多國內外的學者利用多種方式對信息素的傳播和揮發(fā)進行修正。如柳長安等[4]利用柵格法并對柵格進行編號，再通過引入自適應的函數(shù)對信息素的含量進行修正，最后再通過研究狼群分配原則再次對信息素進行修正。在螞蟻的前進路上，把路上螞蟻留下的信息含量較低的路線去掉，使得螞蟻在每次迭代中都能找到最多信息素含量的路線，得到最優(yōu)解。針對正反饋過程易陷入局部最優(yōu)解的情況，對蟻群算法進行改進，覃剛力等[5]提出針對信息素矩陣在每一次蟻群迭代中的改變，提出了一種動態(tài)自適應調整信息素的方法改進蟻群算法求解商旅行問題，通過信息素矩陣的改變，達到對蟻群算法的監(jiān)控，實時判斷算法的搜索狀態(tài)，采用強制機制，減小必要的信息素，達到更好的效果。針對螞蟻的易出現(xiàn)停滯現(xiàn)象，鄭松等[6]提出了一種針對全局動態(tài)調整選擇策略的改進蟻群算法，能夠有效抑制蟻群算法的停滯現(xiàn)象，更容易得到局部最優(yōu)解。

3 蟻群算法在機器人上的應用

因為蟻群的數(shù)量龐大、基數(shù)足的特點，可以通過傳播信息素的方法來改變蟻群的路徑規(guī)劃趨勢和移動方向的規(guī)劃。國內外許多學者對此進行進一步的改進和運用。

3.1 蟻群算法在TSP問題上的應用

因為蟻群的數(shù)量龐大、基數(shù)足的特點，可以通過傳播信息素的方法來分配整個蟻群中的任務和對路線進行規(guī)劃。蟻群在尋找食物的過程中，每只螞蟻都會在途徑的路上釋放一種具有信息的因子——信息素，每個螞蟻都能感知到這種物質的存在，并根據(jù)信息濃度的強度指導自己的移動方向。傳統(tǒng)的機器人路徑規(guī)劃一般是在自然環(huán)境中，機器人按照給定的參數(shù)指標和一定的規(guī)則在給定的全局空間中不斷探索一條從開始位置到目標位置的無碰撞路徑。

近年來，國內外的學者都對蟻群算法在路徑規(guī)劃問題上的研究提出了不同的創(chuàng)新點。任紅格等[7]提出的采用修改的算法路徑搜索策略以及創(chuàng)新的啟發(fā)函數(shù)進行規(guī)劃。結合信息素揮發(fā)系數(shù)，解決了平時有時無法搜索到最優(yōu)路徑等問題，提高了搜索算法的的效率，也得到了較為優(yōu)良的路徑規(guī)劃路線。劉輝等[8]基于改進的蟻群算法對無人礦車路徑進行規(guī)劃研究，將速度-坡度作為一個影響因子，結合蟻群算法的狀態(tài)轉移概率建立相關的影響公式。在實際的場景中，具體是在路徑較短的條件下選擇坡度較小的節(jié)點。將每代螞蟻中的優(yōu)良的螞蟻進行局部路徑優(yōu)化，提高搜索路徑的能力。與傳統(tǒng)的蟻群算法進行比較該種算法在實際的采礦類環(huán)境下，改進過后的蟻群算法在采礦的情況下全局尋優(yōu)的能力更為良好，算法的實際收斂速度更快，實際用時較短。鄧向陽等[9]在基本的蟻群算法基礎上提出先驗優(yōu)勢方位角的概念，建立了主優(yōu)勢網格和次優(yōu)網格的模型，在全局的解空間中構建了起始點與目標點互換的交替雙向引導策略，應用在具有復雜障礙物分布的大規(guī)模地圖，改變了傳統(tǒng)蟻群算法信息素結構。由仿真實驗可得出，該算法大大提升了構建初始解及收斂的速度，針對于大規(guī)模場景下的路徑規(guī)劃，改良的蟻群算法在處理大規(guī)模的地圖環(huán)境中可以具有優(yōu)良的適應性，求解的過程也得到了很大的提升，能夠很好地求解在復雜的路況下的復雜路障環(huán)境的問題。李文振等[10]針對在蟻群算法在移動機器人路徑規(guī)劃中存在的一些穩(wěn)定性不足、收斂速度慢、易陷入局部最優(yōu)等問題，優(yōu)化改進了傳統(tǒng)的蟻群算法。主要是通過改進轉移概率來改變轉移規(guī)則，讓螞蟻可以準確預測搜索到下一個最佳柵格位置，同時采用了新的信息素更新規(guī)則可以加快收斂速度，擴大搜索空間。仿真結果表明，該改進算法在路徑搜索效率和收斂速度方面明顯優(yōu)于傳統(tǒng)蟻群算法。藍丹等[11]結合智能車輛的具體動力學方程約束，對規(guī)劃路徑進行平滑和優(yōu)化處理，對智能車在車道障礙物的具體建模場景中，均成功規(guī)劃出一條更為便捷且更為平滑的全局安全路徑。實驗結果表明該方法能夠較好地克服傳統(tǒng)蟻群算法存在的缺陷，能提高算法效率同時優(yōu)化車輛的具體行駛路徑，實現(xiàn)了動態(tài)避障的目標。何雅穎等[12]提出的由起點到終點距離以及地圖參數(shù)來構建全局優(yōu)先區(qū)域，避免算法在龐大的全局空間中進行盲目的搜索；在信息素的更新公式中引入信息素增強因子，再提高相應的路徑信息素含量。采用反向學習來優(yōu)化路徑上的信息素含量，能夠很好地解決傳統(tǒng)蟻群算法存在陷入局部最優(yōu)、收斂速度慢等一些問題。

3.2 蟻群算法的其他應用

自蟻群算法被其他的研究者開發(fā)以來，已經被運用于很多其他的方面，如基于生產的多目標分配問題、集裝箱經典分配問題、無人機的遠距離調度問題、甚至還可以用于電力的用戶規(guī)劃，運用十分廣泛。

孫新宇等[13]基于經典蟻群算法的基本特性和固有特點，對比了最優(yōu)解算法、試探算法和循環(huán)改進算法對解決裝配線問題，不能取得良好的結果之后，便對原有的蟻群算法進行改進和嘗試，在原有的蟻群算法加入局部搜索的機制，利用了比較新穎的蟻群算法解決了混流裝配線的調度問題。四川大學徐剛等[14]基于原有的算法模型對基本特征進行改進，引入了具有變異特征的蟻群算法，利用蟻群中的相互幫助、相互傳遞信息的機制尋找水庫中的水分配的最優(yōu)解，并且本方法較好地解決了動態(tài)規(guī)劃中的水庫群問題優(yōu)化調度中的所特有的“維數(shù)”問題。除此之外，蟻群算法的運用對無人機的位置功能的規(guī)劃也有幫助，柳長安[15]在文中利用蟻群算法不受搜索空間的限制約束和不必要求連續(xù)性和導數(shù)存在的假設的特點，在對無人機的動態(tài)航路的規(guī)劃中有良好的路徑規(guī)劃特性，并提出了改進的蟻群算法，解決了多架無人機的路徑規(guī)劃問題。在配電網的調度規(guī)劃問題中，王志剛等[16]以配電網中的綜合使用費用和過負荷懲罰費最小為目的，提出了一種網架規(guī)劃的數(shù)學模型，把每只螞蟻作為一個線路集合，最后形成一個規(guī)劃方案，有效說明了蟻群算法在配電網的調度規(guī)劃問題中的可行性。同時，東南大學的陳歆技等[17]將線路中的故障定位問題轉化為一種新型的TSP問題，并且采用電力系統(tǒng)中的分級保護的原理對整個配電網進行區(qū)分，最后借助蟻群算法進行局部優(yōu)化，最后較好地解決了配電的故障問題。

4 改進蟻群算法在機器人應用中的未來展望

隨著蟻群算法的不斷改進與發(fā)展，蟻群算法已經能在很多領域進行應用。在未來，蟻群算法與其他各種智能算法結合的改進型蟻群算法將被多次利用并且運用于解決實際問題。但是與其他智能算法相比，蟻群算法還不成熟，蟻群算法的運用還有很長一段時間，仍需要更多的研究者去發(fā)掘和運用。同時，蟻群算法的收斂性問題雖然被眾多學者解決，但是如何權衡收斂速度和收斂次數(shù)的矛盾是最主要的問題。