基于粒子群優化的多智能體協作進化方法

馬子鵬

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

0 前言

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

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

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

1 粒子群算法實現多智能體協作

1.1 多智能體系統

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

圖1 帶有進化機制的多智能體系統結構

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

1.2 粒子群算法實現多智能體協作進化

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

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

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

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

(2)適應度函數的設計

要求該函數能夠對粒子位置的優劣作出區分，對粒子的進化應該有好的導向性，從而提高粒子群的進化能力。要結合具體問題優化目標設計適應度函數，一般應滿足較優的粒子位置適應度函數的值較大。為了使函數有更好的區分性能可以對適應性函數作一些修訂，比如說線形變換、指數變換和乘冪變換等［6］。

(3)粒子群算法流程

當設計好粒子位置和適應度函數后就可以進行粒子群算法的操作，流程如下:

步驟1 初始化每個粒子，包括它們的速度和位置，設置個體最優位置pBest為當前位置，全局最優gBest為群體中最優的個體最優者。

步驟2 計算本代進化中每個粒子位置的適應度函數值。

步驟3 檢查粒子當前的適應度函數值，如果比其個體最優值pBest大，則用該值更新pBest，如果該粒子的pBest比全局最優gBest的值大，則用pBest更新gBest。

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

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

步驟5 如果沒有達到結束條件，跳轉到步驟2繼續循環，否則結束。

2 實例仿真

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

其中

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

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

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

圖4 粒子群優化箱子的移動軌跡圖

圖5 重置目標的箱子運動軌跡

3 結束語

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

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

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

［3］LIU Jiming．多智能體模型與實驗［M］．北京:清華大學出版社，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］．北京:清華大學出版社，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］．山東大學學報，2010，40(6):8－11．

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