動(dòng)態(tài)混沌蟻群系統(tǒng)及其在機(jī)器人路徑規(guī)劃中的應(yīng)用

李 娟，游曉明，劉 升，陳 佳

(1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201600； 2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201600)(*通信作者電子郵箱yxm6301@163.com)

0 引言

移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題是機(jī)器人的研究熱點(diǎn)之一。目前機(jī)器人路徑規(guī)劃主要解決3個(gè)問(wèn)題：1)使機(jī)器人從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)；2)能繞過(guò)障礙物；3)在解決以上問(wèn)題的前提下，機(jī)器人的運(yùn)動(dòng)軌跡要盡量?jī)?yōu)化[1]。從路徑規(guī)劃的環(huán)境感知角度的劃分有：基于環(huán)境模型的規(guī)劃方法、基于事例學(xué)習(xí)的規(guī)劃方法和基于行為的規(guī)劃方法；從目標(biāo)范圍劃分有：全局路徑規(guī)劃和局部路徑規(guī)劃；從隨著時(shí)間的變化規(guī)劃環(huán)境是否變化的劃分有：靜態(tài)和動(dòng)態(tài)路徑規(guī)劃。路徑規(guī)劃問(wèn)題通常采用的算法包括：柵格法、可視圖法、遺傳算法(Genetic Algorithm, GA)等[2]。

群智能優(yōu)化算法是人們通過(guò)觀察自然環(huán)境中的群體，將其復(fù)雜的行為分解成一個(gè)個(gè)數(shù)學(xué)模型，其易于實(shí)現(xiàn)、魯棒性強(qiáng)等特點(diǎn)，使得群智能優(yōu)化算法成為一種熱門的進(jìn)化算法。這種算法包括蟻群優(yōu)化(Ant Colony Optimization, ACO)算法、遺傳算法、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法等，其中蟻群算法是1991年由Dorigo等[3]提出的一種新型模擬進(jìn)化算法，蟻群算法是受到真實(shí)螞蟻行為特別是其覓食行為的啟發(fā)，利用正反饋、自組織和分布式協(xié)作來(lái)尋找最優(yōu)路徑，它有強(qiáng)魯棒性、并行分布式計(jì)算、全局搜索能力強(qiáng)、易與其他問(wèn)題結(jié)合等優(yōu)點(diǎn)，使得其成功運(yùn)用到機(jī)器人路徑規(guī)劃、旅行商問(wèn)題(Traveling Salesman Problem， TSP)、圖像識(shí)別等領(lǐng)域[4]。

蟻群算法的主要特點(diǎn)是正反饋和分布式計(jì)算，但是對(duì)于大規(guī)模機(jī)器人路徑規(guī)劃的問(wèn)題，解的質(zhì)量不高。針對(duì)蟻群算法收斂速度慢的不足，文獻(xiàn)[5]提出了最優(yōu)最差螞蟻系統(tǒng)(Best-Worst Ant System, BWAS)，BWAS的基本思想是增強(qiáng)迭代過(guò)程中較優(yōu)路徑的信息素并減弱較差路徑的信息素，使得螞蟻向較優(yōu)路徑靠近，以提高算法的收斂速度；但文獻(xiàn)[6]指出這種做法可能會(huì)使算法陷入局部最優(yōu)從而無(wú)法找到全局最優(yōu)解。Ghumman等[7]提出了最大最小螞蟻系統(tǒng)(Max Min Ant System, MMAS)，該算法通過(guò)限定信息素值的范圍來(lái)避免某條路徑上的信息素濃度過(guò)大或者過(guò)小，并以此來(lái)增加種群多樣性，擴(kuò)大解的范圍，避免了算法早熟、陷入局部最優(yōu)解的現(xiàn)象；但是，MMAS的收斂速度比較慢，搜索時(shí)間也比較長(zhǎng)。Boussaid等[8]提出了蟻群系統(tǒng)(Ant Colony System, ACS)，ACS的種群多樣性好，不過(guò)其搜索效率較低，收斂速度比較慢。

