（计算机应用技术专业论文）车间控制智能贴片通讯平台中多智能体协作的研究和实现.pdf

午问控制杆能贴片通i n 、r f 、 ，彰钾能体协”：的研究手f i 实现 摘要 协作可以定义为若干个任务在一些机器上进行加工”如何按时i 日j 或成本对机器和物 力等资源进行安排”使某些目标函数达到最优。在车间控制智能应用领域，由于现代调 度的复杂性，而且在运行环境上越来越充满了不确定性，系统的制造任务经常动态变化， 这些不确定性、动态性和复杂性组合在一起，使调度变得更加困难，为了处理这种不断增 长的不确定性和复杂性，调度系统必须具有较强的适应性、鲁棒性和可伸缩性。本文采用 了多智能体协作方法，设计了一种新的基于车间控制智能贴片中多智能体协作的调度系 统。 本文首先阐述了智能贴片系统结构以及协议，基于当前现状，深入进行了多智能体 系统协作行为的研究。 基于车间控制的基本问题，本文采用多智能体协调方法设计了一种新车间控制智能 调度系统。首先分析了多智能体车间调度系统基本框架主要包括工件智能体，车间任务 智能体，设备智能体以及管理和监控智能体，详要介绍了多智能体协调系统的运行，以 及他们的操作规则。在基于多智能体的生产调度系统中，资源分配、调度策略和系统目标 都要通过智能体之间的协调才能实现。接着分析了比传统的调度系统相比分布式控制结 构实现、任务和个性化需求的简易实现、采用了改进了模拟退火动态调度遗传算法提高 效率等优点。 针对多智能协调需求，本文重点进行协调策略建模，详细分析了多智能体的核心问 题多智能体协作算法、以及改进的多智能体协作算法的实现。 最后，通过多智能体系统例子说明了本论文所设计的改进的多智能体协作算法拥有 较小的平均产品延迟率，并且可用于解决考虑加工时间和加工成本的情况，比一般的调度 系统更能实现效率。 关键词：多a g e n t ，协作；改进的多智能体协作算法；车间调度 人迮交通人学i i 中形! 1 ，7 f _ 沦之 a b s t r a c t c o l l a b o r a t i o nc a nb ed e f i n e d 嬲an u m b e ro ft a s k si nan u m b e ro fm a c h i n e sf o r p r o c e s s i n g ”h o wt o t i m eo rc o s to ft h em a c h i n e r ya n dm a t e r i a ir e s o u r c e ss u c h a s a r r a n g e m e n t s ”t oe n a b l ec e r t a i no b j e c t i v ef u n c t i o no p t i m a l i nt h ef i e l do fi n t e l l i g e n tc o n t r o l a p p l i c a t i o n so fw o r k s h o p ，d u et ot h ec o m p l e x i t yo fm o d e ms c h e d u l i n g ，c a u s et h eo p e r a t i n g e n v i r o n m e n tt ob e c o m ei n c r e a s i n g l yf u l lo fu n c e r t a i n t y ，t h es y s t e md y n a m i cm a n u f a c t u r i n g t a s k so f t e nc h a n g e ，t h e s eu n c e r t a i n t i e s ，d y n a m i ca n dc o m p l e xn a t u r et o g e t h e r , c o u r s et h e s c h e d u l i n gb e c o m e sm o r ed i f f i c u l t ，i no r d e rt o d e a lw i t ht h i s g r o w i n gu n c e r t a i n t ya n d c o m p l e x i t yo ft h es c h e d u l i n g ，t h es y s t e mm u s th a v eas t r o n ga d a p t a b i l i t y ，r o b u s t n e s sa n d s c a l a b i l i t y i nt h i sp a p e r ，am u l t i - a g e n tc o l l a b o r a t i v ea p p r o a c ht od e s i g nan e wc h i p b a s e d i n t e l l i g e n ts h o pf l o o rc o n t r o li nc o l l a b o r a t i v em u l t i a g e n ts c h e d u l i n gs y s t e m f i r s t ，t h i sp a p e rd e s c r i b e st h ei n t e l l i g e n tp l a c e m e n ts y s t e ms t r u c t u r ea n da g r e e m e n t ， b a s e do nt h ec u r r e n ts t a t u sq u o ，i n - d e p t hc o l l a b o r a t i v em u l t i a g e n ts y s t e mb e h a v i o rr e s e a r c h b a s e do nt h eb a s i cp l a n tc o n t r o lp r o b l e m ，t h i sp a p e ra d o p t sm u l t i a g e n tc o o r d i n a t e d a p p r o a c ht o t h ed e s i g no faf l e ws h o pf l o o rc o n t r o li n t e l l i g e n ts c h e d u l i n gs y s t e m f i r s t ， a n a l y s i so fm u l t i a g e n ts h o pf l o o rs c h e d u l i n gs y s t e mm a i n l yi n c l u d e st h eb a s i cf r a m e w o r ko f t h ew o r kp i e c ea g e n t ，t a s ka g e n tw o r k s h o p s ，e q u i p m e n t ，m a n a g e m e n ta n dm o n i t o r i n ga g e n t a n dt h ea g e n ta r es e tt oi n t r o d u c ea m u l t i a g e n tc o o r d i n a t i o ns y s t e mo p e r a t i o n ，a n dt h e i rr o l e s o fo p e r a t i o n m u l t i a g e n t - b a s e d p r o d u c t i o n s c h e d u l i n gs y s t e m s ，r e s o u r c ea l l o c a t i o n ， s c h e d u l i n gp o l i c ya n ds y s t e mo b j e c t i v e si st h r o u g ht h ec o o r d i n a t i o nb e t w e e nt h ea g e n tc a nb e a c h i e v e d a n dt h e na n a l y z e di nc o m p a r i s o nt h a nt h et r a d i t i o n a ls c h e d u l i n gs y s t e mt oa c h i e v e ad i s t r i b u t e dc o n t r o ls t r u c t u r e ，t a s k s ，a n dt h es i m p l er e a l i z a t i o no fi n d i v i d u a ln e e d s ，u s i n ga i m p r o v e dg e n e t i ca l g o r i t h mf o rd y n a m i cs c h e d u l i n g s i m u l a t e d a n n e a l i n gt oi m p r o v e e f f i c i e n c ya n ds oo n i nv i e wo ft h e m u l t i i n t e l l i g e n t c o o r d i n a t e dd e m a n d ，t h i sa r t i c l ec a r r i e so nt h e c o o r d i n a t e ds t r a t e g ym o d e l i n gw i t he m p h a s i s ，m u l t ia n a l y s i sm u l t i a g e n t sc o r eq u e s t i o nm u l t i a g e n tc o o p e r a t i o na l g o r i t h m ，嬲w e l la si m p r o v e m e n tm u l t i - a g e n tc o o p e r a t i o na l g o r i t h m r e a l i z a t i o n f i n a l l y ，f r o mt h em u l t i - a g e n ts y s t e me x a m p l et h ep r e s e n tp a p e rd e s i g n st h ei m p r o v e m e n t m u l t i 。a g e n tc o o p e r a t i o na l g o r i t h mt h a th a st h es m a l la v e r a g ep r o d u c td e t e n t i o nr a t e ，a n dm a y u s ei ns o l v i n gt h ec o n s i d e r a t i o np r o c e s sp e r i o da n dt h ep r o c e s s i n gc o s ts i t u a t i o n ，c a nr e a l i z e t h ee f f i c i e n c yc o m p a r e dt ot h eg e n e r a ld i s p a t c h i n gs y s t e m k e yw o r d s ：m u l t i - a g e n tc o l l a b o r a t i o n ：i g d s a ；s h o ps c h e d u l i n g 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太整塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名： 搴、呼彳气 日期：加罩 年1 2 - 月f 弓日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太董塞通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太整塞通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为大连交通大堂口学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太鎏交通态堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 僦黼始舅、晰锄签名剽 日期：撕了年f 月f 厂日日期：伽7 年棚，f 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱： 电话： 邮编： 绍沦 绪论 随着现代制造业的发展，小批量，多类型，有不同完工时间和产品要求的产品需求 逐步取代大批量单类型的产品制造计划。在这种情况下，提高生产调度水平和产品竞争 力，要求调度控制系统能够实时动态响应生产任务的不确定变化，同时反映车问的生产 情况和设备使用情况，及时调整生产计划和资源分配。这样以来如何利用车间的现有资 源包括实时的加工能，满足被加工任务所需的各种约束如加工次序，所需机器，按时完 成所有的任务包括性能指标最小，同时得到企业最优的综合利益，就成为一个十分现实 和迫切的问题。综合利益最优通常有以下几类准则：1 ) 最大效率准则。在市场规模无 限的条件下，以最快的生产速度生产制品、满足市场，以此获得更大的利润。其中包括 作业交货期、工件平均流通时间、作业完成时问、设备利用率及生产率等。2 ) 最小费 q 用准则。在产量一定并且产出时间不影响经营成果的条件下，以成本最低为原则组织生 产，以实现利润最大化的目的。其中包括生产成本、拖期生产的惩罚费用及提前完工的 库存费用等。3 ) 最大利润率准则。在其它条件一定的情况下，以投资收益比最大为目标 组织生产。在综合考虑利益时，主要是采用权重系数法给单个目标值赋予随机数权重， 然后线性相加转化为单目标优化问题，但往往具有不平衡性，通常无法给出一个合理的 一 权重系数。为了使上次准则尽量的得到满足，本论文采用了多智能体协作系统去解决车 间调度问题，采用改进的算法提高了效率。 人造交通人学i ：学硕卜f ? ，论艾 第一章多智能协作系统研究 1 1 研究背景和主要研究内容 1 1 1 研究背景 现代制造系统的复杂性、动态性以及市场、技术、经营环境的迅速变化，要求制造 控制结构具有可靠性、容错性、可修改性等特点。随着现代制造业的发展，小批量、多 类型的，有不同完工时间和产品要求的产品需求逐步取代大批量单类型的产品制造计 划。为适应这样的新形势并得益于计算机和通信技术的发展，车问制造控制结构经历了 集中式控制到分布式控制等几种形式，其发展趋势是越来越强调控制职责的分布、自治 和协调。在分布式控制带来系统自适应性、容错性和快速实时响应能力的同时，必须要 解决分布所带来的协调问题、实体间频繁的通信以及局部目标与全局目标间的冲突等问 题。在这种情况下，如何利用车间的现有资源包括实时的加工能力，满足被加工任务所 需的各种约束包括加工次序、所需机器等，使所有的任务能尽量按时完成( 性能指标最 小) ，同时得到企业利益的最大化，实现企业的在线实时调度，就成为一个十分现实和 迫切的问题。 1 1 2 研究主要内容 本文的研究内容是，在总结国内外多智能体系统体系结构与协作机制各种主要流 派研究现状的基础上，提出基于车间控制智能贴片的多智能体系统体系结构和协作机 制，对多智能体协作中的一系列问题，进行理论及实验上的深入研究。 首先，本文建立了基于车间控制智能贴片中多智能体协调系统的逻辑框架，在此框 架上，我们分析了多智能体系统协作的各个组成部分及功能，并将此系统的运行完整的 用数据流表示出来，在此框架上，我们定义了系统的操作规则，更能完整用数学符号进 行编码运算，然后分析此框架上运行的优点。 其次，针对多智能体协作模型，“基于多智能体协商策略提出”【1 1 ，我们采用了基 于动态平衡的多智能体协商策略，突出了车间调度效率，接着我们从模式分析角度建立 了协作算法的数学模型，并且分析了基于协作机制的多智能体协作方法模型及系统：然后 从“多智能体系统的体系结构 【2 】，角度出发，建立了完整和明确的基于协作机制的多 智能体系统运行环境，在所建立的基本框架基础上，将进化规则策略系统与协作机制相 结合，研究了基于进化规则策略系统的多智能体协作行为协作问题；提出了基于协作机制 下多智能体系统完整运行概念，并构建了协作系统的基础类库。 2 第一审多钾能体协f 1 。系统州究 具体内容如f ： 1 ) 多智能体系统的协作模型建模方法研究：首先介绍了协作计算的主要思想作算法 的流程，给出了协作算法的形式化描述，指出协作模型的核心问题是体适应度评价方法， 而随机选取法和最优选取法这两种代表个体的选择方法正是决定个体适应度评价的关 键。然后，从模式分析角度建立了基于模式复制方程的多群体协作算法的数学模型，对 随机选取法和最优选取法进行了理论分析、比较，提出了一种能够结合两种代表个体选 取方法优点的新的个体适应度评价方法，并通过仿真实验验证了新方法的效率。然后， 基于w o o l d r i d g e 建立的多智能体系统符号模型，结合智能体之间协作的协作机制，重新 定义了协作智能体的符号化演绎理论模型，包括协作智能体的信念、动作、通信等自身 系统的各个方面，尤其是对于协作智能体的外部动作定义部动作规则库的维护以及基于 协作机制的决策器模型，都结合协作机制给出了合理描述，从而在理论上形成了一个比 较完整的体系。 2 ) 基于协作的多智能体系统体系结构及协作机制研究：这一部分首先“考察了- 些典 型的智能体体系结构及p t s 领域的智能体体系结构”i ”l 等单个智能体体系结构的主要 思想。在此基础上，给出了基于协作机制的多智能体系统的定义，通过对其构成、各个 构成部分的作用以及相互之间的内部信息协调机制、协作智能体体系结构的分层设计方 法、智能体与世界的交互过程、“m a s b c e 中的分级循环过程、m a s b c e 中的周期步 进机制”【6 1 等进行分析，明确了基于协作的多智能体系统体系结构及协作机制。 3 ) 多智能体协作行为的协作方法研究：对于多智能体协作行为的研究是以s b c e 模 型中的重要组成部分。这部分从行为工程的角度出发，首先考察了多智能体协作行为的 主要研究方法，然后介绍了进化规则策略系统s a m u e l 的基本情况，分析了基于进化 规则策略系统的学习智能体的规则学习过程，然后将协作机制与进化规则策略系统结合 起来，构建了基于进化规则策略系统的多智能体系统协作模型，并按照协作机制中的个 体适应度评价方法，对多智能体协作中行为策略的评估过程进行了深入分析。 4 1 基于协作的多智能体系统仿真框架和实验研究：根据基于协作方法的多 智能体体系结构和协作机制的基本思想，我们建立了基于协作方法的多智能体协作系统 仿真框架，对仿真框架进行了面向对象的设计，并构建了多智能体仿真系统的基础类库， 建立了一个基于协作机制的多智能体协作系统的开放式仿真实验环境。最后，以典型的 多智能体协作行为研究平台进行了实验研究，并得出结论：将协作机制与知识规则系统相 结合，可以为智能体的行为提供有益的决策支持，智能体之间可以通过协作的方式提高 和增进彼此的协作行为。 3 人造交通人。；ti 中顾f j 学何论文 1 1 3 文章主要结构 本文一共分为5 章，第一章主要介绍了论文的研究的背景和主要研究内容以及论文 的内容和结构。 第二章介绍了车间控制多智能体系统。包括搭建智能贴片多智能体系统框架主要包 括工件智能体，车间任务智能体，设备智能体以及管理和监控智能体，详要介绍了多智 能体协调系统的运行，以及他们的操作规则。在基于多智能体的生产调度系统中，资源分 配、调度策略和系统目标都要通过智能体之间的协调、实现。此章是本论文研究的重点。 第三章进行多智能体调度协作系统的建模，是本论文的主要研究重点，主要研究了 多智能体的协商策略，以及传统调度算法与改进的协作调度算法的深入研究，包括对编 码、解码，适应度函数、交叉变异、算法其他的相关参数上进行详要的研究、验证，最 后得出改进的协作算法性能更佳。 第四章是多智能体系统的设计和实现，这章阐述了系统开发需求、概要设计包括建 模方法、系统功能模块组成、模块说明、数据库设计，用设计的系统和具体的数据来验 证该改进协作算法对车间控制智能贴片系统确实能更快、更好得到最优解。 1 2 智能贴片系统 1 2 1 智能贴片结构 本文提出的这种车间控制智能贴片的核心部分是蓝牙芯片。此次应用中，我们采用 了英国c s r ( c 二b r i d g e s i l i e o nr a d i o ) 公司出品的b l u e c o r e 2 系列芯片。下面简要介绍该 芯片的结构。由于车间控制智能贴片主要进行是数据传输，所以采用b h i e c o r e z - e x t e m a l 类型。其“b h i e c o r e z e x t e m a l 类型功能框图 1 7 】如图1 1 所示。 r a m 2 。4 g h z 的 d s pi o a u d i o m c u 图1 1b h i e c o r e z - e x t e m a l 结构图 f i g 1 1e x a m p l eo fh e a d e r ss e r i a ln u m b e r 4 第一章多钾能体协仵系缗 j j 究 可以看出，b l u e c o r e z e x t e r n a l 主要由2 4 g h z 的无线收发单元、3 2 k b y t e 的r a m 、 数字信号处理器d s p 、微控制单元m c u 和f o 接口单元组成。该芯片外部引脚采用 v f b g a 封装，分为射频控制、外部存储器控制、电源接地等几大类，其中包括了1 6 位 数据线、1 9 位地址线，用于扩展外部存储器。1 9 位的地址线和1 6 位的数据线决定了 b l u e c o r e z e x t e r n a l 外部可扩展s mb i t 的r o m ，同时它还具有p c m 、s p i 、u a r t 、u s b 、 p i o 几种i 0 接口。此次设计主要用到了u a r t 和p l o 两种接口。主要技术参数：1 s v 工作电压：采用0 1 8 c m o s 技术，将更多的功能模块集中于蓝牙芯片中，减少外部元件 的数量，既增加了系统的可靠性，又简化了外部电路的设计。可进行数据和语音通信， 本文提出的智能贴片仅用到了数据通信功能。 智能贴片具体的逻辑映射框架如图1 2 所示，这一工作在工件完成其工艺编制后进 行。具体可由一台连有蓝牙贴片的p c 机充当录入主机，在蓝牙通信模式中称这样的p c 机为蓝牙主机。在研究的控制模式中他负责完成各车间资源信息代码转换编制。这一过 程借助相应软件实现，之后利用贴片的无线通信功能建立蓝牙链路将反映各车间资源特 性的编码信息从蓝牙主机录入将进入生产现场的贴片中。这样的过程将车间资源分别映 射为各类型代理。 (，l ：烯) y 接蒯嚣i f 羹务 l ”l ：件( j 他资源) f o 息i f , j a r z , 对寐入f 占息进行编印5 0 篮牙连l 羹f t , j 建瓷 编码f ? i 息的传输 图1 2 智能贴片映射图 f i g 1 2am a p p i n go fa g e n tc h i p 5 皇 ，、近交j 哑人r 7 研! t j f 寺沦文 框架中映射结束的最后“断丌蓝牙连接”是闪为控制模式采用蓝牙作为控制信息传 输的手段，而蓝牙协议中规定一个蓝身：主设备只能同时和7 个从设备处于活动连接状念， 该状态f 才可进行数据收发。因此映射完成后贴片需释放链路，为其他资源的映射做准 备，其他各子框架中也有类似情况。 1 2 2 智能贴片协议 所谓协议，简单地说就是一组内容和顺序定义的消息。蓝牙分为蓝牙专有协议与通 用协议。其中蓝牙专有协议包括：蓝牙核心协议1 8 k 链路管理协议l m p 、逻辑链路控制和 适应协议l 2 c a p 、服务发现协议s d p ) 以及电缆替代协议( r f c o m m ) 、电话控制协议 t c s b i n ( 是l t ut q 9 3 1 建议的一个子集) ；通用协议包括a t 命令集以及大量的可选外围 协议( p p p ，t c p i p ，o x b e x 等) 。除了上述协议外，蓝牙协议还规定了主机控制接h ( h c i ) ， 用于在蓝牙设备的主机和基带模块之间提供一个通用接口。绝大部分蓝牙设备需要核心 协议( 加上基带与射频部分) ，而其他协议根据应用的需要而定。电缆替代协议、电话传送 控制协议和被采用的可选协议在核心协议的基础上构成了面向应用的协议。 在此文研究中，蓝牙芯片中包含了3 层意思：一是信息传递的先后；二是信息传递的 类型，即在什么样情况下传递什么样的信息；三是每条信息的具体内容是什么，包括字段 组成、每个字段的含义、各字段罩的具体分类。本研究采用了代理技术，为实现车间的 实时动态调度优化资源配置，各代理问必须进行信息的交互，尤其是一些实时消息。因 此，a g e n t 间的通信协议必须定义通信过程、消息格式、消息内容，使各a g e n t 明确知道 其语言的语意。具体到车间，就是要明确其调度控制的过程，为完成控制所需的信息参 数类型及其具体内容。 1 2 3 多智能体协作原理 多智能体系统( m a s ) ，是由多个可计算的智能体组成的集合，其中每个智能体是一 个物理的或抽象的实体，可作用于自身和环境，并与其他的智能体通讯。也可以定义为： 多智能体系统是由一些对所处环境具有局部观点并对环境产生局部响应的智能体构成 的网络系统。还可以定义：“多智能体系统是一个分布式系统，系统中多个异步且松耦合 的问题求解器( p r o b l e ms o l v e r ) 共同协作”1 9 - 1 0 l ，以完成无法由单一求解器独立承担的任 务。在此，异步表明各问题求解器是并行操作的：松耦合则表明各问题求解器更多的工作 是内部计算，而不是相互间的通讯。多智能体系统理论的研究实质上是“分布式人工智 能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 ) 的一个分支”【1 1 j 。分布式人工智能侧重于对计算 机研制的研究，如对分布的传感器数据的分析、组织结构和协调协议等的研究。这方面 6 第辛彰钾能体协f 1 系统研究 的研究已经开展了近二十年，逐步走向成熟。但是，随着传统的人工智能研究的深入， 出现了协商理论、分布推理、智能体之间的学习和通讯语占等新兴的研究领域。 进化计算是一种模仿自然界中生物之间“自然选择、适者生存 的进化机制而提出 的随机型计算方法，应用于问题求解已经有三十多年的历史，“从r o t h e n b e r g 提出求解 函数最优化的进化策略( e v o l u t i o n a r ys t r a t e g y ，e s ) ”1 1 2 j ，到f o g e l 提出用于进化有限状 态机的进化编程( e v o l u t i o n a r yp r o g r a m m i n g ) 方法，一直到“h o l l a n d 提出的遗传算法 ( g e n e t i ca l g o r i t h m ，g 舢”1 1 3 】，都是达尔文进化论思想在问题求解领域的映射。其中， 遗传算法应用最广，它已经成功应用到十分广泛的问题领域，如多峰函数最优化、机器 学习及复杂结构进化问题( 如基于遗传算法的神经网络) 等。但是，遗传算法也随着问题 复杂度增加而变得低效甚至无能为力，这主要是因为传统的遗传算法中存在着一些内在 的问题： ( 1 ) 传统遗传算法中的物种群体具有很强的收敛性，这导致算法到最后只保留了最 “强壮 的个体，而排除个体多样性和个体之间的共生，这样对于那些需要给出更多信 息而不是只给出峰值的问题就无能为力了。 ( 2 ) 传统遗传算法中的每个个体都代表了求解问题的完整解决方案，并且个体之间 是彼此孤立的。由于没有建立群体成员之间的交互模型，十分不利于成员之间产生共同 适应和协调行为。 为了克服传统进化算法的不足，解决一类更为广泛的机器学习、共同适应以及多智 能体间的协调问题，人们模仿自然界中物种之间的协作机制， “提出了协作计算( c p c ， c o r p o r a t ec o m p u t i n g ) 方法 【1 4 1 。早期的这类算法有h o l l a n d 的基于规则的学习分类器系 统，d ej o n g 的拥挤技术，g o l d b e r g 的适应度共享模型，g r o s s o 的孤岛模型，h 此b a n d s 的自然规划和调度算法以及h i l l i s 的基于“寄生物与寄主模型的协作算法等。 目前己经发展了多种不同的协作方法，如“基于捕食者一猎物问题得到的竞争型协 作方法( c o m p e t i t i v e e v o l u t i o n ) ” i s j ，“基于自然界中的共生现象衍生得来的合作型协作 方法( c o o p e r a t i v ec o e v o l u t i o n ) 1 1 6 j ，还有“基于自然界中个体的生存期适应度评估 ( l i f e t i m ef i t n e s s e v a l u a t i o n ) 方法产生的协作遗传算法( o o e v o l u t i o n a r yg a ) 1 1 7 1 等。 在多智能体协作问题中，针对不同的应用领域背景，可以选择竞争型或合作型协作 方法。一般地，对于相互问存在资源争夺、捕猎等竞争关系的智能体，可以采用竞争型 协作方法调节智能体之间的关系，使得智能体通过彼此之间的竞争而获得性能提升：而对 于需要多个智能体合作完成共同任务的场合，一般采用合作型协作方法，合作型协作注 重于群体之间的合作关系，通过对群体间有利于合作的个体进行适应度加强，不利于合 7 人适交通人硕 ：? 何论文 作的个体进行适应度减弱，促使群体向着有利于产生相互合作和共同适应行为的方向进 化。 1 2 4 多智能体下车间调度问题 ( 1 ) 车间调度问题介绍 车间调度问题可以说是生产管理的核心问题，调度的成功与否，对保证生产目标的 最佳实现，对在制品库存、交货期限满意率、缩短供货周期、提高生产效率都有重要作 用，特别还关系到企业的大量投资的收益问题。调度问题就是指在一定时间水平上合理 分配资源，以达到预先设定任务的指标。调度问题按生产方式的类型分为“开环车间型 ( o p e ns h o p ) 和“闭环车间型( c l o s e ds h o p ) p s 】，前者面对顾客，后者面对库存；而在 开环下j o bs h o p ( 作业车间) 和f l o ws h o p ( 流水车间) 是最重要也是研究最多的两类基本调 度问题1 1 9 1 。本论文主要是j s p 问题研究。1 9 5 7 年，j a c k s o n 把调度问题分为静态和动态 两种，静态调度基于以下三点假设：( 1 ) 待加工工件集合确定；( 2 ) 加工时间确定，且作 计划时全部待加工工件已到位；( 3 ) 用到的机器可以连续运转。也就是说，静态调度要求 利用整个生产系统的全部信息，是信息完全的调度。而动态调度则是信息不完全的一类 调度，其特点是：( 1 ) 能在生产线实时调度；( 2 ) 对随机扰动能在线识别，并快速重新调 度。实际生产中，工件的到达和机器故障的发生常常是随机的，生产系统的各种信息也 不可能完全获得，所以动态调度才是我们追求的目标。 ( 2 ) 车间调度问题描述 调度通常用甘特图( g a n t tc h a r t ) 来表示，下图为4 个工件、3 台机器的面向机器的 甘特图： m a m 2 m 1 图1 34 个工件3 台机器的甘特图 f i g 1 34p i e c e3m a c h i n e g a n t tc h a r t ( 3 ) 车间调度问题研究方法 8 第章多纠能体协竹系统研究 调度i 、u j 题的研究是一个闭环的、不断反复优化的过程；建模与算法研究是核心。模 型的结构、输入与输出完全由实例和决策者决定，模拟仿真可以利用计算机语言实现， 而研究算法则是相对独立于实例的纯数学优化问题，这是本论文的算法研究对象。车间 调度是在计划的基础上，从备选计划中选择一组可行计划，在满足活动对时间要求和有 限共享资源约束的条件下，为每个活动分配所需资源与时间。人们在某一时期为了制造 不同产品，必须使用共同资源，如人力、材料、设备等，就会出现如何有效分配资源的 问题，即车间调度问题。调度可以定义为若干个任务在一组机器上进行加工时如何按时 间对机器等资源进行安排，使某些目标函数达到最优或近似最优，即调度的优化。调度 重点强调时间概念，具有实时性，对快速响应性要求更高。小生境遗传算法在解决车间 调度问题上也有着巨大的贡献。车间调度是生产管理的核心内容和关键技术，其任务是 在企业车间有限的资源约束下，确定工件在相关设备上的加工顺序和加工时间，以保证 所选定的生产目标最优。科学的制定生产调度方案，对于控制车间的在制品库存，提高 产品交货期满足率，缩短产品供货周期和提高企业生产率起着至关重要的作用。已有很 多用于求解车间调度的最优化方法被提出。包括启发式方法、仿真方法、人工神经网络 和拉格朗日松弛法，尽管这些研究取得了一定的成果，但它们仅适用规模较小的问题， 且寻优结果不具备全局特性。用基于小生境技术的遗传算法解决车间调度问题可以克服 上述缺点。 车间调度的特点： 复杂性：从原材料到产品，各操作任务相互影响、相互作用，加之产品工艺的多 样性和环境条件的不确定性，随着调度问题规模的增加，调度方案和求解问题所花费的 时间呈指数增加。由于n p 问题的难解行，如今人们不再苛求能够在自己可接受的时间 内找出尽可能好的解，而倾向于针对具体的组合优化问题设计算法，以求在尽可能短的 时间内找出尽可能好的解。 不确定性：车间调度的不确定性主要表现在随机性和模糊性。 多约束行：生产资源( 人力、原料供应、设备生产能力) 的数量、缓存容量、市 场需求产品的交货同期以及产品的工艺流程等都是约束。众多约束限制使调度问题建模 和求解更为复杂。 多目标性：调度优化的目标多，如最短生产期、最大生产利润、最小提前拖延惩 罚、最小费用及最满意程度等。这些目标之间往往有抵触，使各个目标都最优往往是很 困难的。生产实际中优化目标常常是多目标的综合考虑，包括成本、资源利用率、利润 目标等。 车间调度问题优化的主要目标： 9 人连交通人学i 颂卜忙沦艾 最大能力指标，包括最大生产率、最短牛广：剧期等，它们都可以归为往f 州定或者 无限的产品需求下，最大化生产能力以提高经济效益。 成本指标，包括最大利润、最小化运行费用、最小投资、最大收益等，其中收益 指产品销售收入，运行费用包括库存成本、生产成本和缺货损失等。 客户满意度指标，包括最短的延迟，最小提i i i f 或者拖后惩罚，平均延迟时问( m e a n t a r d i n e s s ) 最小等。 1 2 5 多智能体交互和协作原理与方法 实际上是学习如何由群体来执行一项给定任务的问题，解决这个问题需要群体机器 人从它们与环境的局部交换中连续地获取经验。这些群体经验是逐渐更新的。该系统是 一个具有并行和协作特征的抽象模型，可应用于物体搬运、清理房间、机器人足球等等。 根据智能体最基本的定义，它应该具备三个特性：自主性、环境交互性和社会性【刎。即 智能体能够独立的思考、行动而不需要人或其他智能体干预；智能体能够从外界获取环 境信息，并通过自身活动对环境的施加影响；智能体能够与其他智能体进行通信以及动 作之问的分工协作。根据智能体的以上特性，协作智能体的设计应该包含以下几个模块： 感知模块，通信模块和随行计算模块。感知模块负责收集环境信息，包括搜索目标，目 的地，以及识别同伴；通信模块负责与其他智能体尽心通信以及与外部环境交互；随行 计算模块负责所有的协同运动的选择与评估计算信息由一个主机进行集中处理。 对于研究多智能体协作与设计系统时，研究多智能体的协作方法是关键点的，下面 列举了现在常用的关于多智能协作方法： ( 1 ) 基于合作型协作的问题自动分解 协作算法中建立了进化个体之间的交互模型，个体之间通过彼此间竞争与合作关系 的协作交互模型担负不同的角色。对于竞争型协作，这些角色之间是相互对立的，而对 于合作型协作，个体之间是合作关系，它们共同分享公共任务的后果，包括分享成功完 成任务的奖励以及分担任务失败的惩罚等。有一类问题最适合利用合作型协作方法解 决，它们的特点是，问题能够被自然地分解成一些彼此交互或者合作的子模块来解决， 每个子模块能够在它自身的群体中进化，并且每个进化群体都能为问题的解决方案提供 最好的个体。“p o t t e r 和d e j o n g 的通用合作型协作模型1 2 1 ”1 2 1 j 重点研究了如何将问题 自动分解成合适的子模块和角色，这些子模块之间能够通过协作产生共同适应。他们还 提出了一种“物种创建和消亡模型”，通过适当的物种创建及消亡算法自动产生合适的 子模块数目。如图1 1 1 0 第一审多钾能体t 协作系统研究 如果检查到进化停滞不前，则： 对于代表子模块的每个物种群体，进行： 检查代表该子模块的物种群体的贡献 如果贡献不足够，煳老掉代表该子模块的物种群体( 物种消亡) 加入一个初始个体为随机个体的群体( 物种创建) 对新加入群体中的个体进行适成度评体 结柬 图1 4 物种创建和消亡模型 f i g 1 4m o d e lf o r t h ec r e a t i o na n de x t i n c t i o no fs p e c i e s ( 2 ) 神经网络合作型协作 m i i k k u l a i n e n 等提出了一种m u l t i a g e n te s p ( e n f o r c e ds u b p o p u l a t i o n s ) 方法1 2 2 1 ，采用 神经网络控制智能体，神经网络中的每个神经元都由一个子群体来进化，多个神经元之 间形成合作型协作的关系，并且在一个公共任务中对整个神经网络进行测试。通过追逐 实验发现，这种结构可以大大减少智能体之间通信的作用，在智能体协作过程中相互之 间甚至不必要通信，不适当的通信反而会引起协作效率的降低。 ( 3 ) 强化学习方法 “b a l c h 等研究了机器人团队使用强化学习( r e i n f o r c e m e n tl e a r n i n g ) 方法 2 3 l 获得 行为多样性的问题，他发现，当强化效应作用于局部时( 如分别应用到每个智能体) ，团 队中的智能体都学到相同的行为；而对于所有智能体的全局强化效应，则可以带来多样化 的行为。这个结论为多智能体协作模型中的信贷分配策略提供了有益的启示：即使一些智 能体没有像其他智能体那样为团队做出同样大的贡献，也需要对整个团队进行奖励，因 为单纯奖励个体会导致每个个体都不顾团队的整体利益而只顾增大自身的报酬，从而引 起不良的竞争行为。 本章小结 本章论述了论文的研究背景、简要内容以及文章的总体结构，在第二节中对智能贴 片系统的贴片结构、贴片协议、多智能下车间调度问题及协作原理及多智能体的交互和 协作方法作了简要的介绍，为接下来论文的主要研究做了铺垫。 人j 尘瓮j ! ! i 人：0l 学硕卜学何沦文 第二章基于车间控制智能贴片多智能体调度系统 2 1 智能体车间调度系统架构 多智能体车间调度系统主要由四个智能体组成，a g e n t 将调度分为工件a g e n t ，车i 日j 任 务a g e n t ，设备a g e n t ，管理与监控a g e n t 。当车间管理人员输入调度作业以后，系统通过 这四个智能体的交互和合作，共同完成调度任务，然后输出调度结果，如图2 1 所示。 图2 1 多智能体车间调度系统框架 f i g u r e2 2f r a m eo fm u l t i - a g e n tb a s e dj o bs c h e d u l i n gs y s t e m 2 1 1 基于工件智能体 工件智能体用于接受外界以及车间任务智能体及管理和监控智能体的输入判断，判 断是否可以完成任务，如果可以则分配工序给设备智能体，由具体的设备去完成任务以 及最终输出作业安排等。当车间任务智能体分配给工件智能体的工件完工或者中途某故 障时，这时管理和监控智能体负责采集数据，然后传到人机界面，由人工进行处理。 2 1 2 基于车间任务智能体 车间任务智能体用于提供车间所有资源的信息以及可完成的任务的工件，传递相关 的信息给工件智能体和设备智能体，包括些待完成的信息，以及最新一些从人机界面传 递的规则。 车间任务智能体的知识库包括车间资源的详细信息，包括加工时间，加工成本，损 耗等具体细节。如图所示，车间资源智能体与其他智能体均具有通讯协议。 1 2 第一：蕈荩j 1 i 问扣制爷。能0 蚺片彩钾能体凋瞍系统 2 1 3 基于设备智能体 设备智能体用于对各个工序的最后执行，以及他们之1 1 日j 的协调，设备智能体主要接 受由工件智能体对工件信息分解后的工序，然后由设备智能体去完成。 2 1 4 基于管理和监控智能体 管理和监控智能体主要用于解决加工工序的冲突