（计算机软件与理论专业论文）基于agent的分布式入侵检测系统研究(1).pdf

基于a g e n t 的分布式入侵检测系统研究摘要嗣络入侵是指企图占用、偷窃或者毁坏他人的计算机信息资源的行为。网络入侵为网络上的信息、资源带来了严重的安全威胁。特别是目前出现了一些难以对付的逃避入侵检测的方法，如慢速攻击、变换特征、插入和逃遁、破坏日志系统、系统内核篡改、拒绝服务攻击等。面对上述的入侵，传统的基于主机的入侵检测系统和基j 二网络的入侵枪测系统显示出其局限性。由此提出了分布式入侵检测的思想，即采用多个检测部件，各检测部件选用不同的检测方法，协同合作，完成检测任务。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 的分布式入侵检测系统m a i d s ，从系统的可靠性、可用性、准确性和适应性等方面进行了理论分析，并实现其主要功能模块，通过实验证明其理论上可能存在的优点。本文所做的创新性的工作主要如下：1 从伦理学和仿生学的角度总结了现存一些多a g e n t 系统存在的问题。2 改进了联盟等多个a g e n t 之间的合作机制，其主要工作建立在由j e n n i n g s 等人于2 0 0 4 年提出的f i r e 模型的基础上。3 提出了多a g e n t 系统的伦理学模型。4 基于a g e n t 技术，设计分布式入侵检测系统m a i d s 模型。关键词：分布式入侵检测系统多a g e n t 系统联盟t h er e s e a r c ho nd i s t r i b u t e di n t r u s i o nd e t e c t i o ns y s t e mb a s e do na g e n ta b s t r a c ti n t r u s i o nd e t e c t i o n sa r et h eb e h a v i o r st h a ts o m e o n ew a n t st oo c c u p y ，s e i z eo rd e s t r o yo t h e rp e o p l e sc o m p u t e rr e s o u r c e i n t r u s i o nd e t e c t i o nb e h a v i o r sb r i n gas e r i o u ss a f e t yt h r e a tf o rt h ei n f o r m a t i o na n dr e s o u r c e so ft h en e t w o r k r e c e n t l y ，s o m ei n t r u s i o nm e t h o d st h a tw e r eh a r dt od e t e c tw e r ea p p e a r e d f o re x a m p l e ，s l o wi n t r u s i o n ，c h a n g ec h a r a c t e r ，i n t e r l e a v ea n de s c a p e ，d e s t r o ys y s t e ml o g ，d i s t o r to p e r a t i n gs y s t e mk e r n e l ，d e n yo fs e r v i c ea n dt h et r a d i t i o n a li n t r u s i o nd e t e c t i o ns y s t e m sw h i c ho n l yb a s e do nh o s to rn e t w o r kd i s p l a yt h e i rl o c a l i z a t i o nt od e t e c tt h e s ei n t r u s i o nb e h a v i o r s d i s t r i b u t e di n t r u s i o nd e t e c t i o nw a sp r o p o s e d ，t h a ta d o p ts e v e r a ld e t e c t i o n sp a r t s ，a n de a c hp a r tc h o o s e sd i f f e r e n td e t e c t i o nm e t h o d ，t h e nw o r kt o g e t h e rt oa c c o m p l i s ht h ed e t e c t i o nt a s k a g e n th a sg a i n e dc o n s i d e r a b l er e s e a r c hi n t e r e s t si nr e c e n ty e a r s ，i th a sas i g n i f i c a n tp o s i t i o ni nc o m p u t e rs c i e n c e ，a n dh a sa l r e a d yg o ta ne x t e n s i v ea p p l i c a t i o ni nd i s t r i b u t e dc o m p u t i n g t h ei n t r u s i o nd e t e c t i o ns y s t e m sw h i c hb a s e do na g e n tt e c h n o l o g ym a yn o to n l yr e a l i z ed i s t r i b u t e di d e a ，b u ta l s oh a v et h ei n t e l l i g e n tc h a r a c t e r i s t i c s ，s ot h e yc a nd e t e c tn e wi n t r u s i o nb e h a v i o r s p a r t i c u l a r l y ，m u l t i - a g e n ts y s t e mh a ss p e c i a la d v a n t a g e si nt h ea p p l i c a t i o no fl a r g e s c a l e ，d i s t r i b u t e da n dc r o s s p l a t f o r mc o m p u t i n g i tc a na c c o m p l i s ht h ed e t e c t i o nt a s ko v e r a l ls i t u a t i o n ，m a k et h es y s t e m sh a v ec l e a rs t r u c t u r e s ，g o o de x p a n s i b i l i t i e sa n dt r a n s p l a n t a t i o nt h a tu s i n ga g e n tt od i s t r i b u t e di n t r u s i o nd e t e c t i o ns y s t e m s s ot h e yn e e d n tm a n yh o s ta n dn e t w o r kr e s o u r c e s ，c u td o w nt h ep o s s i b i l i t yo ft h eb o t t l e n e c k ，a n da p tt od i s t r i b u t es e r v i c e t h er e s e a r c hw o r ko ft h i sd i s s e r t a t i o ni n c l u d e s2s i d e s ，a g e n ta n dd is t r i b u t e di n t r u s i o nd e t e c t i o n i tp r o p o s e sad i s t r i b u t e di n t r u s i o nd e t e c t i o ns y s t e mn a m e dm a i d s ，b a s e do ns u m m a r i z i n ga n di m p r o v i n gt h ec o o p e r a t i n gt h e o r i e sb e t w e e na g e n t s t h i sd i s s e r t a t i o na n a l y z e sb yt h e o r ym e t h o d sf r o md e p e n d a b i l i t y ，d e s i r a b i l i t y ，a c c u r a c ya n ds u i t a b i l i t yo ft h es y s t e m a n dr e a l i z e ss o m em o d u l e so ft h es y s t e m ，p r o v e st h em e r i t st h a ti tm a yh a sb ye x p e r i m e n t t h ec r e a t i v ew o r k so ft h i sd i s s e r t a t i o ni n c l u d e sa sf 0 1 i o w s ：1 s u m m a r i z i n ge x i s t i n gm u l t i a g e n ts y s t e m si nt h ev i e wo fb i o n i c sa n de t h i c s 2 i m p r o v i n gt h em e t h o d so fc o o p e r a t i n gb e t w e e na g e n t ss u c ha sc o a l i t i o n ，m a n yw o r ka r eb a s e do nt h ef i r em o d e lo fm u l t i - a g e n ts y s t e mt h a tp r o p o s e db yj e n n i n g si n2 0 0 4 3 p r o p o s i n gt h ee t h i c sm o d e o fm u l t i a g e n ts y s t e m ，4 d e s i g n i n gm a i d s w h i c hi sam o d e lo fd i s t r i b u t e di n t r u s i o nd e t e c t i o ns y s t e mb a s e do na g e n t k e y w o r d s ：d i s t r i b u t e di n t r u s i o nd e t e c t i o ns y s t e m ，m u l t i - a g e n ts y s t e m c o a l i t i o n合肥工业大学本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士学位论文质晕要求。主席：委员：导师：答辩委员会签名丝殇中卿灭磁独创性声明本人，嘲所警交的学位论文是本人在导师指导f 进行的研究f 作及取得的研究成果。据我所知。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得盒壁j ：、业盘堂或其他教育机构的学位或证幸；而使用过的材料。与我一同i ，作的问，占对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论义作者签名：专勃u签字日期：三，年争j 矽口学位论文版权使用授权书本学位论文作者完全了解盒罂王些盍堂有关保留、使用学位论文的规定，有权保留_ ，f = 向国家有关部门或机构送交论文的复印件和磁盈，允许论文被查阅和借阅。本人授权金鲤王业盔堂可以将学位论文的全部或部分内容编入有关数据库进子检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)学位论文作者签名：苍钆签字日期：2 眄年牛月吝d 日学位论文作者毕业后去向：南虿p 芝技1 ，作单位：翎e 二箩大学胡 日学椤。通讯地址：导师签名：f ：a r ( r ，s ) ，其中：历p 表示信息素痕迹挥发后的剩余度；若蚂蚁k 访问过支路( r ，s ) ，t( r ，s ) o = q l k ，否则为0 。q 为常数，表示一只蚂蚁一周期内在路径上留下的信息素总量。蚁群系统中的蚂蚁称为人工蚂蚁，一般由移动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 中的仿动物技术的发展趋势之一。2 4 3 仿生物机体大自然的进化本着优胜劣汰、适者生存的原则，许多生物机体本身对开放环境具有很强的适应性。利用生物机体本身的特性，构造相应的多a g e n t 系统，能够有效解决某些特定的问题。仿生物机体在多a g e n t 系统中应用的典型代表就是基于免疫学的多a g e n t 系统，它被广泛应用于分布式入侵检测系统。基于免疫学的多a g e n t 系统主要模拟人体内的免疫系统。在病原体带来的生存压力和自然界的遗传、变异、选择作用下，人类进化出了适应的、分布的、高效的、多样的和多层次的维持生存和保持健康的机制，这就是人体内的免疫系统。免疫机制可以为改善计算机的安全提供借鉴，通过对自然免疫系统的模拟研究，可能会使计算机安全系统获得许多理想的特性。例如，文献【8 3 】给出了免疫系统的形式化描述，文献f 8 4 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 中的应用分为仿人类、仿动物和仿生物机体3 个方面，并认为结合几种动物或人类的合理行为构造更优化的多a g e n t 系统将是a g e n t 中仿生技术应用的重点和发展趋向。2 5小结本章对现有关于多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 系统模型研究中存在的问题以及克服这些问题所要做的工作。2 3 节的主题思想是伦理学的思想将在多a g e n t 系统研究中得到重视，并应用于a g e n t 间的协作。2 4 节通过将a g e n t 的研究工作从仿人类、仿动物和仿# 物机体3 个方面进行说明，提出了如f 重要论断：结合几种动物或人类的合理行为构造更优化的多a g e n t 系统将是a g e n t 中仿生技术应用的重点和发展趋向。第三章多a g e n t 系统的改进工作3 。1引言信任和名誉的概念越来越受到多a g e n t 系统理论研究领域的重视，这是因为信任和名誉能够有效促进多个a g e n t 之间进行合作。特别是在开放性的多a g e n t 系统中，由于a g e n t 可以在任何时候进入或退出计算，所以信任和名誉越发显得重要。比较常见的信任和名誉模型有e b a y 8 5j 和a m a z o na u c t i o n s i8 6 1 等。在这两种系统中都提供了一个集中评价a g e n t 信任和名誉值的静态数据中心，通过对这个数据中心的访问，a g e n t 能够学习到其他a g e n t的名誉值，并确定对其的信任程度。z a c h a r i a 和m a t s 提出的s p o r a s l 87 i模型改进了上述两种模型，在s p o r a s 中a g e n t 的名誉值可以动态更改。但，s p o r a s 集中式的控制方法使其仍然不能有效应付开放性的分布式计算环境。h u y n h 和j e n n i n g s 等人在文献【8 8 】中对信任和名誉机制作了进步的研究，提出了多a g e n t 系统的f i r e 模型，并在此模型基础上二讨论了a g e n t 之间的合作过程，还通过实验证明了与s p o r a s以及不存在信任机制的多a g e n t 系统相比f i r e 具有的高效性。但是文献【8 8 】既没有给出完整的a g e n t 形式化描述，也没有进。+ 步研究建立a g e n t 联盟可能会对系统效率的进一步提高。自1 9 9 3 年文献f 8 9 9 0 】等提出联盟方法以来，s a n d h o l m & l e s s e r 一1以及罗翊和石纯一1 4 7 1 、徐晋晖 7 2 1 等人作了进一步的深入研究，已取得了定的进展。通过联盟可以提高a g e n t 求解能力，获得更多的报酬，因此联盟足多a g e n t 系统中a g e n t 合作的一种重要的方法和途径。本章研究工作将围绕f i r e 模型展开，这是j e n n i n g s 于2 0 0 4 年提出的一种信任和名誉模型。接下来的2 节内容，针对f i r e 模型做了一些改进工作：3 4 节提出了多a g e n t 系统的伦理学模型，它可以被认为是f i r e 模型的扩充模型；最后对本章的工作做了简要的小结。本章内容是对上一章的进一步深化并作为下一章分布式入侵检测系统的理论基础。3 2 基于f i r e 模型的a g e n t 联盟研究+3 2 1 基于f i r e 模型的a g e n t 语义描述h u y n h 和j e n n i n g s 等人在文献【8 8 】中提出了多a g e n t 系统的f i r e模型，认为a g e n t 的信任和名誉模型包括4 个组成部分：i t ( i n t e r a c t i o nt r u s t ) 、r t ( r o l e b a s e dt r u s t ) 、w r ( w i t n e s sr e p u t a t i o n ) 和c r ( c e r t i f i e dr e p u t a t i o n ) 。其中，i t 是彼此直接交互的a g e n t 之间给予对方的t r u s t值；r t 是两个a g e n t 合作中由于角色关系给予对方的t r u s t 值；w r 是a g e n ta 希望和a g e n tb 合作时，通过调查发现的其他a g e n t 给予a g e n tb 的名誉值；c r 则是a g e n t 在过去与其他a g e n t 合作的过程中，通过其他a g e n t 列自己的服务质量等的反馈意见给自己的名誉上的自我评价。基于f i r e 模型的思想，a g e n t 通过定义1 给出：定义3 1 a g e n t 是由如下组成部分构成的元组，a g e n t = d e f ，其中，泌是a g e n t 的标识符，不同的a g e n t 应该具有不同的埘；g o a l 是a g e n t 的目标集，其元素是a g e n t 需要达到的目标，以及达到这些目标需要完成的一些子目标。g o a l 的初始值是空集，即a g e n t尚未接到任何任务。g o a l 元素的确定应该是一个不断扩充的动态过程，直到a g e n t 完成规定任务。子目标集的最后一个元素与其上层目标相同，表示卜层目标的实现。例如。a g e n ta 的目标集g o a l 。= g o g 。o ，g o7 ，9 0 2 ，9 0 3 ) ，g j g ，o ，g j ) ) 表示a g e n t 有2 个最终目标g o 和g l ，要达到目标g o 则需通过子目标g o 。，g o ，9 0 7 ，和g o s = g o 的逐步实现，同样，为达到目标g ，的要通过实现子目标g ，。和g = g t 两步来实现；a c t 是a g e n t 的动作集，其形式为4 c t = a c l o ，a c t ，a c l 。 ，说明a g e n t 值能够完成哪些动作；彳，咖是a g e n t 的盟友集合，其元素是a g e n t 结成的联盟中其他a g e n t 的i d 集合。爿，眵的初始值是空集，表明a g e n t 尚未与其他a g e n t结成联盟：丁一月= ，lr t ，w r ，c r ) 是a g e n t 给予其他a g e n t 和自己的t r u s t 和r e p u t a t i o n 值；r u l e 是a g e n t 与其他a g e n t 合作的规则集，基于f i r e 模型的a g e n t的规则集形式为r u l e = ? j t ? r t ，? w r ，? c r ) 表示a g e n t 希望与其他本节主要内容已投微电子学与计算机2 8a g e n t 合作时，要预先对其，7 、尺，、w r 以及c r 进行测试，如果其他a g e n t 的，r 、月r 、w r 、c r 值满足合作的条件，则双方共同合作进行问题求解；y ：爿c 卜+ d 是资源需求函数，表示a g e n t 完成动作a c t 需要的资源数日是d ；是a g e n t 通信语言，不同的a g e n t 之问以进行通信。在定义3 1 中，为了使a g e n t 容易结成联盟进行问题求解，在f i r e模型的基础上为a g e n t 增加了一个爿，炒属性，用t ：指示与a g e n t 结成联盟的其他a g e n t 。3 2 2 基于联盟的求解算法联盟是多a g e n t 系统中a g e n t 合作的一种重要的方法和途径，通过联盟可以提高a g e n t 求解能力。本文采用文献【7 2 】中关于a g e n t 联盟问题的一般描述。设a g e n t 集= 一，a 2 ，a 。) ，资源集q = ( g ，q 2 ，g 。) ) ，其中q i = ( 日，7 ，q 一，g ，“) ，g ，表示彳。第，种资源的数量；任务集7 1 = 丁，乃，l ，其中t i = f 。，t ，。，t ，) 是4 ，的任务集，f 是a ，的第_ ，个任务，对每一个任务有对应的资源需求说明；每一个a g e n t 开始都持有一定的资源。则一个联盟c 可以用( 心，q 。，q 。，t c ，t 。，矿俐，以) 来描述，其中c 是的子集，q 。是c 拥有的资源，q 。是资源分配的结果，l 是c 的任务集合，r 。是任务分配的结果，矿阳是联盟的值，u = ( “，u l 。j ) 是吖一对c 成员的一个分配。联盟问题是求一个满足稳定性要求的 u 。c s ，( u ，c s ) 为问题求解的一个中间状态或最后结果，其中联盟结构c s = c ，c 2 ，( 是v 的一个划分，u - ( “j ，甜2 ，。) 是每个a g e n t 所得报酬的描述。由于f i r e 不是一种效用模型，本文规定联盟值以目标集的形式给出，联盟中的a g e n t 可以访问联盟值，从而扩大各自的知识面，提高问题的求解效率。f i r e a g e n t 构成联盟进行问题求解过程通过算法3 1 给出：算法3 1 由月个a g e n t 构成的多a g e n t 系统中，a g e n t 以联盟方式进行求解。假设a g e n ta 。是第一个获得计算任务的a g e n t ，( 可能有多个a g e n t 同时获得计算任务，选择其中之一作为a o ) 。步骤j 初始化，对v a ，n ，a ，g o a l ：= m ，a t a i l y ：= 中；步骤2 根据求解目标，为接收到某些任务的a 。g o a l “g ) 进行赋值；步骤3 ao 判断能否直接达到自己的目标，能则转到步骤9 ，否则继续；步骤4 a o 是否已经存在盟友( 是否已经建立联盟) ，有则转剑步骤6 ，无则继续；步骤5 a 口测试其他a g e n t 的，7 、尺t 、w r 和c r 值，建立联盟；步骤6 a o 逐个检测联盟中其他a g e n t 是否能够完成其目标，若存在彳，能满足要求，则转到步骤8 ，否心继续：步骤7 a d 从a d a c t 中选择一个能够满足执行条件的a c t 执行转步骤3 ：步骤8 a o 参照a ，g o a l 中的相应目标，完成其目标：步骤9 a o 达到计算目标，结束计算。算法3 1 步骤1 对a g e n t 的g o a l 和az l y 进行赋初值，因为a g e n t尚未接收到计算任务，也未参与计算所以这2 个集合均赋初值为空集；步骤2 说明a g e n t 接收到计算任务( 同时接收到计算任务的可能还有其他a g e n t ，对它们的g o a l 也要赋值；若其他a g e n t 没有接收到计算任务，则其g o a l 保持不变) ：步骤3 到步骤9 是a g e n t 通过联盟进行问题求解的过程，步骤3 的含义有2 点：( 1 ) a g e n t 可能处于特殊的位置，正好满足目标的要求，则不需再计算；( 2 ) a g e n t 经过若干次计算，达到了目标，此时相当于对某个目标毋，通过进行子目标用。譬j ，自= 譬，的逐步解决，已达到求解目标，螅0 结束计算；步骤4 和步骤5 表明a g e n t 根据f i r e 模型的原则建立联盟；步骤6 和步骤8 结合说明a g e n t 通过借用联盟中其他a g e n t 的有用的目标集来提高求解效率：步骤7 说明在a g e n t 寻求不到盟友帮助的情况下，自己执行个随机的动作，以探测可能达到目标的路径：步骤9 是指a g e n t 完成自己的求解目标，结束自己的求解过程，但整个系统可能仍在继续计算，此时a g e n t 还不能完全终止，其目标集可能会被其盟友a g e n t 利用。3 2 3 实验及其结果分析文献f 8 8 在给出f i r e 模型的同时。通过实验验证了与s p o r a s 以及不存在信任机制的多a g e n t 系统相比f i r e 具有对问题求解的高效性。本节仅在f i r e 模型没有引入联盟( 但a g e n t 寻求靠近它的其他a g e n t 的帮助) 和引入联盟( 算法1 ) 2 种情况下，做如下a g e n t 随机行走实验，证明采用联盟机制进一步提高了f i r e 模型的求解效率。实验操作系统环境为w i n d o w sx pp r o f e s s i o n a ls p l ，编程语占为d e v c + +4 9 9 0 。设有4 个a g e n t 在8 8 方格环境下做随机行走，从不同起点( 随机给出) 出发寻找某个终点，每次只能沿水平或垂直方向前进一步，所有4 个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 没有到过的方格。图i 所示是独立实验3 次的结果，图中横坐标表示独立求解的次数，纵坐标表示每一次求解过程所有a g e n t 由起点走到终点所需步数之和。因为a g e n t 在需要移动之前必须测试环境以确定移动方向，所以在此实验中，所有a g e n t 测试次数之和也与算法效率密切相关。圈2 是对应于图1 所示8 次实验，2 种求解方式下所有a g e n t 测试次数之和的比较图，图中横坐标仍然表示独立求解的次数，纵坐标表示每一次求解过程所有a g e n t 对环境测试次数之和。图3 18 8 方格环境移动次数比较图3 28 8 方格环境浏试次数比较3 1比较陶1 和图2 中的曲线能够看出，在某些特殊情况下，就近a g e n t合作方式求解效率呵能接近( 第1 、6 次实验) 、或略高于( 第8 次实验) 联盟方式，f h 总体来说，在f i r e 模型中引入联盟机制比爿i 结成联盟进行求解的f i r e 求解速度快，求解效率有显著提高。3 3 一种基于f i r e 模型的a g e n t 联合测谎算法+3 3 1 说谎行为测度和控制算法联盟是多a g e n t 系统中a g e n t 合作的一种重要的方法和途径，通过联盟可以提高a g e n t 求解能力，3 2 节的实验结果证明了在f i r e 模型巾引入联盟机制能够提高其运算效率。本节将在联盟合作方式下，讨论对a g e n t 说谎行为的测度和控制算法。本文采用3 2 节关于a g e n t 联盟问题的一般描述。由于f i r e 不是一种效用模型，本节仍然规定联盟值以目标集的形式给出，联盟中的a g e n t 可以访问联盟值，从而扩大各自的知识面，提高问题的求解效率。对a g e n t 说谎行为进行测度和控制通过算法3 2 实现：算法3 2 由h 个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 是第一个获得计算任务的a g e n t ，( 可能有多个a g e n t 同时获得计算任务t 选择其c ，之一作为a nj 。步骤1 初始化，对v a 。e n ，a g o a l ：= 中，一a l l y ：= m ；步骤2 根据求解目标，为接收到某些任务的a g o a l ( ，劲) 进行赋值；步骤3 a 。剀断能否直接达到自己的目标，能则转劐步骤9 ，否则继续步骤4 a 。是否已经存在盟友( 是否已经建立联盟) ，有则转到步骤6 ，无划继续；步骤5 a n 测试其他a g e n t 的i t 、r t 、w r 和c r 值，建立联益n ? 、步骤6 ao 逐个检测联盟中其他a g e n t 是否能够完成其目标，若存在a ，能满足要求。则转到步骤8 ，否则继续；本节主要内容己投系统仿真学报步骤7 a 口从a da c t 中选择一个能够满足执行条件的a c l 执行，转步骤3 ：步骤8 ，联盟中最易达剑a ，所提供目标的a g e n t 对此目标进行测试若彳，说谎，继续，否则转步骤1 2 ；步骤9 对v a 女n 。，减小其芙y - a ，的，丁、月r 、w r 和c r 值；步骤l0 若联盟中其他a g e n t 关丁二a ，的，r 、r r 、w r 和c r 值之干1 1 小】某规定值( 说谎次数太多。不能够再信任) ，将a ，从n c 中删除；步骤1 1 转步骤7 ：步骤1 2 一。参照彳，g o a l 中的相应目标，完成其目标；步骤】3 ，一。达到讨算目标，结束计算。算法3 2 步骤1 对a g e n t 的g o a l 和a t z y 进行赋初值，因为a g e n t尚未接收到计算任务，也未参与计算，所以这2 个集合均赋初值为空集：步骤2 说明a g e n t 接收到计算任务( 同时接收到计算任务的可篚还有其他a g e n t ，对它们的g o a l 也要赋值；若其他a g e n t 没有接收到计算任务，则其g o a l 保持不变) ；步骤3 的含义有2 点：( 1 ) a g e n t可能处于特殊的位置，正好满足目标的要求，则不需再计算：( 2 ) a g e n t经过若于次计算，达到了目标，此时相当于对某个目标g ，通过进行子日标g ，“，g i j ，g 。= g 。的逐步解决，已达到求解目标，则结束计算：步骤4 和步骤5 表明a g e n t 根据f i r e 模型的原则建立联盟。：步骤6 表明a ，声明与求解目标相关信息；步骤8 至步骤i l 是联盟c叶1 各a g e n t 联合对4 ，进行测谎，步骤8 表明联盟。中a g e n t 对爿，测谎时，采用距离彳，提供的目标最近者进行测试，从而保证测试工作最小；彳，说谎，则联盟c 各a g e n t 通过步骤9 减小关于爿，的相应l r 成员值，对其进行谴责；当联盟f 中各a g e n t 对a ，评价太差( i t 、r t 、w r 和c r 值之和小于某规定值) ，则通过步骤1 0 将4 ，从联盟札中剔除；步骤1 2 表明a ，提供了真实的信息，ao 能够根据此信息顺利达到目标；步骤1 3 是指a g e n t 完成自己的求解目标，结束自己的求解过程，但整个系统可能仍在继续计算，此时a g e n t 还不能完全终止，其目标集可能会被其盟友a g e n t 利用。3 3 2 实验及其结果分析本节在f i r e 模型中各a g e n t 以联盟方式进行问题求解情况下，针对指定测谎a g e n t 、联合测谎以及联盟中不存在说谎a g e n t3 种计算方式，做如下a g e n t 随机行走实验，证明联合测谎机制性能优于指定测谎a g e n t 方式，能保证系统的求解效率。实验环境同3 2 3 节。设有4 个a g e n t 在方格环境下做随机行走，从不同起点( 随机给出) 出发寻找某个终点，每次只能沿水平或垂直方向前进一步，所有4个a g e n t 均由起点走到终点为一次求解过程。为确定联合测谎算法的适用范嘲，本节设置了2 种环境：8 x 8 方格环境和2 0 x 2 0 方格环境。1 0 08 06 04 02 0of 二= 箝歪a 面丽丽芳交1：i - - * - a g e n t 联合测谎方式| - 无说谎a g e n t 联盟方式圈3 38 8 方格环境算法性能比较本节仍然假设终点也随机给出，且其标志与坐标无关，从而使得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 没有到过的方格。图3 3 和图3 4 所示是分别在8 x 8 方格环境和2 0 2 0 方格环境下独立实验8 次的结果，图中横坐标表示独立求解的次数，纵坐标表示每一次求解过程所有a g e n t 由起点走到终点所需步数之和。圈3 42 0 2 0 方格环境算法性能比较3 4图3 3 表明，在范围较小的计算环境( 8 8 方格环境) 中，整体计算量较小，除某些特殊情况( 第4 、8 次实验) 外，联合测谎算法j 指定a g e n t 测谎方式相比没有明显的优势。结合图3 3 ，从图3 ，4 中的曲线能够看出，在范围比较大的计算环境( 2 0 x 2 0 方格环境) 中，联合测谎算法的求解效率明艟高于指定a g e n t 测谎方式。特别，在周2 的第6 、8 次实验中，联合测谎算法效率逼近联盟中1 i 存在说谎a g e n t 的计算方式，具有非常商的求解速度。可见，与指定测谎a g e n t 计算方式相比，本文提出的联合测谎算法性能更优越，并更适用于大规模的计算环境。3 4 伦理学模型：f i r e 模型的扩展3 4 1 多a g e n t 系统的伦理学模型伦理学是研究道德的科学，信任和名誉是伦理学中的范畴。本节将伦理学引入多a g e n t 系统中，构造出多a g e n t 系统的伦理学模型通过定义3 2 3 4 给出。多a g e n t 系统的伦理学模型可以被看作是f i r e模型的扩展模型。定义3 2 ，个多a g e n t 系统具备如下结构：s y s t e m ：= 其中：a g 。( f n ) 是多a g e n t 系统中各a g e n t ；r e pt a b( r e p u t a t i o nt a b l e ) 是名誉矩阵，它是一个n x n 二维矩阵，用于记录系统中各a g e n t 对其他a g e n t 的道德评价：a g 对其他h j 个a g e n t 的道德评价构成名誉矩阵的第j 行；除4 西之外的n j 个a g e n t 对a g j 的道德评价构成名誉矩阵的第，列。定义3 3 ，系统中单个a g e n t 可以用如下的四元组来描述：a g e n t ：= 其中：m ( m o r a l i t y ) 是指单个a g e n t 的品德模块，是单个a g e n t对自身行为以及自身价值实现情况的一种判断；f ( f a c u l t y ) 是单个a g e n t 的才能，是单个a g e n t 具体实现的功能；n ( n e e d ) 是单个a g e n t自身的需要，如通过自学习达到自身刁一能的完善等；c ( c o n t r i b u t i o n )是贡献模块，用于描述单个a g e n t 参与系统运算的过程中实际贡献的大小。定义3 4 定义3 3 中的的品德模块m 又可以描述成如下二元组的奉节主要内窖发表于2 0 0 4 年t 微电子学与计算机第5 期3 s形式： ，：= 。其i ：c o n s ( c o s c i e n c e ) 足良一t l , 模块，是单个a g e n t 对自己的行为的评价和道德评价；b l e s ( b l e s s e d n e s s ) 是幸福模块，是单个a g e n t在执行任务之后对自身价值实现的评价。3 d 2 模型分析2 4 2 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 ，( j f 一) 觉得与爿岛( 7 h ) 防作时能够有效完成系统的任务，则赋予a g j 正的名誉值，并将此值累加到名誉矩阵的相应位夏r e pt a b 。的数据上，表示给这些参与运算的a g e n t 以荣誉；否则，赋予负的名誉值并进行累加，表示舆论谴责。名誉表示a g e n t 所能达到的道德程度和与其它a g e n t相互协作的能力。( 二)品德品德包括良心和幸福两个组成部分。( 1 ) 良心c o n s c i e n c e良心是a g e n t 自己对 j 己的行为、道德的一种意见和判断，是促进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 ) 幸福b l e s s e d n e s s幸福在伦理学中定义为重大的快乐，。般来说是理想实现的心理体验。a g e n t 除追求良心满足之外。还应追求幸福。幸福的实现比较复杂，有三个正的因素( 才能、贡献和良心) 和一个负的因素( 需要) 。才能越高、贡献越大、良心越好幸福就越容易实现；相反，需要( 欲望) 越大，幸福便越难实现。规定，b l e s = c o n s + f + c j 。( 三) 需要n e e da g e n t 每次参与协作，在完成运算的过程中，还应该积极的提高自身的素质，即在协作中受益，这就是需要。需要直接影响a g e n t 能否获得较夫的幸福值。在这里规定：= 厶f 。( 四) 才一自f a c u l t y才能是a g e n t 的设计者赋fa g e n t 的具体的功能以及a g e n t 在参- j 协作运算时通过自学习对自己的功能的扩充。才能的大小直接决定着a g e n t 能甭有效完成系统交给的任务。为了计算需要，可以为a g e n t的能力进行粗略的定义级别，用整数表示。( 五) 贡献c d 打f r f 6 “f f o 贞献是参与协作运算的a g e n t 奉献的力量。对于贡献的计算可以采用如下的公式：ic = d 。5，：i其中：c ，是爿g ，的贡献值，设g ( 1 ，) 是系统将运算任务分解成。系列的原子任务中由a g ，完成的( 共k 个原子任务) 第，个原子任务，d ，7 是g ，。的难度系数。3 4 2 2a 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 3 ：算法3 3 步骤1 系统得到运算任务：步骤2 系统将运算任务分解成一系列的原子任务；步骤3 系统针对这些原子任务寻找才能最强的a g e n t ( 假设是a g ，) 并将任务交给它；步骤4 a g ，在名誉矩阵第i 行中查找名誉值较高的并j