计算机应用

作者：郭志鹏, 刘惊雷

单位：烟台大学 计算机与控制工程学院, 山东 烟台 264005

关键词：重叠联盟结构生成,最优联盟结构,联盟数量约束,单调性,固定参数可解

基金：国家自然科学基金资助项目（61773331，61703360，61801414）。

针对重叠联盟的合作博弈框架（OCF games）中重叠联盟结构生成（OCSG）求解困难的问题，提出了一种基于贪心方法的有效算法。首先使用了一种带有联盟数量k约束的OCF博弈（kOCF games）模型来限制OCSG问题的规模；然后引入了一种相似度量来表示任意两个联盟结构之间的相似程度，并基于相似度量定义了单调性的性质，这意味着某一联盟结构与最优联盟结构的相似度越高，该联盟的单调性的值就越大；最后对于具有单调性质的kOCF博弈，采用了逐一插入玩家编号以逼近最优联盟结构的方法设计了联盟约束贪心（CCG）算法来求解给定的OCSG问题，并在理论上证明了CCG算法的复杂度是O（n2k+1）。通过实验分析和验证了不同参数和联盟值分布对所提算法性能的影响，并把该算法与Zick等提出的算法（ZICK Y，CHALKIADAKIS G，ELKIND E，et al. Cooperative games with overlapping coalitions： charting the tractability frontier. Artificial Intelligence，2019，271：74-97）在约束条件等方面进行了对比，得出了当联盟最大数量k被常数约束时所提算法的搜索次数随agent的个数基本呈线性增长的结果。可见CCG算法是固定参数k可解的，而且拥有更好的适用性。

来源：2021年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2021年第1期