帶自適應(yīng)整定參數(shù)的機(jī)器人達(dá)爾文粒子群優(yōu)化算法

Robot Darwinian Particle Swarm Optimization

with Self-adaptive Tuning Parameters

余志鵬

(順德職業(yè)技術(shù)學(xué)院電信系，廣東 佛山　528333)

帶自適應(yīng)整定參數(shù)的機(jī)器人達(dá)爾文粒子群優(yōu)化算法

Robot Darwinian Particle Swarm Optimization

with Self-adaptive Tuning Parameters

余志鵬

(順德職業(yè)技術(shù)學(xué)院電信系，廣東 佛山528333)

摘要：對(duì)基數(shù)龐大的機(jī)器人群族引入達(dá)爾文粒子群優(yōu)化算法(DPSO)。該算法將自然選擇應(yīng)用到粒子群算法中，對(duì)整個(gè)機(jī)器人群族進(jìn)行動(dòng)態(tài)分割，根據(jù)上下文評(píng)價(jià)指標(biāo)配合機(jī)器人行為對(duì)機(jī)器人的行為進(jìn)行預(yù)測(cè)，提高了機(jī)器人群族運(yùn)動(dòng)的最優(yōu)逃脫方案成功率。仿真試驗(yàn)表明，通過(guò)對(duì)該算法的輸入?yún)?shù)進(jìn)行自適應(yīng)整定，可以改進(jìn)系統(tǒng)的收斂率，增加通信的約束，使整個(gè)機(jī)器人群族在未來(lái)更大的范圍內(nèi)有效驅(qū)動(dòng)數(shù)量更大的無(wú)線機(jī)器人群族。

關(guān)鍵詞：RDPSO機(jī)器人群族上下文評(píng)價(jià)自適應(yīng)感知能力

Abstract：The Darwinian particle swarm optimization (DPSO) is introduced in the robots swarm with tremendous cardinality. The algorithm applies natural choice in particle swarm algorithm, dynamically divides the entire robots swarm, and predicts the behavior of robots according to the context evaluation indicator with robot’s behavior, to increase the optimal escape rate of the motion of robots swarm. The simulation tests show that through adaptive tuning of the input parameters of the algorithm, the convergence rate of the system can be improved, the communication constrain is increased, which lead to larger wireless robots swarm can be efficiently driven by entire robots swarm in larger scope in the future.

Keywords：Robot Darwinian particle swarm optimization(RDPSO)Robot swarmContext evaluationSelf-adaptionSensory ability

0引言

在基于群族智能化的仿生算法里，比較著名的是粒子群優(yōu)化算法(particle swarm optimization，PSO)[1]。PSO包含很多個(gè)粒子，這些粒子一起進(jìn)行空間探索，以找到最優(yōu)的解決方案。PSO的擴(kuò)展式(如robotic Darwinian PSO, RDPSO)提出在面對(duì)動(dòng)態(tài)和復(fù)雜問題時(shí)會(huì)出現(xiàn)一些障礙，如隨時(shí)間變化的大量次佳方案問題。通常在自然界中發(fā)現(xiàn)的對(duì)關(guān)聯(lián)信息缺乏自適應(yīng)性會(huì)作用于次佳方案，可以通過(guò)全面的解決方案(如統(tǒng)一機(jī)器人的行動(dòng))來(lái)克服這個(gè)缺點(diǎn)[2]。例如，在搜救應(yīng)用中受難者只要還有一點(diǎn)機(jī)會(huì)獲救，機(jī)器人應(yīng)該堅(jiān)持搜救。盡管之前提出的RDPSO本來(lái)就具備獎(jiǎng)懲規(guī)則，以激發(fā)自然選擇來(lái)避免停滯，但機(jī)器人可能會(huì)花費(fèi)大量時(shí)間才意識(shí)到它們陷于次優(yōu)方案或者方案已過(guò)時(shí)。如對(duì)于一個(gè)基于嗅覺的群族，因氣味受擴(kuò)散和氣流原因影響，所以很難尋找到氣味的源頭(如對(duì)致命氣體源的尋找)[3]。對(duì)于這些方案，本文將提出幾個(gè)已有的相關(guān)研究。

