基于粒子群優(yōu)化的多智能體協(xié)作進(jìn)化方法

馬子鵬

(西安郵電大學(xué)自動(dòng)化學(xué)院，陜西西安710121)

0 前言

傳統(tǒng)的多智能體系統(tǒng)的控制方法主要是集中式和由上到下的分層式［1］，但這些方法違背了智能體的自適應(yīng)性和靈活性以及相對(duì)獨(dú)立性的思想，并且有過(guò)度依賴主控制器的致命缺陷。因此，分散的自治的多智能體如何利用集體行為相互協(xié)作高效地共同完成單個(gè)智能體難以完成的復(fù)雜任務(wù)，是研究設(shè)計(jì)多智能體系統(tǒng)的核心問(wèn)題之一。

群智能是人們對(duì)自然界的諸如螞蟻、鳥(niǎo)群覓食等群體性活動(dòng)進(jìn)行研究總結(jié)規(guī)律，得出的智能組合優(yōu)化算法?，F(xiàn)在研究較多的群智能算法有蟻群算法、遺傳算法、粒子群算法、免疫算法等。這些群體就像天然的多個(gè)智能體，自然而然地人們將群智能優(yōu)化方法應(yīng)用到多智能體的協(xié)作上。在多智能體系統(tǒng)中，可以在沒(méi)有全局規(guī)劃和命令的控制下通過(guò)個(gè)體間的局部感知、協(xié)作以及與環(huán)境的相互作用達(dá)到全局優(yōu)化的目的［2］。多智能體系統(tǒng)中個(gè)體的簡(jiǎn)單局部交互來(lái)產(chǎn)生復(fù)雜的、適應(yīng)的與目標(biāo)驅(qū)動(dòng)的群體行為，這個(gè)進(jìn)化的系統(tǒng)能夠在一個(gè)動(dòng)態(tài)環(huán)境中根據(jù)改變而改善適應(yīng)性［3］。本質(zhì)上，涉及到的問(wèn)題是環(huán)境的整體表示和搜索策略的優(yōu)化。加拿大的Jiming LIU 在文獻(xiàn)［3］用遺傳算法實(shí)現(xiàn)了多智能體的集體行為。

粒子群優(yōu)化算法 (Particle Swarm Optimization，PSO)由KENNDY 和EBERHART 等［4］于1995年提出，模擬生物活動(dòng)和社會(huì)心理學(xué)行為的全局隨機(jī)搜索算法，它的原理和機(jī)制簡(jiǎn)單，算法實(shí)現(xiàn)容易，具有魯棒性、分布并行性和全局尋優(yōu)的能力，是函數(shù)最優(yōu)化方面的高效方法之一。本文作者嘗試將該算法應(yīng)用到無(wú)限傳感網(wǎng)絡(luò)多智能體的協(xié)作中，給出了用該算法實(shí)現(xiàn)多智能體協(xié)作的方法和Matlab 仿真的結(jié)果。

1 粒子群算法實(shí)現(xiàn)多智能體協(xié)作

1.1 多智能體系統(tǒng)

多智能體系統(tǒng)通常是由多個(gè)自治的、分布式的、異構(gòu)的智能體所構(gòu)成的復(fù)雜系統(tǒng)。各智能體之間互相通信，彼此協(xié)調(diào)，并行地求解單個(gè)智能體難以解決的復(fù)雜問(wèn)題［5］，因此能有效地提高問(wèn)題求解的能力。一個(gè)具有協(xié)作進(jìn)化機(jī)制的多智能體結(jié)構(gòu)如圖1 所示。

圖1 帶有進(jìn)化機(jī)制的多智能體系統(tǒng)結(jié)構(gòu)