近年來(lái)，非線性動(dòng)力學(xué)的研究發(fā)展迅速，科學(xué)家將其應(yīng)用到群智能算法中，特別是混沌在優(yōu)化算法方面取得的進(jìn)展，引起了學(xué)者們的關(guān)注。Gandomi等[9]提出了將混沌算子引入蝙蝠算法(Bat Algorithm, BA)中，混沌蝙蝠算法可以提高全局最優(yōu)的可靠性和結(jié)果的質(zhì)量。Javidi等[10]提出混沌遺傳算法(Chaos Genetic Algorithm, CGA)，使用Tent混沌映射和Logistic混沌映射來(lái)生成混沌值，可以避免算法局部收斂，實(shí)驗(yàn)結(jié)果表明CGA減少了優(yōu)化過(guò)程中的迭代次數(shù)，并顯著提高了GA的性能。Wang[11]在2009年提出了將混沌蟻群算法應(yīng)用到基于QoS(Quality of Service)的網(wǎng)絡(luò)服務(wù)組合中，用混沌變量來(lái)克服蟻群算法效率低、易陷入局部最優(yōu)的不足，且蟻群算法的正反饋性也降低了混沌搜索的盲目性，兩者相互改進(jìn)，實(shí)驗(yàn)表明混沌蟻群算法是高效的。

為了提高ACS算法的收斂速度、增加種群多樣性，本文對(duì)ACS算法引入動(dòng)態(tài)混沌算子，以增加種群多樣性、避免陷入局部最優(yōu)、提高解的質(zhì)量，在迭代后期則將混沌算子去除以提高其收斂速度，來(lái)平衡ACS算法的收斂速度和種群多樣性的關(guān)系。本文將其應(yīng)用到基于環(huán)境模型的靜態(tài)全局路徑規(guī)劃中，實(shí)驗(yàn)結(jié)果表明所提算法是可行且有效的。

1 相關(guān)工作

1.1 蟻群系統(tǒng)

受自然界中螞蟻群體的覓食行為的啟發(fā)，Dorigo等[3]提出了ACO。螞蟻個(gè)體之間是通過(guò)信息素(pheromone)來(lái)傳遞信息的，螞蟻通過(guò)路徑后會(huì)在路徑上留下信息素，同時(shí)可以感知其他螞蟻留下的信息素。在覓食過(guò)程中，某條路徑通過(guò)的螞蟻越多，信息素濃度越高，其他螞蟻就越傾向于選擇該條路徑，這種行為就是一種信息正反饋現(xiàn)象。在相同的時(shí)間之內(nèi)，路徑越短，則走過(guò)的螞蟻數(shù)目越多，信息素濃度也就越強(qiáng)。螞蟻之間就是通過(guò)這種信息交流的方式來(lái)找到巢穴與食物源之間的最短路徑，并由此提出了蟻群算法。

針對(duì)基本蟻群算法的缺陷，科學(xué)家提出了各種改進(jìn)算法，Dorigo等[3]提出了精英蟻群系統(tǒng)(Elitist Ant colony System, EAS)，EAS的提出是基于遺傳算法的，其將迭代過(guò)程中擁有較優(yōu)路徑的螞蟻保留到下一代，以提高算法的收斂速度；但是，當(dāng)精英螞蟻的數(shù)量選擇不當(dāng)時(shí)，算法將很快聚集在局部路徑導(dǎo)致算法早熟，陷入局部最優(yōu)解[12-13]。Bullnheimer等[14]提出了基于排序的螞蟻系統(tǒng)(rank-based Ant System, ASrank),ASrank中每只螞蟻根據(jù)其所經(jīng)路徑長(zhǎng)度進(jìn)行排序，其釋放的信息素值根據(jù)它們各自的等級(jí)高低來(lái)決定。ACS是一種經(jīng)典的改進(jìn)算法[8]。在狀態(tài)轉(zhuǎn)移過(guò)程中，螞蟻利用偽隨機(jī)概率選擇下一個(gè)節(jié)點(diǎn):

(1)

(2)

其中s是螞蟻k在當(dāng)前迭代中未游歷的所有候選解。

螞蟻從節(jié)點(diǎn)i到j(luò)之后，進(jìn)行局部信息素更新，如式(3)所示：

τij=(1-λ)τij+λτ0

(3)

其中：λ為局部信息素殘留因子；τ0表示路徑信息素初始值，文獻(xiàn)[3]中說(shuō)明了該值的3種可能取值，實(shí)驗(yàn)結(jié)果表明，τ0直接為給定值時(shí)實(shí)驗(yàn)結(jié)果最好，故本文將τ0設(shè)為定值。信息素更新是為了給更短的路徑分配更多的信息素，反映了ACS的正反饋性。

