（计算机软件与理论专业论文）基于遗传算法的多agent任务分配问题研究.pdf

l，f 。 f l ， 摘要 多a g e n t 理论及相关技术为分布式系统的研究提供了一个崭新的途径。多a g e n t 系 统理论是分布式人工智能体系的一个分支，目前多a g e n t 技术已经成为了当今人工智能 领域研究的热点之一。而多a g e n t 任务分配问题是多a g e n t 系统研究的基础性问题，体 现了系统高层组织形式与运行机制，是多a g e n t 系统实现目标的基础。一方面，任务分 配的好坏直接影响到整个系统的运行效率，并且直接关系到系统中各a g e n t 能否最大限 度发挥自己的能力，避免占用更多的资源。另一方面，当一个a g e n t 没有能力完成当前 任务时，如何在现有机制的基础上，通过有效地对话、协商使多a g e n t 合作完成此项任 务已经成为越来越多研究者关注的问题。 本文在此着重分析多a g e n t 系统中的任务分配过程，首先说明了多a g e n t 系统任务 分配问题是一种典型的组合优化问题，由于传统的任务分配问题的目标是充分利用分布 式系统多处理机的并行性，将一个任务分解成多个子任务，通过子任务的并行执行使问 题能够在最短的时问内解决。本文在此对任务的分解问题不再做详细阐述，只对在任务 分配的过程中如何将各个任务分配给拥有完成相应任务能力的a g e n t ，同时对冲突进行 合理的优化进行分析，然后通过对影响任务分配问题的因素进行分析，将遗传算法、蚁 群算法和模拟退火算法进行比较，得出结论：随着问题规模的不断增大，遗传算法在解 决任务分配问题中的优越性得到了充分体现，遗传算法相比其他常见的启发式算法有较 高的性能，能够用较少的时间得到更优的解。 很多传统技术对多a g e n t 任务分配问题的应用领域常常无能为力，而遗传算法却提 供了一条解决复杂任务分配问题的新途径，然而标准遗传算法在解决任务分配问题上存 在着局部搜索能力较差、收敛速度低等缺点，所以需要进一步对遗传算法进行改进，才 能使遗传算法在解决任务分配问题中发挥更加重要的作用。针对遗传算法这些缺点，本 文提出了两种改进方法，一种是将局部搜索能力强的算法引入到遗传算法，同时设计出 能适应新的编码方式的遗传算子，并在遗传算子中融入与问题相关的启发式知识，这样 可以使混合遗传算法既能保持遗传算法的全局最优特点，又能够提高其运行效率；另一 种方法是提出一种基于二叉树编码的遗传算法。首先将任务分配问题转化为等效的a o v 图，并将其转化成二叉树，然后进行遍历编码，最后用改进的遗传算子进行算法优化， 该算法克服了一维编码的局限性，比普通的一维编码遗传算法有更高的执行效率。 最后设计出一个多a g e n t 任务分配问题的实例，建立任务分配的目标函数，指导 a g e n t 与任务进行组合优化，利用改进的遗传算法来求解该多a g e n t 任务分配问题。通 过仿真试验比较了这两种改进的遗传算法和标准遗传算法在解决任务分配问题上的运 算性能。仿真结果显示两种改进的遗传算法无论是在搜索的速度还是搜索的精度上均优 于标准遗传算法，充分体现了遗传算法在解决多a g e n t 任务分配问题的可行性和优越性。 关键词：多a g e n t 系统，遗传算法，任务分配 i ”黪 r 一 a b s t r a c t m u l t i - a g e n tt h et h e o r ya n dt h ec o r r e l a t i o nt e c h n i q u eh a v ep r o v i d e dab r a n d - n e ww a yf o rt h e d i s t r i b u t i o n a ls y s t e m sr e s e a r c h t h em u l t i - a g e n ts y s t e mt h e o r yi sad i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e s y s t e m sb r a n c h ，a tp r e s e n tt h em u l t i a g e n tt e c h n o l o g ya l r e a d yb e c a m en o wo n eo fa r t i f i c i a li n t e l l i g e n c e a r e ar e s e a r c hh o ts p o t s b u tt h em u l t i - a g e n tt a s ka l l o c a t i o nq u e s t i o ni st h em u l t i - a g e n ts y s t e mr e s e a r c h f o u n d a t i o n a lq u e s t i o n ，h a sm a n i f e s t e dt h es y s t e mh i g h l e v e lc o n f i g u r a t i o no fo r g a n i z a t i o na n dt h e o p e r a t i o n a lm e c h a n i s m ，i st h em u l t i a g e n ts y s t e mr e a l i z e st h eg o a lf o u n d a t i o n a tt h es a m et i m e ，t a s k a l l o c a t i o nq u a l i t yi m m e d i a t ei n f l u e n c eo v e r a l ls y s t e m se f f i c i e n c y , a n dw h e t h e ri nt h ed i r e c tr e l a t i o ns y s t e m e a c hd o e sa g e n tm a x i m u ml i m i td i s p l a yo w na b i l i t y , a v o i d st a k i n gm o r er e s o u r c e s o nt h eo t h e rh a n d , w h e na g e n td o e sn o th a v ea b i l i t yc o m p l e t e st h ec u r r e n tm i s s i o n ，h o wi nt h ee x i s t i n gm e c h a n i s m s f o u n d a t i o n ，t h r o u g he f f e c t i v e l yt ot a l k ，t h ec o n s u l t a t i o nt oc a u s et h em u l t i - a g e n tc o o p e r a t i o nt oc o m p l e t e t h i st a s ka l r e a d yt ob e c o m em o r ea n dm o r er e s e a r c h e rm a t t e ro fc o n c e m t h i sa r t i c l ei nt h i sa n a l y z e si nt h em u l t i - a g e n ts y s t e m st a s ka l l o c a t i o np r o c e s se m p h a f i c a l l y ，f n s t e x p l a i n e dt h em u l t i - a g e n ts y s t e mt a s ka s s i g n m e n tp r o b l e mi so n ek i n do ft y p i c a lc o m b i n a t i o no p t i m i z a t i o n q u e s t i o n ，b e c a u s e t h et r a d i t i o n a lt a s ka l l o c a t i o n q u e s t i o n sg o a l u s e st h ed i s t r i b u t i o n a l s y s t e m m u l t i p r o c e s s i n gm a c h i n ep a r a l l e l i s mf u l l y , t a s kd e c o m p o s i t i o nc h e n gd u o g et h ec h i l dd u t y , e n a b l e st h e q u e s t i o nt h r o u g ht h ec h i l dd u t y sc o n c u r r e n te x e c u t i o nt os o l v ei nt h es h o r t e s tt i m e t h i sa r t i c l en ol o n g e ri n d e t a i le l a b o r a t e dt ot h et a s kd e c o m p o s i t i o nq u e s t i o nh o wo n l yt oe n a b l ee a c ht a s k a l l o c a t i o ni nt a s k a l l o c a t i o n sp r o c e s sf o rt oh a v ec o m p l e t e st h ec o r r e s p o n d i n gd u t ya b i l i t ya g e n t ，a n da v o i d sc o n f l i c t i n g c a r r i e so nt h er e a s o n a b l eo p t i m i z a t i o nt oc a r r yo nt h ea n a l y s i s t h e nt oa f f e c t st h et a s ka l l o c a t i o nq u e s t i o n t h ef a c t o rt oc a r r yo nt h ea n a l y s i s ，t h r o u g ht h eg e n e t i ca l g o r i t h m ，t h ea n tg r o u pa l g o r i t h ma n dt h e s i m u l a t i o na n n e a l i n ga l g o r i t h mw i l lc a n - yo nt h ec o m p a r i s o n w i l ld r a wt h ec o n c l u s i o n ：a l o n g 、i ms c a l e u n c e a s i n ge n l a r g e m e n t ，g e n e t i ca l g o r i t h m ss u p e r i o r i t yo b t a i n sm a n i f e s t s ，t h eg e n e t i ca l g o r i t h mc o m p a r e s o t h e rc o m m o nh e u r i s t i ca l g o r i t h m st oh a v et h eh i g hp e r f o r m a n c e ，c a l lu s et h ef e wt i m et oo b t a i nam o r e m a n yt r a d i t i o n a lt e c h n o l o g i e sa r ch e l p l e s sf r e q u e n t l yt ot h em u l t i - a g e n tt a s ka l l o c a t i o nq u e s t i o n s i i i a p p l i c a t i o nd o m a m ，b u th a sp r o v i d e das o l u t i o nc o m p l e xt a s ka s s i g n m e n tp r o b l e mn e ww a yu s i n gt h e g e n e t i ca l g o r i t h m ，b u tt h es t a n d a r dg e n e t i ca l g o r i t h ma l s oh a st h ep a r t i a ls e a r c ha b i l i t yi nt h es o l u t i o nt a s k a l l o c a t i o nq u e s t i o nt ob eb a d , t h ec o n v e r g e n c er a t el o ws t a t u ss h o r t c o m i n g ，t h e r e f o r en c e d st of u r t h e rm a k e t h ei m p r o v e m e n tt ot h eg e n e t i ca l g o r i t h m ，c a r le n a b l et h eg e n e t i ca l g o r i t h mt op l a yam o r ev i t a lr o l ei nt h e s o l u t i o nt a s ka l l o c a t i o nq u e s t i o n i nv i e wo fg e n e t i ca l g o r i t h mt h e s es h o r t c o m i n g s ，t h i sa r t i c l ep r o p o s e dt w o k i n do fi m p r o v e m e n t sg e n e t i ca l g o r i t h m s ，o n ek i n di si n t r o d u c e st h ep a r t i a ls e a r c ha b i l i t ys t r o n ga l g o r i t h m t h eg e n e t i ca l g o r i t h m ，s i m u l t a n e o u s l yd e s i g n sc a l la d a p tt h en e we n c o d i n gm e t h o dh e r e d i t yo p e r a t o r , a n d i n t e g r a t e si nt h eh e r e d i t yo p e r a t o rw i t ht h eq u e s t i o nr e l a t e dh e u r i s t i ck n o w l e d g e ，l i k et h i sm a ye n a b l et h e b l e n d i n gi n h e r i t a n c ea l g o r i t h mb o t ht om a i n t a i nt h eg e n e t i ca l g o r i t h mt h eo v e r a l ls i t u a t i o no p t i m i z a t i o n c h a r a c t e r i s t i c ，a n dc a nr a i s ei t so p e r a t i n ge f f i c i e n c y ；a n o t h e ra l g o r i t h mp r o p o s e do n ek i n db a s e do nt h e b i n a r yt r e ec o d ei m p r o v e m e n tg e n e t i ca l g o r i t h m f i r s tt r a n s f o r m st h et a s ka l l o c a t i o nq u e s t i o na st h e e q u i v a l e n ta o vc h a r t ，a n dt r a n s f o r m si tt h eb i n a r yt r e e ，t h e nc a r r i e so nt h et r a v e r s a lc o d e ，f i n a l l yu s e st h e i m p r o v e m e n tt h eh e r e d i t yo p e r a t o rt oc a r r yo nt h ea l g o r i t h mt oo p t i m i z e ，t h i sa l g o r i t h mh a so v e r c o m et h e u n i v a r i a t ec o d el i m i t a t i o n ，h a sh i g hc o m p a r e dt ot h eo r d i n a r yu n i v a r i a t ec o d eg e n e t i ca l g o r i t h mc a r r i e so u t t h ee f f i c i e n c y f i n a l l ye s t a b l i s h e sm o r et h a naa g e n tt a s ka l l o c a t i o nq u e s t i o nt h ee x a m p l e ，p r o p o s e st h ei m p r o v e m e n t g e n e t i ca l g o r i t h mu s i n gt h i sa r t i c l et os o l v et h em u l t i - a g e n tt a s ka l l o c a t i o nq u e s t i o n i no r d e rt or e a l i z et h e t a s ka l l o c a t i o nm e c h a n i s m ，e s t a b l i s h e st h et a s ka l l o c a t i o nt h eo b j e c t i v ef u n c t i o n ，i n s t r u c t sa g e n ta n dt h e d u t ) ，c a r r i e so nt h ec o m b i n a t i o nt oo p t i m i z e ，s o l v e st h em o s ts u p e r i o rt a s ka l l o c a t i o np l a nu s i n gt h e i m p r o v e m e n tg e n e t i ca l g o r i t h m h a sc o m p a r e dt h e s et w ok i n do fi m p r o v e m e n tg e n e t i ca l g o r i t h ma n dt h e s t a n d a r dg e n e t i ca l g o r i t h mt h r o u g ht h es i m u l a t i o nt e s t i n gi nt h es o l u t i o nt a s ka l l o c a t i o nq u e s t i o no p e r a t i o n p e r f o r m a n c e t h es i m u l a t i o nr e s u l td e m o n s t r a t e st w ok i n d o fi m p r o v e m e n t st h eg e n e t i ca l g o r i t h m s ， r e g a r d l e s s i n t h es e a r c hs p e e ds e a r c h e si nt h ep r e c i s i o ns u r p a s s e st h es t a n d a r dg e n e t i ca l g o r i t h m , m a n i f e s t e dt h eg e n e t i ca l g o r i t h mt os o l v et h em u l t i - a g e n tt a s ka l l o c a t i o nq u e s t i o nf e a s i b i l i t ya n dt h e k e y w o r d ：m u l t i - a g e n ts y s t e m ；g e n e t i ca l g o r i t h m ；t a s ka l l o c a t i o n i v t ” f 1 直 目录 摘要i a b s t r a c t i i i 目录v 第一章引言1 1 1 引言l 1 2 研究现状。2 1 3 多a g e n t 系统4 1 3 1a g e n t 的定义和分类4 1 3 2 多a g e n t 系统研究的发展5 1 3 3 多a g e n t 系统的研究热点6 1 3 4 多a g e n t 系统的应用领域7 1 4 本文的研究目的和内容8 1 4 1 问题的提出8 1 4 2 本文的研究目的8 1 4 3 本文的研究内容9 1 4 4 本文的组织结构9 第二章多a g e n t 任务分配问题1 l 2 1 多a g e n t 任务分配问题的提出l l 2 2 多a g e n t 任务分配问题的描述l l 2 2 1 任务分配问题的一般性描述。n 2 2 2 多a g e n t 任务分配问题的数学建模1 2 2 3 多a g e n t 任务分配问题的分类l3 2 4 解决多a g e n t 任务分配问题的算法1 6 2 4 1 影响算法的因素1 6 2 4 2 算法的比较17 2 4 3 遗传算法在解决任务分配问题的优势1 8 v 2 5 本章小结1 9 第三章遗传算法概述2 l 3 1 遗传算法的原理2 1 3 2 遗传算法的基本流程2 2 3 3 遗传算法的应用2 3 3 4 遗传算法的改进2 4 3 4 1 改进遗传算法的分类2 4 3 4 2 混合遗传算法2 7 3 5 任务分配问题中的遗传算法实现2 8 3 5 1 解决任务分配问题算法的产生2 8 3 5 2 遗传算法在解决任务分配问题中的产生和发展2 9 3 5 3 遗传算法实现2 9 第四章改进遗传算法的任务分配问题3 3 4 1 改进的混合遗传算法设计3 3 4 1 1 引入了具有相关知识的启发式算法设计编码方案3 3 4 1 2 引入改进的遗传算子3 4 4 1 3 改进的混合遗传算法实现3 4 4 2 改进的二叉树编码遗传算法设计3 6 4 2 1 二叉树编码3 6 4 2 2 改进的二叉树编码遗传算法实现3 8 4 3 仿真实验3 8 4 3 1 第一组实验3 9 4 3 2 第二组实验3 9 第五章总结与展望4 3 5 1 论文的总结4 3 5 2 下一步工作展望4 4 参考文献4 5 致谢4 9 攻读学位期间发表的学术论文目录一5 l v i t 、 j 硷 独创性声明5 3 关于论文使用授权的说明5 3 v l l t 气 & 一 第一章引言 1 1 引言 第一章引言 伴随着计算机技术、网络技术、电子通讯技术、无线传感技术以及人工智能技术的 发展，机器人的开发和利用得到了飞速的发展，机器人的发展可以分为三个阶段。第一 阶段机器人是指一种只通过程序员编程的简单重复操作的机器人。第二阶段机器人是指 带有一定适应能力，通过计算机的分析处理独立完成比较复杂操作的机器人。第三阶段 机器人则是指具有高度适应能力的智能机器人，智能机器人是各个学科领域的集中体 现，涉及到控制学、结构学、计算机技术、人工智能技术和其他的一些相关领域。 随着智能机器人的出现与现代工业科技的发展，许多复杂的任务很难由单独的一个 机器人完成，需要由更多的智能机器人来共同协作完成，因此现代工业和科学领域的研 究迫切的需要更多机器人完成更多复杂的任务，这些需求促使人工智能领域的研究重点 逐渐转移到多智能体机器人系统的研究上。一方面要通过增强单个机器人的性能来提高 系统的效率，另一方面要通过合理安排复杂的任务来提高各个智能机器人之间的协作能 力。 8 0 年代后期，随着分布式系统的逐渐成熟和人工智能技术的发展，出现了多种多机 器人合作的方法。这些多机器人方法都体现出比单个机器人系统更多的优势： ( 1 ) 当任务比较复杂的时候，单个机器人很难有足够的能力来完成这些任务，多机 器人就能通过能力互补来共同完成这些任务。 ( 2 ) 多机器人合作可以节省时间，提高工作效率。 ( 3 ) 多机器人系统的并行性可以帮助系统拥有更好的鲁棒性。 ( 4 ) 相互协作的n 个多机器人系统的工作能力可以远远大于单个机器人系统的n 倍。 但是多机器人系统也存在着很多需要改进的地方，包括以下几方面： ( i ) 怎样对机器人更好的表达、描述和分配任务。 ( 2 ) 怎样使机器人相互联系。 ( 3 ) 怎样解决各个机器人相互冲突的问题。 在分布式系统中，任务分配是一个研究热点。任务分配是分布式系统中的一个重要 基于遗传算法的多a g e n t 任务分配问题研究 环节，它对于发挥各处理单元的作用，从整体上提高系统资源的利用率等都具有非常重 要的意义。快速有效的任务分配策略实质是将任务合理和透明地在处理机之间进行分 配，并重新排列任务的执行顺序，以符合任务约束关系的要求，使整个系统的任务能在 最短的时间内完成，从而达到系统的综合性能最优。 多机器人任务分配问题是多a g e n t 系统研究的基础性问题，体现了系统高层组织形 式与运行机制，是多a g e n t 系统实现目标的基础。一方面，任务分配的好坏直接影响整 个系统的效率，而且直接关系到系统中各机器人能否最大限度发挥自己的能力，避免占 用更多的资源。另一方面，当一个机器人没有能力完成当前任务时，如何在现有机制的 基础上，通过有效地对话、协商使多机器人合作完成此项任务已经成为越来越多研究者 关注的问题。 多机器人任务分配可以看作是最优分配问题、整数线性规划问题、调度问题、网络 流问题或者组合优化问题。早期的多机器人任务分配方法多为集中式的，由一个管理者 负责分配任务给系统中其他机器人，虽然这样能得到全局最优解，但是也存在着很多问 题，如不能求解动态环境下任务分配问题等。随着分布式人工智能的发展，分布式任务 分配方法以其鲁棒性和高效性受到越来越多的关注。与集中式方法相比，分布式任务分 配方法能够得到更快更好的解，但多为近似最优解。 1 2 研究现状 经过三十多年来的发展，多机器人系统已经在理论和实践研究上有了很大的进展， 建立了很多多机器人的仿真系统和试验系统。目前国内对于多机器人系统的研究还处于 起步阶段，但是国外对于多机器人系统的研究却相当的广泛和深入。如欧盟设立专门进 行多机器人系统研究的m a r t h a 课题“用于搬运的多自主机器人系统( m u l t i p l e a u t o n o m o u sr o b o t sf o rt r a n s p o r ta n dh a n d l i n ga p p l i c a t i o n ) ，美国海军研究部和能源部也对 多机器人系统的研究进行了资助。从总体上讲目前多机器人系统的研究还处于实验阶 段，离实用化还有一定的距离。但是，进行多机器人系统的研究是机器人技术发展的必 然趋势，必将对机器人技术的发展带来划时代的变革。 目前多机器人领域的研究内容主要包括控制结构( 或体系结构) ，通信相冲突的解决 等问题。其中控制结构和通信问题属于多机器人系统中的高级控制任务，而冲突的解决 ( 包括防止死锁和路径规划等问题) 则属于多机器人系统中的低级控制任务。 2 厂 第一章引言 近几年对于多a g e n t 任务分配问题的研究逐渐向多领域的方向深入发展。研究方向包 括以下几方面： ( 1 ) 组合优化法 组合优化法是研究任务分配问题比较基础的方法，包括线性规划法、匈牙利算法【i 】 等，这些算法对于m 个a g e n t 、r 1 个任务的情况，通过对各个任务的有效值在某个集中点 统一获得，可以在相应时间内求得最优分配。但是该算法通信要求太高、计算量较大、 鲁棒性实时性不好。 ( 2 ) 基于市场机制的任务分配方法 基于市场机制的任务分配方法是目前研究最广泛的方法，该方法的基本思想是通过 合同协商实现任务分配策略，系统中的管理者将任务分解成多个子任务，寻找合适的任 务承担者来完成各项子任务，任务承担者依据自身的能力来做出评价，向管理者提交标 书，管理者依据特定的仲裁机制确定中标者，与其建立合同关系，并由其完成招标的子 任务。这是一种典型的意图式任务分配方法，系统中各个子系统以自私的方式，以子系 统的局部最优为目标来进行优化，最终获得最优解。基于市场机制的任务分配算法优点 是计算简单，适合大量子系统之间协调其相互活动，子系统删减自如，对系统的动态性 没有影响【2 】，但基于市场机制的任务分配方法对通信的要求过高，任务分配中的拍卖任务 可以是单任务也可以是多任务组合。 ( 3 ) 基于决策论模型的任务分配方法 近些年出现了一种利用决策论模型对任务分配问题进行建模【3 1 。由于m a s 中运行 环境、网络条件等因素的不同，利用多a g e n t 进行任务分配的时候必须考虑一些不确定 的因素和每个a g e n t 的感知能力、完成任务的能力、对其他a g e n t 的承诺能力、相互通 信的代价、任务的性质等等。利用决策论模型不仅可以刻画多个a g e n t 相互协助以完成 复杂问题的求解、合作，而且模型的求解结果可以提供这类具有多属性的任务分配问题 的解决方案。比如李为相等利用决策论模型提出了一种多属性m a s 任务分配模型及最 优任务分配原理，并采用了基于效用理论的多属性决策方法p r o m e t h e e i i 对m a s 任务分配算法进行有效地实证分析。 ( 4 ) 基于结构化的解决多a g e n t 任务分配方法 由于集中式分配方法不能适应变化的环境，而分布式的合同网适合于网络负载轻的 情况，所以在结合了分布式任务分配方法和集中式任务分配方法优点的基础上，提出了 基丁遗传算法的多a g e n t 任务分配问题研究 结构化分层任务分配机制，该机制降低了多a g e n t 之间通信的代价，具有灵活性好，反 应速度快等优点被广泛的应用多a g e n t 任务分配领域。 由于很多解决多a g e n t 任务分配问题的算法对于确定的静态环境是有效的，而对于 不确定的动态环境却无能为力，所以很多研究者针对具有动态模糊特性的任务环境进行 研究，并且借助其他相关理论来合理的模拟m a s 系统中任务分配的运行过程，并且能 获得优秀的任务分配策略和良好的分配结果。 多机器人任务分配问题一直被公认为是一类n p 问题【4 1 。传统的方法大多采用集合 划分和覆盖的理论【5 1 或线性规划逼近的方法【6 】。近年来，有很多学者将遗传算法用于任 务分配问题的研究【7 】【7 】【9 】【10 1 ，利用遗传算法的全局性和鲁棒性。例如： ( 1 ) 针对传统遗传算法中初始种群的构造和遗传算子的局限性，结合遗传算法和演化 策略的优点，提出了一个异构系统中任务分配的进化算法。 ( 2 ) 设计了一种基于问题空问的遗传算法。 ( 3 ) 在遗传算法中动态地改变控制参数，是种群快速的向更好的解进化。 1 3 多a g e n t 系统 1 3 1 a g e n t 的定义和分类 a g e n t 是多a g e n t 的基础，a g e n t 源于计算机学科和分布式人工智能，a g e n t 一般 被认为是一个物理的或抽象的实体，它能作用于自身和环境并能对周围环境作出反应， a g e n t 的典型特性有自主性、主动性、社会交互性及反应性等。概括地说，a g e n t 是一 个知识表示与分析推理有机结合的能动的实体【1 1 】。m u l t i - a g e n ts y s t e m 是近三十多年来 蓬勃兴起的崭新的计算机学科，许多来自不同领域的研究者都在努力地从各自的角度来 研究a g e n t 技术。尽管这个领域还处于起步阶段，但它强劲的发展势头决定其必将成为 计算机科学发展最快的领域之一。 a g e n t 相对典型的定义就是：a g e n t 系统就是一类具有自主性的能够不断感应和作 用于环境，完成计划需要完成相应任务的系统。虽然a g e n t 研究领域对a g e n t 一直没有 一个统一的定义，但是a g e n t 领域的研究者却对于a g e n t 的弱性定义和强性定义概念【1 2 】 有着比较一致的观点。 a g e n t 的弱性定义是指具有自主能力、社交能力、反应能力、预动能力的硬件系统 或者基于软件的计算机系统。这一定义已经在很多领域被广泛认可。但是在人工智能领 4 ， 第一章引言 域，大部分研究者更强调它应该具有很多人类的属性，比如人类的精神状态，于是提出 了强性定义，强性定义指除了具有弱性定义的能力以外还具有知识和信念、意图和义务、 诚实和理性等人类所特有的特征。 逐渐地，a g e n t 技术已经融入到计算机的各个领域，所以从不同的角度可以对a g e n t 进行各种分类： ( 1 ) 根据a g e n t 的存在形式可以分为有形a g e n t 和无形a g e n t ，有形a g e n t 一般是 指机器人或者是操作者本身。无形a g e n t 一般是指与a g e n t 相关的软件，然后共同作用 于一台或多台计算机中。 ( 2 ) 根据a g e n t 的移动性可以分为静止a g e n t 和移动a g e n t ，对有存在实体的a g e n t 比较好理解，移动a g e n t 可以指移动机器人。而对于无形实体的a g e n t 来说，移动a g e n t 可以是在计算机网络中互相联系的应用程序等等。 ( 3 ) 根据a g e n t 的思维深度可以分为反应型a g e n t 、深思型a g e n t 和混合型a g e n t 。 反应型a g e n t 没有任何的符号模型来表示周围环境，而深思型a g e n t 可以通过一些符号 推理模型来和其他的a g e n t 相互联系。混合型a g e n t 则是反应型a g e n t 和深思型a g e n t 的结合。 ( 4 ) 还可以根据基本属性把a g e n t 分成协作a g e n t 、协助学习a g e n t 和交互型a g e n t 。 这些分类都不是非常清晰的区分开来，只是为了突出强调他们的主要功能。 1 3 2 多a g e n t 系统研究的发展 多a g e n t 系统m a s ( m u i t i a g e n ts y s t e m ) 是指由多个可以进行计算的a g e n t 组成的集 合，其中a g t 可以是一个实体也可以是一个抽象的物体，可以作用于自身的环境。 m a s 理论的研究实质是分布式人工智能体系的一个分支，分布式人工智能d a i ( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ) 偏重于对计算机制的研究，但是随着人工智能研究 的不断深入，出现了协商理论、a g e n t 之间的学习、分布推理和通讯语言等新兴的研究 领域。 m a s 理论的研究主要面向两类应用环境，一类是在网络中有自主运行能力的节点 之间，如计算机集成制造和实现网络化的工业等等。另一类是本质上集中式的应用问题， 但可以通过分布式的算法取得更好的解。 m a s 理论是从实际应用中慢慢发展起来的，所以研究和应用是在一起共同进步的， 基丁遗传算法的多a g e n t 任务分配问题研究 虽然八十年代就有了m a s 理论的研究，但直到九十年代m a s 理论才因为工业等产业的迫 切需要，迅速的与其他系统相结合逐步发展起来的， 1 3 3 多a g e n t 系统的研究热点 在l v i a s 当中我们主要研究的目标是构造一个可以与其他系统相互协作，具有自主 决策能力的系统【1 3 】。根据这个研究目标国内外研究学者通过从以下几个方面的研究来开 展工作。 ( 1 ) 为多a g e n t 的行为建立公式化的数学模型 r a o 等人提出基于模态逻辑的b d i 模型理论是最具代表性的，但其“逻辑全知 问题又是影响理论进一步发展的因素：另外，还有j o s e p h 提出的关于知识和信念的逻辑 1 5 ；c o h e n 提出的描述a g e n t 预知观念的逻辑【1 6 】。但这些采用正规模态逻辑建立的模型均 未能摆脱逻辑全知的困难【17 1 ( 2 ) a g e n t 之问的任务分配与协作 在m a s 当中每个a g e n t 之间相互作用，共同完成m a s 的目标。a g e n t 之间的任务 分配与协作是m a s 研究的核心问题之一，它包括在执行复杂的任务的时候合理的分配 和分解任务，各a g e n t 协作策略等等问题，多a g e n t 系统中存在着许多能够独立求解问 题的a g e n t ，但是，许多复杂系统中的问题并不是单个a g e n t 就能独立完成的。所以对 于这些复杂问题，可以依据一定的原则和方法将其分解为一系列能被a g e n t 独立解决的 子问题。然后把这些子问题分配给那些能够完成的a g e n t 来求解，就是一个任务分配问 题。通过多a g e n t 之间的任务分配与协作，不仅弥补了单个a g e n t 在知识、能力上的不 足，同时也提高了系统求解问题的能力，拓宽了系统的应用。因此，任务分配机制是研 究的热点问题之一。例如由于a g e n