算法分析
基于粒子群优化算法
的多智能体系统分布式任务分配
郑小样曾志文
(国防科学技术大学机电工程与自动化学院湖南长沙410073)
数事我术与度用
摘要：本文提出了一种基于粒子群优化并且具备冲突消解能力的多智能体系统分布式任务分配算法。待多项任务分配给多个智能体是一个基础的资源分配问题，这类问题在很多控制和决策系统中出现，例如多机器人系统以及计算机系航。被用于分布式系统中解决此类问题的算法可以看做是一系列步媒，智能体能够利用这些步骤自动周期性地行信息交换并更新自已的任务。本文提出的算法经过仿真实验验证，仅需要少量的信息交换即可消解智能体之间任务分配的冲突。
关键词：粒子群优化分市式任务分配冲突消解
文章编号：1007-9416(2014)05-0138-02
中图分类号：TP301
文献标识码：A
多智能体系统(Multi一agentsystem)自90年代起就是一个热点研究课题，到如今这个领城已经有大量的科学成果。相应地，越来越多的多智能体系统应用被引人工厂、实验室基至普通家庭。同时这些应用的背景也越来越复杂，例如利用机器人搜救队在灾区搜导生还者。因此，为了保证多智能体系统的鲁棒性，分布式的任务分配算法是必要的。许多学者以及进行了这方面的研究。然面，这些分布式的任务分配算法需要智能体之间进行大量的通信来达到冲突消解的目的。
本文提出的分布式任务分配算法基于粒子群优化算法。该算法仅仅需要少量的通信解决冲突间题，面且粒子群算法本身只用到基
础运算法则，计算效率高。 1粒子群优化
粒子群优化是在1995年由Eberhart和Kennedy提出，这个算法是模仿鸟群智能：当一群年在寻找食物时，他们会倾向于搜索已经有食物被发现的区城。在粒子群算法中，粒子即是“鸟“而各个粒子的位置对应于所求优化间题的一个可行解。同时，每个粒子都有自己的搜索速度，该速度受全局最优解和个体最优解影响。
粒子群算法公式如下：
(gx 3saq8)pun + (x asaqd)pue*5 + 4 = t+ xk+1 = xk + vk+#
(3)(2)
其中k是粒子i在第k次选代中的速度，C,和c是加速因子， rand和rand是在区间(0,1)上的随机数，x是粒子在第k次送代
表1
任务
粒子群优化结果粒子位置代表的Agent
任务 Agentl Agent2 Agent3
任务 Agent1 Agent2 Agent3
138
方方数据
任务1 3
任务1 3 3
任务2 1 1 1
任务2 1 1
中的位置，pbest,是经过k次送代以后找到的个体最优解，gbest*是经过k次选代以后找到的全局最优解。
1.1粒子位置定义
任务分配问题中的可行解往往对应于Agent的编号，即为离散值而不是连续值，因此找到一个合适的粒子位置定义是将粒子群优化应用到任务分配间题中的关键点。本文采用元索均为整数的向量表示粒子的位置。该向量的维度与任务分配间题中的任务数相同，且各个向量中元素代表一个Agent的编号。表1用一个例子解释了上述向量。
根据这个定义，很明显向量中的元素X必须服从约束 XS[1,Agentmax]
在程序实现中可以将约束表示如下，
x<1
(1,
X=Agentmax X > Agentmi
(x,
otherwise.
1.2适应度函数
(3)
与粒子位置定义相同，要将粒子群优化应用到任务分配间题中适应度函数是不可或缺的。不同的适应度函数会导致不同的pbest和 gbest，从而得到不同的最优解。本文采用一种求和函数作为适应度函数，该函数方程如下：
其中R，表示Agent完成任务j可以获得的收益，h表示任务 j是否分配给了Agenti；如果任务的确是分配给Agenti的则h,=1，
......下转第140页
任务分配问题中粒子位置定义
任务1 3.14
Agent3
任务2 2.02 2 Agent2
表2分布式任务分配结果
任务3 3 3 3
任务4 2 2 2
任务5 3 3 3
表3冲突消解后任务分配结果
任务3 3 3 3
任务4 2 2 2
任务5 3 3 3
任务6 en 3
任务6 3 3 3
任务3 2.33 2 Agent2
任务7 2 2 2
任务7 2 2 2
任务8 2 N 2
任务8 2 2 2
任务4 1.98
Agent1
任务9 3-1
任务9-1-