在一次迭代之后，僅對(duì)當(dāng)前循環(huán)最短的路徑應(yīng)用全局信息素更新規(guī)則即式(4)，這在一定程度上可以提高算法的收斂速度。

τij=(1-ρ)τij+ρΔτij

(4)

(5)

其中：ρ為全局信息素殘留因子；Lgb表示在一次循環(huán)中最優(yōu)螞蟻k走過(guò)的總長(zhǎng)度即當(dāng)代最短路徑。信息素更新公式(3)～(4)包含了螞蟻?zhàn)哌^(guò)路徑后信息素的增量和信息素?fù)]發(fā)，是為了模擬信息素強(qiáng)度的變化。

1.2 移動(dòng)機(jī)器人的路徑規(guī)劃

路徑規(guī)劃一般分為三個(gè)環(huán)節(jié)：環(huán)境建模、路徑搜索和路徑平滑(本文不考慮路徑平滑這一環(huán)節(jié)，在搜索范圍內(nèi)，默認(rèn)路徑可行)。環(huán)境建模的方法有：可視圖法、自由空間法、Maklink圖法、柵格法、Voronoi圖法等。由于柵格法具有精度高、易于實(shí)現(xiàn)等優(yōu)點(diǎn)，本文將采用最經(jīng)典的柵格法。

柵格法的原理是：假設(shè)機(jī)器人的工作空間是在二維平面上的有限區(qū)域，而且工作空間中分布的障礙物是靜態(tài)的、有限個(gè)且位置及大小都是已知的。將工作區(qū)域劃分為單位大小的柵格，若柵格內(nèi)無(wú)障礙物則稱為自由柵格，用白色表示，記為0；否則稱為障礙柵格，用黑色表示，記為1。當(dāng)機(jī)器人四周無(wú)障礙且不處于邊緣柵格時(shí)，有8個(gè)方向可以移動(dòng)到相鄰柵格，分別是右、右上、右下、左、左上、左下、正上、正下。可以根據(jù)機(jī)器人的起始點(diǎn)、目標(biāo)點(diǎn)和障礙物，建立一個(gè)柵格坐標(biāo)系。

1.3 混沌優(yōu)化算法

混沌不同于隨機(jī)、混亂，它對(duì)初始條件非常敏感。混沌理論通常被說(shuō)明為由Lorenz[15]描述的所謂的“蝴蝶效應(yīng)”，是一種發(fā)生在確定性非線性系統(tǒng)中的有界動(dòng)態(tài)行為。混沌序列有三個(gè)主要的屬性：遍歷性、隨機(jī)性、初值敏感性，混沌優(yōu)化就是利用混沌序列進(jìn)行的優(yōu)化搜索?；煦绲谋闅v性質(zhì)可以確保混沌變量在一定范圍內(nèi)不重復(fù)地遍歷所有狀態(tài)，這可以作為一種優(yōu)化機(jī)制，避免算法落入局部最優(yōu)解[16]，因此，這樣的群體不僅能得到最短路徑，而且能保證種群多樣性。目前，有10余種常用的混沌映射，本文在表1中給出了5種經(jīng)典的混沌映射表達(dá)式，并在圖1中給出了不同混沌映射的混沌圖形[11，17]。

表1 混沌映射表達(dá)式

圖1 混沌映射的曲線

由圖1可知，這幾種混沌映射的混沌性都很好，但是Logistic混沌映射簡(jiǎn)單易實(shí)行，則本文選用典型的Logistic混沌映射,迭代公式如下：

zi+1=μzi(1-zi);

i=0,1,2,…,z0∈[0,1],μ∈(2,4]

(6)

通過(guò)式(6)，可以得到一系列相應(yīng)的值z(mì)1,z2,…。

當(dāng)Logistic混沌映射參數(shù)μ值滿足參數(shù)范圍時(shí)，改變初始值，可以得到混沌狀態(tài)，故本文選用經(jīng)典的μ=4。

通過(guò)討論μ與z0的值，可以得出結(jié)論：1)μ=4時(shí)，改變初值z(mì)0的值(z0≠0,0.25,0.5,0.75,1)，系統(tǒng)一直為混沌狀態(tài)，如圖2；2)z0=0,0.25,0.75,1，μ=4時(shí)，系統(tǒng)的動(dòng)態(tài)形態(tài)都是只有一個(gè)周期點(diǎn)，如圖3。

