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

word基于仿真的优化方法综述 李东 汪定伟1 引言人们对复杂事物和复杂系统建立数学模型并进展求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用基于仿真的优化(Simulation Based Optimization，SBO)方法正是在这样的背景下开展起来的随着优化问题越来越复杂，对优化对象的评价只能通过仿真获得的统计指标来实现这时，SBO是复杂优化问题的惟一选择近年来，SBO已成为国际上最热的研究方向虽然SBO已经在很多领域得到了应用，但是当前对于SBO的理论研究并不完善，算法仍在不断探索和改良中，新的研究成果不断出现2 SBO的研究概况与分类综观最优化的开展过程，大约经过了以下几个阶段：①1940～1970年数学规划阶段一目标和约束是解析函数②1970-2000年智能优化阶段一目标和约束放宽为含有判断逻辑的计算机程序③2000年一未来基于仿真的优化(SBO)阶段一用大量仿真的统计数据来进展性能评价有些学者对SBO做了一些综述工作Andradottir从连续事件和离散事件两个方面，对SBO技术作了总结；Azadivar从单目标优化和多目标优化的角度对SBO方法作了论述；在国内，杨湘龙等认为SBO是非枚举地从可能值中找到最优输入变量值，使得输出结果为最优或满意解的过程。

王凌等按照优化方法的不同，对SBO与其改良和应用作了综述随着对SBO方法研究的深入，SBO在复杂工程系统的设计优化、供给链和物流系统、制造系统与社会经济系统等领域得到了应用总结当前的研究和应用情况，可以看出，基于仿真的优化是仿真方法和优化方法的结合，是借助仿真手段实现系统的优化的一种优化方法这里既强调了仿真与优化是互相融合的，又强调了优化是目的，仿真是手段的思想本文基于这一思想，在计算方法上按照仿真在SBO中所起作用的不同，将SBO分为仿真用于策略验证；将仿真的输出作为优化算法中的适应值一即仿真起到适应值函数的作用；用仿真方法获取优化算法中用解析方法无法得到的参数或函数这3类以往的综述工作，在分类时往往注重对优化方法的阐述，而无视了仿真在优化中的作用，而本文的分类方式，更能表现SBO方法是仿真与优化相结合的这一特点，更加面向具体应用3 SBO方法1)仿真用于策略验证在SBO中，将仿真用于策略验证是应用最简单的一种，主要适用于数学模型难以表达、解空间为一组候选的策略集，且解空间不大的问题此类优化的做法是将候选策略集中的策略逐一输入仿真模型，驱动仿真运行，然后比拟每一组输出结果，根据输出结果来确定最优的策略，如图1所示。

图1 仿真用于策略验证流程图Jacobs等将此类方法应用于荷兰航空公司航班计划的制定中，确定当有航班因故延误时，使用何种调整策略其目标是追求利润的最大候选策略集为：S={交换两个航班的次序，使用备用飞机，缩短维护时间，取消该航班}候选策略集中只有4种策略，逐一输入到仿真模型中，即可比拟出在不同运营时期，选用哪种策略最好在这个应用中，候选策略是4个可直接操作的方案还有的应用中，策略集是由一组启发式方法构成的，仿真用于验证哪种启发式方法好Takahama等使用基于仿真的优化方法来确定如何为自动化仓储系统分配存储空间，目标是作业数量最少、运输距离最短、库存费用最低将仓储过程分为两个阶段来仿真，第1阶段是仓库收到货物阶段，其策略集由3种启发式方法构成：Sl={随机选择位置存放货物，将属于一样顾客的货物集中堆放，按离库时间先后存放货物}第2阶段是提取货物，为了提取压在下面的货物，需要将上面的货物移开，针对将上面的货物移动到哪个位置，其策略集由4种启发式方法构成：S2={移到最近的位置，移到最近且离库时间更迟的货物上，综合前两个策略但前者优先于后者，综合前两个策略但后者优先于前者}这里的策略不是可直接操作的方案，而是指导作业如何进展的规如此，依据不同的规如此，会得到不同的仿真结果。

