摘? 要: 介紹了一種基于模糊邏輯的協(xié)調(diào)策略。協(xié)調(diào)策略考慮協(xié)商過程中的各種因素，包括時間、對手?jǐn)?shù)目、對手的提議等，使用模糊規(guī)則和模糊推理，對多個相互影響的并發(fā)一對一協(xié)商進(jìn)行協(xié)調(diào)。實(shí)驗(yàn)證明，該策略能夠很好地適應(yīng)信息不完全的環(huán)境。
關(guān)鍵詞： 一對多協(xié)商； 協(xié)調(diào)策略； 模糊邏輯
?
自動協(xié)商是多主體系統(tǒng)MAS(Multi-agent System)中的一個研究熱點(diǎn)。沖突是協(xié)商的起點(diǎn), 整個過程是一個協(xié)商雙方或多方不斷妥協(xié)、就共同關(guān)心的問題力求達(dá)成一致的動態(tài)交互過程。根據(jù)參與協(xié)商者的數(shù)量可將協(xié)商劃分為：一對一協(xié)商、一對多協(xié)商、多對多協(xié)商[1]。
隨著主體技術(shù)在電子商務(wù)、網(wǎng)格等領(lǐng)域的應(yīng)用，一對多協(xié)商受到愈來愈多的重視。早期的一對多協(xié)商研究主要是采用拍賣作為參與方的協(xié)商策略。但是拍賣方式極不靈活，而且買賣雙方的信息交流不充分[2]。因此，研究人員將一對多協(xié)商轉(zhuǎn)化為多個并發(fā)的一對一協(xié)商[2～4]，于是多個并發(fā)的一對一協(xié)商之間的相互協(xié)調(diào)就變得尤為重要。
多個并發(fā)的一對一協(xié)商組成的一對多協(xié)商是一個較新的課題。目前, 并發(fā)協(xié)商的研究還處于起步階段。參考文獻(xiàn)[2]提出了三種協(xié)調(diào)策略，參考文獻(xiàn)[3]主要研究了并發(fā)協(xié)商的承諾管理問題，參考文獻(xiàn)[4]提出了一種基于相對效用理論的協(xié)調(diào)策略。但是，協(xié)商過程中由于信息不完全而導(dǎo)致的不確定性和復(fù)雜性沒有被充分考慮。本文提出了一種基于模糊邏輯的一對多協(xié)商的協(xié)調(diào)策略，用來控制多個并行進(jìn)行的一對一協(xié)商。實(shí)驗(yàn)結(jié)果證明，這種策略能較好地適應(yīng)動態(tài)、不確定的環(huán)境，幫助主體尋找花費(fèi)盡可能少、同時具有更高性價比的協(xié)商結(jié)果。
1 一對一協(xié)商模型
它向?qū)Ψ桨l(fā)送一個Accept消息，協(xié)商成功結(jié)束；如果某一方的時間門限已經(jīng)到達(dá)而仍未達(dá)成一致，則此方向?qū)Ψ桨l(fā)送一個Withdraw消息，協(xié)商失敗。
當(dāng)主體g收到協(xié)商對手的一個提議X時，首先計算這個提議的效用Vg(x)，如果大于等于τg，則接受這個提議，協(xié)商成功結(jié)束；否則，如果時間沒有超時，則計算讓步幅度C并給對方一個新的提議，其中C代表上一個提議和本次提議的效用之差。采用參考文獻(xiàn)[5]的算法來計算C。
2 一對多協(xié)商模型
??? 把一對多協(xié)商轉(zhuǎn)化為多個并發(fā)的一對一協(xié)商，需要一個協(xié)調(diào)者，基于某種協(xié)調(diào)策略對多個并發(fā)的一對一協(xié)商進(jìn)行協(xié)調(diào)，確保多個并發(fā)的一對一協(xié)商能夠有效、有序地執(zhí)行。圖1 是一對多協(xié)商的系統(tǒng)結(jié)構(gòu)圖。
?
假設(shè)主體Negotiator有n個協(xié)商對手。Negotiator主體由一個Coordinator和n個sub-negotiator組成，每個sub-negotiator對應(yīng)一個協(xié)商對手，代表Negotiator和一個協(xié)商對手進(jìn)行一對一協(xié)商，稱之為一個協(xié)商線程(thread)。Coordinator負(fù)責(zé)協(xié)調(diào)各協(xié)商線程。
2.1 協(xié)商線程
所有sub-negotiator具有相同的知識，包括Negotiator主體的偏好、協(xié)商時間等。每個sub-negotiator都使用參考文獻(xiàn)[5]引入的雙邊協(xié)商算法。但是，這些sub-negotiator的建議產(chǎn)生機(jī)制不盡相同，具體表現(xiàn)在讓步速度參數(shù)的不同[5]。因?yàn)榻ㄗh產(chǎn)生機(jī)制和協(xié)商對手的不同，所有sub-negotiator的行為是不相同的。
在每個協(xié)商回合，第i個sub-negotiator收到對手的消息，其決策過程如下:
(1)如果收到Accept消息，則向Coordinator報告協(xié)商成功，并報告達(dá)成的服務(wù)合約；終止此協(xié)商線程；
(2)如果收到Withdraw消息，則向Coordinator報告協(xié)商失敗，終止此協(xié)商線程；
(3)如果對手的提議可以接受，則向Coordinator報告協(xié)商成功，并報告達(dá)成的服務(wù)合約；
(4)如果對手的提議不可接受，則首先根據(jù)參考文獻(xiàn)[5]中的一對一協(xié)商策略計算下一回合向?qū)κ肿尣降姆?，然后向Coordinator報告對手的提議和擬讓步幅度Ci，并等待Coordinator對擬讓步幅度的調(diào)整，產(chǎn)生一個新的提議。
可以看出，在每個協(xié)商回合，sub-negotiator都要向Coordinator報告當(dāng)前協(xié)商線程的狀態(tài)，并根據(jù)Coordinator的指令向?qū)κ痔嶙h。
2.2 協(xié)商協(xié)調(diào)策略
首先，Coordinator是一個信息集中的地方。在一個協(xié)商線程中的每個協(xié)商回合，sub-negotiator就向Coordinator報告當(dāng)前各協(xié)商線程的狀態(tài)。Coordinator記錄當(dāng)前仍在活動的協(xié)商線程數(shù)目m，維持一個當(dāng)前各協(xié)商對手的最新提議列表，并計算最大效用Vm=max{V(p1),V(p2),… V(pm)以及協(xié)商距離Δ=τ－Vm。
最重要的是，Coordinator負(fù)責(zé)協(xié)調(diào)各個協(xié)商線程。每當(dāng)收到一個sub-negotiator的報告，Coordinator的決策過程如下：
(1)如果此協(xié)商線程成功結(jié)束，則Coordinator中止所有協(xié)商線程，協(xié)商結(jié)束。
(2)如果此協(xié)商線程失敗，則Coordinator終止此協(xié)商線程，并更新自己的知識：當(dāng)前仍在活動的協(xié)商線程數(shù)目m、當(dāng)前各協(xié)商對手的最新提議列表、以及最大效用和協(xié)商距離。
(3)如果此協(xié)商線程仍在進(jìn)行， 則sub-negotiator給Coordinator的報告包括以下內(nèi)容：協(xié)商對手的最新提議和擬讓步幅度Ci。Coordinator更新自己的知識，對Ci進(jìn)行調(diào)整，并通知sub-negotiator新的讓步幅度。
在對擬讓步幅度進(jìn)行調(diào)整時，Coordinator考慮當(dāng)前的形勢，包括當(dāng)前仍在活動的協(xié)商線程數(shù)目m、時間t以及協(xié)商距離Δ，基于模糊規(guī)則和Sugeno模糊推理系統(tǒng)進(jìn)行決策。之所以基于模糊規(guī)則和Sugeno模糊推理系統(tǒng)，是因?yàn)橹黧w掌握的信息不完全，必須面對不確定性，而模糊推理已經(jīng)被證明適用于許多具有這個特點(diǎn)的領(lǐng)域。
具體地，調(diào)整策略的規(guī)則庫具體意義如下：
(1)如果當(dāng)前時間t很接近tmax，則大幅度地調(diào)大整體讓步幅度Ci；
(2)如果當(dāng)前仍在活動的線程數(shù)目m很大，時間t不接近tmax，但是協(xié)商距離Δ比較大，則幾乎不用調(diào)整整體讓步幅度；
(3)如果當(dāng)前仍在活動的線程數(shù)目m很大，時間t不接近tmax，而且協(xié)商距離Δ較小，則調(diào)小讓步幅度；
(4)如果當(dāng)前仍在活動的線程數(shù)目m很小，協(xié)商距離Δ比較大，但是時間t距tmax較遠(yuǎn)，則幾乎不用調(diào)整整體讓步幅度；
(5)如果當(dāng)前仍在活動的線程數(shù)目m很小，但是時間t距tmax較遠(yuǎn)，而且協(xié)商距離Δ比較小，則調(diào)小整體讓步幅度；
(6)如果當(dāng)前仍在活動的線程數(shù)目m很小，協(xié)商距離Δ比較大，時間t距tmax不遠(yuǎn)不近，則調(diào)大整體讓步幅度；
(7)如果當(dāng)前仍在活動的線程數(shù)目m很小，協(xié)商距離Δ比較小，時間t距tmax不遠(yuǎn)不近，則幾乎不用調(diào)整整體讓步幅度。
“t is close-to/medium-to/far-from tmax”用模糊集合表示，如圖2所示。
?
表示“m is big/small”的模糊集合如圖3。
表示“Δ is big/small“的模糊集合如圖4。
?
這些模糊集合中的參數(shù)如t1、t2、t3、t4、m1、m2、Δ1、Δ2，由用戶通過歷史經(jīng)驗(yàn)確定。
“much-bigger-than, bigger-than, close-to, smaller-than, much-smaller-than”等概念也用模糊集合表示，如圖5。
這些模糊集合中的參數(shù)cj(1≤j≤8)可以表示為ci和Δ的函數(shù)，而這些函數(shù)也可以由用戶根據(jù)經(jīng)驗(yàn)指定。
根據(jù)推理規(guī)則庫和Sugeno模糊推理算法，可以得到一個三角模糊數(shù)，設(shè)為C=(mc,θc,χc)，其中mc是中心，θc 和χc是左右距離。假設(shè)用戶指定的置信水平為α，則C的α-截集Cα如圖6所示。
最后，Coordinator從這個α-截集中隨機(jī)選取一個值，作為新的讓步幅度，并通知sub-negotiator。sub-negotiator根據(jù)新的讓步幅度 ，產(chǎn)生一個新的提議給協(xié)商對手。
3 實(shí)驗(yàn)
將本文中的協(xié)調(diào)策略FCS(Fuzzy technique-based Coordinating Strategy）與eCN[3]和OP[2]進(jìn)行比較，結(jié)果如圖7和圖8所示。
?
圖7比較了三種協(xié)調(diào)策略可獲得的效用?？梢钥闯?，當(dāng)協(xié)商對手的數(shù)目不多(小于等于25)，本文的FCS策略是最優(yōu)的。當(dāng)協(xié)商對手?jǐn)?shù)目超過25，eCN策略是最優(yōu)的， FCS策略緊隨其后。
由圖8，使用本文的FCS策略，協(xié)商時間大大減少；而且協(xié)商對手越多，這種時間節(jié)省的效果就越明顯。當(dāng)協(xié)商對手?jǐn)?shù)目超過20，F(xiàn)CS策略的協(xié)商時間不足eCN和OP的一半。
因此，當(dāng)協(xié)商對手?jǐn)?shù)目不是很多時，本文基于模糊推理的協(xié)調(diào)策略無論是在效用，還是在時間上，都具有更好的表現(xiàn)。當(dāng)協(xié)商對手的數(shù)目較多時，本文的協(xié)調(diào)策略雖然在效用上表現(xiàn)不是最優(yōu)，但是協(xié)商時間大大減少。這尤其適用于時間有限的協(xié)商場景。
本文重點(diǎn)研究了一對多協(xié)商中協(xié)調(diào)者使用的對多個并發(fā)的一對一協(xié)商進(jìn)行協(xié)調(diào)的協(xié)調(diào)策略。為了在信息不完全的環(huán)境中對多個協(xié)商線程進(jìn)行有效的協(xié)調(diào)，協(xié)調(diào)策略使用了模糊規(guī)則和模糊推理技術(shù)。實(shí)驗(yàn)證明，該協(xié)調(diào)策略在動態(tài)不確定環(huán)境中，能夠在縮短協(xié)商時間、提高協(xié)商效率的同時，保證協(xié)商主體獲得較高的效用。
參考文獻(xiàn)
[1] ?LOMUSCIO A R，WOOLDRIDGE M， JENNINGS N R. A?classification scheme for negotiation in electronic commerce[J].Int J of Group Decision and Negotiation，2003，12(1):31-56.
[2] ?RAHWAN I，KOWALCZYK R，PHAM H H. Intelligent?agents for automated one-to-many e-commerce negotiation
?[C].Twenty-Fifth Australian Computer Science Conference，2002:197-204.
[3] ?NGUYEN T D， JENNINGS N R. Coordinating multiple?concurrent negotiations[C]. Proc 3rd Int Conf on
?Autonomous Agents and Multi-Agent Systems，New York，USA，2004:1064-1071.
[4] ?孫天昊，朱慶生，李雙慶. 一對多協(xié)商協(xié)調(diào)策略[J].?計算機(jī)工程與應(yīng)用，2007,43(3):230-233.
[5] ?KWANG M S,CHUNG Y C. Agents that react to changing??market situations[J]. IEEE Transactions on Systems, Man?and Cybernetics, Part B, 2003,33(2):188-201.