任子仪
烟台大学计算机与控制工程学院 烟台 264005
基金项目:国家自然科学基金(62072392，61972360)，山东省重大科技创新工程项目(2019JZZY020131)
详细信息
作者简介:童向荣：男，1975年生，博士，教授，主要研究方向为多Agent系统、分布式人工智能、数据挖掘
任子仪：女，1994年生，硕士生，研究方向为联盟结构生成和数据挖掘
通讯作者:童向荣 xr_tong@163.com
中图分类号:TP18计量
文章访问数:379
HTML全文浏览量:165
PDF下载量:35
被引次数:0
出版历程
收稿日期:2020-06-23
修回日期:2020-12-26
网络出版日期:2021-02-06
刊出日期:2021-07-10
Coalition Structure Generation Constrained by Trust and Utility Relationship
Xiangrong TONG,,Ziyi REN
School of Computer and Control Engineering, Yantai University, Yantai 264005, China
Funds:The National Natural Science Foundation of China (62072392,61972360), Shandong Province Major Science and Technology Innovation Project (2019JZZY020131)
摘要
摘要:联盟结构生成是分布式人工智能的重要研究内容，一般仅依据智能体效用生成任意数量的联盟，这导致最优联盟结构生成的计算复杂度NP难。实际上，信任是合作的基础，信任关系对最终效用有直接的影响，应该综合考虑信任和效用关系。针对以上问题，该文扩展效用约束为信任和效用约束，用信任和效用二元组表示，以此作为联盟结构生成的依据。借鉴图割的s-t-cut算法，研究了基于信任和效用关系的联盟结构生成，在保证智能体个体理性和联盟稳定(无块)的前提下，使用信任和效用关系对网络进行切割，从而形成联盟。由此，该文提出了两种多项式时间的精确算法：信任关系约束下的MT-s-t-cut算法和信任效用关系约束下的MTU-s-t-cut算法，这两种算法均能够在多项式时间内得到最优联盟结构。仿真实验验证了信任关系影响所形成的联盟结构，社会整体效用随智能体数量的增加而增加，并且算法的运行时间远小于动态规划法(DP)和ODP-IP算法。
关键词:联盟结构生成/
信任效用关系/
信任传递/
图割
Abstract:The coalition structure generation is an important domain of distributed artificial intelligence. Most coalition formation models are only based on the utility, and any number of coalitions are permitted, which makes it be NP complexity difficult to generate the optimal coalition structure. Actually, Trust is the base of cooperation and has direct effect on the final utility. So, not only utility but also trust relationship should be seriously considered. To this end, the utility constraint is extended to trust and utility constraint, a two-tuples is used to represent utility and trust, which is the base of coalition structure generation. Inspired by the classic s-t-cut algorithm for graph cut, coalition structure generation constrained by trust and utility relationship is investigated. Assuming that individual rationality of agents and the stability of coalition (there is no block) is satisfied, the network is cut by the relationship of utility and trust to formation coalitions. The proposed algorithms of coalition structure generation named MT-s-t-cut and MTU-s-t-cut (Trust s-t-cut) can output the optimal coalition structure in polynomial time. The results of simulated experiments show that the social utility increases with the number of agents, and the running time of the algorithms are far less than that of Dynamic Programming (DP) and Optimal Dynamic Programming and Integer Partition (ODP-IP) algorithms.
Key words:Coalition structure generation/
Trust utility relationship/
Trust transitivity/
Graph cut
PDF全文下载地址:
https://jeit.ac.cn/article/exportPdf?id=90d85537-f539-464f-a584-585b07e37c4b
