石美鳳，吳 俊，陳 媛

(重慶理工大學 計算機科學與工程學院， 重慶 400054)

0 引言

多智能體系統(tǒng)(multi-agent system，MAS)是由多個自治智能體(agent)組成的能夠相互作用的計算系統(tǒng)。在MAS中，Agent之間通過相互協(xié)作來完成共同目標，可以互相競爭使得自身利益最大化，或者互相合作使得總體利益最大化[1]。它是分布式人工智能的一個重要研究領域。

分布式約束優(yōu)化問題(distributed constraint optimization problems,DCOPs)[2-4]是MAS領域的一個關鍵問題。在DCOPs中，每一個Agent控制一個或者多個變量，并且相互協(xié)調(diào)、利用本地信息的交互為變量賦值以獲得全局最優(yōu)。簡而言之，DCOPs的求解目標是找到一組所有變量的賦值組合使所有變量之間的約束總和最小。DCOPs已成功地應用于實際生活中，如交通燈規(guī)劃[5]、傳感器網(wǎng)絡[6]、任務調(diào)度[7]和智能電網(wǎng)[8]等。

在DCOPs中，通常假設約束對變量雙方的代價是相同的，即這些約束是對稱的。然而在工程實際應用中，約束對變量雙方的代價常常是不同的。因此提出了非對稱分布式約束優(yōu)化問題(asymmetric distributed constraint optimization problems,ADCOPs)框架[9-11]。ADCOPs比DCOPs更加復雜，它根據(jù)每個Agent的私有偏好創(chuàng)建約束函數(shù)，約束的變量雙方擁有不同的代價。

根據(jù)能否保證找到最優(yōu)解，ADCOPs算法可以分為完備算法[12-14]與非完備算法[15-17]。完備算法能夠穩(wěn)定地找到最優(yōu)解，非完備算法能夠在很短時間內(nèi)找到次優(yōu)解。完備算法大致可分為通過遍歷解空間求解的搜索算法和通過消除約束關系求解的推理算法兩大類。但由于DCOPs是NP難問題，完備算法的計算復雜度將隨著問題規(guī)模的增大而呈指數(shù)級增長，這使得它在實際應用中受限。非完備算法的計算復雜度遠低于完備算法，所以非完備算法在大規(guī)模應用中更為普遍。

求解ADCOPs的非完備算法相關研究很少，基于決策機制的局部搜索算法屬于其中之一，因其邏輯簡單最受歡迎。目前求解ADCOPs的算法大部分是從DCOPs算法上擴充而來。ACLS[15]在DSA[18]算法基礎上，通過交換部分最佳響應的單面約束函數(shù)值來決定Agent的決策。MCS-MGM[15]則是基于MGM[19]算法，通過不斷更新彼此的約束函數(shù)和收益來驅使Agent決策。GCA-MGM[16]是對MCS-MGM的改進，放寬了更新約束函數(shù)的條件來保證算法的收斂。AsymACO[17]改進了傳統(tǒng)的蟻群優(yōu)化算法，通過優(yōu)化信息素機制來求解ADCOPs問題。

AsymACO算法的信息素機制利用了取值代價變化帶來的全局代價的變化，獲得了很好的成效。而局部搜索算法的研究卻未考慮局部代價的變化記錄，僅通過單輪次的取值變化來決策。因此，本文考慮到局部搜索算法，利用了指數(shù)加權移動平均(exponential weighted moving average,EWMA)去對取值變化引來的局部代價變化進行模擬，收集最近輪次的局部代價移動均值，并結合了AsymACO的種群搜索思想，提出了一種歷史局部代價的求解非對稱分布式約束優(yōu)化問題算法(historical local cost,HLC)，并將種群的交互引入來突破局部最優(yōu)，探索其他解空間。然后Agent根據(jù)模擬值來計算值域中每個值的被選取概率，根據(jù)該概率取值。借助于EWMA，在記錄局部代價變換歷史的同時，對存儲資源的需要基本沒有增加。

