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

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

面向并发多任务的重叠联盟效用分配策略*

重叠联盟效用分配是多agent系统中的一个难点问题,文中提出面向并发多任务的重置联盟效用分配策略.首先基于能者多劳的思想采取按比例分配,对多个并发任务进行并行分派,并根据任务分派情况划分重叠联盟的效用.然后推演一个agent同时加入多个联盟时满足效用非减原则的充分必要条件.最后通过实例验证文中方法的有效性,并与串行效用分配进行对比分析.结果表明,在新agent申请加入联盟时,文中策略更易满足效用非减条件,具有更好的时效性.     

多任务联盟形成中的Agent行为策略研究

Agent联盟是多Agent系统中一种重要的合作方式,联盟形成是其研究的关键问题.本文提出一种串行多任务联盟形成中的Agent行为策略,首先论证了Agent合作求解多任务的过程是一个Markov决策过程,然后基于Q-学习求解单个Agent的最优行为策略.实例表明该策略在面向多任务的领域中可以快速、有效地串行形成多个任务求解联盟.     

分布式自利agent任务分配算法

在有自利agent参与的任务分配情形中,由于agent的自利性,导致各agent不能有效合作,影响agent的个体收益和系统总收益.解决该问题的一个途径是对agent所得的收益进行合理分配.文中基于分布式自利agent联盟技能博弈模型,提出自利agent的任务分配算法.模型中提供技能的服务agent和管理任务的agent都是自利的,分别处于不同的地理位置,具有不同的视野范围.算法为任务agent设计效益分配策略,合理分配自己的收益给所需的技能,任务分配结果在保证个体自利性的前提下获得较高的系统收益.仿真结果验证文中算法的有效性,并考察自利agent的视野范围对自利agent的个体收益和系统总收益的影响.     

一种基于理性Agent的任务求解联盟形成策略

联盟形成是多 agent 系统中的一个关键问题, 主要着眼于如何在联盟内 agent 间划分联盟的效用. 但已有策略无法摆脱搭便车问题, 尤其是额外效用的分配没有确切反映出各 agent 对于联盟贡献的差异性, 导致联盟潜在的不稳定. 本文给出了一种新的联盟形成的行为策略, 在公平分配原则和无妒忌原则的基础上, 提高了对额外效用分配的合理性, 在具有超加性的面向任务的领域中可以形成全局最优联盟, 并具有 Nash 均衡意义下的稳定性.     

LeCMPSO算法求解异构无人机协同多任务重分配问题

无人机系统在军事领域有着广泛应用, 由于战场环境复杂多变, 无人机遭遇突发状况后需进行任务重分配.异构无人机是指多种类型的无人机, 可完成单一无人机无法完成的多类型复杂任务, 异构无人机协同多任务重分配问题约束条件复杂且包含混合变量, 现有多目标优化算法不能有效处理此类问题. 为高效求解上述问题, 本文构建多约束异构无人机协同多任务重分配问题模型, 提出一种学习引导的协同多目标粒子群优化算法(LeCMPSO), 该算法引入基于先验知识的初始化策略和基于历史信息学习的粒子更新策略, 能有效避免不可行解的产生并提升算法的搜索效率. 通过在4组实例上的仿真实验表明, 与其他典型的协同进化多目标优化算法相比, 所提算法在解集的多样性、收敛性及搜索时间方面均具有较好的性能.     

基于评价因子行为等级更新的多Agent联盟效用分配策略

为了进一步增强多Agent联盟效用分配的合理性,提升联盟的稳定性,提出了一种基于评价因子行为等级更新的多Agent联盟效用分配策略。该策略引入评价因子概念,将行为等级定性描述的agent行为因素通过既定方法量化为行为评价因子,agent完成任务的能力表示为能力评价因子,结合这两种评价因子对agent联盟的效用进行划分,并根据agent完成任务情况和是否存在欺骗行为对agent的行为等级进行更新。理论分析和分配实验表明,新策略在满足联盟形成机制的相关要求外,增强了多Agent联盟中效用分配的合理性。     

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

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

