Skip to content
返回搜索结果

多目标模拟退火 (MOSA)

提出者
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
年份
1992–1998
类型
Metaheuristic / Pareto-based optimizer
类别
Simulation / optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

多目标模拟退火 (MOSA) 将经典的模拟退火元启发式方法扩展到具有两个或多个相互冲突的目标函数的问题上。MOSA 不会收敛到单一的最优解,而是通过随机探索解空间,并维护一个非支配(帕累托最优)解的存档,从而为决策者提供一个多样化的权衡前沿,而不是一个预设的答案。

方法背后的直觉

经典的模拟退火模仿了金属的可控冷却过程,以逃离局部最优解——在高温下偶尔接受较差的解,然后随着温度下降变得更具选择性。MOSA 同时将这种概率逃逸机制应用于多个目标。当一个候选解在某些目标上变差但在其他目标上有所改善时,支配关系逻辑决定了它是否能进入帕累托存档。冷却进度表逐渐降低随机性,将搜索聚焦在帕累托前沿附近。其结果是得到了真实的帕累托前沿的近似值,而无需梯度信息或凸性假设。

历史学

模拟退火由 Kirkpatrick 等人于 1983 年引入。Serafini (1992) 最早正式提出将其扩展到多目标问题。Czyzak 和 Jaszkiewicz (1998) 开发了帕累托模拟退火 (PSA),它将帕累托存档确立为核心输出结构,并提供了当今广泛采用的接受准则公式。此后,MOSA 被应用于工程设计、调度和物流领域。

何时使用

当你面临一个具有两个或多个相互冲突的目标以及连续或组合决策变量的优化问题时,特别是当目标函数景观是非凸的、多峰的或无梯度的,可以使用 MOSA。它非常适合调度、路由、工程设计和资源分配问题,在这些问题中,明确的权衡前沿比单一加权聚合更有用。当问题只有一个目标(经典 SA 就足够了)、必须精确找到帕累托前沿(对于小问题,精确算法更好)、目标数量超过大约五个(超体积指标方法扩展性更好)或目标函数每次评估的成本极高(优先考虑基于代理的模型)时,请勿使用 MOSA。

局限与注意事项

  • 帕累托前沿的解质量和覆盖范围对初始温度、冷却率和邻域算子的选择敏感,需要针对具体问题进行调整。
  • 收敛到高质量的帕累托前沿可能需要大量的目标函数评估,对于昂贵的黑盒模拟来说速度很慢。
  • 维护和更新帕累托存档会带来额外开销,并且存档可能会变大,增加内存和比较成本。
  • 与基于种群的方法(例如 NSGA-II)不同,基本 MOSA 的单轨迹性质可能导致帕累托前沿覆盖不均匀。
  • 理论上的收敛保证需要无限慢的冷却进度表,这是不切实际的;有限的进度表会牺牲最优性保证。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 不需要梯度信息,并且可以处理非凸、不连续和多峰的目标函数景观。
  • 对较差解的概率性接受允许逃离纯粹贪婪方法所陷入的局部帕累托前沿。
  • 在单次运行中产生完整帕累托前沿的多样化近似,为决策者提供明确的权衡选项。
  • 实现简单,并且冷却进度表提供了一个直观的参数来调整探索-利用平衡。
  • 适用于连续和组合优化问题,只需少量重构。

应用

  • 多目标作业车间和流水车间调度(同时最小化完工时间和延迟时间)
  • 具有成本和可靠性目标的网络设计和路由问题
  • 工程设计优化(例如,最小化结构组件的重量和应力)
  • 平衡预期回报和风险的投资组合优化
  • 具有竞争性经济和环境目标的土地利用和空间规划
  • 平衡成本、覆盖范围和服务质量的医疗资源分配

使用方式

使用方式

1

生成一个初始解(随机或启发式),设置一个足够高的初始温度 T_0 以允许广泛探索,用找到的任何非支配解初始化帕累托存档,并定义停止标准(最大迭代次数或最低温度阈值)。

2

使用适合问题结构的邻域算子(例如,对于连续变量的交换、插入或高斯扰动)扰动当前解,以产生一个或多个候选邻域解。

3

评估候选邻域的所有目标函数。确定它相对于当前解和帕累托存档中的解是支配、被支配还是非支配。将非支配候选解添加到存档中;移除被支配的存档成员。

4

应用多目标接受准则。如果邻域解相对于当前解是非支配的,则接受它。如果它是被支配的,它仍可能以概率 P = exp(−ΔF / T) 被接受,其中 ΔF 聚合了目标函数恶化程度,从而允许逃离局部帕累托前沿。

公式
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

根据冷却进度表降低温度,通常是几何衰减:T_{k+1} = α · T_k,其中 α ∈ (0.8, 0.99)。较低的温度会缩小对较差移动的接受范围,从而逐步加强在帕累托前沿有希望的区域附近的搜索。

公式
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

将最终的帕累托存档作为结果返回。进行后处理以剔除可能累积的被支配解,并将存档呈现为帕累托最优前沿的离散近似,供决策者选择。

常见陷阱

  • 将初始温度 T_0 设置得太低会导致过早收敛到帕累托前沿的局部区域;始终校准 T_0,使初始接受率约为 70-90%。
  • 使用接近 1.0 的冷却率 α 会使运行时间过长;使用接近 0 的冷却率会导致在帕累托前沿被充分探索之前就快速收敛。
  • 使用朴素的目标函数差值之和来定义接受概率的 ΔF 会混合不可比较的尺度——在聚合之前对每个目标进行归一化。
  • 未能定期从存档中移除被支配的解会膨胀存档并降低最终输出的质量。
  • 基于单次运行评估成功与否具有误导性,因为存在随机变异;务必对多次独立运行的结果进行聚合。

常见问题

MOSA 与 NSGA-II 有何不同?

NSGA-II 是一种基于种群的进化算法,它使用交叉、变异和非支配排序同时演化一组解。MOSA 是一种基于轨迹的方法,它使用概率移动一次探索一个解。MOSA 通常更容易实现,并且适用于组合问题,而 NSGA-II 通常能为连续问题提供更好的帕累托前沿覆盖,并且具有更可预测的可扩展性。

我应该如何设置初始温度 T_0?

一种常见的启发式方法是进行一个简短的预备阶段,并选择 T_0,使得大约 80% 的随机邻域移动被接受。这确保了开始时的广泛探索。由于合适的温度尺度取决于目标函数差值的量级,因此建议进行特定于问题的校准。

MOSA 能处理两个以上的目标吗?

是的,但随着目标数量的增加,性能会下降。帕累托存档的管理成本会增加,非支配解的比例会迅速增长,使得接受准则的区分度降低。对于具有四个或五个以上目标的问题,通常更倾向于使用基于超体积指标或基于分解的方法(例如 MOEA/D)。

我如何知道何时停止算法?

常见的停止标准包括达到最低温度、耗尽最大迭代次数预算或在指定迭代次数内观察到帕累托存档的超体积指标没有改善。在实践中,比较不同迭代次数预算下多次运行的存档质量是诊断收敛性的可靠方法。

MOSA 是否适用于昂贵的模拟模型?

通常不适用于未经修改的 MOSA。每次迭代至少需要一次目标函数评估,而 MOSA 通常需要数千次迭代才能获得良好的帕累托前沿近似。当每次评估都涉及昂贵的模拟时,MOSA 的基于代理的变体(使用元模型来近似目标函数)是更可取的。

相关方法

参考文献

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    打开 DOI 文献
    已复制。
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

    打开出版物文献
    已复制。