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

馬子鵬

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

0 前言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)粒子群算法流程

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

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

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

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

步驟4 對每個粒子的速度v 和位置x 按下式進行更新:

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

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

2 實例仿真

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

其中

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

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

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

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

圖5 重置目標(biāo)的箱子運動軌跡

3 結(jié)束語

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

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

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

［3］LIU Jiming．多智能體模型與實驗［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］張軍．計算智能［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］王云，王俊，韓偉．基于進化算法的多智能體合作學(xué)習(xí)［J］．山東大學(xué)學(xué)報，2010，40(6):8－11．

［11］韓偉，韓忠愿．基于黑板模型的的多智能體合作學(xué)習(xí)［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．