李東東，王 雷，馬康康

(安徽工程大學(xué) 機(jī)械工程學(xué)院，安徽 蕪湖 241000)

隨著互聯(lián)網(wǎng)的普遍應(yīng)用，各個(gè)領(lǐng)域使用越來越多的機(jī)器人來完成一些重復(fù)性的勞動(dòng).諸如物流領(lǐng)域的貨物搬運(yùn)機(jī)器人，醫(yī)用的手術(shù)輔助機(jī)器人，制造業(yè)的加工機(jī)器人，家庭用的清潔機(jī)器人等.由于機(jī)器人的廣泛應(yīng)用，對(duì)機(jī)器人的路徑規(guī)劃研究變得尤其重要.

近些年來，智能算法的迅速發(fā)展使機(jī)器人路徑的規(guī)劃變得高效化和簡(jiǎn)單化，常見的算法有遺傳算法[1]，粒子群算法[2]，人工勢(shì)場(chǎng)法[3]，A*算法[4]，蟻群算法[5-7]等.其中，蟻群算法作為一種基于種群的概率選擇算法，與其它啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性和較好解的搜索能力，且容易與多種啟發(fā)式算法結(jié)合進(jìn)而改善算法性能[8]，因此，蟻群算法在路徑規(guī)劃領(lǐng)域中得以廣泛應(yīng)用.文獻(xiàn)[9]將蟻群算法用于智能作業(yè)車間AGV 調(diào)度問題，文獻(xiàn)[10]用蟻群算法設(shè)計(jì)了一種小型無人機(jī)高性能動(dòng)力學(xué)模型辨識(shí)方法，取得了較好的效果.但蟻群算法也存在一些缺點(diǎn)，如收斂速度慢、容易陷入局部最優(yōu)解等.針對(duì)這些不足，國(guó)內(nèi)外諸多學(xué)者嘗試著對(duì)傳統(tǒng)的蟻群算法進(jìn)行改進(jìn)，如陳勁峰等[11]通過提出一種自適應(yīng)信息素給予機(jī)制，避免算法受到非最優(yōu)路徑上信息素影響而最終陷入局部最優(yōu)解；曹新亮等[12]選擇將初始信息素進(jìn)行差異化設(shè)置，以達(dá)到防止非最優(yōu)路徑上的信息素對(duì)螞蟻產(chǎn)生誤導(dǎo)的作用，從而加快算法的收斂速度.以上算法依舊存在一些缺陷需要彌補(bǔ)，比如螞蟻的選擇策略受制于信息素濃度，而濃度是由路徑?jīng)Q定的，故存在冗余部分的路徑，其產(chǎn)生的信息素濃度將受到冗余路徑的干擾，進(jìn)而影響螞蟻的選擇正確率.基于以上存在的問題，本文提出一種新的改進(jìn)蟻群算法，即通過引入終距指數(shù)這一概念，取代信息素濃度的標(biāo)記功能，從而螞蟻可以依賴該指數(shù)進(jìn)行決策選擇.仿真實(shí)驗(yàn)結(jié)果表明，采取本文新改進(jìn)蟻群算法，算法的性能有明顯的改善.

1 傳統(tǒng)蟻群算法

蟻群算法(Ant Colony Optimization,ACO)是一種尋找優(yōu)化路徑的概率型算法.它由Marco Dorigo 于1992 年在其博士論文中提出[13]，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為.其最初主要被應(yīng)用于研究TSP 問題，并表現(xiàn)出良好的求解效果，因此該算法得到進(jìn)一步的發(fā)展.隨后，在路徑規(guī)劃領(lǐng)域，蟻群算法也展現(xiàn)出較好的搜索能力，正反饋特性、分布式計(jì)算等等.但由于該算法的本質(zhì)是一種基礎(chǔ)算法，故在路徑規(guī)劃應(yīng)用中還存在一些缺陷，比如收斂速度較慢、易陷入局部最優(yōu)解等，因此，對(duì)該算法的改進(jìn)也成為了路徑規(guī)劃領(lǐng)域的一個(gè)熱門課題.