實(shí)驗(yàn)結(jié)果表明，當(dāng)μ=4，z0≠0,0.25,0.5,0.75,1時(shí)，系統(tǒng)為完全混沌狀態(tài)：

當(dāng)μ=4，z0=0,1時(shí)，zi=0恒成立；

當(dāng)μ=4，z0=0.25時(shí)，zi=0.75(i≥1)恒成立；

當(dāng)μ=4，z0=0.5時(shí)，z1=1,zi=0(i=2,3,…)恒成立；

當(dāng)μ=4，z0=0.75時(shí)，zi=0.75(i≥0)恒成立；

因此本文的參數(shù)將設(shè)置為μ=4，z0=0.1。下面是使用Matlab仿真Logistic映射，繪制改變?chǔ)痰闹禃r(shí)對(duì)應(yīng)z的值，讓初始系統(tǒng)的值z(mì)0=0.1，迭代次數(shù)為200次。μ是控制參數(shù)，當(dāng)μ=4，Logistic映射處于完全混沌狀態(tài)。

圖2 不同初始值時(shí)的Logistic混沌圖

圖3 異常初始值參數(shù)的Logistic混沌圖

2 改進(jìn)的混沌蟻群系統(tǒng)

針對(duì)ACS的不足，本文提出了在蟻群系統(tǒng)中引入動(dòng)態(tài)混沌算子，用動(dòng)態(tài)混沌算子來(lái)改變信息素的更新方式，以提高算法收斂速度、避免落入局部最優(yōu)、增加種群多樣性。

2.1 動(dòng)態(tài)混沌算子

基于ACS的種群多樣性差、收斂速度慢、易陷入局部最優(yōu)解的不足，本文的改進(jìn)措施是引入動(dòng)態(tài)混沌算子，在迭代前期加入混沌算子，以調(diào)整路徑中的信息素值，來(lái)增加算法的種群多樣性，在迭代后期去除混沌擾動(dòng)來(lái)提高算法的收斂速度。全局信息素更新式(4)修改為式(7)：

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)+R

(7)

(8)

其中：zij為混沌變量，是由Logistics混沌映射式(6)迭代得到的；p為系數(shù)以調(diào)整混沌算子的值使其適應(yīng)ACS算法全局信息素的值；NC為算法的當(dāng)前迭代次數(shù)，NC0為迭代閾值，本文通過(guò)實(shí)驗(yàn)證明當(dāng)NC0為20時(shí)，動(dòng)態(tài)混沌蟻群系統(tǒng)所得結(jié)果將更優(yōu)、更穩(wěn)定，如表2。

當(dāng)ACS初始化時(shí)，每條路徑上的信息素都是相同的，使得螞蟻難以從選擇概率相同的路徑中快速找到更好的路徑，從而導(dǎo)致算法易陷入局部最優(yōu)且收斂速度較慢，動(dòng)態(tài)混沌蟻群系統(tǒng)加入混沌算子可以很好地解決這一問(wèn)題。動(dòng)態(tài)混沌蟻群系統(tǒng)在迭代初期利用混沌算子增加全局路徑信息素值，以增加種群多樣性，使算法避免陷入最優(yōu)解，并得到較好的最優(yōu)解；在迭代后期將去除混沌算子，使算法的全局信息素增長(zhǎng)減緩，以提高算法的收斂速度。

利用混沌算子的遍歷性可以增加原始ACS的種群多樣性，利用ACS的正反饋性也可以降低混沌變量的隨機(jī)性、盲目性，兩者相互改進(jìn)，故使用混沌序列是必要的。通過(guò)本文的實(shí)驗(yàn)結(jié)果，表明引入動(dòng)態(tài)混沌算子后，動(dòng)態(tài)混沌蟻群系統(tǒng)所得全局最優(yōu)解更優(yōu)，與傳統(tǒng)蟻群系統(tǒng)相比能夠更好地平衡收斂速度和種群多樣性之間的關(guān)系。

2.2 改進(jìn)的混沌蟻群系統(tǒng)

本文改進(jìn)算法的流程如圖4所示。

圖4 動(dòng)態(tài)混沌蟻群系統(tǒng)流程

本文提出的改進(jìn)算法的偽代碼如下：

Begin

初始化參數(shù)(螞蟻數(shù)目M、禁忌表Tabu、路徑信息素值τ0、最大迭代次數(shù)NCmax、當(dāng)前最優(yōu)解Lbest等)

While 迭代次數(shù)NC<最大迭代次數(shù)NCmax

do 將M只螞蟻隨機(jī)放到起始點(diǎn)i上，并將該起始點(diǎn)i放入禁忌表Tabu中

While 有螞蟻未完成一次循環(huán)

do 根據(jù)偽隨機(jī)概率公式(式(1))選擇下一個(gè)節(jié)點(diǎn)j，再將節(jié)點(diǎn)j放入禁忌表Tabu中

對(duì)路徑進(jìn)行局部信息素τij更新(式(3))

end

記錄第k只螞蟻的路徑長(zhǎng)度Lk

if 當(dāng)前最優(yōu)解Lbest>Lk

thenLbest←Lk

引入動(dòng)態(tài)混沌算子對(duì)當(dāng)前最短路徑進(jìn)行全局信息素τ更新(式(7))

NC←NC+1

end

Output:當(dāng)前蟻群中的最短路徑，即為最優(yōu)路徑

End

3 仿真實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證動(dòng)態(tài)混沌蟻群系統(tǒng)的可行性與有效性，本文在Matlab環(huán)境下將對(duì)以下5種地圖進(jìn)行仿真，并與傳統(tǒng)蟻群系統(tǒng)(ACS)、基于精英策略的螞蟻算法(EAS)、基于排序的螞蟻算法(ASrank)進(jìn)行比較。

本文引入動(dòng)態(tài)混沌算子以平衡算法的種群多樣性與收斂速度之間的關(guān)系，在迭代前期引入混沌算子來(lái)增加算法的種群多樣性，在迭代后期去除混沌算子來(lái)提升算法的收斂速度。本文通過(guò)實(shí)驗(yàn)表明，動(dòng)態(tài)混沌算子的迭代閾值NC0為20時(shí)，算法結(jié)果更優(yōu)，如表2所示。

表2 動(dòng)態(tài)混沌蟻群系統(tǒng)中不同參數(shù)NC0所得的解

表2為動(dòng)態(tài)混沌蟻群系統(tǒng)在同一路徑規(guī)劃環(huán)境下運(yùn)行10次，改變動(dòng)態(tài)混沌算子的參數(shù)NC0的值，其他參數(shù)不變的實(shí)驗(yàn)數(shù)據(jù)。由表2可知，當(dāng)動(dòng)態(tài)混沌算子的參數(shù)NC0為10，15，20，25時(shí)，運(yùn)行10次動(dòng)態(tài)混沌蟻群系統(tǒng)所得解的最小值都為29.213 2，即參數(shù)NC0為10，15，20，25時(shí)，動(dòng)態(tài)混沌蟻群系統(tǒng)都有可能得到最優(yōu)解，但是當(dāng)NC0為20次時(shí)，動(dòng)態(tài)混沌蟻群系統(tǒng)的均值、標(biāo)準(zhǔn)差都為最小，故此時(shí)動(dòng)態(tài)混沌蟻群系統(tǒng)所得解的質(zhì)量更穩(wěn)定。由此，動(dòng)態(tài)混沌蟻群系統(tǒng)的動(dòng)態(tài)混沌算子的參數(shù)NC0設(shè)為20次。

本文實(shí)驗(yàn)中所用參數(shù)設(shè)置如表3所示。

表3 各算法實(shí)驗(yàn)參數(shù)設(shè)置

對(duì)于20×20的障礙圖(如圖5所示)，由全局最優(yōu)路徑比較可以看出，動(dòng)態(tài)混沌蟻群系統(tǒng)的路徑結(jié)果(實(shí)線)優(yōu)于ACS算法的路徑結(jié)果(虛線)，迭代情況比較圖中動(dòng)態(tài)混沌蟻群系統(tǒng)的最短路徑明顯優(yōu)于ACS、EAS、ASrank。對(duì)于復(fù)雜情形下50×50的障礙圖(如圖6)，動(dòng)態(tài)混沌蟻群系統(tǒng)的結(jié)果同樣優(yōu)于ACS、EAS、ASrank，且收斂代數(shù)也較少。

