基于梯度博弈的網(wǎng)絡化軟件優(yōu)化機制

舒 暢 李青山 王 璐 王子奇 計亞江

(西安電子科技大學計算機科學與技術學院 西安 710071)

(shuchang@stu.xidian.edu.cn)

隨著互聯(lián)網(wǎng)的普及和移動技術的發(fā)展，當前軟件技術的發(fā)展呈現(xiàn)出了明顯的網(wǎng)絡化趨勢，越來越多的軟件應用選擇將業(yè)務或服務拆分后布置在不同的硬件設施上，通過互聯(lián)網(wǎng)通信協(xié)同完成工作，以實現(xiàn)更多樣化的功能.這類以網(wǎng)絡為媒介，以信息或服務資源為元素，以元素間的協(xié)同與互操作為構造手段，所建立的軟件密集型混合系統(tǒng)被稱為網(wǎng)絡化軟件[1].《中國互聯(lián)網(wǎng)發(fā)展報告(2021)》顯示，2020年我國工業(yè)互聯(lián)網(wǎng)市場規(guī)模已超9 000億元，物聯(lián)網(wǎng)市場規(guī)模達1.7萬億元，網(wǎng)絡化軟件的研究和發(fā)展有著廣闊的前景.

近年來，互聯(lián)網(wǎng)應用規(guī)模擴展迅速，網(wǎng)絡化軟件在互聯(lián)網(wǎng)中的部署越來越復雜，節(jié)點故障、通信擁塞、激增的用戶請求等突發(fā)因素為軟件的平穩(wěn)運行帶來了巨大挑戰(zhàn)，導致軟件性能和服務質量的下降，造成重大的損失.例如，2019年6月，谷歌的云服務器出現(xiàn)約4 h的宕機故障，大量基于該服務的網(wǎng)站或應用服務加載緩慢、無法登錄，其中，大型視頻網(wǎng)站YouTube的全球觀看人數(shù)減少了10%；2021年3月，蘋果App Store，iCloud等服務出現(xiàn)大規(guī)模故障，大量用戶訪問相關服務緩慢或失敗.因此，網(wǎng)絡化軟件需要實現(xiàn)優(yōu)化調(diào)整功能，主動調(diào)節(jié)各類參數(shù)，以保障軟件的正常運行，防止性能下降，提高系統(tǒng)的穩(wěn)定性.

網(wǎng)絡化軟件部署在異構的聯(lián)網(wǎng)設備上，根據(jù)功能或服務范圍由數(shù)量不等的計算設備組成軟件節(jié)點，完成發(fā)送、匯集與處理數(shù)據(jù)的任務.軟件節(jié)點的大量部署使網(wǎng)絡化軟件產(chǎn)生了高度分布的特征.在此背景下，網(wǎng)絡化軟件的發(fā)展呈現(xiàn)出去中心化的趨勢，系統(tǒng)架構越發(fā)開放和平等，系統(tǒng)中每個節(jié)點高度自治，不具備強制性的中心控制[2].然而，由于網(wǎng)絡化軟件高度分布的特點，軟件節(jié)點之間存在的通信延遲阻礙了節(jié)點間的信息共享，導致各個節(jié)點在進行自主優(yōu)化調(diào)整時出現(xiàn)個體與集體信念的不一致，為網(wǎng)絡化軟件系統(tǒng)的優(yōu)化調(diào)整帶來了困難.

針對網(wǎng)絡化軟件性能優(yōu)化中存在的節(jié)點間信息交流問題，本文研究了一種基于多智能體博弈的分布式優(yōu)化框架，將智能體設置在不同的軟件節(jié)點上，各個智能體使用有限的信息估計系統(tǒng)狀態(tài)并做出決策對軟件的參數(shù)進行管理，實現(xiàn)軟件性能的優(yōu)化.此外，本文針對現(xiàn)有方法易發(fā)散、參數(shù)選取困難的問題提出了自適應步長機制和強制協(xié)調(diào)機制，根據(jù)各個智能體的估計誤差調(diào)整當前決策尋優(yōu)步長，防止由于智能體之間估計偏差過大帶來的發(fā)散問題，同時保證了方法的收斂速度.

1 相關工作

