基于ZGS的大規模多智能體系統的分布式優化算法

夏海琪

（1.中科院上海微系統與信息技術研究所上海200050；2.上海科技大學上海201210）

網絡技術的蓬勃發展，智能電網[1]、通信網絡、神經網絡、無線傳感網絡[2]等等各類大規模的不同形態的網絡系統無不在人類的生活生產和發展中起著至關重要的用。而利用分布式優化技術解決這一類大規模多智能體系統網絡[3-4]的優化問題便是近年來在這個研究方向最熱門的主題之一。通過圖論的知識根據多智能體系統的實際情況確定網絡的拓撲結構，然后利用分布式優化算法將優化問題的數據或決策變量分布至網絡中，使單個節點根據自身掌握的信息對最優決策進行估計，并通過與相鄰節點間協作性的信息交互，不斷修正自身的決策變量，最終實現全網絡的優化問題。前幾年提出的當前熱門的分布式優化算法之一zero-gradient-sum（ZGS）算法[5-6]相比于傳統的基于梯度的坐標下降優化算法[7]、分布式對偶算法[8-10]、ADMM[11-13]等算法計算量更小，信息交互少，收斂效果好，使得它在大規模無線通信傳感器等類似多智能體網絡上有極大的應用前景。然而更快，更高效，通信量更少的分布式優化算法才更能適應當前大數據背景下的大規模多智能體網絡系統的發展。本文以此為出發現，結合ZGS算法思路設計了一個新的算法Accelerated-Zero-Gradient-Sum（AZGS）。相比于原有算法收斂效果更快，通信量更少，更加高效。以下正文利用非線性優化理論、圖論、分布式計算模型等理論對新算法更高效得解決多智能體系統的一致性[12-13]進行分析。

1 模型闡述

考慮由n個多智能體組成的網絡，通過特定拓撲中的無向連接，其網絡拓撲圖為G=(V，E(k))。其中：k∈N*={1，2，3，...}，代表不同的時刻；V={1，2，3，...，n}，表示網絡拓撲圖的節點集；E(k)={(i，j):i，j∈V，i≠j}，表示網絡拓撲圖的邊集，代表在k時刻節點i和節點j之間可以相互通信。因為是無向圖，所以(i，j)=(j，i)。而對于一個多智能體網絡系統，通常我們優化的目標可以表示為如下的優化問題：

F(x)=∑i∈Vfi(x)其中fi(x)表示拓撲網絡中各個節點的損失函數且都是強凸函數：?f(y)-?f(x)T(y-x)≥λ‖y-x‖2，?x，y∈RmX=[x1，x2，...，xn]，xi∈Rm為i節點的值，若對于 ?i，j∈{1，2，...，n}，i≠j有xi=xj，表示拓撲網絡中所有的節點i∈{1，2，...，n}信息達到一致，X*便是滿足全局一致，同時達到整個網絡損失和最小的最優解。我們的目標就是設計一種分布式的優化算法去求得這個值。

2 算法設計

在文獻[5]中提出的Gossip算法便是基于以ZGS算法為基礎提出的，它是一種解決分布式優化問題的新穎思路。它提出在網絡迭代更新的過程中始終滿足兩個條件：

算法一：

Step2：隨機喚醒一個節點i∈V，令其所其一鄰節點（可通信節點）為j；

Step3：把節點j的損失函數fj和當前節點值xj傳遞給節點i；

Step5：節點i把更新后的xi(k)傳遞給所有相鄰節點j；

Step6：對于j更新節點值xj←xi(k)；

Step7：重復Step2，直至收斂；

此算法是一種將一些經典的一致平均算法推廣到分布式凸優化問題的算法。在迭代過程中，各節點的Lagrangian函數梯度之和始終為零。通過使節點變量之間的差距逐漸縮小至零，各節點變量將收斂至問題的最優解。這類算法的收斂性分析主要利用函數的凸性派生出的Lyapunov函數。各節點還可以利用該函數來獨立決定執行更新和通信的時間點。它的優點是規避了常規優化算法迭代過程中的步長問題，而且能保證在具有時變拓撲結構的網絡中實現漸進收斂，甚至獲得收斂速度的保證。為了使得算法更加通用，如[14-16]是在此基礎上在節點喚醒過程中采用非均勻分布的形式，考慮到各個節點在整個網絡中所起到的作用不同賦予不同大小的權重。而本文則選擇從另外兩個不同方向在原有算法的基礎上進行革新。

