成本最小化的最优重叠联盟结构生成算法

重叠联盟结构生成(OCSG)的解空间复杂性较高,基于演化计算的随机搜索方法不能保证得到最优解,且其假设Agent承担任务消耗资源时不产生任何成本代价,导致无法区分各联盟结构的差异性。针对该问题,构建以联盟结构成本最小化为优化目标的OCSG数学模型,并提出一种基于动态规划的最优OCSG算法。实验结果表明,与TTGs_DP算法相比,该算法的环境适应性较好,资源利用率较高。

单调重叠联盟下的最优联盟结构生成

针对重叠联盟的合作博弈框架(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可解的,而且拥有更好的适用性。