【作者】 童向荣；

【导师】 黄厚宽；

【作者基本信息】 北京交通大学 ， 计算机应用技术， 2010， 博士

【摘要】 在大规模开放环境中,Agent不可避免地要与其它Agent反复交互以实现其合作求解目标,因而每个Agent都会形成自己的历史交互。智能Agent自然能够从中得到更多的信息和知识并将其应用于之后的交互中,优化多Agent的合作求解效果。在Agent理论中,信任与协商是两个基本问题。信任是合作求解的前提和基础,协商是合作求解的基本方法,因而信任和协商关系密切。信任计算是一个有意义的研究方向,它能够保证软件Agent在大规模开放环境中的良好交互。不完全信息条件下的多议题协商一直是多Agent系统合作求解研究的一个至关重要又有挑战性的课题,一直是众多学者关注的焦点之一。然而,多Agent合作求解中的信任与协商问题至今没有得到很好的解决,存在一些可以继续改进的地方。从多Agent的交互历史中学习,得到信任计算和协商优化方法,正是本文研究的动机。关于多Agent合作求解中的信任与协商研究,主要存在以下问题。目前Agent信任研究大多是基于概率论以平均交互成功率来计算,较少考虑信任动态变化,因而信任的准确预测和异常行为的检测能力不能令人满意。另外,很少有工作致力于长期联盟信誉的研究。而且开放网络环境中存在着大量不精确和不完全信息,导致信任计算置信度不高,如何提高信任的应对噪声能力仍然需要进行探讨。在目前不完全信息条件下的Agent多议题协商中,最优回价策略一般采用间接学习对手偏好的方式,尚不能令人满意,而实际上Agent一般拥有或多或少的协商经验和领域知识,目前这些经验和知识都未得到很好的利用。多议题协商中效用函数的选择一直没有得到应有的重视,很多学者采用了线性的效用函数,这导致了在计算Agent的协商效用时涵盖范围较小。本文针对以上问题开展工作,主要工作如下:(1)提出了一种Agent动态交互信任计算模型。以概率论为工具,按时间分段交互历史信息,结合信任的变化率,给出信任计算的置信度和异常行为检测机制。实验以网上电子商务为背景,实验结果表明预测误差比TRAVOS少一倍,计算量也较少;改进了Jennings等人关于Agent信任的工作。(2)提出了一种Agent长期联盟信誉模型LCCM。还给出了联盟信誉与联盟收益之间的关系函数。实验结果表明LCCM能够有效地计算联盟信誉,并能反映不同参数对联盟信誉的影响。(3)提出了一种不完全信息条件下基于案例和对策论的Agent多议题Pareto最优协商模型。当案例库规模控制在一定范围内时低于Fatima工作的计算复杂度。实验结果表明该协商模型能够取得更优的效用和更短的达成一致时间。改进了Fatima等人的工作。(4)将多议题协商的效用函数由线性扩展为非线性,基于Sigmoid函数提出了一种改进的符合边际效用递减原理的效用函数,给出了一种两阶段多资源配置协商模型和可行的算法。其算法的计算复杂度为多项式级。实验结果显示该模型的优化效率高于其它协商模型和算法。更多还原

【Abstract】 Generally, there are iterative interactions among agents in large open environment. So each agent usually forms its own interaction history. Sequentially, intelligent agent would derive some useful information and knowledge from history data to be reused in the future for optimizing the performance of interactions.Trust and negotiation are two important problems in cooperative solving of multi-agent systems. Trust is the base of cooperative solving and negotiation is a basic method of cooperative solving. So it is necessary to research on trust and negotiation together. Computation of trust is an interesting direction in multi-agent systems, for good trust relationship would guarantee the success of the future interactions in large open environment. Furthermore, multi-issue negotiation with incomplete information is always an important and challenging problem in cooperative solving. Unfortunately, trust and negotiation have not been resolved ideally up to now. It is the motivation of this dissertation to obtain optimal methods of trust and negotiation from the history of interactions.There are some shortages in the researches of trust and negotiation of multi-agent systems.Previous work on trust is only based on the average probability of historical interactions and there is a lack of attention to dynamic variety of agent trust. So the ability of precise prediction of trust and abnormal behavior detection is not satisfied. Few studies have been done on agent coalition credit to this day and there is a need to investigate it in detail. Furthermore, there are lots of imprecise and lying information in large open environment, which leads to a low confidence of trust computation.Previous work on multi-issue negotiation usually uses indirect approaches to acquire the preferences of the opponent such as a variety of data mining methods. On the other hand, agents usually have some negotiation experiences and domain knowledge which may help them get better negotiation results. Furthermore, the choice of utility functions has not been paid more attention to. Previous papers mostly adopted linear utility functions which is not widely used in most circumstances.To this end, this dissertation introduces the followings.(1) We propose a computational model of agent dynamic interaction trust (CMAIT), where interaction history is divided by time. Sequentially, based on the first derivative of trust, we give the confidence of computational information and that of computational deviation of CMAIT. The mechanism of abnormal behavior’s detection of CMAIT is also given. We conduct Experiments on E-commerce at taobao website. Experimental results demonstrate that the computational error of CMAIT is half of that of TRAVOS model and its computational complexity is also lower than TRAVOS model. It improves the work of Jennings on agent trust.(2) We present a long-term coalition credit model (LCCM). Sequentially, the relationship between coalition credit and coalition payoff is also given. Generalization of LCCM can be demonstrated through experiments applied in both cooperative and competitive environment. Experimental results show that LCCM is capable of coalition credit computation efficiently and can properly reflect the effect of various factors on coalition credit.(3) We propose an agent multi-issue negotiation model under incomplete information based on cases and game theory. The computational complexity of the proposed algorithm is polynomial order and it is commonly lower than that of Fatima, as long as the scale of cases base is limited to a bounded quantities. Experimental results indicate that the utility and the reaching time of our experiments have an advantage of that of human beings and the method of Lin. It improves the work of Fatima.(4) We expand linear utility function to a nonlinear one. Particularly, we propose an improved utility function based on sigmoid function in neural network, according to the principle of marginal utility decreasing. Sequentially, we present a negotiation model over multiple divisible resources with two phases, as well as its feasible algorithm. The computational complexity of this model is polynomial order. Experimental results show that the optimal efficiency of this model takes an advantage over the previous work.更多还原