目前軟件在線優(yōu)化的研究主要集中于如何通過合理的資源分配和任務調(diào)度提高軟件的服務質量或降低資源消耗和運營成本.阿里巴巴的云服務器集群采用了集中式任務管理機制，在阿里巴巴的混部集群中，由Sigma和Fuxi兩種管理中心匯總各個服務器的運行信息并對進程合理調(diào)度以提升資源的利用率[3]；Sahni等人[4]提出了一種啟發(fā)式的云計算資源彈性伸縮方法，該方法通過資源提供歷史和在線的工作負載分析估計后續(xù)任務的資源需求，之后使用貪心算法給出一組最優(yōu)的資源配置，以更低的資源消耗和更高的資源利用率滿足軟件的服務質量需求；Chen等人[5]基于反饋控制實現(xiàn)了一種組合服務的自優(yōu)化機制，設置函數(shù)數(shù)值化計算當前的服務質量，根據(jù)計算結果使用比例積分微分控制器對影響服務質量的因素進行重要性排序，產(chǎn)生優(yōu)化調(diào)整的策略；Das等人[6]針對流處理系統(tǒng)的容錯和效率問題，提出了一種基于不動點迭代的控制算法，自適應地調(diào)整批處理作業(yè)的大小，使工作負載能夠適應系統(tǒng)當前的情況.現(xiàn)有研究以軟件控制的自動化和智能化為目的，但大多著眼于使用集中控制方法對軟件系統(tǒng)進行調(diào)控，然而，這種方法無法完全適用于愈發(fā)龐大、愈發(fā)復雜的網(wǎng)絡化軟件系統(tǒng).首先，在集中控制的情況下，中心控制節(jié)點的故障將會導致調(diào)控機制停擺，缺乏可靠性；其次，集中為所有軟件節(jié)點提供控制策略需要收集大量的節(jié)點信息并產(chǎn)生巨大的計算開銷，效率低下；最后，在部署或移除軟件節(jié)點時，需要為中心節(jié)點更新控制邏輯，難以應用于動態(tài)變化的大型系統(tǒng).

本文采用多智能體博弈的方法對網(wǎng)絡化軟件進行優(yōu)化，將智能體設置在不同的軟件節(jié)點上，實現(xiàn)分布式的優(yōu)化決策與控制，相關研究聚焦于智能體的收益函數(shù)的設計和博弈決策方法上.收益函數(shù)的設計很大程度影響了博弈優(yōu)化的收斂效果，為了保證系統(tǒng)能在多輪博弈后達到納什均衡，常見的做法是根據(jù)實際情況將收益函數(shù)設計成符合勢博弈(potential games)[7]和凸博弈(convex games)[8]等具有良好收斂性質的形式.Li等人[9]通過改造系統(tǒng)的全局目標函數(shù)作為各個智能體的收益函數(shù)，設計了一種使用非完全信息的勢博弈分布式優(yōu)化模型；Wu等人[10]為多智能體任務分配問題設計了一種勢博弈模型，該模型將各智能體的收益函數(shù)設置為任務收益的指數(shù)形式，保證重要的任務被優(yōu)先完成，此外，將實際需求與參與智能體數(shù)目之差作為指數(shù)，防止過多的智能體被分配于同一任務造成浪費.博弈決策的目的是如何讓智能體做出決策優(yōu)化自身收益函數(shù)的值，常見的決策方法有沿收益函數(shù)的梯度調(diào)整的梯度博弈(gradient-play)[11]、根據(jù)歷史博弈記錄計算最佳決策的虛擬博弈(fictitious play)[12]、根據(jù)概率分布選擇策略的對數(shù)線性學習(log-linear learning)[13]等.Ye等人[14]對梯度博弈進行了擴展，在收益函數(shù)中使用對所有智能體值的估計值計算梯度，使其能讓系統(tǒng)中的各個智能體在不了解全局信息的情況下收斂至納什均衡；Heinrich等人[15]使用強化學習過程尋找最優(yōu)近似代替虛擬博弈中的最優(yōu)策略選取，改善了此類方法在大規(guī)模的博弈場景中的表現(xiàn).

在分布式多智能體博弈中，智能體之間的信念沖突是導致博弈無法達到納什均衡的主要原因之一，本文采用多智能體一致性協(xié)議(consensus protocols)緩解系統(tǒng)中各個智能體之間的信念差異，該技術來源于自動化和控制理論領域，是一種通過智能體間信息交換實現(xiàn)信念趨同和協(xié)同合作的技術.Saber等人在文獻[16]中提出了多智能體一致性協(xié)議的基礎形式和收斂分析，并在文獻[17]中進一步分析了收斂速度與智能體網(wǎng)絡的連通度和網(wǎng)絡類型之間的關系；Xie等人[18]在基礎的一致性協(xié)議上增加了基于智能體當前狀態(tài)的反饋控制機制，該協(xié)議能在變化的網(wǎng)絡連接狀態(tài)下收斂；Zuo等人[19]根據(jù)不等式關系進一步改造了一致性協(xié)議，使其能在有外部干擾的情況下以任意初始狀態(tài)在有限時間內(nèi)收斂.

2 優(yōu)化模型

2.1 系統(tǒng)模型

為了便于讀者理解本文的優(yōu)化決策機制，首先給出本文的系統(tǒng)模型.本文系統(tǒng)模型的構建基于廣泛應用于自主計算領域的感知—分析—決策—執(zhí)行(monitor-analyze-plan-execute, MAPE)控制方法[20]，如圖1所示，MAPE循環(huán)包括4個主要階段：

1) 感知(monitor)階段.該階段收集系統(tǒng)信息，對系統(tǒng)參數(shù)和結構的變化情況進行監(jiān)控，并將變化數(shù)值化傳遞給分析階段.