1相關(guān)研究

不考慮PSO的主要變體，解決設(shè)定和調(diào)整參數(shù)的困難，以及在更大范圍保持搜索能力的問題，仍然是近來(lái)研究工作的重點(diǎn)[4-5]。例如，學(xué)界提出的一個(gè)最常用的、解決PSO參數(shù)設(shè)置和調(diào)整問題的策略就是基于對(duì)該算法的穩(wěn)定性分析。在文獻(xiàn)[5]中，對(duì)單個(gè)粒子軌跡的廣義模型進(jìn)行分析，廣義模型包含了一組系數(shù)控制系統(tǒng)的收斂度。經(jīng)過(guò)運(yùn)算后的系統(tǒng)是一個(gè)二階線性系統(tǒng)，它的穩(wěn)定性和參數(shù)取決于極點(diǎn)的位置，或者狀態(tài)矩陣的特征值。

Yasuda等人[6]提出一個(gè)基于行為的數(shù)值穩(wěn)定性分析算法，包含研究過(guò)程中對(duì)控制多樣化和激烈化的群組行為的反饋。Yasuda等人展示了使用PSO的穩(wěn)定和非穩(wěn)定區(qū)可控制群組行為。但是，對(duì)于分布式的方法，例如RDPSO，在計(jì)算群組行為時(shí)忽略了一個(gè)事實(shí)，就是群組里每個(gè)機(jī)器人不僅需要即時(shí)共享它的位置，還需要即時(shí)共享它對(duì)所有其他成員的相對(duì)速度。帶有模糊邏輯的合成PSO算法已經(jīng)完成對(duì)這些信息的共享，可以替代上述算法。

模糊邏輯的作用在于不確定性能被包含在決策過(guò)程里。模糊和不精確與定性數(shù)據(jù)的關(guān)聯(lián)衍生出這種邏輯算法，它用語(yǔ)言變量和不確定范圍內(nèi)的重疊關(guān)系函數(shù)得到結(jié)果。例如，在Shi and Eberhart[7]的論文中，把模糊控制與PSO相結(jié)合，使系統(tǒng)能動(dòng)態(tài)地自適應(yīng)粒子慣量。類似地，Liu等人[8]提出一種邏輯控制器，以自適應(yīng)地調(diào)整PSO粒子的最小速率。

目前，沒有研究引進(jìn)自適應(yīng)行為來(lái)克服真實(shí)世界情境里的動(dòng)態(tài)特性。機(jī)器人的行為需要根據(jù)環(huán)境的上下文信息來(lái)改變。當(dāng)考慮基于因子、任務(wù)相關(guān)以及環(huán)境情況時(shí)[9]，要把上下文知識(shí)概念納入計(jì)算中。

2RDPSO算法簡(jiǎn)介

本節(jié)簡(jiǎn)單地介紹文獻(xiàn)[9]提出的RDPSO算法，在文獻(xiàn)[10]有進(jìn)一步的擴(kuò)展。由于RDPOS算法是在真實(shí)移動(dòng)機(jī)器人里對(duì)DPSO的改進(jìn)版，其具有5個(gè)特點(diǎn)。①基于分階數(shù)微積分，有更好的慣性影響；②有故障回避動(dòng)作，避免撞車；③有算法保證MANET協(xié)議在整個(gè)任務(wù)中保持連接；④用異常處理算法對(duì)機(jī)器人建立二維慣性調(diào)度，保護(hù)MANET協(xié)議的連接，這個(gè)算法在機(jī)器人里傳播得越廣越好；⑤用異常賞罰機(jī)制來(lái)評(píng)估機(jī)器人的檢測(cè)和創(chuàng)新效果。

機(jī)器人n的行為可以用以下積分方程來(lái)描述，在每個(gè)離散時(shí)間片中，t∈No：

(1)

(2)

