（齊魯工業(yè)大學(xué)（山東省科學(xué)院），山東 濟南 250353）

0 引言

20 世紀(jì)70 年代以來，各國學(xué)者對移動機器人的研究從未停止［1］。進入21 世紀(jì)后，隨著生產(chǎn)力的大幅提高，用機器人來代替人工的趨勢開始不可逆轉(zhuǎn)，特別是5G 時代的來臨，全世界即將邁入萬物互聯(lián)的時代，如何使機器人進行高效的工作成為研究熱點。路徑規(guī)劃是移動機器人實現(xiàn)正常工作的重要前提，對于移動機器人路徑規(guī)劃的研究，根據(jù)提出時間的前后以及算法的本質(zhì)，可以分為經(jīng)典路徑規(guī)劃算法和現(xiàn)代智能路徑規(guī)劃算法［2-3］。經(jīng)典的路徑規(guī)劃方法有D* 算法［4］、A*算法［5］、人工勢場法［6］、柵格法［7］、自由空間法等；智能的路徑規(guī)劃方法有遺傳算法［8］、粒子群算法［9］、人工蜂群算法［10］、蟻群算法［11］等。相關(guān)學(xué)者在這些算法的基礎(chǔ)上進行了創(chuàng)新和改進，以便使機器人適應(yīng)日益復(fù)雜的工作環(huán)境。

經(jīng)典的蟻群算法存在著前期搜索時間長、容易陷入局部最優(yōu)等缺點，難以適應(yīng)日益復(fù)雜的工作環(huán)境，因此近年來相關(guān)學(xué)者針對性地提出了一些改進的方法。董蓉等通過將遺傳算法和蟻群算法結(jié)合，首先用遺傳算法來獲取最優(yōu)解，作為蟻群算法的初始信息素部分，然后利用蟻群算法的正反饋機制進行求解［12］；李旭等利用K-means 聚類的將最優(yōu)路徑問題分成小的TSP 問題，在每個問題中和問題間利用蟻群算法找到最優(yōu)路徑［13］；郭勝國等為了避免使蟻群陷入局部最優(yōu)值，引入分段函數(shù)，利用狀態(tài)轉(zhuǎn)移概率的組合優(yōu)化方法來平衡每條路徑的信息，并且引入了導(dǎo)引函數(shù)來加快蟻群的收斂速度［14］；趙靜等通過使揮發(fā)因子自適應(yīng)變化來提高蟻群算法在全局路徑搜索時的收斂速度［15］。以上改進算法一定程度上克服了傳統(tǒng)算法中存在的不足，但是依舊存在一定的問題，如無法保證蟻群的收斂速度達到最優(yōu)，路徑長度達到最短。

通過重新設(shè)計蟻群算法的啟發(fā)函數(shù)，使得路徑長度較短的路徑更容易被較多的螞蟻選中，而路徑較長的路徑被螞蟻選中的概率變小，以此來提高蟻群選擇的路徑為最優(yōu)路徑的概率。最后通過MATLAB 的仿真對比可以發(fā)現(xiàn)改進后的蟻群算法比經(jīng)典的蟻群算法具有更短的路徑長度和更快的收斂速度，以此來證明改進算法的實用性。

1 經(jīng)典蟻群算法

蟻群算法是學(xué)者Dorigo.M 在20 世紀(jì)末觀察蟻群覓食而提出的一種智能算法，該算法最初提出是為了解決旅行商問題（Travelling Salesman Problem，TSP），后來學(xué)者們發(fā)現(xiàn)該算法在解決路徑規(guī)劃問題時可靠性強，主要體現(xiàn)在蟻群算法的正反饋機制、較強的魯棒性和易于與其他算法結(jié)合等特點。