经仿真验证，S1中的第2个策略和S2中的第2个策略组合起来是最好的将仿真应用于策略验证的方法有其局限性，它只能从候选策略集中选出最好的方案，不能主动地寻找最优解它实际上是通过枚举的方法来比照每个策略的效果，当策略数量较多或是不能显式地表达出策略时，这类方法不适用相对来讲，其他两类方法的应用X围更广2)仿真输出适应值在SBO方法中，将仿真的输出作为算法的适应值是当前一个研究热点这一类方法在解决适应值函数无法表达的优化问题时有明显的优越性它是将仿真模块嵌入到优化算法中，将仿真模块的输出作为算法的适应值，用于指导优化算法搜索新的解优化算法产生的新解又作为下一次仿真的输入，直到仿真模型的输出满足终止条件，如图2所示图2 仿真输出作为优化算法适应值流程图仿真模块可与任意优化算法相结合，当前研究中，将仿真嵌入到GA，SA和PSO的应用较多见①基于仿真的GA GA具有并行搜索、不需要目标函数连续可导等优点，在求解非线性或离散问题时表现出了优越性动态性、随机性是供给链优化的一个难点，在数学模型中，供给链中的不确定性(如需求波动，运输不稳定性)经常被忽略SBO被认为是解决这一问题的有效方法Ding等和Truong等都将仿真模块嵌入到GA中，用于解决供给链的优化问题。

GA的染色体编码，如图3所示图3 染色体编码示意图第1组6位编码表示工厂和分销中心的选址，假如选择该地建立相应设施如此编为1，否如此为0；第2组两位编码为库存策略，分别表示根本存储，(R，Q)，(s，S)等策略；第3组4位编码表示库存的控制参数；第4组3位编码分别表示各工厂加工产品的比例在这个应用案例中，仿真模块的输出即为GA的适应值，GA输出的解又是仿真模块的输入通过这种方式，供给链的结构和生产存储策略都得到了优化除用于供给链外，仿真与GA相结合在其他方面也有应用，Akhtar等用基于仿真的GA求解了火箭的弹道问题需要注意的是，以仿真模块来获取适应值的计算代价要远大于计算适应值函数，而以上研究没有给出计算所需消耗的时间Takahashi等使用SBO方法来求解电梯的最优调度方案，同样是使用基于仿真的GA，采取了一些方法缩短了计算时间②基于仿真的SA算法SA算法能概率性地跳出局优解并最终趋于全局最优，在工程中得到广泛应用在SBO的研究中，将仿真模块与SA相结合的应用也较多Tamaki等使用基于仿真的SA算法求解一类生产加工问题其仿真过程为：NF台机器加工NP个产品，产品PK的投入生产时间、交货时间和在机器上的加工顺序，半成品从一台机器移动到另一台机器的工作由吊车完成。

其决策变量是：半成品由哪台吊车运输、吊车的作业顺序和吊车运输发生冲突时的避让规如此其目标为生产时间最短、交付拖期最短，双目标优化即：式中，tT1m和tT2m名分别为产品m投人生产和生产完成的时间；tpk为产品k实际交付时间；dpk为产品k应交付时间；w1和w2分别为赋予生产时间和交付拖期的权重优化模块使用模拟退火算法，目标权重取(0.5，0.5)初始温度TS=100 000，终止温度TF=l，随机生成初始解按启发式(随机生成运输某产品的起重机编号，在±10内变化某产品的生产顺序，在±10内变化当发生冲突时吊车避让的优先级)找一邻近解，如符合本次迭代温度条件如此承受该解，直到达到最低温度Abdelsalam等使用基于仿真的SA算法求解了怎样缩短产品开发周期的问题，它用SA算法来求取没计结构矩阵中的产品开发行为的最优顺序，用Monte Carlo方法来输出适应值算法过程从一组初始解开始，如图4所示图4 一种基于仿真的SA流程示意图数学模块从优化模块接收一组新的解，由仿真模块对这组解进展仿真，得到目标函数的均值这个值又反应给优化器，供优化模型寻找新的解基于仿真的SA算法与基于仿真的GA存在同样的问题：即计算代价较高。

