許明樂 游曉明* 劉 升

1(上海工程技術(shù)大學(xué)電子電氣工程學(xué)院 上海 201620)2(上海工程技術(shù)大學(xué)管理學(xué)院 上海 201620)

?

基于統(tǒng)計分析的自適應(yīng)蟻群算法及應(yīng)用

許明樂1游曉明1*劉 升2

1(上海工程技術(shù)大學(xué)電子電氣工程學(xué)院 上海 201620)2(上海工程技術(shù)大學(xué)管理學(xué)院 上海 201620)

路徑規(guī)劃是機器人關(guān)鍵技術(shù)之一。利用改進的蟻群算法進行機器人的路徑規(guī)劃。針對傳統(tǒng)蟻群算法收斂速度慢且易陷入局部最優(yōu)解的缺陷，在Ant Colony System算法基礎(chǔ)上，對每代蟻群動態(tài)隨機統(tǒng)計分析，提取最優(yōu)、平均和最差的螞蟻信息，構(gòu)成自適應(yīng)算子用于局部信息素的自適應(yīng)更新。仿真實驗結(jié)果證明該自適應(yīng)算子在平衡增加收斂速度和陷入局部最優(yōu)解矛盾的問題中是有效的。

路徑規(guī)劃 自適應(yīng)精英策略 統(tǒng)計分析 蟻群算法

0 引 言

移動機器人技術(shù)是機器人技術(shù)的重要組成部分，應(yīng)用前景十分廣闊，可廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、醫(yī)療、以及服務(wù)業(yè)等[1]。文獻[2]提出未來數(shù)年內(nèi)，中國服務(wù)機器人發(fā)展將超過傳統(tǒng)的工業(yè)機器人。機器人路徑規(guī)劃技術(shù)是服務(wù)機器人研究的核心內(nèi)容之一[3]，研究機器人的路徑規(guī)劃問題十分必要。

近年來，各國學(xué)者致力于機器人路徑規(guī)劃的研究且取得了相當(dāng)豐碩的研究成果。目前已有多種算法用于規(guī)劃機器人的路徑，文獻[4]將其分為經(jīng)典方法和進化算法。進化算法等人工智能技術(shù)是近些年來新興的技術(shù)，有著傳統(tǒng)方法不具有的優(yōu)點，它使得移動機器人在理論上擁有了一定的“智能”。

進化算法中的蟻群算法是人工智能技術(shù)的組成部分，最早由意大利學(xué)者Dorigo于20世紀(jì)90年代提出AS(ant system)，首先成功應(yīng)用于解決TSP問題[5]。蟻群算法是一種擁有自組織和正反饋優(yōu)點的并行優(yōu)化算法，經(jīng)過學(xué)者們大量研究，成功運用于許多領(lǐng)域[6]。

然而，和其他算法一樣，蟻群算法也面臨著一些挑戰(zhàn)，一個有效的啟發(fā)式算法必須要實現(xiàn)對還未探索過領(lǐng)域的探索和對當(dāng)前已獲得結(jié)果的開發(fā)之間的平衡，改善路徑上信息素的更新方式是實現(xiàn)這種平衡的方法之一[7]。文獻[5]提出精英螞蟻的概念，在基本的信息素更新的基礎(chǔ)上，額外增加了最優(yōu)路徑上信息素增量，以提高收斂速度。然而精英螞蟻的增加，使得最優(yōu)路徑上信息素快速增加，降低了種群多樣性。文獻[8]根據(jù)每代中不同螞蟻的結(jié)果得到不同的信息素增量，可以避免精英螞蟻的影響。在提高收斂速度的同時，通過減少最優(yōu)螞蟻與次優(yōu)螞蟻路徑上信息素的差距來增加種群多樣性。但是此方法僅使用了部分螞蟻的信息，無法體現(xiàn)群體智能行為。文獻[9]提出局部更新信息素的方法，通過減少已訪問邊上的信息素量來鼓勵后續(xù)螞蟻選擇其他的邊，以提高種群多樣性。然而，局部信息素的更新是一個定值，每一代蟻群之間相同，不能表現(xiàn)蟻群算法作為群智能算法的進化智能。

蟻群算法作為一種正反饋的群智能算法，應(yīng)當(dāng)積極使用群體所表現(xiàn)的智能行為，以提高蟻群算法的性能。本文在局部更新的基礎(chǔ)上，對每一代蟻群進行統(tǒng)計分析，利用整個蟻群的信息以提高種群多樣性，對蟻群中不同螞蟻統(tǒng)計分析進行不同的信息素更新以提高收斂速度。根據(jù)每一代螞蟻的不同結(jié)果還可以自適應(yīng)地調(diào)整蟻群迭代過程，以體現(xiàn)蟻群的群體智能行為。

1 機器人路徑規(guī)劃問題和環(huán)境建模

機器人的路徑規(guī)劃是指按照一定的性能指標(biāo)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無碰路徑[14]。按照機器人對環(huán)境信息已知程度的不同，路徑規(guī)劃問題分為對環(huán)境已知的全局路徑規(guī)劃和對環(huán)境信息完全不知或者部分不知的局部路徑規(guī)劃問題[7]。前者在已知或者直接給出的靜態(tài)環(huán)境中進行相關(guān)的工作，本文進行的就是機器人全局路徑規(guī)劃研究，即障礙地圖已知的機器人路徑規(guī)劃研究。

對于機器人的環(huán)境建模有多種方法，如可視圖法、maklink和人工勢場法等。其中柵格法是一類經(jīng)典的環(huán)境建模方法，本文采用此種方法對環(huán)境進行建模，將環(huán)境劃分為單位大小的正方格，如果方格內(nèi)有障礙物，則標(biāo)記為1，在圖形中表示為黑色；沒有障礙物的方格標(biāo)記為0，在圖形中表示為白色。在計算中用方格的中心表示方格的整體位置。在四周沒有障礙、也不是邊緣方格的前提下，每個方格有8個方向可以移動，即右、右上、右下、左、左上、左下、和正上和正下八個方向可以移動。

2 相關(guān)工作

從自然界中螞蟻尋求蟻穴到食物之間的最短路徑得到啟示，20世紀(jì)90年代Dorigo.M最早提出螞蟻算法AS，主要基于搜索過程中信息素的正反饋機制和啟發(fā)式的貪婪機制，首先成功運用于NP難中的TSP問題。根據(jù)算法優(yōu)點，蟻群優(yōu)化算法成功運用于很多問題[12-14]。與此同時，蟻群算法也開始應(yīng)用于機器人路徑規(guī)劃。

在基本蟻群AS的基礎(chǔ)上，本章介紹了幾類經(jīng)典的改進算法，分別是精英蟻群算法(ASelite)，排序蟻群算法(ASrank)，和蟻群系統(tǒng)(ACS)。

2.1 基于精英策略的蟻群算法(ASelitist)

根據(jù)基本的蟻群優(yōu)化算法，精英策略改進了信息素的更新方式[5, 13]。主要思想是：每一次迭代中全局最優(yōu)螞蟻所經(jīng)過的路徑，獲得額外的信息素更新，相當(dāng)于好幾只螞蟻經(jīng)過了此最優(yōu)路徑并釋放了信息素。這加強了全局最優(yōu)螞蟻對后續(xù)螞蟻的影響，使后面的螞蟻在全局最優(yōu)路徑及其附近的路徑上的選擇概率增加，在當(dāng)前最優(yōu)的路徑上進一步的開發(fā)，提高了算法的收斂速度。

精英策略螞蟻系統(tǒng)中信息素更新規(guī)則按下式計算：

τ(i,j)←(1-ρ)τ(i,j)+△τ(i,j)+△τ(i,j)*

(1)

(2)

式中，σ為精英螞蟻的數(shù)量，L*為全局最優(yōu)路徑的長度。

實驗結(jié)果表明基于精英策略的螞蟻算法提升了螞蟻算法收斂速度[5]。但是，隨著精英螞蟻對應(yīng)路徑上信息素的增加，降低了后續(xù)螞蟻解的多樣性。單純的精英算法犧牲了算法的多樣性來提升收斂速度。其潛在的缺陷和遺傳算法中保留最優(yōu)個體的行為類似，造成算法的早熟，使得某一條路徑上的信息素急劇增加，從而嚴(yán)重影響了后續(xù)螞蟻解的多樣性，使得算法收斂于某一局部最優(yōu)解[17]。

作為群智能進化算法，精英策略雖提高了種群中最優(yōu)個體的作用，但忽視了每一代螞蟻中較優(yōu)個體的智能行為，沒體現(xiàn)種群進化的特點。

