基于某仿真地优化方法综述

《基于某仿真地优化方法综述》由会员分享，可在线阅读，更多相关《基于某仿真地优化方法综述（11页珍藏版）》请在装配图网上搜索。

1、word基于仿真的优化方法综述 李东 汪定伟1 引言人们对复杂事物和复杂系统建立数学模型并进展求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化(Simulation Based Optimization，SBO)方法正是在这样的背景下开展起来的。随着优化问题越来越复杂，对优化对象的评价只能通过仿真获得的统计指标来实现。这时，SBO是复杂优化问题的惟一选择。近年来，SBO已成为国际上最热的研究方向。虽然SBO已经在很多领域得到了应用，但是当前对于SBO的理论研究并不完善

2、，算法仍在不断探索和改良中，新的研究成果不断出现。2 SBO的研究概况与分类综观最优化的开展过程，大约经过了以下几个阶段：19401970年数学规划阶段一目标和约束是解析函数。1970-2000年智能优化阶段一目标和约束放宽为含有判断逻辑的计算机程序。2000年一未来基于仿真的优化(SBO)阶段一用大量仿真的统计数据来进展性能评价。有些学者对SBO做了一些综述工作。Andradottir从连续事件和离散事件两个方面，对SBO技术作了总结；Azadivar从单目标优化和多目标优化的角度对SBO方法作了论述；在国内，杨湘龙等认为SBO是非枚举地从可能值中找到最优输入变量值，使得输出结果为最优或满意

3、解的过程。王凌等按照优化方法的不同，对SBO与其改良和应用作了综述。随着对SBO方法研究的深入，SBO在复杂工程系统的设计优化、供给链和物流系统、制造系统与社会经济系统等领域得到了应用。总结当前的研究和应用情况，可以看出，基于仿真的优化是仿真方法和优化方法的结合，是借助仿真手段实现系统的优化的一种优化方法。这里既强调了仿真与优化是互相融合的，又强调了优化是目的，仿真是手段的思想。本文基于这一思想，在计算方法上按照仿真在SBO中所起作用的不同，将SBO分为仿真用于策略验证；将仿真的输出作为优化算法中的适应值一即仿真起到适应值函数的作用；用仿真方法获取优化算法中用解析方法无法得到的参数或函数这3类

4、。以往的综述工作，在分类时往往注重对优化方法的阐述，而无视了仿真在优化中的作用，而本文的分类方式，更能表现SBO方法是仿真与优化相结合的这一特点，更加面向具体应用。3 SBO方法1)仿真用于策略验证在SBO中，将仿真用于策略验证是应用最简单的一种，主要适用于数学模型难以表达、解空间为一组候选的策略集，且解空间不大的问题。此类优化的做法是将候选策略集中的策略逐一输入仿真模型，驱动仿真运行，然后比拟每一组输出结果，根据输出结果来确定最优的策略，如图1所示。图1 仿真用于策略验证流程图Jacobs等将此类方法应用于荷兰航空公司航班计划的制定中，确定当有航班因故延误时，使用何种调整策略。其目标是追求利

5、润的最大。候选策略集为：S=交换两个航班的次序，使用备用飞机，缩短维护时间，取消该航班。候选策略集中只有4种策略，逐一输入到仿真模型中，即可比拟出在不同运营时期，选用哪种策略最好。在这个应用中，候选策略是4个可直接操作的方案。还有的应用中，策略集是由一组启发式方法构成的，仿真用于验证哪种启发式方法好。Takahama等使用基于仿真的优化方法来确定如何为自动化仓储系统分配存储空间，目标是作业数量最少、运输距离最短、库存费用最低。将仓储过程分为两个阶段来仿真，第1阶段是仓库收到货物阶段，其策略集由3种启发式方法构成：Sl=随机选择位置存放货物，将属于一样顾客的货物集中堆放，按离库时间先后存放货物。

