摘? 要: 介紹了一種基于模糊邏輯的協(xié)調(diào)策略。協(xié)調(diào)策略考慮協(xié)商過(guò)程中的各種因素，包括時(shí)間、對(duì)手?jǐn)?shù)目、對(duì)手的提議等，使用模糊規(guī)則和模糊推理，對(duì)多個(gè)相互影響的并發(fā)一對(duì)一協(xié)商進(jìn)行協(xié)調(diào)。實(shí)驗(yàn)證明，該策略能夠很好地適應(yīng)信息不完全的環(huán)境。
關(guān)鍵詞： 一對(duì)多協(xié)商； 協(xié)調(diào)策略； 模糊邏輯
?
自動(dòng)協(xié)商是多主體系統(tǒng)MAS(Multi-agent System)中的一個(gè)研究熱點(diǎn)。沖突是協(xié)商的起點(diǎn), 整個(gè)過(guò)程是一個(gè)協(xié)商雙方或多方不斷妥協(xié)、就共同關(guān)心的問(wèn)題力求達(dá)成一致的動(dòng)態(tài)交互過(guò)程。根據(jù)參與協(xié)商者的數(shù)量可將協(xié)商劃分為：一對(duì)一協(xié)商、一對(duì)多協(xié)商、多對(duì)多協(xié)商[1]。
隨著主體技術(shù)在電子商務(wù)、網(wǎng)格等領(lǐng)域的應(yīng)用，一對(duì)多協(xié)商受到愈來(lái)愈多的重視。早期的一對(duì)多協(xié)商研究主要是采用拍賣作為參與方的協(xié)商策略。但是拍賣方式極不靈活，而且買賣雙方的信息交流不充分[2]。因此，研究人員將一對(duì)多協(xié)商轉(zhuǎn)化為多個(gè)并發(fā)的一對(duì)一協(xié)商[2～4]，于是多個(gè)并發(fā)的一對(duì)一協(xié)商之間的相互協(xié)調(diào)就變得尤為重要。
多個(gè)并發(fā)的一對(duì)一協(xié)商組成的一對(duì)多協(xié)商是一個(gè)較新的課題。目前, 并發(fā)協(xié)商的研究還處于起步階段。參考文獻(xiàn)[2]提出了三種協(xié)調(diào)策略，參考文獻(xiàn)[3]主要研究了并發(fā)協(xié)商的承諾管理問(wèn)題，參考文獻(xiàn)[4]提出了一種基于相對(duì)效用理論的協(xié)調(diào)策略。但是，協(xié)商過(guò)程中由于信息不完全而導(dǎo)致的不確定性和復(fù)雜性沒(méi)有被充分考慮。本文提出了一種基于模糊邏輯的一對(duì)多協(xié)商的協(xié)調(diào)策略，用來(lái)控制多個(gè)并行進(jìn)行的一對(duì)一協(xié)商。實(shí)驗(yàn)結(jié)果證明，這種策略能較好地適應(yīng)動(dòng)態(tài)、不確定的環(huán)境，幫助主體尋找花費(fèi)盡可能少、同時(shí)具有更高性價(jià)比的協(xié)商結(jié)果。
1 一對(duì)一協(xié)商模型
它向?qū)Ψ桨l(fā)送一個(gè)Accept消息，協(xié)商成功結(jié)束；如果某一方的時(shí)間門限已經(jīng)到達(dá)而仍未達(dá)成一致，則此方向?qū)Ψ桨l(fā)送一個(gè)Withdraw消息，協(xié)商失敗。
當(dāng)主體g收到協(xié)商對(duì)手的一個(gè)提議X時(shí)，首先計(jì)算這個(gè)提議的效用Vg(x)，如果大于等于τg，則接受這個(gè)提議，協(xié)商成功結(jié)束；否則，如果時(shí)間沒(méi)有超時(shí)，則計(jì)算讓步幅度C并給對(duì)方一個(gè)新的提議，其中C代表上一個(gè)提議和本次提議的效用之差。采用參考文獻(xiàn)[5]的算法來(lái)計(jì)算C。
2 一對(duì)多協(xié)商模型
??? 把一對(duì)多協(xié)商轉(zhuǎn)化為多個(gè)并發(fā)的一對(duì)一協(xié)商，需要一個(gè)協(xié)調(diào)者，基于某種協(xié)調(diào)策略對(duì)多個(gè)并發(fā)的一對(duì)一協(xié)商進(jìn)行協(xié)調(diào)，確保多個(gè)并發(fā)的一對(duì)一協(xié)商能夠有效、有序地執(zhí)行。圖1 是一對(duì)多協(xié)商的系統(tǒng)結(jié)構(gòu)圖。
?
假設(shè)主體Negotiator有n個(gè)協(xié)商對(duì)手。Negotiator主體由一個(gè)Coordinator和n個(gè)sub-negotiator組成，每個(gè)sub-negotiator對(duì)應(yīng)一個(gè)協(xié)商對(duì)手，代表Negotiator和一個(gè)協(xié)商對(duì)手進(jìn)行一對(duì)一協(xié)商，稱之為一個(gè)協(xié)商線程(thread)。Coordinator負(fù)責(zé)協(xié)調(diào)各協(xié)商線程。
2.1 協(xié)商線程
所有sub-negotiator具有相同的知識(shí)，包括Negotiator主體的偏好、協(xié)商時(shí)間等。每個(gè)sub-negotiator都使用參考文獻(xiàn)[5]引入的雙邊協(xié)商算法。但是，這些sub-negotiator的建議產(chǎn)生機(jī)制不盡相同，具體表現(xiàn)在讓步速度參數(shù)的不同[5]。因?yàn)榻ㄗh產(chǎn)生機(jī)制和協(xié)商對(duì)手的不同，所有sub-negotiator的行為是不相同的。
在每個(gè)協(xié)商回合，第i個(gè)sub-negotiator收到對(duì)手的消息，其決策過(guò)程如下:
(1)如果收到Accept消息，則向Coordinator報(bào)告協(xié)商成功，并報(bào)告達(dá)成的服務(wù)合約；終止此協(xié)商線程；
(2)如果收到Withdraw消息，則向Coordinator報(bào)告協(xié)商失敗，終止此協(xié)商線程；
(3)如果對(duì)手的提議可以接受，則向Coordinator報(bào)告協(xié)商成功，并報(bào)告達(dá)成的服務(wù)合約；
(4)如果對(duì)手的提議不可接受，則首先根據(jù)參考文獻(xiàn)[5]中的一對(duì)一協(xié)商策略計(jì)算下一回合向?qū)κ肿尣降姆?，然后向Coordinator報(bào)告對(duì)手的提議和擬讓步幅度Ci，并等待Coordinator對(duì)擬讓步幅度的調(diào)整，產(chǎn)生一個(gè)新的提議。
可以看出，在每個(gè)協(xié)商回合，sub-negotiator都要向Coordinator報(bào)告當(dāng)前協(xié)商線程的狀態(tài)，并根據(jù)Coordinator的指令向?qū)κ痔嶙h。
2.2 協(xié)商協(xié)調(diào)策略
首先，Coordinator是一個(gè)信息集中的地方。在一個(gè)協(xié)商線程中的每個(gè)協(xié)商回合，sub-negotiator就向Coordinator報(bào)告當(dāng)前各協(xié)商線程的狀態(tài)。Coordinator記錄當(dāng)前仍在活動(dòng)的協(xié)商線程數(shù)目m，維持一個(gè)當(dāng)前各協(xié)商對(duì)手的最新提議列表，并計(jì)算最大效用Vm=max{V(p1),V(p2),… V(pm)以及協(xié)商距離Δ=τ－Vm。
最重要的是，Coordinator負(fù)責(zé)協(xié)調(diào)各個(gè)協(xié)商線程。每當(dāng)收到一個(gè)sub-negotiator的報(bào)告，Coordinator的決策過(guò)程如下：
(1)如果此協(xié)商線程成功結(jié)束，則Coordinator中止所有協(xié)商線程，協(xié)商結(jié)束。
(2)如果此協(xié)商線程失敗，則Coordinator終止此協(xié)商線程，并更新自己的知識(shí)：當(dāng)前仍在活動(dòng)的協(xié)商線程數(shù)目m、當(dāng)前各協(xié)商對(duì)手的最新提議列表、以及最大效用和協(xié)商距離。
(3)如果此協(xié)商線程仍在進(jìn)行， 則sub-negotiator給Coordinator的報(bào)告包括以下內(nèi)容：協(xié)商對(duì)手的最新提議和擬讓步幅度Ci。Coordinator更新自己的知識(shí)，對(duì)Ci進(jìn)行調(diào)整，并通知sub-negotiator新的讓步幅度。
在對(duì)擬讓步幅度進(jìn)行調(diào)整時(shí)，Coordinator考慮當(dāng)前的形勢(shì)，包括當(dāng)前仍在活動(dòng)的協(xié)商線程數(shù)目m、時(shí)間t以及協(xié)商距離Δ，基于模糊規(guī)則和Sugeno模糊推理系統(tǒng)進(jìn)行決策。之所以基于模糊規(guī)則和Sugeno模糊推理系統(tǒng)，是因?yàn)橹黧w掌握的信息不完全，必須面對(duì)不確定性，而模糊推理已經(jīng)被證明適用于許多具有這個(gè)特點(diǎn)的領(lǐng)域。
具體地，調(diào)整策略的規(guī)則庫(kù)具體意義如下：
(1)如果當(dāng)前時(shí)間t很接近tmax，則大幅度地調(diào)大整體讓步幅度Ci；
(2)如果當(dāng)前仍在活動(dòng)的線程數(shù)目m很大，時(shí)間t不接近tmax，但是協(xié)商距離Δ比較大，則幾乎不用調(diào)整整體讓步幅度；
(3)如果當(dāng)前仍在活動(dòng)的線程數(shù)目m很大，時(shí)間t不接近tmax，而且協(xié)商距離Δ較小，則調(diào)小讓步幅度；
(4)如果當(dāng)前仍在活動(dòng)的線程數(shù)目m很小，協(xié)商距離Δ比較大，但是時(shí)間t距tmax較遠(yuǎn)，則幾乎不用調(diào)整整體讓步幅度；
(5)如果當(dāng)前仍在活動(dòng)的線程數(shù)目m很小，但是時(shí)間t距tmax較遠(yuǎn)，而且協(xié)商距離Δ比較小，則調(diào)小整體讓步幅度；
(6)如果當(dāng)前仍在活動(dòng)的線程數(shù)目m很小，協(xié)商距離Δ比較大，時(shí)間t距tmax不遠(yuǎn)不近，則調(diào)大整體讓步幅度；
(7)如果當(dāng)前仍在活動(dòng)的線程數(shù)目m很小，協(xié)商距離Δ比較小，時(shí)間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，由用戶通過(guò)歷史經(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ī)則庫(kù)和Sugeno模糊推理算法，可以得到一個(gè)三角模糊數(shù)，設(shè)為C=(mc,θc,χc)，其中mc是中心，θc 和χc是左右距離。假設(shè)用戶指定的置信水平為α，則C的α-截集Cα如圖6所示。
最后，Coordinator從這個(gè)α-截集中隨機(jī)選取一個(gè)值，作為新的讓步幅度，并通知sub-negotiator。sub-negotiator根據(jù)新的讓步幅度 ，產(chǎn)生一個(gè)新的提議給協(xié)商對(duì)手。
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é)商對(duì)手的數(shù)目不多(小于等于25)，本文的FCS策略是最優(yōu)的。當(dāng)協(xié)商對(duì)手?jǐn)?shù)目超過(guò)25，eCN策略是最優(yōu)的， FCS策略緊隨其后。
由圖8，使用本文的FCS策略，協(xié)商時(shí)間大大減少；而且協(xié)商對(duì)手越多，這種時(shí)間節(jié)省的效果就越明顯。當(dāng)協(xié)商對(duì)手?jǐn)?shù)目超過(guò)20，F(xiàn)CS策略的協(xié)商時(shí)間不足eCN和OP的一半。
因此，當(dāng)協(xié)商對(duì)手?jǐn)?shù)目不是很多時(shí)，本文基于模糊推理的協(xié)調(diào)策略無(wú)論是在效用，還是在時(shí)間上，都具有更好的表現(xiàn)。當(dāng)協(xié)商對(duì)手的數(shù)目較多時(shí)，本文的協(xié)調(diào)策略雖然在效用上表現(xiàn)不是最優(yōu)，但是協(xié)商時(shí)間大大減少。這尤其適用于時(shí)間有限的協(xié)商場(chǎng)景。
本文重點(diǎn)研究了一對(duì)多協(xié)商中協(xié)調(diào)者使用的對(duì)多個(gè)并發(fā)的一對(duì)一協(xié)商進(jìn)行協(xié)調(diào)的協(xié)調(diào)策略。為了在信息不完全的環(huán)境中對(duì)多個(gè)協(xié)商線程進(jìn)行有效的協(xié)調(diào)，協(xié)調(diào)策略使用了模糊規(guī)則和模糊推理技術(shù)。實(shí)驗(yàn)證明，該協(xié)調(diào)策略在動(dòng)態(tài)不確定環(huán)境中，能夠在縮短協(xié)商時(shí)間、提高協(xié)商效率的同時(shí)，保證協(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] ?孫天昊，朱慶生，李雙慶. 一對(duì)多協(xié)商協(xié)調(diào)策略[J].?計(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.