圖5 20×20環(huán)境中不同情形下的迭代情況對(duì)比

Tab. 4 Performance comparison of four algorithms under different environments

圖5(a)為動(dòng)態(tài)混沌蟻群系統(tǒng)與ACS算法全局最優(yōu)路徑的對(duì)比，由該圖可以看出，對(duì)于簡(jiǎn)單環(huán)境下的路徑規(guī)劃問(wèn)題，動(dòng)態(tài)混沌蟻群系統(tǒng)與ACS算法都可以找到最優(yōu)路徑，但是由圖5(b)的迭代情況對(duì)比可以看出,動(dòng)態(tài)混沌蟻群系統(tǒng)的最優(yōu)路徑(33.313 7)比ACS算法(34.485 3)更短，且得到最優(yōu)路徑所需迭代次數(shù)也更少(如表4)。動(dòng)態(tài)混沌蟻群系統(tǒng)與EAS、ASrank相比，雖然動(dòng)態(tài)混沌蟻群系統(tǒng)的尋優(yōu)迭代次數(shù)比EAS多一些，但是最優(yōu)路徑是更好的，詳細(xì)數(shù)據(jù)如表4。動(dòng)態(tài)混沌蟻群系統(tǒng)引入動(dòng)態(tài)混沌算子，來(lái)平衡種群多樣性與收斂速度的關(guān)系，在迭代前期引入混沌算子，使得算法的種群多樣性增加，所以與ACS、EAS、ASrank相比可以得到較優(yōu)的最優(yōu)路徑，在迭代后期則去除混沌算子，來(lái)提高收斂速度，因此動(dòng)態(tài)混沌蟻群系統(tǒng)在得到較優(yōu)的最短路徑的同時(shí)，收斂速度也較快。

從圖5(c)可以看出，對(duì)于特殊環(huán)境下的較小規(guī)模路徑規(guī)劃問(wèn)題，動(dòng)態(tài)混沌蟻群系統(tǒng)與ACS算法相比，動(dòng)態(tài)混沌蟻群系統(tǒng)的最優(yōu)路徑更優(yōu)。由于動(dòng)態(tài)混沌蟻群系統(tǒng)能夠平衡種群多樣性與收斂速度的關(guān)系，動(dòng)態(tài)混沌蟻群系統(tǒng)與ACS、EAS、ASrank相比(如圖5(d))，最優(yōu)路徑質(zhì)量相差不多，其中動(dòng)態(tài)混沌蟻群系統(tǒng)路徑是最短的，值為38.870，ACS、EAS和ASrank分別為40.870，42.870和42.041 6，但是動(dòng)態(tài)混沌蟻群系統(tǒng)收斂速度更快。

圖5(e)～(f)中的路徑規(guī)劃問(wèn)題是較小規(guī)模下的一種特殊環(huán)境，從圖5(e)可以看出，動(dòng)態(tài)混沌蟻群系統(tǒng)能夠較優(yōu)地避開(kāi)陷阱，從而得到較好的最優(yōu)解；從圖5(f)的迭代情況比較可以看到，動(dòng)態(tài)混沌蟻群系統(tǒng)較其他3種算法的結(jié)果也更好，動(dòng)態(tài)混沌蟻群系統(tǒng)的路徑為34.485 3，比ACS、EAS和ASrank的路徑都短，且收斂速度最快(如表4)，故動(dòng)態(tài)混沌蟻群系統(tǒng)能夠在找到最優(yōu)解的同時(shí)，提高收斂速度。

圖5(g)～(h)中的特殊環(huán)境下的路徑規(guī)劃問(wèn)題易導(dǎo)致結(jié)果陷入局部最優(yōu)，如圖5(g)中的ACS算法，但是由于動(dòng)態(tài)混沌蟻群系統(tǒng)前期的種群多樣性較好，因此動(dòng)態(tài)混沌蟻群系統(tǒng)能夠很好的找到最優(yōu)解；圖5(h)中可以看出，動(dòng)態(tài)混沌蟻群系統(tǒng)的最優(yōu)解較好，收斂速度也較優(yōu)，能夠較好地平衡種群多樣性與收斂速度的關(guān)系。

