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