部分系數(shù)α允許描述機(jī)器人的軌道現(xiàn)象，因?yàn)樗膬?nèi)在記憶屬性。認(rèn)知組件χ1[t]和社會(huì)組件χ2[t]在PSO算法里是常規(guī)的，χ1[t]代表機(jī)器人n的局部最佳位置，χ2[t]代表機(jī)器人n的全局最佳位置。避障組件χ3[t]由每個(gè)機(jī)器人的位置代表，它使一個(gè)檢測(cè)距離的障礙的函數(shù)g(xn[t])單調(diào)遞增或遞減。在一個(gè)沒有障礙的環(huán)境里，障礙敏感性權(quán)重ρ3被設(shè)為0。但是，在現(xiàn)實(shí)世界中，必須考慮障礙，ρ3的值取決于幾個(gè)情況：跟主要目標(biāo)相關(guān)(例如，最小消耗功能或最大適應(yīng)力功能)；跟傳感器信息相關(guān)(如g(xn[t])的單調(diào)性)。MANET組件χ4[t]用最接近的機(jī)器人的位置代表，它的位置隨著當(dāng)前機(jī)器人位置的最大通信范圍dmax增加而增加。更大的ρ4可以提高網(wǎng)絡(luò)連接，以保證機(jī)器人間的特定的范圍或者機(jī)器人間的信號(hào)質(zhì)量。

除了這些組件，RDPSO用多群族代表，例如，幾組機(jī)器人一起形成一個(gè)群族，各個(gè)群族各的行為通過(guò)式(1)和式(2)描述。這次方案中，搜索和獎(jiǎng)懲規(guī)則管理著整個(gè)機(jī)器人群族，基于“社會(huì)排斥”概念(更多細(xì)節(jié)請(qǐng)查閱[9])。RDOSO獎(jiǎng)懲規(guī)則如表1所示。

表1　RDPSO獎(jiǎng)懲規(guī)則

在族群中選取特定的機(jī)器人單獨(dú)考慮，而不是像其他活躍群里的機(jī)器人一樣尋找目標(biāo)函數(shù)的最優(yōu)解，因?yàn)檫@樣會(huì)使機(jī)器人隨機(jī)地游移在場(chǎng)景之中。這樣改進(jìn)算法，使它沒那么容易允許目標(biāo)陷入次優(yōu)方案之中。存在多個(gè)群族允許分布式的方法，因?yàn)橐酝盟袡C(jī)器人口定義的網(wǎng)絡(luò)如今被劃分成多個(gè)更小的網(wǎng)絡(luò)(每個(gè)群族1個(gè))，因此節(jié)點(diǎn)減少了，機(jī)器人間的信息交換在相同的網(wǎng)絡(luò)下進(jìn)行。這就是說(shuō)，機(jī)器人間的相互作用被限制在同一群族內(nèi)部的相互作用，使得RDPSO的可擴(kuò)展性可以延伸到大量的機(jī)器人。

3自適應(yīng)系統(tǒng)參數(shù)調(diào)整

為提高群族里RDPSO機(jī)器人的收斂率，機(jī)器人應(yīng)該盡量分散。它們必須保持機(jī)器人間最大通信距離或最小信號(hào)質(zhì)量。在此預(yù)期下，需要找到加強(qiáng)通信因子ρ4和任務(wù)因子(如ρ1和ρ2)的最佳組合，因?yàn)闄C(jī)器人通過(guò)MANET網(wǎng)絡(luò)通信的同時(shí)要規(guī)劃自身的路線。

機(jī)器人利用之前結(jié)果數(shù)據(jù)最簡(jiǎn)易的方法是當(dāng)機(jī)器人間的距離接近極限值(如最大距離或最小信號(hào)質(zhì)量)時(shí)保證增加通信因子ρ4的權(quán)重。因此，探索內(nèi)部的知識(shí)允許定義一個(gè)基于因子的上下文標(biāo)準(zhǔn)來(lái)表示機(jī)器人間的距離。

然而，這種標(biāo)準(zhǔn)需要依靠機(jī)器人間最大通信距離dmax或最小信號(hào)質(zhì)量qmin。在現(xiàn)實(shí)中，只考慮dmax不能匹配實(shí)際的傳播模型，因?yàn)樗鼜?fù)雜。信號(hào)的大小不僅取決于距離，還取決于被其他障礙物反射的多種路徑。