6、第2阶段是提取货物，为了提取压在下面的货物，需要将上面的货物移开，针对将上面的货物移动到哪个位置，其策略集由4种启发式方法构成：S2=移到最近的位置，移到最近且离库时间更迟的货物上，综合前两个策略但前者优先于后者，综合前两个策略但后者优先于前者。这里的策略不是可直接操作的方案，而是指导作业如何进展的规如此，依据不同的规如此，会得到不同的仿真结果。经仿真验证，S1中的第2个策略和S2中的第2个策略组合起来是最好的。将仿真应用于策略验证的方法有其局限性，它只能从候选策略集中选出最好的方案，不能主动地寻找最优解。它实际上是通过枚举的方法来比照每个策略的效果，当策略数量较多或是不能显式地表达出策略时，

7、这类方法不适用。相对来讲，其他两类方法的应用X围更广。2)仿真输出适应值在SBO方法中，将仿真的输出作为算法的适应值是当前一个研究热点。这一类方法在解决适应值函数无法表达的优化问题时有明显的优越性。它是将仿真模块嵌入到优化算法中，将仿真模块的输出作为算法的适应值，用于指导优化算法搜索新的解。优化算法产生的新解又作为下一次仿真的输入，直到仿真模型的输出满足终止条件，如图2所示。图2 仿真输出作为优化算法适应值流程图仿真模块可与任意优化算法相结合，当前研究中，将仿真嵌入到GA，SA和PSO的应用较多见。基于仿真的GA GA具有并行搜索、不需要目标函数连续可导等优点，在求解非线性或离散问题时表现出了

8、优越性。动态性、随机性是供给链优化的一个难点，在数学模型中，供给链中的不确定性(如需求波动，运输不稳定性)经常被忽略。SBO被认为是解决这一问题的有效方法。Ding等和Truong等都将仿真模块嵌入到GA中，用于解决供给链的优化问题。GA的染色体编码，如图3所示。图3 染色体编码示意图第1组6位编码表示工厂和分销中心的选址，假如选择该地建立相应设施如此编为1，否如此为0；第2组两位编码为库存策略，分别表示根本存储，(R，Q)，(s，S)等策略；第3组4位编码表示库存的控制参数；第4组3位编码分别表示各工厂加工产品的比例。在这个应用案例中，仿真模块的输出即为GA的适应值，GA输出的解又是仿真模块

9、的输入。通过这种方式，供给链的结构和生产存储策略都得到了优化。除用于供给链外，仿真与GA相结合在其他方面也有应用，Akhtar等用基于仿真的GA求解了火箭的弹道问题。需要注意的是，以仿真模块来获取适应值的计算代价要远大于计算适应值函数，而以上研究没有给出计算所需消耗的时间。Takahashi等使用SBO方法来求解电梯的最优调度方案，同样是使用基于仿真的GA，采取了一些方法缩短了计算时间。基于仿真的SA算法SA算法能概率性地跳出局优解并最终趋于全局最优，在工程中得到广泛应用。在SBO的研究中，将仿真模块与SA相结合的应用也较多。Tamaki等使用基于仿真的SA算法求解一类生产加工问题。其仿真过程