1.1 環(huán)境模型在路徑規(guī)劃的研究中，對(duì)環(huán)境的建模方法有很多，其中以柵格圖最為簡(jiǎn)單有效.柵格法是Howden 在1968 年提出的[14]，并用于路徑規(guī)劃問題環(huán)境.其原理可以簡(jiǎn)單地描述為：假定機(jī)器人的運(yùn)動(dòng)空間是一個(gè)水平的二維平面，對(duì)平面進(jìn)行矩形切割，通常采用20×20 的切割策略.將沒有障礙物的柵格標(biāo)記為0，被障礙物充滿或者部分填充的柵格標(biāo)記為1，這樣，就可以將一個(gè)真實(shí)的物理環(huán)境，映射成一個(gè)只包含0 或1 的數(shù)字矩陣.環(huán)境的柵格圖模型如圖1 所示.

圖1 柵格模型Fig.1 Grid model

另外，機(jī)器人在柵格范圍內(nèi)移動(dòng)時(shí)，對(duì)其軌跡方向可以簡(jiǎn)化等效為8 個(gè)方向，如圖2 所示.

圖2 機(jī)器人移動(dòng)方向圖Fig.2 Robot’s moving directions

1.2 基本蟻群算法解決思路初始化一定數(shù)量m的螞蟻，進(jìn)入迭代循環(huán)，在每一次的循環(huán)中，螞蟻按概率選擇節(jié)點(diǎn)移動(dòng)，直到移動(dòng)至終點(diǎn)或者無法移動(dòng)為止.節(jié)點(diǎn)選擇方法有很多，這里采用最經(jīng)典的輪盤賭法，選擇概率受信息素以及距離啟發(fā)因子的影響，每個(gè)節(jié)點(diǎn)的概率依據(jù)全概率公式生成，如：

其中，di j為節(jié)點(diǎn)（i，j）到終點(diǎn)（ie，je）的歐式距離，公式為：

當(dāng)一代螞蟻移動(dòng)終止后，環(huán)境中的信息素將會(huì)按照式(4)進(jìn)行削減，以模擬現(xiàn)實(shí)中的揮發(fā)效果.

其中，ρ是揮發(fā)系數(shù).另外，根據(jù)當(dāng)代螞蟻的行駛軌跡，對(duì)路線上的節(jié)點(diǎn)依據(jù)式(5)進(jìn)行信息素更新.

其中，Q為單只螞蟻在一條路徑上留下的總信息素量，Lk為第k只螞蟻?zhàn)哌^的路徑總長(zhǎng)度.

2 改進(jìn)蟻群算法

在傳統(tǒng)蟻群算法中，螞蟻在選擇節(jié)點(diǎn)時(shí)，依賴于信息素濃度來進(jìn)行節(jié)點(diǎn)選擇，但由于信息素濃度的生成受制于路徑長(zhǎng)度，而路徑又可能含有冗余成分，因此，信息素濃度無法直接表明節(jié)點(diǎn)的優(yōu)劣，這會(huì)使得螞蟻不容易找到最短路徑，收斂速度過慢.于是，本文重寫信息素，旨在強(qiáng)調(diào)信息素與節(jié)點(diǎn)優(yōu)劣的關(guān)系，引入終距指數(shù)代替信息素的作用，螞蟻能通過終距指數(shù)更好地感知某節(jié)點(diǎn)的優(yōu)劣.

2.1 終距指數(shù)的引入在傳統(tǒng)的蟻群算法中，螞蟻是通過環(huán)境的信息素濃度以及距離啟發(fā)因子來選擇下一步的走向，其中，信息素濃度總是繼承于上一代螞蟻的可行路徑.然而，信息素濃度并不能有效地反映某一節(jié)點(diǎn)的優(yōu)劣程度，因?yàn)閺乃惴ǖ倪壿嬌蟻碚f，信息素是若干條路徑的某種表示的疊加，因此可能存在冗余路徑，那么，冗余部分可能就會(huì)使得路徑上的某一節(jié)點(diǎn)變差.以圖3 為例進(jìn)行加以說明.

