（计算机软件与理论专业论文）基于多agent的车间生产调度系统的研究.pdf

大连理工大学硕士学位论文 摘要 生产调度系统是企业资源计划( e r p ) 的核心，也是目前其实施的瓶颈。在敏捷化、 全球化的新形势下，生产调度研究面临着许多新问题，迫切需要有新的方法和机制来解 决。课题是实验室与s u n 公司合作研究的基于分布式对象技术的资源管理项目和实验 室原有车间生产管理系统的结合。将多a g e n t 技术运用于车间生产调度领域，期望能够 对生产调度问题的实际解决提供有益的探索。 本文针对目前生产调度问题进行了深入的分析研究，在其基础上，结合生产对象的 实际状况，建立了基于多a g e n t 的车间生产调度系统( m u l t i a g e n ts c h e d u l i n gs y s t e m ， m a s 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 t 生产调度系统进行了实现，在r m i 技术的支 持下，实现了a g e n t 之间的通讯。并针对多品种小批量制造系统进行了仿真实验。实验 结果表明了本文提出的m a s s 模型、体系结构与协商机制的可行性和有效性。该调度系 统能够处理包括突发事件在内的各种生产调度中的实际问题，具有良好的开放性、敏捷 性和对不同制造需求的适应性，同时，具有较好的稳定性和一定的优化性能。 关键词：车间生产调度；多a g e n t 系统；合同网协议；协商 大连理工大学硕士学位论文 t h er e s e a r c ho fj o bs h o ps c h e d u l i n gs y s t e mb a s e do nm u l t i a g e n t a b s t r a c t p r o d u c t i o ns c h e d u l i n gs y s t e mi st h ec o r eo fe n t e r p r i s er e s o u r c ep l a n n i n g ( e r p ) ，a l s o t h eb o t t l e n e c ko f e r p i nt h es i t u a t i o no f a g i l ea n d g l o b a lm a n u f a c t u r i n g ，m a n yn e wp r o b l e m o fp r o d u c t i o ns c h e d u l i n gr e s e a r c hd e v e l o p s t h i sm s e a r e hd i r e c f i o nc o m e sf r o mac o o o c r a t e p r o j e c tn a m e dr e s o u r c em a n a g e m e n ts y s t e mb a s e d 0 1 1d i s t r i b u t e do b j e c tt e c h n o l o g yw i t h s u nc o m p a n y t h ep a p e ri st h ee x t e n d e du s ei nad i s c r a t ep a r tp r o d u c ec o m p a n y a m u l t i a g e n ts c h e d u l i n gs y s t e m ( m a s s ) i sp r e s e n t e di n t h i sp a p e rt os o l v et h ea g i l e s c h e d u l i n gp r o b l e m a f t e rd e e p l yr e s e a r c h i n go f t h ec u r r e n tr e s e a r c ha c h i e v e m e n t , t h i sp a p e rb u i l tm u l t i - a g e n t m o d e lc o n s i s t e do ft m a ，r m h , t aa n dr a ah y b r i dt y p eo fa g e n ti sb u i l tt oi n a k ea g e n t i n d i v i d u a lc a nt h i n ka n da c t i v e t h eh y b r i da r c h i t e c t u r eo fm u l t i a g e n ti n t e g r a t e dt h e h i e r a r c h ya n dt h eh c t e r a r c h yi s a l s op r o p o s e da f t e ra n a l y z i n g t h e ma r eh o r i z o n t a la n d v e r t i c a ln e g o t i a t i o n si n t h ea r c h i t e c t u r eo fm a s si no r d e rt oo v e r c o m ed r a w b a c k so f h i e r a r c h ya n dh e t e r a r c h y ，a n dt oi n a k e t h em a s s a 百l ea n df l e x i b l er e 印o s e sc a p a b i l i t i e sa n d a f e a s i b l e ，m b u s ta n dn ：a ro p t m a i z e ds c h e d u l e r s a tl a s tam u l t i - a g e n ts c h e d u l i n gs y s t e mi sb u i l tu pu s i n gd i s t r i b u t e do b j e c t i nt h es u p p o r t o fr m it e c h n o l o g y ，t h ec o m m u n i c a t i o no fa g e n t si si m p l e m e n t e d w ea l s od i ds o m e e x p e r i m e n t sa b o u ta g i l ep r o d u c t i o ne n v i r o m e n t t h es i m u l a t i o nr e s u l t sh a v es u c c e s s f u l l y s h o w nt h a tt h e a p p r o a c h i s c a p a b l e o f g e n e r a t i n g f e a s i b l es c h e d u l e r si na na g i l e m a n u f a c t u r i n ge n v i r o n m e n t t h ee x p e r i m e n t sh a v ea l s od e m o n s t r a t e dt h a ti th a si n c o r p o m t e d t h ef e a t u r e so fa d a p t i v ea n da g i l i t yt o c h a n g e si np r o d u c t i o nd i v e r s i 哆a n de n v i r o n m e n t c o n f i g u r a t i o n k e yw o r d s ：j o bs h o ps c h e d u l i n g ；m u l t i - a g e n ts y s t e m ；c o n t r a c tn e tp r o t o c o l ；n e g o t i a t i o n i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究y - 作及取缮研究成果。尽我辑知，除了文中转剐加汉标潼和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或孝英镪单位赡学位或证搴瑟使用过鼹麓料。岛我一冠工馋妁露志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 终者签名觯嚣麓：乏型l 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论 文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学 位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采 用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 导师签名： 趁卫d 月塑日 大连理工大学硕士学位论文 1绪论 1 1 课题背景及研究意义 制造业是我国国民经济的支柱产业之一，如今正面临着经济全球化带来的机遇与挑 战。国内外市场已从过去相对稳定的市场变为多变的市场，市场需求的多样性使得以往 单一品种大批量生产转向多品种小批量生产。企业的生产计划与控制成了企业管理的重 要组成部分。在这种形势下，国家提出了以“信息化带动产业化”的发展战略，以企业、 行业信息化促进制造行业提高市场反映速度、增加生产柔性、加强成本控制，使企业从 容应对更加激烈的竞争环境，进而提高企业的竞争力【1 1 。 在敏捷化和全球制造的新形势下，生产调度研究面临着许多新问题，迫切需要有新 的调度方法和调度机制来解决 2 】。敏捷制造( a g i l em a n u f a e t t t r i n g ) 【3 】，准时生产( j u s ti n t i m e ) 、并行工程( c o n c u r r e n te n g i n e e r i n g ) 、精益生产( l e a np r o d u c t i o n ) 等多种先进制造 模式【4 】，是2 1 世纪企业提高生产力、提升核心竞争力的基础。在这些模式下如何进行组 织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行 优化调度都是我们面临的问题。其中车间作业优化调度与控制技术是实现生产高效率、 高柔性和高可靠性的关键，有效实用的调度方法的研究与应用已成为先进制造技术实践 的基础。 本课题来源于本实验室为某零件加工公司设计和开发的基于分布式对象技术的 d i s e r e t ee r p 系统。该公司是一家以生产汽车配件为主的中小型离散制造业企业，其生 产方式是基于订单的生产，订单的规模往往较小，而且品种繁多，因此具有业务多变、 管理灵活等特点。本文将利用多a g e n t j 里论，结合企业车间的生产实际来建立基于多 a g e n t 的车间生产调度系统。该企业具有我国中小型离散企业的普遍特点，因此对该公 司调度系统的研究，具有较强的普遍性和社会意义，也是对我国中小型离散制造业信息 化系统的很有意义的尝试。 1 2 车间生产调度问题描述 车间生产调度问题一般可以描述为：针对某项可以分解的工作，在一定的约束条件 下，如何安排其组成部分( 操作) 所占用的资源、加工时间及先后顺序，以获得产品制造 时间或者成本等性能指标最优。 车间生产调度问题主要集中在车间的计划与调度方面，许多学者作了大量研究，得 出了不少的研究成果。制造系统的车间生产调度是针对一项可分解的工作( 如产品制 造) ，探讨在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过下 基于多a g e n t 的车间生产调度系统的研究 达生产指令，安排其组成部分( 操作) 使用哪些资源、其加工时间及加工的先后顺序，以 获得产品制造时间或成本的最优化。在理论研究中，车间生产调度问题常被称为排序问 题或资源分配问题【”。 现代调度的复杂性，特别是由于现代制造系统的运行环境越来越充满了不确定性， 系统的制造任务经常动态变化，这些不确定性、动态性和复杂性组合在一起，使调度变 得更加困难，为了处理这种不断增长的不确定性和复杂性，调度系统必须具有较强的适 应性、鲁棒性和可伸缩性 6 】。 1 2 1 车间生产调度问题指标 车间生产调度中涉及的资源包括：原料、设备( 加工、存贮、运输) 、人力、资金、 能源等。资源的详细分配受到产品的生产工艺的限制。影响调度问题的因素很多，正常 情况下有：产品的投产期，交货期( 完成期) ，生产能力，加工顺序，加工设备和原料的 可用性，批量大小，加工路径，成本限制等，这些都是所谓的约束条件。有些约束条件 是必须要满足的，如交货期，生产能力等，而有些达到一定的满意度即可，如生产成本 等。这些约束在进行调度时可以作为确定性因素考虑。而对于设备故障，原料供应变化， 生产任务变化等非正常情况，都是事先不能预见的，在进行调度时大都作为不确定性因 素考虑。车间生产调度的性能指标可以是成本最低、库存费用最少( 减少流动资金占用) 、 生产周期最短、生产切换最少、设备利用率最高、三废最少等。实际车间生产调度的性 能指标大致可以归结为三类【5 】： ( 1 ) 最大能力指标：包括最大生产率、最短的生产周期等。它们都可以归结为在固 定或者无限的产品需求下，最大化生产能力以提高经济效益。在假定存在连续固定需求 的前提下，工厂通过库存满足产品的需求，调度问题的主要目标为提高生产设备的利用 率、缩短产品的生产周期，使工厂生产能力最大。因此，这类车间生产调度问题可以称 为最大能力调度问题。 ( 2 ) 成本指标：包括最大利润、最小化运行费用、最小投资、最大收益等。其中收 益指产品销售收入，运行费用包括库存成本，生产成本和缺货损失。 ( 3 ) 客户满意度指标：包括最短的延迟，最小提前或者拖后惩罚等。在传统的调度 中，一般以平均流通时间最小、制造周期最短、满足交货期为调度目标，而在实际生产 中，由于提前完成的产品必须保存到交货期，而拖期产品必须交付违约金，因此，在实 际调度中经常考虑提前或者拖后惩罚。 1 2 2 车间生产调度问题特点 车间生产调度问题有以下特点【7 l ： 大连理工大学硕士学位论文 ( 1 ) 复杂性 车间中工件、机器、缓存和搬运系统之间相互影响、相互作用。每个工件又要考虑 它的加工时间、安装时间和操作顺序等因素，因而相当复杂。调度问题是在等式或不等 式约束下求解指标的优化，在计算量上往往是n p 完全问题，随着问题规模的增大，其 计算量急剧增加，使得一些常规的方法无能为力，对于这一点已经证明【钔。即使对于单 台机床加工问题，如果有n 个工件而每个工件只考虑加工时间以及与操作序列有关的安 装时间，则这个问题就和n 个城市的t s p 问题等价。对于一般加工系统，问题更复杂。 ( 2 ) 随机性 车间生产调度中有很多随机和不确定因素，如工件到达时间的不确定性，实际工件 的加工时间也有一定的随机性。而且系统中常有突发偶然事件，如机器出故障、作业交 货期的改变等。 ( 3 ) 约束性 车间生产调度问题中资源的数量、缓存的容量、工件加工时间以及工件的操作顺序 等都是约束。此外还有一些人为的因素，如要求各机器上的负荷要平衡等。 ( 4 ) 多目标 调度的目标很多，而且这些目标之间往往是有冲突的。调度目标分为三类：基于作 业交货期的目标、基于作业完成时间的目标和基于生产成本的目标。 1 3 车间生产调度问题的研究现状和发展趋势 1 3 1 车间生产调度问题的研究现状 由于调度问题在理论上的复杂性、在制造实践中的重要性以及调度环境本身的动态 性，它引起了人们的广泛重视。我们从文献中可以了解到，人们采取了多种方法，这些 方法主要包括运筹学方法、分枝定界法、启发式方法等传统的优化调度方法和遗传算法、 神经网络、蚁群算法以及多a g e n t 等智能方法，如文献【9 1 4 】。 传统的调度技术和模型无论所使用具体的计算技术是属于数学优化方法的、还是运 筹学的、抑或是人工智能方法，调度的研究工作始终是从应用数学的分析与研究角度展 开的。由于这种调度模型和概念是对实际车间生产调度问题的抽象，它能够产生最优调 度方案，但随着调度规模增大，求解难度急剧增加。而且，在实际制造系统开放的、动 态的环境下，车间生产调度问题呈现极强的动态性，例如机器的损坏、加工计划的改变 以及紧急订单的处理等，这就使得传统的调度技术和模型很难直接运用于解决实际的车 间生产调度问题。 基于多a g e n t 的车间生产调度系统的研究 很多研究表明，寻找最优调度解是非常困难的，最有工程意义的求解算法是在合理、 有限的时间内寻找到一个近似的、有用的解。近年来在这方面己经取得了不少研究成果， 特别是遗传算法、神经网络、蚁群算法和多智能体等智能求解方法，为解决较大规模的 优化问题提供了比较可行的方法。 遗传算法是一种模仿生物群体进化过程的优化算法，具有较好的并行性和鲁棒性， 并且易于与其它算法相结合，在实际应用中取得了较好的效果。其中典型的应用有： l e e ( 1 9 9 7 ) 等用机器学习来产生将工件下发到车间层的知识库，然后用遗传算法在各台 机器上分配工件【1 5 i tj i a n ( 1 9 9 7 ) 等提出一种f m s 的调度和重调度算法【1 6 1 ，用遗传算法 产生一个初始调度，当意外事件发生时，仅重新调度直接受影响的工序；h u a n gm i n ( 2 0 0 3 ) 等提出了基于规则的遗传算法【l ”。遗传算法虽然能够产生较优的解，但是属于集 中式方法。当问题的规模增大时，算法所需时间往往是企业的生产实际是不能接受的。 神经网络在调度中的应用主要有两类：一类方法是将调度问题看成一类组合优化问 题，利用其并行处理能力降低计算的复杂性。f o o 和t a k e f u j i ( 1 9 8 8 ) 最早提出的用 h o p f i e l d 神经网络求解作业车间调度问题( j s p ) ，是一个比较有影响的方法，但不能保 证神经网络稳态输出为可行的调度方案。j o n e s ( 1 9 9 5 ) 等提出一种解决实时排序和调度问 题混合方法的框架，综合运用了神经网络、遗传算法和实时仿真等方法 1 8 , 1 9 1 ，但只提供 了一个框架。l i u ( 1 9 9 6 ) 等提出一种用神经网络选择调度规则的方法【2 0 1 ，但需要大量的 训练样本和很长的训练时间。t o m ( 2 0 0 2 ) 等应用多层的前馈神经网络进行调度，用模拟 退火算法分别训练特定调度条件下的各个神经网络，然后用b p 算法训练全部调度条件 下的最终神经网络口”。神经网络方法需要较长的训练时间和不确定性的结果，所以还一 直处于理论研究阶段。 进入八十年代，基于分布式人工智能的多a g e n t 技术的逐渐兴起，为车间生产调度 的研究与开发创造了一种新思路和新方法。基于多a g e n t 的调度方法既融合了多种现代 的理论和技术成果，如先进制造、分布式人工智能、计算机技术等，又能够适应当前制 造系统对于柔性、敏捷性和重构能力的需要。基于a g e n t 的制造研究吸引了越来越多的 关注。多a g e n t 系统( m u l t i a g e n t s y s t e m ，m a s ) 技术由于系统中a g e n t 具有高度自治性、 智能性、协作性、交互性、适应性等特点，较好满足了敏捷制造环境下车间生产管理的 需要，并且多a g e n t 系统技术能将车间生产调度系统研究从传统的集中式转向分布式， 将复杂的问题分解为多个较小的相关子问题，降低系统的复杂性，越来越被人们青睐。 1 3 2 车间生产调度问题的研究发展趋势 回顾以往的研究历程，我们发现在早期的研究中，车间生产调度往往被抽象描述为 大连理工大学硕士学位论文 一个有性能指标、有约束条件、寻求最优解的数学问题。但由于其实质上是一个n p 难题， 即随着问题规模增大，寻求最优解的计算量呈指数增长，使得一些常规的优化方法难以 奏效。因此，激发了很多研究者致力于“优化调度”的研究，试图解决调度算法的求解 速度和求解质量等问题。 随着研究的深入和制造系统的发展，特别是柔性制造系统、计算机集成制造系统的 应用，实际生产系统的复杂性和动态性增加，促使人们进一步研究能够处理生产环境的 不确定性和意外事件的车间生产调度技术，使得调度目标变成“敏捷调度”。 正如本文在前面所分析的，要解决敏捷调度问题，如果依然遵循经典的调度研究的 方法和思路，单纯通过研究某些算法的改进和扩展等努力来解决，是达不到预期的效果 的。面对敏捷化制造的复杂要求，不仅需要研究新的、更实用的调度算法，还需要从系 统的角度出发，研究理想的调度系统模型、合理的调度系统结构、以及能够集成多种优 良的调度方法和技术的调度策略和方法。这是车间生产调度系统适应未来制造需要的必 然发展趋势。也是制造控制理论和技术发展的必然趋势。 1 4 本文的主要研究内容和组织结构 1 4 1 主要研究内容， 车间生产调度是实施e r p 的关键环节之一，因此车间生产调度问题( 包括理论的研 究和应用系统的开发) 一直都受到学术界和企业界的关注。早期的研究主要着眼于优化 调度，后来逐步转向柔性调度，随着科技的发展和社会需求的变化，目前更倾向于敏捷 调度。敏捷调度面向以多品种、小批量、客户化产品为主的敏捷制造，要求在产品开发 和制造周期内，具有较高的适应性和效率响应客户的需求。 车间生产调度问题通常是多约束、多目标、随机不确定优化问题，已被证明是n p 难题。过去的智能求解方法也表明，寻找调度问题的最优解是非常困难的。随着现代科 技的快速发展，采用新的计算机技术、人工智能技术进行车间生产调度，已成为必然的 要求。多a g e n t 技术是计算机和分布式人工智能领域的最新研究成果，是面向对象技术 的新发展，为解决车间生产调度问题提供了新的思路。这也是本论文深入研究的问题。 本文针对车间生产调度的现状，运用计算机与人工智能领域的最新理论成果多 a g e n t ： 支术，进行基于多a g e n t 技术的车间生产调度问题的探讨与研究，以期对车间生产 调度问题的实际解决提供有价值的参考。 基于多a g e n t 的车间生产调度系统的研究 1 4 2 本文组织结构 第1 章绪论：讨论了课题的研究背景、来源以及研究意义；对现有的生产调度研 究的理论与应用成果进行研究，结合敏捷化制造实际的需要，分析了传统生产调度研究 存在的问题、现有成果和发展趋势，引入了多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 系统在调度领域的应用现状进行了详细的介绍。 第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 体系结构；设计了改进合同网的协商机制。 第4 章基于多a g e n t 车间生产调度仿真系统的实现：应用分布式对象技术实现了 基于多a g e n t 的车间生产调度仿真系统。该系统的实现是在j a v a 语言的面向对象机制和 分布式r m i 技术的支持下实现的。在协商过程中根据对象的实际生产要求建立了一些 决策函数和算法使a g e n t 能够自主决策，并且大大减少协商次数。 第5 章实验及结果分析：针对多品种小批量零件车间加工系统的生产调度问题， 在所开发的仿真原型系统上进行一系列仿真实验，并对实验结果进行分析，验证所提出 的m a s 模型、结构、机制、调度策略的可行性和有效性，检验其敏捷性和优化性能。 大连理工大学硕士学位论文 2 a g e n t 与多a g e n t 系统 多a g e n t 系统( m u l t i a g e n ts y s t e m ，m a s ) 自2 0 世纪8 0 年代被引入生产调度领域 以来，就一直受到研究人员的关注和青睐，成为设计和实施分布式敏捷调度系统的可行 性技术。专家们预测多a g e n t 系统应用于制造业的研究，将给制造业带来巨大的效益。 本章探讨了m a s 的起源，深入分析、研究了多a g e n t 的概念、体系结构和通信交互协 议，以及多a g e n t 技术的应用前景，特别是在敏捷制造系统的重构和生产控制与调度领 域的应用。这些分析和研究是本文后几章的理论基础。 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 m 中来，但是a g e n t 并不等 同于专家系统和大多数以知识为基础的应用系统。由于a g e n t 的研究还没有完全成熟， 因此学术界并没有统一的定义。 2 1 1 a g e n t 的定义 在a g e n t 的众多定义中，比较通用的是w o o l d r i a g e 和j e n n i n g s 在1 9 9 5 年提出的定义 2 2 1 ：a g e n t 是处在某种环境中的计算机系统，该系统有能力在这个环境中自主行动以实 现其设计目标。这个定义强调的是a g e n t 的自主性。 a g e n t 所有可能具有的特点如下： ( 1 ) 自治性( a u t o n o m y ) ：a g e n t 不直接由人或其它东西控制，它对自己的行为和内 部状态有一定的控制权。 ( 2 ) 社会能力( s o c i a la b m t y ) 可通信性( c o m m u n i c a b i l i t y ) 交互性( i n t e r a c t i o n ) ：a g e n t 能够通过某种主体通信语言( a g e n tc o m m u n i c a t i o nl a n g u a g e ，a c l ) 与其它a g e n t 交换信 息，并协同工作。 ( 3 ) 反应性( r e a c t i v i t y ) ：即对周围环境的感知和影响。a g e n t 能感知周围环境并对其 间的变化产生实时响应，这些动作的执行基于知识库的规则或预定的执行计划；a g e n t 也能够主动地进行基于自身目标和信念的活动，以改变周围环境。 “) 推理性( r e a s o n i n g ) ：软件a g e n t 可根据已有的知识和经验，以理性、可再生的 方式进行推理。软件a g e n t 的智能由三个主要部件来完成，即内部知识库、自适应能力 以及基于知识库的推理能力。 基于多a g e n t 的车间生产调度系统的研究 ( 5 ) 学习和适应能力( 1 e a r n i n ga n da d a p t a b i l i t y ) ：主体可以根据过去的经验积累知 识，也可以修改其行为以适应新的环境。 ( 6 ) 规划能力( p l a n n i n g ) ：根据日标、环境等的要求，a g e n t 应该至少对自己的短期 行为做出规划。虽然程序设计人员可以提供一些常见情况的处理策略，但这些策略不可 能覆盖a g e n t 将遇到的所有情况。所以，a g e n t 需要具有生成规划的能力。 ( 7 ) 时间连续性( 1 0 n g e v i t y ) ：传统程序在用户需要时激活，不需要时或者运算结束 后停止，a g e n t 与之不同，它应该至少在“相当长”的时间内连续运行。 ( 8 ) 可移动性( m o b i l i t y ) ：移动a g e n t p f f 】_ 携带数据、指令和状态移动到其它环境中并 在那里执行智能指令。 2 1 2a g e n t 的结构模型 x v a g e m 结构模型的研究主要是从逻辑、行为、心理、社会等角度出发，对a g e n t 的 本质进行描述，为m a s 的创建奠定基础。现在对a g e m 模型的研究可以划分为三种类型： 慎思型a g e n t ( d e l i b e r 砒i v ea g e n t ) 、反应型a g e m ( r e a c t i v ea g e n t ) 和混合型a g e n t ( h 蛳d a g e n t ) 。 哥信息处理模块l 【 牵申 通 讯 4 - 模 执 块 行 模 _ + | 决策与职能控制模块 块 图2 1 一种混合式a g e n t 结构模型 f i g 2 1h y b r i da r c h i t e c t u r em o d e lo f a g e n t 慎思a g e n t 是具有内部状态的主动软件，它与具体的领域知识不同，具有知识表示、 问题求解表示、环境表示、具体通讯协议等。 反应式a g e n t 能对外部刺激迅速产生反应，几乎没有内部状态，基本不做推理，类 似于客户服务器结构。 大连理工大学硕士学位论文 其中混合模型，同时具有慎思型a g e n t 和反应性的特点，是一种经常采用的结构模 型，其基本结构如图2 1 所示。该结构由环境感知模块、执行模块、通讯模块、信息处理 模块、决策与智能控制模块以及知识库和任务表组成。 2 2 多a g e n t 系统 2 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 e n t 成员的限制，它通过竞争或磋商等手段协调和解决 各成员a g e n t 的目标和行为之间的矛盾和冲突。 多a g e m 系统可以将耦合度较深的问题解耦成简单的任务，使系统便于升级和控制； 可以接受动态和不确定的知识，具有一定的智能性、适应性和鲁棒性；十分适合分布式 架构。采用多个a g e n t 进行协作，可以通过任务分解和任务协调来提高整个系统的性能， 也可以克服单个a g e n t 知识不完全、处理的信息不确定等缺点。 目前b i a s 技术已经在广泛的领域内得到了应用，特别是开放系统和复杂系统，以 解决一些其它技术不能解决或不容易解决的问题。 2 2 2 多a g e n t 系统的体系结构 系统中的a g e n t 需要按照一定的结构组织起来，以相互通信和协作，这就需要为 m a s 选择合适的体系结构。体系结构是任何控制系统的骨架，通过对现有文献的分析 可以得出，m a s 的体系结构主要分为以下几种类型：层次型( h i e r a r c h i c a l ) ，异构型 ( h e t e r a r c h i e a l ) 和混合型( h y b r i d ) 。此外还可能包括基于域的层次结构( d o m a i n - b a s e d h i e r a r c h i c a ls t r u c t u r e ) 、级联a g e n t 结构( c a s c a d i n ga g e n ts t r u c t u r e ) 、相邻关系结构 ( p r o x i m i t yr e l a t i o ns t r u c t u r e ) 和基于总线网的结构( b u s b a s e dn e t w o r ks t r u c t u r e ) 【2 5 j 。 ( 1 ) 层次体系结构( h i e r a r c h i c a la r c h i t e c t a z r e ) 层次型认为在高级和低级控制层次间存在等级和主仆关系。高层控制器根据低层状 态的简单模型进行调度和决策。如果执行时没有干扰，这种体系结构可以提供一个在全 局上优化或近似优化的决策集合，因为高层控制者有全局观念。但是有些超出系统直接 控制范围的因素，如客户的快速变化的请求，订单修改等外部干扰，以及一些可以被控 制的内部生产干扰，如资源故障、工具缺少和送货迟到等，会在操作级上破坏全局计划 和调度。在层次性组织结构中，a g e n t 之间的协作更加容易，对协商过程中的通讯要求 比较低，但是运行时传递的消息比较多。文献 2 6 】中使用的就是这种方法。 ( 2 ) 异构体系结构( h e t e r a r c h i c a la r c h i t e c t u r e ) 为了提高系统的健壮性，异构型框架被提了出来。在这种体系结构中，a g e m 之间 是平等的，它们通过相互协作做出自己的决策。由于a g e n t 之间的协商是在同一层次进 行的，因此问题的解决更加简单。这种体系结构具有更好的分布性、可维护性、健壮性、 容错性，并且使系统更加模块化，从而易于重构。这种方法适用于对自治性要求较高的 环境。 异构体系结构的优点是：提高了a g e m 的自治性，降低了系统的复杂性，增强了系 统的容错能力，但这种结构缺少全局观，优化性能差，缺乏预见性，稳定性，使协商变 得更加困难。 ( 3 ) 混合体系结构( h v b 删a r c h i t e c t u r e ) 人们意识到层次结构和分布式结构各自存在的弱点，试图通过控制结构上的改变和 改进来克服这些弱点。一种研究思路是将m a s 构造成层次结构，但是允许各个a g e n t 之间超越“父子”之间的层次关系进行协商。p a r u n a k 最早提出了这样一种准层次结构 的多a g e m 系统，该系统采用一种静态的层次结构，由全局调度单元、工作站和生产单 元组成。工作站是最基本的生产单位，而生产单元是一些工作站或其它生产单元的集合。 当全局调度单元从整个工厂的角度做出一个初步的、时间较为宽松的调度计划后，层次 结构中各个控制层通过实时协商获得较详细的调度计划。与传统的层次结构不同的是， 虽然系统模型中使用了层次结构，但是允许a g e n t 在其父结点和子结点之间协商的同时， 也允许与其同一层的其它结点( 兄弟结点) 进行协商。 另一种思路是在异构系统结构中允许局部的层次结构的存在，实现局部的任务优化 与控制。这种层次结构可能是物理上的，也可能是逻辑上的；可能是静态的也可能是动 态的。例如c h o i 等提出基于多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 相互通信协商， 整个系统具有异构性。混合结构集成了递阶结构和分布式结构的优点，成为m a s 的发 展趋势。 2 2 3 多a g e n t 间的交互与合作 在m a s 中，多个a g e n t 需要相互合作，共同完成任务。“合作”一词在m a s 中具 有如下意义： ( 1 ) 由于系统中的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 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 之间还是可以像人类社会一样为了实现 各自的目标相互合作。 ( 1 ) a g e n t 间的通信方式 m a s 中的a g e n t 需要通过相互通信来进行合作。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 的数目很多时，黑板中的数据量会呈指数 增长，导致系统的效率降低【3 0 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 必须知道 通信语言的语义。消息的语义内容知识是分布式问题求解的核心部分。消息报告机制适 用于资源数量庞大、动态变化环境下的车间生产调度系统，具有良好的开放性和动态可 重组性【3 ”。 主体通信语言( a g e n tc o m m u m e a ：t el a n g u a g e ，a c l ) 的理论基础是基于言语行为 ( s p e e c ha c t ) 的理论。国际上最著名的a c l 是美国a r p a 的知识共享计划( k n o w l e d g e s h a r i n ge f f o r t ) 中提出的两个相关的语言：一个是k q m l ( k n o w l e d g eq u e r ya n d m m f i p d a f i o nl a n g u a g e ) ，另一个是知识交换格式k i f ( k n o w l e d g eh t e r c h a n g ef o r m a t ) 。 k q m l 定义了一种a g e n t 之间传递信息的标准语法以及一些术语( p e r f o r m a t i v e ) 。这些 述语主要从言语行为理论中演化而来，例如t e l l 、p e r f o r m 、r e p l y 等等。k i f 则给信息 的内容提供一种语法，类似于l i s p 的语法书写的一节谓词演算。 ( 2 ) a g e n t 之间的协商机制 在m a s 中，协商的含意有多种理解。所有协商活动的目的是在一组独立工作的 a g e n t 间构建协作。 协商受特定的协议或机制的支配。协商协议提供可能的协商形式的基本规则、协商 过程和通信基础。可以对协议进行设计使得任何特定的协商过程都具有特定的所希望的 特性这就是机制设计。机制设计关心的问题包括： 保证成功：如果最终能确保达成一致，则协议是保证成功的。 最大的社会利益：直观地说，如果保证任何输出都能是参加协商的各方效用的 综合最大，则社会利益最大。 p a r e t o 效率：如果不存在其它的协商结局使至少一个a g e n t 更好而没有使其它 a g e n t 更差，则称这个协商结局具有p a r e t o 效率。 个体理性：如果遵守一个协议能保证协商参加者的最大利益，则称这个协议是 具有个体理性的。具有个体理性的协议是重要的，因为没有个体理性，a g e n t 就没有参 加协商的动机。 稳定性：如果一个协议使所有的a g e n t 都有按照特定方针行动的动机，则这个 协议是稳定的。稳定性的最著名形式是n a s h 平衡。 简洁性：一个简洁的协议是这样的协议，它做出的合适的策略对于协商的参加 者来说是显而易见的。也就是说，如果使用一个协议，参加者可以容易地决定最佳策略， 则这个协议是简洁的。 分布性：一个理想的协议应该设计成保证尽量没有缺陷，并且理想情况下使 a g e n t 之间的通信最少。 协商策略取决于具体的a g e n t 。尽管开发者可以提供不同程度的协商能力，但是一 定要保证协议和策略相匹配，即选择的策略要在可用的协议中能执行。 一般来说，任何一个协商框架都有四个组成部分： 一个协商集合，表示a g e n t 可能提出建议的空间； 一个协议，定义a g e n t 提出的合法的建议，它是先验的协商历史的函数；