基于優化蟻群算法的智能機器人路徑規劃研究

樊嘯宇

摘 要：由于利用蟻群算法實現人工智能機器人路徑規劃領域中的算法自身缺陷問題，本文提出一種用于人工智能機器人路徑規劃的改進式蟻群算法。在人工智能機器人路徑規劃方面，采用基于柵格的技術實現路徑量化工作；在獲取全局路徑最優解方面，基于排序的精英螞蟻策略，提高全局最優解的搜索能力并提高算法的收斂速度。通過驗證，基于人工智能的思想，在蟻群算法改良環節中成功引入了集成式算法創新模式，不僅實現了機器人路徑規劃自主選擇性，而且提高路徑尋優準確性和快速響應性。

關鍵詞：人工智能；路徑規劃；蟻群算法；柵格；精英螞蟻策略

中圖分類號：TP242 文獻標識碼：A 文章編號：1671-2064（2018）20-0034-03

1 引言

在人工智能的研究領域中，路徑規劃是至關重要的一項研究分支。基于此，智能機器人的路徑規劃是指在給定的環境模型中，尋找一條從起始點到目標點的最優無碰撞路徑的人工智能式自主擇優過程。

其中蟻群算法是一種經典的啟發式優化算法[1]，模擬了螞蟻覓食的行為，通過釋放信息素標記路徑，之后經過的螞蟻會根據遺留的信息素濃度選擇較優的路徑，經過一定次數的迭代后，能得到全局最優路徑。蟻群算法雖然具有較強的魯棒性、并行性和正反饋機制，具有很強的發現較好路徑解的能力，但是也存在一些明顯的缺陷：（1）每次迭代搜索后僅保留本次最優解，對歷史信息利用率較低，導致算法的收斂速度相對較低；（2）易陷入局部最優解而使算法迭代停滯，不利于更好解的發現。針對蟻群算法的以上缺陷，目前大致有兩種改進方案：一種是在經典蟻群算法的基礎上進行改進[2]，另一種是將蟻群算法與其他智能算法結合，如遺傳算法[3]、免疫算法[4]等。

為了提高蟻群算法的路徑量化分析和獲取全局最優解的能力，本文在路徑規劃構建方面，采用了基于柵格的思想；在獲取全局最優解方面，采用了基于排序的精英螞蟻策略。基于以上人工智能的算法集成創新，實現人工智能機器人路徑規劃獲取全局最優解的過程。

2 基于柵格思想規劃路徑的蟻群算法構建

2.1 構建用于路徑規劃的蟻群算法

在螞蟻k（k=1，2，…，m）的運動過程中，各條路徑上的信息素濃度決定其移動方向。表示在t時刻螞蟻k由柵格i（xi，yi）轉移到柵格j（xj，yj）的狀態轉移概率，由各條路徑上殘留的信息素濃度及路徑的啟發信息計算，螞蟻在選擇路徑時會盡量選擇離自己距離較近且信息素濃度較大的方向。狀態轉移公式為：

（2-1）

其中表示螞蟻k下一步可以選擇的節點，C為全部節點集合；

（k=1，2，…，m）表示禁忌表，記錄螞蟻k當前已走過的城市；

α表示信息啟發因子，反映了信息素濃度的相對重要程度；

β表示期望啟發因子，反映了期望值的相對重要程度；

表示邊（i，j）上的信息素濃度；

表示邊（i，j）上的啟發信息，一般取柵格i到柵格j距離dij的倒數，即。

為了防止殘留信息素濃度過大導致啟發信息的作用不明顯，在螞蟻完成一次迭代后，對信息素濃度進行更新處理。信息素更新規則為：

， （2-2）

（2-3）

其中ρ表示信息素揮發系數，則表示信息素殘留系數；

表示邊（i，j）上的信息素增量；

表示螞蟻k在邊（i，j）上的信息素增量。

2.2 信息素增量的計算

根據信息素增量的不同，M.Dorigo提出三種蟻群算法模型[5-6]：蟻周模型、蟻量模型、蟻密模型。蟻周模型的原理是利用螞蟻經過路徑的總長度（整體信息）計算信息素增量；蟻量模型的原理是利用螞蟻經過的節點間的距離（局部信息）計算信息素增量；蟻密模型的原理是將信息素增量取為恒值，沒有考慮不同螞蟻經過路徑的長短。

