一种竞争环境下基于改进遗传算法的电子商务协商*

李 剑，景 博,袁彩霞

(1．北京邮电大学网络与交换国家重点实验室，北京 100876；2．北京理工大学软件学院，北京 100081)

在基于多智能体的电子商务系统中，通常需要自治的agent之间进行自动协商。但是由于智能体自身的不完全、不对称信息的存在，协商时往往要做出无数次的让步或要提出无数的建议与反建议也不能达到满意的协商效果，从而使得协商的效率非常低下。因此怎样提高电子商务中自动协商效率是一个关键的问题[1-2]。

针对于这一问题，本文将改进的遗传算法(IGA，Improved Genetic Algorithm)应用于竞争环境下电子商务的双边多议题协商当中，来提高agent协商的效率。多种实验证明，改进的遗传算法在求解竞争环境下双边多议题协商的时候效率更高一些。

1 问题

在竞争环境下基于智能体的电子商务环境当中[3]，智能体在自动协商的时候都是追求自身利益的最大化[4-5]。但是智能体之间的利益往往是相互冲突的，这就带来一个问题，如何在协商过程中，或者说在协商解的空间当中找出一个协商双方整体利益最大化同时又尽量满足双方各自利益的最优解是电子商务中一个关键的问题[6]。

下面以基于智能体的电子商务当中双边多议题协商为例说明这一问题[7]。在双边多议题协商当中，买方智能体a和卖方智能体b的效用函数为

(1)

其中i表示智能体a或b，j表示议题。

为了求得协商双方的最优解，许多应用当中都采用求下式的最大值作为衡量条件[8]

(2)

这个判断条件追求的是双方智能体整体利益的最大化，适合于电子商务当中协商双方关系是合作的情况，比如一个公司的两个子公司进行协商的时候可以用公式(2)找出最优解。

但是在竞争的电子商务环境下,对于单个智能体而言，他们追求的是个体利益的最大化，而不是整体利益的最大化。这时如果仅仅使用公式(2)来确定协商双方效用的话，往往不能达到公平的目的。例如，有两个竞争类型的智能体，分别对于一个商品的价格(用x表示)和付款日期(用y表示)进行协商。价格区间为10～110元(最小让步价格是10元)，付款时间从1～11 d(最小让步是1 d)。买方智能体a两个议题的权重分别为0.6和0.4；卖方智能体b两个议题的权重分别为0.9和0.1；卖方智能体b的初始出价是(110元，11 d)；买方智能体a的初始出价是(10元，1 d)。

这时如果按照傅亏等[8]的方法，采用公式(2)的最大值查找协商的最优结果的话，可以得出(x=9,y=1)时f(Ua,Ub)具有最大值0.374 4。此时卖方智能体的效用为0.72而买方智能体的效用为0.52。这显然对于买方智能体是不能接受的，因为它比卖方智能体的效用少了20个百分点(20 %)。也就是说这样的协商结果对于买方智能体来说“不太公平”，违反了电子商务公平交易的原则[9-10]。

2 本文的求解模型

2.1 本文的求解机制

针对于上一节所提出的问题，本文的解决方案如下：

在寻找双方智能体协商的最优解的时候，应该同时满足两个约束条件。

1) 双方智能体的满意度(或效用)相等或相近，这样才算公平，即

|Ua-Ub|≤k

(3)

2) 双方整体利益最大化，这样才能尽最大努力保证双方各自利益最大化。这一点和文献[8]一样，可以用公式(2)来表示。

以上文给出的例子为例，采用本文的解决方案(k=0.05)，可以得出(x=7,y=3)时f(Ua,Ub)的值为0.33。此时卖方智能体的效用为0.55而买方智能体的效用为0.60。这样的协商结果，虽然双方整体效用有所降低，但是双方的满意度差只有5个百分点(0.05)。这样的协商结果协商双方应该是可以接受的，体现了“公平”原则。

2.2 本文的求解方法

本文采用改进的遗传算法IGA来求解竞争环境下双边多议题协商的最优解。遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，具有良好的全局搜索能力。但是标准的遗传算法(SGA，Standard Genetic Algorithm)在求解问题的时候容易造成早熟和局部收敛现象[11]。针对于这一问题，本文在求解竞争环境下双边多议题协商问题遗传算法的时候，采用了两种方法同时对遗传算法进行改进。

一方面，在遗传算法的第七步中借鉴了模拟退火算法的Metropolis准则。以一定的概率接受恶化解，从而使遗传算法具有更强的逃脱局部极值和避免过早收敛的全局优化能力，遗传算法的这种改进称为基于Metropolis准则的遗传算法(MGA, Genetic Algorithm based on Metropolis)。接受准则为Metropolis准则

