2.4　基于仿真的优化方法

由于混流装配线生产计划优化问题的复杂性，很难用一个精确的解析模型来进行描述分析。而通过对仿真模型的运行收集数据，就能够对实际生产计划优化系统进行性能、状态方面的分析，从而能够对系统采用合适的控制优化方法。因而可以在研究动态环境下基于纯仿真模型的混流装配线生产计划优化问题，设计基于纯仿真模型的混流装配线生产计划优化方法，即在一个较短的时间段内用仿真来评价一个分派规则集，选取最小代价的规则，以适应系统状态的变化。基于纯仿真法虽然可以包含解析模型无法描述的因素，并且可以提供给使用者一个优化性能测试的机会，但其不可避免地存在以下问题。

（1）缺乏理论意义。

（2）应用仿真进行生产计划进行优化的费用很高。

（3）仿真的准确性很大程度受编程人员的判断和技巧的限制。

仿真优化研究是基于仿真的目标优化问题，在混流装配线生产计划优化问题中同样可以使用基于仿真的优化方法，其原理如图2-7所示，即基于模型仿真给出的输入/输出关系（性能）通过优化算法得到最佳的输入量。混流装配线生产计划优化问题可以利用仿真优化方法进行模拟求解。仿真优化的特点可归纳如下。

（1）系统的输入/输出关系缺少结构信息，不存在解析表达式，仅能通过仿真得到。

（2）存在不确定因素，一次仿真仅给出对应某一输入的一次性能估计，通常存在误差。

（3）系统仿真过程较费时，且缺少与优化模块的合理接口，以致整个优化过程很慢。

（4）输入变量空间大，且连续量、离散量和逻辑量共存，优化涉及多目标，并存在多极小，以致难以高效地实现全局优化。

鉴于仿真优化的工程背景和上述难点，它一直是不同领域理论和工程人员共同关注的重要课题，尤其在仿真、运筹学和DEDS领域。随着计算机技术、人工智能和数学分析方法的发展，仿真优化的研究取得了一定进展，而仿真优化算法在混流装配线生产计划优化问题中可归纳为基于梯度的方法、随机优化方法、响应曲面法和统计方法4类及这些方法的混合，如图2-8所示。下面对它们进行简单介绍。

2.4.1　基于梯度的方法

在混流装配线生产计划优化问题中，将梯度策略集成进入邻域搜索算法的研究较少，但可以从特征信息状态变换角度对多阶段混流生产过程进行数学建模，将优化问题转化为状态空间中的路径规划问题，集成梯度搜索策略进入该领域的优化搜索算法，形成一套基于梯度求解的多阶段混流生产过程问题的特征状态模型、分析与控制方法。基于梯度的方法通过估计性能指标的梯度来判定改进性能的方向，进而将混流装配线生产计划优化问题转化为基于确定的数学规划方法进行求解。它主要包括有限差分估计法、似然比估计法、摄动分析法和频域实验法，其应用依赖于梯度估计的可靠性和高效性。

（1）有限差分估计法：最原始的梯度估计方法，实现对梯度的估计需要多次重复仿真，运行成本大。

（2）似然比估计法：分析系统样本路径的概率测度对随机变量分布函数的依赖关系，通过测度变换获得似然比来构造性能测度的估计量。它仅需一次仿真即可获得梯度估计，适用于瞬态和再生仿真优化问题。

（3）摄动分析法：通过跟踪系统的样本路径，分析参数摄动对系统性能的影响，进而获得样本性能对参数的梯度，并作为系统性能梯度的估计量。它通过一次运行估计即可得到所有目标函数的偏梯度，因此计算效率高，但基于无穷小摄动分析得到的估计通常有偏差且不一致。

（4）频域实验法：在一次长仿真运行中的不同频率上对选定的输入参数进行正弦振荡，然后对输出变量值进行谱分析。若输出量对输入量敏感，则参数的正弦振荡将导致响应的相应振荡。以此来发现影响最大的输入参数，从而得到梯度的最大方向，但该方法必须解决振荡指数、频率和幅度的确定问题。

2.4.2　随机优化方法

基于最优化的方法，如动态规划法与分析定界法等，大多数是建立在对优化目标的枚举上，因此只能解决小规模的混流装配线生产计划优化问题，距离实用还有较大距离。大多数混流装配线生产计划优化问题属于一类NP困难组合问题，寻找具有多项式复杂性的最优算法几乎是不可能的；但因其解的最优性具有随机性、局部优越性，所以可以通过随机优化方法对混流装配线生产计划优化问题进行求解，再结合其他优化方法得到全局最优解。

