Skip to content
返回搜索结果

多目标禁忌搜索 (MOTS) — 帕累托最优解的元启发式算法

提出者
Hansen, M. P.; building on Glover (1989) Tabu Search
年份
1997
类型
Metaheuristic multi-objective optimization
类别
Simulation / optimization

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

字号

它有什么作用?

多目标禁忌搜索 (MOTS) 是一种元启发式算法,它扩展了经典的禁忌搜索框架,以同时优化两个或更多相互冲突的目标函数。它不寻求单一最优解,而是旨在逼近帕累托前沿——即一组解决方案,其中任何一个目标都无法在不恶化另一个目标的情况下得到改善——这使得它适用于工程、物流和运筹学中复杂的组合和连续优化问题。

方法背后的直觉

想象一下,您正在探索一个崎岖不平、山谷纵横的景观,但您有几张显示不同地形(每个目标一张)的地图,这些地图相互矛盾。MOTS 通过移动到相邻解决方案来导航这个空间,它维护一个短期记忆列表(禁忌列表)来记录最近访问过的位置以避免循环,并维护一个迄今为止发现的非支配解决方案的档案。周期性地,战略性多样化将搜索推向帕累托前沿的未探索区域,平衡了对有希望区域的利用和全局探索。

历史学

多目标禁忌搜索扩展了 Fred Glover 于 1989 年提出的单目标禁忌搜索。第一个系统的 MOTS 公式——包括帕累托档案和多目标期望准则——由 M. P. Hansen 在 1997 年的 MCDM 会议上提出。随后,Gandibleux、Teghem 等人的工作将变体形式化用于组合问题,此后 MOTS 已应用于调度、物流和工程设计,作为进化多目标算法的有力替代方案。

何时使用

当您面临具有两个或更多冲突目标(例如,成本与质量,时间与风险)且精确方法在计算上不可行时,请使用 MOTS。它在调度、车辆路径、网络设计和投资组合选择问题上表现出色,这些问题的搜索空间对于穷举枚举来说太大。当邻域结构有意义且移动算子可以清晰定义时,优先选择 MOTS 而非纯粹的随机搜索。在以下情况下请勿使用 MOTS:问题只有一个目标(普通禁忌搜索就足够了);当帕累托前沿可以精确枚举时;当梯度信息可用且景观是凸的(此时应使用数学规划);或者当实时决策需要确定性、可重现的输出而没有随机变异时。

局限与注意事项

  • 性能对禁忌列表长度、邻域定义和多样化策略高度敏感——需要仔细的参数调整。
  • 无法保证收敛到真正的帕累托前沿;解决方案质量取决于运行长度和问题结构。
  • 当邻域较大或目标评估成本较高时,每次迭代的计算成本很高。
  • 随着目标数量和档案规模的增加,维护和更新帕累托档案的成本可能会变得很高。
  • 由于禁忌机制的顺序记忆性质,并行实现并非易事。

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

优势

  • 通过禁忌列表避免重新访问最近的解决方案,降低了在复杂景观中循环的风险。
  • 期望准则允许在移动带来显著改进时覆盖禁忌限制,平衡了记忆与灵活性。
  • 不需要梯度信息,使其适用于不可微、离散或黑盒目标函数。
  • 在单次运行中生成整个帕累托前沿的近似值,支持多准则决策。
  • 灵活的邻域和移动算子设计允许针对特定问题进行定制。
  • 多样化机制能够跳出局部最优并更好地覆盖帕累托前沿。

应用

  • 多目标车辆路径和物流调度(同时最小化成本和交货时间)
  • 双目标项目调度:在优先约束下最小化完工时间和资源成本
  • 投资组合优化:平衡多种资产类别的预期收益与风险
  • 网络设计:最小化安装成本同时最大化可靠性或吞吐量
  • 制造过程规划:联合优化周期时间、能源使用和质量指标
  • 环境管理:平衡经济产出与污染或生态影响

使用方式

使用方式

1

用一个或多个起始解决方案(随机生成或启发式构建)初始化搜索。设置一个固定长度 L 的空禁忌列表,并用起始种群中的非支配解决方案初始化帕累托档案。

2

通过应用移动算子(交换、插入、扰动)生成当前解决方案 s 的邻域 N(s)。评估所有邻居解决方案在每个目标函数上的表现,以确定进展的候选者。

3

应用禁忌过滤:排除其定义移动出现在禁忌列表中的邻居,除非它们满足一个期望准则——通常是该邻居支配所有当前档案成员,或至少在一个目标上改进了已知最佳值。这可以防止循环并强制进行探索。

4

选择最佳的非禁忌邻居(或满足期望准则的胜者)作为下一个当前解决方案。如果新解决方案是非支配的,则将其添加到帕累托档案中;删除任何被新条目支配的档案成员。

5

当搜索停滞时应用多样化策略:长期频率记忆识别很少访问的区域;从精英档案解决方案或随机扰动解决方案重新开始,以扩展帕累托前沿的覆盖范围。

6

重复邻域、过滤和档案步骤,直到满足停止准则——通常是最大迭代次数、函数评估次数或已用 CPU 时间。返回帕累托档案作为近似的帕累托最优前沿。

常见陷阱

  • 禁忌列表设置过短会导致循环;设置过长会过度限制搜索并错过好的解决方案——经验校准至关重要。
  • 忽视多样化会导致在帕累托前沿的某个区域过早收敛,产生较差的近似。
  • 当目标数量超过三个时,应用 MOTS 会降低性能,因为档案管理和多样性维护变得计算繁重;对于多目标问题,请考虑基于分解的方法。
  • 使用通用移动算子而没有针对特定问题进行设计,与定制实现相比,会严重限制解决方案质量。
  • 仅报告最终档案而不检查收敛历史可能会掩盖过早停滞。

常见问题

当存在多个目标时,MOTS 如何处理禁忌列表?

禁忌列表存储的是移动(而非解决方案),因此其操作方式与单目标禁忌搜索相同。关键区别在于,非禁忌邻居的选择使用多目标支配或标量化函数,并且期望准则被重新定义,允许禁忌移动,如果由此产生的解决方案不被所有当前档案成员支配。

帕累托档案是什么?它应该有多大?

帕累托档案存储搜索过程中发现的所有非支配解决方案。其最大规模通常是有限制的(例如,100-500 个解决方案),以保持内存和更新成本可控。当档案已满时,通过拥挤距离或基于网格的修剪从过度拥挤的区域移除解决方案,以保持多样性。

MOTS 与 NSGA-II 在多目标问题上如何比较?

NSGA-II 使用基于种群的进化方法,结合交叉和变异,使其在搜索早期更擅长全局探索。MOTS 依赖于邻域移动和记忆,这通常能提供更精细的局部搜索质量。实际上,MOTS 在具有强邻域结构的组合问题上往往表现更好,而 NSGA-II 更广泛地用于连续问题。

通常需要多少次迭代?

没有普遍的规则。常见的做法是预算函数评估次数而非迭代次数——通常根据问题规模进行 10,000 到 100,000 次评估——并进行多次独立运行以评估解决方案质量和帕累托前沿的稳定性。

MOTS 能处理超过两个目标吗?

可以,但随着目标数量超过三个(目标空间中的“维度诅咒”),其有效性会降低。对于四个或更多目标,档案规模会爆炸,多样性维护变得困难;通常更倾向于基于分解或基于指标的方法。

相关方法

参考文献

  1. Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.

    打开出版物文献
    已复制。
  2. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    打开 DOI 文献
    已复制。