其中df为新生成的染色体适应度与父个体染色体适应度之差,t为退火过程的控制参数。

另外，在标准遗传算法中，采用固定的交叉和变异概率，也容易造成早熟和局部收敛。为了避免陷于局部最优，种群中的个体在整个遗传过程中，要保持解的多样性。这里对Pc和Pm采用自适应的选择的策略，具体描述如下。

(4)

变异概率Pm如下

(5)

其中pc1,pc1,pm1,pm1为小于1且大于零的参数。

这种遗传算法的改进称为自适应遗传算法(AGA, Adaptive Genetic Algorithm)。

3 实 验

3.1 实验数据

设置双边多议题竞争协商中的议题数量为4个。为每一个议题定义它的意义和取值范围。以商品买卖协商为例，设置以下4个议题及取值范围。① 商品价格: 1 000～1 150 (元)。② 商品数量：100～200 (件)。③ 交付期：5～12 (天)。④ 保质期：1～16(月)。

每个agent 都初始化自己的权重，使得所有权重之和为1。并且agent 彼此之间不知道对方议题的权重。买方agenta和卖方agentb的权重如下

买方agenta和卖方agentb的效用计算公式采用公式(1)的计算方法。

3.2 实验过程

3.2.1 编码与解码 针对于本文电子商务的实际情况，本文采用二进制编码的方法，对于实验中的四个议题具体编码和解码如下：

1)第一个议题：商品价格: 1 000～1 150(元)。

对于该议题，采用二进制编码的方法来进行。但需要考虑精度。对于给定区间[x,y]，设采用二进制编码长度为n，则任何一个变量可以表示为

x=x+x1×(y-x)/2+x2×(y-x)/22+

…+xn×(y-x)/2n

(6)

对应一个二进制编码x1x2…xn。二进制编码与实际变量的最大误差为(y-x)/2n。

针对于本议题，将区间[1 000,1 150]进行32等分，因此可以采用5位二进制编码的形式，即00000-11111来表示。这样表示的最大误差为

ω=(1 150-1 000)/25=4.687 5元

解码的过程是编码的逆过程。

2)第二个议题: 商品数量：100～200 (件)。采用4位二进制编码，0000-1111。编码与解码方法与议题一是一样的，这里不再赘述，以下类同。

3)第三个议题：交付期：5～12 (天)；采用3位二进制编码：000-111;

4)第四个议题：保质期：1～16 (月)。采用4位二进制编码：0000-1111;

以上四个议题加起来，总共需要用16位二进制来表示。在实验中，采用一个无符号整型变量就足可以表示了。因为一个整型变量占用四个字节，32位。例如，编码0001011111100000表示1 010元；194件；11天；1月。

3.2.2 形成初始群体 采用随机的方法产生初始群体，即随机生成一组任意排列的字符串。群体中的个体数目是固定的，种群规模一般在L-2L之间(L为编码长度)。因为本实验染色体的长为16，所以我们选择种群的数量为20。但是这里所选择的20个初始群体都必需满足后面的约束条件，以表现出竞争环境下的协商。

3.2.3 计算适应度 适应度函数依然采用公式(2)作为适应度函数。

3.2.4 父个体的选取 采用轮盘赌的方法进行父个体的选取，个体被选中的概率与其在群体中相应适应函数值成正比，算法以此概率分布从群体中随机选取两个不同的染色体作为两个父个体。

3.2.5 交叉 交叉规则采用双亲双子法，交配位为随机取位。该方法在双亲个体确定后，以一个随机位进行位之后的所有基因对换，对换后形成两个孩子后代，交叉概率如公式(4)所示。

3.2.6 变异 在算法中设置变异。变异位取反，由0变为1，或由1变为0，变异概率Pc如公式(5)所示。

3.2.7 种群进化方法 种群进化时采用模拟退火算法中的Metropolis准则，方法如下：

df=孩子个体适应值-群体中最小的个体适应值；如果孩子个体与群体中的个体不重复且满足((df>0) or (exp (df/t)>random))条件，那么替换适应值最小的个体。

另外一个孩子替换群体中适应值倒数第二的个体实现过程类似。t为退火过程的控制参数。t的初值为0.95，控制参数的衰减函数t(k+1)=λ*t(k)， 取λ=0.9。

