论文拾萃|禁忌搜索在随机仿真优化应用中的最优预算分配策略

前言

今天向大家推荐并介绍一篇文章，这篇文章解决的是禁忌搜索算法应用在仿真优化问题时所面临的预算分配问题。文章的作者为同济大学机械与能源工程学院的余春龙助理教授，蒙特利尔大学数学与工业工程学院的Nadia Lahrichi教授，以及米兰理工大学机械工程学院的Andrea Matta教授。

1

研究背景

禁忌搜索（TS）是广泛使用的算法框架，被用于解决诸多领域中的组合优化问题，如制造、交通、医疗和能源等。当TS用于求解仿真优化问题(Simulation Optimization)时，解的质量通常通过一个随机仿真模型进行评估。在此情况下，一个解所对应的目标函数值是一个随机变量而非确定值，难以准确地评估其质量。因此，TS在进行邻域搜索时，它所选择的局部最优解可能并非真实的局部最优解，从而导致搜索无法朝着正确的方向进行。受到“仿真噪声”的影响，TS在仿真优化问题中的应用面临两个问题：(1)迭代过程中搜索方向上的偏差导致最优解不在搜索的范围内；（2）目标函数评估的偏差导致搜索范围内的最优解没有被正确地识别。

在该研究中，“预算”表示可供解的评估使用的仿真样本的数量。仿真噪声可以通过增加预算得到改善，但会增加仿真的时间和成本，在许多实际应用场景中（如车间的实时调度与控制）预算通常是有限制的。因此，TS在仿真优化问题中的应用面临着利用-探索的两难问题，即分配更多的预算用于一个解的评估从而提高评估精度，还是分配更多的预算用于探索更广的解空间？在TS中，预算分配问题可以分为两个层级，第一个层级是为每一轮搜索迭代分配预算，第二个层级是在单次迭代过程中为邻域解分配预算。本研究聚焦于后者，即：给定单次TS迭代的总预算，通过优化对邻域解的预算分配，以最大限度地降低仿真噪声造成的错误邻域移动概率，最终提高TS的效率。

该研究为TS提出了渐进式最优预算分配策略。在现有文献中，预算的分配多遵循平均分配原则或简单的分配规则，这些规则并非最优。该研究首次将排序与选择(R&S)的概念无缝地集成到TS中，基于大偏差理论，对预算分配的渐近最优性提供了理论结果。此外，研究提出了最优预算分配的解析式形式，使最优策略能更容易地应用到实际问题中，并提供了一种顺序分配程序，便于在预算分配的过程中更好地收集相关参数的后验信息。

2

问题描述

2.1

仿真优化

仿真优化问题可以表示如下

其中

是搜索空间，

是仿真的输出结果Y（x）的数学期望。一般来说，y（x）可以用n次仿真结果的平均值来估计，即

。 则n的值越大，估计的结果就越准确。文章引入了以下常见假设：

1） 搜索空间的所有仿真结果的方差有限，样本仿真结果之间相互独立并且分布；

2） 仿真结果

符合正态分布。

2.2

禁忌搜索

此处介绍本文使用的禁忌搜索算法的流程，首先介绍以下符号

文章中描述的禁忌搜索算法流程如下：

其中T 表示禁忌表。

2.3

预算分配问题

定义

为禁忌搜索在第t轮迭代时的状态，并定义m为一次禁忌搜索迭代过程，即

这一过程。前文讲过，由于仿真存在的误差，禁忌搜索实际采纳的邻域移动和实际正确的移动存在偏差，用

表示正确的邻域移动，用

表示实际采纳的移动，该实际移动是基于样本均值

作出的，其中

代表仿真过程的随机性。采纳了实际正确的移动概率为：

这个式子的含义是，当仿真的结果为

时，TS作出实际正确移动的概率。

在文章关注的问题里，一次迭代提供的预算为n ，则预算分配问题可以定义如下：

其中

是取样比例，也就是用于第i 个邻域解的评估的样本数量为

。

