一種改進粒子群通訊算法在目標(biāo)搜索中的應(yīng)用

何喬

摘 要：針對粒子群算法應(yīng)用于機器人目標(biāo)搜索過程中存在的早熟現(xiàn)象，提出一種基于改進粒子群算法和模擬退火算法相結(jié)合的目標(biāo)搜索新方法，以提高算法的全局搜索能力。為解決通訊距離有限、機器人無法與基站進行信息交互和不能實時追蹤動態(tài)目標(biāo)等問題，引入通訊功能。算法中機器人與基站有兩種通訊方式，一種是基站跟隨最優(yōu)機器人移動的通訊方式，另一種是在前者基礎(chǔ)上將機器人按一定比例分為通訊機器人和搜索機器人的通訊方式，由通訊機器人負(fù)責(zé)搜索機器人與基站之間的通訊。兩種通訊方式下機器人都采用動態(tài)多目標(biāo)搜索策略搜索動態(tài)多目標(biāo)。在考慮通訊距離的情況下，經(jīng)過仿真測試，與傳統(tǒng)的通訊粒子群算法相比，提出的改進通訊粒子群算法能更加有效地追蹤動態(tài)目標(biāo)。

關(guān)鍵詞：粒子群算法；模擬退火算法；通訊機器人；動態(tài)多目標(biāo)搜索

DOI：10. 11907/rjdk. 182395

中圖分類號：TP301 文獻標(biāo)識碼：A 文章編號：1672-7800（2019）005-0031-06

Abstract： Aiming at the prematurity of swarm optimization （PSO） algorithm when applied to the robot target search process， a new target search method based on improved particle swarm optimization algorithm and simulated annealing algorithm is proposed. For the premature phenomenon of particle swarm optimization algorithm， the simulated annealing algorithm is introduced to improve the algorithm of the global search capability. In order to tackle the problem that the robot can not have information interaction with the base station and real-time dynamic target tracking due to the limited communication distance， this paper introduces the communication function. Algorithm of robot and base station has two kinds of communication methods， one is the base station with the optimal robot of mobile communication， the other is based on the former general robot according to certain proportion into the communication robot communication methods and search robot， the robot communications is responsible for the search robot and communications between the base station. Robots are under two kinds of communication methods using dynamic multi-objective search strategy. Under the condition of considering the communication distance， compared with the traditional communication particle swarm optimization algorithm， the improved communication particle swarm optimization algorithm can track dynamic targets more effectively according to the simulation test.

Key Words：particle swarm optimization；simulated annealing algorithm； communication robots； dynamic multi-objective search

0 引言

粒子群算法思想源于對鳥群簡化模型的研究及行為模擬。由Craig Reynolds[1]建立的Boid模型是一個簡單的人工生命系統(tǒng)，專門用來模擬鳥類聚集飛行的行為。模型中的每個個體行為只與周圍的鄰近個體行為有關(guān)，每個個體只需要遵循下面3項原則：①避免碰撞原則：避免每個個體與相鄰的個體發(fā)生碰撞；②速度一致原則：和相鄰個體間平均速度保持一致；③向中心聚集原則：向相鄰個體的平均位置移動。Kennedy & Eberhart[2-3]從鳥類群居性動物的覓食行為中得到啟示，提出了粒子群算法（PSO）。在PSO中，將食物地點看成求解問題的最優(yōu)解，通過每個個體之間位置信息的交互，逐步指引所有粒子聚集，同時朝著最優(yōu)解方向移動。PSO實現(xiàn)簡單，容易理解，與GA[4-5]等進化算法的很大不同之處在于：①PSO沒有交叉和變異過程；②PSO沒有淘汰粒子機制；③PSO不但具有局部信息交互能力，還有全局信息交互能力，這些能力通過粒子群的記憶能力體現(xiàn)。

現(xiàn)實生活中有很多惡劣環(huán)境，機器人比人更適合工作，如爆炸物和放射源的檢測，使用機器人操作會更安全[6]，因此一些學(xué)者將粒子群算法應(yīng)用于機器人目標(biāo)搜索中。文獻[7]提出運用分布式粒子群算法搜索動態(tài)目標(biāo)，利用分布式思想的優(yōu)勢改進算法從而提升算法效率；文獻[8]提出運用一種動態(tài)粒子群算法搜索動態(tài)目標(biāo)，從而減少算法耗時；文獻[9]提出一種多機器人粒子群目標(biāo)搜索算法對多個目標(biāo)進行搜索。這些算法改進只是對參數(shù)作了修改，當(dāng)搜索范圍很大、機器人之間在相互通信[10-11]時難以完成對移動目標(biāo)的跟蹤，即動態(tài)多目標(biāo)追蹤問題沒有得到很好解決。