現實網絡中，多智能體單次通信往往會傳遞許多數據，因此新算法把單個智能體的變量擴展到xi∈Rm，那么新算法的迭代條件變為：

也因為網絡的復雜性和數據維度的擴展，那么從更加節能和加快收斂的角度考慮對[6]中算法進行新的改進是必不可少的。首先是網絡在喚醒某個節點的后，同時與其相鄰的所有節點進行信息交互。主要在算法是在原有算法的基礎上把每次迭代的鄰節點j改為所有與節點i相鄰的節點集Ni；另外考慮信息交互重復的問題，引入狀態矩陣Zij，矩陣所有 元 素 初 始 值 為 1，同 時 ?i，j∈{1，2，...，n}，?k∈N*，Z(k)ij=Z(k)ji，當節點i被喚醒時，同時更新 ?j∈Ni，若Zij為1，則損失函數fj（僅初次傳遞需要）和當前節點值xj傳遞給節點i，同時更新Zij為0，否則不傳遞。另外，因為所有節點j∈Ni更新之后，對于每個節點j對應的節點w∈Nj，w≠i，w?Ni，更新Zjw為1；綜合上述，設計出新的優化算法流程如下：

算法二：

Step1：初始化各個節點：xi←x*i；

Step2：隨機喚醒一個節點i∈V，令其所其鄰節點（可通信節點）的集合為Ni；

Step3：每個節點j∈Ni，若Zij=1把損失函數fj和（僅初次傳遞需要）當前節點值xj傳遞給節點i，若Zij=0，則不傳遞，并更新狀態矩陣Z；

Step5：節點i把更新后的xi(k)傳遞給所有相鄰節點j∈Ni；

Step6：對于 ?j∈Ni更新節點值xj←xi(k)；

Step7：重復Step2，直至收斂；

3 算法收斂性分析

關于新算法的收斂性分析主要利用經典的李雅普諾夫穩定性方法[15]，定義李雅普諾夫候選函數為：

由于問題模型描述中已經定義fi(x):Rm→R的強凸性和連續可導性，我們有：

由式（5）和式（6）可以知道V(x(k))≥0，?k≥0；所以要證明新算法收斂，只需要證明：

利用算法最初的限定條件（3）以及李雅普諾夫候選函數的定義我們可以得出：

根據式（8）可知V(x(k))是非增函數。由此可知：

由原函數的強突性可得：

其中γ:[0，∞)m→[0，∞)，γ(0)=0 是連續嚴格遞增函數。其證明可參照[5]定理4。然后根據式（9），式（10）可得：

結合式（11）以及新算法step6得：

B={i∈V:‖xi(k1)‖≥‖xp(k1)‖}，那么當k>k1時，對于任意節點i∈A和任意節點j∈B，{i，j}≠u(k)這與網絡的連通性，不存在獨立節點相矛盾。故

從而當ε取很小的我時候，根據γ函數的定義可以得出式（7）成立，即：

實現全局最優以及整個多智能體網絡的一致性任務。

4 算法仿真實驗驗證

對于上述算法的仿真，實驗環境為matlab，網絡規模為20個節點，首先根據算法模型的通過程序隨機生成連通性網絡拓撲結構如圖1所示。

從圖1中可以看到所模擬的拓撲圖是根據定義的連通網絡，既沒有獨立節點。其中的線段表示智能體之間能否進行信息交互。線段的長短模擬智能體之間的距離，與實際環境多智能體通過局部無線通信進行信息交互的可行性受距離因素所影響相一致。

圖1 模擬多智能體網絡拓撲圖

然后通過文獻[5]中的算法的對圖1的多智能體網絡進行仿真，結果如圖2所示。

圖2 原算法仿真結果

可以看出在大約1 750次迭代之后，網絡一致性基本實現。新設計的算法的同樣在圖1的網絡中進行仿真，結果如圖3所示。

圖3 新算法仿真結果

通過圖2與圖3的對比可以清晰看到原算法在迭代1750次以上能讓網絡圖中的節點實現整體的一致性問題，而新算法在迭代320次以上就能實現很好的優化結果。另外，在仿真過程中引入Zij，看似并沒有減少多智能體之間的通信過程次數，甚至有所增加。然而不難發現及時增加的通信次數，所傳遞的僅僅是Zij的值（0或1），而相當一部分這樣的通信代替了原來需要傳遞的值xi∈Rm，在實際環境中m的值也往往比較大，那么進過新的信號傳遞方式在一定程度上增加了網絡的通信次數，從單次信號傳遞的能量上就節約了將近m倍，同時提升信息傳遞速度。以傳遞一個數值為一次消耗計算，那么改進后的算法在圖1這個模擬的多智能體網絡為例，隨著變量維度的增大于，其節省的計算消耗如圖4所示。