螞蟻覓食的過程可簡要進行如下概括：假設(shè)一群螞蟻開始在蟻穴到食物間路線不明確的情況下尋找食物，當(dāng)其中一只螞蟻尋找到食物并返回蟻穴時會在運動經(jīng)過的路徑上面留下一些信息素，信息素的作用是告知其他螞蟻這是一條可行的路徑，以便吸引其他的螞蟻來這條路徑搬運食物。路徑上的信息素會隨著時間的推移而逐漸揮發(fā)，也就是說路徑較短的路線上殘留的信息素會比路徑較長的路線上殘留的信息素更多，一段時間后大部分螞蟻便會沿著路徑較短的路線行進，路徑上信息素的濃度反映的便是路徑的長短。但是個別的螞蟻會另辟蹊徑，同時自身分泌信息素，假設(shè)發(fā)現(xiàn)的路徑比原路徑更短，大部分螞蟻就會沿著新發(fā)現(xiàn)的路徑進行覓食。這就是蟻群算法正反饋的過程，最后螞蟻們就會發(fā)現(xiàn)一條最短的路徑。

蟻群算法解決問題的基本步驟如圖1 所示。在算法開始時初始化所有的參數(shù)，并將所有的螞蟻置于出發(fā)點，所有螞蟻按照規(guī)則訪問未訪問的節(jié)點，直至訪問完所有節(jié)點。當(dāng)所有螞蟻完成一遍訪問后更新路徑上的信息素濃度，并且判斷是否達到最大迭代次數(shù)，如果達到，則輸出最優(yōu)解，如果未達到，則在當(dāng)前的搜索次數(shù)上加1 并且所有的螞蟻重新進行迭代直至最大迭代次數(shù)。

2 蟻群算法解決路徑規(guī)劃基本步驟

蟻群算法解決路徑規(guī)劃問題的主要步驟為：

圖1 蟻群算法解決問題基本步驟

1）建立環(huán)境地圖。假設(shè)目標(biāo)環(huán)境已知，首先建立機器人工作環(huán)境，用0 和1 組成矩陣，0 表示機器人通行路徑，1 表示障礙物。

2）初始化參數(shù)。蟻群算法中的參數(shù)較多，應(yīng)在開始規(guī)劃前進行各種參數(shù)的設(shè)置，其中初始信息素矩陣設(shè)置為100×100 階全0 矩陣；螞蟻數(shù)量設(shè)置為m。

3）構(gòu)建解空間。首先將所有的螞蟻置于出發(fā)點，螞蟻將會按規(guī)則訪問所有的節(jié)點，最后計算每個螞蟻走的路徑和長度，求出最優(yōu)路徑。其中螞蟻訪問節(jié)點的規(guī)則為：螞蟻k（k∈［1，m］）根據(jù)各個節(jié)點路徑上的信息素濃度和路徑距離（權(quán)）決定其下一個要訪問的節(jié)點。t 時刻螞蟻k 從節(jié)點i 訪問節(jié)點j 的概率為

式中：α 為信息素啟發(fā)因子；β 為期望啟發(fā)因子；τij（t）、τis（t）為t 時刻，ij、is連線上信息素的濃度；ηij（t）、ηis（t）為啟發(fā)函數(shù)，，其中dij、dis分別為線路ij、is 的長度；Jk（i）為螞蟻k 未訪問節(jié)點集合。

4）更新信息素。在螞蟻釋放信息素的同時，各個節(jié)點之間的信息素也會隨著時間的推移而逐漸消失，參數(shù)ρ 為信息素?fù)]發(fā)因子，表示信息素的揮發(fā)程度。因此當(dāng)所有的螞蟻訪問完一遍所有的節(jié)點之后，每個節(jié)點間的信息素也要進行相對地更新，更新的方式為

單位時間內(nèi)信息素增量的計算主要依靠3 種模型，即蟻周模型、蟻量模型和蟻密模型。蟻周模型根據(jù)螞蟻行進的總長度來計算增加的信息素濃度；蟻量模型根據(jù)螞蟻行進的局部長度信息來計算增加的信息素濃度；蟻密模型則將一個恒值（信息素增加系數(shù)）作為增加信息素的濃度。