圖6是較大規(guī)模的路徑規(guī)劃問(wèn)題，由于動(dòng)態(tài)混沌蟻群系統(tǒng)在迭代前期引入混沌算子，使得種群多樣性增加，解的質(zhì)量也更好，而且動(dòng)態(tài)混沌蟻群系統(tǒng)在迭代后期去除混沌算子，以提高收斂速度，因此，對(duì)于大規(guī)模的路徑規(guī)劃問(wèn)題，動(dòng)態(tài)混沌蟻群系統(tǒng)解的質(zhì)量與收斂速度都優(yōu)于ACS、EAS和ASrank，動(dòng)態(tài)混沌蟻群系統(tǒng)同樣能夠較好地平衡種群多樣性與收斂速度的關(guān)系。

表4為本文算法(動(dòng)態(tài)混沌蟻群系統(tǒng))、ACS、EAS和ASrank四種算法的最優(yōu)路徑長(zhǎng)度和達(dá)到最優(yōu)路徑時(shí)迭代次數(shù)的具體實(shí)驗(yàn)數(shù)據(jù)，由表4可以看出動(dòng)態(tài)混沌蟻群系統(tǒng)解的質(zhì)量更高，且收斂速度也較快。表4中：Lb為最優(yōu)路徑長(zhǎng)度；NCb為達(dá)到最優(yōu)路徑時(shí)的迭代次數(shù)，T為達(dá)到收斂時(shí)所用時(shí)間(單位：s)。

由表4可以看出，對(duì)于圖5(c)～(h)，動(dòng)態(tài)混沌蟻群系統(tǒng)達(dá)到收斂時(shí)的路徑長(zhǎng)度、迭代次數(shù)和運(yùn)行時(shí)間與ACS、EAS和ASrank相比，都是最優(yōu)的。對(duì)于圖5(a)、(b)，本文改進(jìn)算法比ACS和ASrank的收斂速度、最優(yōu)路徑長(zhǎng)度都優(yōu)秀，因此本文算法與ACS和ASrank相比，解的質(zhì)量最優(yōu)；圖5(a)、(b)中本文改進(jìn)算法與EAS的收斂時(shí)間分別為4.92 s和4.34 s，但是本文改進(jìn)算法與EAS的最優(yōu)路徑長(zhǎng)度分別為33.313和36.142，本文改進(jìn)算法最優(yōu)路徑長(zhǎng)度比EAS大幅度減少，因此本文改進(jìn)算法能夠很好地平衡最優(yōu)路徑長(zhǎng)度與收斂速度的關(guān)系，解的質(zhì)量更優(yōu)。圖5(g)、(h)的情況與圖5(a)、(b)相似，因此，動(dòng)態(tài)混沌蟻群系統(tǒng)對(duì)ACS引入動(dòng)態(tài)混沌算子，可以平衡算法的收斂速度和最優(yōu)路徑長(zhǎng)度之間的關(guān)系，提高解的質(zhì)量。

圖6 50×50環(huán)境迭代情況對(duì)比

4 結(jié)語(yǔ)

傳統(tǒng)蟻群系統(tǒng)存在種群多樣性不佳、解的質(zhì)量不高等不足，僅僅依賴傳統(tǒng)的信息素更新方式將難以找到最優(yōu)解，且容易陷入局部最優(yōu)，因此本文提出了在迭代前期對(duì)ACS的全局信息素更新方式引入Logistic混沌算子，避免了算法陷入局部最優(yōu)解，且收斂速度也較快，在迭代后期則去除Logistic混沌算子，以提高收斂速度，避免因?yàn)榉N群多樣性的增加而引起收斂速度的降低。仿真結(jié)果表明，動(dòng)態(tài)混沌蟻群系統(tǒng)與傳統(tǒng)算法相比，對(duì)于簡(jiǎn)單環(huán)境下的路徑規(guī)劃問(wèn)題(20×20環(huán)境)，動(dòng)態(tài)混沌蟻群系統(tǒng)解的質(zhì)量更高、種群多樣性更好，并且對(duì)于復(fù)雜環(huán)境下的路徑規(guī)劃問(wèn)題(50×50環(huán)境)，動(dòng)態(tài)混沌蟻群系統(tǒng)可以避免陷入局部最優(yōu)且解的質(zhì)量更好。動(dòng)態(tài)混沌蟻群系統(tǒng)雖然能夠很好地找到最優(yōu)解，但是其收斂速度還不能保證每種類型的路徑規(guī)劃問(wèn)題都能達(dá)到最優(yōu)。下一步將進(jìn)一步研究混沌算子模型，用于改進(jìn)蟻群算法，從而進(jìn)一步提高解的質(zhì)量。