圖3 經(jīng)過某定點(diǎn)A 的不同路徑圖Fig.3 Different moving paths through a fixed point A

圖3 為3 條條螞蟻?zhàn)叱龅穆窂?，假定左下角的?jié)點(diǎn)為0，右上角的節(jié)點(diǎn)為399，節(jié)點(diǎn)序列由左向右，由下向上遞增，則圖3 中的兩條路徑的節(jié)點(diǎn)信息分別是：

3 條路徑的總長(zhǎng)度分別是Lsum_1=35.80，Lsum_2=38.04以及Lsum_3=30.97，其中，第三條路線為全局最優(yōu)路徑.圖中標(biāo)記節(jié)點(diǎn)A 的序列為266，對(duì)于A 點(diǎn)來說，前兩個(gè)路線產(chǎn)生的信息素濃度根本無法反映出A 點(diǎn)的好壞，因?yàn)槁窂街械娜哂嗖糠謺?huì)干擾節(jié)點(diǎn)上的信息素濃度，盡管可以通過迭代的方式去慢慢消除這種影響，但是嚴(yán)重影響收斂速度.

分析3 條路徑信息可知，如果能提取出3 條路徑中好的部分，而忽略甚至棄用冗余部分，用提取的若干個(gè)好的片段進(jìn)行組合，則可以加快最優(yōu)路徑的產(chǎn)生.首先，本文引入終距指數(shù)kij的概念，kij為i行j列的節(jié)點(diǎn)的終距指數(shù)，該值代表了該節(jié)點(diǎn)到終點(diǎn)的已知距離.每當(dāng)各代螞蟻都行動(dòng)后，依據(jù)當(dāng)代所有可行解來對(duì)各節(jié)點(diǎn)進(jìn)行kij更新，從每條路徑的最后一個(gè)節(jié)點(diǎn)開始反向更新kij.更新的原則是：初始化節(jié)點(diǎn)的kij為99，更新時(shí)，若某節(jié)點(diǎn)新產(chǎn)生的kij小于現(xiàn)有的kij，則更新，這意味著該節(jié)點(diǎn)到終點(diǎn)發(fā)現(xiàn)了新的最短距離，否則，代表了沒有發(fā)現(xiàn)新的最短路徑.不更新kij.kij的計(jì)算公式如下：

以上述案列中的第一個(gè)路徑為例，取A 節(jié)點(diǎn)為研究對(duì)象，按照前述的算法邏輯，從最后一個(gè)節(jié)點(diǎn)進(jìn)行反向更新kij，故有k19?19=0，由于前一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)之間的路徑是直線而不是斜線，另外本文定義單位柵格長(zhǎng)度為1，因此，k18?19=1，若路徑線段為斜線，則為1.414，即k17?18=1+1.414=2.414，以此類推，得到A 節(jié)點(diǎn)的終距指數(shù)k6?13=17.726，當(dāng)?shù)诙l路徑的終距指數(shù)更新時(shí)，會(huì)發(fā)現(xiàn)A 節(jié)點(diǎn)新的終距指數(shù)=17.14，由于即表明對(duì)于A 節(jié)點(diǎn)來說，出現(xiàn)了新的更短的到達(dá)終點(diǎn)的路徑，故更新A 的終距指數(shù)，按照既定的邏輯執(zhí)行完其余的節(jié)點(diǎn)的更新.注意，當(dāng)這些步驟完成時(shí)，如果從起點(diǎn)位置按照最大梯度連接一條指向終點(diǎn)的路徑，就會(huì)發(fā)現(xiàn)新的路徑是由兩條路徑的中若干段節(jié)點(diǎn)到節(jié)點(diǎn)的最短路徑組合而成，由于對(duì)于各節(jié)點(diǎn)來說，僅保留最優(yōu)的結(jié)果，因此，面對(duì)已有數(shù)據(jù)中的更優(yōu)解，新產(chǎn)生的路徑中的冗余部分將無法產(chǎn)生不良的影響.