帶有協(xié)作進(jìn)化機(jī)制的多智能體系統(tǒng)是一個(gè)靠集體行為來(lái)完成一個(gè)復(fù)雜任務(wù)的系統(tǒng)，集體行為在執(zhí)行任務(wù)的過(guò)程中逐步進(jìn)化，直至完成任務(wù)。在求解問(wèn)題的過(guò)程中，智能體和環(huán)境之間通過(guò)局部感知連續(xù)獲得經(jīng)驗(yàn)，是一個(gè)在協(xié)作策略的作用下邊進(jìn)化學(xué)習(xí)邊執(zhí)行求解的過(guò)程，單個(gè)智能體能夠從外界獲取環(huán)境信息，可以獨(dú)立自主地思考、行動(dòng)來(lái)影響環(huán)境，智能體之間可以相互通信，實(shí)現(xiàn)分工協(xié)作。

1.2 粒子群算法實(shí)現(xiàn)多智能體協(xié)作進(jìn)化

粒子群優(yōu)化算法是通過(guò)模擬鳥(niǎo)群覓食行為而發(fā)展起來(lái)的一種基于群體協(xié)作的隨機(jī)搜索算法，用于解決優(yōu)化問(wèn)題。優(yōu)化問(wèn)題的每個(gè)解都是搜索空間中的一個(gè)粒子，多個(gè)粒子構(gòu)成粒子群。在搜索過(guò)程中，每個(gè)粒子要維護(hù)速度和位置兩個(gè)向量，位置向量決定被優(yōu)化的函數(shù)的適應(yīng)值，這個(gè)函數(shù)被稱為適應(yīng)度函數(shù)，每個(gè)粒子還有一個(gè)速度決定它們飛翔的方向和距離。另外，每個(gè)粒子要維護(hù)自己的局部歷史最優(yōu)位置，算法要維護(hù)整個(gè)全局的歷史最優(yōu)位置，然后粒子們就追隨著這兩個(gè)最優(yōu)粒子在解空間中搜索。由此可見(jiàn)，對(duì)于用粒子群算法實(shí)現(xiàn)多智能體協(xié)作進(jìn)化的關(guān)鍵涉及到粒子的位置、速度向量和適應(yīng)度函數(shù)在多智能體系統(tǒng)中如何表示和進(jìn)化。

(1)多智能體粒子的表示方法

在算法中粒子進(jìn)化時(shí)涉及到位置向量和速度向量，位置向量體現(xiàn)了粒子所代表的解在解空間的位置，適應(yīng)度函數(shù)用該向量來(lái)評(píng)估粒子的優(yōu)劣，是評(píng)估解質(zhì)量的基礎(chǔ)。速度向量表示解向量進(jìn)化的方向和速率，是單步位置的變化。在基本的函數(shù)優(yōu)化的粒子群算法中，位置是用一個(gè)函數(shù)的解向量表示，速度是和位置維數(shù)相同的向量。對(duì)于多智能體協(xié)作的粒子來(lái)說(shuō)，一個(gè)問(wèn)題的解由協(xié)作智能體的解共同組合而成，那粒子的位置也是由各個(gè)智能體的位置組合而成。假設(shè)有n 個(gè)智能體協(xié)作，每個(gè)智能體的位置的維數(shù)為m，則粒子的位置維數(shù)為m×n，結(jié)構(gòu)如圖2 所示。

圖2 多智能體粒子位置表示

(2)適應(yīng)度函數(shù)的設(shè)計(jì)

要求該函數(shù)能夠?qū)αＷ游恢玫膬?yōu)劣作出區(qū)分，對(duì)粒子的進(jìn)化應(yīng)該有好的導(dǎo)向性，從而提高粒子群的進(jìn)化能力。要結(jié)合具體問(wèn)題優(yōu)化目標(biāo)設(shè)計(jì)適應(yīng)度函數(shù)，一般應(yīng)滿足較優(yōu)的粒子位置適應(yīng)度函數(shù)的值較大。為了使函數(shù)有更好的區(qū)分性能可以對(duì)適應(yīng)性函數(shù)作一些修訂，比如說(shuō)線形變換、指數(shù)變換和乘冪變換等［6］。

(3)粒子群算法流程

當(dāng)設(shè)計(jì)好粒子位置和適應(yīng)度函數(shù)后就可以進(jìn)行粒子群算法的操作，流程如下:

步驟1 初始化每個(gè)粒子，包括它們的速度和位置，設(shè)置個(gè)體最優(yōu)位置pBest為當(dāng)前位置，全局最優(yōu)gBest為群體中最優(yōu)的個(gè)體最優(yōu)者。

步驟2 計(jì)算本代進(jìn)化中每個(gè)粒子位置的適應(yīng)度函數(shù)值。

步驟3 檢查粒子當(dāng)前的適應(yīng)度函數(shù)值，如果比其個(gè)體最優(yōu)值pBest大，則用該值更新pBest，如果該粒子的pBest比全局最優(yōu)gBest的值大，則用pBest更新gBest。

步驟4 對(duì)每個(gè)粒子的速度v 和位置x 按下式進(jìn)行更新:

式中:0 ＜ω ＜1 是慣量權(quán)重，c1和c2是加速系數(shù)，一般取2.0，rand1和rand2是隨機(jī)產(chǎn)生的［0，1］之間的數(shù)值。

步驟5 如果沒(méi)有達(dá)到結(jié)束條件，跳轉(zhuǎn)到步驟2繼續(xù)循環(huán)，否則結(jié)束。

2 實(shí)例仿真

實(shí)例用Matlab 對(duì)5 個(gè)智能體協(xié)作進(jìn)行路徑規(guī)劃，把箱子推到目的地進(jìn)行仿真。智能體推箱子采用文獻(xiàn)［3］提到的人工排斥力模型。智能體分布在箱子的附近產(chǎn)生排斥力使箱子移動(dòng)，該模型類似胡克定律，在距箱子一定鄰域內(nèi)距離越近產(chǎn)生的推力越大。箱子的移動(dòng)由多個(gè)智能體的排斥力的合力決定，即多個(gè)智能體協(xié)作完成箱子的移動(dòng)。該實(shí)例的適應(yīng)度函數(shù)由三部分組成，一是全局信息，表示多個(gè)智能體合力的大小;二是表示合力的方向和目標(biāo)方向的夾角，指出了箱子的運(yùn)動(dòng)方向多大程度上和目標(biāo)方向一致;三部分表示的是個(gè)體智能體的局部作用，即智能體相對(duì)箱子的空間距離和的倒數(shù)，指出了智能體和箱子接近的程度;具體定義如下:

其中

式中:α、β、γ 表示每部分的權(quán)重，sum(fi)表示多個(gè)智能體和合力，θ 表示運(yùn)動(dòng)方向和目標(biāo)方向的夾角，Di表示第i 個(gè)智能體和箱子的距離。

箱子的初始位置和目的位置在1 200 ×1 200 二維的范圍內(nèi)進(jìn)行設(shè)置。粒子群算法的粒子個(gè)數(shù)為50，每個(gè)粒子的位置由5 個(gè)智能體相對(duì)于箱子坐標(biāo)的空間位置向量構(gòu)成，是一個(gè)10 維的向量，初始值由隨機(jī)函數(shù)產(chǎn)生。圖3 和圖4 是分別采用遺傳算法和粒子群算法實(shí)現(xiàn)多智能體協(xié)作推箱子的運(yùn)動(dòng)軌跡圖?？梢钥吹竭z傳算法在進(jìn)化的開(kāi)始階段的軌跡是振蕩的、無(wú)序的，隨后曲線變得光滑最終到達(dá)目的地。相比較而言，粒子群算法在開(kāi)始階段振蕩較小，這是由于粒子群算法收斂速度快的原因，并且粒子群算法箱子運(yùn)行的軌跡偏離目標(biāo)的程度也比遺傳算法小得多。到達(dá)目標(biāo)執(zhí)行的迭代次數(shù)遺傳算法k =51，粒子群算法是k=42?？梢?jiàn)在本實(shí)例中，基于粒子群算法得多智能體協(xié)作比遺傳算法收斂速度快，并且運(yùn)動(dòng)的方向與目標(biāo)方向基本一致。另外，為了考察智能體對(duì)新目標(biāo)的適應(yīng)性，又進(jìn)行了目標(biāo)重置的實(shí)驗(yàn)，即當(dāng)箱子移動(dòng)到一個(gè)目的地后，重新設(shè)置一個(gè)目的地，讓智能體把箱子再推到新目的地。圖5 給出了重置目標(biāo)的箱子運(yùn)動(dòng)的軌跡，從圖4 可以看出，智能體通過(guò)42 次迭代到達(dá)第一次目的地，然后重置目的地后，迭代32 次到達(dá)了新目的地。這說(shuō)明，基于粒子群算法的多智能體協(xié)作進(jìn)化能夠適應(yīng)新任務(wù)的動(dòng)態(tài)變化。

圖3 遺傳算法箱子的軌跡圖

圖4 粒子群優(yōu)化箱子的移動(dòng)軌跡圖

圖5 重置目標(biāo)的箱子運(yùn)動(dòng)軌跡

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

通過(guò)研究多智能體協(xié)作進(jìn)化的機(jī)制和粒子群算法，提出了基于粒子群算法的多智能體協(xié)作進(jìn)化方法。通過(guò)仿真實(shí)驗(yàn)，并通過(guò)和遺傳算法進(jìn)化比較，結(jié)果顯示該算法能夠有效減少前期搜索的振蕩，加快收斂速度，驗(yàn)證了該算法的有效性。并且粒子群算法具有參數(shù)少、操作步驟簡(jiǎn)單的特點(diǎn)，是實(shí)現(xiàn)多智能體協(xié)作進(jìn)化行之有效的方法。

［1］王越超，談大龍．協(xié)作機(jī)器人學(xué)的研究現(xiàn)狀與發(fā)展［J］．機(jī)器人，1998，20(1):69－75．

［2］秦海力，耿麗娜，鄭志強(qiáng)．群智能算法應(yīng)用于MAS 系統(tǒng)協(xié)作的探討［J］．計(jì)算機(jī)仿真，2008，25(7):141－144．

［3］LIU Jiming．多智能體模型與實(shí)驗(yàn)［M］．北京:清華大學(xué)出版社，2003．

［4］EBERHART R C，KENNEDY J．A New Optimizer Using Particle Swarm Theory［C］．Proc．the Sixth Int．Symp．Micro Machine and Human Science，1995:39－43．

［5］GABER Heba，AMIN Safaa，SALEM Abdel-Badeeh M．A Combined Coordination Technique for Multi-Agent Path Planning［C］．10th International Conference on Intelligent Systems Design and Applications，2010:563－568．

［6］張軍．計(jì)算智能［M］．北京:清華大學(xué)出版社，2009．

［7］ZHONG Weicai，LIU Jing，XUE Mingzhi，et al．A Multiagent Genetic Algorithm for Global Numerical Optimization［J］．IEEE Trans on Systems，Man and Cybernetics，2004，34(2):1128－1141．

［8］BERNDT Jan Ole，HERZOG Otthein．Efficient Multiagent Coordination in Dynamic Environments［C］．IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology，2011:188－195．

［9］ZHANG Haopeng，HUI Qing．Multiagent Coordination Optimization:A Control-Theoretic Perspective of Swarm Intelligence Algorithms［C］．IEEE Congress on Evolutionary Computation，2013:3339－3346．

［10］王云，王俊，韓偉．基于進(jìn)化算法的多智能體合作學(xué)習(xí)［J］．山東大學(xué)學(xué)報(bào)，2010，40(6):8－11．

［11］韓偉，韓忠愿．基于黑板模型的的多智能體合作學(xué)習(xí)［J］．計(jì)算機(jī)工程，2007，33(22):42－44．

［12］LI Xun，MA Hongxu．Particle Swarm Optimization Based Multi-Robot Task Allocation Using Wireless Sensor Network［C］．Proceedings of the 2008 IEEE International Conference on Information and Automation，2008:1300－1303．