3.2.8 终止 重复以上3.2.3～3.2.7步，当发现算法在50次算法迭代后再也无法改进性能，也就是适应值没有变化时，则停止计算，算法结束。这时认为算法达到了满意的结果。

3.2.9 约束条件 在以上改进的遗传算法当中，所有选择的个体都必需要满足以下约束条件：

1) 协商双方智能体的效用之差小于0.05。这一点表现出竞争环境下的协商必需要协商双方效用相近或相等，也只有这样才能表现电子商务竞争环境下的“公平”。

2) 协商任何一方智能体的效用值必需要大于0.5。这一点表现出智能体自身的利益。

3.3 实验结果与分析

在实验中，分别对于标准遗传算法SGA、基于Metropolis准则的遗传算法MGA、自适应遗传算法AGA和改进的遗传算法IGA各进行了1 000次的实验，结果表明SGA平均需要360次才能达到协商的满意解，MGA平均需要230次才能达到满意解，AGA平均需要207次才能达到满意解，而IGA平均需要151次就可以达到协商的满意解。这说明本文算法的优越性。

在这个实验当中，由于两个智能体处于竞争的环境当中，所以要求两个智能体的效用之差(或满意度之差)要小于0.05，也就是说ΔU<0.05。图1是SGA搜索最佳协商结果的过程，图2是MGA搜索最佳协商结果的过程，图3是AGA搜索最佳协商结果的过程，图4是IGA算法搜索最佳协商结果的过程。图5是前面4种算法达到协商满意结果时效率的比较。5个图中的实验数据都是1 000次实验的平均值，并且每迭代20次记录一次。

最终的协商解为：1 000元；194件；10天；1月。这时适应度为0.455 6，Ua=0.67，Ub=0.68，Ua与Ub之差ΔU=0.01。从这个实验结果可以看出，IGA算法要比其它几种GA算法在达到同样的协商结果时效率要高一些。

图1 SGA算法搜索最佳结果的过程

图2 MGA算法搜索最佳结果的过程

图3 AGA算法搜索最佳结果的过程

图4 IGA算法搜索最佳结果的过程

图5 四种遗传算法搜索最佳结果的对比

4 结 论

在基于智能体的电子商务当中，智能体协商的研究一直是一个热门话题。这其中一个关键问题是如何使得协议双方都最大限度地达到协商的满意解，甚至最优解，并且提高协商的效率。针对于这一问题，提出了一种竞争环境下的双边多议题协商模型，并且将改进的遗传算法IGA应用于这种模型当中，来提高模型中agent协商的效率。实验证明，这种方法可以快速、精确地为协商双方提供比较好的协商解。

参考文献：

[1] 孔宁红. 电子商务对传统会计的冲击和影响[J]. 中山大学学报：自然科学版，2003,42(S):259-260.

[2] 李艳会，朱思铭.一类电子商务网站竞争模型分析[J]. 中山大学学报：自然科学版，2003,42(5): 6-10.

[3] KEBRIAEI H, MAJD V J, RAHIMI K A. A new agent matching scheme using an ordered fuzzy similarity measure and game theory J]. Computational Intelligence, 2008, 24(2): 108-121.

[4] LIN R, KRAUS S, WILKENFELD J, et al. Negotiating with bounded rational agents in environments with incomplete information using an automated agent [J]. Artificial Intelligence, 2008, 172(4)：823-851.

[5] LAU, RAYMOND Y K. Towards a web services and intelligent agents-based negotiation system for B2B e-commerce [J]. Electronic Commerce Research and Applications, 2007, 6(3): 260-273.

[6] KRAUS S, HOZ W P, WILKENFELD J, et al. Resolving crises through automated bilateral negotiations [J]. Artificial Intelligence, 2008, 172(1):1-18.

[7] WANG Y, LIN K J. Reputation-oriented trustworthy computing in e-commerce environments [J]. IEEE Internet Computing, 2008, 12(4): 55-59.

[8] 傅亏,聂规划，高新亚. 基于混合遗传算法的电子市场双边协商求解[J].武汉理工大学学报,2007, 29(3): 138-141.

[9] GALIN A, GROSS M, GOSALKER G. E-negotiation versus face-to-face negotiation what has changed - if anything [J]. Computers in Human Behavior, 2007, 23(1): 787-797.

[10] 谢黎明, 余丰人, 丘海明. 基于混合遗传算法的多约束组播路由问题的求解 [J]. 中山大学学报:自然科学版，2005, 44(2): 45-48.

[11] 许义海, 李晓东. 一种快速寻优的新型改进遗传算法 [J]. 中山大学学报:自然科学版，2006,45(2): 36-40.