2.2 終距指數(shù)抗干擾能力分析為了進(jìn)一步證明終距指數(shù)對(duì)生成路徑中的局部冗余路段具備抗干擾能力，將上述案例推廣到一般模型，簡(jiǎn)化環(huán)境模型為4×4 無障礙物柵格圖，將最優(yōu)路徑分成兩段并分別置于兩個(gè)非最優(yōu)路徑中，如圖4 和圖5 所示.

圖4 4×4 無障礙物柵格環(huán)境模型Fig.4 4×4 grid model for no obstacle

圖5 包含最優(yōu)路徑信息的兩段路徑(圓圈標(biāo)記節(jié)點(diǎn)為最優(yōu)路徑節(jié)點(diǎn))Fig.5 Two segment paths with optimal path information (The circle marked node is the optimal path node)

由路徑1 與路徑2 單獨(dú)決定的終距指數(shù)矩陣如圖6 中所示(默認(rèn)值設(shè)為99).觀察圖6，在以路徑1 對(duì)應(yīng)的終距指數(shù)矩陣為基準(zhǔn)的基礎(chǔ)上，更新路徑2 對(duì)應(yīng)的終距指數(shù)信息的過程中，依次更新終距指數(shù)0,1,2，但在更新終距指數(shù) 3時(shí)，由于現(xiàn)存對(duì)應(yīng)節(jié)點(diǎn)終距指數(shù)為2.41 ＜3，即路徑2 中該節(jié)點(diǎn)至終點(diǎn)的局部路徑相對(duì)路徑1 來說含有冗余成分，因此舍棄終距指數(shù)3，保留原值2.41，并且在路徑2 后續(xù)的節(jié)點(diǎn)更新都基于原值2.41進(jìn)行，即將路徑2 中劣質(zhì)的局部路徑信息替換成路徑1 中更優(yōu)良的局部路徑信息，同時(shí)，在之后的更新中，即更新終距指數(shù)3.41與4.82，這意味著路徑1 中的劣質(zhì)局部路徑信息被路徑2 中更優(yōu)良的局部路徑信息替換.

圖6 終距指數(shù)更新機(jī)制演示Fig.6 Demonstration of renewal mechanism of terminal index

由上述內(nèi)容可知，兩條路徑中的優(yōu)良局部路徑信息可以相互優(yōu)化對(duì)方的劣質(zhì)局部路徑信息，從而使得各自所包含的優(yōu)良局部路徑信息得以遺留下來，進(jìn)而組合成算法得到的最優(yōu)路徑信息.對(duì)比信息素濃度機(jī)制，無法快速?gòu)纳鲜鰞蓷l路徑中找到最優(yōu)路徑信息，因此通過此法可以有效加快算法的尋優(yōu)速度.

2.3 概率選擇策略由于去除了信息素濃度，因此概率選擇策略也需要相應(yīng)修改.首先，由于kij分布的范圍較大，其直接作為概率選擇策略的影響因素欠合適，又考慮到相鄰節(jié)點(diǎn)的終距指數(shù)之差較小，在計(jì)算概率時(shí)，可以先對(duì)所有的相鄰節(jié)點(diǎn)的kij進(jìn)行整體縮減，放大偏差處理，如：

其中，kmin為所有相鄰節(jié)點(diǎn)中的最小終距指數(shù)，q為削減系數(shù)，取值0.8，為更新后的終距指數(shù).經(jīng)實(shí)驗(yàn)，完全可以直接帶入概率選擇策略中進(jìn)行計(jì)算，故而概率選擇公式應(yīng)如下：

其中，α為距離啟發(fā)因子，β為終距指數(shù)啟發(fā)因子，allowedk指螞蟻k可選擇的下一節(jié)點(diǎn)的集合.

另外，由于原信息素濃度與選擇的關(guān)系是正比例關(guān)系，即濃度越高，選擇的概率越大，但終距指數(shù)恰恰相反，指數(shù)越小，被選擇的概率應(yīng)當(dāng)越高，因此，需要將原來的輪盤賭法的選擇機(jī)制改為排除機(jī)制，也就是說，通過輪盤賭選擇節(jié)點(diǎn)，選中者直接丟棄，循環(huán)執(zhí)行，直到只剩下一個(gè)可選節(jié)點(diǎn).輪盤賭反向選擇的流程框圖如圖7 所示.