需要注意的是，我们求解预算分配问题获得最优解，并不意味着我们求得了仿真优化问题的最优解。由于元启发式方法的特性，禁忌搜索算法本身并不保证能够找到问题的最优解。文章解决的是在禁忌搜索过程中的预算分配问题，使得禁忌搜索算法能够尽可能朝着正确的迭代方向进行迭代。

3

仿真预算分配

在一轮迭代中，禁忌搜索迭代有两种情况，一种是邻域解中没有比已知最优解更好的，我们称为 Best-holding 。另一种则更新已知最优解为当前领域解中的最优解，我们称为 Best-improving。如果我们的迭代过程没有出现偏差，则在 Best-Holding 的情况下有

，其中

是邻域解中的非禁忌最优解。在Best-Improving 的情况下，应该作出迭代

，其中

为邻域解中的最优解。

在 Best-Holding 的场景中，我们的迭代可能出现以下几种偏差：

在 Best-Improving 的场景中，我们的迭代可能出现以下几种偏差：

作出错误迭代的概率标记为PFM，在 Best-Holding 的场景下，表达如下：

且PCM=1-PFM。

求解预算分配问题的主要难点在于并不存在解析式。文章基于大偏差理论，提出了解决上述预算分配问题的代理模型。通过证明该代理模型为连续凸优化模型，进一步采用KKT条件求解，获得了渐进最优预算分配，从而使得禁忌搜索能够作出正确的迭代。

由于篇幅有限，此处只介绍文章提出的分配方法的具体的结论和分配程序，详细的推导过程推荐大家阅读论文原文。

在 Best-Holding 的场景中，文章有以下结论：

这种分配方式能够尽可能均衡地降低三种错误移动的概率。

在 Best-Improving 的场景中，文章有以下结论：

在这种场景下的预算分配问题，实际上和传统的 R&S 问题类似，因此可以通过Chen 等人(2000) 提出的OCBA方法进行求解。

总的来说，整个预算分配的过程如下：

4

实验结果

4.1

单次迭代中的预算分配问题

文章提出的分配策略与平均分配的策略(EA)相比结果如下：

(a)-(d)分别代表不同的场景。TSOCBA代表上文中的Algorithm2的策略， TSOCBA(p1)和TSOCBA类似，但是场景固定为Best-Holding并且用上述Proposition 1作为分配的策略。TSOCBA(p2)则将场景固定为Best-Improving并且用上述 Proposition 2 作为分配的策略。显然，在单次迭代中的预算分配问题上，文章提出的分配策略具有较快的收敛速度。

4.2

禁忌搜索结合TSOCBA

将文章提出的TSOCBA与Chen等人(2000)提出的传统OCBA进行比较。在（s，S）库存问题中，由 TSOCBA 引导的TS比用 OCBA 引导的TS更容易识别出最优解。在复杂的医生排班问题中，与OCBA相比，TSOCBA引导的 TS 可以到达搜索空间中更有潜力的区域，获得的解与最优解的差距更小。此外，在许多算例中，TSOCBA相对于OCBA的优势随着模拟噪声水平的增加而增加。下面给出医生排班问题中的比较结果：

通过对比可以看到文章提出的策略不管是在性能上还是稳定性上，而且TSOCBA 的算法性能的稳定性更高。

4.3

与 OptQuest 比较

OptQuest 是知名度比较高的仿真优化求解器，文章采用提出的 TSOCBA 引导的 TS 与该求解器进行比较。采用的场景是生产线吞吐量最大化问题与医生排班问题，比较的结果如下图：

从图中以可发现，在这两个问题上，与该求解器相比，文章提出的策略有更好的表现。

文章信息

题目：Optimal budget allocation policy for tabu search in stochastic simulation optimization.

作者 ：Chunlong Yu 作者 ：Nadia Lahrichi 作者 ：Andrea Matta

期刊 ：Computers & Operations Research

DOI：10.1016/j.cor.2022.106046

引用：Yu, C., Lahrichi, N., & Matta, A. (2023). Optimal budget allocation policy for tabu search in stochastic simulation optimization. Computers & Operations Research, 150, 106046.

https://doi.org/10.1016/j.cor.2022.106046