10、为：NF台机器加工NP个产品，产品PK的投入生产时间、交货时间和在机器上的加工顺序，半成品从一台机器移动到另一台机器的工作由吊车完成。其决策变量是：半成品由哪台吊车运输、吊车的作业顺序和吊车运输发生冲突时的避让规如此。其目标为生产时间最短、交付拖期最短，双目标优化。即：式中，tT1m和tT2m名分别为产品m投人生产和生产完成的时间；tpk为产品k实际交付时间；dpk为产品k应交付时间；w1和w2分别为赋予生产时间和交付拖期的权重。优化模块使用模拟退火算法，目标权重取(0.5，0.5)。初始温度TS=100 000，终止温度TF=l，随机生成初始解。按启发式(随机生成运输某产品的起重机编号，在1

11、0内变化某产品的生产顺序，在10内变化当发生冲突时吊车避让的优先级)找一邻近解，如符合本次迭代温度条件如此承受该解，直到达到最低温度。Abdelsalam等使用基于仿真的SA算法求解了怎样缩短产品开发周期的问题，它用SA算法来求取没计结构矩阵中的产品开发行为的最优顺序，用Monte Carlo方法来输出适应值。算法过程从一组初始解开始，如图4所示。图4 一种基于仿真的SA流程示意图数学模块从优化模块接收一组新的解，由仿真模块对这组解进展仿真，得到目标函数的均值。这个值又反应给优化器，供优化模型寻找新的解。基于仿真的SA算法与基于仿真的GA存在同样的问题：即计算代价较高。基于仿真的PSO算法PS

12、O以其在求解实优化问题中表现出的良好性能而得到广泛应用。近两年，基于仿真的PSO开始受到关注。Wisnut等将基于仿真的PSO算法用于帮助机器人查找气体源，Zhang等将PSO与仿真方法结合，求解了建筑资源配置问题。在Wisnut等人的研究中，其仿真模块为：在气味分布函数的情况下，一组机器人被分别赋予初始位置和速度。机器人的位置坐标为输入变量，速度和气味分布函数值都由位置坐标计算。当机器人发现了更好的坐标时，就把它存储在向量Pi中，所有Pi中最好的解，即全局最优，存储在Pg中。每个机器人能够互通信息，都获得气体浓度值，并选择局部浓度最大点的位置。文中进一步把算法应用于动态环境，当环境发生变化(

13、如风速变化等)时，机器人以一定的步长分散开，重新寻找气体源。在PSO模块中，粒子的速度和位置按下式更新：式中，xin和Vin分别为第n次运算中粒子i的位置和速度向量；X为收缩系数，X占，当：时，承受假设，即满足约束条件，于是随机性约束通过仿真得到解决。4 SBO的应用SBO在多个领域得到了应用，并取得令人满意的效果。1)在复杂工程系统的设计优化中的应用仿真方法更适于描述复杂系统，因此，基于仿真的优化方法在复杂工程系统的设计优化中应用也最广泛。Tveit和Fogelhohm应用仿真与进化计算结合的方法来做多阶段蒸汽发动机网络的设计优化，其仿真模型对解的评估的准确性优于以前的工作。Lee等如此研究

14、如何用仿真与计划计算方法结合起来解决航空器中零件和设施的安置优化，将问题归结为一个多目标模型，并用较小的计算量求出了Pareto解集。Wang等用仿真优化的方法进展绿色建设的优化设计，将仿真框架与遗传算法结合，在求解单目标优化问题和无约束多目标优化问题中都取得了满意的效果，并通过搜索绿沟建设优化设计中生活消费和环境的Pareto解验证了算法的有效性。Barbieri和Barbieri如此在消声器的曲面设计中采用了仿真优化的方法，也取得了较好的效果。2)在供给链和物流系统中的应用供给链和物流本身具有的不确定性决定了基于仿真的优化方法是研究它的理想工具。Kochel和Nielande用基于仿真的优

15、化来做供给链中的五级串行库存系统的库存补充的优化，克制了数学建模中需要给出许多假设的缺点，得出了多级库存优化问题的一般性策略。Jung等J贝4从市场需求有较强的不确定性的角度出发，用基于仿真的优化方法求出能满足客户满意度的安全库存水平。Ding等o为一个纺织行业供给链中的网络企业群开发了一个基于仿真的优化应用系统ONE，能协助决策者对供给链网络进展评估、设计和改良。3)在制造系统中的应用许多关于制造系统的研究中使用了基于仿真的优化方法。Arakawa等用基于仿真的优化来考虑非合作型能力约束的作业车间调度问题，算法中参加了局域搜索，减少了计算时间。该方法用于实际系统中，得到了较好的效果。Alla