圖7 輪盤賭反向選擇框圖Fig.7 Flow chart based on roulette reverse selection

2.4 算法步驟基于上述內(nèi)容，改進(jìn)后的蟻群算法步驟如下：

步驟 1將機(jī)器人的運(yùn)動(dòng)環(huán)境進(jìn)行數(shù)字編碼，對(duì)編碼得到的0-1 矩陣映射為柵格圖模型.

步驟 2初始化所有節(jié)點(diǎn)的終距指數(shù)k′ij，以及距離啟發(fā)因子 α，終距指數(shù)啟發(fā)因子 β，螞蟻數(shù)量m，迭代次數(shù)T以及削減系數(shù)q等其它算法參數(shù).

步驟 3開始進(jìn)入循環(huán)迭代.

步驟 4將各代螞蟻放至初始點(diǎn)，按照?qǐng)D2 的運(yùn)動(dòng)規(guī)則，借助式(9)進(jìn)行概率選擇下一個(gè)節(jié)點(diǎn).

步驟 5判定當(dāng)前點(diǎn)是否為終點(diǎn)，如果是，就終止尋路，并記錄下路徑信息；否則，繼續(xù)選擇下一個(gè)節(jié)點(diǎn).

步驟 6當(dāng)代螞蟻尋路結(jié)束后，取出當(dāng)代所有可行路徑解，依照式(7)對(duì)各節(jié)點(diǎn)進(jìn)行終距指數(shù)的更新.從起點(diǎn)開始，通過基于終距指數(shù)的最大梯度下降法，得到一條最優(yōu)路徑作為當(dāng)前代的最優(yōu)解.

步驟 7循環(huán)T代后結(jié)束，輸出全局最優(yōu)解.

2.5 算法時(shí)間復(fù)雜度分析考慮到本文提出的改進(jìn)策略主要是用終距指數(shù)代替信息素，從而改變螞蟻概率選擇可行節(jié)點(diǎn)的概率計(jì)算方法，進(jìn)而影響螞蟻的尋路結(jié)果，進(jìn)一步分析可以發(fā)現(xiàn)，信息素對(duì)蟻群算法時(shí)間復(fù)雜度的影響主要來源于信息素的更新機(jī)制，因此，在探討改良策略對(duì)原算法的時(shí)間復(fù)雜度影響時(shí)，僅需研究原算法中信息素的更新機(jī)制與改良算法中的終距指數(shù)的更新機(jī)制即可.

信息素濃度的更新機(jī)制的步驟如下：

步驟 1設(shè)獲取某條可通行路徑L，構(gòu)成其的n個(gè)節(jié)點(diǎn)為l0,l1,l2,···,ln，每只螞蟻一次行動(dòng)釋放的信息素總量為E，信息素存放于矩陣M中.

步驟 2計(jì)算出每個(gè)節(jié)點(diǎn)分配的信息素量e=E/n.

步驟 3通過一層循環(huán)，依次對(duì)每個(gè)節(jié)點(diǎn)l0,l1,l2,...ln所對(duì)應(yīng)的M中元素進(jìn)行更新.

終距指數(shù)的更新機(jī)制步驟如下：

步驟 1設(shè)獲取某條可通行路徑L，構(gòu)成其的n個(gè)節(jié)點(diǎn)為l0,l1,l2,···,ln，終距指數(shù)存放于矩陣M中.

步驟 2令終點(diǎn)的終距指數(shù)

步驟 3通過一層循環(huán)，倒序依次取出每個(gè)節(jié)點(diǎn)ln?1,ln?2,···l2,l1,l0進(jìn)行后續(xù)步驟4～5 判斷.