鑒于信息素增量計算的普遍適用性和非特定條件約束的前提下，蟻周模型的性能優于其他兩種模型[7]，因此本文采用蟻周模型：

（2-4）

其中Q為常量，表示螞蟻在一次迭代中釋放的信息素總量。

Lk表示第k只螞蟻在本次迭代中經過路徑的總長度。

3 基于排序的精英螞蟻策略改進的蟻群算法設計

由于蟻群算法存在收斂速度慢和容易出現停滯現象等缺陷，本文將采用基于排序的精英螞蟻策略并對之優化，修正蟻群算法的上述缺陷，進而優化蟻群算法獲取全局最優解的過程。

基于排序的精英螞蟻策略改進蟻群算法的具體思路：通過信息素更新，實現螞蟻的解的多種可能性，為最大—最小螞蟻策略突破蟻群算法過早收斂于局部最優解的局面做鋪墊；同時，引入自適應特性的信息素揮發系數更新機制，完善全局解的搜索能力并提高算法自身的收斂速度。

3.1 信息素更新設計

傳統的精英蟻群系統[8]為了使當前找到的最優解在下一次迭代中對螞蟻更有吸引力，在每次迭代結束后給予所有已經找到的最優解額外的信息素增量。這些獲得額外信息素增量的路徑視為被精英螞蟻走過，這些路徑上的某些邊可能屬于全局最優解。

然而精英螞蟻對應的路徑上的額外信息素增量，使得某一條路徑上的信息素濃度急劇增加，降低了后續螞蟻選擇其他最優解的概率，影響了后續螞蟻的解的多樣性，容易造成算法的早熟，使得算法收斂于某一局部最優解。因此，本文在精英螞蟻策略中加入排序策略[9]，將不同的路徑根據信息素濃度進行排序，分別給予不同程度的信息素增量（賦予精英螞蟻的優秀程度越高，給予的信息素增量越大），同時對于每一次迭代中的最優解給予一定的額外信息素增量。這樣提高了后續螞蟻的解的多樣性，解決了因收斂過快而停滯于局部最優解的問題。

具體方法如下：每次迭代完成后，螞蟻按路徑長度排序，即L1≤L2≤……≤L3，根據螞蟻的排名μ對信息素增量進行加權。設ω為當前最優路徑上信息素的權重，ω必然大于等于其它權重。第μ個最優路徑的權重為max{0，ω-μ}。同時，給予當前最優路徑額外的信息素增量。基于排序的精英螞蟻策略下的信息素更新設計則為：

， （3-1）

其中表示只螞蟻在邊（i，j）上根據排名的信息素增量：

（3-2）

（3-3）

（3-4）

其中μ為最優螞蟻排名，為第μ只最優螞蟻在邊（i，j）上的信息素增量，為第μ只最優螞蟻的路徑總長度，為精英螞蟻在邊（i，j）上的信息素增量，為當前最優路徑的總長度。

3.2 最大—最小螞蟻策略

在基于排序的精英螞蟻策略的基礎上，為了進一步避免算法過早收斂于局部最優解，可以引入最大—最小螞蟻策略[10]，即在每次迭代后將各條路徑可能的信息素濃度限制在區間內，超出這個范圍的值被強制設為或者是。這樣可以有效地避免某條路徑上的信息素濃度遠大于其余路徑，使得所有的螞蟻都集中到同一條路徑上，從而使算法不再擴散。

在此基礎上增加信息素濃度平滑機制可以提高性能，即當信息素濃度收斂或接近收斂于最大值時，通過增加選擇低強度信息素濃度路徑的概率以提高發現新解的能力。

， （3-5）

其中和分別為平滑化之前和之后的信息素濃度。

3.3 信息素揮發系數自適應

在基于排序的精英螞蟻策略的基礎上，信息素揮發系數ρ直接影響算法的全局搜索能力及收斂速度[11]。為了既使算法擁有較強的全局搜索能力，又避免其出現停滯狀態，引入信息素揮發系數自適應策略：

， （3-6）

其中為ρ的最小值，γ為揮發系數衰減常數，取0.95。

算法運行初期ρ較大，信息的正反饋作用占主導，從未搜索過的路徑上的信息素濃度趨近于0，再次選擇已搜索過的路徑的可能性較大，收斂速度比較快，易出現局部收斂。后期ρ逐漸減小，信息的正反饋作用逐漸減弱，從未搜索過的路徑信息素濃度增大，搜索的隨機性能增強，全局搜索能力提高，但會降低蟻群算法收斂速度，所以設置一個最小值，防止ρ過小而使算法停滯。

