昂贵优化问题介绍

问题的定义

在许多优化任务中，算法每产生一个候选解，都要调用一次高保真仿真、训练完整模型或进行实体实验。若一次评估需要数小时、数天或昂贵实验资源，即使优化算法本身运行很快，可完成的真实评估次数仍然很少。昂贵优化（expensive optimization）讨论的正是如何在有限评估预算下有效搜索。

以单目标最小化为例，问题可写为：

$$\begin{aligned} \min_{\mathbf{x} \in \mathcal{X}}\quad & f(\mathbf{x}) \\ \text{s.t.}\quad & g_i(\mathbf{x}) \le 0, \quad i=1,\ldots,p, \\ & h_j(\mathbf{x}) = 0, \quad j=1,\ldots,q. \end{aligned}$$

其中，$\mathbf{x}$ 是决策变量，$f$ 是目标函数，$g_i$ 和 $h_j$ 是约束函数。昂贵之处可以来自目标函数、约束函数，或两者的评估。若第 $k$ 次评估的成本为 $c_k$，可用总预算为 $B$，则实际搜索还要满足：

$$\sum_{k=1}^{N} c_k \le B,$$

这里 $N$ 是预算内可完成的真实评估次数。成本既可以用计算时间、实验次数或经费表示，也可以用这些资源的组合表示。

什么会让一次评估变得昂贵

• 高保真数值仿真：如复杂流体、结构、电磁或气候模型。计算精度较高，但网格、求解器和长时间尺度会带来较大计算开销。
• 实体实验与测试：如材料合成、风洞测试或硬件测量。单次实验可能耗时、耗材，且准备和测量过程也占用预算。
• 完整模型训练或系统评测：若每组参数都要从头训练深度模型，或在大型系统上跑完整工作负载，单次候选解的成本可能远高于搜索算法本身。

因此，“昂贵”没有统一的绝对阈值，关键是真实评估成本相对于可用预算和搜索需求是否构成瓶颈。这类问题常是黑箱问题，意味着无法直接取得目标函数的解析式或梯度；但黑箱和昂贵并非同义词，函数也可能已知公式却计算代价很高。

昂贵优化与其他优化问题的区别

昂贵优化描述的是评估资源受限这一计算场景；多目标优化描述的是同时存在多个目标及其权衡；高维优化则描述的是决策变量数量较多。它们是不同维度的问题特征，可以分别出现，也可以叠加。例如，一个结构设计任务可以同时具有高保真仿真昂贵、多目标和高维的特点。

评估预算有限时，常规群体算法若每代都对大量个体调用真实模型，可能很快耗尽预算。因而方法设计除了考虑“搜索如何前进”，还要回答“下一次昂贵评估应花在哪里”。

典型求解思路

用代理模型近似真实函数

代理模型（surrogate model）或响应面（response surface）根据已完成的真实评估，拟合一个计算便宜的近似函数 $\hat f(\mathbf{x})$。优化器可以先在 $\hat f$ 上筛选和比较大量候选解，再将少量有价值的候选点交给真实模型评估。

只追逐代理模型预测值最低的点，容易反复利用模型已经掌握的区域，却忽略预测误差较大的区域。因此，代理辅助算法通常会综合考虑预测表现与不确定性或潜在信息价值，在开发已知优良区域和探索未知区域之间作取舍。Jones、Schonlau 与 Welch 提出的高效全局优化（Efficient Global Optimization, EGO）是这一思路的经典方法之一：它用 Kriging 模型及期望改进准则安排后续评估。

常用的两类代理模型可分别参见径向基函数（RBF）和 Kriging。

其他节省评估预算的方法

代理模型不是唯一选择，常见策略还包括：

• 多保真评估：先用成本较低、精度较低的模型筛查候选解，再对有潜力的点使用高保真模型；需要处理不同保真度之间的偏差。
• 利用已有知识：用物理规律、解析近似或历史数据缩小搜索范围、构造初始设计，或辅助近似模型；前提是这些知识确实适用于当前任务。
• 并行批量评估：若实验或仿真可以并行执行，可一次选择多个候选点评估，以减少墙钟时间；这并不会自动减少总计算量。
• 有预算意识的直接搜索：减少每轮真实评估数量，并清楚记录已用预算、剩余预算和停止条件。若问题有可利用的梯度或结构，也可优先使用相应信息，避免把预算花在无必要的黑箱查询上。

一个典型的代理辅助流程

1. 在可行域内选择一批初始点，调用真实目标与约束函数并记录结果。
2. 根据已有数据拟合或更新代理模型，并检查它在当前数据范围内的预测误差。
3. 依据预测值、不确定性、可行性和评估成本选择下一个候选点或一批候选点。
4. 调用真实函数评估所选点，将新数据并入样本集，再更新代理模型。
5. 当评估预算耗尽、达到预设停止条件，或继续搜索的收益不足时停止，并以真实评估结果报告最终解。

代理模型是筛选与决策工具，不是最终结果的替代品。尤其在约束边界、样本稀疏区或模型外推区域，预测误差可能改变候选点排序，所以最终解及其约束满足情况应由真实评估确认。

方法选择时要关注的边界

• 样本少时，模型误差会直接影响搜索方向。 初始设计和采样策略需要覆盖关键区域，不能只依据代理模型的漂亮拟合图判断其可靠性。
• 噪声会改变“最好点”的可信度。 若同一决策的实验结果有随机波动，应考虑重复测量、噪声建模或稳健的比较方法，并在报告中说明重复评估如何计入预算。
• 维度增加会提高建模难度。 经典高斯过程等模型在高维、大样本或复杂离散空间里未必合适，代理形式与变量编码应结合问题规模选择。
• 预算应按真实调用统计。 初始样本、失败评估、约束调用、重复实验和最终验证都可能消耗资源；比较算法时应统一统计口径。

昂贵优化的重点不是一味减少评估次数，而是在明确的资源预算内，让每次真实评估提供尽可能多的搜索价值，同时保留对模型误差和最终结果的核验。

参考资料

• Jones, D. R., Schonlau, M., & Welch, W. J. (1998). Efficient Global Optimization of Expensive Black-Box Functions. Journal of Global Optimization, 13, 455–492.
• Jin, Y. (2011). Surrogate-assisted evolutionary computation: Recent advances and future challenges. Swarm and Evolutionary Computation, 1(2), 61–70.