分析上述內(nèi)可以得到，對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為n的路徑，兩個(gè)更新機(jī)制僅含有一層與n一階線性相關(guān)的for 循環(huán)，因此，它們的時(shí)間復(fù)雜度都為O(n)，故終距指數(shù)的更新機(jī)制并不會(huì)增加原算法的時(shí)間復(fù)雜度.

3 仿真實(shí)驗(yàn)與分析

3.1 算法參數(shù)選擇為了證實(shí)本文改進(jìn)算法的可行性和有效性，本文采取python3.8 編制程序進(jìn)行仿真.硬件環(huán)境信息：CPU2.5 GHz，i5 處理器.算法各參數(shù)設(shè)定如下：距離啟發(fā)因子β=1.5，終距指數(shù)啟發(fā)因子α=0.9，削減系數(shù)q=0.8，螞蟻數(shù)量m=30，最大迭代次數(shù)為T=100.

3.2 算法驗(yàn)證仿真實(shí)驗(yàn)首先取文獻(xiàn)[12]中的20×20 小規(guī)模柵格數(shù)據(jù)進(jìn)行測(cè)試，仿真結(jié)果如圖8～圖10 所示.

圖8 本文改進(jìn)算法在20×20 環(huán)境模型下的仿真結(jié)果Fig.8 Simulation result by using the improved algorithm under 20×20 environment model

圖9 20×20 環(huán)境模型下的迭代結(jié)束時(shí)各節(jié)點(diǎn)終距指數(shù)Fig.9 The terminal index of each node at the end of iteration under 20 ×20 environment model

圖10 不同算法對(duì)20×20 柵格模型的收斂結(jié)果對(duì)比圖Fig.10 Comparison of convergence results of different algorithms for 20× 20 grid model

圖8 為本文改進(jìn)蟻群算法所得無碰撞最優(yōu)路徑，圖9 為算法迭代收斂后的各節(jié)點(diǎn)終距指數(shù)表，圖10 為算法迭代過程中的每代最優(yōu)路徑的對(duì)比結(jié)果，從仿真的結(jié)果來看，本文改進(jìn)蟻群算法、傳統(tǒng)蟻群算法以及文獻(xiàn)[12]中的改進(jìn)蟻群算法都能找到最優(yōu)解，但從收斂速度的角度來看，本文改進(jìn)蟻群算法在第3 代就可以收斂到問題的最優(yōu)解，而傳統(tǒng)蟻群算法及文獻(xiàn)[12]中的改進(jìn)蟻群算法分別要在第43 代與第34 代才能找到問題的最優(yōu)解.因此，本文的改進(jìn)蟻群算法是有效和可行的.

為了進(jìn)一步驗(yàn)證本文算法的優(yōu)越性，將環(huán)境模型由20×20 擴(kuò)大為更為復(fù)雜的30×30 柵格模型，柵格圖數(shù)據(jù)取文獻(xiàn)[11]中的數(shù)據(jù)作為測(cè)試數(shù)據(jù)，仿真環(huán)境不變，仿真結(jié)果如圖11～圖13 以及表1 所示.

圖11 為本文改進(jìn)蟻群算法的仿真路徑結(jié)果，圖12 為算法達(dá)到收斂后的各節(jié)點(diǎn)的終距指數(shù)表，圖13 為傳統(tǒng)蟻群算法、文獻(xiàn)[11]改進(jìn)蟻群算法以及本文改進(jìn)蟻群算法的迭代圖,表1 為3 種算法仿真結(jié)果在收斂值以及收斂代數(shù)方面的對(duì)比.由以上仿真結(jié)果可得，在采用相同的螞蟻群體和迭代次數(shù)的前提下，本文改進(jìn)蟻群算法與傳統(tǒng)蟻群算法以及文獻(xiàn)[11]算法在2 種不同規(guī)模環(huán)境的路徑規(guī)劃比較中，本文改進(jìn)蟻群算法獲得路徑距離更短，收斂速度更快.

表1 不同算法的實(shí)驗(yàn)結(jié)果Tab.1 Experimental results of different algorithms

圖11 本文算法仿真路徑圖Fig.11 Simulation result by using the improved algorithm under 30×30 environment mode