2) 分析(analyze)階段.該階段根據(jù)感知階段收集的信息確定系統(tǒng)的當前狀態(tài)和變化趨勢.

3) 決策(plan)階段.該階段針對當前系統(tǒng)的狀態(tài)和問題產(chǎn)生調(diào)整策略，以保證系統(tǒng)的穩(wěn)定運行或優(yōu)化系統(tǒng)的性能.

4) 執(zhí)行(execute)階段.該階段根據(jù)決策階段產(chǎn)生的策略調(diào)整系統(tǒng)行為，在執(zhí)行階段結束后，將再次進入感知階段開啟下輪MAPE控制循環(huán).

Fig. 1 MAPE loop圖1 MAPE循環(huán)

本文的系統(tǒng)模型如圖2所示，在網(wǎng)絡化軟件系統(tǒng)中設置分析預測節(jié)點負責感知階段和分析階段的工作，收集節(jié)點信息，分析預測節(jié)點根據(jù)與軟件節(jié)點間的網(wǎng)絡延遲確定管理范圍，對分析范圍內(nèi)的軟件系統(tǒng)狀態(tài)建模并分析預測系統(tǒng)性能的變化情況，生成節(jié)點數(shù)據(jù)與該區(qū)域系統(tǒng)總體效益之間的函數(shù)[21].分析完成后，各個分析預測節(jié)點將結果分發(fā)給網(wǎng)絡中的軟件節(jié)點，部署在各個軟件節(jié)點上的智能體以此為依據(jù)對節(jié)點的參數(shù)進行調(diào)整，實現(xiàn)系統(tǒng)性能的整體優(yōu)化.

Fig. 2 System model of networked software圖2 網(wǎng)絡化軟件系統(tǒng)模型

在這個過程中，由于網(wǎng)絡化軟件系統(tǒng)的性能受各個軟件節(jié)點狀態(tài)的影響，分析預測節(jié)點得到的函數(shù)變量中包含多個軟件節(jié)點的參數(shù)，部署在軟件節(jié)點上的智能體需要擁有其他節(jié)點的信息才能做出優(yōu)化決策.然而，分布在各處的軟件節(jié)點雖然能夠通過網(wǎng)絡相互通信間接獲取全局的節(jié)點信息，但長距離通信的延遲和不穩(wěn)定會導致信息傳遞緩慢，進而影響優(yōu)化決策的效率，該問題會隨軟件部署的規(guī)模擴大而加深.因此本文讓每個節(jié)點通過不完全的節(jié)點信息，相互博弈做出決策，具體做法是根據(jù)每次優(yōu)化的最大時間限制和迭代次數(shù)上限計算出通信時延的閾值，各個節(jié)點選擇與自己通信穩(wěn)定且通信時延較符合閾值的節(jié)點建立連接，智能體使用不完全的節(jié)點信息做出決策來優(yōu)化軟件性能.

2.2 博弈模型

本文的主要研究內(nèi)容是通過分布在軟件節(jié)點上智能體間的博弈實現(xiàn)網(wǎng)絡化軟件優(yōu)化機制，一個博弈場景G描述為G={N,v,V,F,J}，下面分別介紹.

1)N={A1,A2,…,An}為網(wǎng)絡中的智能體集合，其中n為集合的大小，即網(wǎng)絡化軟件的節(jié)點數(shù)量.

2)v=(v1,v2,…,vn)，其中vi為各個智能體維護的取值(value)，取值可以代表節(jié)點的最大硬件負載、最大任務排隊量等參數(shù)，智能體通過調(diào)整自身的取值實現(xiàn)各類優(yōu)化決策.

3)V=V1×V2×…×Vn，其中Vi為各個智能體的取值空間(value space)，取值空間是對智能體取值的限制，對于每個智能體的值有vi∈Vi，即智能體只能在取值空間規(guī)定的范圍內(nèi)調(diào)整自身的取值.

4)F:V為全局效益函數(shù)，是一個關于智能體取值的函數(shù)，由所有分析預測節(jié)點根據(jù)系統(tǒng)的情況給出，用于衡量系統(tǒng)的整體性能.本文中的效益函數(shù)F的結果為系統(tǒng)功耗、響應時間等與軟件系統(tǒng)性能負相關的指標，系統(tǒng)的優(yōu)化目標等價于優(yōu)化問題：

(1)

5)J={J1,J2,…,Jn}為各個智能體的收益函數(shù)集合，其中Ji:V，收益函數(shù)由分析預測節(jié)點賦予智能體，是智能體進行決策的標準，各個智能體在多輪博弈中通過調(diào)整自身取值獲取更高的收益函數(shù)值，并最終讓整個系統(tǒng)達到納什均衡(Nash equilibrium),從而產(chǎn)生調(diào)整策略，納什均衡的定義如下.

在納什均衡下，網(wǎng)絡中所有的智能體都無法僅通過改變自身的取值使得自身的收益函數(shù)結果變得更好，當博弈到達納什均衡時，各個智能體的取值將趨于穩(wěn)定.通過合理地構造智能體的收益函數(shù)，可以讓博弈的納什均衡充分接近如式(1)所示的優(yōu)化問題的解.本文使用一種簡單的博弈構造方法，對于網(wǎng)絡中的所有智能體Ai，令

這種方式構造出的是一類具有良好特性的博弈：勢博弈(potential games).

則稱博弈G為勢博弈，Φ為G的勢函數(shù).

顯然，使用上文方法構造出的全局效益函數(shù)F是對應博弈的勢函數(shù).在勢博弈中，單個智能體的取值改變對其自身的收益函數(shù)的影響和對全局效益函數(shù)的影響相同，有限勢博弈一定存在納什均衡，這為本文的優(yōu)化決策設計提供了收斂保證.由于各個智能體不能完全掌握網(wǎng)絡中所有智能體的取值情況，所以無法直接計算收益函數(shù).為了解決這個問題，引入智能體的取值估計(estimation)[9]：e=(e1,e2,…,en)替代真實的取值計算收益函數(shù)，其中ei= (ei1,ei2,…,ein)，eij表示智能體Ai對智能體Aj取值的估計，用于替代智能體Ai可能無法得知的智能體Aj的取值vj.在第3節(jié)中將介紹如何讓取值估計在博弈迭代過程中接近各個智能體的真實取值，以使得這種決策方式是有效的.

3 網(wǎng)絡化軟件博弈優(yōu)化機制

3.1 基于多智能體一致性的梯度博弈

本文考慮連續(xù)博弈(continuous games)，即F和Ji均為連續(xù)函數(shù)的博弈決策問題，如帶寬控制等采用連續(xù)取值空間的優(yōu)化問題需要使用連續(xù)博弈解決，服務降級、CPU核心、成塊的內(nèi)存分配等離散目標則需要先轉換為連續(xù)的優(yōu)化問題.梯度博弈是一種常用的連續(xù)博弈決策方法[23]，在每輪博弈中，各個智能體將取值估計代入收益函數(shù)，沿自身取值的梯度方向對取值進行調(diào)整：

(2)

其中：vi(t)表示智能體Ai在第t輪迭代時的取值；εi>0，為每輪更新取值的步長；符號[·]+表示第t輪時梯度在智能體Ai可選取值變化集合上的投影，防止取值超出該節(jié)點可以選擇的范圍.對于第2節(jié)中構造的博弈G={N,v,V,F,J}，設F在V上具有凸性，則G能使用梯度博弈以合適的步長收斂至納什均衡[9,23]，大部分的軟件優(yōu)化問題滿足該條件或可轉化為滿足該條件的等價問題[24-25]，如果無法滿足該條件則無法使用此類方法求解納什均衡.與常規(guī)的梯度博弈不同，式(2)在更新取值時使用的不是真實的梯度，而是根據(jù)估計值ei計算出的虛擬梯度，顯然，如果在博弈迭代中智能體無法正確估計全局的取值情況，梯度博弈將由于錯誤的梯度而無法收斂至納什均衡.

為了讓智能體正確估計其余智能體的取值，基于一致性協(xié)議對各個智能體的估計值進行修正，使其接近系統(tǒng)中各個節(jié)點的真實狀態(tài).在每輪博弈的取值調(diào)整前，每個智能體向與其建立連接的智能體集合Ni發(fā)送自己的取值和估計信息，并在調(diào)整結束后利用這些信息：

1) 通過一致性協(xié)議[16]減少各個智能體之間的估計誤差，令

(3)

其中Ni為與Ai建立連接的智能體集合(包括Ai自身).

(4)

注意，雖然每個智能體能在博弈當中獲取一定的真實取值信息，但不能通過持續(xù)將其代入收益函數(shù)的方式計算梯度，因為這樣會破壞式(3)的信息交換，可能會引起算法失效.

3) 更新估計值

(5)

其中α1和α2為比例系數(shù)，0<α1<1，0<α2<1，α1和α2用于約束估計值的變化速度.與常規(guī)的一致性協(xié)議不同，以上方法中除了需要讓智能體與相鄰智能體的估計趨于一致外，還要讓估計值接近一組不斷變化的真實取值.

綜合第2節(jié)中的系統(tǒng)模型和本節(jié)的博弈機制，基于Li等人[9]和Ye等人[14]的工作，我們總結了基于多智能體一致性和梯度博弈的分布式優(yōu)化(distributed optimization based on consensus and gradient-play, DOCG)算法.

算法1.DOCG算法.

輸入：迭代次數(shù)上限l、各個智能體的初始取值vi(0)、梯度博弈步長εi、比例系數(shù)α1和α2；

輸出：更新完成后的各個智能體取值v′.

① for each AgentIinN

②ei(0)←v(0);/*通過網(wǎng)絡通信初始化各

個智能體的估計值*/

③ end for

④iter_count←0;

⑤ whileiter_count

⑥ for each AgentIinN

⑦getinfo();

/*從相鄰的智能體獲取信息*/