1 非對稱分布式約束優(yōu)化問題

1.1 ADCOPs

ADCOPs問題可以用四元組〈A,X,D,F〉進行表示：

A={a1,…,an}是智能體的集合，一個智能體可以控制一個或者多個變量；

X={x1,…,xm}是變量的集合；

D={d1,…,dm}是值域的集合，變量xi從值域di取值；

F={f1,…,fq}是約束代價函數(shù)的集合，約束fi∶Di1×…×Dik→R+∪{0}是變量之間的不同組合時所產(chǎn)生的非負代價的映射。在ADCOPs中，約束fi對雙方產(chǎn)生的代價是不同的。

通常來說，非對稱分布式約束優(yōu)化問題的求解目的是為所有變量賦值，使得所有智能體之間產(chǎn)生的約束代價之和最低。即：

ADCOPs中智能體與其他智能體相連接，該結構可以通過約束圖直觀地表示，如圖1所示。在約束圖中，圓形節(jié)點表示智能體控制的變量，節(jié)點之間的相連邊表示智能體之間存在約束關系，通過邊連接的智能體互為鄰居。

圖1 ADCOPs約束圖實例

表1是圖1中智能體之間的約束矩陣，展示了約束代價同變量取值的關系，變量取不同值時對應不同的約束代價。對ADCOPs而言，約束代價對變量雙方的代價是不同。如x1=1,x2=1，對x1的代價為5，對x2的代價為7。

表1 ADCOPs約束矩陣元素

1.2 局部搜索算法

局部搜索算法是求解ADCOPs問題的典型非完備算法，大多數(shù)局部搜索算法都是Agent同步進行的，在每一輪中主要考慮如何替換取值。Agent向約束圖中的鄰居發(fā)送包含其值或其他信息的消息，并接收來自鄰居的相同類型消息。然后Agent根據(jù)消息的內(nèi)容使用自身策略選擇一個新的值，再根據(jù)不同的替換規(guī)則決定是否替換舊值。在ACLS[15]中，當周圍鄰居取值發(fā)生變化時，Agent從自己值域中搜索出能夠降低局部代價的新值，以預先設定的概率替換舊值。但在MCS_MGM[15]中，只有所有鄰居中收益最大的Agent才能代替舊值。本文以ACLS為例對該框架進行說明。

首先，Agent在值域中隨機初始化一個值并發(fā)送給所有鄰居(第1～2行)，然后進入一個重復迭代的循環(huán)(第3～11行)，直到滿足終止條件。在循環(huán)過程中，Agent收集來自鄰居的值，并計算鄰居取值與自身取值的約束代價，將該代價發(fā)送給鄰居，然后它同樣收到鄰居發(fā)送過來的自身取值代價，從值域中選擇一個能夠減少自身代價的新值(第3～8行)。最后，Agent根據(jù)設置的概率 (第9～11行)決定選擇新值還是舊值。ACLS[15]算法框架如下：

Algorithm1: ACLS

For each agentxiexecutes:

1 value ← Choose_Random_Value()

2 send value to neighbors

3 while (no termination condition is met)

4 collect neighbors’ value

5 compute cost and send it to neighbors

6 collect neighbors’ cost

7 select a new value which reduces local cost most

8 Δ← the number of the local cost reduced by the new value

9 if Δ≥0&&random()≤pthen

10 assign the new value

11 send new value to neighbors

2 本文方法

局部搜索算法策略通常只考慮了連續(xù)2輪的信息差，而未對之前輪次的歷史記錄加以利用。對于ACLS，智能體每輪的取值取決于當前輪次同上輪次之間的局部代價差值，只依賴單一輪次鄰居值的變化，局部代價在該策略中呈非遞增規(guī)律，很容易陷入局部最優(yōu)。MCS_MGM遵循了ACLS的主要思想，只加入了鄰居之間的博弈機制來確定值的變化。不止如此，其他局部搜索算法也未涉及局部代價的動態(tài)變化及其Agent歷史取值記錄。