2.2 基于排序策略的蟻群算法(ASrank)

考慮到精英策略的缺陷，聯(lián)系到遺傳算法中對個體適應(yīng)度排序并進行選擇的策略，Bullnheimer·B等提出了基于排序的精英螞蟻算法，它只更新一定量較優(yōu)螞蟻路徑上的信息素[8]。此算法改進后的信息素更新策略按照下式進行：

τ(i,j)←ρ·τ(i,j)+△τ(i,j)+τ(i,j)*

(3)

△τ(i,j)μ=

(4)

式(3)中τ(i,j)*是全局最優(yōu)路徑上信息素更新的增量，是保留了精英策略的部分，也按照式(2)進行計算。

排序策略不僅增加了最優(yōu)路徑上的信息素增量，還增加了次優(yōu)路徑上的信息素增量。相對于精英螞蟻算法，排序策略提高了后續(xù)螞蟻解的多樣性，即后續(xù)螞蟻在路徑轉(zhuǎn)移中的指導(dǎo)不僅僅來自于全局最優(yōu)螞蟻，還有歷次迭代中前幾只較優(yōu)的螞蟻。排序策略保留了精英策略讓當(dāng)前最優(yōu)的螞蟻指導(dǎo)后續(xù)螞蟻解的構(gòu)造過程，但更進一步地考慮了每代螞蟻中較優(yōu)個體的智能行為，并且還考慮了優(yōu)化程度不同螞蟻之間的差別，即給予不同的權(quán)重。正如文獻[8]所說排序策略通過選擇多個較優(yōu)個體的方法來減少精英策略或者是全局優(yōu)化策略帶來的潛在缺陷。實驗結(jié)果表明排序策略有一定的效果。

排序策略使用更多的螞蟻信息緩解了精英策略的弊端，可見考慮更多螞蟻的信息有利于解決蟻群算法中收斂速度和解的多樣性之間的矛盾，這體現(xiàn)了排序策略的有效性。然而，排序策略僅僅考慮了每一代螞蟻中較優(yōu)個體的信息，忽視了每一代螞蟻的整體信息。此外，雖然排序策略考慮了較優(yōu)螞蟻之間的不同，但是卻沒有考慮到較優(yōu)螞蟻與其他不執(zhí)行更新操作螞蟻之間的不同，如最后一只較優(yōu)螞蟻和第一只非較優(yōu)螞蟻之間的差異很有可能極小，這種情況下，更新前者而不更新后者是有一定缺陷的?？紤]每一代螞蟻的所有信息將有助于算法性能的進一步提高。

2.3 蟻群系統(tǒng)(ACS)

針對基本蟻群算法的缺陷，ACS是一類經(jīng)典的改進算法[11]。相對于基本蟻群算法，ACS主要對狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新方式做了如下改變：

在狀態(tài)轉(zhuǎn)移過程中，利于偽隨機概率選擇下一城市，即位于城市i的螞蟻在選擇下一城市時按照下式進行：

(5)

通過偽隨機的不確定性，改變了AS中選擇路徑的規(guī)則和信息素和啟發(fā)式之間的確定性關(guān)系，增加了螞蟻在求解過程中解的多樣性，從而增加跳出局部最優(yōu)解的可能性。

ACS算法有全局信息素更新和局部信息素更新兩個部分。局部信息素的更新利用了每一代螞蟻的路徑信息，一定程度上提高了算法多樣性。但是路徑對應(yīng)的信息素增量都相同，每一代增量也相同，沒有考慮不同螞蟻的信息，也無法體現(xiàn)群體進化的特點。

ACS中全局信息素更新規(guī)則根據(jù)下式進行：

τ(i,j)←(1-α)·τ(i,j)+α·△τ(i,j)

(6)

式中：

全局信息素更新的是當(dāng)前所有迭代中出現(xiàn)的全局最優(yōu)解對應(yīng)路徑上的信息素。與此同時，文獻[11]也提出了當(dāng)代最優(yōu)的概念，相對于全局最優(yōu)解，當(dāng)代最優(yōu)路徑上信息素的更新得到的實驗效果稍差于全局最優(yōu)。全局最優(yōu)路徑上信息素的增強，指導(dǎo)了后面螞蟻解的構(gòu)造過程，使得當(dāng)前最優(yōu)解對應(yīng)路徑上的鄰近路徑在此后得到進一步的開發(fā)，增加了收斂速度。在全局最優(yōu)和當(dāng)代最優(yōu)的選擇中，根據(jù)實驗結(jié)果作者選擇了前者，然而作者卻忽視了當(dāng)代最優(yōu)的信息。正如文獻[11]所說，全局最優(yōu)只是比當(dāng)代最優(yōu)的效果稍微好一點，將兩者同時使用有可能進一步的提高算法的性能。

