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

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

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

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

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

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

联盟结构图的性质及应用

形成有效的联盟是多Agent系统的一个重大课题.然而联盟结构的数目很大,对于包含n个Agent系统来说,其可能构成的联盟结构是O(nn),以至于通过穷举搜索最优联盟结构是不可能的.另外联盟结构空间是一个什么样的形态,这是目前为止很少有人系统研究的课题,尤其是其图性质的研究.从图的视点讨论多Agent系统中的最优联盟结构生成问题.首先将联盟结构空间抽象为一个联盟结构图,其中顶点代表联盟结构,有向边代表联盟结构的分解.随后总结和形式化该联盟结构图所具有的两个性质:最优子结构、重复子结构问题;推广了一个性质:关键搜索集;给出了一个新性质:较少冗余路径的图的连通性.为了理解联盟结构图的这些性质,将这些性质用到了有效动态规划法(effective dynamic programming,EDP)中,分析得到其时间复杂度的下界是Ω(2.1n),上界是O(3n).实验分析表明,EDP算法比DP算法的搜索次数更少,在含有21个Agent的系统中,EDP比DP减少42%的搜索次数.     

基于改进型蚁群算法的多任务联盟形成算法

联盟形成是多Agent系统研究的关键问题之一,基于蚁群算法的联盟形成是一种有效的研究方法.创新地把能力互补性原则引入到下一个Agent的选择判断中,引导蚂蚁沿着能生成具有较大联盟值的联盟的方向前进;引入一种带有"调节剂"的扰动策略来预防算法陷入局部最优和出现停滞;在每一轮的任务分配中尽可能多地分配任务,使得联盟在执行任务时具有一定的并行性.算法能更早地搜索到最优解或次优解,在时间复杂度和全局搜索能力等方面均优于相关算法.     

一种非线性动态自适应的Agent联盟生产算法

代理(Agent)联盟是对无线传感器网络WSN(Wireless Sensor Network)进行管理的重要手段.引入粒子群算法PSO(Particle Swarm Optimization)并对其进行改进,使PSO的参数具有非线性动态自适应性.将改进的PSO用于求解Agent联盟生成问题,并针对WSN的特性设计了一种效益函数用于评价联盟的效益.采用基于非线性动态自适应PSO的Agent联盟生成算法,在联盟生成初期搜索范围较广,搜索后期在局部挖掘上表现出良好的性能.实验证明在解决Agent联盟生成问题中,基于PSO的算法在稳定性上优于其他算法,基于改进PSO的联盟生成算法可以加大搜索空间,更快的收敛到最优解,且该算法可以同时生成多个Agent联盟,支持并行多任务环境下的Agent联盟求解.     

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

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

分布式环境下面向复杂任务的Agent联盟构建

在分布式环境下,现有Agent联盟构建算法不能解决带有相互依赖关系和转移成本的任务流程问题。为此,利用Agent协商构建联盟,在协商过程中设定方案发布Agent和参与Agent,并对应设计以成本信息调整和盈利任务争取为主的决策算法。在Agent的反馈信息中加入争取信息,允许参与Agent在多轮协商中采用可控制的信息泄露机制,通过泄露自己的成本信息向方案发布Agent争取可获利的任务,经过多轮协商,形成最优联盟结构。实验结果表明,在按劳分配联盟总收益的模式下,相比传统的信息不泄露机制,该信息泄露机制能够更快地形成联盟,并且具有更高的联盟净收益和Agent平均收益率。     

一种基于多Agent的进化多目标优化算法

将进化多Agent系统引入多目标优化问题求解，通过Agent的局部搜索机制及Agent种群的协同进化机制来寻求Pareto最优解。在设计的进化算法当中借鉴了人工生命系统中的一些基本方法，如能量、小生境和迁移机制等。实例表明通过该进化算法求得Pareto最优解集具有很高的效率。     

低约束密度分布式约束优化问题的求解算法

多Agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,Agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.     

基于合作技能博弈的单任务联盟结构生成算法

