仿真及优化发展现状和未来展望

.仿真及优化发展现状和未来展望摘要：仿真优化技术是实现传统制造向可预测制造、科学制造转变的关键技术，目前已经引起科学界和企业界的广泛关注。本文在阐述了仿真优化基本原理和方法的基础上，介绍了国内外仿真优化技术在制造系统中各个层次的应用概况、研究成果及各种仿真优化系统采用的开发工具，并对国内外发展状况进行了简要的对比分析，指出了目前仿真优化研究中存在的问题以及主要发展趋势。关键词：仿真，优化，仿真软件，仿真建模。引言20 世纪 90 年代，为了解决产品在 TQCSE 方面存在的问题，出现了多种制造模式，如可重构制造和大规模定制等。在这些先进制造模式指导下的制造系统规模庞大、结构复杂，制造系统从初期规划（资源配置、布局规划）到实际运行（供求关系管理、生产计划与调度）阶段都存在复杂的决策问题。这些决策问题包含众多影响因素、因素之间关系错综复杂，传统数学优化方法已经无法解决这类问题，仿真优化技术则以其独特的优化方法和强大的建模能力引起科学界和企业界的广泛关注。每年 Winter Simulation 会议都将仿真优化列为一个国际前沿课题来研讨，并介绍最新的理论研究成果及应用情况。2000 年，世界著名的两本仿真书籍Simulation Modeling and Analysis与Discrete Event Systems Simulation首次将仿真优化作为一个专题进行讨论，并指出仿真优化对仿真的推广应用具有重要的影响；自上世纪 90 年代中期开始，各种商业化仿真软件将优化作为一个重要模块纳入其中，目前已成为不可或缺的部分。尽管仿真优化已经取得了长足的发展，有些仿真优化系统已经开始工业应用，但仿真优化领域仍然存在一些亟待解决的问题。本文首先从仿真优化的原理、方法等方面对这一技术进行分析，然后综述国内外研究现状，最后分析仿真优化存在的问题及发展趋势。一、仿真优化原理 利用传统优化技术求解优化问题时，首先要建立问题的解析模型，然后利用某一方法进行优化，通常可以求得问题的最优解。但由于实际问题的复杂性和随机性，很难建立起精确的解析模型。仿真技术作为一种建模方法，能够将系统的相关要素按照实际的运行逻辑有机地结合起来，真实反映出系统的行为，因此可以利用仿真模型代替解析模型研究系统的行为特性。然而，仿真实质上是一种试验方法，通过枚举对备选方案进行逐一验证，搜索目标不明确，无法给出问题的最优或近优解，当试验方案较多时，该方法变得极其复杂，甚至无法实现。因此，将仿真技术和优化方法相结合为解决实际问题提供了有效的优化手段。仿真优化的基本原理是将仿真模型看作一个实值函数其中 X为可控因素，即决策参数，是不可控，f(X,) 因素为仿真模型的输出，它是一个向量函数。根据仿真优化原理，仿真优化过程描述如下：首先由优化算法产生初始解（决策参数），然后将其输入仿真模型中，仿真运行结束输出响应值（性能指标），通过数据转换接口将其反馈到优化算法中，作为优化算法确定新一轮搜索方向的依据，并将搜索结果重新输入仿真模型。上述过程反复进行，直至满足预先设定的终止条件。常见的仿真优化过程模型。二、仿真优化方法 目前常用的仿真优化方法包括如下几类：基于梯度的方法、随机优化方法、响应曲面法、统计方法和启发式方法等，其中每类都包括多种方法。很多文献重点阐述了各种方法的原理和性质，而对仿真优化系统的开发及其应用情况涉及很少，没有从系统的角度研究仿真优化的进展情况。在各类方法中，非启发式方法一般需要大量的理论假设，计算复杂、稳健性差，算法性能随求解问题规模的增大迅速下降，在实际中很少采用。启发式方法则可以避免上述弊端，除此之外，它还可以实现全局优化，并且能够解决离散、定性决策变量问题。 三、仿真优化研究现状 近几年，许多国家和大学的研究机构都开展了仿真优化的研究，特别是从 90 年代中后期，随着智能优化算法和仿真建模技术的充分发展和应用，仿真优化已从单纯的理论研究走向了实际应用，渗透到各个领域。 3.1 国外仿真优化的研究状况 1998 年，美国密西西比州立大学的 Bowden 等人首次指出，仿真优化研究人员缺乏从系统的角度对仿真优化进行研究，有必要将仿真优化的各种单点技术集成到一个统一的技术框架下，为此，他们提出了“六域”集成的仿真优化框架。“六域”涵盖了仿真优化的六个研究范畴，即问题域、算法域、分类域、策略域、智能域和界面域。问题域辅助用户构造目标函数和约束条件；算法域涉及优化算法库的建立及各种算法的描述；分类域依据求解问题规模和决策变量性质等对给定问题进行分类；策略域实现对某类问题选择适当优化算法，并在有限的计算资源基础上提高仿真优化效率；智能域根据所研究的领域问题知识选择适当的优化策略和方法；界面域研究优化器与用户及仿真模型的接口问题。“六域”构成了一个完整而有联系的理论框架，为仿真优化的集成问题指明了方向。基于“六域”集成思想，他们开发了一个仿真优化系统，并以一个“拉式”生产系统为例，重点研究各种仿真优化方法策略。该系统包括 33 个决策参数，以看板数量作为评价指标，优化算法分别采用进化策略（ES）、Hooke-Jeeves（HJ）模式搜索法及 ES 和 HJ 相结合的两阶段搜索策略。实验发现，HJ 收敛速度最快，但解的质量较ES 差，ES+HJ 方法的运行时间和解的质量均处于 HJ 和 ES之间，能够在可接受的时间内获得较优解。该项研究结果表明，有效的搜索策略能够提高优化效率、改善解的质量。 美国堪萨斯州立大学 Azadivar 一直致力于仿真优化理论及应用研究，他和 Tompkins 于 1999 年针对具有离散、定性决策变量和模型结构变化的问题提出了一种 GA 和仿真模型自动生成器相结合的仿真优化方法。该方法具有一定的代表性，一般来说，在仿真优化系统中，仿真模型始终保持不变，只需改变输入参数即可，并且输入参数都是定量的，而他们解决的是一个制造系统初期规划问题，即确定购买设备的数量、车间布局形式和采用的工艺路线以及调度规则等，优化算法在每次迭代中产生的解是一组全新的系统配置方案，前一代解对应的仿真模型可能与当前配置方案不一致，因此需要重新构建仿真模型。他们采用了 MODSIM对制造系统进行建模，利用面向对象技术中的封装和延迟绑定技术实现仿真模型的自动创建功能。为了保证优化算法和仿真模型之间的有机集成，基于 GA 的优化器也在 MODSIM中实现。为了实现对各种参数并行优化，GA 采用三段编码方式，依次表示工件的工艺路线、设备类型和车间布局方案。该方法的优点是可以解决离散与定性输入参数问题，并且适合对相似类型的制造系统进行布局规划，同时也存在一定的缺点，优化算法在寻优过程中不可避免会产生重复设计方案，针对每组方案需要重新创建模型并运行仿真，需要耗费大量的计算资源，影响运行效率，因此，该方法缺乏去掉重复方案的有效手段。 2000 年，法国 Cergy 大学的 Fontanili 等人研究了装配线运行管理问题。他们归纳总结了装配线在运行过程中可能存在的决策点，如订单释放优先级、投产批量、工件释放间隔时间和缓冲区容量等，这些决策点之间相互关联、相互影响，是一个典型的组合优化问题。为解决这一问题，他们采用 GA 和商业化仿真软件 WITNESS 开发了一个仿真优化系统，在该系统中利用开发工具 Delphi 编制优化算法程序，并通过 Microsoft OLE 自动化技术实现和仿真模型集成。中GA 采用整数编码，染色体的每个基因代表相邻工件的投产时间间隔。Fontanili 利用该系统对单一产品与混合产品的装配流程进行了研究，以生产周期作为性能评价指标，实验数据表明，通过仿真优化技术，极大地改善了装配线的运行效果。但是，在列举的众多决策点中，该系统只考虑了如何优化工件的投产时间间隔，而没有涵盖对其它运行参数的优化。 日本JGC 公司在意识到仿真优化的重要性后，联合美国西北大学共同研制开发了一个用于解决制造企业设施规划的仿真优化软件。该软件以 JGC 公司实际工程应用需求出发，注重优化策略和仿真结果的统计分析问题。他们采用 Awe Sim 作为仿真建模工具，优化模块使用麻省理工大学的 Wall 开发的遗传算法库（GALib-a），通过 C+语言实现二者的集成及编写统计分析程序，利用 Visual Basic 开发统一用户界面。该系统将仿真优化过程分为三个阶段，首先是基本参数的设置，用户可以通过图形化的界面定义决策变量、目标函数、约束条件以及根据经验知识为系统提供效果相对较好的初始设计方案，除此之外，还可以定义与统计分析相关的参数；其次是备选方案的生成，优化器根据初始条件产生可行解，并根据问题规模的大小及系统运行时间的约束，自动决定是否搜索整个解空间，在该过程中系统数据库存储了所有设计方案及其响应值，评估每个方案之前，先在数据库中检索该方案是否存在，以决定是否对其进行仿真评估，避免浪费计算资源；再次是仿真输出的统计分析，针对随机仿真问题，每个方案需多次运行仿真才能确定最终响应值，该步骤利用改进的统计分析方法来提高分析精度及减少仿真迭代次数。该系统显著提高了仿真优化效率与可操作性，各模块相互统一，同时又保持了一定的独立性，初步具备了 Bowden 等提出的仿真优化的“六域”集成思想。 2004 年，比利时 Facultes 大学 Allaoui 等人利用仿真优化技术研究了具有维修时间约束的混合流水车间调度问题。他们指出，调度问题的复杂性来源于求解算法自身复杂性和生产系统结构、功能复杂性，其根本原因是传统的调度方法不适合解决大规模问题，无法描述生产系统的动态随机性。因此，他们兼顾启发式调度规则、智能优化算法 SA 和模型仿真的优点，建立了一个求解调度问题的仿真优化系统。该系统以 Delphi 为开发环境编写调度规则和 SA 程序，采用仿真器 RAO（Resource-Actions-Operations）构建仿真模型，并考虑了多种随机因素，如设备故障时间、设备维修时间、生产准备时间、工件运送时间等。为了改善初始解的质量，采用启发式调度规则（SPT、LPT 或 EDD）为 SA 产生一个初始解，然后通过 SA 和仿真模型的迭代优化确定最终解。Allaoui 以最大流通时间、平均流通时间、最大延迟时间、平均延迟时间和延迟工件数量为评价指标，研究了不同维修时间比例下仿真优化调度的效果，并将其与 NEH 方法（被认为目前解决混合流水车间调度问题最好的启发式方法）进行了比较分析。实验数据表明，在各项性能指标上，仿真优化调度方法的调度结果均优于 NEH 方法。由此可见，仿真优化方法的优化能力和模型表达能力是任何调度方法无法比拟的。Lacomme等曾经指出仿真优化方法是解决调度问题的最有效方法，它对调度问题的研究具有巨大的推动作用。但是，该系统没有解决随机仿真需要大量迭代次数问题，势必影响系统运行效率。 2005 年，在美国诺斯罗普.格鲁门舰船系统部（NGSS）的支持下，密西西比州立大学的 Greenwood 等人开始了一项仿真优化项目的研究，研究对象是 NGSS 的两个钣金加工车间，研究目标是建立仿真优化决策支持系统（DSS），用以减少仿真建模与系统分析的复杂性。DSS 是涵盖三个关键模块即 DSS 控制器、仿真优化模型（包括仿真模型和优化器）和图形化用户界面的集成系统。其中，DSS 控制器主要用于处理用户、仿真模型、优化器之间进行的数据交换及逻辑推理过程。仿真建模涉及两个车间，其中帕斯卡古拉的钣金车间仿真模型由密西西比州立大学工业工程中心采用Pro Model 构建的，新奥尔良的钣金车间仿真模型由新奥尔良大学仿真设计中采用 QUEST 开发的，他们通过 Active X技术，将仿真模型集成到 DSS 中。优化器的核心算法是 ES，它可以根据车间当前状态及不同性能评价指标自动选取性能较好的调度规则。图形化用户界面负责用户与仿真模型及优化算法的交互，同时也为维护各种生产数据和运行参数提供一个编辑环境。该系统能够进行车间调度及优化系统运行参数，Greenwood 通过两个实例，并以生产周期和延迟时间作为评价指标验证了 DSS 的有效性。但是，该系统的仿真模型通用性差，即使是解决同类型系统的调度问题，也需对模型进行颠覆性修改，此外，决策支持系统一般需要大量的数据以支持其决策过程，而该系统采用 Excel 作为仿真数据库，不利于同其它信息系统进行集成，导致获取生产数据需要耗费大量时间。Ding 等人在欧共体研究计划“网络化企业优化方法研究”项目中，提出了一个解决供应商选择问题的仿真优化方法。该方法包括三个基本模块：基于遗传算法的优化器、仿真器和建模框架。为了实现模块之间的无缝集，所有模块均采用C+语言实现。GA 采用三段编码方式，分别代表供应商、供应产品比例和补给水平，通过遗传操作产生备选方案，建模框架根据每种方案构建仿真模型，由仿真器描述整个供销过程，并以采购成本、运输成本、库存成本和延迟供应惩罚成本之和作为方案评价指标。文中以一个欧洲分销商如何选择分别地处亚洲和欧洲的供应商的问题作为实例对该方法进行了详细描述，实验数据表明，该方法能够较好地解决这类决策问题。但是，自行开发仿真程序需要耗费大量时间，并且建模能力和模型功能均无法达到专业化仿真软件的水平。3.2 国内仿真优化的研究状况 同济大学的陈伟等人以基于进化策略的仿真优化方法为基础，开发了一套可用于优化独立制造岛硬件配置的仿真优化系统，实现非枚举地从所有可能的方案中搜索到最佳的硬件配置方案。该系统的主要组成部分有初始化模块、仿真模块和优化模块。初始化模块负责对数据进行初始化处理，以供仿真模块使用，仿真模块整体嵌入到优化模块中，实现二者无缝集成。为了方便系统功能的扩展和升级，该系统将基础数据和程序进行分离，只需更改原始数据库中的数据及对程序做细微修改，就可以将其应用到类似系统的规划中。但是，由于实际生产系统的复杂性和零件加工的随机不确定性等，自行开发的仿真系统考虑的因素不全面，其建模功能有待扩充，特别是研究关于系统配置的仿真优化问题，要求仿真模型能够根据不同的配置方案自动更新，对建模方法提出了更高的要求。西北工业大学的郑锋等人提出了一个GA和过程仿真相结合的调度规则决策方法，用以实现调度规则的优选。在该方法中，遗传算法采用分段整数编码，各个基因段按先后顺序分别表示工件进入系统的排序规则、工件选择加工设备的规则和加工设备选择工件的规则，每个染色体就是一个调度方案。他们利用扩展 Petri 网对生产过程进行仿真，以获得调度方案的各项性能指标，为了解决多目标问题，采用层次分析法和模糊评判相结合的决策优化方法求取相应的适应值。除此之外，为了提高优化算法的效率，采用主从式并行遗传算法代替传统遗传算法。他们以西北锆管有限责任公司材轧制车间作为实例，采用拖期订单数、总完工时间、系统生产率、平均通过时间和关键设备利用率作为性能评价指标，研究了动态生产环境下仿真优化方法的决策效果。实验结果表明，该方法是有效的，特别是并行 GA 的引入使该方法更符合实际生产需求。但是，由于 Petri 网自身的局限性导致模型可重用性和可扩展性差，随着生产系统内外环境的不断变化，已构建的模型可能变成“废弃模型”，因此不利于展开其它方面的研究，而且 Petri 网不适合解决大规模复杂问题。 南京航空航天大学的郭宇等人对仿真优化平台及其关键技术进行了研究。他们在“六域”集成的仿真优化思想基础上，提出了一个包括界面层，应用层，通信层，数据层和支撑层的五层结构框架，并采用 Visual C+开发了基于虚拟仿真环境的制造系统仿真优化平台。在该平台中应用层是核心层，它包括两个相对独立的模块：虚拟仿真模块和优化控制模块，两者通过数据通信接口实现集成。其中虚拟仿真模块包括资源模板库和建模仿真编辑器，资源模板库提供基本仿真建模对象，建模仿真编辑器实现建模功能及仿真运行的驱动机制；优化控制模块采用基于变尺度遗传算法和增强连续禁忌搜索算法的混合优化算法，用以提高算法的收敛速度。该平台为仿真研究对象提供了一个虚拟环境，增强了可视化效果。但是，对仿真优化进行研究，关键问题之一是如何提高系统的运行效率，在仿真运行过程中应尽量避免采用耗费大量系统资源的三维模型和仿真动画，待仿真优化结束后，将这个最优或近优方案构建的虚拟仿真环境呈现给用户即可。 此外，清华大学的刘民等人开展了并行机调度问题的仿真优化研究，北京理工大学的孙连胜等人将仿真优化技术应用到了柔性制造系统规划中，这些研究了仿真优化的应用范围。四、国内外仿真优化研究现状对比分析国内较早就开展了仿真优化算法的研究，而仿真优化系统的建立起步较晚，目前，虽然已经取得了一些研究成果，但与国外相比差距较大。国外仿真优化技术已在制造系统各个层次得到了应用，针对不同问题开发了各种仿真优化系统，并且出现了多种商业化仿真软件，如 Auto Simulations公司的 Auto Mod、Opt Tek Systems 公司的 Opt Quest 和 Lanner Group 公司的 Optimizer 等；国内由仿真优化软件自身的发展及制造系统现状等，仿真优化技术在实际应用中还存在诸多问题，开发的仿真优化系统在功能上还有待于完善。五、存在的不足及发展趋势5.1实现仿真优化的通用性仿真优化的通用性包括两层含义，一是优化算法的稳健性，二是仿真模型的可重用性和可扩展性。工业应用领域中的问题一般比较复杂，多种类型决策变量并存，如连续、离散决策变量问题，离散决策变量中又存在定量和定性的问题，并且同一领域中不同类型的问题规模大小也不同，因此，要注重仿真优化算法解决问题范围的能力研究。仿真与优化是一个有机整体，在强调优化算法稳健性的同时也应该考虑仿真模型的通用性，否则会出现“单边倒”的现象。就仿真模型而言，应该研究有效的仿真建模方法，提高模型的模块化程度，针对不同问题采用“即插即用”的方式快速构建仿真模型。如仿真优化系统辅助完成制造系统的初期规划后，应能快速、方便地扩展到制造系统运行中，如供应链管理、生产计划和调度、生产运行控制等。否则，仿真优化系统将变成“一次性”或“废弃”的系统，造成资金和资源的浪费。5.2 实现仿真优化的高效性 对仿真优化的高效性研究体现在如何提高优化算法效率、仿真运行效率和仿真评估效率。工程应用领域经常面临着在最短的时间内做出有效的决策的问题，而各种优化算法都存在求解时间和求解质量的矛盾。因此，如何在保证解的质量前提下提高优化算法搜索效率是仿真优化能否推广应用的关键问题。因此，一方面，对具有实际应用价值的优化算法本身进行研究，如确定优化算法最佳的运行参数（目前仍没有好的解决办法）；另一方面探索新的高效优化算法。对仿真而言，不同的仿真软件由于采用的仿真机制不同，其运行效率也不同，并且不同的建模方法及技巧对仿真运行效率也会有影响。如在基于事件驱动的仿真软件中构建生产系统仿真模型时，在保证生产系统运行逻辑准确的前提下，可以利用一个实体表示一批工件，这样可以减少事件发生次数，对于大规模生产问题，能够节省大量的仿真运行成本。除此之外，对于随机仿真问题，每一组方案需要进行多次重复独立实验，其运行时间往往超过优化算法的一次搜索时间，因此，有效的仿真统计分析技术也是未来研究的重点。5.3实现仿真优化的智能化仿真优化的应用目标是为用户提供一个辅助决策支持工具，而实际工程设计问题一般比较复杂，涉及因素较多，完全依靠计算机来进行决策很难考虑周全，随着人工智能技术的发展，将领域知识引入到仿真优化系统中，建立决策支持系统，充分发挥人的创造性和计算机的计算能力，实现人机协同决策功能。除此之外，仿真优化专业性强的特点也要求建立智能决策系统。目前的仿真优化系统要求用户对仿真优化算法和仿真建模工具有较深入的了解，才能够开展工程应用，如各种仿真优化算法存在大量运行参数（GA 的种群规模、交叉率、变异率、遗传数，TS 的状态产生函数、状态接受函数、初温、停止准则等）需要选择，仿真实验也需要设置各种参数，如仿真开始时间、仿真结束时间、仿真迭代次数和“预热”时间等等，任何一项参数的变动对仿真优化结果都会产生影响，如果要求非仿真专业人员来完成这些设置几乎是一件不可能的事，因此如何根据具体问题，利用专家知识系统辅助完成这些工作是一个可行的实现方法。5.4实现仿真优化的集成化仿真优化涉及到的技术方方面面，而国内外学者集中于对仿真优化的单点技术研究，没有从整体上考虑仿真优化的性能，如目前开发的大多数仿真优化系统停留在优化算法设计和仿真模型构建及二者的简单集成上，对于如何根据不同问题选择适当的优化算法，如何利用领域知识提高算法效率等研究很少，势必影响仿真优化在工程领域中的应用和推广，因此按照“六域”集成思想从集成的角度去研究、开发仿真优化系统是重要的发展方向。参考文献：1王凌,张亮,郑大钟.仿真优化研究进展J.控制与决策,2003,18(3): 257-262.2 FuMC.Optimization for simulation:theory vs.practice J.Informs Journal on Computing (S0899-1499), 2002, 14(3): 192-215.3冯允成,邹志红,周泓.离散系统仿真 M.北京:机械工业出版社, 1998.4 Lacksonen T. Empirical comparison of search algorithms for discrete event simulation J. Computer&Industrial Engineering (S0360-8352), 2001, 40(1): 133-148.5Andradottir S. A review of simulation optimization techniques C/ Proc Winter Simulation Conference. Washington: IEEE Computer Society Press, 1998: 151-158. 6Azadivar F. Simulation optimization methodologies C/ Proc Winter Simulation Conference. Phoenix, 1999: 93-100. 7杨湘龙, 王飞, 冯允成. 仿真优化理论与方法综述 J. 计算机仿真, 2000, 17(5): 1-5. 8 何立琴, 魏守水, 李勇健. 离散事件动态系统仿真优化方法综述 J.山东大学学报, 2003, 33(3): 314-319. .