摘? 要: 介紹了一種基于模糊邏輯的協(xié)調(diào)策略,。協(xié)調(diào)策略考慮協(xié)商過程中的各種因素,，包括時(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è)過程是一個(gè)協(xié)商雙方或多方不斷妥協(xié),、就共同關(guān)心的問題力求達(dá)成一致的動(dòng)態(tài)交互過程。根據(jù)參與協(xié)商者的數(shù)量可將協(xié)商劃分為：一對(duì)一協(xié)商,、一對(duì)多協(xié)商,、多對(duì)多協(xié)商[1]。
隨著主體技術(shù)在電子商務(wù)、網(wǎng)格等領(lǐng)域的應(yīng)用,，一對(duì)多協(xié)商受到愈來愈多的重視,。早期的一對(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é)商的承諾管理問題,，參考文獻(xiàn)[4]提出了一種基于相對(duì)效用理論的協(xié)調(diào)策略,。但是，協(xié)商過程中由于信息不完全而導(dǎo)致的不確定性和復(fù)雜性沒有被充分考慮,。本文提出了一種基于模糊邏輯的一對(duì)多協(xié)商的協(xié)調(diào)策略,，用來控制多個(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í)間沒有超時(shí),，則計(jì)算讓步幅度C并給對(duì)方一個(gè)新的提議，其中C代表上一個(gè)提議和本次提議的效用之差,。采用參考文獻(xiàn)[5]的算法來計(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ì)手的消息，其決策過程如下:
(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ū)κ肿尣降姆龋缓笙駽oordinator報(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的決策過程如下：
(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ī)則庫具體意義如下：
(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,，由用戶通過歷史經(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模糊推理算法,，可以得到一個(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ù)目超過25，eCN策略是最優(yōu)的,， FCS策略緊隨其后,。
由圖8，使用本文的FCS策略,，協(xié)商時(shí)間大大減少,；而且協(xié)商對(duì)手越多,，這種時(shí)間節(jié)省的效果就越明顯,。當(dāng)協(xié)商對(duì)手?jǐn)?shù)目超過20，F(xiàn)CS策略的協(xié)商時(shí)間不足eCN和OP的一半,。
因此,，當(dāng)協(xié)商對(duì)手?jǐn)?shù)目不是很多時(shí)，本文基于模糊推理的協(xié)調(diào)策略無論是在效用,，還是在時(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.