搜索
第30卷第11期电子与信息学报Vol.30No.112008年11月JournalofElectronics&InformationTechnologyNov..2008一种竞争环境下基于自适应遗传算法的多边多议题协商李剑①景博②杨义先①①(北京邮电大学网络与交换技术国家重点实验室信息安全中心北京100876)②(北京应用气象研究所计算机室北京100029)摘要：为了提高竞争环境下基于智能体电子商务多边多议题协商当中agent协商的效率，该文提出了一种竞争环境下agent的协商模型，并且将自适应遗传算法AGA应用于该模型当中，来提高模型中agent协商的效率。在实验中，分别对于两种遗传算法即：标准遗传算法SGA和自适应遗传算法AGA各进行了1000次的实验。结果表明同样达到协商满意解的时候，SGA平均需要183次协商，而AGA平均需要152次协商。这个结果说明，在求解竞争环境下多边多议题协商问题的时候，自适应遗传算法AGA可以使得协商当中的agent高效达到协商的满意解。关键词：电子商务；智能体；多边多议题协商；自适应遗传算法中图分类号：TP301文献标识码：A文章编号：1009-5896(2008)11-2613-04AnAdaptiveGeneticAlgorithmandItsApplicationtoMulti-literalMulti-issueCompetitiveE-commerceLiJian①JingBo②YangYi-xian①①(InformationSecurityCenter,StateKeyLabofNetworkandSwitchingTechnology,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)②(Dept.ofComputerTechnology,BeijingInstituteofAppliedMeteorology,Beijing100029,China)Abstract:Tomaketheagentsnegotiatemoreefficientlyinmulti-lateralmulti-issuenegotiationinmulti-agentbasedcompetitivee-commerce,anagentnegotiationmodelincompetitiveenvironmentispresented,andtheAdaptiveGeneticAlgorithm(AGA)isappliedtothemodeltoenhancethenegotiationefficiency.Intheexperiments,twokindsofgeneticalgorithmsareusedtocomparewith,theyareStandardGeneticAlgorithm(SGA)andAGA.After1000timesofexperimentsforthetwokindsofagentstogainthesatisfyingresult,SGAaveragelyneedsnegotiationof183runs,whiletheAGAaveragelyneedsonly152runs.TheexperimentresultsshowthattheAGAcangainthesatisfyingnegotiationresultmoreefficientlythanSGAincompetitivemulti-lateralmulti-issuenegotiation.Keywords:E-commerce;Agent;Multi-lateralmulti-issuenegotiation;Adaptivegeneticalgorithm1引言在基于多智能体的电子商务系统中[1]，通常需要自治的agent之间进行自动协商[2]。但是由于智能体自身的不完全、不对称信息的存在，协商时往往要做出无数次的让步或要提出无数的建议与反建议也不能达到满意的协商效果，从而使得协商的效率非常低下[3]。因此怎样提高电子商务中智能体自动协商效率是一个关键的问题[4,5]。针对于这一问题，本文将自适应遗传算法AGA(AdaptiveGeneticAlgorithm)应用于竞争环境下电子商务的多边多议题协商当中[6,7]，来提高agent协商的效率。实验证明，自遗传算法在求解竞争环境下多边多议题协商的时候效率更高一些。2008-07-09收到，2008-09-10改回国家“973”计划项目(2007CB310704)和国家自然基金重点项目(90718001)资助课题2问题的提出与相关工作在竞争环境下基于智能体的电子商务环境当中[8]，智能体在自动协商[9]的时候都是追求自身利益的昀大化。但是智能体之间的利益往往是相互冲突的[10]，这就带来一个问题，如何在协商过程中，或者说在协商解的空间当中找出一个协商各方整体利益昀大化同时又尽量满足智能体各自利益昀大化是电子商务中一个关键的问题[11]。下面以基于智能体电子商务当中多边多议题协商为例说明这一问题。在多边多议题协商当中，个体智能体的效用函数如式(1)所示。iU=1()Niiijjjjwvx=∑(1)在式(1)中i表示智能体，j表示议题。为了求得协商各方的昀优解，许多应用当中都采用求式(2)的昀大值作为衡量条件。2614电子与信息学报第30卷121211(,,,)==(())NMMMMMMjjjijfUUUUUUwvx==×××∑∏(2)这个判断条件追求的是各方智能体整体利益的昀大化，适合于电子商务当中协商各方关系是合作的情况，比如一个公司的多个子公司进行协商的时候可以用式(2)找出昀优解。但是在竞争的电子商务环境下，对于单个智能体而言，他们追求的是个体利益的昀大化，而不是整体利益的昀大化。这时如果仅仅使用式(2)来确定协商各方效用的话，往往不能达到公平的目的。例如，有两个竞争类型的智能体，分别对于一个商品的价格(用x表示)和付款日期(用y表示)进行协商。价格区间为10元到110元(昀小让步价格是10元)，付款时间从1天到11天(昀小让步是1天)。买方智能体a两个议题的权重分别为0.6和0.4；卖方智能体b两个议题的权重分别为0.9和0.1；卖方智能体b的初始出价是(110元，11天)；买方智能体a的初始出价是(10元，1天)。这时如果按照文献[12]中的方法，采用式(2)的昀大值查找协商的昀优结果的话，可以得出(x=9,y=1)时(,)abfUU具有昀大值0.3744。此时卖方智能体的效用为0.72而买方智能体的效用为0.52。这显然对于买方智能体是不能接受的，因为它比卖方智能体的效用少了20个百分点(0.20)。也就是说这样的协商结果对于买方智能体来说“不太公平”，违反了电子商务公平交易的原则。3本文的求解模型3.1本文的求解机制针对上一节所提出的问题，本文的解决方案如下：在寻找多个智能体协商的昀优解的时候，应该同时满足两个约束条件。(1)任意两个智能体的满意度(或效用)相等或相近，这样才算公平。=abUUk−(3)(2)各方整体利益昀大化，这样才能尽昀大努力保证智能体各自利益昀大化。这一点和文献[12]一样，可以用式(2)来表示。以上文给出的例子为例，采用本文的解决方案(k=0.05)，可以得出(x=7,y=3)时(,)abfUU的值为0.33。此时卖方智能体的效用为0.55而买方智能体的效用为0.60。这样的协商结果，虽然双方整体效用有所降低，但是双方的满意度差只有5个百分点(0.05)。这样的协商结果协商双方应该是可以接受的，体现了“公平”原则。3.2本文的求解方法本文采用自适应遗传算法AGA来求解竞争环境下多边多议题协商的昀优解。遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，具有良好的全局搜索能力[13]。但是标准的遗传算法SGA(StandardGeneticAlgorithm)在求解问题的时候容易造成早熟和局部收敛现象[14]。针对于这一问题，本文在求解竞争环境下多边多议题协商问题遗传算法的时候，采用了自适应遗传算法来对问题进行求解[15]。在标准遗传算法中，采用固定的交叉和变异概率，容易造成早熟和局部收敛。为了避免陷于局部昀优，种群中的个体在整个遗传过程中，要保持解的多样性。这里对cP和mP采用自适应的选择的策略。交叉概率cP和变异概率mP选择不当会造成早熟，cP和mP越大，则算法的搜索能力越强，个体适应度波动越大；反之，cP和mP越小，个体适应度比较平稳。SGA采用固定的cP和mP，易造成早熟和局部收敛。而AGA对cP和mP采用自适应选择的策略，具体描述如下。设maxf和f分别为群体的昀大适应度和平均适应度，f′为两个交叉个体适应度的较大值，f为变异个体的适应度。自适应遗传算法的遗传概率cP(也称交叉概率)如下：121max1()(),,cccccppffpffffPpff⎧′⎪−−⎪′−≥⎪⎪−=⎨⎪⎪′⎪⎪⎩(4)变异概率mP如下：12max1max1()(),,mmmmmppffpffffPpff⎧−−⎪⎪−≥⎪⎪−=⎨⎪⎪⎪⎪⎩(5)其中1212,,,ccmmpppp为小于1，大于零的参数。在同一代中，对于不同的个体赋予不同的cP和mP，适应度高的个体应给予保护，cP和mP相应减少，而适应度低的个体应该增大cP和mP。这样在每一代群体以及群体中的每个个体都有不同的cP和mP，实现了参数的自适应选取。这种遗传算法的改进称为自适应遗传算法。4实验4.1实验数据在实验中设置3个竞争类型的智能体对4个议题进行协商。为每一个议题定义它的意义和取值范围。以商品买卖协商为例，设置以下4个议题及取值范围。(1)商品价格:1000-1150(元)。(2)商品数量：100-200(件)。(3)交付期：5-12(天)。(4)保质期：1-16(月)。每个agent都初始化自己的权重，使得所有权重之和为1。并且agent彼此之间不知道对方议题的权重。3个竞争类型的智能体卖方agent1，买方agent2和库存方agent3的权重如表1所示：表14个智能体的权重信息议题agent1agent2agent3agent410.26(大)0.15(大)0.21(小)0.38(小)20.18(小)0.34(小)0.29(大)0.19(大)30.16(小)0.09(大)0.34(小)0.41(大)第11期李剑等：一种竞争环境下基于自适应遗传算法的多边多议题协商2615表中(大)表示该议题越大对于该智能体越有利，表中(小)表示该议题值越小对于该智能体越有利。3个智能体的效用计算公式采用式(1)的计算方法。4.2实验过程步骤1编码与解码针对于本文电子商务的实际情况，本文采用二进制编码的方法，对于实验中的4个议题具体编码和解码如下：(1)第1个议题：商品价格：1000-1150(元)。对于该议题，采用二进制编码的方法来进行。但需要考虑精度。对于给定区间[a,b]，设采用二进制编码长度为n，则任何一个变量可以表示为212()/2()/2()/2nnxaabaabaaba=+×−+×−++×−(6)对应一个二进制编码12naaa。二进制编码与实际变量的昀大误差为()/2nba−。针对于本议题，我们将区间[1000,1150]进行32等分，因此可以采用5位二进制编码的形式，即：00000-11111来表示。这样表示的昀大误差为5(11501000)/2ω=−=4.6875元解码的过程是编码的逆过程。(2)第2个议题:商品数量：100-200(件)。采用4位二进制编码，0000-1111。编码与解码方法与议题一是一样的，这里不再赘述，以下类同。(3)第3个议题：交付期：5-12(天)；采用3位二进制编码：000-111;(4)第4个议题：保质期：1-16(月)。采用4位二进制编码：0000-1111;以上4个议题加起来，总共需要用16位二进制来表示。在实验