（机械设计及理论专业论文）基于混合动态系统建模方法的制造单元仿真优化研究.pdf

华中科技大学博士学位论文 摘要 。随着先进制造技术的发展，制造系统变得越来越复杂，对其设计、调度及控制 要求越来越高。作为一种有效的工具，计算机仿真技术在这个领域应用的越来越广 泛。但计算机仿真作为一个测试与验证平台，仅仅只能对给定的设计结果进行评价， 无法提供进一步的辅助决策功能。近年来，在仿真基础上发展起来的仿真优化技术 则弥补了这方面缺陷。仿真优化方法通过仿真模型与优化决策机制的结合，一方面 为仿真增强了智能决策机制，另一方面解决了传统优化方法无法处理复杂系统模型 描述的问题。但是，目前仿真优化主要集中在优化算法上，缺乏从系统和应用对象 的角度对其进行总体研究，使得仿真优化的进步发展失去了基础。脾文针对目前 仿真优化研究中存在的实际问题，从系统、建模、算法上进行了创新，以解决制造 单元设计、调度和控制的优化问题。 本文首先对当前仿真优化工作中所存在问题进行了详细地分析与研究。在前人 的研究基础上，结合先进的设计理念，提出了种新的基于虚拟仿真环境的仿真优 化理论框架。 f 其次，依据所提出的仿真优化理论框架，在面向对象的建模思想指导下，将混 合动态系统模型描述和工作机制应用到制造单元仿真建模中，这种混合动态建模方 法将连续变量和状态引入仿真模型之中，弥补了利用离散事件建模方法所引起的模 型描述和系统运行机制上的不足，提高了模型描述的完整性和可信度。1 ，- 7 然后，针对制造单元仿真模型的特点，并根据变尺度遗传算法和增强禁忌搜索 算法的工作原理和运行机制，提出了一种新的混合仿真优化算法，作为仿真优化系 统的优化搜索引擎的核心。了提高仿真优化效率，增加仿真优化的问题求解功能， 论文应用神经网络技术，设计了神经网络加速求解器，用于完成仿真优化的加速和 逆向求解的功能。土夕 最后，通过对制造单元优化设计问题的界定，根据仿真优化理论框架和关键技 术的研究成果，构造了面向制造单元的仿真优化设计环境，接着，基于这个环境开 发了一个面向制造单元优化的原型系统一一s i m o p t1 0 ，并通过实例对论文相关研 究工作进行了验证 ， ， ：； v 7 一一- 。o 、 关健词t 仿真优化j 混合动态系统? 苞向对舅9 混合优化算法、神经网络越速，求解黟 华中科技大学博士学位论文 a b s t r a c t m a n u f a c t u r i n gs y s t e m ( m s ) i sb e c o m i n gi n c r e a s i n g l yc o m p l i c a t e d w i t ht h e d e v e l o p m e n t o fa d v a n c e dm a n u f a c t u r i n gt e c h n o l o g y , s oad e m a n df o ra ne f f e c t i v ed e s i g n ， d i s p a t c h a n dc o n t r o lo fm si s a r i s i n g a s a l le f f e c t i v e t o o l ，c o m p u t e r s i m u l a t i o n t e c h n i q u eh a sb e e na p p l i e dw i d e l yi nt h ed o m a i n h o w e v e r ，i tc o u l do n l ye v a l u a t et h e g i v e nd e s i g nr e s u l t s 。a n dc o u l d n tt a k ea nu l t e r i o rs t e pt oh e l pd e c i s i o n - m a k i n ga sa t e s t i n ga n dv a l i d a t i n gp l a t f o r m ，i nr e c e n ty e a r , s i m u l a t i o no p t i m i z a t i o n ( s o ) t e c h n i q u e t a m eo fs i m u l a t i o nr e m e d i e st h el i m i t a t i o no f s i m u l a t i o n t h r o u g hc o m b i n e ds i m u l a t i o n m o d e lw i t l lo p t i m i z a t i o nd e c i s i o nm e c h a n i s m s oe n h a n c e ss i m u l a t i o nw i t l lc a p a c i t yo f i n t e l l i g e n td e c i s i o n s ，a n ds e t t l e st h em o d e ld e s c r i p t i o n ( m d ) o f t h ec o m p l i c a t e ds y s t e m ， w i t hw h i c ht r a d i t i o n a lo p t i m i z a t i o na p p r o a c hc o u l d n td e a l p r e s e n t l y , b e c a u s em o s to f r e s e a r c ho ns of o c u s e dm a i n l yo no p t i m i z a t i o na l g o r i t h m sa n di g n o r e ds y s t e ma n d a p p l i e do b j e c t s ，s ol o s e sah e a d w a yb a s e a i m i n g a tt h ep r a c t i c a lp r o b l e m s e x i t i n gi ns o ， t h ed i s s e r t a t i o ni n n o v a t e dt h es y s t e m ，m o d e l i n ga n do p t i m i z a t i o na l g o r i t h m ，w h i c ha r e u s e dt os o l v et h ep r o b l e mo f d e s i g n ，d i s p a t c ha n d c o n t r o lo p t i m i z a t i o no fm a c h i n ec e l l i nt h e d i s s e r t a t i o n ，f i r s t l y , t h ep r o b l e m sl y i n g i nt h ep r e s e n tr e s e a r c ho ns oa r e a n a l y z e d a n ds t u d i e di n d e t a i l a c c o r d i n g t ot h e p r e d e c e s s o r s a c h i e v e m e n t sa n d c o m b i n e dw i t ha d v a n c e dd e s i g nt h e o r i e s ，an e wa c a d e m i cf r a m e w o r ko fs oi sp r o p o s e d b a s e do nv i r t u a le n v i r o n m e n t s e c o n d l y ，a c c o r d i n g t ot h ea c a d e m i c f r a m e w o r k ，a n d w i t ht h e g u i d a n c e o f o b j e c t o r i e n t e dm o d e l i n g ( o o m ) ，t h em d a n dr u n n i n gm e c h a n i s mo fh y b r i dd y n a m i c s y s t e m ( h d s ) a r ea p p l i e dt o t h es i m u l a t i o nm o d e lo fm a c h i n ec e l l t h e a p p r o a c h m o d i f i e st h ef a u l t sc a u s e db yd i s c r e t ee v e n ts y s t e m ( d e s ) m o d e l i n g ，a n di m p r o v e s i n t e g r i t ya n dr e l i a b i l i t yo f m d t h i r d l y , a i m i n ga t t h ef e a t u r eo fs i m u l a t i o nm o d e lo fm a c h i n ec e l l ，an e w h y b r i d s i m u l a t i o no p t i m i z a t i o na l g o r i t h mi s p u tf o r w a r dt h a ti sk e r n e lo fo p t i m i z i n ge n g i n e n e u r a ln e t w o r kt e c h n i q u ei su s e dt o d e s i g nn e u r a ln e t w o r ka c c e l e r a t i n g & s o l v i n g c o m p o n e n t ( n n a s c ) f o ri m p r o v i n gt h er u n n i n ge f f i c i e n c ya n da d d i n gt h er e s o l v i n g a b i l i t yo f s o t h e c o m p o n e n t c o u l da c c e l e r a t et h es oa n df i n i s hr e v e r s e de x p l a n a t i o n s f i n a l l y , t h r o u g hd e f i n i n gt h eo p t i m i z a t i o np r o b l e m so fm a c h i n ec e l l ，ad e s i g n i n g e n v i r o n m e n to fs of o rm a c h i n ee e l li sc o n s t r u c t e da c c o r d i n gt ot h ea c a d e m i cf r a m e w o r k a n dt h er e s e a r c hf i n d i n g so f k e yt e c h n i q u e s t h e nap r o t o t y p es y s t e mf o rs o o fm a c h i n e c e l li sd e v e l o p e d ，i e ，s i m o p t1 0 ，a n dt h ec o r r e l a t i v er e s e a r c h p r o g r a m s a r ev a l i d a t e db y s o m ei n s t a n c e s k e y w o r d s ：s o h d so o m h y b r i ds i m u l a t i o no p t i m i z a t i o na l g o r i t h m n n a s c l i 华中科技大学博士学位论文 = = = = = = = = ；= = = = = = = = = = = = = = = = = = 一= 1 绪论 1 1 课曩概述 1 1 1 课篡的来源 本课题得到国家自然科学基金重大项目“支持产品创新设计的知识获取、组织、传递及运 用研究”( 项目批准号：5 9 9 9 0 4 7 0 - - ：2 ) 和湖北省科技攻关计划“数字化设计、分析与仿真平台 的研发与产业化”项目资助。 本文的研究目的为：通过对制造单元仿真建模和仿真优化技术的研究，构建一种面向制造 单元的仿真优化环境，用于解决制造单元设计与调度控制中的几类优化问题。 1 1 2 研究背景 随着先进生产制造技术的发展，制造系统变得越来越复杂，对它的设计、控制、调度也变 得越来越困难。然而，先进生产制造技术的发展对设计要求却越来越高。传统基于数学分析的 设计方法很难得到理想的结果。据报道，国外已运行的复杂制造系统( 特别是f m s ) 中，约有8 0 没有完全达到设计要求，其中6 0 是由于生产线的规划不合理设计或者对生产线的控制或调度 的失误造成的。为了避免投资失误带来的风险，提高生产线的生产效率，需要对生产线的设计 方案进行分析和评估。然而，觋代的先进生产线都具有复杂的结构，完全是个集物流、加工、 调度于一体的完整 造系统，具有动态性和复杂性等特点，传统的理论和方法很难处理此类系 统。为了更好地认识现代生产线的行为和性能，需要采用与之适应的先进理论和工具对其进行 研究圳。 系统仿真技术为复杂系统设计，尤其是制造系统设计提供了一种新的、有效的工具。它不 仅能将制造系统中复杂的逻辑、工艺、调度、控制关系转换为比皎直观的模型描述，而且能够 充分考虑影响系统的外界、内部的随机因素；不仅能够建立系统的静态模型，而且能够i 蘑过仿 真描述系统的动态特性。因此在审i 陛系统的设计和运行控制中，有大量的问题可以利用计算机 仿真技术去求解，如： ( 1 ) 系统性能参数的预测 对于个审燃统常常需要了解它在某些特定条件下运行的性能参数。如对f m s 系统，若 已知其运行条件( 零件加工时间，毛坯到达规律，刀具寿命规律，刀具分配情况等) ，求解系统 运行的主要性能指标，如生产率、零件通过时间、平均等待时间等，如果通过数学模型去分析， 尤其对于包含多台设备的f m s 系统，很难得到有效结果，但通过计算机仿真就方便得多。 ( 2 ) 系统设计方案的选择 华中科技大学博士学位论文 对于一个待建的制造系统，人们需要先进行配置设计和布局设计。如选择机床的类型，机 床的数量，托盘的数量，布局的方案等时存在多种可行方案解，但如何在其中选出最优方案， 可以通过建立不同方案的仿真模型进行试验结果对t e 。 ( 3 ) 管理调度方案决策 制造系统中，大至一个车间，小至一个刀具管理系统，都会经常不断地遇到计划调度问题。 但在生产实际中，采用数学模型进行求解，无论在考虑时间还是解的精度上都不太可行，计算 机仿真可以通过建立统一模型，测试不同调度方案下系统的整体运行状态f 4 】。 当前在制造行业出现的许多先进带归盏理论和设计方法也将仿真技术列为其中的项重要内 容，将仿真集成到制造系统设计、生产、控制、调度已经成为一种趋势”】。 1 1 3 课鼍的目的、意义 计算机仿真技术作为一种建模、实验分析方法，能够把组成制造系统的生产资源、产品工 艺数据等信息动态地结合起来，以制造系统活动过程的“复现”代替以往数学等方法单纯的抽 象描述，其表达形式易于理解，能全面反映制造系统的活动过程和特征，为制造系统的设计和 调度控制提供了理想手段。仿真方法本质上是种试验方法，它把个现实或抽象系统的部分 状态或特征用个系统( 或模型) 代替，通过不断改变设计变量使得输出结果相应的发生变化， 从而提供对设计变量最直观的评估。 从另一个角度看，仿真虽然能够提供有效的、精确的模型，但就它本身而言，它只是种 描述性( d e s c r i p t i v e ) 的方法而不是说明性( p r e s c r i p t i v e ) 的模型工具1 5 1 。仿真作为个测试与 验证平台，仅仅只能解决正向的求解问题( 预测) ，即将给定的输入( 设计变量) 通过仿真模型 映射至i j 输出端。传统基于仿真方法的设计过程如图1 - 1 中虚线框内所示，遵循：设计模型一动 态运行该模型一得出结果一设计人员分析( _ 般需要通过咨询专家) 的流程。在这个过程中， 仿真模型只能$ 黾供大量的与决策变量对应的输出结果数据。而设计人员需要从中发现规律，并 最终确定最优的设计方案和模型。无疑，这一步工作不仅需要设计人员具有较强的数据分析专 业知识，并且需要大量的时间和经验去处理这些海量的数据。 在设计一个新系统时，往往存在许多种设计方案，通常经过对不同设计方案进行系统设 计目标函数的评估，从中选出各种指标都比较好的方案。对于简单的系统来说，可以通过对 少量设计方案的逐个比较和筛选或者通过专家意见找出较优的结果。但对于复杂系统来说， 设计目标往往受到大量的决策变量、环境变量以及许多随机因素的影响，决策变量和设计目 标之间也存在复杂的各类线性、非线性约束，同时，目标函数的响应曲面大都具有很强的非 线性、多峰值等特征，设计方案的解空间相应的也变得非常巨大，如在制造系统的调度控制 中涉及到的大量的组合优化问题，即使利用当前最快的计算机，通过最有经验和专业知识的 设计人员或者专家人工决策，在求解时间和解的质量上往往都不能令人满意，当然以上假设 华中科技大学博士学位论文 往往是不现实的“1 】。 图1 1 传统仿真设计方法 随着高性能计算机技术的发展和软件理论及应用技术的不断提高，可以考虑将仿真与一些 决策机制或智能机制结合，使仿真在处理问题时能够带有更多的智能因素，如方案的优化求解， 结果的自动分析等等，将给e 述问题的求解提供了一条光明之路，同时也使仿真摆脱了纯粹的 工具角色，变成了个真正具有智能睁征并能辅助决策的有效方法，无疑，这将给仿真技术带 来更广泛的发展空间，也将大大改进工程设计人员的工作方法和设计手段【1 2 1 。 仿真优化也正是基于这种思想提出的( 如图1 - 2 ) ，与传统仿真设计方法相比，设计人员从 仿真模块和决策流程的闭环中跳了出来，通过在设计流程中嵌入了决策系统、专家系统和优化 引擎，一方面使得设计人员不再直接面对仿真模块所提供的各种类型的海量数据，把令人繁琐 的计算、搜索甚至决策任务部分或完全交给计算机，充分“享受”高科技带来的乐趣；另一方 面，在仿真设计的流程中不需要再增加与设计人员交互的专用数据通道，充分降低了系统的开 发复杂度，同时提高了系统的集成度。 图i - 2 仿真与决策系统的关系 华中科技大学博士学位论文 1 1 4 仿真惯帧出 从传统优化意义上说，优化进程首先需要确定目标函数、决策变量、优化问题的数学模型 以及系统各种约束条件，然后需要设计算法搜索策略以及相关的优化机制。而仿真优化与传统 优化的本质区别就在于：在传统优化进程的基础上用系统仿真模型替代优化问题的数学模型。 虽然在形式上，仿真优化方法与传统优化方法的区别很小，就是一个模型的替代问题，但在实 际应用中。与仿真优化方法相比，传统优化方法无论在模型描述还是搜索机制上都无法满足当 前的设计要求，具体表现为： ( 1 ) 传统基于数等制描述的方法一般只自铡泣系统在稳态和静态的模型。因此对这类系统分 析时，对其动态因素进行了大量的简化和假设，而这些因素实际上往往对系统有非常大的 影响，从而使得无法对这类制造系统的动态特性和随机因素进行准确的预测和分析。即使 在当前的分析方法中引入了动态分析参数，但是因为基于数学分析方法的求解需要大量的 计算和建模时间，无法适应处理复杂制造系统的要求1 4 ，7 - m 14 】； ( 2 ) 很难建立这类系统的分析和优化数学模型。在很多实际问题中，如生产过程、开放存储网 络、资金预算、人工智能、专家系统等领域，人们制定决策时会碰到两类不确定性现象， 一类是随帅赊，类点蝴现象，以往的最侈淞教术需要将实际问题抽象为各种解析模 型，即目标函数与一些约束条件，然后根据目标函数与约束条件的形式，选择适当的方法 进行优化。然而有些复杂系统并不能简单地处理为几个函数和若干个约束条件，因此对于 这种情况线性规划与非线规划等优化技术就无能为力了【”，博一7 1 。 ( 3 ) 即使可以通过数学模型对带糙系统进行描述，但问题性态上般都是n p 问题，很难通过 传统优化方法得出满足功能目标或其它目标的最好解1 1 5 - - 1 7 。 仿真优化的基本思想是将所研究问题看作一个“黑箱”，用仿真模型描述这个“黑箱”的输 入输出之间的逻辑关系，提供由输入到输出的映射；将输出信息作为“优化器”的输入，“优化 器”根据对仿真输出的分析与评价的结果，生成新的系统参数或决策变昏挂彳诗卜轮评估，然 后，不断重复以匕过程，直至满足一定的停止准则，可以用图1 3 基本框架描述仿真优化的工 作原理【1 3 1 卜1 9 1 。 e v a n s g w 等人( 于1 9 9 1 ) 认为仿真优化模型实际上是一种特殊的试错法( a na dh o e l r i a l - a n - e r r o rf a s h i o n ) ，分析员首先给仿真模型输入一个初始的设计变量，然后检查对应的性能 指标( 目标) ，分析员根据以前和当前的目标响应重新改变设计参数，从而逐步达到提高输出的 目的冽。但是问题在于这个过程如果没有个有效的指导，那么在可行域比较大的情况下，优 化过程将变得比较盲目和困难，这正是仿真优化设计的核心内容。 因此仿真优化可以定义为这样个过程，即不滔过明确评估每卟可能的决算呵珀瞅中 拢撇自孽 变t 仿= 鲋阱匕的刚尉酣潭小彻聃i 潍阮同喇七斟翻嘞陡试睑中的僦息 4 华中科技大学博士学位论文 输入 图l - 3 仿真优化的基本框架 当前的先进技术不仅为仿真开了一个新门，而且扩展了优化的应用领域。新的技术使仿真 能够应用在处理以前被认为是不可行的领域中，同样优化算法的发展也使优化方法突破了传统 方法求解对象的局限性。仿真与优化的集成使得仿真方法更加有效，仿真优化与传统优化相比 具有的最大好处在于能够处理不确定的和存在复杂交互情况( 撇化鲤很难建立) 的模型。 下面通过一个具体的实例来说明仿真优化的应用方式i ”】。 【问题描述】在个单队单服务员排队系统( g i g 1 ) 中，假设第i 个顾客在系统中的滞留时间 为d 。，服务台按照先到先服务( f i f o ) 的原则从队列中选择顾客进行服务。 【问题提出】一般说来，顾客的平均滞留时间x 较大时，说明服务员的效率较低，因而系统中 顾客的等待成本较高，而x 较小时，对服务员的工作能力有较高的要求，因而服 务成本较高。令e 为顾客的单位时间成本，c 。为服务成本，优化目标为系统运 行的总成本最少。则问题的提出：如何在工的可行域中找到个值z 使得系统 运行的总成本最少。 【问题求解】( 只考虑稳态仿真) ，则x 作为决策变量，可得所有顾客的平均滞留时间的期望值 为 广1 f ( 柳= z e f ( z 奶2 牌层恃酽i ( 1 1 ) 研】为函数期望值，为系统中顾客的数目，则系统的总成本可以简单地定义为： ，( x ) = c 。f ( x ) + c ，i x f l - 2 ) 则优化数学模型为 m i nf t 丑、= c c f t x 、+ c l | x s f 6 s x 土一6 【l o ， 九 其中，五为顾客平均到达率，6 为误差精度，令6 * 0 。 式( 1 - 3 ) 中，( x ) 没有解析表达式，给定个x 。只能通过一次仿真得到个f ( x ) 的 值。l 习此每一次设计变量z 的评估只能由仿真输出目标函数f ( x ) 得出，优化过程也就是根据 x 和f ( x ) 映射信息，通过优化算法在式( 1 - 3 ) 确定的x 可行空间中找到最优值。这是个 华中科技大学博士学位论文 典型的仿真优化例子。 仿真中的优化技术一直是一个充满“活力”的领域，由于仿真优化应用仿真模型作为求解 对象，它通过提供在不确定的复杂问题的决策极大增强了仿真模型的用处，使得优化对京的领 域得到极大的扩展，同时大大提高了优化设计的灵活性。今天，仿真优化已经在系统设计与自 动控制、仿真算法优化等领域得n t 相当广泛的应用，例如8 1 驯： 一生产计划中机器的最好配置： 投资规划中最好的资本组合； 一生产力设计中最好的雇员利用率； _ 商业推销中最好的机构位置； _ 电力规划中最好的运行计划： - 医院管理中最好的医护人员分配； 制造设计中最好的公差设置； 废物处理中最好的处理策略： 一许多其它实际目标； 1 2 文献综述 仿真优化技术起源于匕世纪四十年代，到八十年代，随着计算机技术和算法理论的发展仿 真优化得到了越来越广泛的关注。在w s c 2 0 0 1 ( 国际冬季仿真会议) 上，专家指出，仿真优 化将成为当前仿真工作研究的热点。在近几年的每一届国际冬季仿真会议上( s i m u l a d o n c o n f e c e ) ，国际上著名的仿真专家都针对当前仿真优化的研究和发展做个专题，在其中主 要讨论仿真优化的发展现状和仿真优化的发展方向【l 1 2 4 , 2 q 。仿真优化技术的核心就是仿真模 型和仿真优化算法，因此对其的研究也必须从以上两方面着手。 1 2 1 制造系统仿真建模技术发晨 ( 1 ) 制造系统建模技术综述 排队论于5 0 年代发展起来。6 0 年代开始用于描述帛| 谴系统的某些问题，如著名的u m e 定 律，在7 0 年代和8 0 年代以排队论方法分析f m s 颇为盛行。从7 0 年代末，数学规划开始用于 解决带! 瞄系统中f m s 的任务分派问题，应用动态规划法处理f m s 运行中的问题。同时，以美 国斯坦福大学教授y c h o 为首的研究者们创立扰动分析法，对d f _ d s ( 离散事件动态系统) 进行分析。p c l f i 网理论是6 0 年代初p e t r i 提出的适合分析非同步并发系统( a s y n c h r o n o u s c o n c 删s y s t e m ) ，在8 0 年代初期大量用于制造系统分析。二十世纪八十年代以来，陆续出 现了一些新的理论和方法。这些理论和方法通常被区分为三个基本层次，即逻辑层次、代数层 次和统计性能层次【l 4 ，1 闭，如表i - i 所示。 6 华中科技大学博士学位论文 逻辑层次的理论和方法着眼于在逻辑时间层次上，研究生产线中事件和状态的符号序列关 系，采用的主要数学工具包括形式语言有限自动机、p e t r i 网、马尔柯夫链等。代数层次着眼 于在物理时间层次上，研究生产线的代数特性和运动过程，采用的主要数学工具有极大极小代 数。统计性能层次着眼于在性能层次上，研究随机情况下生产线的各种平均性能及其优化问题， 采用的主要数学工具包括排队论、广义马尔柯夫过程等。 表i - i 现代生产线的建模和分析方法分类 可时宁化不可时序化 逻辑层次有限自动机形式语言方法 p e t r i 分析方法 代数层次极大极小代数方法 性能层次排队网络方法 摄动分析方法 系统仿真方法 随机性。卜i _ 一确定性 随着计算机技术的提高和仿真理论的不断充实，系统仿真已成为制造系统建模和分析的最 有力的工具。在许多先进的制造理论和系统中( 如虚拟制造、敏捷制造、产品全生命周期设计 等等) ，仿真技术都起着举足轻重的作用阻2 1 。但是，由于仿真技术的出现时间比较短，在系统 仿真建模理论和分析方法上还存在一些不足。 ( 2 1 计算机仿真建模的新发展 当前串胖元仿真建模技术主要采用离散事件仿真建模方法，在离散事件仿真中，将些 系统中存在的连续变量离散成点，系统的状态随着瞬间事件的发生而在些离散和随机的点上 发生变化。对于那些和时间特性紧密相关的变量，其变量在两个状态之间的变化被忽略。因此 无法满足对复杂系统的描述。仿真优化的基础是系统的仿真模型，对模型描述的越准确其结果 的可信度必然越高，对仿真模型的控制和仿真运行的设置也更加易于集成【”娜1 。 混合动态系统( h y b r i dd y l 倒cs y s t e m ，简称h i ) s ) 是在离散事件动态系统( d e d s ) 研 究领域中出现的一个新的生长点。与传统的基于离散事件建甓疗法相比，将混合动态系统的建 模方法应用于制造单元仿真中将大大提高模型的可靠性和准确性，同时使得仿真分析对象的领 域得到了大大的拓广。 所谓h d s 可以理解为同时包含有相互作用的离散事件过程和连续变量过程的类动态系 统，离散事件过程需要采用逻辑类型的模型来建模并服从于离散事件系统的演化机制，连续变 量过程需要采用微分或差分方程形式盼隧驰襁潞服从于连续变量系统的运动规律，而两者 的交互作用按具体问题有着多种类型和复杂的机理。 华中科技大学博士学位论文 混合动态系统一般具有如下几个特征：( 1 ) 系统中同时包含按照离散事件系统机制演化的 离散事件和基于连续变量系统规律变化的连续变量，系统状态的演化过程是种“混合”运动 过程。( 2 ) 系统中离散事件和连续变量之间依据某种规则构成相互作用，离散事件过程和连续 变量过程互为约束。( 3 ) 系统的状态是随时间而演化的，即系统具有个动态系统的基本特征。 对于h d s ，由于其中包含连续变量，使系统的动态呈现出比d e d s 更为丰富的形态，因此， 不能采用传统方法回避连续变量动态系统( c v d s ) 而将其简单地归结为d e d s 来加以研究， 尽管对于某些特定的h d s ，可以通过对连续变量的状态空间的区域划分，来得到在一定意义下 的连续对象的等价离散事件对象模型，但当涉及到系统的许多有意义的性能指标特别是时间型 指标时，考虑连续对象就非常必要。实践表明，在一些d e d s 模型中引入连续流模型使得求解 优化问题更为灵活和有效。 虚拟仿真技术为表述混合动态系统仿真提供了有效的平台，采用面向对象的建模方法，封 装了完整的实体属性，同时对仿真过程中事件的管理也采用与离散事件仿真不同的逻辑控制机 制，使系统运行时的对象之间的消息传递和事件处理更为自然和有效，另外，在虚拟仿真系统 中采用先进的图形技术，给设计人员提供了一种直观的交互和控制方式。 1 2 2 仿真优化综述 仿真优化模型在形式上与一般的优化模型似乎没什么不同，但由于仿真优化模型中的目标 函数没有解析形式，目存在着不可控因素的干扰，给定组输入变量后，只能通过仿真运行来 求得目标函数值，因此传统优化方法一般不能直接应用，需要针对其特点建立套特有的算法 体系，当前的仿真优化研究正是集中在算法的改良和算法适应度的调整，经过几十年的研究与 发展，仿真优化算法主要形成如下几类【1 3 1 7 , 1 3 2 9 3 2 ： 一、基于梯度估计的搜索方法 基于梯度的搜索方法是传统优化方法中应用最为广泛的类方法，如最速下降法等等。但 是仿真优化模型无法通过解析方法得出目标函数的梯度( 导数) 方向，因此在仿真优化方法中 采用种梯度估计方法，其核心就是i 蝴真模型给出的目标函数信息，采用不同的算法得出 近似梯度，然后再利用确定的数学规划方法来求解。问题描述为如下： m i n 厂( 0 ) 0 e e ( 1 - 4 ) 其中e 为决策参数，也就是输入变量，可行域 c r ”，假定可行域连续，目标函数值厂( o ) 可 通过仿真运行得到。则基于梯度估计的搜索方法的代表为随机优化( s t o d m f i c o p t i m i z a t i o n ) 。 随机i 优化解决的是在目标函数值无法解析得到但可以估计的情况下，如何得到最优解的问 题。典型的随机优化算法是基于梯度估计的迭代技术。 ( 1 ) r m 和k w 方法 华中科技大学博士学位论文 5 0 年代出现的r o b b i n s - m o n r o 和k i e f e r - w o l f o w i t z 是两个最常用的非限定随机逼近方法。 但当目标函数平缓时收敛很慢、目标函数陡峭时又会出现发散的情况，这两个方法的不足还包 括缺乏好的停止淮则和无法处理有约束的情况等。9 0 年代出现的一些新随钆优化方法与传统方 法比较，可以在更一般的假设条件下收敛，或者在某些条件下取得了更好的结果。 r m 方法用于解决式( 1 4 ) 中的优化问题时，若问题的可行域 封闭且为凸时，可产生一 个序列 为最优解的估计值，其中 0 + i = 。( 0 。一口。雪( 0 ) ) 行21 ( 1 5 ) 口。 是正实数序列，满足= 。且口：。，而童喊) 是g ( e 。) = v f o ( o 。) 的估计值， n - 1n - i 函数霄。将r 4 中的每个元素映射到 中的最接近的点。如。 序列通常选定形式为= a n ，口 是一个正标量，且口的取值随迭代次数的增加而变化，以满足e 述条件。这样的选择使得r m 方法在某些情况下具有最快的可能收敛速度，即以玎的速度收敛到最优解，r a m 方法的表现 在很大程度上依赖于标量口的选择。r m 方法一股仅能收敛于优化问题( 1 4 ) 的局部最优解， g - d f a n dsb 和sk m i t t s ( 1 9 8 9 ) 提出了如何用随机逼近的办法求解全局问题的方法。r m 的另 一个问题是当其求解优化问题( 1 4 ) 时，若可n o 无界且目标函数在决策参数e 上的增长速 度超过2 次方时，算法不能保证收敛，a n d r a d o t t i rs ( 1 9 9 6 ) 提出通过缩放比例的方法进行解决。 当有限差分法用于得到( 1 - 5 ) 中的梯度估计时，求解过程就称为k w 方法。使用k w 方 法解决问题( 1 - 4 ) 时，每次迭代需要执行至少d4 - 1 次不同参数值的仿真，其中d 是优化问题 的维数，这意味着当d 较大时，k w 方法迭代的计算量是很大的，会导致收敛较慢：s p a l ljc ( 1 9 9 2 ) 提出使用仿真扰动的方法解决该问题，这样在每次迭代时，不论维数多少，仅需要进 行两次仿真运行。 ( 2 ) 样本路径优化 样本路径优化的原理就是通过较多的样本所包含的目标函数信息进行寻优过程，通过列应 的均值函数近似得到期望值函数，再利用确定的非线性规划方法对均值函数进行优化。这样， 统计方法就介入到优化算法中，解决了随机优化中的一些问题并提高了方法的效率。假设问题 ( 1 - - 4 ) 表述为：令n 为正整数，设存在随机发量x ，e ，和函数h ：0 r _ r ，对于所 有的i = 1 , 2 ，n 和0 0 有服从累积分布函数为最的置( e ) 满足置c o ) = h ( o ，r ) ，这样对于 所有0 0 我们可以用 1 ( o ) = - 号e h ( o ，j j ：) ( 1 啕 i l 来估计目标函数。一旦随胡变量k ，巧，k 产生，近似目标函数就是个关于参数0 的确定函 数。 设随机变量置( e ) 的观测值可以通过逆变法得到，令i 为区间i o ，l l 上的独立均匀分布的随 9 华中科技大学博士学位论文 机变量，则对于所有的y o ，1 】和e o ，有矗( o ，y ) = 巧1 ( y ) 成立。假设对于所有的o o ， 随机变量x ( o ) 的密度函数为 ，且若有0 。 满足兀( x ) = 0 ，则可以导出矗( z ) = 0 ，有 ，( e ) = 协o ) d x = 卜怒诋o ) d x ( 1 - 7 )j ， 其中= ；型兴称为似然比。第二种方法中令r 为来自于的独立观测值，且对于所有的y 和 _ ，e 。q j 0 0 有h ( o ，y ) = 玑( _ y ) a o ( y ) ，函数h 在0 = 0 。上对e 的梯度值与似然比方法中g ( o 。) 梯度 的估计值是一致的。 样本路径优化方法的命名是由于此方法使用仿真产生一个样本路径k ，k ，y ，并且得到 的最优解的估计值是在优化问题( 1 - 6 ) 基础上的样本路径匕产生的。般说来，样本容量n 应较大，才能使( 1 - 6 ) 与问题( 1 4 ) 更加近似。 基于梯度估计方法的核心就是对目标响应函数的梯度估计，以下介绍几种典型梯度估计方 法。 ( 1 ) 有限微分法 这种方法是最原始的梯度方法，需要执行多次重复仿真，适用于瞬态和再生仿真。设 g ( e ) = v f ，而梯度通过估计得到的，所以有雪( o ) = 倍( e ) ，营：( e ) ，誊。( e ) ，则雪( o ) 估计式 有两种形式，即前向差分( 1 - 8 式) 和中心差分( 1 - 9 式) ， 前向差分雪( 0 ) = f ( o + c e , ) - f ( 0 ) 0 - 8 ) 中心差分雪( o ) ：f ( o + c e , ) ：- f ( o 一- 。e - ) ( 1 - 9 ) 其中f - 1 , 2 ，d ，c 为一个小的正标量，而e ，为第i 个单位向量。 两者的区别在于：在前向差分中，为估计在某特定x 值下的梯度，最少要做d + 1 次仿真运 行，而中心差分法则至少需要仿真2 d 次，但中心差分可获得比前向差分更小的偏差。 由于有限微分方法为了获得更加可靠的可，的估计值，需要多次的运行来求得的偏微分， 使原本已经很大的运行成本更高；另一方面为使偏差减小，需要c 较小，又造成了估计值方差 的增大。 ( 2 ) 似然比法( 1 i k e l i h o o d r a t i o so rs o o r ef u n c t i o n s ) 似然比方法又称评分函数，最早由g l y n npw 于1 9 8 7 年提出，r o b i n s t e i nh 于1 9 9 1 提出 对其的改进，r o b i n s t 咖h 和s h a p i r oa ( 1 9 9 3 ) 在此前研究基础e 又进步对其进行了拓展。 似然比法的特点是仅需要单次仿真运行就可以得到梯度的估计值，其基本思想是分析系统样本 路径的概率测度对随机变量分布函数的依赖关系，通过测度变换获得似然比，进而构造性能测 度的估计量。在此方法中，仿真输出变量的期望值对某输，入变量的梯度被表示成为输入变量 l o 华中科技大学博士学位论文 和仿真参数的函数期望值，仿真参数是指仿真运行长度、输出变量值等。设有： f ( o ) ；占( ，! e ) ) ( 1 - l o ) 其中x ( 0 ) 是服从累积分布函数r 的随机变量，其密度函数为凡，假设有下式成立， g ( o ) = vi x f e ( x ) d x = i x v f o ( x ) d x ( 1 - 1 1 ) 则有 g ( 0 ，= j 妥静施肛e x ( o ，黼 m 动 这样，就可以用x ，( o ) v f o ( x 。( o ) ) 厶( x ，( 0 ) ) 作为g ( 0 ) 的估计值，其中x ，( o ) 为从f 。产 生的独立的观测值。 又如，对于参数为e 的泊松过程，n ，是时间( 0 ，乃之间的事件数，y 是输出变量，则由 昙e ( y ) ：l ( 牛一r ) yi ，式子右边可以在仿真中通过统计跟踪计算得到。又如再生过程中， o a lj 输出变量的稳态值可以表示成两个期望值的比率似然比。 似然比方法具有良好的计算和变异特性，产生估计值的统计特性往往比较好，单精确的梯 度估计往往需要较长的仿真运行时间。 ( 3 ) 扰动分析( p e r t u r b a t i o na n a l y s i s ) 扰动分析是类常用的有关梯度的估计方法，b e t t o n v i lk 于1 9 8 9 年，g l a s s e r m a n p 于1 9 9 1 ， h oyc 和c a ox r 于1 9 9 1 分目对扰动分析法进行了研究，其中最有名的是耢小扰动分析( 理i a ) ， 在该算法中所有的目标函数的偏梯度通过单次仿真运 亏：估计得到。其基本思想就是跟踪系统的 仿真样本路径，分析参数扰动对系统性能的影响，获得仿真样本性能对参数的梯度( 样本梯度) ， 作为系统性能测度梯度的估计量。 无穷小扰动分析法中所有的导数可以在单次仿真运行中得到，所以从计算效率上有显著的 优势。但是，使用i p a 得到的估计值通常是有偏的且不稳定。 ( 4 ) 频域方法 频域试验是在一次较长的仿真运行过程中，应用不同频率上对选定的输入参数进行正弦振 荡，对输出变量值再进行谱( 傅立叶) 分析，如果输出变量对输入参数是敏感的，则参数的正 弦振荡将导致响应的对应( 放大) 振荡。这样，就可以发珊哪个输入捌燃出变量的影响 最大，从而找到梯度最大的方向。 但设定疑啸胡盘法需要选定合适的试验参数，如怎样确定i 式验单元嬲指数，怎样选定 驱动频率，怎样设定振荡的振幅。这些参数的选择还没有一种有效的计算方法，而需要相当的 华中科技大学博士学位论文 经验，因此实际应用的比较少。 二、响应曲面法( r s m ) 响应曲面法是试验设计与数理统计相结合的优化方法。i 疆过给定初始的试验设计点，分别 对这些点进行仿真运行，可以产生与各设诮式验点的仿真输出响应，通过应用系列回归模型， 将这些响应拟合成响应曲面，在响应面的最大梯度方向上寻优，对回归函数结果进行优化，得 到该响应面上的最优解：然后以该点为中心点再作试验设计，得到新的试验点，重复进行，直 到满足终l 七条件。该方法开始于一阶回归方程和最速上升下降搜索方法，在找到最优点的附 近时，使用更高阶的回归方程。般情况下，虽然r s m 比许多梯度方法所需的仿真次数要少， 但在复杂优化问题应用中需要的仿真次数仍然很多。 三、启发式方法 启发式方法是现代抛化技术发展的杰出成果，它们不仅在求解传统优化问题时表现出色， 而且由于启发式算法的具有非悌度、启发式搜索