基于分治法求解对称三对角矩阵特征问题的混合并行实现

基于对称三对角矩阵特征求解的分而治之方法,提出了一种改进的使用MPI/Cilk模型求解的混合并行实现,结合节点间数据并行和节点内多任务并行,实现了对分治算法中分治阶段和合并阶段的多任务划分和动态调度.节点内利用Cilk任务并行模型解决了线程级并行的数据依赖和饥饿等待等问题,提高了并行性;节点间通过改进合并过程中的通信流程,使组内进程间只进行互补的数据交换,降低了通信开销.数值实验体现了该混合并行算法在计算效率和扩展性方面的优势.     

基于任务能力排序的虚拟企业联盟生成方法

将虚拟企业联盟生成问题转化为多Agent问题,针对传统求解多Agent问题过程中仅考虑成本和联盟值最优的局限性,引入“一企多标”和资源配置等实际问题并给出解决方案。重点论述了基于改进的蚁群算法及任务能力排序的虚拟企业联盟生成方法,在求解过程中首先根据任务所需的核心能力对Agent集进行划分,然后利用改进的蚁群算法来求解该问题,以使满足该任务能力要求的Agent优先被选择,从而避免优势资源得不到利用的现象,起到合理配置资源的作用。通过模拟算例分析表明,该方法能有效、快速求解多虚拟企业联盟生成问题,表现了该方法的正确性。     

基于模糊评判的Agent联盟效用分配

多个Agent同时形成任务求解联盟时,联盟效用的分配是一个棘手的问题。已有的平均分配和基于能力大小的分配策略都没有反映出Agent对联盟贡献的差异性,不利于联盟的形成和完成任务的绩效。提出了一种基于模糊评判的联盟效用分配方法。首先模糊评价Agent的各维能力贡献率,然后综合计算出整体贡献因子,并据此完成联盟效用的合理分配,最后通过实例分析说明了此方法的有效性。     

基于熟人的Agent联盟策略

在多ａｇｅｎｔ系统中,ａｇｅｎｔ可以通过协商形成联盟来完成任务求解。本文基于ａｇｅｎｔ联盟的统计规律提出了ａｇｅｎｔ熟人的概念,以熟人为基础的联盟策略可以有效减少联盟形成过程中的通讯开销和计算量。随后给出了一种基于该策略的联盟竞争任务的算法,该算法适用于动态,开放的环境、无中心控制,不存在通讯和计算瓶颈。     

单调速率任务分配算法利用率的界限分析

通过对单调速率任务分配算法调度策略和可调度条件的分析,在多处理器周期任务抢占调度模型基础上,细致刻画了任务分配算法如何分配任务的行为。依据Liu和Layland定理,给出多处理器下任务分配算法的最小RM利用率界的定理。仿真结果表明,分配算法的利用率界是不同特征任务集选择不同分配算法进行任务划分的关键,通过对任务集总利用率与算法利用率界的比较,判断使用该算法对任务集是否可以产生可行分配。     

Searching for overlapping coalitions in multiple virtual organizations

Coalition formation is an active and essential component for multi-agent systems (MAS) in task-oriented domains in which tasks can be too complicated to be accomplished by a single agent with insufficient resources. By forming a coalition, agents are able to cooperate and combine resources to complete tasks that are impossible to accomplish alone within a given time bound. For example, in virtual enterprises, small and agile enterprises can provide more services and make more profits than an individual can. In many multi-task environments, especially in parallel multi-task environments, an individual abundant in resources is inclined to undertake more than one task to make more profits and participate in multiple virtual organizations (MVOs) at the same time, where every member has to decide how to allocate different parts of its resources to serve multiple different project tasks. Such overlapping property is a very intractable problem in practical decision making, and to the best of our knowledge, current coalition formation algorithms typically exclude the possibility of having overlapping coalitions, that is an agent can only be a member of one coalition at any given time, leading to waste of resources, preventing the system from efficiently allocating all agents’ resources, and limiting the scope of their applications in real-world scenarios. Indeed, overlapping coalition formation (OCF) is an important research question, because MVOs are very crucial and beneficial in parallel multi-task domains where only a few selected individuals have rare, but highly demanded, resources. With this in mind, we develop a discrete particle swarm optimization based algorithm to solve the OCF problem in MVOs, applicable for more complex virtual enterprises environments. We introduce a two-dimensional binary encoding scheme and propose a novel repairing strategy for resolving conflicts over the usage of joint resources among overlapping coalitions. With this novel strategy for cooperative conflict resolution, any invalid encoding can be adjusted into a valid one without any resource conflict. Finally, simulations are conducted to show the efficiency of the proposed algorithm.     

