多主體目標優化的動態合作博弈方法
2008-12-31 00:00:00王睿
計算機應用研究 2008年12期
(1.山東經濟學院 信息管理學院， 濟南 250014； 2.山東大學 計算機科學與技術學院， 濟南 250061)
摘 要：
通過多目標優化和動態合作博弈理論，定義了聯盟中多主體目標優化問題，提出了能夠適應動態環境的基于合作博弈的多主體目標優化模型。該模型的組成一方面能夠利用主體的協作能力，另一方面又能夠充分考慮動態聯盟的特征，適合大規模網絡中多主體協作，避免模型中主體理性和團體理性的沖突。基于所提出的多主體目標優化模型，設計了一種聯盟效用分配算法。仿真實驗表明，聯盟效用分配算法能夠使多主體根據最優共識原則，分配各方的合作效用，從而達到多贏的帕累托最優局面。
關鍵詞：多主體聯盟； 多目標優化； 動態合作博弈； 沙普利值
中圖分類號：TP301 文獻標志碼： A
文章編號：10013695(2008)12358304
Dynamiccooperativegame approach to multiagent objective optimization
WANG Rui1，2
(1.College of Information Management， Shandong Economic University， Jinan 250014， China;
2.College of Computer Science Technology， Shandong University， Jinan 250061， China)
Abstract:
With multiobjective optimization technology and dynamic cooperative game theory， this paper introduced a multiagent objective optimization model， which could adapt to dynamic environments. The model could make use of the cooperative ability of the multiagent well and could consider dynamic coalition characteristic fully. This model was suit for the large scale complex task agent cooperation and could avoid the conflict between individual object and group object. Designed a coalition utility allocation algorithm based on the multiagent objective optimization problem. The results of emulation test show that the coalition utility allocation algorithm can achieve a multiwin Paretooptimal outcome， which make the coalition tending to be more stable.
Key words：multiagent coalition; multiobjective optimization; dynamic cooperative game; Shapley value
0 引言
多主體合作求解是多主體系統(multiagent system，MAS)理論與技術研究的重點。多主體合作求解模型可以從主體的信念、意圖、規劃等心智狀態出發來研究多主體間的合作，如聯合意圖框架(joint intention)[1]、規劃團隊行為（planned team activity）[2]、共享規劃（shared plan）[3]和動態描述邏輯[4]等。這些方法著重改進和提高主體在合作過程中的自主性，而往往忽略主體的效益、性能和質量等因素。同時，多主體運行環境一般具有動態、復雜的因素，因此從根本上說，這些協作模型在具備較高技術指標的同時，缺乏處理多主體協作意外的機制及手段。Rosenschein[5]最早將博弈論引入多agent系統，其以效用函數最大化為目標。合作博弈[6]指的是每個局中人(在博弈論中，把參加競爭或合作的各方稱為局中人)為了實現總體利益最大化以及單個利益最大化，將其他局中人當做自己的合作伙伴，進行信息共享，簽訂協議，建立聯盟，最終達到共贏的目的。但是上述研究是基于靜態合作博奕理論，在實際應用中存在三個重要的問題：a)重復地進行一樣的博弈在實際的經濟合作中是罕見的；b)參與者必須作出具有約束力的協議；c)納什均衡缺乏一定的效率。現實中的主體合作是在動態復雜的環境下，隨機因素使合作博弈的復雜性增加，這種復雜決策情況稱之為動態合作博弈[7]。利益的分配是合作博弈的研究重點，但在合作博弈中，引用利益分配機制——沙普利值所指定的分配一般只有一次，不適合維持整個合作過程中的動態穩定性。
本文提出了一個多主體目標優化模型和多主體效用分配的動態合作博弈方法。本文所作的研究以開放環境下動態聯盟[8~10]作為多主體合作的有效方式，以聯盟內各成員分別發揮各自的優勢或核心能力，并按一定的方式共享利益、分擔風險為基本出發點，通過動態合作博弈理論實現聯盟主體隨著時間而轉變的決策互動；聯盟成員認同最初鎖定的最優共識原則，互惠互利，促使多主體效用的最優化分配以使合作高效穩定地運行，從而實現多主體目標的優化。
1 多主體目標優化問題的定義
多主體目標優化是指同時優化多個主體的目標，即在多主體合作中通過協同效應，發揮各方的所長和優勢，創造共贏的結果，甚至達到帕累托最優局面[11]。每個主體的偏好都可以用期望效用函數表示，即每個主體的目標就是通過策略最優化各自的效用函數。本文采用多主體動態合作博弈的方法實現每個主體效用的最優化分配。
11 單個主體的效用函數
定義1單個主體i的效用函數：
u(xi)=∫ T t0(g(xi(s))-
civi(s))ds+q(xi(T))；i∈[1，2，…，k] (1)
在有k個主體的合作中，主體i的效用函數u(xi)即為在時區[t0，T]的所有收益效用。其中：xi（s）表示主體i的即時狀態，可允許的狀態軌跡為{xi(s)，t0≤s≤T]}；主體i的瞬時效用為g(xi(s))-civi(s)，代表了在時間點s的主體i的凈效用；g(xi(s))反映主體i在時間點s的正效用；civi(s)是成本，即負效用；ci為常量；q(xi(T)）為主體對T時刻的期望效用，即根據主體在各方面的情況和潛力，計算出主體i在結束時間的潛在凈效用值。
12 多主體目標優化模型
參與組織的主體間具有長期目標合作關系的集合稱做多主體聯盟K。其管理功能包括成員管理與聯盟行為準則制定等。在聯盟型博弈中隱含的假設是存在一個在參與者之間可以自由轉移的交換媒介（貨幣）。這些博弈被稱為可轉移效用博弈(tugames)[12]。
定義2一個效用可轉移的聯盟〈K，u〉由一個有限的主體集合K和一個定義在集合K的效用函數u組成。效用函數u對集合K中的每一個主體都會有一個效用值，其值為一個實數。
由此可知，一個效用可轉移的聯盟〈K，u〉的有限的主體集合K中每個效用向量是xi，且每個主體i都有一個效用函數u(xi)。
性質1對于效用可轉移的聯盟S、T，為了保證每個主體都愿意組成總聯盟S∪T，一個效用可轉移的聯盟型博弈是超可加的，即
u(S∪T)≥u(S)+u(T)，S∩T=（2）
定義3在一個由k個主體組成的效用可轉移的聯盟〈K，u〉中，效用向量xi=(x1，x2，…，xk)(i∈K)是滿足團體理性的，當且僅當每個主體所分配的效用總和相等于總聯盟的效用，即
∑ i∈K u(xi)=u(K)(3)
式(3)稱之為團體理性。
定義4在一個有k個主體組成的效用可轉移的聯盟〈K，u〉中，效用向量xi=(x1，x2，…，xk)(i∈K)是滿足主體理性的，當且僅當每個主體所分配的效用都比不參加聯盟而獨立執行時高，即
u(xi)≥u({i}); i∈K(4)
式(4)稱之為主體理性。
在多主體目標優化問題中，一般說來要使每個目標函數同時達到各自最優解是不存在的。因此，多目標最優問題的解不是所有子目標的最佳解，而是帕累托最優解，即任何一個目標函數的值在不使其他目標函數值減弱的情況下已不可能進一步改進。
性質2在多主體目標優化過程中，主體的效用向量之間有三種關系：
u(α)≥u(β) (α占優)
u(β)≥u(α) (β占優)
u(α)≥u(β) and u(β)≥u(α) (α對于β無區別)
如圖1所示，兩個主體的效用函數u(x1)和u(x2)從源點開始，分別沿著x和y軸增長。對于x1，因為u1(B)＞u1(C)，同時對于x2，u2(B)＞u2(C)，所以在B點的解決方案好于C點，即在B點，x1、x2達到雙贏。圖中u1(B)＞u1(E)，同時u2(E)＞u2(B)，可知E點針對于B點的方案可以忽略。由圖1可知，B點的右上角區域是帕累托最優狀態，即達到這樣一種狀態，任何一種分配方法，其他主體的效用下降而使一個主體的效用更好的這種情況不存在。
基于上述說明，下面給出效用可轉移的聯盟〈K，u〉的多主體目標優化問題的定義。
定義5
max∑ i∈K u(xi)
s.t. ∑ i∈K u(xi)=u(K); u(xi)≥u({i}); i∈K(5)
其中：u(xi)表示參與聯盟〈K，u〉的主體i的效用函數。這個聯盟具有超可加性，聯盟成員都愿意最大化聯盟效用，并根據團體理性和主體理性分配聯盟的合作效用。
2 動態合作博弈方法求解
在以上描述的多主體優化模型中存在兩個優化問題，即多主體聯盟效用最大化和多主體效用分配最優化。動態合作博弈方法求解包括合作策略的求解和聯盟效用分配求解兩大部分。本文將根據團體理性和主體理性來確定合作控制集合和聯盟效用分配方案。
21 多主體聯盟的合作優化策略
當k個主體在組成聯盟〈K，u〉之后，參與的主體可以在合作過程中的各方面產生協同效應。設φi(s，xK(s))表示聯盟〈K，u〉對主體i狀態的控制函數，是關于主體i狀態和其他聯盟主體狀態的線性函數。例如在有三個服務主體的供應鏈的服務主體聯盟中，主體i可以分享其他另外兩個主體p、q在資源、設備和技術等方面發展的成果。
φi(s，xK(s))={γ[p，i]p[xi(s)+xp(s)]}2/2+{γ[q，i]q[xi(s)+xq(s)]}2/2(6)
其中：γ[p，i]p、γ[q，i]q分別為主體p、q對主體i狀態的影響程度系數。
定義6聯盟〈K，u〉的最優合作控制集合
φK(s，xK(s))=[φ1(s，xK(s))，φ2(s，xK(s))，…，
φk(s，xK(s))](7)
聯盟〈K，u〉中的每個主體將保證聯盟的最優合作控制，為最大化聯盟的合作效用提供了最優解法，相應的博弈的最優狀態取決于服務主體狀態在最優合作控制下的每一個時間點的發展變化。聯盟的效用在多主體共同合作下，將隨著時間的進展而轉變。在聯盟中，每個主體都愿意最大化聯盟效用，同時采用特定機制分配聯盟效用，認同最初鎖定的最優共識原則。由于效用可轉移，根據團體理性，參與聯盟的多主體共同決定合作方案。在合作計劃下，k個主體聯手最大化聯盟效用等于k個主體的合作效用之和。
定義7從時間點t0開始，在k個主體協作效用下，聯盟效用為
∑ i∈K ∫ T t0(g(xi(s))-civi(s))ds+∑ i∈K q(xi(T)) (8)
22 多主體的聯盟效用分配算法
Shapley值[13]方法是一種廣泛應用的分配機制，不僅符合團體理性和主體理性，并且Shapley是必定存在和惟一的。此外，Shapley值易于計算，比其他合作解法，如核(core) 、核仁、穩定集(stable sets) 和談判集更為理想。
k個主體的合作計劃中，所有的主體都在保證最大化聯盟整體利益的前提下，按照Shapley值分配聯盟的合作效用，達到多主體目標的最優化。
主體i在時間點τ∈[t0，T]可以從聯盟中獲得的效用為
v(τ)i(τ，xτ*N)=∑ KN [(k-1)!(n-k)!/n!][C(τ)K(τ，xτ*K)-
C(τ)K(τ，xτ*K\\i)]; i∈N(9)
其中：k、n表示聯盟K中的主體數和系統工作域N中的主體數;K\\i表示從聯盟K中排除主體i;(k-1)!(n-k)!/n!表示加權因子；C(τ)K(τ，xτ*K)表示聯盟K在時間點τ的價值函數，C(τ)K(τ，xτ*K)-C(τ)K(τ，xτ*K\\i)是參與者主體i對聯盟的邊際效用；v(τ)i(τ，xτ*K)可以表示為參與聯盟〈K，u〉主體i在時間為τ的終點效用。
為了保證以Shapley值分配合作效用在沿著博弈的最優軌跡的每時每刻都有效，需要進一步計算每一個時間點τ∈[t0，T]的協調補償Bi(τ)，如
算法1計算動態Shapley值解——聯盟效用分配算法（CUA）
begin
定義多主體目標優化問題max∑ i∈K u(xi)；
for all i∈K do
end
所有主體得到的補償的總和都必須等于所有主體在總聯盟K中采用最優合作控制時的瞬時效用的總和。引入協調補償的實質是為了實現動態平穩的合作方案。在時間不間斷的動態環境下的聯盟過程實際上是多主體的動態合作博弈過程，在每時每刻分發給每個聯盟主體的補償可以協調整個聯盟博弈狀態進展而為每個主體效用帶來的種種影響， 使聯盟各方按照最優共識原則得到合作效用，從而達到多贏的帕累托最優局面。
3 實驗結果及性能分析
本文方法作為遷移工作流研究的一部分[14，15]，已在本實驗室研制的移動協同服務平臺上進行驗證。與傳統的工作流模型不同，遷移工作流是一個或多個遷移實例在不同的工作位置之間不斷遷移并就地利用工作流服務完成任務的過程，因此，遷移工作流研究所要解決的關鍵問題之一是如何有效地組織遷移實例的工作位置。單個工作位置的能力和資源是有限的，因此需要多個工作位置協作來共同完成工作流目標。
簡化的實驗系統結構如圖2所示。本研究把所有服務組織的停靠站服務器稱做遷移實例的遷移域，因此，整個工作流執行是跨機構的，而多服務主體系統又把整個遷移域變成一個動態的實體。當遷移工作流管理機發現遷移域中不存在一個單獨的服務主體能夠滿足遷移實例的服務請求，或者遷移實例要求通過服務協作來完成遷移工作流目標時，或者遷移工作流管理機發現通過服務聯盟可高效實現遷移工作流目標時，服務主體聯盟過程開始。
31 應用實例的背景
供應鏈集成的最高層次是企業間的戰略協作問題，當企業以動態聯盟的形式加入供應鏈時，即展開了合作對策的過程，企業之間通過一種協商機制，謀求一種雙贏的目標。目前關于供應鏈管理（集成化、敏捷化供應鏈）的研究思路是將集成供應鏈管理系統的內在機制視為由相互協作的智能代理模塊組成的網絡，每個代理模塊實現供應鏈的一項或幾項功能，每個代理模塊又與其他代理模塊協調運作。
物流服務供應鏈是隨著物流服務產業的不斷發展而形成的，它是指以物流服務集成商為核心，以功能型物流服務提供商→物流服務集成商→客戶為基本結構，通過提供柔性化的物流服務保證產品供應鏈的物流運作的一種新型供應鏈。物流服務供應鏈本質上是一種以能力合作為基礎的供應鏈，其運行的前提是供應鏈內企業間的利益的合理分配。因此，研究物流服務供應鏈能力合作的動機、協調策略以及合理有效的分配方式，對于提高整個物流服務供應鏈運營績效不僅具有積極的理論意義，也具有良好的現實意義。
32 應用實例的數據假定與計算
為簡化例子與實際應用相符合，設物流服務供應鏈有三方物流服務提供商A、B、C。若各物流服務提供商獨自運作，則每個物流服務提供商每年僅能獲利10萬元;若A、B 合作，共可獲利30萬元，A、C 合作共可獲利50萬元，B、C 合作共可獲利40萬元；三個企業合作共可獲利90萬元。現在研究三企業合作時應如何合理分配90萬元的利益。
在表1中，C(K)是A企業參加供應鏈合作的效用；C(K\\i)為沒有A企業參加供應鏈聯盟的效用，C(K)-C(K\\i)為A企業對于供應鏈聯盟的效用；|K|為參與聯盟的企業數；v(T)A(T，xT*N)表示A企業對參加的供應鏈聯盟的加權平均值，加權因子取決于供應鏈聯盟的企業數。由表1值，A的終點效用的Shapley值為1/3+1/3+2/3+5/3=3，A的最終分配的效用是3+(7/9+2/9-1/9-5/9)=333。同理，B的最終分配的效用是233，C的最終分配效用是334。
33 結果的比較與分析
圖3反映了A、B、C三個服務主體聯盟成員在各自獨立、兩兩合作以及三者聯盟的效用情況。由圖3可知在保證聯盟效用最大化的同時，三個服務主體A、B、C從聯盟中分配的效用大于獨立執行時的效用。
服務主體A參加合作與獨自運作的效用對比關系可以從圖4看出，一個成功的合作安排必須滿足主體理性，并且沿著博弈的最優狀態，在每時每刻主體理性都得以維持。因此多服務主體能夠較好地遵守最優共識原則，有效地避免了某個服務主體脫離聯盟的行為。
再將聯盟效用分配算法與文獻[16]針對供應鏈模型提出的兩階段分配算法進行適應性比較，實驗結果如圖5所示。圖5表明，聯盟效用分配算法在適應動態環境方面比兩階段分配算法好。這是因為聯盟效用分配算法在根據最優共識原則分配整體的合作效用時，每位聯盟的參與者在每時每刻收到的補償將保證博弈的最優狀態。而兩階段分配算法中， 由于在一段時間內效用的分配是不變的，聯盟的參與者都選擇最高的效用，這將造成部分參與者不滿而退出聯盟，不能使合作圓滿結束。
4 結束語
本文論述了如何利用動態合作博弈方法實現多主體目標優化，研究了聯盟中多主體之間的相互作用，并建立聯盟的最優合作控制集合，提出了多服務主體的動態合作博弈模型;討論了動態環境下Shapley值沿著博弈的最優狀態的有效性;最 后基于上述模型設計了動態聯盟效用分配算法，實現聯盟中多主體的目標優化。仿真實驗表明，該算法能夠有效地保證在整個聯盟過程中Shapley值都能得以維持，避免多服務主體退出聯盟的行為直至合作的圓滿結束，達到多贏的帕累托最優局面。
參考文獻：
[1]COHEN P R， LEVESQUE H J. Teamwork[J].Nou’s ， 1991， 25 (4):487512.
[2] GROSZ B J， KRAUS S. Collaborative plans for complex group action[J].Artificial Intelligence ， 1996， 86 (2):269357.
[3] KINNY D， LJUNGBERG M， RAO A S， et al. Planned team activity[C]//Proc of the 4th European Workshop on Modelling Autonomous Agents in a Multiagent World， Artificial Social Systems. London: SpringerVerlag， 1992:227256.
[4] 羅杰文，史忠植，王茂光，等.基于動態描述邏輯的多主體協作模型[J].計算機研究與發展，2006， 43 (8):13171322.
[5] ROSENSCHEIN J S. Rational interaction: cooperation among intelligent agents[D]. Stanford，CA: Stanford University， 1986.
[6] Von NEUMANN J， MORGENSTERN O. Theory of games and economic behavior[M]. Princeton， N J: Princeton University Press， 1953.
[7] FILAR J A， PETROSJAN L A. Dynamic cooperative games[J].International Game Theory Review ， 2000， 2 (1):4765.
[8] 許青松，范玉順.支持動態聯盟的多代理系統[J].控制與決策，2001， 16 (2):199202.
[9] 陳剛，陸汝鈐.關系網模型——基于社會合作機制的多agent協作組織方法[J].計算機研究與發展，2003， 40 (1):107114.
[10] IHDE T. Dynamic alliance auctions: a mechanism for Internetbased transportation markets[M]. [S.l.]: Physica Verlag，2004.
[11] MACKENZIE A B， WICKER S B. Game theory and the design of selfconfiguring， adaptive wireless networks[J].Communications Magazine，2001， 39 (11):126131.
[12] CALVO E， SANTOS J C. Potentials in cooperative TUgames[J].Mathematical Social Sciences，1997， 34 (2):175190.
[13] SHORROCKS A F. Decomposition procedures for distributional analysis: a unified framework based on the Shapley value[D].[S.l.]: University of Essex， 1999.
[14] 曾廣周，黨妍.基于移動計算范型的遷移工作流研究[J].計算機學報，2003， 26 (10):13431349.
[15] 曾廣周，楊公平，王曉琳.基于agent能力自信度的任務分配問題研究[J].計算機學報，2007， 30 (11):19221929.
[16] JIN Mingzhou， WU S D. Procurement auctions with supplier coalitions: validity requirements and mechanism design[D]. [S.l.]:Lehigh University， 2002.
