模式识别与人工智能
2025年4月3日 星期四   首 页     期刊简介     编委会     投稿指南     伦理声明     联系我们                                                                English
模式识别与人工智能  2009, Vol. 22 Issue (6): 841-847    DOI:
论文与报告 最新目录| 下期目录| 过刊浏览| 高级检索 |
联盟结构图的代数性质及应用*
刘惊雷,张伟,王玲玲
烟台大学 计算机学院 烟台 264005
Algebra Property and Application of Coalition Structure Graph
LIU Jing-Lei, ZHANG Wei, WANG Ling-Ling
School of Computer, Yantai University, Yantai 264005

全文: PDF (394 KB)   HTML (1 KB) 
输出: BibTeX | EndNote (RIS)      
摘要 将联盟结构的空间抽象为联盟结构图,并在该图上定义2种运算并和交, 从而联盟结构图中所有顶点关于并和交构成代数结构——联盟结构格.为了简化该格性质的研究, 又引入整数拆分图, 并在联盟结构图和整数拆分图之间建立映射关系F,且由映射关系F诱导一个等价关系EF. 这样在联盟结构图中搜索最优联盟结构时,可以利用某个联盟结构对EF产生的等价类的上界和平均值作为剪枝函数, 当某个等价类的上界低于剪枝函数时,该等价类中的大量联盟结构就被剪枝掉. 最后设计一种动态规划算法.实验表明它的有效性.在20个Agent时,它比原动态规划算法减少43%的搜索次数.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
刘惊雷
张伟
王玲玲
关键词 最优联盟结构联盟结构图整数拆分图(ISG)联盟结构格(CSL)等价关系    
Abstract:The space of coalition structure is abstracted as a coalition structure graph, and two operators, union and intersection, are defined. Thus, all the coalition structures form an algebra structure, coalition structure lattice (CSL). In order to simplify the study of CSL algebra property, the integer split graph is introduced, and a mapping relation F from coalition structures to integer splits and an equivalent relation EF based on F are constructed. Therefore, during searching optimal coalition structure in CSL, the current optimal value and average value are used as prune function. When the upper bound of some equivalent class is lower than the prune function, a large number of coalition structures in equivalent class are pruned. Finally, better dynamic programming (BDP) algorithm is given, and the validity of the proposed algorithm is proved by experimental analysis. Furthermore, the results indicate that BDP decreases 43% searching numbers than dynamic programming when there are 20 agents.
Key wordsOptimal Coalition Structure    Coalition Structure Graph    Integer Split Graph (ISG)    Coalition Structure Lattice (CSL)    Equivalent Relation   
收稿日期: 2008-11-24     
ZTFLH: TP301  
基金资助:国家自然科学基金项目(No.60496323)、山东省教育厅科技计划项目(No.J07JYJ24)资助
作者简介: 刘惊雷,男,1970年生,副教授,主要研究方向为程序理论、Agent组织与联盟.E-mail: jinglei_liu@sina.com.张伟,男,1961年生,教授,硕士生导师,主要研究方向为多Agent系统、并行处理.王玲玲,女,1978年生,讲师,主要研究方向为Petri网.
引用本文:   
刘惊雷,张伟,王玲玲. 联盟结构图的代数性质及应用*[J]. 模式识别与人工智能, 2009, 22(6): 841-847. LIU Jing-Lei, ZHANG Wei, WANG Ling-Ling. Algebra Property and Application of Coalition Structure Graph. , 2009, 22(6): 841-847.
链接本文:  
http://manu46.magtech.com.cn/Jweb_prai/CN/      或     http://manu46.magtech.com.cn/Jweb_prai/CN/Y2009/V22/I6/841
版权所有 © 《模式识别与人工智能》编辑部
地址:安微省合肥市蜀山湖路350号 电话:0551-65591176 传真:0551-65591176 Email:bjb@iim.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn