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

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

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

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

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

6、1,2,m 記錄當前螞蟻k 所走過的位置,避免路徑重復,降低算法效率.在t 時刻螞蟻k 由i 位置轉移到j 位置由狀態轉移概率P ij k (t 決定,狀態轉移概率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 下一步允許選擇的位置;為信息啟發式因子,表示軌跡的相對重要性,其值越大,螞蟻之間的協作性越強;為期望啟發式因子,它反應了螞蟻在運動過程中選擇路徑的受重視程度;ij (t 為啟發式函數,ij (t =1/d ij .如果2個所走位置間的距離越短,P ij k

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

8、cle 模型作為研究對象.在該模型中,當第k 只螞蟻在本次循環中經過(i ,j 時,ij (t =Q /L k ,粒子群算法(PSO 的基本原理粒子群算法是源于鳥類覓食的一種優化算法,與遺傳算法類似,是一種基于迭代的優化工具.粒子群算法PSO 算法主要是以速度和位置為模型對目標進行搜索.在一個2維平面中隨機初始化一群粒子,每一個粒子所通過的位置表示其可能解,粒子通過多次尋優,獲得最優路徑.每一次迭代結束,粒子根據其個體極值和全局極值來更新速度和位置: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 為粒子的當前速度,X ij (t 為粒子的當前位置,C 1、C 2為學習因子,P ij ,Best 表示第(i ,j 個粒子迄今為止搜索到的個體極值,g Best 表示全局值,rand (為(0,1之間的隨機數,為加權系數.加權系數是用于控制前一速度對當前速度的影響,其可以保持粒子的運動慣性,促進粒子有足夠的能力探索新的空間,在算法不斷迭代的過程中,值隨之減小,個體極值和全局值不斷更新,最終達到全局最優.加權系數的表達式為=max -N iter (max -min N iter ,max ,其中m

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

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

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

13、真結果如圖2圖4所示 .圖2 基于蟻群算法的最優路徑圖圖3 基于粒子群算法的最優路徑圖圖4 基于粒子群-蟻群融合算法的最優路徑圖由圖2圖4可以分析得到最優解及最優路徑,如表1所示.表1 3種算法最優解及最優路徑對比算法名稱最優解最優路徑蟻群算法(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粒子群-蟻群融合優化算法(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結果表明,粒子群-蟻群融合優化算法獲得的最優解要優于單一的蟻群算法或單一的粒子群算法.4 結論本文提出了基于粒子群-蟻群算法相瑪融合的綜合優化算法對移動機器人路徑規劃問題進行研究.首先利用粒子群算法對路徑進行粗略搜索,獲得問題的次優解,然后再利用蟻群算法次優路徑進行精確搜索,最終獲得最優路徑.根據仿真結果顯示分672江西師范大學學報(自然科學版2014年析可知,粒子群-蟻群融合優化算法獲得的最終最優解優于單一以蟻群算法或粒子群算法進行路徑尋優的最優解.該算法對于移動機器人路徑規劃的應用研究具有一定的參考意義.5 參考文獻1薛頌東,曾建潮.群機器人研究綜述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陳曉娥,蘇理.一種基于環境柵格地圖的多機器人路徑規劃方法J .機械科

18、學與技術,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張頻捷.蟻群優化算法及其應用研究D .長沙:中南大學,2010.9禹旺明,熊紅云.改進的蟻群算法在TSP 中的應用J .現代物流技術,2009(1:27-29.10卞鋒.粒子群

19、優化算法在TSP 中的研究及應用D .無錫:江南大學,2008.11蘇晉榮,王建珍.改進粒子群優化算法求解TSP 問題J .計算機工程與應用,2010,46(4:52-54.12姚興田,吳亮亮,馬永林.自動3維重構中確定下一最優視點的方法研究J .江西師范大學學報:自然科學版,2013,37(6:569-573.13張磊,張興國.基于李群代數表達幀間位姿變化矩陣的3D 視覺跟蹤研究J .江西師范大學學報:自然科學版,2012,36(5:466-471.14徐雪松.復雜環境中移動機器人路徑規劃J .江西師范大學學報:自然科學版,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(責任編輯:冉小曉772第3期張興國,等:基于粒子群-蟻群融合算法的移動機器人路徑優化規劃 基于粒子群-蟻群融合算法的移動機器人路徑優化規劃作者:張興國, 周東健, 李成浩, ZHANG Xing-guo, ZHOU Dong-jian, LI Cheng-hao作者單位:南通大學機械工程學院,江蘇 南通,226019刊名: 江西師范大學學報(自然科學版英文刊名:Journal of Jiangxi Normal University (Natural Sciences Edition年,卷(期:2014(3參考文獻(14條1.薛頌東;曾建潮群機器人研究綜述 2008(022.Montiel-Ross O;Sepulveda R;Castillo O Ant colony test center for planning autonomous mobile ro