針對這些問題，為使機器人目標(biāo)搜索仿真實驗更加接近真實情況，考慮通訊距離限制問題，本文提出一種改進的粒子群通訊方式，以實現(xiàn)動態(tài)多目標(biāo)搜索。

1 相關(guān)工作

1.1 粒子群算法

粒子群算法模擬鳥類覓食過程，采用更新粒子速度-位置的方式搜索目標(biāo)。算法中潛在的解被稱為“粒子”，粒子通過一些簡單的規(guī)則“飛越”解空間尋找目標(biāo)。所有的粒子都有一個根據(jù)所處位置得到的適應(yīng)值和一個指引其搜索方向的速度。種群最初被隨機分布在空間中，通過不停迭代找到最優(yōu)解。在每次迭代過程中，粒子通過追隨兩個極值更新自己的速度和位置，一個是粒子本身在迭代過程中所找到的使適應(yīng)值最優(yōu)的位置，另一個是當(dāng)前粒子群中找到的最優(yōu)位置。粒子找到上述兩個極值后，通過式（1）更新自己的速度，式（2）更新自己的位置[12]。

1.3 移動基站下的通訊方式

在實際目標(biāo)搜索過程中通常會設(shè)置一個基站，基站會保存要搜索目標(biāo)的最優(yōu)位置。機器人在目標(biāo)搜索過程中需要不斷把搜索目標(biāo)位置信息傳送給基站。然而在大多數(shù)模擬機器人目標(biāo)搜索仿真實驗中，只要其中一個機器人找到目標(biāo)位置就意味著其它機器人也獲得這個位置。這只是理想的情形，而現(xiàn)實中機器人在空間中搜索目標(biāo)很不確定，因為現(xiàn)實搜索過程中每個機器人都會有一個通訊半徑，如果超過這個半徑，機器人和基站之間信息就不能相互傳遞。在這種背景下，提出一種在有限通訊距離下的新型通訊方式。由粒子群算法基本原理可知，搜索過程中機器人的運動趨勢是向著群體中的最優(yōu)機器人移動，如果在搜索中基站向最優(yōu)機器人移動，則會最大可能地使基站與絕大部分機器人通訊，但同時也會錯過與一些機器人的通訊機會。所以在新型通訊方式下，為了在仿真實驗中使基站與機器人實現(xiàn)更好的通訊，基站在移動過程中將保存所遇到的機器人位置，并向著最優(yōu)機器人位置和基站內(nèi)保存的其它機器人平均位置合成方向運動[20]。

1.4 增加通訊機器人的通訊方式

為了讓移動基站模式具有更廣的通訊范圍，在移動基站通訊方式的基礎(chǔ)上將機器人群按一定比例分為通訊機器人和搜索機器人。通訊機器人主要負(fù)責(zé)與處在基站通訊范圍外的機器人進行通訊，搜索機器人主要負(fù)責(zé)搜索任務(wù)。這樣的分工可使搜索機器人不用去考慮通訊問題，只需依靠通訊機器人就能使基站與所有搜索機器人進行通訊。在通訊過程中基站保存著每個搜索機器人的個體極值，在移動中廣播自己的位置和全局極值的同時，廣播每個搜索機器人的個體極值。如果通訊機器人無法與基站進行通訊，則增大移動步長向基站方向運動，并保證每個通訊機器人的通訊范圍內(nèi)至少存在一個通訊機器人，這樣可使每個通訊機器人能完成通訊任務(wù)。搜索機器人在搜索過程中的位置是實時變化的，當(dāng)搜索機器人有通訊需求時，如果通訊機器人能接近搜索機器人將要搜索的路徑，也就是將通訊機器人往個體極值和全局極值合成的方向逐個運動，以增大與搜索機器人進行通訊的概率。進行通訊時，搜索機器人將所獲得的位置信息與基站內(nèi)保存的位置進行比較，如果優(yōu)于基站內(nèi)保存的位置則更新。為了使機器人之間的消息傳遞更加接近實際，在此參照了路由協(xié)議中的信息傳遞方式，如圖1所示。

圖1中，SRobot表示搜索機器人，CRobot3表示通訊機器人。假設(shè)機器人之間的最大通訊距離為[R]，圖中通訊機器人之間的距離R1、R2、R41、R32都小于R。當(dāng)滿足某個通訊機器人與基站的通訊條件時，其它通訊機器人只要在通訊范圍內(nèi)就可經(jīng)過這個機器人與基站進行信息交互，而經(jīng)過的機器人數(shù)量稱為跳數(shù)，例如能直接與基站進行通訊跳數(shù)為1。在通訊過程中通訊機器人會將自己到基站之間的跳數(shù)傳遞給基站，由基站廣播所有通訊機器人當(dāng)前的跳數(shù)。通訊中只可與擁有同樣跳數(shù)或更低跳數(shù)的機器人進行通訊。CRobot3可經(jīng)過兩條路徑與基站通訊，一條跳數(shù)為2，一條跳數(shù)為3。為了提高消息傳遞效率，降低丟包率，本文將使用迪杰斯特拉算法計算出經(jīng)過節(jié)點數(shù)最少的一條傳遞路徑。