3 基于統(tǒng)計分析的自適應(yīng)精英蟻群算法

蟻群算法是一種隨機搜索方法，與遺傳算法類似，主要用在大量的可能解中尋求最優(yōu)解。蟻群算法解的構(gòu)造主要包括兩部分，其一是通過每個個體單獨構(gòu)造解，其二是群體之間的信息交流。個體螞蟻的行為雖然簡單，但是作為一個群體而體現(xiàn)出相應(yīng)的智能。蟻群算法通過信息素的改變，充分地發(fā)揮了個體螞蟻與群體之間智能行為。

然而實際上，以上改進算法都忽視了整個群體螞蟻的智能行為，要么只是利用了部分螞蟻的信息，或者是沒考慮迭代過程中蟻群的進化。由第2節(jié)分析，如果利用蟻群算法作為進化算法的特征，以及每一代蟻群的信息，則可以提高種群多樣性。

但是，如果直接利用所有螞蟻的所有信息，最優(yōu)個體的信息的作用會被相應(yīng)的降低，進而使得算法的收斂速度下降；還會由于信息交流量增加，算法的復(fù)雜度也會增加。因此本文尋找一種利用群體信息而又不會影響算法其他性能的方法。

統(tǒng)計學(xué)中利用均值等概念來表示一個群體的相關(guān)特征信息。本文借鑒統(tǒng)計分析的方法提取了每一代蟻群的三個特征參數(shù)，即在最優(yōu)值的基礎(chǔ)上，本文還提取了每代螞蟻信息的均值和最差的值來代表這一代的螞蟻信息，進而在蟻群的信息交流(信息素更新)中加以利用。

本文在ACS算法基礎(chǔ)上借鑒精英策略和排序策略，加入本文提出的自適應(yīng)算子。得到的局部信息素更新方式按照下式進行：

τ(i,j)←(1-ρ)·τ(i,j)+ρ·△τ(i,j)

(7)

式中ρ為可調(diào)參數(shù)，而△τ(i,j)按下式計算：

△τ(i,j)=

(8)

式中，σ為精英螞蟻的個數(shù)，為可調(diào)參數(shù)，Lk為每一代中最優(yōu)螞蟻對應(yīng)的最短路徑長度，Lwor為每代中最差螞蟻對應(yīng)的路徑長度，L為每代中除去最優(yōu)螞蟻的其他σ-1個較優(yōu)螞蟻對應(yīng)的路徑長度，Lave為每代螞蟻的平均路徑長度。

本文引用了ACS中全局信息素更新策略，本文全局信息素更新策略按照下式進行：

τ(i,j)←(1-α)·τ(i,j)+α·△τ(i,j)*

(9)

另外，根據(jù)機器人路徑規(guī)劃的實際問題，本文引用文獻[18]啟發(fā)式方法，即當(dāng)前節(jié)點到下一節(jié)點的啟發(fā)式信息是下一節(jié)點到目標(biāo)節(jié)點的歐式距離。啟發(fā)式信息按照下式生成：

eta(j)=distance(j,goal)

(10)

式中，eta(j)表示節(jié)點j的啟發(fā)式信息，distance(j,goal)表示節(jié)點j到節(jié)點goal之間歐式距離，goal是機器人路徑規(guī)劃的目標(biāo)結(jié)點。

4 實驗結(jié)果與仿真

為了驗證本文改進算法的有效性，本節(jié)將本文算法和精英螞蟻算法、排序蟻群算法及蟻群系統(tǒng)分別應(yīng)用于柵格法的機器人路徑規(guī)劃仿真實驗中。仿真實驗在MATLAB中進行：3.3 GHz處理器，內(nèi)存4 GB，32位系統(tǒng)。

4.1 簡單環(huán)境下四種算法的性能比較