16、oui和Artiba如此用该方法来考虑设备维修的混合流水车间的调度优化问题。文中使用了一种启发式方法，并通过实例验证了该方法在某些条件下优于NEH启发式方法。Kampf和Kochel研究多项目的生产存储系统的生产批量和顺序的优化问题，系统的复杂性导致很难获得解析解，因此用仿真与遗传算法相结合，得到了最优策略；Zhang和Li建立了离散事件仿真系统模型，与一种启发式方法相结合，用于建筑工程的多项资源竞争活动间的资源优化分配问题，优化了资源流分配。4)在社会经济系统中的应用社会经济系统的优化涵盖内容广泛，描述困难，有些学者尝试用基于仿真的优化方法来研究它。Ermolieva采用基于仿真优化的方法来

17、做包括人口变化、生产消费和福利等多种因素的社会保险系统的策略优化，得到的优化解具有鲁棒性。Adachi和Gupta用基于仿真的优化方法来做长期财务规划中的资产配置和投资策略的优化。Mitchell等人针对悉尼地区包含风能、太阳能等多种可再生能源系统的配置与调度优化问题，采用基于仿真的优化方法。通过仿真，能够描述可再生能源系统的所有主要设计问题。5 SBO方法的难点和开展方向SBO方法虽然已经被认为是一种新的好的优化方法，但对于它的应用还存在着难点，其难点集中表现于计算代价过高。原因如下：仿真一次的计算量往往较大，远大于计算适应值函数。在SBO方法中，如果为种群中每代每个个体都运行一次仿真，其计

18、算代价是非常大的。为了克制系统随机性造成的波动，要进展屡次仿真，造成了计算量的成倍增加。算法进展中，对过去的仿真信息利用不够，导致一样的解可能被屡次仿真，带来了不必要的计算。为了克制以上原因带来的难点，有学者进展了探索和研究。为了减少计算量，使用了扰动函数、并行计算和调整仿真模型3种方法。使用扰动函数既能克制系统的随机性，又不必屡次运行仿真。将适应值函数f(x)，变换为有扰动的函数，即：式中，为随机扰动。设h为已经计算过的点，h与名的距离为d，k为fx的斜率，如此F(h)服从正态分布：式中，2为f(x)的方差。这样，由F(h)可反过来估计出f(z)。扰动函数法利用了历史计算的信息，从而可用一次

19、计算代替屡次仿真的均值，是SBO中克制随机性并减少计算量的一个比拟实用的方法。高度开展的并行计算技术成为缩短SBO计算时间的有力工具，它虽然并未减少计算量，但多机并行使得计算速度大大提高，SBO方法与并行计算技术融合是一个必然的开展趋势。YE等将并行仿真模型应用于港口自动引导小车的调度上，有效地提高了仿真运行的速度。调整仿真模型是指随着仿真次数的增加，系统学习到了更多的知识，利用学到的知识对仿真模型的结构、流程进展调整和简化，使得仿真过程更加合理，用时更短。这种方法虽然依赖于具体问题，应用尚不多见，但不失为减少仿真过程计算量的有效方法；此外，利用问题本身的性质进展推理，猜想好的解，并给出启发式方法也是SBO的一个开展方向。6 结语本文按照仿真模块所起的作用对SBO方法进展了分类，分别对仿真用于策略验证、基于仿真的GA、基于仿真的SA、基于仿真的PSO和仿真用于获取随机参数或函数等方法的实现作了介绍；概括了SBO方法在复杂系统设计优化、供给链和物流系统、制造系统以与社会经济系统等领域的应用情况和应用效果；总结了SBO方法存在的难点与开展方向。从综述可见，SBO方法已受到了广泛关注，并取得了一些研究成果。随着研究的深入，SBO方法必然成为研究复杂、随机系统优化的一种主要工具。(end)11 / 11