⑧gradient_play(ei(iter_count),εi);

/*使用估計值和梯度博弈更新取值*/

⑨estimation_update();/*基于相鄰智

能體的信息更新估計值*/

⑩ end for

顯然，智能體間到達納什均衡的充要條件為所有智能體的估計值等于其可獲得的真實取值，且在多輪迭代中不再變化.當智能體的估計值與相鄰智能體取值相等且穩(wěn)定時，根據(jù)梯度博弈的原理，任何智能體對取值做出的調(diào)整都會讓自身的收益函數(shù)結果變差，根據(jù)定義1，此時博弈已達到納什均衡；另一方面，假設存在智能體的估計值與相鄰智能體的估計或真實取值序列存在偏差，那么在接下來的迭代中該智能體仍會根據(jù)式(5)修正自身的估計值，此時智能體間并不是納什均衡狀態(tài).基于Ye等人[14]的分析，在效益函數(shù)滿足一定條件時，使用算法1控制的系統(tǒng)達到的納什均衡是Lyapunov穩(wěn)定的，軟件系統(tǒng)本質上也是一種控制系統(tǒng)[26]，但算法1中的梯度博弈的步長和估計修正中的比例系數(shù)很大程度上影響了方法的收斂能力.在3.2節(jié)和3.3節(jié)中，將探究如何設置和控制這2類參數(shù)以提升算法的收斂能力.

3.2 自適應梯度步長機制

在算法1中，取值更新和估計修正過程是相互影響的，過大的估計誤差會造成梯度方向的偏移，使取值越來越偏離應有的更新方向，同時取值的錯誤更新也會反作用于估計值的修正，進而造成惡性循環(huán)讓取值點“迷失”在高維曲面上無法到達對應納什均衡的取值點.對于更新步長ε=(εi)和比例系數(shù)α1，α2各存在一組范圍上限，當ε和α1，α2均在范圍限制之內(nèi)時，算法1能保證收斂至納什均衡，但這2類上限的嚴格計算都和全局效益函數(shù)F有關，且對于每個智能體，計算這2類上限的時間復雜度均在O(n2)以上[14].顯然通過計算確定這2種參數(shù)是不明智的，而為了保證方法收斂保守地選擇參數(shù)則會降低算法的效率.

對于算法1，假設比例系數(shù)符合收斂限制，暫時停止取值的更新(暫時令步長ε=0)并讓各個智能體以式(5)的方法修正估計值，各個智能體的估計值將在迭代中逐漸統(tǒng)一并收斂于真實的取值.這時使用式(2)計算的梯度將趨于真實的梯度，之后當估計誤差過大時再次停止更新取值并修正估計值，重復這個過程能讓各個智能體將取值調(diào)整至納什均衡的某個鄰域當中，但這種做法會大幅降低算法的效率.基于以上討論，我們提出一種隨迭代過程變化的步長選取方法，令

(6)

其中

為智能體估計值與相鄰智能體真實取值之間的誤差；εmax i為該智能體沿虛擬梯度更新的最大步長，當智能體對相鄰智能體的估計值沒有誤差時，可以以最大步長更新自身的取值；τi為衰減系數(shù)，0<τi<1，讓取值的迭代步長隨估計誤差的增大而減小，實現(xiàn)在誤差過大時減緩取值的更新速度.

可變步長可以防止上文中提到的“取值迷失”情況并為步長提供了更大的選擇空間，但同時也帶來了新的問題.在算法執(zhí)行后期各個智能體之間的估計值和取值差異將逐步收斂，此時可變步長也將趨于最大步長，如圖3所示，當最大步長過大時算法會在納什均衡點附近發(fā)生震蕩，這種現(xiàn)象會隨著最大步長的增加而變得越發(fā)嚴重.根據(jù)3.1節(jié)中關于算法1的納什均衡條件的討論，當震蕩現(xiàn)象發(fā)生時降低最大步長即可讓算法收斂，具體做法為：為式(3)的估計誤差設定范圍判斷其是否接近收斂狀態(tài)，在幾輪迭代后，若估計誤差接近算法卻沒有達到納什均衡，則逐步下調(diào)最大步長，該機制的具體執(zhí)行方式見3.4節(jié).

Fig. 3 Oscillation phenomenon圖3 震蕩現(xiàn)象

3.3 強制協(xié)調(diào)機制

3.2節(jié)中，我們在比例系數(shù)符合收斂條件的情況下討論了步長的設計與調(diào)整，然而，不當?shù)谋壤禂?shù)將導致估計值與真實取值之間的誤差越來越大，讓式(6)的可變步長逐漸趨于0，最終智能體的取值不再更新，算法呈現(xiàn)出如圖4所示的過早收斂現(xiàn)象.

Fig. 4 Premature convergence phenomenon圖4 過早收斂現(xiàn)象