本文首先將各種算法運用于不同的簡單障礙環(huán)境下進行路徑規(guī)劃，各種環(huán)境下的參數(shù)設(shè)置見表1所示。起點從障礙圖的左上角開始計數(shù)，從左到右，從上到下依次增加。

表1 不同環(huán)境下算法的參數(shù)設(shè)置情況

圖1和圖2分別給出了都為U型障礙物環(huán)境但障礙物位置不同時四種算法的路徑規(guī)劃情況和迭代曲線圖。從中可以看出，當(dāng)U型障礙物在右邊時，四種算法都能很快地找到最優(yōu)路徑，各種算法并沒有太大區(qū)別。但是一旦U型障礙物在左邊時，此時啟發(fā)式的理想路徑經(jīng)過U型障礙物的內(nèi)部，情況則變得不一樣。ACS收斂速度最快，但是本文算法得到了最優(yōu)解，相應(yīng)的收斂速度也并不慢。除了本文算法，其他算法都未能找到最優(yōu)解。

從圖3和圖4看出，即使在同一障礙物下，即使起點相同，而終點不同時，路徑規(guī)劃的難度也是不一樣的。當(dāng)終點在障礙物交接中間時，ACS算法和本文算法都能夠找到最優(yōu)解，但本文的收斂速度明顯要快于ACS算法，而精英螞蟻和排序螞蟻算法并沒有找到最優(yōu)路徑。當(dāng)終點位于障礙物交界的左邊時，排序算法和精英算法幾乎始終在距離終點最近的點處徘徊，無法找到新的出口，其多樣性明顯比較差。而ACS算法雖然在前幾次都能夠逃離局部最優(yōu)解，然而，在最后一個可能局部最優(yōu)解中沒能成功逃離，其多樣性還有待進一步提高。雖然ACS算法收斂速度最快，但是本文算法并沒有下降很多。本文算法在較困難的路徑規(guī)劃中仍然可以較快地找到最優(yōu)解而不陷入局部最優(yōu)。

圖1 U_1·右邊U型障礙物路徑規(guī)劃和迭代情況

圖2 U_2·左邊U型障礙物路徑規(guī)劃和迭代情況

圖3 Z_1·Z型障礙物簡單情況的路徑規(guī)劃和迭代情況

圖4 Z_2·Z型障礙物復(fù)雜情況的路徑規(guī)劃和迭代情況

從圖5得到，在這種障礙物環(huán)境下，傳統(tǒng)算法都比較難以得到最優(yōu)解，在第一個缺口處總是陷入了局部最優(yōu)?？芍浯颂幍亩鄻有暂^差，因而很難尋找到全局最優(yōu)。相對來講，ACS算法比精英螞蟻算法和排序螞蟻算法有了很大的提高。本文算法找到了全局最優(yōu)解，而對應(yīng)的收斂速度只是稍微下降了一點。

圖6中E型障礙物中間存在著一個缺口，相對于圖5，則大大緩解了啟發(fā)式構(gòu)成的陷入局部最優(yōu)解的威脅，所有算法都能夠找到全局最優(yōu)解,但本文算法是最快收斂的。

圖5 E_2 無缺口的E型障礙物路徑規(guī)劃和迭代情況

4.2 復(fù)雜環(huán)境下四種算法的性能比較

上節(jié)給出了四種算法在簡單環(huán)境下的性能比較分析，體現(xiàn)了本文算法的有效性。本節(jié)將驗證復(fù)雜環(huán)境下算法的有效性。上節(jié)中，環(huán)境只是20乘以20的柵格，本節(jié)環(huán)境為50乘以50的柵格。解空間的增加大大增加了算法尋找最優(yōu)解的難度。表2給出了復(fù)雜環(huán)境下蟻群優(yōu)化算法的參數(shù)。

表2 復(fù)雜環(huán)境下算法的參數(shù)設(shè)置情況

圖7給出了第一種復(fù)雜環(huán)境下的路徑規(guī)劃和迭代情況。由圖可知，本文算法不僅收斂速度快，而且得到了全局最優(yōu)解。而其他算法不僅收斂速度較慢，還沒有得到最優(yōu)解，都陷入了局部最優(yōu)。

圖7 complex_1·第一種復(fù)雜情況下的路徑規(guī)劃和迭代情況