這種結(jié)構(gòu)的整體組織與常用的反饋控制器相似，上下文知識(shí)是通過(guò)對(duì)數(shù)據(jù)的推理分析獲得的，再用這些知識(shí)控制機(jī)器人。因此，基于之前提出和定義的指標(biāo)，人們可以進(jìn)入模糊系統(tǒng)工程的輸入和輸出關(guān)系，關(guān)系函數(shù)會(huì)用廣義的鐘形函數(shù)定義。廣義鐘形函數(shù)典型的高斯函數(shù)多一個(gè)參數(shù)，在關(guān)系函數(shù)里使用的高斯函數(shù)的定義為：

(3)

式中：參數(shù)a、b和c各代表曲線的寬度、斜率、中心。

所有的指標(biāo)都定義為0~1，只有半條曲線被用作代表群族和機(jī)器人的狀態(tài)，如c=1。為了得到更柔和的響應(yīng)，寬度和斜率可以定義為a=0.5、b=3。

每個(gè)輸入的一般關(guān)系函數(shù)如圖1所示。

圖1　每個(gè)輸入的一般關(guān)系函數(shù)

群族動(dòng)作從屬函數(shù)μAS(AS[t])代表群族的活躍程度。至于機(jī)器人的社會(huì)化參數(shù)μSn(Sn[t])，它代表機(jī)器人的社會(huì)化程度。對(duì)于避障從屬闡述μOn(On[t])，可以作出同樣的分析，這里代表了指定機(jī)器人里障礙有多遠(yuǎn)。近似從屬函數(shù)μPn(Pn[t])代表某個(gè)機(jī)器人離其鄰居的距離。

對(duì)于后面的函數(shù)，基于對(duì)之前部分提出的初步試驗(yàn)評(píng)價(jià)，定義如圖2所示的三角成員關(guān)系。這些函數(shù)不僅可以軟化和表達(dá)輸出，更重要的一點(diǎn)是還可以把文獻(xiàn)[11]所示的吸引因子常規(guī)化。

圖2　系數(shù)量化結(jié)果的關(guān)系函數(shù)

加入模糊系統(tǒng)的目的在于對(duì)RDPSO算法可以系統(tǒng)地調(diào)整它的行為。通過(guò)這種方法，機(jī)器人通過(guò)觀察參數(shù)的發(fā)展變化，就可以容易地明白關(guān)于機(jī)器人和群族的上下文信息。因此，上下文知識(shí)的使用，通過(guò)允許對(duì)環(huán)境和任務(wù)的快速檢測(cè)，探索真實(shí)世界的特性的動(dòng)態(tài)信息，提高了機(jī)器人的感知能力(如檢測(cè)障礙)。

基于用之前定義的指標(biāo)所代表的輸入所提供的信息，模糊邏輯系統(tǒng)可以推論出上下文知識(shí)，它可以通過(guò)參數(shù)的自適應(yīng)來(lái)控制RDPSO的行為。其邏輯推理如圖3所示。

圖3　模糊自適應(yīng)系統(tǒng)控制RDPSO行為邏輯推理圖

4仿真試驗(yàn)

本節(jié)使用虛擬機(jī)器人進(jìn)行仿真，這樣可以對(duì)更大數(shù)量的機(jī)器人在更大的場(chǎng)地里的自適應(yīng)RDPSO行為進(jìn)行分析。試驗(yàn)在600 m×600 m模擬場(chǎng)地進(jìn)行，每次嘗試障礙都隨機(jī)防止?；鶞?zhǔn)方程F(x,y)定義為標(biāo)準(zhǔn)的高斯函數(shù)。

(4)

式中：x-y代表平面坐標(biāo)，m。

所以，機(jī)器人隊(duì)伍的目標(biāo)是最大化F (x, y)，也就是最小化原始基準(zhǔn)函數(shù)F (x, y)，機(jī)器人群族要尋找f (x, y)=1的最優(yōu)方案，而且要避免障礙和保證網(wǎng)絡(luò)連接。