蟻周模型計算公式為

式中：Q為信息增加強度系數(shù)，為常數(shù)；Lk為第k 只螞蟻訪問完所有節(jié)點后的路徑長度。

蟻量模型計算公式為

式中：dij為ij 連線上的歐幾里得距離。

蟻密模型計算公式為

由此可見，蟻周模型的計算方式比其余兩種計算方式更科學(xué)，故本文采用的蟻周模型來計算單位時間內(nèi)信息素的增量。

5）判斷終止與迭代。所有的螞蟻完成一次迭代后，判斷迭代次數(shù)是否達到最大，如果達到最大迭代次數(shù)，則輸出最優(yōu)值；否則重復(fù)步驟3）和4），直到完成最大迭代次數(shù)。

在MATLAB 中進行仿真，并根據(jù)多次的仿真實驗對比確定各參數(shù)的初始數(shù)據(jù)。仿真使用20 柵格×20 柵格的環(huán)境地圖，初始信息素矩陣設(shè)置為100×100 階的全0 矩陣；最大迭代次數(shù)設(shè)置為100；螞蟻數(shù)量m 設(shè)置為50；信息素重要程度因子設(shè)置α 為1；啟發(fā)函數(shù)重要程度因子β 設(shè)置為7；信息素?fù)]發(fā)因子ρ 設(shè)置為0.3；信息素增加強度系數(shù)Q 設(shè)置為1。對經(jīng)典蟻群算法的仿真結(jié)果如圖2 和圖3 所示。其中黑色柵格為障礙物柵格，不可通行；白色柵格為自由柵格，可通行，紅色為路線。

圖2 經(jīng)典蟻群算法仿真結(jié)果

圖3 經(jīng)典蟻群算法收斂曲線

從仿真的結(jié)果可知，經(jīng)典的蟻群算法基本上能完成從設(shè)定的起始點到目標(biāo)點的路徑規(guī)劃，但達到最大的迭代次數(shù)時并沒有完成收斂。此時應(yīng)考慮對蟻群的啟發(fā)函數(shù)改進，來達到減少迭代次數(shù)和減少路徑長度的目的。

3 改進啟發(fā)函數(shù)

經(jīng)典蟻群算法的啟發(fā)函數(shù)為

但其忽略了自然界蟻群搜索帶有的隨機性，因此改進啟發(fā)函數(shù)的定義方式，通過引入閾值ζ 來自動調(diào)整蟻群的啟發(fā)函數(shù)，改進的啟發(fā)函數(shù)為

式中：di為經(jīng)過節(jié)點i 的所有路徑的最小值。

通過改進蟻群算法的啟發(fā)函數(shù)，使得路徑長度較短的路徑更容易被較多的螞蟻選中，而路徑較長的路徑被螞蟻選中的概率變小，以此來提高蟻群選擇的路徑為最優(yōu)路徑的概率。利用MATLAB 對改進蟻群算法進行仿真，結(jié)果如圖4 和圖5 所示。在本次仿真中，閾值ζ 設(shè)置的值為5。

圖4 改進后蟻群算法仿真結(jié)果

圖5 改進后算法收斂曲線

從優(yōu)化前后的機器人運動路線圖以及蟻群的收斂曲線可以看出，優(yōu)化后的蟻群算法比經(jīng)典的算法具有更快的收斂速度以及更短的搜索路徑，證明改進后的算法具有可靠性。

4 結(jié)語

介紹經(jīng)典算法的原理以及該算法在解決路徑規(guī)劃問題時一般的步驟，針對經(jīng)典算法中存在的前期搜索時間長，易于陷入局部最優(yōu)等缺點進行改進，通過對啟發(fā)函數(shù)的重新設(shè)計來縮短經(jīng)典算法的迭代時間以及搜索路徑的長度。最后在MATLAB 的仿真下驗證了改進算法的可靠性。下一步將對算法的穩(wěn)定性展開研究。