信息素揮發系數自適應更新規則為：

（3-7）

4 技術路線流程設計（圖1）

步驟1：構建柵格模型，初始化改進蟻群算法中的原始參數，設置螞蟻數量m、信息啟發因子α、期望啟發因子β、信息素揮發系數ρ、信息素總量Q、最大迭代次數NCmax。初始化禁忌表，迭代次數NC=1。

步驟2：螞蟻k（k=1，2，…，m）開始遍歷。更新螞蟻k當前位置的禁忌表，根據狀態轉移公式（2-1）計算每個可行柵格的轉移概率，使用輪盤賭的方法選擇下一個柵格。

步驟3：一次迭代完成后，螞蟻按路徑長度排序，根據排名μ對信息素增量進行加權，同時根據信息素揮發系數自適應策略更新信息素揮發系數ρ，共同作用對信息素濃度進行更新。

步驟4：使用最大—最小螞蟻策略，進一步更新信息素濃度。

步驟5：令迭代次數。若，則清空禁忌表，跳轉至步驟2，直到為止；否則輸出全局最優解。

5 仿真和說明

本文以實際真實路徑作為參考，分別采用常規的蟻群算法和改進的蟻群算法在逼近真實路徑方面進行對比。具體仿真參數設定如表1所示。

通過上述參數數值設定，常規的蟻群算法和改進的蟻群算法分別對路徑進行規劃，其路徑規劃效果對比如圖2所示。

從圖2可知，縱坐標代表與理想真實路徑的吻合度，橫坐標表示路徑規劃的耗時。由于改進的蟻群算法較正常的蟻群算法復雜，故路徑規劃前期效果較差；但是，隨著路徑規劃過程不斷迭代，最終采用改進的蟻群算法路徑規劃吻合度高達98.7%，高于采用蟻群算法的路徑規劃吻合度89.4%；同時，在路徑規劃效果達到穩定狀態的過程中，改進的蟻群算法耗時257.4ms小于蟻群算法耗時329.2ms。

仿真結果表明：在路徑規劃吻合度方面，改進的蟻群算法搜索全局最優解的能力得到提升；在節約時間成本方面，改進的蟻群算法收斂速度更快。

6 結語

本文針對人工智能路徑規劃領域的蟻群算法進行改進，設計基于排序的精英螞蟻策略改進的蟻群算法模型，采用排序策略、信息素揮發系數自適應策略和最大—最小螞蟻策略改進信息素更新規則，以完善對全局最優解的搜索能力并提高算法的收斂速度。通過仿真，證明本設計具有理論優勢和實際應用價值，并為后續的人工智能機器人路徑規劃研究提供了參考方案。

參考文獻

[1]Colorni A， Dorigo M， Maniezzo V. Distributed Optimization by Ant Colonies[C]// Ecal91-European Conference on Artificial Life. 1991：134-142.

[2]喻環.改進蟻群算法在機器人路徑規劃上的應用研究[D].安徽大學，2017.

[3]趙凱，李聲晉，孫娟，趙鋒.改進蟻群算法在移動機器人路徑規劃中的研究[J].微型機與應用，2013，32（04）：67-70.

[4]邱莉莉.基于改進蟻群算法的機器人路徑規劃[D].東華大學，2015.

[5]Gambardella M，Dorigo M. Solving symmetricand asymmetric TSPs by ant colonies[C]//Proc of the IEEE Conf on Evol Compu， 1996：622-627.

[6]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transaction on System， Man and Cybernetics： Part B， 1996， 26（1）： 29-41.

[7]胡小兵.蟻群優化原理、理論及其應用研究[D].重慶大學，2004.

[8]B.Bullnheimer， R.F.Hart， C.Strauss. Applying the ant System to the Vehicle Routing Problem. Meta-Heuristics： Advances and Trends in Local Search Paradigms for Optimization. Kluwer， Boston， 1998：109-120.

[9]任瑞春.基于排序加權的蟻群算法[D].大連海事大學，2006.

[10]王鴻豪.基于蟻群算法的機器人路徑規劃及其在港口上的應用探討[D].武漢理工大學，2007.

[11]申鉉京，劉陽陽，黃永平，徐鐵，何習文.求解TSP問題的快速蟻群算法[J].吉林大學學報（工學版），2013，43（01）：147-151.