事實上對于局部搜索算法來說，改變Agent分配的目的通常是為了降低局部代價。當局部代價降低時，隨著輪次增加，全局代價也呈下降趨勢。各種改進的局部搜索算法都將精力集中在改善局部代價與全局代價的沖突：局部代價上升時，全局代價很可能降低。這些策略致力于使算法擺脫局部代價單調(diào)下降的局面，跳出局部最優(yōu)去尋求更高質量的全局解。而所有的這些改進算法都沒有考慮到局部代價的變化記錄。

全局代價等于所有局部代價之和，局部代價的變化深深影響全局代價。在局部搜索算法的初始輪次中，每個Agent的值與鄰居的值還沒有達到平衡狀態(tài)，因此不斷嘗試局部解。此時Agent的變化頻率比較快，取值范圍廣。而隨著輪次的增加，Agent與鄰居之間的交互已經(jīng)逐漸充分，取值變化頻率趨于平緩，取值范圍逐漸縮小。假設知道了每個值所對應的局部代價預估值，便可以選擇局部代價預估較低的取值來獲得較低的全局代價。很明顯，不同取值的局部代價變化規(guī)律是不同的，因此有必要為值域中所有值都維護一個局部代價預估值。在得到預估值后，Agent以此進行取值。所以在此基礎上，本文提出了一種基于歷史局部代價來求解ADCOPs的新算法HLC。

2.1 HLC

HLC可以分為2個階段：初始化階段和局部代價模擬階段。

HLC算法的框架如下：

Algorithm2: HLC

Function StartCycle:

1 foreachk∈C,p∈Pdo

2vk,p← randomly selects a value fromDi

3Vi←Vi∪vk,p

4 sends ValueMessage({i,Vi}) to neighbors

Function SelectValue:

5 clearVi

6 foreachk∈C,p∈Pdo

7vk,p←Selects a value by formula (4)

8Vi←Vi∪vk,p

9 sends ValueMessage({i,Vi}) to neighbors

For each agentxiexecutes:

10 Initialize Parameters:C,P,α,β,γ,ecy

11 foreachk∈Cdo

12 foreachdi∈Dido

14 StartCycle()

When received ValueMessage(m,recv_Vm):

15 update local view with (m,recv_Vm)

16 foreachk∈C,p∈Pdo

17 calculate cost by constraint matrix

18 send CostMessage() to neighborsm

When received CostMessage:

19 foreachk∈Cdo

20 foreachdi∈Dido

21 updateestk(di) by formula (2)

22 if (current_cycle%ecy=0) then

23 foreachk∈Cdo

24 foreachdi∈Dido

25 exchangeestk(di) by formula (3)

26 SelectValue()

初始化階段需要設置一些參數(shù)和選取初始種群。在迭代過程中，為了對解空間進行充分地搜索，本文引入了種群搜索的思想，使用個體來代表Agent的取值。HLC中有多個種群，每個種群內(nèi)部包含多個獨立的個體，個體攜帶不同的取值信息。種群帶有編號，種群中的個體也帶有編號，即Agent及其鄰居的同一編號的種群中同一編號的個體，組成一組局部解，產(chǎn)生該組局部代價。

假設有C個種群，則對于種群Ck來說，di的局部代價預估值應該被初始化為ai取di時，與鄰居所能產(chǎn)生的最大局部代價，初始化模擬值可由以下公式計算：

(1)

式中，estk(di)代表下一輪次 Agent取值為di時預計產(chǎn)生的局部代價，它通過對以往輪次的局部代價進行聯(lián)合模擬得到，并根據(jù)其變化進行維護更新。它受鄰居取值變化的影響，能夠反應出di的性能。初始化時，它代表di的最壞情形。其中k為種群的序號，m∈Ni是ai的鄰居。以圖1為例，x1的每個模擬值應該初始化為：

estk1(1)=estk2(1)=(5+2+4)*2=22

estk1(2)=estk2(2)=(8+5+5)*2=36