測(cè)試組進(jìn)行100次測(cè)試和500次迭代，每次被設(shè)成機(jī)器人向量N={50,100,}。然后，一個(gè)初始的最小和最大的機(jī)器人群族的數(shù)量分別為2、5、8。迭代間的最大行走距離被設(shè)為0.750 m，也就是max|xn[t+1]-xn[t]|=0.750，機(jī)器人間最大通信距離設(shè)為dmax=15 m。

圖4描述了在50次試驗(yàn)中應(yīng)用了非自適應(yīng)和自適應(yīng)RDPSO算法，計(jì)算出的最優(yōu)方案在中值、首個(gè)和第三個(gè)四分位數(shù)的對(duì)于機(jī)器人N={50,100}的最終輸出。

通過(guò)對(duì)圖4的分析，可以清楚地知道給定的任務(wù)可以由任何數(shù)量≥25的機(jī)器人完成。事實(shí)上，除去機(jī)器人數(shù)量這個(gè)因數(shù)，大部分情況下，包括非自適應(yīng)和自適應(yīng)RDPSO都是收斂的。然而，非自適應(yīng)算法需要占用首個(gè)和1/4中值鍵間的更大的區(qū)域，尤其對(duì)于機(jī)器人數(shù)目巨大的情況。

圖4　利用非自適應(yīng)和自適應(yīng)RDPSO的群族表現(xiàn)

因?yàn)榄h(huán)境是連續(xù)不斷地變化的，對(duì)環(huán)境的最優(yōu)方案也是隨時(shí)間變化的。這要求RDPSO能在短期內(nèi)找到方案，而且能找到最優(yōu)方案的軌跡。非自適應(yīng)算法如常規(guī)的RDPSO，在動(dòng)態(tài)環(huán)境中通常會(huì)出現(xiàn)幾個(gè)錯(cuò)誤，因?yàn)樗鼈內(nèi)鄙僭趧?dòng)態(tài)改變環(huán)境中追蹤不平穩(wěn)的最優(yōu)方案的能力(如文獻(xiàn)[12-13])。

函數(shù)F(x,y)的動(dòng)作的A序列如圖5所示。

圖5　基于強(qiáng)制Duffing振蕩器的F(x,y)函數(shù)頂峰的平面運(yùn)動(dòng)。

混沌函數(shù)是最普遍和得到充分研究的方法—產(chǎn)生不穩(wěn)定函數(shù)(如logistic函數(shù)[14])。在這篇文獻(xiàn)里，采用一種基于強(qiáng)制杜芬振蕩器[15]的常規(guī)方法動(dòng)態(tài)地改變峰值位置。因此，函數(shù)F(x,y)定義為動(dòng)態(tài)時(shí)變高斯方程。

每個(gè)峰值的動(dòng)作可以通過(guò)元組{γ,ω,ε,Γ,Ω}配置。在元組里，γ控制阻尼的大小，ω控制復(fù)原力的大小，ε復(fù)原力的非線性量的大小，?？刂浦芷隍?qū)動(dòng)力的振幅，Ω控制周期驅(qū)動(dòng)力的頻率。盡管為了得到更不可預(yù)見的和混沌的行為，元組{γ,ω,ε,Γ,Ω}可能隨機(jī)定義，為了更好地理解實(shí)驗(yàn)結(jié)果，他們將被定義為常數(shù){0.1, 1, 0.25, 1, 0.5}。為了使表面平滑，應(yīng)用一個(gè)循環(huán)平均過(guò)濾器。

5結(jié)束語(yǔ)

