基于整数二部拆分的最优联盟结构求解

doi:10.3969/j.issn.1007130X.2010.

J4 ›› 2010, Vol. 32 ›› Issue (5): 64-66.doi: 10.3969/j.issn.1007130X.2010.

基于整数二部拆分的最优联盟结构求解

刘惊雷,张振荣,张伟

（烟台大学计算机学院，山东烟台 264005）

收稿日期:2009-11-15 修回日期:2010-02-09 出版日期:2010-04-28 发布日期:2010-05-11
通讯作者: 刘惊雷 E-mail:jinglei_liu @sina.com
作者简介:刘惊雷(1970),男,山西临猗人,硕士,副教授,研究方向为程序理论、Agent组织与联盟;张振荣,硕士生,研究方向为多Agent联盟;张伟,博士,教授,研究方向为多Agent系统。
基金资助:
国家自然科学基金资助项目（60496323）;山东省教育厅科技计划资助项目（J07JYJ24）

Optimal Coalition Structure Solving Based on the Bipartite of Integer

LIU Jinglei,ZHANG Zhenrong,ZHANG Wei

（School of Computer Science and Technology,Yantai University,Yantai 264005,China）

Received:2009-11-15 Revised:2010-02-09 Online:2010-04-28 Published:2010-05-11
Contact: LIU Jinglei E-mail:jinglei_liu @sina.com

摘要/Abstract

摘要：

联盟结构是对Agent集合的一个划分，通过联盟形成联盟结构，可以使Agent之间形成有效合作，完成单个Agent所不能完成的任务。本文提出了BIDP来求最优联盟结构，该算法利用整数二部拆分来生成二部划分，并利用二部拆分的界来对搜索空间进行限界。随后把该算法与DP算法做了理论和实验分析, 理论上得出BIDP所需要的空间比DP减少33.3%。实验表明，当联盟值满足均匀分布和正态分布，BIDP在21个Agent的情况下，搜索空间比DP减少35%和92%。最后对求最优联盟结构的确定式算法作了总结，即时间复杂度的上界是O(3n)，下界是Ω(2n)，空间复杂度是Θ(2n)。

关键词: 最优联盟结构, BIDP算法, 整数二部拆分, 二部划分, 时间和空间复杂度

Abstract:

Coalition structure is a partition of the agent set, forming a coalition structure by coalition can make agents cooperate effectively and fulfill the tasks that a single agent can not. In this paper, we propose a BIDP (Bipartite of Integer Dynamic Programming) algorithm to solve the optimal coalition structure generation, which adopts the bipartite of integer to generate bipartite partitions, and takes the bound of integer bipartite as the bound of the search space. And a theoretical analysis proves that BIDP can save 33.3% memory in any case than DP (Dynamic Programming). An experiment analysis shows that BIDP can save 35% and 92% searching numbers on 21 agents when the coalition values meet the uniform distribution and normal distribution. Finally,the paper gives a verdict that the time complexity of the determinant algorithm to solve OCS is between Ω(2n) and O(3n), and the space complexity is Θ(2n).

Key words: optimal coalition structure;BIDP algorithm;bipartite of integer;bipartite partition;time and space complexity

中图分类号:

TP18

刘惊雷,张振荣,张伟. 基于整数二部拆分的最优联盟结构求解[J]. J4, 2010, 32(5): 64-66.

LIU Jinglei,ZHANG Zhenrong,ZHANG Wei. Optimal Coalition Structure Solving Based on the Bipartite of Integer[J]. J4, 2010, 32(5): 64-66.

编辑推荐

Metrics

阅读次数

全文

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	0	0	35

来源	本网站	其他网站

次数	28	7
比例	80%	20%

摘要

最新录用	在线预览	正式出版

0	0	48

	来源	本网站

	次数	48
	比例	100%

[1]	方汐,马剑竹,王茂光,焦文品. 一种基于双向选择的多Agent系统自动集成方案[J]. J4, 2010, 32(6): 68-73.
[2]	潘晓英. 多智能体社会进化算法的动力学分析[J]. J4, 2010, 32(6): 74-76.
[3]	刘俞斌1，张伟1，童向荣1，董红斌2. 一种基于多目标优化的Agent多议题协商模型[J]. J4, 2010, 32(6): 85-87.
[4]	景丽萍，恽佳丽，于剑. 领域知识在文本聚类应用中的机遇和挑战[J]. J4, 2010, 32(6): 88-91.
[5]	丁浩1，丁世飞1,2，胡立花1. 基于粗糙集的属性约简研究进展[J]. J4, 2010, 32(6): 92-94.
[6]	李峻金，向阳，牛鹏. 一种用于数据挖掘的差异粒子群算法[J]. J4, 2010, 32(6): 95-98.
[7]	雷红艳,邹汉斌. 粗糙的方向性模糊聚类算法[J]. J4, 2010, 32(6): 99-102.
[8]	刘晓亮1,丁世飞1,2 ，朱红1，张力文1. SVM用于文本分类的适用性[J]. J4, 2010, 32(6): 106-108.
[9]	詹宇斌，殷建平，刘新旺. 局部切空间对齐算法的核主成分分析解释[J]. J4, 2010, 32(6): 158-161.
[10]	陈育武1，曹健1，李明禄1，赵海燕2. 复杂任务的Agent联盟算法[J]. J4, 2010, 32(5): 74-78.
[11]	刘晓勇. 基于最优适值保留的蚁群文本聚类算法[J]. J4, 2010, 32(5): 79-81.
[12]	袁浩. 基于量子蚁群算法的粗糙集属性约简方法[J]. J4, 2010, 32(5): 82-84.
[13]	谢明霞1,2，郭建忠1，张海波3，陈科1. 高维数据相似性度量方法研究[J]. J4, 2010, 32(5): 92-96.
[14]	陈凤娟，孙静. 粗糙集信息观中的绝对约简[J]. J4, 2010, 32(5): 97-99.
[15]	李悦群,毛文吉,王飞跃. 面向领域开源文本的因果知识提取[J]. J4, 2010, 32(5): 100-104.

基于整数二部拆分的最优联盟结构求解

Optimal Coalition Structure Solving Based on the Bipartite of Integer

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价