高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

信任和效用关系约束的联盟结构生成

童向荣 任子仪

童向荣, 任子仪. 信任和效用关系约束的联盟结构生成[J]. 电子与信息学报. doi: 10.11999/JEIT200509
引用本文: 童向荣, 任子仪. 信任和效用关系约束的联盟结构生成[J]. 电子与信息学报. doi: 10.11999/JEIT200509
Xiangrong TONG, Ziyi REN. Coalition Structure Generation Constrained by Trust and Utility Relationship[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT200509
Citation: Xiangrong TONG, Ziyi REN. Coalition Structure Generation Constrained by Trust and Utility Relationship[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT200509

信任和效用关系约束的联盟结构生成

doi: 10.11999/JEIT200509
基金项目: 国家自然科学基金(62072392,61972360),山东省重大科技创新工程项目(2019JZZY020131)
详细信息
    作者简介:

    童向荣:男,1975年生,博士,教授,主要研究方向为多Agent系统、分布式人工智能、数据挖掘

    任子仪:女,1994年生,硕士生,研究方向为联盟结构生成和数据挖掘

    通讯作者:

    童向荣 xr_tong@163.com

  • 中图分类号: TP18

Coalition Structure Generation Constrained by Trust and Utility Relationship

Funds: The National Natural Science Foundation of China (62072392,61972360), Shandong Province Major Science and Technology Innovation Project (2019JZZY020131)
  • 摘要: 联盟结构生成是分布式人工智能的重要研究内容,一般仅依据Agent效用生成任意数量的联盟,这导致最优联盟结构生成的计算复杂度NP难。实际上,信任是合作的基础,信任关系对最终效用有直接的影响,应该综合考虑信任和效用关系。针对以上问题,该文扩展效用约束为信任和效用约束,用信任和效用二元组表示,以此作为联盟结构生成的依据。借鉴图割的s-t-cut算法,研究了基于信任和效用关系的联盟结构生成,在保证Agent个体理性和联盟稳定(无块)的前提下,使用信任和效用关系对网络进行切割,从而形成联盟。由此,该文提出了两种多项式时间的精确算法:信任关系约束下的MT-s-t-cut算法和信任效用关系约束下的MTU-s-t-cut算法,这两种算法均能够在多项式时间内得到最优联盟结构。仿真实验验证了信任关系影响所形成的联盟结构,社会整体效用随Agent数量的增加而增加,并且算法的运行时间远小于DP和ODP-IP算法。
  • 图  1  不同联盟结构的效用

    图  2  Agent信任网络

    图  3  2-联盟核成员

    图  4  信任网络

    图  5  |A|对社会福利的影响

    图  6  两种算法的Agent数量与运行时间的关系

    图  7  算法运行时间对比

    图  8  工作量对比

    图  9  前4种算法时间对比

    图  10  与CSG-UCT算法对比

     MT-s-t-cut算法
     输入:$G = < A,E,\omega ,\rho > $
     输出:${C_1},{C_2}$
     //(1) 计算传递概率和效用
     For all Agent ${a_i},{a_j} \in A$
        ${P_{ij}}$,$\varOmega {}_{ij}$
     Endfor
     //(2) 进行图割生成CS
     For all Agent $ {a}_{s},{a}_{t}\in A $
       Do
         while exist a path p from $ {a}_{s} $ to $ {a}_{t} $ in the residual
     network Gf
         Do
           ${\rm{cf}}\left( p \right){\rm{ }} \leftarrow {\rm{min}}\left\{ {{\rm{cf}}\left( {{a_i},{a_j}} \right)|\left( {{a_i},{a_j}} \right){\rm{ in }}\;p} \right\}$
           For each edge $ < {a_i},{a_j} > $ in p
             ${P_{ij}} \leftarrow {P_{ij}} - {\rm{cf}}(p)$
             ${P_{ji}} \leftarrow {P_{ji}} + {\rm{cf}}(p)$
           Endfor
         EndDo
         If $(V({C_1}) + V({C_2})) < (V(C) + V(C'))$ then
           ${C_1} \leftarrow C,{C_2} \leftarrow C'$
         Endif
       EndDo
     Endfor
    下载: 导出CSV
     MTU-s-t-cut算法
     输入:$G = < A,E,\omega ,\rho > $
     输出:${C_1},{C_2}$
     //(1) 计算传递概率和效用
     For all Agent $ {a}_{s},{a}_{t}\in A $
        ${P_{ij}}$,$\varOmega {}_{ij}$
     Endfor
     //(2) 计算信任效用关系
     For each edge $ < {a_i},{a_j} > \notin E$
       ${f_{\rho ,\omega }}({a_i},{a_j})$
     Endfor
     //(3) 进行图割生成联盟
     For all Agent $ {a}_{s},{a}_{t}\in A $
       Do
         while exist a path p from $ {a}_{s} $ to $ {a}_{t} $ in the residual
     network Gf
         Do
           ${\rm{cf}}\left( p \right){\rm{ }} \leftarrow {\rm{min}}\left\{ {cf\left( {{a_i},{a_j}} \right)|\left( {{a_i},{a_j}} \right){\rm{ in }}p} \right\}$
           For each edge $ < {a_i},{a_j} > $ in p
             ${f_{\rho ,\omega }}({a_i},{a_j}) \leftarrow {f_{\rho ,\omega }}({a_i},{a_j}) - {\rm{cf}}(p)$
             ${f_{\rho ,\omega }}({a_j},{a_i}) \leftarrow {f_{\rho ,\omega }}({a_j},{a_i}) + {\rm{cf}}(p)$
           Endfor
         EndDo
         If ${\rm{SW}}({\rm{CS}}) < {\rm{SW}}({\rm{CS}}')$ then
            ${\rm{CS}} \to {\rm{CS'}}$
         Endif
       EndDo
     Endfor
    下载: 导出CSV
  • [1] 智慧, 王飞跃, 黄子菊. 大规模MIMO系统中联合用户分组和联盟博弈的动态导频分配方案[J]. 电子与信息学报, 2020, 42(7): 1686–1693. doi:  10.11999/5EIT190445

    ZHI Hui, WANG Feiyue, and HUANG Ziju. Dynamic pilot allocation scheme for joint user grouping and alliance game in massive MIMO systems[J]. Journal of Electronics &Information Technology, 2020, 42(7): 1686–1693. doi:  10.11999/5EIT190445
    [2] CHANGDER N, AKNINE S, and DUTTA A. An imperfect algorithm for coalition structure generation, long abstract[C]. The Thirty-Third AAAI Conference on Artificial Intelligence, Hawaii, USA, 2019: 9923–9924. doi: 10.1145/1838206.1838342.(本条文献doi打不开, 请核对).
    [3] UEDA S, IWASAKI A, CONITZER V, et al. Coalition structure generation in cooperative games with compact representations[J]. Autonomous Agents and Multi-Agent Systems, 2018, 32(4): 503–533. doi:  10.1007/s10458-018-9386-z
    [4] GALLARDO J M, JIMÉNEZ N, and JIMÉNEZ-LOSADA A. Nontransferable utility games with fuzzy coalition restrictions[J]. Fuzzy Sets and Systems, 2018, 349: 42–52. doi:  10.1016/j.fss.2017.08.004
    [5] KARAKAYA M and KLAUS B. Hedonic coalition formation games with variable populations: Core characterizations and (im)possibilities[J]. International Journal of Game Theory, 2017, 46(2): 435–455. doi:  10.1007/s00182-016-0533-y
    [6] İNAL H. The existence of a unique core partition in coalition formation games[J]. Games and Economic Behavior, 2019, 114: 215–231. d. doi:  10.1016/j.geb.2019.01.009
    [7] DENG Yuan, SHEN Weiran, and TANG Pingzhong. Coalitional permutation manipulations in the gale-Shapley algorithm[C]. Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, Stockholm, Sweden, 2018: 928–936.
    [8] LIN Dianchao and JABARI S E. Transferable utility games based intersection control for connected vehicles[C]. 2019 IEEE Intelligent Transportation Systems Conference (ITSC), Auckland, New Zealand, 2019: 3496–3501.
    [9] RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition structure generation: A survey[J]. Artificial Intelligence, 2015, 229: 139–174. doi:  10.1016/j.artint.2015.08.004
    [10] 王海艳, 杨文彬, 王随昌, 等. 基于可信联盟的服务推荐方法[J]. 计算机学报, 2014, 37(2): 301–311. doi:  10.3724/SP.J.1016.2014.00301

    WANG Haiyan, YANG Wenbin, WANG Suichang, et al. A service recommendation method based on trustworthy community[J]. Chinese Journal of Computers, 2014, 37(2): 301–311. doi:  10.3724/SP.J.1016.2014.00301
    [11] SLESS L, HAZON N, KRAUS S, et al. Forming k coalitions and facilitating relationships in social networks[J]. Artificial Intelligence, 2018, 259: 217–245. doi:  10.1016/j.artint.2018.03.004
    [12] 童向荣, 张伟, 龙宇. Agent主观信任的传递性[J]. 软件学报, 2012, 23(11): 2862–2870. doi:  10.3724/SP.J.1001.2012.04303

    TONG Xiangrong, ZHANG Wei, and LONG Yu. Transitivity of Agent subjective trust[J]. Journal of Software, 2012, 23(11): 2862–2870. doi:  10.3724/SP.J.1001.2012.04303
    [13] WANG Xiaofeng, SU Jinshu, WANG Baosheng, et al. Trust description and propagation system: Semantics and axiomatization[J]. Knowledge-Based Systems, 2015, 90: 81–91. doi:  10.1016/j.knosys.2015.09.030
    [14] MAO Chengying, XU Changfu, and HE Qiang. A cost-effective algorithm for inferring the trust between two individuals in social networks[J]. Knowledge-Based Systems, 2019, 164: 122–138. doi:  10.1016/j.knosys.2018.10.027
    [15] KARGER D R. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm[C]. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, USA, 1993: 21–30. doi: 10.1145/313559.313605.(本条文献doi打不开, 请核对).
    [16] BRÂNZEI S and LARSON K. Coalitional affinity games[C]. Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, Budapest, Hungary, 2009: 1319–1320.
    [17] YEH D Y. A dynamic programming approach to the complete set partitioning problem[J]. Bit Numerical Mathematics, 1986, 26(4): 467–474. doi:  10.1007/BF01935053
    [18] MICHALAK T, RAHWAN T, ELKIND E, et al. A hybrid exact algorithm for complete set partitioning[J]. Artificial Intelligence, 2016, 230: 14–50. doi:  10.1016/j.artint.2015.09.006
    [19] WU Feng and RAMCHURN S D. Monte-Carlo tree search for scalable coalition formation[C]. Proceedings of the 29th International Joint Conference on Artificial Intelligence, Yokohama, Japan, 2020: 407–413.
  • [1] 李双明, 关欣, 衣晓, 吴斌.  用于异质信息的信任区间交互式多属性识别方法, 电子与信息学报. 2021, 43(0): 1-7. doi: 10.11999/JEIT200038
    [2] 欧静兰, 余欢欢, 吴皓威, 马锐, 王柳彬.  基于携能通信的非信任双向中继网络安全传输方案, 电子与信息学报. 2020, 42(12): 2908-2914. doi: 10.11999/JEIT200069
    [3] 徐军, 钟元生, 万树平.  一种集成直觉模糊信息的激励自适应信任模型, 电子与信息学报. 2016, 38(4): 803-810. doi: 10.11999/JEIT150750
    [4] 廖苗, 赵于前, 曾业战, 黄忠朝, 邹北骥.  基于图割和边缘行进的肝脏CT序列图像分割, 电子与信息学报. 2016, 38(6): 1552-1556. doi: 10.11999/JEIT151005
    [5] 韩祺祎, 任梦吟, 文红.  基于拓扑势的P2P社区推荐信任模型, 电子与信息学报. 2015, 37(6): 1279-1284. doi: 10.11999/JEIT141303
    [6] 龚卫华, 郭伟鹏, 杨良怀.  信任网络中多维信任序列模式挖掘方法研究, 电子与信息学报. 2014, 36(8): 1810-1816. doi: 10.3724/SP.J.1146.2013.01362
    [7] 谢晓兰, 刘亮, 赵鹏.  面向云计算基于双层激励和欺骗检测的信任模型, 电子与信息学报. 2012, 34(4): 812-817. doi: 10.3724/SP.J.1146.2011.00787
    [8] 蒋黎明, 张宏, 张琨, 徐建.  开放系统中一种基于模糊修正的证据信任模型, 电子与信息学报. 2011, 33(8): 1930-1936. doi: 10.3724/SP.J.1146.2011.00063
    [9] 李峰, 申利民, 司亚利, 穆运峰.  一种基于实体上下文和时间戳的信任预测模型, 电子与信息学报. 2011, 33(5): 1217-1223. doi: 10.3724/SP.J.1146.2010.01041
    [10] 喻莉, 李静茹, 刘祖浩.  基于自适应遗忘机制的半环信任模型, 电子与信息学报. 2011, 33(1): 175-179. doi: 10.3724/SP.J.1146.2010.00221
    [11] 朱云峰, 章毓晋.  直推式多视图协同分割, 电子与信息学报. 2011, 33(4): 763-768. doi: 10.3724/SP.J.1146.2010.00839
    [12] 杨明, 刘元安, 马晓雷, 李立.  一种基于定价与信任的网格资源分配算法, 电子与信息学报. 2010, 32(4): 846-851. doi: 10.3724/SP.J.1146.2009.00435
    [13] 蒋建国, 张国富, 齐美彬, 苏兆品.  基于离散粒子群求解复杂联盟的并行生成, 电子与信息学报. 2009, 31(3): 519-522. doi: 10.3724/SP.J.1146.2007.01593
    [14] 贾宇平, 杨威, 付耀文, 庄钊文.  一种基于度量层信息的基本信任分配构造方法, 电子与信息学报. 2009, 31(6): 1345-1349. doi: 10.3724/SP.J.1146.2008.01105
    [15] 纪俊杰, 阳小龙, 王进, 吴雄飚, 林建人, 隆克平.  基于信任关系的IP网络容错容侵机制, 电子与信息学报. 2009, 31(7): 1576-1581. doi: 10.3724/SP.J.1146.2008.00615
    [16] 张静, 胡捍英, 童珉, 李庆荣.  一种基于信任模型的安全度量及安全路由算法设计, 电子与信息学报. 2008, 30(1): 10-15. doi: 10.3724/SP.J.1146.2007.00726
    [17] 刘嘉, 王宏琦.  一种基于图割的交互式图像分割方法, 电子与信息学报. 2008, 30(8): 1973-1976. doi: 10.3724/SP.J.1146.2007.00075
    [18] 田春岐, 邹仕洪, 田慧蓉, 王文东, 程时端.  一种基于信誉和风险评价的分布式P2P信任模型, 电子与信息学报. 2007, 29(7): 1628-1632. doi: 10.3724/SP.J.1146.2006.00154
    [19] 田慧蓉, 邹仕洪, 王文东, 程时端.  P2P网络层次化信任模型, 电子与信息学报. 2007, 29(11): 2560-2563. doi: 10.3724/SP.J.1146.2005.01560
    [20] 张仕斌, 何大可, 遠藤誉.  模糊自主信任建立策略的研究, 电子与信息学报. 2006, 28(8): 1492-1496.
  • 加载中
  • 图(10) / 表(2)
    计量
    • 文章访问数:  29
    • HTML全文浏览量:  17
    • PDF下载量:  2
    • 被引次数: 0
    出版历程
    • 收稿日期:  2020-06-23
    • 修回日期:  2020-12-26
    • 网络出版日期:  2021-02-06

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注