圖4 變量維度與耗能節約關系

從圖4中不難看出，變量維度m的增伴隨著更大比例的能耗節約。即實際的m值比較大的情況下，改進的信息交互方式能進一步實現更快更節能的目的。這也契合大數據爆發時代高效，節能綠色通信的發展趨勢。

5 結論

本次研究了基于ZGS算法方向的分布式優化算法。新提出的AZGS，改進節點信息的交互模式，結合李雅普諾夫方程，論證了新算法在通過分布式的方法解決了多智能體網絡的一致性問題的前提下。實現了速度更快更快，信息交互更加節能。并在matlab環境下實現仿真驗證。該結果有利于在實際多智能體通信網絡中通過更加高效節能的交互方式解決問題。另外之后的研究工作會在多智能體信息交互的安全性考慮進一步研究，以實現多智能體網絡更安全，更節能，更高效的綠色通信。

參考文獻：

[1]李俊雄，黎燦兵，曹一家，等.面向智能電網的互動式節能調度初探[J].電力系統自動化，2013，37（8）:20-25.

[2]崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展[J].計算機研究與發展，2015，42（1）:163-174.

[3]Barrat M Barthelemy，Vespignani A.Dynamical processes on complex networks[M].Cambridge University Press，2010.

[4]Ren W，Beard R W.Consensus seeking in multiagent systems under dynamically changing interaction topologies[J].IEEE Transactions on Automatic Control，2005，50（5）：655-661.

[5]Lu J，Tang C Y，Regier P R，et al.Gossip algorithms for convex consensus optimization over networks[J].IEEE Transactions on Automatic Control，2011，56（12）：2917-2923.

[6]Lu J，Tang C Y.Zero-gradient-sum algorithms for distributed convex optimization:The continuoustime case[J].IEEE Transactions on Automatic Control，2012，57（9）：2348-2354.

[7]Bezdek J C，Hathaway R J，Howard R E.Local convergence analysis of a grouped variable version of coordinate descent[J].Journal of Optimization theory and applications，2013，54（3）：471-477.

[8]Johansson B，Soldati P，Johansso M.Mathematical decomposition techniques for distributed crosslayeroptimization ofdata networks[C].IEEE Journal on Selected Areas in Communications，2006，24（8）：1535-1547.

[9]Lu J，Johansson M.Convergence analysis of approximate primal solutions in dual first-order methods[J].SIAM Journal on Optimization，2016，26（4）:2430-2467.

[10]Larsson T，Patriksson M，Stromberg A-B.Ergodic，primal convergence in dual subgradient schemes for convex programming[J].Mathematical Programming，2009，86（2）：283-312.

[11]曹茂.無線傳感器網絡下基于分布式凸定位問題算法研究[D].重慶：重慶師范大學，2014.

[12]林靜然，姜昌旭，利強，等.基于ADMM的分布式功率分配和接入控制聯合優化算法[J].電子科技大學學報，2016，45（5）:726-731.

[13]Boyd S，Parikh N，Chu E，et al.Distributed optimization and statisticallearning via the alternating direction method ofmultipliers[J].Foundations and Trends in Machine Learning，2011，3（1）：1-122.

[14]楊洪勇，張嗣瀛.離散時間系統的多智能體的一致性[J].控制與決策，2009，24（3）:413-416.

[15]謝光強，章云.多智能體系統協調控制一致性問題研究綜述倡[J].計算機應用研究，2011，28（6）:234-239.

[16]王長城，戚國慶，李銀伢，等.量化狀態信息下多智能體Gossip算法及分布式優化[J].電子與信息學報，2014（1）:128-134.

[17]俞輝，蹇繼貴，王永驥.多智能體時滯網絡的加權平均一致性[J].控制與決策，2007，22（5）:558-561.

[18]譚拂曉，關新平，劉德榮.非平衡拓撲結構的多智能體網絡系統一致性協議[J].控制理論與應用，2009，26（10）:1087-1092.

[19]潘歡.二階多智能體一致性算法研究[D].長沙:中南大學信息科學與工程學院，2012.