多智能體系統中子域適應度評估的合作協進化協作

張曉勇，彭軍，李哲琴

(中南大學 信息科學與工程學院，湖南 長沙，410083)

協作是多智能體系統中的1個關鍵問題，多智能體系統中的自主智能體要完成系統的目標必須進行有效的協作。智能體處在一個高度動態變化的環境中，狀態空間極大且難以準確預測，所以，難以預先為智能體設定完整的行為策略和控制參數。智能體必須具有自適應動態環境的能力，在運行過程中動態調整自身行為策略，實現多智能體系統更強的環境適應性和魯棒性，才能更好地完成系統的復雜任務。多智能體系統協進化算法是近年來進化理論發展的熱點，它為解決復雜系統動態自適應、機器學習等問題提供了1種新手段[1-6]。協進化算法基于生態學的種群協同理論，運用種群間的自動調節、自適應原理，是復雜動態變化環境中的智能體群體產生適應性協作行為的新途徑。對于協進化算法在多智能體系統協作的應用，目前已有一些成功的范例[7-9]。Uchibe等[10]用合作型協進化算法獲取足球機器人的協作行為；Luke等[11]用協進化方法訓練得到了1個完整的機器人足球隊；Puppala等[12]提出了 1種“共享記憶”方法，用于存儲協進化過程中成功合作的個體對，并將這種方法應用到2個房屋粉刷機器人的協調控制中，獲得了較好的效果。但是，這些方法都只適用于任務簡單的同構智能體系統中。在異構問題域中，Fukuda等[13]采用1種細菌感染協進化算法，解決智能機器人運動規劃的決策問題；Thomas等[14]對著名的“捕食者-獵物”問題進行了全面研究，并采用合作型協進化方法研究了由k個異類智能體組成的團隊如何獲取合作策略的問題。這些方法不適用于復雜、高維的問題域中。采用合作協進化算法對異構多智能體系統的協作行為策略進行優化、尋求最優協作策略時，存在如下問題：適應度函數難以建立；協作難以達到全局最優。為此，本文作者針對非結構化的環境和多樣化復雜任務的異構多智能體系統協作效用最大化問題，提出1種基于子域適應度評估的合作協進化協作算法，克服了合作協進化算法在解決復雜多智能體系統協作問題時存在的通信量過于繁重、適應度函數難以建立等問題。

1 合作協進化算法

合作協進化算法模擬自然界種群之間的協進化機制，對所有種群進行并行進化，優化種群之間的合作。在多智能體系統中采用合作協進化算法對智能體之間的行為進行自適應協作協調，定義如下。

(1)問題域：整個多智能體系統所要解決的問題或者需要完成的任務。

(2)種群：1個智能體所擁有的行為決策集。

(3)個體：1個狀態環境下通過規則推理生成的1個行為決策。

(4)適應度函數：對問題域中任務完成的優劣程度進行度量的函數。

合作協進化算法的核心部分是個體適應度的評估。個體的適應度是根據其與其他種群中個體一起完成任務的優劣通過適應度函數計算得到賦值的。對那些有利于種群間協調協作的行為賦予較高的適應度，而對于不利于協作的策略則賦予較低的適應度，使種群朝著相互協調適應的方向進化，產生全局協調協作行為。

2 子域適應度評估的合作協進化算法

2.1 問題域的劃分

在異構多智能體系統的實際問題中，不同種類的智能體完成的任務不同，對某智能體來說，其他類智能體的行為決策對其子任務的完成影響較小。因此，在評估該智能體行為決策的適應度時，若不從異構種群中選取代表個體參與評估，則可減少通信負擔。根據智能體的異構特征和整個系統的任務規劃，將問題域空間分解成相互影響較小、較易求解的子問題域，這樣，在子問題域進行合作協進化，將大大降低協進化算法中適應度評估函數的維數，簡化適應度函數的建立過程。異構多智能體系統的自適應協作問題描述如下。

定義1：問題域。問題域F由異構多智能體系統中所有的種群組成，能完成多智能體系統需要完成的總任務。按照動態任務規劃方法可以將總任務劃分成N個子任務，則問題域F可以表示為：

定義2：子問題域。子問題域Fi由M個同構種群構成，能完成問題域F總任務中的一部分(子任務)。其中，M表示子問題域Fi中的智能體個數。同構種群結構相同，行為功能相同并且聯系緊密，以完成同一子任務為目標，則子問題域Fi可以表示為：

復雜動態環境下的異構多智能體協作問題便可歸結為系統中所有異構智能體尋找最優合作策略來完成任務。

