基于粒子群-蟻群融合算法的移動機(jī)器人路徑優(yōu)化規(guī)劃

1、第38卷第3期江西師范大學(xué)學(xué)報(自然科學(xué)版2014年5月 Journal of Jiangxi Normal University (Natural Science May 2014收稿日期:2014-01-09基金項目:江蘇省自然科學(xué)基金(BK20131205資助項目.作者簡介:張興國(1975-,男,江蘇沐陽人,副教授,主要從事光機(jī)電一體化、機(jī)器視覺和機(jī)器人技術(shù)方面的研究.文章編號:1000-5862(201403-0274-04基于粒子群-蟻群融合算法的移動機(jī)器人路徑優(yōu)化規(guī)劃張興國,周東健,李成浩(南通大學(xué)機(jī)械工程學(xué)院,江蘇南通 226019摘要:基于TSP 問題,提出了一種基于粒子群-

2、蟻群算法相互融合的綜合優(yōu)化算法對移動機(jī)器人路徑規(guī)劃問題進(jìn)行研究.通過粒子群算法對全局路徑實施粗略搜索,獲得部分次優(yōu)解,在獲得次優(yōu)解的路徑上進(jìn)行信息素分布,再采用蟻群算法進(jìn)行精確搜索,得到路徑規(guī)劃的最優(yōu)解.實驗結(jié)果表明:粒子群-蟻群融合優(yōu)化算法在路徑尋優(yōu)上優(yōu)于蟻群算法及粒子群算法.關(guān)鍵詞:蟻群算法;粒子群算法;TSP 問題;路徑規(guī)劃;移動機(jī)器人中圖分類號:TP 242 文獻(xiàn)標(biāo)志碼:A0 引言機(jī)器人智能化是未來機(jī)器人發(fā)展的必然趨勢,部分智能機(jī)器人已在航空航天、深?？碧?、醫(yī)學(xué)救護(hù)、工業(yè)生產(chǎn)、民用等領(lǐng)域得到廣泛應(yīng)用.目前移動機(jī)器人的路徑規(guī)劃方式主要是仿照群居動物的生活習(xí)性,如螞蟻覓食、蜜蜂采蜜、魚群覓

3、食等1.它們通過其特殊的傳遞信息方式協(xié)同合作,將復(fù)雜的問題分解成若干個簡單的問題來解決.目前,應(yīng)用于多機(jī)器人路徑規(guī)劃中主要算法有:蟻群算法2、遺傳算法3、粒子群算法4、人工神經(jīng)網(wǎng)絡(luò)算法5、圖論法6和禁忌搜索7等.蟻群算法(ACO 是由意大利學(xué)者M(jìn).Dorigo等8于20世紀(jì)90年代提出的模擬進(jìn)化算法.螞蟻之間通過在每條路徑上留下信息素(,螞蟻通過每條路徑上的信息素的多少選擇路徑.蟻群算法在解決組合優(yōu)化問題上具有顯著優(yōu)勢,適合處理分布式問題,求解精度高且其具有較好的正反饋性、并行性、較強(qiáng)的收斂性以及魯棒性等優(yōu)點.雖然蟻群算法具備以上優(yōu)點,但是其仍存在有待改進(jìn)的地方,如搜索時間長、計算量大、易陷入

4、局部最優(yōu)等缺點11-14.粒子群算法(PSO 是一種優(yōu)化仿生算法,是由Eberhart 博士和Kennedy 博士基于鳥群覓食行為提出的一種新型算法10.粒子群算法具有較強(qiáng)的全局搜索能力、收斂速度快、穩(wěn)定性強(qiáng)、搜索時間短等優(yōu)點.但其在組合優(yōu)化問題時沒有優(yōu)勢,在路徑搜索過程中易產(chǎn)生早熟現(xiàn)象,易陷入局部最優(yōu)11.基于蟻群算法和粒子群算法的優(yōu)缺點,針對TSP 問題開展移動機(jī)器人路徑規(guī)劃研究,提出將蟻群算法(ACO 與粒子群算法(PSO 相互融合,即先利用粒子群算法的全局搜索能力,對整個路徑進(jìn)行粗略搜索,獲得問題的次優(yōu)解;再利用次優(yōu)解對部分路徑上的信息素重新分布,增強(qiáng)信息素,提高蟻群算法的搜索能力;最

5、后利用蟻群算法對次優(yōu)路徑采取精確搜索,最終得到最優(yōu)解.1 蟻群算法及粒子群算法基本原理1.1 蟻群算法(ACO 的基本原理根據(jù)實驗室場地要求建立n 個螞蟻游歷位置坐標(biāo)C(x i ,y i ,設(shè)每2個點之間的距離為d ij ,依下式計算出兩點之間的距離:d ij =(x i -x j 2+(y i -y j 槡2.在初始時刻隨機(jī)地將m 個螞蟻放到不同的位置,保證初始時刻每個螞蟻不會在同一位置出現(xiàn).設(shè)在0時刻,各條路徑上的信息素量ij (0=C (C 為常數(shù),螞蟻k (k =1,2,m 在運動過程中,根據(jù)各條路上所含有的信息素量情況決定其轉(zhuǎn)移方向.在運動過程中采用禁忌表T tabu ,k (k =

6、1,2,m 記錄當(dāng)前螞蟻k 所走過的位置,避免路徑重復(fù),降低算法效率.在t 時刻螞蟻k 由i 位置轉(zhuǎn)移到j(luò) 位置由狀態(tài)轉(zhuǎn)移概率P ij k (t 決定,狀態(tài)轉(zhuǎn)移概率P ij k(t 為P ij k (t =ij (t ij (t s Tallowed ,kis (t is (t 0, j T allowed ,k ,其他,其中j 表示螞蟻k 下一步允許選擇的位置;為信息啟發(fā)式因子,表示軌跡的相對重要性,其值越大,螞蟻之間的協(xié)作性越強(qiáng);為期望啟發(fā)式因子,它反應(yīng)了螞蟻在運動過程中選擇路徑的受重視程度;ij (t 為啟發(fā)式函數(shù),ij (t =1/d ij .如果2個所走位置間的距離越短,P ij k

7、(t 越大,則螞蟻k 由位置i 轉(zhuǎn)移到位置j 的概率越高.為避免殘留信息過多引起殘留信息淹沒啟發(fā)信息,所以在每只螞蟻走過n 個指定的位置,要對信息素進(jìn)行更新.因此,在t +n 時刻在歷經(jīng)i 到j(luò) 上的信息量可按如下規(guī)則進(jìn)行調(diào)整:ij (t +n =(1-ij (t +ij (t ,(1ij (t =mk =1ij k(t ,(2其中表示信息素?fù)]發(fā)系數(shù),則1-表示信息素殘留因子,(0,1;ij (t 表示螞蟻在本次循環(huán)中路徑(i ,j 上的信息素增量,t =0時刻ij (0=0;ij k(t 表示第k 只螞蟻經(jīng)過路徑(i ,j 時在本次循環(huán)中的信息素增加量.根據(jù)信息素的更新,本文選擇Ant-Cy

8、cle 模型作為研究對象.在該模型中,當(dāng)?shù)趉 只螞蟻在本次循環(huán)中經(jīng)過(i ,j 時,ij (t =Q /L k ,粒子群算法(PSO 的基本原理粒子群算法是源于鳥類覓食的一種優(yōu)化算法,與遺傳算法類似,是一種基于迭代的優(yōu)化工具.粒子群算法PSO 算法主要是以速度和位置為模型對目標(biāo)進(jìn)行搜索.在一個2維平面中隨機(jī)初始化一群粒子,每一個粒子所通過的位置表示其可能解,粒子通過多次尋優(yōu),獲得最優(yōu)路徑.每一次迭代結(jié)束,粒子根據(jù)其個體極值和全局極值來更新速度和位置:V ij (t +1=V ij (t +C 1rand (P ij ,Best -X i ,j (t +C 2rand (g Best -X ij

9、 (t ,X ij (t +1=X ij (t +V i ,j (t +1,其中V ij (t 為粒子的當(dāng)前速度,X ij (t 為粒子的當(dāng)前位置,C 1、C 2為學(xué)習(xí)因子,P ij ,Best 表示第(i ,j 個粒子迄今為止搜索到的個體極值,g Best 表示全局值,rand (為(0,1之間的隨機(jī)數(shù),為加權(quán)系數(shù).加權(quán)系數(shù)是用于控制前一速度對當(dāng)前速度的影響,其可以保持粒子的運動慣性,促進(jìn)粒子有足夠的能力探索新的空間,在算法不斷迭代的過程中,值隨之減小,個體極值和全局值不斷更新,最終達(dá)到全局最優(yōu).加權(quán)系數(shù)的表達(dá)式為=max -N iter (max -min N iter ,max ,其中m

10、ax 為最大加權(quán)系數(shù),min 為最小加權(quán)系數(shù),N iter 為迭代次數(shù),N iter ,max 為最大迭代次數(shù).2 粒子群-蟻群融合優(yōu)化算法根據(jù)粒子群算法(ACO 和蟻群算法(PSO 優(yōu)缺點,將粒子群算法與蟻群算法進(jìn)行相互融合,實現(xiàn)移動機(jī)器人路徑規(guī)劃優(yōu)化.粒子群算法具有較強(qiáng)的全局搜索能力、搜索速度快等優(yōu)點,但不能在路徑搜索的過程中有效地避免障礙物,容易陷入局部最優(yōu)狀態(tài),且在求解組合問題時不具備優(yōu)勢;蟻群算法具有較強(qiáng)的正反饋性、并行性、收斂性以及魯棒性,且其求解精度高,比較適合于組合優(yōu)化問題的求解,但其搜索時間長、計算量大,且初始信息匱乏,初始搜索時目的性差.基于粒子群算法和蟻群算法的各自特點,

11、取長補(bǔ)短,將2種算法進(jìn)行有機(jī)融合,實現(xiàn)綜合優(yōu)化.先利用粒子群算法較強(qiáng)的全局搜索能力進(jìn)行粗搜索,得到一定路徑的信息素;再采用蟻群算法的正反饋機(jī)制進(jìn)行精確搜索.經(jīng)過粗搜索后的初始分布后的信息素分布公式為s =c +p ,其中c 為一個信息素常數(shù),p 為由粒子群算法求得的轉(zhuǎn)換得到的信息素值.蟻群算法和粒子群算法的融合后的步驟如下:(i 先對數(shù)據(jù)初始化;(ii 利用粒子群算法進(jìn)行粗略搜索;(iii 通過粗搜索去獲得TSP 問題次優(yōu)解,獲得次優(yōu)路徑;(iv 在次優(yōu)路徑上的信息素重新分布,增強(qiáng)蟻群算法的搜索能力;(v 利用蟻群算法對次優(yōu)路徑采取精確搜索;(vi 最終獲得問題的最優(yōu)解.粒子群-蟻群融合算法(

12、PAAA 的工作流程如圖1所示.572第3期張興國,等:基于粒子群-蟻群融合算法的移動機(jī)器人路徑優(yōu)化規(guī)劃 圖1 粒子群-蟻群融合算法流程圖3 仿真與實驗分析本文設(shè)計了一組含有20個坐標(biāo)位置的路徑尋優(yōu)問題,其坐標(biāo)集合為C =(1010,(1040,(2020,(2070,(3010,(3050,(3090,(4030,(4070,(5010,(5050,(5070,(6020,(6090,(7030,(7050,(7080,(8040,(8080,(9090.選取螞蟻數(shù)m =20,迭代次數(shù)N c =200,將本坐標(biāo)集合分別利用蟻群算法、粒子群算法、粒子群-蟻群融合優(yōu)化算法進(jìn)行路徑尋優(yōu)仿真試驗,仿

13、真結(jié)果如圖2圖4所示 .圖2 基于蟻群算法的最優(yōu)路徑圖圖3 基于粒子群算法的最優(yōu)路徑圖圖4 基于粒子群-蟻群融合算法的最優(yōu)路徑圖由圖2圖4可以分析得到最優(yōu)解及最優(yōu)路徑,如表1所示.表1 3種算法最優(yōu)解及最優(yōu)路徑對比算法名稱最優(yōu)解最優(yōu)路徑蟻群算法(ACO 387.301217-19-20-16-18-15-13-10-8粒子群算法(PSO 384.781811-12-9-4-7-14-17-20-19-16-18-15-13-10-5-1-3-2-6-8粒子群-蟻群融合優(yōu)化算法(PAAA 383.73833-1-5-8-10-13-15-18-16-20-19-17-14-7-4-9-12-11

14、-6-2圖2圖4以及表1結(jié)果表明,粒子群-蟻群融合優(yōu)化算法獲得的最優(yōu)解要優(yōu)于單一的蟻群算法或單一的粒子群算法.4 結(jié)論本文提出了基于粒子群-蟻群算法相瑪融合的綜合優(yōu)化算法對移動機(jī)器人路徑規(guī)劃問題進(jìn)行研究.首先利用粒子群算法對路徑進(jìn)行粗略搜索,獲得問題的次優(yōu)解,然后再利用蟻群算法次優(yōu)路徑進(jìn)行精確搜索,最終獲得最優(yōu)路徑.根據(jù)仿真結(jié)果顯示分672江西師范大學(xué)學(xué)報(自然科學(xué)版2014年析可知,粒子群-蟻群融合優(yōu)化算法獲得的最終最優(yōu)解優(yōu)于單一以蟻群算法或粒子群算法進(jìn)行路徑尋優(yōu)的最優(yōu)解.該算法對于移動機(jī)器人路徑規(guī)劃的應(yīng)用研究具有一定的參考意義.5 參考文獻(xiàn)1薛頌東,曾建潮.群機(jī)器人研究綜述J .模式識別與

15、人工智能,2008,21(2:177-185.2Montiel-Ross O ,Sepulveda R ,Castillo O ,et al.Ant colonytest center for planning autonomous mobile robot naviga-tion J .Computer Application in Engineer Education ,2013,21(2:214-229.3Roberge V ,Tarbouchi M ,Labonte G.Comparison of paral-lel genetic algorithm and particle swa

16、rm optimization for real-time UAV path planning J .IEEE Transactions onIndustrial Informatics ,2012,9(1:132-141.4Tan Jingjing ,Zhao Ping.Advances in biomedical engineer-ing-2012international conference on environmental engi-neering and technology (ICEET2012C .Hong Kong :Information Engineering Resea

17、rch Institute ,2012.5Chang Qingliang ,Zhou Huaqiang ,Hou Chaojiong.Usingparticle swarm optimization algorithm in an artificial neural network to forecast the strength of paste filling materialJ .Journal of China University of Mining &Technology ,2008(4:551-555.6陳曉娥,蘇理.一種基于環(huán)境柵格地圖的多機(jī)器人路徑規(guī)劃方法J .機(jī)械科

18、學(xué)與技術(shù),2009,28(10:1335-1139.7Liu Jingfa ,Li Gang ,Geng Huantong.A new heuristic algo-rithm for the circular packing problem with equilibrium constraints J .Science China :Information Sciences ,2011,54(8:1572-1575.8張頻捷.蟻群優(yōu)化算法及其應(yīng)用研究D .長沙:中南大學(xué),2010.9禹旺明,熊紅云.改進(jìn)的蟻群算法在TSP 中的應(yīng)用J .現(xiàn)代物流技術(shù),2009(1:27-29.10卞鋒.粒子群

19、優(yōu)化算法在TSP 中的研究及應(yīng)用D .無錫:江南大學(xué),2008.11蘇晉榮,王建珍.改進(jìn)粒子群優(yōu)化算法求解TSP 問題J .計算機(jī)工程與應(yīng)用,2010,46(4:52-54.12姚興田,吳亮亮,馬永林.自動3維重構(gòu)中確定下一最優(yōu)視點的方法研究J .江西師范大學(xué)學(xué)報:自然科學(xué)版,2013,37(6:569-573.13張磊,張興國.基于李群代數(shù)表達(dá)幀間位姿變化矩陣的3D 視覺跟蹤研究J .江西師范大學(xué)學(xué)報:自然科學(xué)版,2012,36(5:466-471.14徐雪松.復(fù)雜環(huán)境中移動機(jī)器人路徑規(guī)劃J .江西師范大學(xué)學(xué)報:自然科學(xué)版,2014,38(1:83-88.The Optimal Path P

20、lanning for Mobile Robot Based on Ant Colony AlgorithmCombined with Particle Swarm OptimizationZHANG Xing-guo ,ZHOU Dong-jian ,LI Cheng-hao(School of Mechanical Engineering ,Nantong University ,Nantong Jiangsu 226019,China Abstract :Aiming at the TSP problem ,in order to research the optimal path pl

21、anning for mobile robot ,a new algo-rithm based on ant colony algorithm combined with particle swarm algorithm(PAAAA has been proposed.Firstly ,using the particle swarm optimization to search the global path ,the second best solution is obtained.Then ,after dis-tributing the pheromones on the second

22、 best solution paths ,using ant colony algorithm to finish accurate searching.Last ,the optimal solution of path planning is achieved.The simulation result shows that PAAA is better than single ant colony algorithm or single particle swarm optimization.Key words :ant colony algorithm ;particle swarm

23、 optimization ;TSP problem ;path planning ;mobile robot(責(zé)任編輯:冉小曉772第3期張興國,等:基于粒子群-蟻群融合算法的移動機(jī)器人路徑優(yōu)化規(guī)劃 基于粒子群-蟻群融合算法的移動機(jī)器人路徑優(yōu)化規(guī)劃作者:張興國, 周東健, 李成浩, ZHANG Xing-guo, ZHOU Dong-jian, LI Cheng-hao作者單位:南通大學(xué)機(jī)械工程學(xué)院,江蘇 南通,226019刊名: 江西師范大學(xué)學(xué)報(自然科學(xué)版英文刊名:Journal of Jiangxi Normal University (Natural Sciences Edition年,卷(期:2014(3參考文獻(xiàn)(14條1.薛頌東;曾建潮群機(jī)器人研究綜述 2008(022.Montiel-Ross O;Sepulveda R;Castillo O Ant colony test center for planning autonomous mobile ro