圖12 30×30 環(huán)境模型下的迭代結(jié)束時(shí)各節(jié)點(diǎn)終距指數(shù)Fig.12 The terminal index of each node at the end of iteration under 30×30 environment model

同時(shí)，觀察圖13 中3 種算法的波動(dòng)曲線，明顯發(fā)現(xiàn)，傳統(tǒng)蟻群算法對(duì)應(yīng)的曲線波動(dòng)較大，這也證實(shí)了傳統(tǒng)蟻群算法在收斂前期受到路徑冗余成分影響較為嚴(yán)重，這也驗(yàn)證了前文所說的在信息素濃度的生成機(jī)制中，由于是以一條完整的路徑作為對(duì)象來生成信息素的，故而無法反映優(yōu)良的局部節(jié)點(diǎn)信息，因此，螞蟻很難通過信息素濃度快速找到最優(yōu)路徑.而文獻(xiàn)[11]也是通過使用自適應(yīng)信息素總量給予機(jī)制削弱螞蟻對(duì)信息素濃度的敏感程度，降低了由劣質(zhì)路徑產(chǎn)生的信息素對(duì)螞蟻決策的影響，從而提高算法的尋解效果，這從圖13 中對(duì)應(yīng)的迭代曲線的波動(dòng)明顯較小可以證明其改進(jìn)策略的有效性.而本文得益于終距指數(shù)更新的篩選策略，使得每代螞蟻生成的路徑信息，僅有更優(yōu)良的節(jié)點(diǎn)信息得以更新并遺留保存，其他劣質(zhì)路徑節(jié)點(diǎn)信息會(huì)被舍棄剔除，這從圖13 中對(duì)應(yīng)的算法收斂曲線的無波動(dòng)可以證明.

圖13 不同算法對(duì)30×30 柵格模型的收斂結(jié)果對(duì)比圖Fig.13 Comparison of convergence results of different algorithms for 30×30 grid mode

3.3 算法穩(wěn)定性驗(yàn)證為了進(jìn)一步驗(yàn)證本文改進(jìn)蟻群算法的穩(wěn)定性，選擇上文30×30 柵格環(huán)境地圖案例進(jìn)行仿真，對(duì)本文改進(jìn)蟻群算法連續(xù)運(yùn)行30 次，得到的具體數(shù)據(jù)如表2 所示.

表2 連續(xù)隨機(jī)運(yùn)行30 次的仿真結(jié)果Tab.2 The simulation results running continuously and randomly for 30 times

如表2 所示，30 次運(yùn)行的收斂代數(shù)較為平穩(wěn)且優(yōu)良，這再次證明本文的改進(jìn)蟻群算法不但有效可行而且穩(wěn)定性好.

4 結(jié)論

傳統(tǒng)蟻群算法的信息素由于其自身的生成機(jī)制，故易受到冗余路徑的干擾，導(dǎo)致信息素濃度與節(jié)點(diǎn)優(yōu)劣性之間的關(guān)聯(lián)較為薄弱，本文對(duì)于節(jié)點(diǎn)的優(yōu)劣性，引入了終距指數(shù)的概念.終距指數(shù)主要受已知的若干個(gè)最優(yōu)局部路線的影響，若已記錄了更優(yōu)的路徑信息，則對(duì)于后續(xù)產(chǎn)生的冗余路徑，終距指數(shù)將會(huì)對(duì)冗余部分完全免疫.終距指數(shù)這種奇特的生成機(jī)制，使得螞蟻依賴終距指數(shù)來進(jìn)行選擇節(jié)點(diǎn)變得更為可靠.算法的仿真結(jié)果表明，螞蟻在通過終距指數(shù)尋路后，無論是尋路結(jié)果，還是尋路速度，都有了明顯地提升.實(shí)驗(yàn)仿真結(jié)果也表明本文基于終距指數(shù)的改進(jìn)蟻群算法在不同復(fù)雜環(huán)境中移動(dòng)機(jī)器人路徑規(guī)劃算法的可行性與優(yōu)越性.