提出一种用于单任务最优联盟结构生成算法STCSG。利用合作技能博弈(CSGs)模型和超图生成合作技能超图(skill hypergraph),根据STSG中最优联盟结构特性,具体讨论了当每个agent最多只能拥有一个技能和一个技能最多被两个agent共同拥有两种情况下搜索合作技能超图的策略,从而求得最优联盟结构。实验结果表明该算法搜索效率较高,时间复杂度为O(n2)。     

一种生成最优联盟结构的任意时间算法

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

基于仿生学改进的粒子群算法

针对标准粒子群算法收敛速度慢和易陷入局部最优的局限性,提出了一种基于仿生学改进的粒子群算法。即通过在标准粒子群公式中加入负梯度项,使算法更加符合鸟群觅食的实际规律,同时使算法的全局和局部搜索能力得到了平衡。仿真对比结果表明,改进的粒子群算法减小了陷入局部极值的可能性,能够提高最优解的精度和优化效率。     

混合拓扑结构的粒子群算法及其在测试数据生成中的应用研究

粒子群算法(PSO)的拓扑结构是影响算法性能的关键因素,为了从根源上避免粒子群算法易陷入局部极值及早熟收敛等问题,提出一种混合拓扑结构的粒子群优化算法(MPSO)并将其应用于软件结构测试数据的自动生成中。通过不同邻域拓扑结构对算法性能影响的分析,采用一种全局寻优和局部寻优相结合的混合粒子群优化算法。通过观察粒子群的多样性反馈信息,对每一代种群粒子以进化时选择全局拓扑结构模型(GPSO)或局部拓扑结构模型(LPSO)的方法进行。实验结果表明,MPSO使得种群的多样性得到保证,避免了粒子群陷入局部极值,提高了算法的收敛速度。     

垂直结构群落系统优化算法

为了求解一类复杂非线性优化问题的全局最优解,基于采用垂直结构群落动力学理论,提出了一种新的垂直结构群落系统优化算法,简称为VS-CSO算法。该算法将优化问题的搜索空间视为一个生态系统,该生态系统具有若干个垂直结构分叉营养水平,在各个营养水平中生活着不同种类的生物种群;在每个种群内,有若干生物个体在活动;生物个体不能跨种群迁移,但在同类种群中会相互影响。各种群以循环捕食-被食或资源-消耗连接在一起。运用垂直结构群落动力学模型开发出了通吃算子、择食算子、干扰算子、侵染算子、新生算子、死亡算子。其中,通吃算子和择食算子可实现个体跨种群的信息交换,而干扰算子和侵染算子可实现种群内部个体之间的信息交换,从而确保个体间信息的充分交换;新生算子可适时补充新个体到种群中,而死亡算子可将种群中的虚弱个体适时清除掉,从而大幅提升算法跳出局部陷阱的能力。在求解过程中,VS-CSO算法每次只对极少变量进行处理,因此可求解高维优化问题。测试结果表明,VS-CSO算法能求解一类非常复杂的单峰函数、多峰函数和复合函数优化问题,其求精能力、探索能力及两者的协调性均优良,且具有全局收敛性的特点。该算法为求解一些较高维复杂函数优化问题的全局最优解提供了可行方案。     

一种利用膜计算求解高维函数的全局优化算法

鉴于传统优化算法在求解高维多模态优化问题时存在收敛速度慢,求解精度低的缺点,针对上述问题提出了一种基于膜计算的优化算法。算法首先对高维空间进行分割,分割后每个子空间作为一个基本膜,基本膜区域中采用差分局部搜索策略提高算法的局部搜索能力和收敛速度。基本膜区域将局部最优解定时传送给表层膜。表层膜区域中采用全局搜索策略寻找全局最优解。通过对5个benchmark函数仿真验证,实验结果表明,该算法在收敛速度,求解精度和稳定性方面都有较大优势。     

基于SA-PSO的多态路径测试数据生成方法

目前测试数据生成方法多数未考虑到面向对象软件的多态特性,无法运用生成的测试数据对程序的多态信息进行充分的测试。根据多态路径测试数据生成的要求,提出了一种应用模拟退火—粒子群优化(simulated annealing-particle swarm optimization,SA-PSO)混合算法在多态路径测试中生成测试数据的方法,并通过多态性实例对基本粒子群算法、遗传算法、PSO-GA（particle swarm optimization-genetic algorithm）和SA-PSO算法在相同条件