2.2 子問題域模型中適應度函數的設計

把復雜問題域劃分成子問題域后，如何將子問題域中合作協進化算法尋求的最優合作策略朝著全局優化方向發展成為1個需要解決的關鍵問題。問題域分解后子問題域中的個體適應度評估需要考慮3個因素：

(1)考慮其所在的子問題域的環境適應性；

(2)考慮其與所在的子問題域中其他種群中個體協調協作的表現；

(3)考慮其對來自其他子問題域中異構種群的環境適應性的影響。

由于子問題域內每個種群的感知范圍有限，只能獲得有限范圍內的局部狀態信息，對其他子問題域內的狀態信息未知。在子問題域中采用合作協進化算法，個體通過適應度函數計算得到的結果是不準確的，因為它只考慮了前面2個因素而沒顧及到全局，從而使得進化難以收斂于全局優化；因此，需要對子問題域模型中的適應度評估函數進行合理設計，使其能夠考慮其他子問題域的影響，以得到1個更準確的評估值。

矩陣法是環境影響綜合評價中的一種基礎方法和重要手段，廣泛應用于環境影響評價中。矩陣法是把各項活動和受影響的各項環境因子分別表示為矩陣的列與行，在兩者之間建立直接的因果關系，以表示哪些活動對哪些環境因子產生影響和影響的程度。子域適應度評估的合作協進化算法采用環境因子影響矩陣法，將其對來自其他子問題域中異構種群的環境適應性的影響映射到適應度函數中評估適應度，進行如下定義。

定義3：環境因子影響矩陣。假設任意一個子域中種群的個體對其他子域中種群的環境因子eq(q=1, …,C)產生影響，共有C個環境因子受到影響。矩陣HN×N(eq)為各個子域的環境因子eq影響矩陣；hiw(eq)表示在對第i個子域中種群的個體進行評估時，來自第w個子域中種群對其環境因子eq的影響，當i = w時，定義hiw(eq)= 0；當i≠w時，hiw(eq)根據實際問題域中各子域中的種群對其他子域的環境因子eq影響程度來定義。則HN×N(eq)可以表示成如下形式：

定義4：貢獻度。N個子域的貢獻度構成貢獻度矢量ZN，為：

定義5：適應度函數。在子問題域Fi中有M個同構種群，種群中的1個個體的適應度函數為：

協進化算法中問題域模型的功能是將需要評價的個體與從問題域的其他種群中選出的代表個體組合形成協作行為，應用在問題域模型中，通過維護隨時更新的狀態信息，采用適應度評估函數評價其適應度，并賦予該個體協作的適應度返回其種群。在改進后的算法中，不僅子問題域模型繼承了問題域模型的功能，子問題域模型之間還能通過信息通信交互獲得環境因子影響矩陣，采用改進的適應度函數評價個體適應度。

2.3 子域適應度評估的合作協進化算法

為了提高算法的效率，每個子問題域獨立進行協進化。子域適應度評估的合作協進化算法描述如下：

2.農業依托。聯合體必須由新型農業經營主體組成，目的是使成員發揮各自優勢，實現合作共贏，提高農業供給體系對市場需求變化的適應能力與持續發展能力。農村產業融合的根本目的在于，借由與第二、第三產業的交融，多渠道挖掘和利用農業在生產、休閑、生態、教育、保健等多種功能，為傳統農業注入新的活力，激發農業增收潛力。二者都強調了農業的基礎地位，都以增強農業競爭力為目標。

1t=0

2 對于每個子域Fi中的所有種群，進行如下操作：

3 對種群進行隨機初始化操作；

4 計算初始種群中每個個體的適應度；

5 結束

6 直到滿足終止條件之前，進行如下操作：

7t=t+1

9 基于適應度從上一代種群中選取新一代種群；

10 將遺傳算子(交叉、變異)應用到種群的個體中；

11 對種群的每個個體，評價其適應度；

12 結束

13 個體適應度評價方法：

14 從子域Fi中的其他種群中選擇代表個體；

15 對于種群中的每個需要評價的個體，進行如下操作：

16 將個體與子域Fi中的其他種群中選擇代表個體組合形成協作行為；

17 通過將這種協作行為應用到該子問題域中；

18 參考來自其他子問題域中的環境因子影響信息評價適應度；

20 結束