③基于仿真的PSO算法PSO以其在求解实优化问题中表现出的良好性能而得到广泛应用近两年，基于仿真的PSO开始受到关注Wisnut等将基于仿真的PSO算法用于帮助机器人查找气体源，Zhang等将PSO与仿真方法结合，求解了建筑资源配置问题在Wisnut等人的研究中，其仿真模块为：在气味分布函数的情况下，一组机器人被分别赋予初始位置和速度机器人的位置坐标为输入变量，速度和气味分布函数值都由位置坐标计算当机器人发现了更好的坐标时，就把它存储在向量Pi中，所有Pi中最好的解，即全局最优，存储在Pg中每个机器人能够互通信息，都获得气体浓度值，并选择局部浓度最大点的位置文中进一步把算法应用于动态环境，当环境发生变化(如风速变化等)时，机器人以一定的步长分散开，重新寻找气体源在PSO模块中，粒子的速度和位置按下式更新：式中，xin和Vin分别为第n次运算中粒子i的位置和速度向量；X为收缩系数，X<1；c1和c2分别为向全局最优解和个体最优解的学习参数这个例子是根据气体浓度信息搜索二维平面中的一个点，其搜索过程与PSO中粒子寻优过程有很大的相似之处，因此，使用基于仿真的PSO算法是很巧妙的构思这里的一个机器人既可以是仿真模块中的一个Agent，又可以是PSO中的一个粒子，实现了仿真与PSO的完美结合。

④其他SBO方法除了上述几种方法外，也有学者对其他一些SBO方法进展了研究Olafsson等针对可行域有限但巨大，且带有随机性的问题，提出了一种基于仿真的嵌入式分区(Nested Partitions)方法其将可行域划分为假如干个子区域，将随机目标函数看作是离散事件的仿真过程，从各子区域中抽取样本输入仿真模块，由仿真输出的期望判断出最有可能找到最优解的子区域，对该子区域继续进展划分，直到找出最优解这为求解随机性优化问题提供了一种可供参考的方法也有学者使用嵌入了优化器的仿真软件来求解优化问题，OptQuest是一种嵌入了TS和GA的优化器，它能够根据用户输入的目标自动搜寻最优解，它可以嵌入到多种仿真软件中Law等使用嵌入了OptQuest的Witness仿真软件求解了一类加工流程中，工作站内机器数量的配置问题其优点是使用方便，但在处理解空间巨大的问题时存在明显的局限性Truong等在使用SBO方法来优化供给链的结构和各种决策时，将决策变量分为两局部，对选址、生产和服务分配等适于用整数表达的变量，归到一个混合整数规划模型中，将定性性质的、易用染色体编码表达的决策变量，归到GA中求解两种方法互相补充，变量共同输入到仿真模型中，并通过实验说明，这样混合起来的算法具有更好的性能。

这些研究同样为SBO方法的开展提供了可供借鉴和参考的途径3)仿真获取随机参数或函数仿真是描述随机性问题的有效方法，这已成为共识因此对于带有随机性的优化问题，用仿真方法求取其中的随机参数或带有随机变量的函数受到了广泛关注与前面所述的仿真输出适应值的方法不同之处在于，不必对整个问题的流程进展仿真，而只对所需的参数或函数涉与到的局部仿真即可，其仿真结果也不是用于评价解的优劣，而是为优化模块提供必要的随机参数或函数的信息，使优化方法能运行下去，如图5所示图5 仿真获取随机参数或函数示意图①为SA状态承受提供参数Talal等考虑一类目标函数是随机离散的，需要通过MonteCarlo法估计优化的问题，即：式中，S为解空间；w叫为随机数文中用SA算法进展求解，假设Zk为第后代计算搜索到的解，Xk为第k代的当前解，如此SA算法中，按下式确定是否承受新解：式中，Uk服从[0，1]区。