摘要
形成有效的联盟是多Agent系统研究中的关键问题.为了有效地完成个体的或共同的目标,Agent集合划分成相互独立的团体,即联盟的形成.联盟结构生成(coalition structure generation,CSG)问题研究的是Agent集合划分成联盟,从而使得收益最大化.传统的算法利用不同的方法来解决这个问题,但都没有对联盟个数进行约束.利用动态规划(dynamic programming,DP)原理设计了新的算法—联盟约束动态规划(coalition constrain dynamic programming,CCDP)算法,并通过该算法生成最优(福利最大化)联盟结构.随后证明了算法的时间复杂度为O(3n).最后通过实验,分析并验证了Agent个数对算法性能的影响,以及联盟个数约束值的大小对算法性能的影响.实验结果证明在Agent集合的个数较大的情况下,在联盟结构搜索图中越靠近中间部分,即联盟个数约束条件的取值越靠近中间部分,算法的效果越好.
Forming effective coalitions is a major area of research in the field of multi-agent systems.Coalition formation is one of the basic methods for establishing cooperations among agents that involve the creation of coherent groupings of independent agents for the sake of achieving their individual or collective goals efficiently.What′s more,this usually needs to calculate a value for every possible coalition,and the value of coalition indicates the profit that coalition would generate if it was formed.However,once these values are calculated,the agents usually need to find a combination of coalitions known as coalition structure,in which every agent belongs to exactly one coalition and there is no intersection between coalitions,and the overall outcome of the system is maximized by forming coalition structure.CSG（coalition structure generation）involves partitioning a set of agents into coalitions so that social surplus is maximized.However,the CSG problem is extremely challenging due to the number of possible solutions that need tobe examined,which grows exponentially with the number of agents involved.Traditionally,there have been put forward many algorithms to solve this problem ranging from dynamic programming to improved dynamic programming,to integer programming,and all of these techniques suffer from having no constaints on the number of coalitions.However,in many real-world applications,there are inherent constraints on the number of coalitions.In this paper,we present the first systematic study of constraint on the number of coalition,and use the DP（dynamic programming）theory to develop an algorithm,which is named as CCDP（coalition constraint dynamic programming）,for generating an optimal（welfare-maximizing）coalition structure.Furthermore,it is proved that the time complexity of this algorithm is O（3n）.In the end,we analyze and verify the influence of agent＇s number and the size of values of constraints on the algorithm performance through detailed experiments.
出处
《南京大学学报（自然科学版）》
CAS
CSCD
北大核心
2015年第4期749-761,共13页
Journal of Nanjing University（Natural Science）
基金
国家自然科学基金(61403328
61403329)
山东省自然科学基金(ZR2013FM011
ZR2013FQ023
ZR2013FQ020
ZR2014FL009)
山东省教育厅科技计划(J14LN23)
关键词
联盟结构
联盟个数约束
动态规划
联盟约束动态规划(CCDP)
时间复杂度
coalition structure
the constraint of the number of coalition
dynamic programming
coalition constraint dynamic programming（CCDP）