随机优化法的典型算法是1979年Azadivar在其博士论文中提出的SAMOPT算法。这种算法是以统计学的随机逼近理论为基础的，之后有学者将这一理论应用于有约束及无约束系统的仿真优化方面，并做了大量的理论工作。而随后有研究人员在解决了几个使随机逼近原理实用化的问题后，发展了SAMOPT算法，并将SAMOPT算法与响应曲面法进行了比较全面的试验比较。结果表明，对于所有的测试问题，SAMOPT算法都比响应曲面法得到了更好的结果，并节省了大量运行时间。

随机优化方法解决了混流装配线生产计划优化问题中目标函数不解析但可估计的优化问题，通常是基于梯度估计的迭代算法，也包括随机逼近方法。在混流装配线生产计划优化问题中的随机优化方法在目标函数平坦时收敛慢，目标函数陡峭时会发散，而且缺少合理的终止准则且难以处理约束，最近有些改进的方法在某些假设条件下可以保证算法的收敛性。此外，在混流装配线生产计划优化问题中的样本路径法通过产生相对很多的样本，用对应的均值函数近似为期望值函数，再利用确定的非线性规划方法对均值函数进行优化。通过介入统计的方法解决了传统随机逼近方法的一些弱点，并提高了效率。

2.4.3　响应曲面法

混流装配线生产计划优化问题的响应曲面法是指在分析目标特征状态空间的数学模型基础上，将其过程映射到优化状态空间中进行研究，通过分析该问题的目标函数在优化空间中的解曲面特点，利用特征状态方程快速地获得目标函数梯度的分析方法，从而有效地指导算法搜索过程，为解决像混流装配线生产计划优化问题这类的大规模组合优化问题提供了一种新的解决思路。

仿真优化的响应曲面法主要是通过仿真设计及仿真结果的回归分析建立系统的响应曲面，再利用数学规划的一些方法进行优化研究，响应曲面法的工作流程如图2-9所示。

这种方法近年来得到了许多学者的研究，并发展了适用于多目标仿真优化的多响应曲面法。其主要思想是通过仿真估计系统的响应面F(x)，在估计出F(x)的近似表达式后，仿真优化问题就变为一个数学规划问题，这时数学规划的所有方法均可使用。为了估计F(x)的近似表达式，通常在仿真结果的基础上使用回归分析（主要为线性回归和二次回归）或样条近似。同时，使用仿真设计技术指导仿真运行，在线性回归时，一般使用一阶正交单纯性设计；在二次回归时，使用中心组合设计；而样条近似则多使用2k设计、2k-p设计及正交设计。

响应曲面法给定初始试验设计点，分别对这些点进行仿真运行来产生相应的输出响应，通过应用一阶回归模型将这些响应拟合为响应曲面，进而用最陡下降法在响应曲面的最大梯度方向对回归函数进行优化来得到最优解，然后再以该点作为中心使用更高阶的回归模型进一步做试验，得到新的试验点，如此重复直到终止条件满足。该方法是试验设计和数理统计相结合的优化方法，相对于一般的梯度估计方法而言，该方法所需的仿真次数较少。

2.4.4　统计方法

为了解决混流装配线生产计划优化方法的收敛速度慢的问题、最优解判断问题、计算时间复杂性问题，可以从基于统计的方法进行研究。统计方法主要包括重点抽样法、排序与选择法、多重比较法和序优化方法。

（1）重点抽样法。重点抽样法的原理是在不同概率测度下进行仿真来增加涉及稀少事件的典型样本路径的概率，对于各仿真路径通过对被估计测度乘上相关因子则可得到原系统的无偏测度估计。如何提出对稀少事件测度的合理改变是该方法面临的主要问题。

（2）排序与选择法。对于那些对所有方案的关系有所了解的问题，排序与选择法将其作为多指标决策问题来处理。当决策涉及选择最佳方案时，使用indifference区域排序技术；当涉及选择包括最佳方案的子集时，则采用子集选择技术，而在每种情况下，决策应保证与预先假定的概率一致。

（3）多重比较法。多重比较法是选择方案有限时排序与选择法的一种替代，它必须提供所有要检验的可替代方案的有关相对性能。

（4）序优化方法。序优化方法的基本思想是：序比值更容易确定，放松优化目标可使问题求解更容易。序优化不过分强调得到精确的最优解，而是以一定期望概率以较少计算量通过“序”的评价得到足够好的解，一般具有指数收敛速度。因此，对于大量缺少结构信息而搜索空间巨大的不确定性优化问题，序优化在保证一定质量的基础上加速了优化过程、减少了计算量。此外，还有神经网络、模糊逻辑及其他方法。