本文提出RDPSO的延伸算法，具有基于上下文信息的自適應(yīng)能力。為使算法具有自適應(yīng)能力，把一個(gè)群族置于仿真環(huán)境中，以評(píng)估機(jī)器人障礙與通信等約束下的動(dòng)態(tài)表現(xiàn)?；谏舷挛牡亩攘勘挥米髂：到y(tǒng)的輸入，系統(tǒng)地適應(yīng)RDPSO算法。仿真試驗(yàn)結(jié)果表明，應(yīng)用了自適應(yīng)算法的RDPSO比普通版本的具有更好的收斂性。該算法使用上下文知識(shí)，允許對(duì)環(huán)境和任務(wù)的快速檢測(cè)，探索真實(shí)世界的特性的動(dòng)態(tài)信息，提高了機(jī)器人的感知能力。即使在動(dòng)態(tài)分布中，自適應(yīng)RDPSO依然可以比非自適應(yīng)RDPSO更容易找到最優(yōu)路徑。在日后的工作中，期望在數(shù)量更大的機(jī)器人群族里使用自適應(yīng)RDPSO，并將RDPSO與傳統(tǒng)類型的機(jī)器人群族算法做比對(duì)。

參考文獻(xiàn)

[1] James K,Russel E.A new optimizer using particle swarm theory[C]//Proceedings of the IEEE Sixth International Symposium on Micro Machine and Human Science,Nagoya,Japan,1995:39-43.

[2] Jim S,Robert M.A survey of animal foraging for directed, persistent search by rescue robotics[C]//Proceedings of the 2011 IEEE International Symposium on Safety,Security and Rescue Robotics,Kyoto,Japan,2011:314-320.

[3] Lino M,Urbano N,Almeida A.Particle swarm-based olfactory guided search Autonomous Robots,2006,20 (3):277-287.

[4] 曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社，2004:89-112.

[5] Maurice C,James K.The particle swarm—explosion,stability,and convergence in a multidimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.

[6] Kellchiro Y,Nobuhiro I,Genki U,et al.Particle swarm optimization: a numerical stability analysis and parameter adjustment based on swarm activity[J].IEEJ Transactions on Electrical and Electronic Engineering,2008(3):642-659.

[7] Yuhui Shi,Russel E.Fuzzy adaptive particle swarm optimization[C]//Proceedings of IEEE Computer,2001:101-106.

[8] Liu Hongbo,Abraham A.A fuzzy adaptive turbulent particle swarm optimization[J].International Journal of Innovative Computing and Applications,2007,1(1):39-47.

[9] 張立川，徐德民，劉明雍，等.基于移動(dòng)長(zhǎng)基線的多 AUV協(xié)同導(dǎo)航[J].機(jī)器人，2009，31(6)：581-585,593.

[10]Micheal S,Couceiro R,Rocha N M.Ferreira.Ensuring Ad Hoc connectivity in distributed search with Robotic Darwinian swarms[C]//Proceedings of the IEEE International Symposium on Safety,Security,and Rescue Robotics,SSRR2011,Kyoto,Japan,2011:284-289.

[11]Micheal S,Couceiro S,Fernando M L.Analysis and parameter adjustment of the RDPSO—towards an understanding of robotic network dynamic partitioning based on Darwin’s theory[J].International Mathematical Forum,2012,7(32)1587-1601.

[12]Aaron C,Gerry D.Adapting particle swarm optimization to dynamic environments[C]//Proceedings of the International Conference on Artificial Intelligence,Las Vegas,USA,2000:429-433.

[13]Xiaohui Cui,Thomas E.Distributed adaptive particle swarm optimizer in dynamic environment[C]//IEEE International Parallel and Distributed Processing Symposium,IPDPS’07,Long Beach,CA,2007: 1-7.

[14]Morrison R,Kenneth A.A test problem generator for non-stationary environments[C]//Proceedings of the 1999 Congress on Evolutionary Computation,CEC’99,Washington DC,USA,1999:786-793.

[15]Chin.A,Kang B.Chaotic motions of a Duffing oscillator subjected to combined parametric and quasiperiodic excitation[J].International Journal of Nonlinear Sciences and Numerical Simulation,2001,2(4):353-364.

中圖分類號(hào)：TP1

文獻(xiàn)標(biāo)志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201503021

修改稿收到日期：2014-06-23。

作者余志鵬(1981-)，男，2007年畢業(yè)于華南理工大學(xué)控制理論與控制工程專業(yè)，獲碩士學(xué)位，講師；主要從事機(jī)器人控制系統(tǒng)開發(fā)的研究。