圖8是另一種復(fù)雜性的障礙地圖，且比圖7更容易陷入局部最優(yōu)解。在這種情況下本文算法依舊得到了比較好的結(jié)果：不僅得到了最優(yōu)解，而且收斂速度也是四種算法中最快的。

圖8 complex_2·第二種復(fù)雜情況下的路徑規(guī)劃和迭代情況

雖然本文算法和ACS算法都能夠得到最優(yōu)解，并且收斂速度也只是比ACS算法稍好一點，幾乎可以忽略不計。但是從迭代曲線圖可以看出，本文算法在得到最優(yōu)解之前能夠保持一個比較穩(wěn)定搜索過程，即本文算法可以在一定的平均迭代次數(shù)上，得到一個比較優(yōu)良的解。比較而言，ACS算法不能保持這樣的特性。另一方面，這也說明ACS可能會出現(xiàn)停滯行為而搜索不到最優(yōu)解。此外，也說明本文算法在自適應(yīng)算子下有一個比較穩(wěn)定的搜索過程。

4.3 四種算法的性能分析比較

前兩節(jié)分別在簡單環(huán)境和復(fù)雜環(huán)境下將本文算法和經(jīng)典蟻群優(yōu)化算法進行了性能比較，證明了本文算法的有效性。為了進一步驗證本文算法的穩(wěn)定性，本節(jié)在同一種地圖中(障礙如圖9)，將不同算法運行20次，統(tǒng)計分析每種算法的結(jié)果，各個算法有著相同的參數(shù)，最大的迭代次數(shù)都為250，相關(guān)參數(shù)見表3，統(tǒng)計分析結(jié)果見表4所示。

表3 算法的參數(shù)設(shè)置情況

表4 不同算法的性能分析

表4分別對比了四種算法在20次情況的不同性能，最優(yōu)結(jié)果，最優(yōu)結(jié)果的次數(shù)，最差結(jié)果，以及算法平均的收斂速度，并分析了算法每次得到結(jié)果的方差。圖9中，分別給出了本文算法和其他算法某次路徑規(guī)劃及相應(yīng)的收斂情況。

圖9 不同算法的路徑規(guī)劃和收斂情況

由表4知，精英策略和排序策略得到的最優(yōu)解的次數(shù)比較少。但精英策略比較穩(wěn)定，而其最易陷入局部最優(yōu)解。排序策略比精英策略的多樣性要好一點，這與前面的理論分析相吻合。算法實驗結(jié)果也表明這兩種算法大部分都落入了如圖9中的局部最優(yōu)解。ACS算法得到的結(jié)果相對來說也很好，能夠快速地穩(wěn)定地得到最優(yōu)解。本文算法的方差比ACS還低一點，表明本文算法可以更加穩(wěn)定地得到解。最差結(jié)果也比ACS好，本文算法多樣性更好。而本文收斂速度并沒有下降很多?？芍疚乃惴軌蜉^快地穩(wěn)定地得到最優(yōu)解。

5 結(jié) 語

本文分析了蟻群算法中利用螞蟻信息這一正反饋過程。在傳統(tǒng)蟻群算法僅使用最優(yōu)或者較優(yōu)的螞蟻信息的基礎(chǔ)上，本文提出的基于統(tǒng)計分析的自適應(yīng)精英蟻群算法對每一代螞蟻的整體信息進行了統(tǒng)計分析，進而不僅提取了最優(yōu)螞蟻的信息，還提取了平均螞蟻的信息以及最差螞蟻的信息。并在信息素更新中加以運用，平衡了蟻群算法的收斂速度和跳出局部最優(yōu)解間的關(guān)系。由于是對每一代蟻群的隨機統(tǒng)計使得蟻群算法具有一定的自適應(yīng)性。將算法應(yīng)用于機器人的全局路徑規(guī)劃問題中，仿真實驗結(jié)果證明了不管是在簡單還是復(fù)雜環(huán)境下，本文算法都能夠得到最優(yōu)的解，較快的收斂速度。此外，由于本文算法可以根據(jù)每代蟻群的整體信息自適應(yīng)的調(diào)整信息素的更新過程，使得本文算法維持一定范圍的搜索解空間。而且，在復(fù)雜情況下，本文算法的效果更加明顯。

未來，將考慮多種群蟻群算法中如何利用多個蟻群種群的相關(guān)信息，以平衡算法收斂速度和解的多樣性之間的矛盾，從而解決更大規(guī)模的復(fù)雜問題，并運用在機器人的路徑規(guī)劃中。此外，還要討論如何確定精英螞蟻個數(shù)以期更加有效地解決實際問題。