在初始化模擬值后，Agent執(zhí)行StartCycle函數(shù)來開始迭代。Agent構造一個空的賦值集合Vi來保存每輪的取值。假設每個種群中有P個個體。在第一輪中，種群k的個體p在域中隨機選擇一個初始值vk,p，然后將vk,p放入Vi中。所有個體都完成取值后，Agent將Vi發(fā)送給所有鄰居。

例如，在圖1中，假設有2個種群，每個種群中分別有2個個體。初始化后，每個Agent中的個體隨機分配為：

Vx1={k1∶[1,1],k2∶[1,2]}

Vx2={k1∶[2,1],k2∶[2,1]}

Vx3={k1∶[2,2],k2∶[1,2]}

Vx4={k1∶[1,2],k2∶[2,1]}

局部代價模擬階段是一個尋找解決方案的過程。在此階段，Agent計算局部代價，不斷更新模擬值，并且進行種群交互，以便更好地模擬局部代價且充分搜索該值的解空間。

當Agent接收到所有鄰居發(fā)送的值集合 后，HLC需要計算同鄰居值集合之間的約束。因為ADCOPs問題對于智能體之間的約束是不同的，Agent需要模擬局部代價而非單方面代價。計算鄰居將產(chǎn)生的約束之后，將該約束發(fā)送給鄰居，鄰居結合自身的代價，便能對局部代價進行模擬。

圖2的示例中，通過查表，x1收到的來自鄰居的約束代價為：

cost(x2,x1)={k1∶[8,7],k2∶[8,3]}

cost(x3,x1)={k1∶[1,1],k2∶[3,4]}

cost(x4,x1)={k1∶[3,2],k2∶[2,1]}

自身將產(chǎn)生的代價為

cost(x1,x2)={k1∶[1,5],k2∶[1,2]}

cost(x1,x3)={k1∶[1,1],k2∶[4,5]}

cost(x1,x4)={k1∶[2,4],k2∶[4,5]}

總的局部代價為：

lc(k1,p1)=8+1+3+1+1+2=16

lc(k1,p2)=7+1+2+5+1+4=20

lc(k2,p1)=8+3+2+1+4+4=22

lc(k2,p2)=3+4+1+2+5+5=20

當?shù)玫剿袀€體的局部代價時，Agent便可更新局部代價模擬值?？紤]到局部代價與迭代輪次之間的時間關系，采用EWMA對局部代價進行模擬。其更新方法定義為：

(2)

式中，βk是種群k的衰退率。假設對于k1和k2，有β={0.5,0.6}。x1的更新操作為：

更新之后，x1的模擬值分別為estk1(1)=19.5,estk1(2)=36(k1未曾隨機到value=2，所以不進行更新),estk2(1)=22,estk2(2)=28。

本文引入一個交換輪次，讓種群分享它們各自發(fā)現(xiàn)的模擬值，這能夠告訴那些探索的模擬值較差的種群，有更好的值和方向可以去探索。種群將向著更優(yōu)的模擬值前進，將自身模擬值同鄰居模擬值進行加權。HLC預先設定了交換間隔ecy，每隔ecy個輪次，Agent將交換獲得的est。交換操作定義為：

(3)

式中，γ為種群的學習率，它代表種群學習的快慢，使種群向最優(yōu)種群進化。如果假設γ=0.5，x1的交換可通過以下公式計算：

estk1(1)=19.5*0.5+19.5*0.5=19.5

estk1(2)=36*0.5+28*0.5=32

estk2(1)=22*0.5+19.5*0.5=20.75

estk2(2)=28*0.5+28*0.5=28

當模擬的局部代價被更新和交換后，Agent中的每個個體執(zhí)行新一輪的選值。由于每個種群中的模擬值不同，Agent需要為每個都計算不同的概率。預估值較低的應該擁有更高的被選概率，所有局部代價相加等于全局代價。所以使用了預估值的倒數(shù)計算概率。選擇di的概率定義為：

(4)

