Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2019, Vol. 45 ›› Issue (11): 198-203. doi: 10.19678/j.issn.1000-3428.0052532

Previous Articles     Next Articles

Optimal Overlapping Coalition Structure Generation Algorithm with Cost Minimization

WEI Bingrua, ZHANG Guofua,b,c, SU Zhaopina,b,c, YUE Fenga,b,c, NIU Fuqianga   

  1. a. School of Computer Science and Information Engineering;b. Anhui Province Key Laboratory of Industry Safety and Emergency Technology;c. Engineering Research Center of Safety-Critical Industrial Measurement and Control Technology, Ministry of Education, Hefei University of Technology, Hefei 230601, China
  • Received:2018-09-03 Revised:2018-10-28 Published:2018-11-15

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

魏冰茹a, 张国富a,b,c, 苏兆品a,b,c, 岳峰a,b,c, 牛福强a   

  1. 合肥工业大学 a. 计算机与信息学院;b. 工业安全与应急技术安徽省重点实验室;c. 安全关键工业测控技术教育部工程研究中心, 合肥 230601
  • 作者简介:魏冰茹(1993-),女,硕士研究生,主研方向为多Agent系统、启发式算法;张国富,教授、博士;苏兆品,副教授、博士;岳峰,副研究员、博士;牛福强,硕士研究生。
  • 基金资助:
    国家自然科学基金(61573125);中央高校基本科研业务费专项资金(JZ2018YYPY0288,JZ2017YYPY0232);安徽省自然科学基金(1608085MF131)。

Abstract: The solution space complexity of Overlapping Coalition Structure Generation(OCSG) is high.The stochastic search method based on evolutionary computation can not guarantee the optimal solution,and it assumes that the Agent does not incur any cost when it undertakes the task to consume resources,which makes it impossible to distinguish the differences among coalition structures.To solve this problem,an OCSG mathematical model with the objective of minimizing the cost of coalition structure is constructed,and an optimal OCSG algorithm based on dynamic planning is proposed.Experimental results show that compared with TTGs_DP algorithm,this algorithm has better environmental adaptability and higher resource utilization rate.

Key words: Multi-Agent Systems(MAS), coalition games, Overlapping Coalition Structure Generation(OCSG), cost minimization, dynamic planning

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

关键词: 多Agent系统, 联盟博弈, 重叠联盟结构生成, 成本最小化, 动态规划

CLC Number: