首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到14条相似文献,搜索用时 203 毫秒
1.
给定限界要求的联盟结构生成   总被引:12,自引:1,他引:11  
胡山立  石纯一 《计算机学报》2001,24(11):1185-1190
联盟形成是多Agent系统中的一个关键问题,目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益。但通常可能的联盟结构的数目太大,不允许穷尽搜索来找出最优解。当实际问题提出最坏情况的具体限界要求时,如何以最小的搜索达到这个要求是需要解决的。文中给出的算法对给定的限界要求K*≥2以最少的搜索层数解决了这个问题。Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的,此时限界是n(系统的Agent 数)。以此为基础,文中给出了算法,在搜索最底两层之后,只要搜索一层就能保证K(n)≤3;而在搜索最底两层之后,最多搜索两层就能保证K(n)≤2。与Samdholm等人给出的算法相比,文中给出的算法达到指定限界的搜索量显著减少。  相似文献   

2.
基于势结构的任一时间联盟结构生成算法   总被引:1,自引:0,他引:1  
联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的.Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法,对于较小的限界明显地优于Sandholm等人给出的算法.深刻分析了联盟结构间的关系,采用更小的搜索粒度(势结构),提出基于势结构的任一时间算法,在搜索最底两层及顶层后,进一步搜索势结构集合CCS(n,6)对应的未搜索过的联盟结构,渐进地给出越来越低的限界,大大改进了Sandholm等人(快1035倍,当n=100,K=2)和Dang等人(快1018倍,当n=100,K=3)的工作.  相似文献   

3.
联盟形成是多Agent系统中的一个关键问题. 寻求能极大化联盟值总和的最优联盟结构是NP-完全的. Sandholm等人已经证明要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能解决的问题. Dang等人给出的算法,对于奇数限界k≥3,在搜索最底两层及顶层后,进一步搜索最大联盟的势不小于- n(k-1)/(k+1) - 的所有联盟结构,是迄今所知的第1个不以层为搜索单位的算法,对于较小的限界明显地优于Sandholm等人给出的算法. 文中深刻分析了联盟结构间的关系,提出的算法在搜索最底两层后,只需进一步搜索最大联盟的势等于- n(k-1)/(k+1) - 的所有联盟结构,从而使需要搜索的联盟结构数大大减少,并进一步将搜索某些层最大联盟的势等于- n(k-1)/(k+1) - 的联盟结构巧妙地改为搜索联盟结构数更少的相应层,使需要搜索的联盟结构数进一步减少,较大地改进了Sandholm等人和Dang等人的工作.  相似文献   

4.
给定限界的势结构分组与联盟结构生成   总被引:1,自引:0,他引:1  
联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.  相似文献   

5.
一种基于势结构分组思想的任一时间联盟结构生成   总被引:1,自引:0,他引:1  
联盟形成是多agent系统中的一个关键问题,找到最优的联盟结构是NP-完全的.Sandholm和Larson等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能完全解决的问题.在任务分配等实际问题中,不同联盟存在同势同值的特征,或同势的2个联盟的值相差不大.研究了最优势结构生成问题,分析了基于势结构的分组思想,并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法.算法在最小搜索之后给出进一步降低限界至2的搜索,也讨论了限界从2降到1的过程中由底向上的补充搜索.从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法,是基于势结构的联盟生成问题的一个重要进展.  相似文献   

6.
联盟结构生成是多agent系统中的一个关键问题。Sandholm等人证明了要建立最坏情况下的限界k, 搜索联盟结构图的最底两层是必要且是充分的,如何进一步搜索是一个长期以来未能解决的问题。当实际应用提出最坏情况的具体限界要求时,如何通过部分的搜索达到这个限界?胡山立和石纯一给出了一种以层为单位的最优搜索算法, Dang等人和苏射雄等人给出了以势结构为单位的联盟结构生成算法。新算法MCCS提出在搜索最底两层及顶层后,搜索势结构集合MCCS(n, k)对应的联盟结构,以更少的势结构达到给定限界k。实验表明,在  相似文献   

7.
联盟结构的生成问题中由于搜索空间的联盟结构数目太大,因而搜索联盟结构的最底两层建立一个最坏情况下的边界值是必要的,边界值将最优的联盟结构限制在某个限界内,通过进一步的搜索可以在任意时间内得到一个较优值。根据联盟的溢出性质,文中提出了一种新的建立边界值的方法,即对任意不相交的联盟集合计算其上下边界的值,通过搜索特定的联盟结构集合建立最坏情况下的边界值。联盟的边界值建立以后,可以在任意时间内得到一个较优值,通过搜索剩余的联盟结构集合,可以对边界值和返回的联盟结构进一步优化。在此基础上文中提出了基于溢出性质的任意时间算法。实验结果表明,采用新的方法建立边界值,使得算法的收敛速度更快,效率更高。  相似文献   

8.
提出一种用于生成最优联盟结构的任意时间算法LVAA。利用分支限界技术和剪枝函数搜索联盟结构图的L1、L2和最顶层后,根据整数拆分对剩余的搜索空间进行横向剪枝,并在横向剪枝剩余的子空间内进行纵向剪枝,从而求得最优联盟结构。实验结果表明,该算法的剪枝效率较高,并能在任意时间点上找到最优值。  相似文献   

9.
在联盟结构生成过程中,同势的2个联盟通常具有相同值或相似值。在同势同值情况下建立不同联盟的限界时,必须搜索势结构图的最底两层。研究最优势结构生成问题,提出一种给定限界的势结构生成算法,确定需要进一步搜索的势结构。分析结果表明,搜索势结构图的最底两层和顶层后,通过搜索势结构集合,可以得到符合要求的限界。与其他势结构生成算法相比,该算法需要搜索的势结构数最少。  相似文献   

10.
给定限界的势结构生成算法   总被引:1,自引:1,他引:0       下载免费PDF全文
李少芳  胡山立 《计算机工程》2009,35(21):186-188
在联盟结构生成过程中,同势的2个联盟通常具有相同值或相似值。在同势同值情况下建立不同联盟的限界时,必须搜索势结构图的最底两层。研究最优势结构生成问题,提出一种给定限界的势结构生成算法,确定需要进一步搜索的势结构。分析结果表明,搜索势结构图的最底两层和顶层后,通过搜索势结构集合,可以得到符合要求的限界。与其他势结构生成算法相比,该算法需要搜索的势结构数最少。  相似文献   

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

12.
一种快速构建最优联盟结构的方法   总被引:4,自引:0,他引:4  
联盟结构是对Agent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效的合作,完成单个Agent所不能完成的任务。然而联盟结构的数目和解空间比较大,以至于通过穷举搜索最优联盟结构是很复杂的。动态规划法通常用于求解具有最优子结构性质和重叠子问题性质的问题,文章在给出了Agent联盟的相关概念之后,论证了构造最优联盟结构问题恰恰具有这两类性质,因此利用动态规划法可以求解。最后给出了相应的算法,并得出采用动态规划法实现最优联盟结构的时间复杂度为O(3n)。  相似文献   

13.
任一时间面向任务联盟结构生成算法   总被引:1,自引:1,他引:0       下载免费PDF全文
联盟形成是多Agent系统中的一个关键问题。目前,大多数学者都在CFG下研究联盟结构生成问题。然而,在很多实际应用中,联盟的形成往往是为了完成任务集中某些任务。但是,在CFG中并没有把联盟和任务一起考虑。显然,加入任务后,问题将变得更复杂。Dang等人已经证明,这是个NP难问题,并且要建立最坏情况下的限界K(n,m),搜索索面向任务联盟结构集合L1、L2(除{(A,Φ),(Φ,T)})是必要且充分的,接着提出一个限界具有保证的任一时间算法。本文深刻分析了面向任务联盟结构间的关系,引入更小的搜索粒度(面向任务势结构),提出一种新的任一时间搜索算法;在搜索完最小搜索之后,进一步搜索CTS集合CTS(n,m,b)对应的部分面向任务联盟结构,渐进给出越来越低的限界,大大改进了Dang等人的工作。  相似文献   

14.
已有的求解最优联盟结构方法大多假定Agent的全局信息已知,采用集中式求解思路,这种假设不适用于分布式环境,且没有充分利用Agent的自治性.在多Agent环境下,个体Agent往-只拥有部分联盟信息并且是自利的,如何在局部信息条件下寻找最优联盟结构是多Agent系统需要解决的关键问题.针对以上问题,基于个体Agent的局部信息及系统整体收益的考虑,通过局部Agent之间的优势信息传递,给出了最优联盟结构的分布式求解算法.该算法的特色是在局部最优假设下,通过局部信息的指导,n个Agent在深度方向上自顶向下对联盟结构图的并行搜索,从而达到缩短搜索时间,降低搜索复杂度的目的,该算法的时间复杂度为O(n2).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号