為了防止因不當?shù)谋壤禂?shù)引起的算法過早收斂，我們?yōu)榛诳勺儾介L的算法1研究一種比例系數(shù)調(diào)整和誤差協(xié)調(diào)機制.類似于3.2節(jié)中的最大步長調(diào)整方法，為智能體的可變步長設置下限δε，當可變步長小于δε時，觸發(fā)強制協(xié)調(diào)：

1) 由于舊的比例系數(shù)無法有效地修正估計值，首先需要嘗試降低當前的比例系數(shù)，讓比例系數(shù)以某種方式降低，比例系數(shù)降低后，誤差的擴大速度將減慢，如果此時的比例系數(shù)仍會引起過早收斂，使用原先的判斷條件觸發(fā)強制協(xié)調(diào)需要更多的迭代輪數(shù)，需要更加嚴格地對誤差大小進行限制，合理地提高判斷誤差過大的可變步長下限δε；

2) 另一方面，觸發(fā)強制協(xié)調(diào)機制時各個智能體的估計誤差很大，考慮到使用式(5)的迭代方法修正誤差的效率，且調(diào)整后的比例系數(shù)可能仍不符合收斂條件，會繼續(xù)擴大誤差，因此在觸發(fā)強制協(xié)調(diào)時將各個智能體當前可獲得的取值信息賦值于其估計值，即讓

eij=vj,Aj∈Nj.

強制協(xié)調(diào)完成后，智能體繼續(xù)執(zhí)行算法直至發(fā)現(xiàn)誤差過大再次進行協(xié)調(diào)或達到納什均衡.強制協(xié)調(diào)的本質是限制智能體之間估計誤差的大小并在必要時修正比例系數(shù)和重啟算法，提高收斂速度.

3.4 決策算法

將3.2節(jié)中的自適應步長機制和強制協(xié)調(diào)機制綜合到算法1中，本文的網(wǎng)絡化軟件優(yōu)化決策機制可以總結為算法2.

算法2.DOCGAC(distributed optimization based on consensus and gradient-play with adaptive step size and coordination)算法.

輸入：迭代次數(shù)上限l、各個智能體的初始取值vi(0)、最大步長εmax i、衰減系數(shù)τi、初始比例系數(shù)α1和α2、判別震蕩的估計誤差范圍δerr、判別過早收斂的可變步長下限δε；

輸出：更新完成后的各個智能體取值v′.

① for each AgentIinN

②ei(0)←v(0);

③ end for

④iter_count←0;

⑤ whileiter_count

⑥ for each AgentIinN

⑦getinfo();

⑧εi←variable_step_size(ei(iter_count),

{vj(iter_count)},εmax i,τi) ;

/*可變步長*/

⑨gradient_play(vi(iter_count),

ei(iter_count),εi);

⑩estimation_update();/*更新估計值*/

算法2使用了按比例減小的方法搜索合適的參數(shù).在最大步長和比例系數(shù)的下調(diào)方面，只要讓它們進入收斂條件的范圍即可，保守的下調(diào)可能導致頻繁觸發(fā)調(diào)整機制，而過于激進的下調(diào)方式反而會讓參數(shù)變得過小影響方法的收斂速度，甚至引起類似于提前收斂的情況，按比例縮小是一種較為折中的選擇.另一方面，合理的初始值能夠減少參數(shù)下調(diào)觸發(fā)的次數(shù)，提高算法的收斂速度.對于最大步長，其合理的初始取值受網(wǎng)絡規(guī)模和效益函數(shù)的復雜程度影響，在實際使用中，由于系統(tǒng)在運行過程中會多次執(zhí)行優(yōu)化機制，因此可以根據(jù)同類型優(yōu)化問題處理時的歷史數(shù)據(jù)對初始值進行調(diào)整，如果智能體在連續(xù)的r輪迭代中都未觸發(fā)步長下調(diào)，則可以謹慎地提高初始值以提高算法的收斂速度，更新最大步長為

其中β為大于1的數(shù)，可以選用下調(diào)最大步長時使用乘數(shù)的倒數(shù)，反之，如果在1輪算法中需要多次下調(diào)步長，則需要在下次算法開始前降低初始值.智能體在執(zhí)行算法時記錄本次算法中觸發(fā)下調(diào)最大步長的次數(shù)c，令新的最大步長為

最大步長會在長期的優(yōu)化過程中趨于穩(wěn)定.對于比例系數(shù)α1，α1限制的是式(3)中基于一致性協(xié)議的估計修正速率，該值與智能體的相鄰智能體個數(shù)有關，相鄰智能體的個數(shù)越多，誤差的累積效應就越強，一種簡單的選取方法是讓每個智能體的初始比例系數(shù)α1與其鄰接智能體的個數(shù)成反比，如令

(7)

而α2限制的式(4)只和單個相鄰智能體的取值有關，其本質是估計值向取值的靠近速度，與梯度博弈中的步長類似，因此可讓其初始值與最大步長的初始值保持一致.

4 實驗分析

為了驗證方法的有效性，我們將在4.1節(jié)和4.2節(jié)對本團隊前期開發(fā)的網(wǎng)上商城系統(tǒng)[27]進行了仿真實驗，該軟件是典型的互聯(lián)網(wǎng)應用，通過集群節(jié)點協(xié)同為用戶提供服務，其整體性能受各個節(jié)點的狀態(tài)影響，適合使用本文的方法進行調(diào)控.我們基于團隊在軟件狀態(tài)分析方面的工作[21]分析了該系統(tǒng)某一時段的各個節(jié)點帶寬與總體響應延遲之間的關系，建立了模擬該系統(tǒng)的10個虛擬節(jié)點，以圖5所示的方式進行連接，通過本文提出的方法讓各個智能體調(diào)節(jié)軟件節(jié)點的帶寬，以系統(tǒng)響應時間的預測值為指標方法驗證有效性，初始帶寬的取值使用了分析時的日志記錄值.

Fig. 5 Connectivity of agents in our simulation圖5 本文仿真實驗智能體連接方式

4.1 機制觸發(fā)

在本節(jié)中，我們對3.2節(jié)和3.3節(jié)提出的2類機制觸發(fā)和效果分別進行了測試，以驗證它們的效果.

1) 自適應梯度步長機制的觸發(fā)

本文的自適應梯度步長機制分為可變步長和最大步長的調(diào)整過程，本節(jié)分別對完整的自適應梯度步長機制、只使用可變步長以及只使用最大步長下調(diào)的情況進行了實驗，實驗結果分別如圖6所示.本輪實驗中，各個智能體的最大步長εmax i均取0.3，衰減系數(shù)τi均取0.5，比例系數(shù)α1，α2均分別取0.2，0.4，其中，在只使用最大步長下調(diào)的情況下使用的最大步長為0.1.

Fig. 6 Triggering of adaptive step size mechanism圖6 自適應步長機制的觸發(fā)情況

從圖6中可以看出，如果不使用步長下調(diào)，算法會在即將到達納什均衡時由于過大的步長發(fā)生震蕩現(xiàn)象；如果不使用可變步長，算法雖然能在合適的步長下收斂至納什均衡，但在收斂過程中會受到估計誤差的影響，出現(xiàn)頻繁的震動，此時比例系數(shù)稍有不當就會讓估計值與真實值的誤差越來越大進而導致算法發(fā)散.

2) 強制協(xié)調(diào)機制

Fig. 7 Triggering of forced coordination mechanism圖7 強制協(xié)調(diào)機制的觸發(fā)情況

我們首先測試了在使用可變步長時強制協(xié)調(diào)機制的觸發(fā)情況，分別對使用和不使用強制協(xié)調(diào)下的方法迭代情況進行了實驗測試.令所有智能體的初始最大步長εmax i=0.2，衰減系數(shù)τi=0.5，比例系數(shù)α1的初始值按式(7)的方法選取，α2的初始值均取0.8，實驗結果如圖7(a)所示.在不使用強制協(xié)調(diào)的情況下，由于估計誤差過大可變步長歸零導致算法在迭代剛剛開始時就停止更新，而強制協(xié)調(diào)機制能夠對比例系數(shù)進行搜索并有效避免過早收斂現(xiàn)象.另一方面，不使用可變步長，在步長合適的情況下，使用強制協(xié)調(diào)機制也能實現(xiàn)對比例系數(shù)的搜索.如圖7(b)所示，將所有智能體的步長均固定為0.1，用于判斷估計誤差大小的最大步長設置為0.08(雖然不使用可變步長，但強制協(xié)調(diào)機制的觸發(fā)條件是該值的大小，本輪實驗中的可變步長僅用于判斷估計誤差大小，不用于計算取值更新)，算法在經(jīng)過幾次比例系數(shù)的下調(diào)后成功收斂到納什均衡，相同的參數(shù)選取下不使用強制協(xié)調(diào)機制算法會發(fā)散.

4.2 對比實驗

根據(jù)4.1節(jié)的討論，算法2主要在收斂速度、參數(shù)選取等方面對算法1進行了改進，我們分別使用算法1和算法2對本節(jié)開始時提到的優(yōu)化問題進行了處理，同時，為了進一步驗證本文方法相較于傳統(tǒng)方法的優(yōu)勢，我們選取了經(jīng)典的最佳響應(best response, BR)和虛擬博弈 (fictitious play, FP)[12]作為參照.BR，F(xiàn)P以及本文使用的梯度方法是機器博弈研究中3類常見的決策方法，當前該領域的研究大多是在這3類方法的基礎上改進而來，目前仍有很多相關的研究和討論，其中最主要的研究是通過近似值替代最佳值的方式克服大量數(shù)據(jù)帶來的求解問題[15,28-29]，在本文的實驗條件下近似值會影響求解精度和收斂輪數(shù)，此處使用精確的最佳值反映3種方法間的區(qū)別以及不完全信息帶來的影響.本輪實驗中，算法1的參數(shù)選?。簽榱朔乐拱l(fā)散，步長εi均使用0.05，比例系數(shù)α1，α2均分別設定為0.2，0.8；算法2的參數(shù)選?。撼跏甲畲蟛介Lεmax i均設置為表現(xiàn)較為平均的0.3，衰減系數(shù)τi均使用較為保守的0.5，比例系數(shù)α1的初始值使用式(7)的選取方法，α2的初始值均設置為0.8；BR和FP均使用估計值計算收益函數(shù)，為了確保能夠順利執(zhí)行，這2種算法的比例系數(shù)組合都選取為0.2和0.3.

Fig. 8 Convergence performance of algorithms圖8 各類算法的效果對比

實驗結果如圖8所示，可以看出算法1使用較為保守的參數(shù)平穩(wěn)地收斂到納什均衡，而算法2由于在執(zhí)行初期更新取值時使用了最大步長，各個智能體間的博弈導致預期結果發(fā)生了巨大的波動，但在接下來的幾輪博弈中在可變步長和強制協(xié)調(diào)機制的控制下，各個智能體放慢了更新幅度并修正了自身對其他智能體的估計，將取值更新重新拉回了正確的方向，最后比改進前的算法更快速地收斂到了納什均衡.BR由于各個智能體激進地追求自身的最佳收益，無法完全達成平衡；FP通過根據(jù)歷史平均采取最佳響應，穩(wěn)定地收斂到了平衡狀態(tài)，但收斂速度不如前2種方法.

4.3 復雜網(wǎng)絡實驗

為了驗證方法在復雜網(wǎng)絡中的效果，我們進行了更大規(guī)模的實驗，設置了1 000個模擬節(jié)點.由于可供使用的節(jié)點數(shù)據(jù)不足，我們模仿文獻[14]中的方法進行了數(shù)值實驗，在3種典型的網(wǎng)絡結構：隨機網(wǎng)絡、小世界網(wǎng)絡、無標度網(wǎng)絡上對算法2進行了測試.在隨機網(wǎng)絡中設置連邊概率p分別為0.1，0.2，0.4，0.8；在小世界網(wǎng)絡中，鄰邊數(shù)k分別取20，40，80，100，重連概率被固定為0.2；在無標度網(wǎng)絡中，每次加入的邊數(shù)m分別設置為10，20，40，50，每種網(wǎng)絡隨機生成后進行測試記錄結果，各重復20次取平均值，實驗結果如圖9所示.由圖9可知，在隨機網(wǎng)絡中，隨著智能體間的連邊增加，算法的收斂速度會大幅減慢，但不會引起發(fā)散.這與我們的設想相反，因為一致性協(xié)議修正估計值的速度會隨連邊的增加而加快[17]，且在全連接實驗中，算法的收斂表現(xiàn)非常好.引起這種情況的原因是復雜的網(wǎng)絡構成讓智能體間的估計相互影響，導致估計修正速度變慢，進而減慢了達到納什均衡的速度.而在小世界網(wǎng)絡和無標度網(wǎng)絡中，由于在局部的網(wǎng)絡結構中出現(xiàn)了近似于全連接的狀態(tài)，降低了該問題的影響，因此在這2種網(wǎng)絡中，連邊數(shù)量的增加對收斂性能的影響不大.網(wǎng)絡的復雜性會一定程度上降低算法的收斂效率，但不會導致算法失效.

Fig. 9 Experimental results of algorithm in complex networks圖9 復雜網(wǎng)絡的算法實驗結果

5 總結與展望

在本文中，我們針對網(wǎng)絡化軟件的優(yōu)化決策問題建立了系統(tǒng)模型，將現(xiàn)有的基于多智能體一致性的分布式梯度博弈方法研究總結為了DOCG算法，并提出了將其應用在網(wǎng)絡化軟件的優(yōu)化決策問題中的方法.此外，我們對該算法進行了改進，研究了能調(diào)節(jié)尋優(yōu)速度和自動搜索合適參數(shù)的自適應步長機制和強制協(xié)調(diào)機制，提出了DOCGAC算法，為軟件在連續(xù)工作中的持續(xù)參數(shù)優(yōu)化提供了一種解決方案.實驗結果表明，改進后的算法能更快地收斂至納什均衡，并且降低了方法對參數(shù)選取的要求，使此類算法能夠應用于網(wǎng)絡化軟件系統(tǒng)的優(yōu)化任務中.

我們的方法也存在一定的不足，與原算法相同，DOCGAC收斂到的納什均衡無法保證是對應優(yōu)化問題的全局最優(yōu)解.在未來的工作中，我們將探索如何讓此類方法的納什均衡更靠近理論最優(yōu)值，并在真實的大規(guī)模網(wǎng)絡化軟件中進一步測試和改進我們的方法.

作者貢獻聲明：舒暢提出核心方法，參與實驗框架的設計和實驗編程，并最終完成了論文的撰寫；李青山擬定研究方向，設計了具體的研究方案；王璐設計了實驗框架和方法，完善研究方案；王子奇負責實驗編程及論文撰寫；計亞江負責實驗數(shù)據(jù)收集和論文核定.