在通訊過程中，為了模擬機器人的通訊需求，提高目標(biāo)搜索效率，本文引入通訊間隔概念，只有當(dāng)前時間和上一次與移動基站通訊的時間差大于通訊間隔才能讓機器人與基站進行通信。把上一次和基站信息交互的時間定義為[tc]，[t]定義為當(dāng)前時間，[c]表示通訊間隔，如果時間[t]和通訊時間[tc]之間的時間間隔大于[c]，通訊機器人就會和基站通訊，通訊成功后[tc]將更新為[t]。時間間隔[c]是可以調(diào)整的變量，當(dāng)希望通訊機器人與基站頻繁交流時就設(shè)置較小的[c]，反之則通訊機器人能夠搜索到更廣闊的區(qū)域。

2 改進的通訊粒子群算法

粒子群算法是一種啟發(fā)式算法，具有記憶功能，可以進行信息共享，但是卻容易陷入局部最優(yōu)解。模擬退火算法具有全局尋優(yōu)的優(yōu)點，可以接受較差的點，擴大尋優(yōu)范圍，能夠很好地跳出局部最優(yōu)解。融合兩種算法，彌補各自的缺點，能夠提高算法性能。本次實驗求解最小值，具體流程如圖4所示。

機器人在搜索目標(biāo)過程中的每一次迭代都會與基站通訊。如果通訊沒有成功，則根據(jù)新粒子的速度和位置計算粒子的適應(yīng)度函數(shù)。如果適應(yīng)度函數(shù)差值小于0，則接受粒子的位置作為個體的最優(yōu)值保存下來，如果適應(yīng)度差值大于0，則按照概率接受粒子的當(dāng)前位置開始退火，如果沒有滿足終止條件則繼續(xù)迭代。如果[t-tc>c+θi]時機器人和基站開始通訊，能否更新全局最優(yōu)值由機器人是否能和基站直接連接或間接通過其它機器人連通決定。如果連通則通訊成功，記錄最優(yōu)值并把最優(yōu)值傳給其它機器人，否則通訊失敗。沒有滿足終止條件就繼續(xù)迭代，尋找最優(yōu)值，只有找到新的最優(yōu)值才會和基站通訊。

3 仿真實驗

3.1 實驗內(nèi)容與實驗設(shè)置

（1）改進的通訊粒子群算法在不同通訊機器人數(shù)量上的實驗對比。本實驗將通訊機器人比例取10%、20%、30%、50%，分別測試這4種比例下的算法性能，以測試改進后的通訊模式是否可行，最終的算法評價指標(biāo)為每一次迭代的全局最優(yōu)值與目標(biāo)真實位置之間的歐氏距離。

從圖4-圖7可以看出，當(dāng)通訊機器人比例為20%時，算法性能最好，當(dāng)比例為50%時，算法誤差過大且波動也較大。因為提高通訊機器人比例就會減少搜索機器人數(shù)量，使機器人搜索范圍縮小，也就降低了找到最優(yōu)值的概率。

（2）改進的通訊粒子群算法與C-dPSO仿真對比。以上實驗得到一個算法性能較優(yōu)的通訊機器人比例，為更好地驗證本文提出的改進的通訊粒子群算法性能，將兩種通訊方式與傳統(tǒng)通訊粒子群算法C-dPSO進行對比。傳統(tǒng)的C-dPSO中基站為固定不動，機器人與基站在通訊范圍內(nèi)才進行信息交流。

圖8、圖9、圖10分別為移動基站—無通訊機器人模式和移動基站下通訊機器人比例為20%和C-dPSO下的誤差仿真。將圖8無通訊機器人模式與圖9存在通訊機器人模式相比，發(fā)現(xiàn)在相同條件下，當(dāng)通訊過程中存在通訊機器人時的誤差要比沒有通訊機器人時小，但是帶通訊機器人的移動基站模式算法性能很大程度受機器人數(shù)量的限制，所以在機器人數(shù)量較少的情況下，無通訊機器人模式可能更佳。圖10為C-dPSO的誤差仿真，可以看出在C-dPSO模式下能很平穩(wěn)地追蹤目標(biāo)，但是各個目標(biāo)誤差值差距較大。經(jīng)過與圖8移動基站—無通訊機器人模式和移動基站下通訊機器人比例為20%的誤差仿真圖進行對比，可以看出本文提出改進的通訊粒子群算法在誤差上要小于C-dPSO，這是因為融合帶通訊粒子群算法下兩種通訊模式都能使機器人與基站進行信息交流。從以上分析可以得出，本文提出的改進通訊粒子群算法通訊能力較傳統(tǒng)的C-dPSO更優(yōu)，且具有實時追蹤動態(tài)多目標(biāo)的能力。