[1] 徐國保,尹怡欣,周美娟.智能移動機器人技術(shù)現(xiàn)狀及展望[J].機器人技術(shù)與應(yīng)用,2007(2):29-34.

[2] 蔡自興.中國機器人學(xué)40年[J].科技導(dǎo)報,2015,33(21):23-31.

[3] 朱大奇,顏明重.移動機器人路徑規(guī)劃技術(shù)綜述[J].控制與決策,2010,25(7):961-967.

[4] Raja P, Pugazhenthi S. Optimal path planning of mobile robots: A review[J]. International Journal of Physical Sciences, 2012,7(9):1314-1320.

[5] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29-41.

[6] 段海濱,王道波,朱家強,等.蟻群算法理論及應(yīng)用研究的進展[J].控制與決策,2004,19(12):1321-1326.

[7] Dorigo M, Stützle T. Ant Colony Optimization: Overview and Recent Advances[J]. International, 2010, 146(5):227-263.

[8] Bullnheimer B, Hartl R F, Strauss C. A New Rank Based Version of the Ant System - A Computational Study[J]. Central European Journal of Operations Research, 1999, 7(1):25-38.

[9] Dorigo M, Birattari M, Stutzle T. Ant colony optimization[J]. IEEE computational intelligence magazine, 2006, 1(4): 28-39.

[10] 李磊,葉濤,譚民,等.移動機器人技術(shù)研究現(xiàn)狀與未來[J].機器人,2002, 24(5)：475-480.

[11] Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation,1997,1(1): 53-66.

[12] 呂勇.蟻群優(yōu)化算法及在網(wǎng)絡(luò)路由中的應(yīng)用研究[D].杭州:浙江大學(xué)電氣工程學(xué)院，2005.

[13] 楊業(yè)娟,屠莉江.基于蟻群算法的水果圖像分割技術(shù)[J].江蘇農(nóng)業(yè)科學(xué),2014,42(9):380-382.

[14] 張海濤,周愛武.蟻群算法在文本聚類中的應(yīng)用研究[J].微電子學(xué)與計算機,2016,33(1):81-84.

[15] Farahnakian F, Ashraf A, Pahikkala T, et al. Using ant colony system to consolidate vms for green cloud computing[J]. IEEE Transactions on Services Computing, 2015,8(2):187-198.

[16] Lee S G. Multiagent elite search strategy for combinatorial optimization problems[C]// International Conference on Computer and Information Sciences. Springer-Verlag, 2005:432-441.

[17] 何琳,王科俊,李國斌,等.最優(yōu)保留遺傳算法及其收斂性分析[J].控制與決策,2000,15(1):63-66.

[18] 郭玉.基于改進蟻群算法的機器人路徑規(guī)劃研究[D].哈爾濱:哈爾濱工業(yè)大學(xué)學(xué)院控制科學(xué)與工程系，2008.

SELF-ADAPTIVE ANT COLONY ALGORITHM BASED ON STATISTICAL ANALYSIS AND ITS APPLICATION

Xu Mingle1You Xiaoming1*Liu Sheng2

1(CollegeofElectronicandElectricalEngineering,ShanghaiUniversityofEngineeringScience,Shanghai201620,China)2(CollegeofManagement,ShanghaiUniversityofEngineeringScience,Shanghai201620,China)

Path planning is one of the key technologies of robot. In this paper, the improved ant colony algorithm is applied to robot path planning. Aiming at the shortcoming of traditional ant colony algorithm which is slow to converge and easy to fall into local optimum, the dynamic random statistical analysis of each ant colony is performed based on the Ant Colony System algorithm. The optimal, average and worst ant information are extracted to form an adaptive operator for the local pheromone adaptive updating. Simulation results show that the proposed adaptive operator is effective in solving the problem of increasing the convergence speed and falling into the local optimal solution.

Path planning Adaptive elitist strategy Statistical analysis Ant colony optimization

2016-06-26。國家自然科學(xué)基金項目(61075115，61403249);上海市教委科研創(chuàng)新重點項目(12ZZ185)。許明樂，碩士生，主研領(lǐng)域：機器人應(yīng)用和群智能算法。游曉明，教授。劉升，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.07.038