周松華

?

基于模糊粒子群優(yōu)化算法的雙邊多議題協(xié)商模型

周松華

（井岡山大學電子與信息工程學院，江西，吉安 343009 ）

針對電子商務應用，提出了一種基于模糊粒子群優(yōu)化算法的雙邊多議題協(xié)商模型。該模型以追求協(xié)商雙方聯(lián)合效用最大化為前提，通過粒子群在對手提議和自身議題理想值域之間進行快速有效搜索出最優(yōu)解或近似最優(yōu)解生成反提議；從而促使協(xié)商實現(xiàn)“雙贏”。實驗分析表明，該模型能有效提高協(xié)商效率。

多Agent系統(tǒng)；自動協(xié)商；粒子群算法

基于Agent的自動協(xié)商是多Agent系統(tǒng)（MAS，Multi-Agent System）領域的一個研究熱點，近年來已經(jīng)取得了許多成果。其中有關電子商務環(huán)境下的自動協(xié)商研究中，具有代表性研究有：（1）基于經(jīng)驗學習的自動化協(xié)商模型[1-2]，使用基于實例的推理技術將以前的經(jīng)驗和策略應用于當前的協(xié)商決策中，提供了可調整的協(xié)商策略來對協(xié)商過程進行動態(tài)控制；（2）面向目標的自動化協(xié)商模型[3]，Agent以自己的信息狀態(tài)和接收到的提議，利用自己的學習系統(tǒng)來產生下一刻的反提議，通過不斷的學習使自身的行為更加理性，提高協(xié)商效率。（3）側重消解協(xié)商僵局的協(xié)商模型[4-6]，通過動態(tài)放寬引起協(xié)商僵局的相關議題的保留值，進行協(xié)商議題保留值的等效置換以保證不降低協(xié)商效用并達到協(xié)商一致。

本文的研究是在基于協(xié)商歷史資源的自治協(xié)商前期研究基礎上，引入粒子群優(yōu)化算法(PSO, Particle swarm optimization)作為協(xié)商指導策略，提出一種基于模糊粒子群優(yōu)化算法[10]的雙邊多議題協(xié)商模型FPSONEC(fuzzy particle swarm optimization negotiation E-commerce)。PSO算法[7-9]是Kennedy等人于1995年提出的一種模擬鳥群覓食行為發(fā)展起來的智能進化算法，粒子群的每次迭代能產生一組非劣解，及其適合擴展來求解目標優(yōu)化問題。而協(xié)商以獲取自身最大利益為目標，通過對相關議題反復協(xié)商以達到“雙贏”的局面，即雙方在一個共同的協(xié)商數(shù)學模型中尋找使雙方利益最大化的最優(yōu)解。本文提出的協(xié)商模型將協(xié)商過程轉化為一個多目標優(yōu)化問題，通過粒子群在指定域范圍內搜索，獲得pareto最優(yōu)解集，生成反提議；促使協(xié)商Agent能最大限度地達到協(xié)商的滿意解甚至最優(yōu)解,并且提高協(xié)商的效率。

1 自動協(xié)商模型

1.1 FPSONEC模型定義

限時條件下，F(xiàn)PSONEC模型整體形式化描述為一個六元組：FPSONEC = <，，，，，>，各元組分別定義為：

協(xié)商參與者集合={1，2}；1為買方2為賣方。

1.2 基于FPSO的協(xié)商策略

理想的協(xié)商“雙贏”局面要求協(xié)商雙方在追求自身效用最大化同時還能達到協(xié)商雙方聯(lián)合效用最大。在信息保密和先驗知識未知的環(huán)境下，本模型中僅買方Agent采用FPSO算法，在基于事例推理技術，從協(xié)商歷史案例中學習獲得對手的近似協(xié)商偏好，以預測對方效用。

1.2.1 FPSO算法

針對協(xié)商過程的不確定性，結合模糊理論對基本粒子群優(yōu)化算法（PSO）進行改進，對慣性權值和粒子的位置更新進行模糊處理，將全局最優(yōu)值用所有粒子的個體最優(yōu)的加權平均值取代，使得粒子能夠通過更多的信息來調整自己的飛行方向和速度，算法的改進能有效解決陷入局部最優(yōu)的缺點，提高算法在協(xié)商議題值域內的搜索精度。

改進的模糊粒子群優(yōu)化算法（FPSO）中每個粒子根據(jù)以下公式（1），（2）調整自己的飛行速度和方向：

1.2.2 協(xié)商優(yōu)化數(shù)學模型描述

編碼方案：種群中的每一個粒子代表要協(xié)商的議題值向量，

Nash提出兩個Agent協(xié)商的最優(yōu)結果是雙方效用的乘積取最大化，協(xié)商過程買方Agent啟動FPSO算法，粒子群在對方提議值和自身理想議題值間范圍內搜索出能滿足聯(lián)合效用（公式3）最大化目標的最優(yōu)解或近似最優(yōu)解；作為本輪反提議。公式（4），（5）為協(xié)商雙方Agent所采用的多議題整合效用函數(shù)進行提議評價。