References)

[1] 朱大奇,顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策,2010,25(7):961-967.(ZHU D Q, YAN M Z. Summary of mobile robot path planning technology [J]. Control and Decision, 2010, 25(7): 961-967.)

[2] 許亞.基于改進(jìn)的人工勢(shì)能場(chǎng)的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].科技展望,2016,26(33):77-78.(XU Y. Research on mobile robot path planning based on improved artificial potential field [J]. Science and Technology, 2016, 26(33): 77-78.)

[3] DORIGO M, MANIEZZO V, COLORNI A. The ant system: optimization by a colony of cooperating Agents [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part B, 1996, 26(1): 1-13.

[4] 夏小云,周育人.蟻群優(yōu)化算法的理論研究進(jìn)展[J].智能系統(tǒng)學(xué)報(bào),2016,11(1):27-36.(XIA X Y, ZHOU Y R. Theoretical research progress of ant colony optimization algorithm [J]. Journal of Intelligent Systems, 2016, 11(1): 27-36.)

[5] 李士勇.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004:112-126.(LI S Y. Ant Colony Algorithm and Its Application [M]. Harbin: Harbin Institute of Technology Press, 2004: 112-126.)

[6] THEPPHAKORN T, PONGCHAROEN P, HICKS C. An ant colony based timetabling tool [J]. International Journal of Production Economics, 2014, 149(3): 131-144.

[7] GHUMMAN N S, KAUR R. Dynamic combination of improved max-min and ant colony algorithm for load balancing in cloud system [C]// Proceedings of the 6th International Conference on Computing, Communication and Networking Technologies. Piscataway, NJ: IEEE, 2015: 1-5.

[8] BOUSSAID I, LEPAGNOT J, SIARRY P. A survey on optimization metaheuristics [J]. Information Science,2013, 237(19): 82-117.

[9] GANDOMI A H, YANG X-S. Chaotic bat algorithm [J]. Journal of Computational Science, 2014, 5(2): 224-232.

[10] JAVIDI M, HOSSEINPOURFARD R. Chaos genetic algorithm instead genetic algorithm [J]. The International Arab Journal of Information Technology, 2015, 12(2): 163-168.

[11] WANG Y. Application of chaos ant colony algorithm in Web service composition based on QoS [J]. International Forum on Information Technology and Applications, 2009, 172(2):25-227.

[12] TAO W Q, YANG G, ZHANG J Y. Fault section locating for distribution network with DG based on improved ant colony algorithm [C]// Proceedings of the 2016 Power Electronics and Motion Control Conference. Piscataway, NJ: IEEE, 2016: 1985-1989.

[13] PRAKASAM A, SAVARIMUTHU N. Metaheuristic algorithms and probabilistic behaviour: a comprehensive analysis of ant colony optimization and its variants [J]. Artificial Intelligence Review, 2016, 45(1): 97-130.

[14] BULLNHEIMER B, HARTL R F, STRAUB C. A new rank based version of ant system — a computational study [J]. Central European Journal of Operations Research, 1999, 7(1): 25-38.

[15] LORENZ N. Deterministic non periodic flow [J]. AMS Journal, 1963, 20(2): 130-141.

[16] WANG Y, YAO M.A new hybrid genetic algorithm based on chaos and PSO [C]// Proceedings of the 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems. Piscataway, NJ: IEEE, 2009: 699-703.

[17] SHAHRZAD S, SEYEDALI M, ANDREW L. Biogeography-based optimisation with chaos [J]. Neural Computing and Applications, 2014, 25(5): 1077-1097.

This work is partially supported by the National Natural Science Foundation of China (61673258, 61075115, 61403249, 61603242).

LIJuan, born in 1991, M. S. candidate. Her research interests include embedded control system, intelligent algorithm, robot system.

YOUXiaoming, born in 1963, Ph. D., professor. Her research interests include intelligent information processing, pattern recognition, artificial intelligence, distributed parallel intelligent processing.

LIUSheng, born in 1966, Ph. D., professor. His research interests include intelligent information processing.

CHENJia, born in 1993, M. S. candidate. Her research interests include embedded control system, intelligent algorithm, robot system.