基于模糊粒子群优化算法的双边多议题协商模型

周松华



基于模糊粒子群优化算法的双边多议题协商模型

周松华

（井冈山大学电子与信息工程学院，江西，吉安 343009 ）

针对电子商务应用，提出了一种基于模糊粒子群优化算法的双边多议题协商模型。该模型以追求协商双方联合效用最大化为前提，通过粒子群在对手提议和自身议题理想值域之间进行快速有效搜索出最优解或近似最优解生成反提议；从而促使协商实现“双赢”。实验分析表明，该模型能有效提高协商效率。

多Agent系统；自动协商；粒子群算法

基于Agent的自动协商是多Agent系统（MAS，Multi-Agent System）领域的一个研究热点，近年来已经取得了许多成果。其中有关电子商务环境下的自动协商研究中，具有代表性研究有：（1）基于经验学习的自动化协商模型[1-2]，使用基于实例的推理技术将以前的经验和策略应用于当前的协商决策中，提供了可调整的协商策略来对协商过程进行动态控制；（2）面向目标的自动化协商模型[3]，Agent以自己的信息状态和接收到的提议，利用自己的学习系统来产生下一刻的反提议，通过不断的学习使自身的行为更加理性，提高协商效率。（3）侧重消解协商僵局的协商模型[4-6]，通过动态放宽引起协商僵局的相关议题的保留值，进行协商议题保留值的等效置换以保证不降低协商效用并达到协商一致。

本文的研究是在基于协商历史资源的自治协商前期研究基础上，引入粒子群优化算法(PSO, Particle swarm optimization)作为协商指导策略，提出一种基于模糊粒子群优化算法[10]的双边多议题协商模型FPSONEC(fuzzy particle swarm optimization negotiation E-commerce)。PSO算法[7-9]是Kennedy等人于1995年提出的一种模拟鸟群觅食行为发展起来的智能进化算法，粒子群的每次迭代能产生一组非劣解，及其适合扩展来求解目标优化问题。而协商以获取自身最大利益为目标，通过对相关议题反复协商以达到“双赢”的局面，即双方在一个共同的协商数学模型中寻找使双方利益最大化的最优解。本文提出的协商模型将协商过程转化为一个多目标优化问题，通过粒子群在指定域范围内搜索，获得pareto最优解集，生成反提议；促使协商Agent能最大限度地达到协商的满意解甚至最优解,并且提高协商的效率。

1 自动协商模型

1.1 FPSONEC模型定义

限时条件下，FPSONEC模型整体形式化描述为一个六元组：FPSONEC = <，，，，，>，各元组分别定义为：

协商参与者集合={1，2}；1为买方2为卖方。

1.2 基于FPSO的协商策略

理想的协商“双赢”局面要求协商双方在追求自身效用最大化同时还能达到协商双方联合效用最大。在信息保密和先验知识未知的环境下，本模型中仅买方Agent采用FPSO算法，在基于事例推理技术，从协商历史案例中学习获得对手的近似协商偏好，以预测对方效用。

1.2.1 FPSO算法

针对协商过程的不确定性，结合模糊理论对基本粒子群优化算法（PSO）进行改进，对惯性权值和粒子的位置更新进行模糊处理，将全局最优值用所有粒子的个体最优的加权平均值取代，使得粒子能够通过更多的信息来调整自己的飞行方向和速度，算法的改进能有效解决陷入局部最优的缺点，提高算法在协商议题值域内的搜索精度。

改进的模糊粒子群优化算法（FPSO）中每个粒子根据以下公式（1），（2）调整自己的飞行速度和方向：

1.2.2 协商优化数学模型描述

编码方案：种群中的每一个粒子代表要协商的议题值向量，

Nash提出两个Agent协商的最优结果是双方效用的乘积取最大化，协商过程买方Agent启动FPSO算法，粒子群在对方提议值和自身理想议题值间范围内搜索出能满足联合效用（公式3）最大化目标的最优解或近似最优解；作为本轮反提议。公式（4），（5）为协商双方Agent所采用的多议题整合效用函数进行提议评价。

1.2.3 模型协商算法

协商开始，双方以协商议题值提议的方式进行协商交互，买方Agent接收到卖方Agent初始提议后，整个协商过程如图1所示：

图1 协商流程图

2 仿真实验及分析

表1 协商参数

在协商过程中启动FPSO算法作为协商策略产生反提议，粒子群规模选择20，每个子群的惯性权重都为1.49，最大进化代数为100，粒子群的c1,c2均取为2。对协商策略进行matlab编程，并对其有效性进行验证。

本文所采用的实验指标包括协商过程中信息交换轮数（nego-rounds），协商过程双方联合效用，实验结果如图2。

图2 协商联合效用分析

本次实验案例协商在基于FPSONEC模型上经过4轮即协商成功，联合效用为0.45，买方和卖方的效用分别为0.68，0.66，基本达到各自的理想效用。

在基于资源的协商和FPSONEC两个模型上分别选取其他12个实验案例的仿真验证统计结果如表2所示。

表2 两种模型的协商效率比较

Table.2 The comparison of Two models ' negotiation efficiency

FPSONEC模型在产生反提议中充分考虑了对方提议和自身最优提议值，以积极的协商态度追求“双赢”为目标。实验表明FPSONEC协商模型相对基于资源的电子商务协商系统有效的提高了协商效率。

3 结论

FPSONEC模型在基于案例资源推理的基础上引入粒子群优化算法进行协商过程控制。并通过实验验证了其相对于单一的依赖协商历史案例资源指导协商在效率上有所提高。但本模型在粒子群搜索域空间限制在对方提议值和自身理想提议值区间进行，当对方提议值超出自身最大值时搜索最优值存在溢出现象，导致协商失败。故模型的后期优化中如何规避协商陷入僵局及消解僵局工作有待于做更多的深入研究。

[1] 杨清平. 蒲国林. 基于交互历史的多Agent自动协商研究[J].计算机科学,2008,35(9):226-229.

[2] 李健利. 使用案例推理的协商策略研究[J].计算机工程与应用,2012,48(8):119-121.

[3] 王黎明.黄厚宽.一个基于多阶段的多Agent多问题协商框架[J].计算机研究与发展，2005,42（11）：1849-1855.

[4] 彭志平,陈珂. 一种消解协商僵局的多目标粒子群优化算法[J].电子学报,2007,35(8):1452-1457.

[5] 王黎明,沈扬. 协商僵局的策略研究[J].计算机应用，2010,30(6):1519-1522.

[6] 张慧 .基于PSO的协商僵局消解机制的研究[D]，太原:太原理工大学, 2008.

[7] 周松华.欧阳春娟,自适应模糊的粒子群优化算法[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] 周松华. 基于资源的电子商务自动协商模型研究[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).