1.2.3 模型協(xié)商算法

協(xié)商開始，雙方以協(xié)商議題值提議的方式進行協(xié)商交互，買方Agent接收到賣方Agent初始提議后，整個協(xié)商過程如圖1所示：

圖1 協(xié)商流程圖

2 仿真實驗及分析

表1 協(xié)商參數(shù)

在協(xié)商過程中啟動FPSO算法作為協(xié)商策略產生反提議，粒子群規(guī)模選擇20，每個子群的慣性權重都為1.49，最大進化代數(shù)為100，粒子群的c1,c2均取為2。對協(xié)商策略進行matlab編程，并對其有效性進行驗證。

本文所采用的實驗指標包括協(xié)商過程中信息交換輪數(shù)（nego-rounds），協(xié)商過程雙方聯(lián)合效用，實驗結果如圖2。

圖2 協(xié)商聯(lián)合效用分析

本次實驗案例協(xié)商在基于FPSONEC模型上經(jīng)過4輪即協(xié)商成功，聯(lián)合效用為0.45，買方和賣方的效用分別為0.68，0.66，基本達到各自的理想效用。

在基于資源的協(xié)商和FPSONEC兩個模型上分別選取其他12個實驗案例的仿真驗證統(tǒng)計結果如表2所示。

表2 兩種模型的協(xié)商效率比較

Table.2 The comparison of Two models ' negotiation efficiency

FPSONEC模型在產生反提議中充分考慮了對方提議和自身最優(yōu)提議值，以積極的協(xié)商態(tài)度追求“雙贏”為目標。實驗表明FPSONEC協(xié)商模型相對基于資源的電子商務協(xié)商系統(tǒng)有效的提高了協(xié)商效率。

3 結論

FPSONEC模型在基于案例資源推理的基礎上引入粒子群優(yōu)化算法進行協(xié)商過程控制。并通過實驗驗證了其相對于單一的依賴協(xié)商歷史案例資源指導協(xié)商在效率上有所提高。但本模型在粒子群搜索域空間限制在對方提議值和自身理想提議值區(qū)間進行，當對方提議值超出自身最大值時搜索最優(yōu)值存在溢出現(xiàn)象，導致協(xié)商失敗。故模型的后期優(yōu)化中如何規(guī)避協(xié)商陷入僵局及消解僵局工作有待于做更多的深入研究。

[1] 楊清平. 蒲國林. 基于交互歷史的多Agent自動協(xié)商研究[J].計算機科學,2008,35(9):226-229.

[2] 李健利. 使用案例推理的協(xié)商策略研究[J].計算機工程與應用,2012,48(8):119-121.

[3] 王黎明.黃厚寬.一個基于多階段的多Agent多問題協(xié)商框架[J].計算機研究與發(fā)展，2005,42（11）：1849-1855.

[4] 彭志平,陳珂. 一種消解協(xié)商僵局的多目標粒子群優(yōu)化算法[J].電子學報,2007,35(8):1452-1457.

[5] 王黎明,沈揚. 協(xié)商僵局的策略研究[J].計算機應用，2010,30(6):1519-1522.

[6] 張慧 .基于PSO的協(xié)商僵局消解機制的研究[D]，太原:太原理工大學, 2008.

[7] 周松華.歐陽春娟,自適應模糊的粒子群優(yōu)化算法[J].計算機工程與應用,2010,46(33):46-48.

[8] Eberhart R C, Kennedy J. A new optimizer using particle swarm theory[C]. Proceedings of the 6th International Symposium on Micro Machine and Human Science. Nagoya，1995:39-43.

[9] Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proceedings IEEE International Conference on Neural Net-works[C].Piscataway:IEEE Press,1995:1942-1948.

[10] Kennedy J, Eberhart R C. Swarm Intelligence[M]. SiliconValley:Morgan Kaufmann Publishers,2001.

[11] 周松華. 基于資源的電子商務自動協(xié)商模型研究[D].廣州:華南師范大學,2005.

RESEARCH ON BILATERAL MULTI-ISSUE NEGOTIATION MODEL BASED ON FPSO

ZHOU Song-hua

(School of Electronics and Information Engineering, Jinggangshan University, Ji’an, Jiangxi 343009, China)

An autonomous negotiation model based on fuzzy particle swarm optimization (FPSO) is proposed in the application of E-commerce. The model is used to pursue negotiations joint utility maximization. The win-win negotiation is achieved and the counter proposal is generated based on the optimal solution or approximate optimal solution, which is provided by the quickly and efficiently search of particle swarm optimization between rival proposal and its’ issues ideal. The experimental analysis shows that the model can effectively improves the efficiency of negotiation.

multi-agent system; autonomous negotiation; particle swarm optimization

1674-8085(2014)01-0051-04

TP393.08

A

10.3969/j.issn.1674-8085.2014.01.011

2013-10-23；

2013-12-09

江西省教育廳科學技術研究項目(GJJ13553)

周松華(1977-)，女，江西吉安人，副教授，碩士，主要從事智能算法及應用，電子商務研究(E-mail:zhousonghua@jgsu.edu.cn).