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

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

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

3、食等1.它們通過(guò)其特殊的傳遞信息方式協(xié)同合作,將復(fù)雜的問(wèn)題分解成若干個(gè)簡(jiǎn)單的問(wèn)題來(lái)解決.目前,應(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)化算法.螞蟻之間通過(guò)在每條路徑上留下信息素(,螞蟻通過(guò)每條路徑上的信息素的多少選擇路徑.蟻群算法在解決組合優(yōu)化問(wèn)題上具有顯著優(yōu)勢(shì),適合處理分布式問(wèn)題,求解精度高且其具有較好的正反饋性、并行性、較強(qiáng)的收斂性以及魯棒性等優(yōu)點(diǎn).雖然蟻群算法具備以上優(yōu)點(diǎn),但是其仍存在有待改進(jìn)的地方,如搜索時(shí)間長(zhǎng)、計(jì)算量大、易陷入

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

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

6、1,2,m 記錄當(dāng)前螞蟻k 所走過(guò)的位置,避免路徑重復(fù),降低算法效率.在t 時(shí)刻螞蟻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ā)式因子,表示軌跡的相對(duì)重要性,其值越大,螞蟻之間的協(xié)作性越強(qiáng);為期望啟發(fā)式因子,它反應(yīng)了螞蟻在運(yùn)動(dòng)過(guò)程中選擇路徑的受重視程度;ij (t 為啟發(fā)式函數(shù),ij (t =1/d ij .如果2個(gè)所走位置間的距離越短,P ij k

7、(t 越大,則螞蟻k 由位置i 轉(zhuǎn)移到位置j 的概率越高.為避免殘留信息過(guò)多引起殘留信息淹沒(méi)啟發(fā)信息,所以在每只螞蟻?zhàn)哌^(guò)n 個(gè)指定的位置,要對(duì)信息素進(jìn)行更新.因此,在t +n 時(shí)刻在歷經(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時(shí)刻ij (0=0;ij k(t 表示第k 只螞蟻經(jīng)過(guò)路徑(i ,j 時(shí)在本次循環(huán)中的信息素增加量.根據(jù)信息素的更新,本文選擇Ant-Cy

8、cle 模型作為研究對(duì)象.在該模型中,當(dāng)?shù)趉 只螞蟻在本次循環(huán)中經(jīng)過(guò)(i ,j 時(shí),ij (t =Q /L k ,粒子群算法(PSO 的基本原理粒子群算法是源于鳥類覓食的一種優(yōu)化算法,與遺傳算法類似,是一種基于迭代的優(yōu)化工具.粒子群算法PSO 算法主要是以速度和位置為模型對(duì)目標(biāo)進(jìn)行搜索.在一個(gè)2維平面中隨機(jī)初始化一群粒子,每一個(gè)粒子所通過(guò)的位置表示其可能解,粒子通過(guò)多次尋優(yōu),獲得最優(yōu)路徑.每一次迭代結(jié)束,粒子根據(jù)其個(gè)體極值和全局極值來(lái)更新速度和位置: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è)粒子迄今為止搜索到的個(gè)體極值,g Best 表示全局值,rand (為(0,1之間的隨機(jī)數(shù),為加權(quán)系數(shù).加權(quán)系數(shù)是用于控制前一速度對(duì)當(dāng)前速度的影響,其可以保持粒子的運(yùn)動(dòng)慣性,促進(jìn)粒子有足夠的能力探索新的空間,在算法不斷迭代的過(guò)程中,值隨之減小,個(gè)體極值和全局值不斷更新,最終達(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)缺點(diǎn),將粒子群算法與蟻群算法進(jìn)行相互融合,實(shí)現(xiàn)移動(dòng)機(jī)器人路徑規(guī)劃優(yōu)化.粒子群算法具有較強(qiáng)的全局搜索能力、搜索速度快等優(yōu)點(diǎn),但不能在路徑搜索的過(guò)程中有效地避免障礙物,容易陷入局部最優(yōu)狀態(tài),且在求解組合問(wèn)題時(shí)不具備優(yōu)勢(shì);蟻群算法具有較強(qiáng)的正反饋性、并行性、收斂性以及魯棒性,且其求解精度高,比較適合于組合優(yōu)化問(wèn)題的求解,但其搜索時(shí)間長(zhǎng)、計(jì)算量大,且初始信息匱乏,初始搜索時(shí)目的性差.基于粒子群算法和蟻群算法的各自特點(diǎn),

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

12、PAAA 的工作流程如圖1所示.572第3期張興國(guó),等:基于粒子群-蟻群融合算法的移動(dòng)機(jī)器人路徑優(yōu)化規(guī)劃 圖1 粒子群-蟻群融合算法流程圖3 仿真與實(shí)驗(yàn)分析本文設(shè)計(jì)了一組含有20個(gè)坐標(biāo)位置的路徑尋優(yōu)問(wèn)題,其坐標(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)仿真試驗(yàn),仿

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)路徑對(duì)比算法名稱最優(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)化算法對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行研究.首先利用粒子群算法對(duì)路徑進(jìn)行粗略搜索,獲得問(wèn)題的次優(yōu)解,然后再利用蟻群算法次優(yōu)路徑進(jìn)行精確搜索,最終獲得最優(yōu)路徑.根據(jù)仿真結(jié)果顯示分672江西師范大學(xué)學(xué)報(bào)(自然科學(xué)版2014年析可知,粒子群-蟻群融合優(yōu)化算法獲得的最終最優(yōu)解優(yōu)于單一以蟻群算法或粒子群算法進(jìn)行路徑尋優(yōu)的最優(yōu)解.該算法對(duì)于移動(dòng)機(jī)器人路徑規(guī)劃的應(yīng)用研究具有一定的參考意義.5 參考文獻(xiàn)1薛頌東,曾建潮.群機(jī)器人研究綜述J .模式識(shí)別與

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 .長(zhǎng)沙:中南大學(xué),2010.9禹旺明,熊紅云.改進(jìn)的蟻群算法在TSP 中的應(yīng)用J .現(xiàn)代物流技術(shù),2009(1:27-29.10卞鋒.粒子群

19、優(yōu)化算法在TSP 中的研究及應(yīng)用D .無(wú)錫:江南大學(xué),2008.11蘇晉榮,王建珍.改進(jìn)粒子群優(yōu)化算法求解TSP 問(wèn)題J .計(jì)算機(jī)工程與應(yīng)用,2010,46(4:52-54.12姚興田,吳亮亮,馬永林.自動(dòng)3維重構(gòu)中確定下一最優(yōu)視點(diǎn)的方法研究J .江西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2013,37(6:569-573.13張磊,張興國(guó).基于李群代數(shù)表達(dá)幀間位姿變化矩陣的3D 視覺(jué)跟蹤研究J .江西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2012,36(5:466-471.14徐雪松.復(fù)雜環(huán)境中移動(dòng)機(jī)器人路徑規(guī)劃J .江西師范大學(xué)學(xué)報(bào):自然科學(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期張興國(guó),等:基于粒子群-蟻群融合算法的移動(dòng)機(jī)器人路徑優(yōu)化規(guī)劃 基于粒子群-蟻群融合算法的移動(dòng)機(jī)器人路徑優(yōu)化規(guī)劃作者:張興國(guó), 周東健, 李成浩, ZHANG Xing-guo, ZHOU Dong-jian, LI Cheng-hao作者單位:南通大學(xué)機(jī)械工程學(xué)院,江蘇 南通,226019刊名: 江西師范大學(xué)學(xué)報(bào)(自然科學(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