4 結(jié)語

使用MATLAB對本文提出的改進通訊粒子群算法搜索動態(tài)多目標(biāo)進行對比仿真。實驗表明，在通訊距離限制的情況下，本文算法能使機器人與基站良好通訊，更好地追蹤多個動態(tài)目標(biāo)。經(jīng)過仿真對比發(fā)現(xiàn)，新型通訊方式下的誤差比現(xiàn)有通訊粒子群算法小，這說明本文提出的算法是切實有效的。本文算法使機器人搜索目標(biāo)仿真實驗更加貼近實際，為粒子群算法應(yīng)用于實際目標(biāo)搜索提供了思路。但是對于如何選擇合適的通訊機器人比例需根據(jù)不同情況確定，這有待進一步研究。

參考文獻：

[1] REYNOLDS C W. Flocks， herds and schools： a distributed behavioral model[J]. Computer Graphics， 1987， 21（4）：25-34.

[2] KENNEDY J， EBERHART R C. Particle swarm optimization.proceedings[J]. IEEE International Conference on Neural Networks，1995（4）：1942-1948.

[3] EBERHART R，KENNEDY J. A new optimizer using particle swarm theory[C].Proceeding of the sixth international symposium on Micro Machine and Human Science，1995：39-43.

[4] COLORNI A，DORIGO M.Distributed optimization by ant colonies[C].Proceeding of the First European Conference on Artificial Life，1991：134-142.

[5] DORIGO M. Optimization，learning and natural algorithms[C]. Dissertation.Dipartimentodi Elettronica，Politecnico di Milano，Italy，1992.

[6] PERREAULT L，WITTIE M P，SHEPPARD J. Communication-aware distributed PSO for dynamic robotic search[C]. Swarm Intelligence. IEEE， 2014：1-8.

[7] LEE J，CHO K，LEE S，et al. Distributed and energy-efficient target localization and tracking in wireless sensor networks[J]. Computer Communications， 2006， 29（13）： 2494-2505.

[8] HEREFORD J M，SIEBOLD M，NICHOLS S. Using the particle swarm optimization algorithm for robotic search applications[C].2007 IEEE Swarm Intelligence Symposium. IEEE，2007： 53-59.

[9] PUGH J，MARTINOLI A. Distributed adaptation in multi-robot search using particle swarm optimization[C].International Conference on Simulation of Adaptive Behavior，2008：393-402.

[10] CAI Y，YANG S X. A potential field-based pso approach for cooperative target searching of multi-robots[C]. Intelligent Control and Automation. IEEE， 2015：1029-1034.

[11] KENNEDY J. Why does it need velocity[C]. Swarm Intelligence Symposium，2005：38-44.

[12] SHI Y H，EBERHART R C. A modified particle swarm optimizer[C].Proceeding of the IEEE International Conference on Evolutionary Computation，1997：303-308.

[13] 康立山. 非數(shù)值并行算法——模擬退火算法[M]. 北京：科學(xué)出版社，1997：22-55.

[14] DANTZING G，RAMSER J. The truck is patching problem[J]. Management science，1959（6）：80-91.

[15] TIKANM，KI A，KEL，et al. Multi-robot system for exploration in an outdoor environment[C]. International Conference on Robotics and Applications，2007：470-476.

[16] 趙志剛，黃樹運，王偉倩. 基于隨機慣性權(quán)重的簡化粒子群優(yōu)化算法[J]. 計算機應(yīng)用研究，2014，31（2）：361-363.

[17] JOHNSON D S，ARAGON C R，MCGEOCH L A，et al. Optimization by simulated annealing： an experimental evaluation； part III[J]. Science， 1990， 39（2548）：671-680.

[18] BOULEIMEN K，LECOCQ H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J]. European Journal of Operational Research， 2003， 149（2）：268-281.

[19] YANG H，YANG Y，YANG Z， et al. A particle swarm optimization algorithm based on simulated annealing[J]. Advanced Materials Research，2014（989-994）：2301-2305.

[20] PELUSI L，PASSARELLA A，CONTI M. Opportunistic networking： data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine， 2006， 44（11）：134-141.

（責(zé)任編輯：杜能鋼）