用遗传算法实现多智能体联盟的形成

在多Agent系统中，当单个Agent不能或不能有效完成特定的任务时，任务就必需分配给一组Agent，即Agent将形成联盟。本文将讨论Agent联盟的形成，并将遗传算法应用于Agent联盟形成中，希望可以快速、高效地找出合适的Agent联盟。     

Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects

We consider a problem domain where coalitions of agents are formed in order to execute tasks. Each task is assigned at most one coalition of agents, and the coalition can be reorganized during execution. Executing a task means bringing it to one of the desired terminal states, which might take several time steps. The state of the task evolves even if no coalition is assigned to its execution and depends nondeterministically on the cumulative actions of the agents in the coalition. Furthermore, we assume that the reward obtained for executing a task evolves in time: the more the execution of the task is delayed, the lesser the reward. A representative example of this class of problems is the allocation of firefighters to fires in a disaster rescue environment. We describe a practical methodology through which a problem of this class can be encoded as a Markov Decision Process. Due to the three levels of factoring in the resulting MDP (the states, actions and rewards are composites of the original features of the problem) the resulting MDP can be directly solved only for small problem instances. We describe two methods for parallel decomposition of the MDP: the MDP RSUA approach for random sampling and uniform allocation and the MDP REUSE method which reuses the lower level MDP to allocate resources to the parallel subproblems. Through an experimental study which models the problem domain using the fire simulation components of the Robocup Rescue simulator, we show that both methods significantly outperform heuristic approaches and MDP REUSE provides an overall higher performance than MDP RSUA.     

分布式约束满足问题及其在MAS任务分配中的应用*

针对多智能体系统(MAS)任务分配问题中多个任务与MAS两者的分布式特征,将任务分配问题形式化为分布式约束满足问题(DCSP)进行求解,分别建立了以任务为中心和以agent为中心两种MAS任务分配模型,基于改进的DCSP分布式并行求解算法,提出了基于DCSP的MAS任务分配问题求解框架。该方法适合求解agent间通信有随机延迟以及agent间存在多约束的问题,应用实例的求解表明了其实用性与有效性。     

复杂约束条件下异构多智能体联盟任务分配

分布式任务决策是提高多智能体系统自主性的关键.以异构多智能体协同执行复杂任务为背景,首先建立了一种考虑任务载荷资源约束、任务耦合关系约束及执行窗口约束等条件的异构多智能体分布式联盟任务分配模型;其次,对一致性包算法(CBBA)进行了扩展,提出了基于改进冲突消解原则的一致性联盟算法(CBCA),以实现异构多智能体协同无冲突任务分配,并进一步证明了在一定条件下CBCA算法收敛于改进顺序贪婪算法(ISGA).最后通过数值仿真,验证了CBCA算法求解复杂约束条件下异构多智能体联盟任务分配问题的可行性和快速性.     

一种基于利益均衡的联盟形成策略

联盟形成是多Agent系统中的一个关键问题,主要研究如何在联盟内Agent间划分联盟效用,使Agent在决策时愿意形成全局更优的联盟.但已有策略对额外效用的平均分配没有顾及后加入联盟的Agent的利益,不利于全局优化联盟的形成.对此,给出一种基于利益均衡的联盟形成策略,在非减性效用分配等原则的基础上,提高了对额外效用分配的合理性,在面向任务的领域中可以达到全局优化解,较好地满足了稳定性、时效性以及分布等要求.