基于局部最优的联盟结构生成算法

联盟形成是多Agent系统中的一个关键问题 .针对多Agent联盟数量是Agent个数指数倍的问题,给出了基于局部最优Agent联盟结构生成算法--OCS算法 .基于局部最优,将Agent联盟结构图化简,并利用划分所对应的一类联盟结构的上界对Agent联盟结构图进行剪枝,极大降低了搜索空间 .接着证明了OCS算法的时间复杂性为O(3n),但在实验上已经接近O(23n/2) .最后通过对比数据分析,表明了OCS算法的效率 . OCS算法是对Rothkopf和刘惊雷等人相关工作的改进 .     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

一种联盟结构的多Agent合作求解算法

为了测试和比较各种先进的多Agent合作求解智能算法,给多Agent合作策略提供一个比较与测试的平台。针对多Agent联盟数量是Agent个数指数倍的问题提出了一种对Agent联盟结构图自上而下的搜索算法,该算法可以对联盟结构图进行化简,降低搜索空间大小。在基于Agent合作收益独立性假设的基础上,证明了同构的联盟结构是最优的收益。最后,以机器人足球赛RoboCup为背景给出了仿真实验,表明了SCS算法的效率。     

联盟结构图的代数性质及应用

将联盟结构的空间抽象为联盟结构图,并在该图上定义2种运算并和交,从而联盟结构图中所有顶点关于并和交构成代数结构--联盟结构格.为了简化该格性质的研究,又引入整数拆分图,并在联盟结构图和整数拆分图之间建立映射关系F,且由映射关系,诱导一个等价关系E_F.这样在联盟结构图中搜索最优联盟结构时,可以利用某个联盟结构对E_F产生的等价类的上界和平均值作为剪枝函数,当某个等价类的上界低于剪枝函数时,该等价类中的大量联盟结构就被剪枝掉.最后设计一种动态规划算法.实验表明它的有效性.在20个Agent时,它比原动态规划算法减少43%的搜索次数.     

一种任一时间联盟结构生成算法

联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值的总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.给出了一个算法,可在最小搜索量内保证找到一个与最优解相距在一个限界内的联盟结构.然后,这个任一时间算法进一步搜索,渐进地给出越来越低的限界,并急剧地降低这个限界,在这一阶段,此算法明显地优于由Sandholm等人给出的算法.     

P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

给定限界要求的联盟结构生成

联盟形成是多Agent系统中的一个关键问题,目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益。但通常可能的联盟结构的数目太大,不允许穷尽搜索来找出最优解。当实际问题提出最坏情况的具体限界要求时,如何以最小的搜索达到这个要求是需要解决的。文中给出的算法对给定的限界要求K*≥2以最少的搜索层数解决了这个问题。Sandholm等人已经证明,要建立最坏情况下的限界K（n),搜索联盟结构图的最底两层是必要且是充分的,此时限界是n(系统的Agent 数）。以此为基础,文中给出了算法,在搜索最底两层之后,只要搜索一层就能保证K(n)≤3;而在搜索最底两层之后,最多搜索两层就能保证K(n)≤2。与Samdholm等人给出的算法相比,文中给出的算法达到指定限界的搜索量显著减少。     

加权3-Set Packing 的改进算法

Packing 问题构成了一类重要的NP 难问题.对于加权3-Set Packing 问题,把问题转化成加权3-Set Packing Augmentation 问题进行求解,即主要讨论如何从一个已知的最大加权k-packing 求得一个权值最大的(k+1)-packing. 通过对问题结构的分析,结合Color-Coding 技术,首先给出了一种时间复杂度为O^*(10.6^3k)的参数算法,极大地改进了目前文献中的最好结果O^*(12.8^3k).通过对(k+1)-packing 结构的进一步分析,利用集合划分技术将上述结果降到O^*(7.56^3k).     

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

一种基于等价的联盟演化机制

联盟是多Ａｇｅｎｔ之间一种重要的合作方法,多数方法没有考虑联盟的演化问题,难以避免大量的计算,而且对于联盟值是已知的假设也是不实际的,文中给出了联盟问题的等价性和相应的联盟演化机制,不通过对联盟值预先计算,可求得联盟问题的解,可以降低计算复杂度,与Ｓｈｅｈｏｒｙ ＆ Ｋｒａｕｓ的工作相比引入了联盟的等价和演化,放松了对联盟值已知的假设限制。     

Coalition Public-Key Cryptosystems

A coalition is understood to be a group of participants (coalitionists) who can collaborate in order to achieve common objectives. The basic principle of a coalition is the absence of a threat to communication flows within the coalition from its participants. In this paper, two new RSA coalition protocols are considered. According to the first protocol, only one participant in a coalition (called its leader) generates an RSA scheme for the other participants. In this case, an ordinary participant should send only one arbitrary number to the leader over a secure channel. In the other version, the general parameters of the RSA scheme being used are transmitted from the leader to a participant over a secure channel. This makes it possible to use very small keys and to substantially increase the data rate.     

基于溢出性原理的联盟结构生成算法

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

最坏情况具有限界的联盟结构生成

联盟形成是多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等人的工作.     

基于自适应PSO和类别分解的多任务串行联盟生成*

现有的联盟生成方案多针对一个agent只能加入一个联盟,不利于联盟总效用的最大化以及联盟中agent能力的充分利用。提出了基于能力类别的agent分解策略,通过定义子agent使得agent可以同时加入多个联盟,在此基础上设计了基于二维离散粒子群的多任务串行联盟生成算法,并对粒子的惯性权重进行动态自适应调整;最后通过算例验证了该方法的有效性。     

一种快速构建最优联盟结构的方法

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

COALITIONS AMONG INTELLIGENT AGENTS: A TRACTABLE CASE

Coalition formation is an important mechanism for cooperation in multiagent systems. In this paper we address the problem of coalition formation among self-interested agents in superadditive task-oriented domains. We assume that each agent has some "structure," i.e., that it can be described by the values taken by a set of m nonnegative attributes that represent the resources w each agent is endowed with. By defining the coalitional value as a function V of w , we prove a sufficient condition for the existence of a stable payment configuration—in the sense of the core—in terms of certain properties of V . We apply these ideas to a simple case that can be described by a linear program and show that it is possible to compute for it—in polynomial time—an optimal task allocation and a stable payment configuration.     

基于量子遗传算法的多任务联盟并行生成算法

提出一种基于量子遗传算法的多任务联盟并行生成算法,运用量子编码映射的方式将任务分配与资源组合合并为一个过程,使多任务联盟问题的复杂性得到降低。实验表明,该算法在面向多任务的领域中可以快速、有效地并行形成多个任务求解联盟;与遗传算法和蚁群算法的对比实验表明,该算法是正确、有效、可行的,在运行时间和解的性能上都优于前两种算法。