子域適應度評估的合作協進化算法協作模型如圖1所示。圖1中整個復雜的問題域有6個種群，分成2個子問題域，則6個種群分成2類，子問題域之間可并行協進化。為了計算種群3中個體的適應度，該個體必須與該子問題域中的其他種群(種群1、種群2)中的代表個體結合組成1個子問題的可能解決方案，然后，考慮對子問題域2中種群的環境適應性的影響來評估此子問題域方案的適應度，并將該個體的適應度反饋到該種群的進化中。

子域適應度評估的合作協進化算法通過復雜問題域按照動態任務分解方法劃分成子域，縮小了種群進化規模，簡化了適應度函數的建立過程；通過設計子域模型中的適應度評估函數，子問題域中的種群進化尋求最優合作策略朝著全局優化方向發展；同時，在評估某種群的個體適應度時需要的代表個體數量減少，使得種群間的通信量大量減少，減輕了系統通信負擔。

3 算法仿真和結果分析

為了驗證子域適應度評估合作協進化算法的有效性，在ECJ(Evolutionary Computation Journal)[15]系統上進行仿真。

3.1 算法仿真

根據 Potter等[8]的實驗結果，合作協進化算法對于典型的多元函數優化問題都能得到很高的優化效率，如 Rosenbrock，Rastrigin，Rotated Griewank和Rotated Expanded Scaffer多元函數，這些函數的共同特點是各個變量之間存在交聯關系。如對于Rosenbrock函數：f=(1-x1)2+100(x2-x12)2，按照合作協進化算法，選擇2個進化種群A與B，種群A中的每個個體對應于變量x1的不同取值，種群B中的每個個體對應于變量x2的不同取值，該函數在x1=x2=1時取全局最小值0。

依據異構復雜問題域模型，將 Rosenbrock，Rastrigin，Rotated Griewank，Rotated Expanded Scaffer多元函數組合起來，每個函數取2個自變量，構建如下異構問題域函數：

圖1 子域適應度評估的合作協進化算法協作模型Fig.1 Collaboration model based on cooperative co-evolution algorithm with sub-domain fitness evaluation

其中：x1，x2，y1，y2，z1，z2，x和y這 8 個自變量可以看成是8個智能體對應的種群中的個體，F為問題域函數，采用改進的算法來求解F函數的全局最優點0。可以證明：當x1和x2為 1，y1，y2，z1，z2，x和y均為0時，F=0。

3.2 仿真結果及分析

在ECJ系統上采用Rosenbrock函數作為問題域進行合作協進化算法仿真，然后，在此系統基礎上進行修改編程，將問題域擴展成異構問題域F，仿真子域適應度評估的合作協進化算法。為了使結果具有對比性，還進行了6個種群的子域適應度評估的合作協進化算法仿真。

3.2.1 算法時間代價分析

在仿真過程中，采用合作協進化算法，2個種群進化到75代時，函數值接近于0，耗時約2 s。采用子域適應度評估的合作協進化算法，基于6個種群同時進化1代耗時約1 s；當進化到23代時，函數值接近于0時共耗時約23 s；基于8個種群同時進化1代需要約3 s，當進化到8代時，函數值接近于0，共耗時約24 s。

從仿真時間可知：進化的種群越多，完成進化所需時間越多。其主要原因是：在ECJ系統中，依據改進后算法編程，采用的是單線程，程序在一個種群進化完成后，才調用下一種群的進化，而沒有實現改進后算法中所示種群之間并行協進化。在實際 MAS系統中，種群的進化是在種群內部并行進行；因此，若實現了改進后算法中所示的種群之間并行協進化，則基于6個種群同時進化1代約需0.17 s，基于8個種群同時進化1代需要約0.37 s。但是，采用合作協進化算法2個種群同時進化1代只需0.027 s。這是因為算法改進后，種群之間并行進化，子域模型之間進行通信來交互環境因子影響信息，適應度評估相對于原來的2個種群的合作協進化更復雜，增加了算法的時間。劃分的子問題域越多，所需時間便越多。

3.2.2 算法收斂性分析

采用合作協進化算法仿真基于2個種群的進化結果如圖2所示；圖3所示為采用子域適應度評估的合作協進化算法仿真基于8個種群的進化結果。

由圖2可知：2個種群合作協進化算法進化比較緩慢，進化到第75代后問題域的值收斂于0。由圖3可知：8個種群采用子域適應度評估的合作協進化算法進化較快。

圖2 合作協進化算法基于2個種群進化結果Fig.2 Results of cooperative co-evolution algorithm for 2 populations

圖3 子域適應度評估的合作協進化算法基于8個種群進化結果Fig.3 Results of cooperative co-evolution algorithm with sub-domain fitness evaluation for 8 populations

由仿真結果可知：當種群數量越多、問題域越復雜時，子域適應度評估的合作協進化算法越顯示其優越的收斂性；通過采用環境因子影響矩陣法設計適應度評估函數，能有效引導種群更快速地尋求全局最優合作策略；種群越多，則需進化到最優的代數越少，驗證了子域適應度評估的合作協進化算法的有效性。

4 結論

(1)根據問題域的異構特征和求解的需要，將問題域空間分解成子問題域，縮小了種群進化規模，簡化了適應度函數的建立過程，同時，在評估某種群的個體適應度時需要的個體數量減少，使得種群間的通信量大量減少，減輕了系統通信負擔。

(2)子問題域模型之間可以進行信息通信交互來獲得環境因子影響信息，通過設計子域模型中的適應度評估函數，采用環境因子影響矩陣法將其他子域影響信息映射到該子域中種群的個體適應度評估中，從全局引導種群之間的協作進化。

(3)在子問題域之間并行進行協進化時，子問題域之間需要交換環境因子影響信息，在一定程度上提高了算法的復雜度，但算法能夠大大減少復雜問題域的進化代數，加快協進化的收斂速度。

[1]Li X, Sol L K. Applications of decision and utility theory in Multi-agent systems[R]. Lincoln: University of Nebraska-Lincoln, 2004.

[2]范波, 潘泉, 張洪才. 一種基于分布式強化學習的多智能體協調方法[J]. 計算機仿真, 2005, 22(6): 115-117.FAN Bo, PAN Quan, ZHANG Hong-cai. A method for multi-agent coordination based on distributed reinforcement learning[J]. Computer Simulation, 2005, 22(6): 115-117.

[3]Huang J, Yang B, Liu D Y. A distributed Q-learning algorithm for multi-agent team coordination[C]//Proceedings of the Fourth International Conference on Machine Learning and Cybernetics.Guangzhou: IEEE Press, 2005: 108-109.

[4]Tehrani A M, Kamel M S, Khamis A M. Fuzzy reinforcement learning for embedded soccer agents in a multi-agent context[J].International Journal of Robotics and Automation, 2006, 21(2):110-119.

[5]Tan K C, Yang Y J, Goh C K. A distributed cooperative coevolutionary algorithm for multiobjective optimization[J].IEEE Transactions on Evolutionary Computation, 2006, 10 (5):527-549.

[6]Lu H, Yen G. Rank-density-based multiobjective genetic algorithm and benchmark test function study[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(4):325-343.

[7]羅杰, 段建民, 陳建新. 一種引入局部交互的群體協作行為協同進化機制[J]. 機器人, 2007, 29(4): 313-319.LUO Jie, DUAN Jian-min, CHEN Jian-xin. A mechanism of cooperative coevolution with local interaction for collective cooperation behaviors[J]. Robot, 2007, 29(4): 313-319.

[8]Potter M A, De Jong K A. Cooperative co-evolution: An architecture for evolving co-adapted subcomponents[J].Evolutionary Computation, 2000, 8(1): 1-29.

[9]Yang Z Y, Tang K, Yao X. Large scale evolutionary optimization using cooperative co-evolution[J]Information Sciences, 2008,178(15): 2985-2999.

[10]Uchibe E, Nakamura M, Asada M. Cooperative behavior acquisition in a multiple mobile robot environment by co-evolution[C]//Robocup-98: Robot Soccer World Cup II,Lecture Notes In Computer Science. London: Springer-Verlag,1999: 273-285.

[11]Luke S, Hohn C, Farris J, et al. Co-evolving soccer softbot team coordination with genetic programming[C]//RoboCup-97: Robot Soccer World Cup I, Lecture Notes in Computer Science.London: Springer-Verlag, 1998: 398-411.

[12]Puppala N, Sen S, Gordin M. Shared memory based cooperative co-evolution[C]//Proceedings of the IEEE International Conference on Evolutionary Computation. New Jersey: IEEE Press, 1998: 570-574.

[13]Fukuda T, Kubota N. Learning, adaptation and evolution of intelligence robotic system[C]//Proceedings of 1998 IEEE International Symposium on Computational Intelligence in Robotics and Automation. New Jersey: IEEE Press, 1998: 2-7.

[14]Thomas D, Haynes, Sen S. Co-adaptation in a team[J].International Journal of Computational Intelligence and Organizations, 1997, 1(4): 1-4.

[15]Luke S. A Java EC research system[EB/OL]. 2008-09.http://cs.gmu.edu/～eclab/projects/ecj/.