式中α是一個通過提高di被選擇概率而顯著影響解質量的參數(shù)，由于問題不同將有不同的局部代價范圍，所以預估值的范圍也不同，因此對不同的問題需要設置不同的α。如果假設α=2，x1中的k1的概率可以通過以下方法計算：

HLC將重復執(zhí)行模擬局部代價操作，直到滿足終止條件。在根據(jù)概率選擇新的值之后，Agent將vk,p放入Vi并再次將其發(fā)送給鄰居。此時，一個輪次周期完成，Agent重復模擬局部解階段，直到設置的輪次結束。

2.2 理論分析

在這一部分中，證明了EWMA的可行性、解的可行性和種群相互作用的優(yōu)越性。

引理1指數(shù)加權移動平均法可對局部代價很好地模擬。

證明EWMA是指值的加權系數(shù)隨時間呈指數(shù)式遞減，可以對時間序列的平均值進行模擬，越接近當前輪次，其加權系數(shù)越大。在HLC中，隨著輪次的增加，前期局部代價的影響逐漸減小，更集中在最近幾輪的局部代價上。EWMA可以改變衰變率來強調(diào)不同的輪次區(qū)間，其表達式為：

vt=β*vt-1+(1-β)*θt

(5)

當v0=0時，有：

vt=(1-β)*(θt+βθt-1+β2θt-2+…+βt-1θ1)

可知，各局部代價的權重系數(shù)呈指數(shù)遞減，越遠的輪次，其占比越低。HLC可以通過設置不同的β值，來控制衰減率，使算法側重于不同的周期。

定理1解的質量隨著消息輪數(shù)的增加而提高。

證明在低輪數(shù)的前r輪中，HLC處于縮減上限的階段。di的取值范圍為整個值域，estk(di)從其上限(最壞情況)開始逐漸減小。此時，EWMA正在估計di的全局性能及其對鄰居的適應度，讓更優(yōu)的值具有更大的概率。

在r到r+t輪中，HLC已經(jīng)進行了適當?shù)乃阉?，并且對每個estk(di)都有了足夠的預估。由于α的顯著增強，較低的擁有較高的概率，從而搜索范圍被縮小。在此搜索階段，算法在前r輪的基礎上繼續(xù)搜索，根據(jù)引理1，estk(di)降低了之前模擬值的影響，而更多地依賴于最近輪次。此時，EWMA實現(xiàn)了模擬局部代價產(chǎn)生預估值的功能，隨著搜索范圍的縮小，模擬精度也得到了提高。

經(jīng)過r+t輪后，HLC進入最后一個階段，即在小范圍內(nèi)搜索局部解來找到更好或最好的賦值。此時，estk(di)得到了很好的模擬，波動已經(jīng)平滑。取值概率的變化頻率平緩，取值范圍完成收斂，并且為每個estk(di)都生成了準確的模擬值。但是由于HLC引入了隨機取值輪次，di都是按概率被選取的，所以HLC仍然具有跳出局部最優(yōu)的能力。

定理2種群的相互作用有助提高解質量。

證明HLC引入的種群對解質量有很大幫助，其思想類似粒子群算法與混合蛙跳算法,不同之處在于每個種群同屬于發(fā)現(xiàn)者和探索者。由于HLC是根據(jù)概率取值的，種群引入的多個個體增加了對取值的嘗試次數(shù)，這有助于HLC去充分搜索解空間，并對當前設置的衰退率進行全面搜索。當種群在尋找自己的解后而陷入局部最優(yōu)解時，由于種群間引入的共享模擬值機制，種群仍有能力跳出自己的局部最優(yōu)，繼續(xù)向新方向探索。

2.3 復雜度分析

在每一輪迭代中，發(fā)送的消息僅包含個體取值信息與同鄰居產(chǎn)生的局部代價信息，因此消息空間復雜度為O(K*P)，其中K為種群數(shù)，P為個體數(shù)。

HLC的時間復雜度主要取決于值消息的計算和局部代價模擬值的更新。在計算值消息時，Agent只需遍歷模擬值矩陣來計算概率。因此，計算值消息的時間復雜度為O(K*max(P,N))，其中N為值域大小。

3 實驗驗證

為了驗證HLC算法的有效性，對ACLS[15]、GCA_MGM[16]和AsymACO[17]等算法與HLC在隨機 ADCOPs問題上進行了實驗評估。為了記錄迭代過程中的最優(yōu)解，采用了ALS平臺[20]。實驗將Agent數(shù)量設置為50和70，值域的大小設置為10，約束代價從[1,100]中隨機選取，并且考慮約束圖密度為0.1(稀疏)和0.6(稠密)。為了消除局部搜索算法隨機性帶來的差異，所有實驗結果選取了每類50個獨立問題的平均值，并且每個問題重復執(zhí)行了30次。

為了得到最優(yōu)的結果，首先在Agent數(shù)量為50的稀疏問題上進行了實驗。第一個實驗研究了解質量與參數(shù)(C,P,β,γ,ecy)之間的關系。根據(jù)表2中的結果，C和P與解質量密切相關。隨著C和P的增加，解質量也在提高，但相應的模擬時間也在增加?？紤]到復雜性和解質量的關系，最終選擇了比較平衡的C=4和P=24。對于β，它影響著種群尋找的輪次，在此為了增加種群的多樣性，使不同的種群關注不同的階段，最終為這4個種群分別選擇了β={0.9,0.8,0.7,0.6}，實際上，β的取值有很強的魯棒性，改變β取值，實驗結果變化不大。γ影響著種群間的學習率，根據(jù)表3的結果，取0.7時解質量最高。對于ecy，最好在陷入局部最優(yōu)時進行交換，可設為60～100。

表2 不同C和P取值的對比(cost/ms)

表3 不同y取值的對比

圖2—3為50個節(jié)點隨機ADCOPs的實驗結果。在1 000次迭代后，算法的變化趨勢趨于平緩。對于稀疏問題，HLC的解質量相比其他算法提高了2.4%～10.6%，對于稠密問題，解質量提高了1.4%～6.5%。觀察圖中HLC的下降曲線，發(fā)現(xiàn)存在多個曲折點，該彎曲是由于種群交互所致。HLC在算法的初始階段就能得到較好的解，而其他算法求解曲線下降更為緩慢。同局部搜索算法ACLS、GCA_MGM和MCS_MSM相比，HLC利用了歷史局部代價與種群，因此有更高的解質量；同基于種群的AsymACO相比，HLC利用了歷史局部代價與種群交互，因此產(chǎn)生了更好的解。由此可知，與對比算法相比，利用了歷史局部代價信息的HLC算法效果更優(yōu)。

圖2 ADCOPs實驗結果(Agent=50, p=0.1)

圖3 ADCOPs實驗結果(Agent=50, p=0.6)

圖4—5展示了在70個節(jié)點的隨機ADCOPs上的實驗結果。在1 000次迭代后，所有算法的解都不再變化。HLC的解質量在稀疏問題上提高了2.2%～3.7%，在稠密問題上提高了1.3%～5.8%。HLC和AsymACO算法的求解質量比普通局部搜索算法更高，但AsymACO算法很快陷入局部最優(yōu)無法跳出，HLC引入了種群間的交互來幫助跳出局部最優(yōu)，有著更高的解質量。

圖4 ADCOPs實驗結果(Agent=70, p=0.1)

圖5 ADCOPs實驗結果(Agent=70, p=0.6)

4 結論

在ADCOPs中，局部代價信息的變化記錄對局部搜索算法有著重要影響，HLC彌補了局部代價的歷史信息在局部搜索算法中未曾應用的空白。引入了EWMA和種群搜索策略，利用EWMA的時間特性和種群的交互特性模擬局部代價及其歷史信息，取得了良好的效果。實驗結果表明，HLC優(yōu)于最新的局部搜索算法和基于種群的算法。此外，HLC缺少對全局信息的利用，在未來的工作中可考慮引入偽樹等通信結構，將全局信息與局部信息相結合。