💻 计算机科学

Redundancy-Triggered Relocation: Decentralized Coordination of Local Searchers for Static and Dynamic Multimodal Optimization

本文提出了冗余触发重定位（Redundancy-Triggered Relocation, RTR），这是一种去中心化的协调机制，其中局部搜索者在有限的感知半径内检测到更优的队友时会自主重启，从而有效地减少了冗余收敛，并在无需中央控制器或特定问题参数调优的情况下，显著提升了在动态多峰优化基准测试上的性能。

原作者： Diego Palma

发布于 2026-11-09

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Diego Palma

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

许多现实世界的问题并不只有一个最佳答案。城市规划师可能需要几条不同的路线来管理交通，或者设计师可能希望为一台机器设计出几种截然不同的配置，每种配置都有其自身的优势。在优化领域——即研究如何寻找最佳解决方案的数学学科中——这一挑战被称为多峰优化（multimodal optimization）。其目标不仅仅是找到可能性景观中的最高峰，而是要定位每一个显著的峰值，无论它们有多少个。当景观本身随时间发生移动和变化时，这项任务会变得更加困难，例如在处理需求波动的物流调度或追踪移动目标等动态环境中。在这些变化的场景中，算法不仅必须找到所有的峰值，还必须在每次变化后重新找到它们。

难点在于这些搜索算法的行为方式。如果任其自流，一群搜索者往往会聚集在单个最具吸引力的峰值上，从而忽略了其他的峰值。为了防止这种情况，研究人员开发了一些方法来让搜索者保持分散，通常是通过强制他们留在不同的组别中，或者通过惩罚那些靠得太近的个体。然而，这些方法通常需要一个中央控制器来监视所有人，或者需要对峰值之间的距离有一个精确的猜测。当环境发生变化，或者搜索者是仅能与邻居通信的物理机器人时，中央控制器就会成为瓶颈甚至变得无法实现。问题依然存在：一群局部搜索者能否在没有指挥官、没有全局地图、且不知道确切存在多少个峰值的情况下，进行有效的协调？

独立研究员迭戈·帕尔玛（Diego Palma）提出了一种名为“冗余触发重定位”（redundancy-triggered relocation）的解决方案。这个想法看似简单：搜索者只有在意识到自己在浪费时间时才应该移动。在这个系统中，每个搜索者只观察其直接相邻的邻居。如果一个搜索者看到附近有一个表现更好且占据着相同领地的队友，它就会得出结论：自己是多余的。与其固执地继续攀爬一个已被更优秀的队友占据的峰值，这个冗余的搜索者会放弃那个位置，并在一个新的随机位置重新开始搜索。这种决策是在局部做出的；搜索者不需要知道系统中其他所有智能体的具体位置，只需要知道其自身有限感知范围内的智能体即可。这使得团队能够实现自我组织，让一个智能体留在每个峰值上，而让多余的智能体去寻找新的峰值，而这一切都不需要中央控制中心。

研究人员使用了一套旨在模拟动态、多峰环境的标准复杂问题测试了这种方法。搜索者配备了强大的局部搜索工具，团队的任务是在景观移动时找到所有的峰值。结果显示，这种“仅在附近存在更优队友时才移动”的简单规则显著提高了团队的表现。在一组二十四个动态问题上，寻找峰值的平均成功率从略高于一半上升到了接近三分之二。这种提升是实质性的，足以使该方法在测试的几种其他动态搜索策略中排名第一。虽然近年来最先进的竞争方案在整体得分上仍略高，但这种新方法在涉及十维锥形结构的特定类型景观中表现出色，在该类景观中找到了测试过的所有方法中最高的平均峰值数量。

至关重要的是，该研究排除了导致这一成功的几种替代解释。收益并非仅仅来自于定期随机移动智能体，也不仅仅来自于在搜索停止改进时才重启搜索。提升专门来自于触发机制：即仅在检测到更优秀的队友时才决定移动。研究还证明，该系统可以容忍信息延迟。即使搜索者使用的是关于队友位置的略微过时的信息，性能依然保持强劲。这表明该方法对于通信可能缓慢或不完美的现实应用场景具有足够的鲁棒性。然而，该方法并非万能良药。当峰值靠得极其近时，它会表现挣扎，在这种情况下，那些显式分析地形形状的更复杂方法表现得更好。它在其他领域使用的、奖励仅寻找单一最高峰的特定指标上也并不出色，因为该方法旨在将其精力均匀地分配到它发现的所有峰值上。

这项研究证实，一群局部搜索者可以在没有中央大脑或全局地图的情况下进行有效的协调。通过依靠一个简单的局部规则——只有当你被邻居超越时才移动——团队避免了多个智能体追逐同一个目标的浪费。这种方法提供了一种轻量级、去中心化的方式来解决复杂的动态问题，证明了有时最有效的协作仅仅是知道何时退位，让别人去完成工作。

问题陈述
动态多峰优化要求算法能够随着目标函数随时间的变化，反复定位多个全局最优解。该领域的一个主要挑战在于如何高效地分配计算预算：如果没有干预，局部搜索器往往会收敛到同一个吸引盆地（basin of attraction），从而浪费资源并错失其他最优解。现有的解决方案，如小生境方法（niching methods）和多种群策略，通常依赖于全局信息、聚类或中央控制器来管理子种群。在分布式设置中（例如机器人或独立的模拟工作单元无法维持对所有队友的实时全局视图时），这些方法可能会产生高昂的计算成本或难以实现。

方法论：冗余触发重定位 (RTR)
本文提出了冗余触发重定位（Redundancy-Triggered Relocation, RTR），这是一种用于局部搜索器团队的去中心化协调规则。其核心机制如下：

局部感知： 每个搜索器 $i$ 仅感知特定感知半径 $v_i$ 范围内的队友。
冗余条件： 如果搜索器感知到一个队友 $j$ 满足以下条件，则被视为冗余： $j$ 比 $i$ 更优（ $f_j > f_i$ ）且位于排除半径 $r_{ex}$ 之内，前提是 $j$ 也在 $i$ 的感知半径内（ $\|x_j - x_i\| \le v_i$ ）。
动作： 若判定为冗余，搜索器立即重定位到一个新点（通常是感知到的队友之外的 $k$ 个随机点中最远的点），并使用全新的步长重启其局部优化器（CMA-ES 或 (1+1)-ES）。若非冗余，则保留当前的盆地。
去中心化： 决策完全基于局部信息（附近队友的位置和适应度值）异步做出。不需要全局聚类、中央控制器，也不需要针对特定问题的最优解数量估计。
可选组件： 评估的配置包括两个附加组件：(1) 通过模仿成功的队友来调整感知半径；(2) 特定的目的地选择策略（最远点）。随后的消融实验表明，这些组件对于核心性能增益并非必不可少。

核心贡献

RTR 规则： 一种轻量级的协调机制，搜索器仅在感知到更优的队友占据了其附近的盆地时才会进行重定位。这使得团队能够实现自我组织，形成“持有者”（精炼最优解）和“侦察兵”（探索新区域），而无需显式的子种群数量参数。
排除机制的理论分析： 本文通过形式化分析（命题 1）证明，全局排除会对团队在静止状态下能持有的最优解数量施加硬性上限，该上限由排除半径处的填充数（packing number）决定。相反，有限的感知放宽了这一限制，允许距离比全局排除半径更近的独特最优解被同时持有，只要较弱持有者的感知半径小于两者之间的距离。
严谨的评估与消融研究： 研究将“触发器”（因冗余而重定位）与其他因素（如重定位频率或基于收敛的重启）进行了分离。通过使用预设的标准和控制变量，证明了性能提升特指源于冗余触发机制和较小的有效排除半径，而非随机重定位或标准的收敛重启。

结果

CEC 2022 动态多峰测试集： 在组织者提供的实例上，采用 CMA-ES 搜索器的 RTR 将平均峰值比率从 0.503（无重定位的独立搜索器）提高到了 0.628。在去掉两个可选组件后，得分提升至 0.640。RTR 在测试的动态基准算法（mQSO, HmSO, DE）中排名第一，并超越了 2022–2024 年间发表的三篇竞赛论文。然而，在整体平均性能方面，它落后于排名前三的论文（DAEA, AMLP-RS-CMSA-ESII, CMA-ES-DS），但在 10 维锥形地形（cone landscapes）上取得了最高的平均值。
CEC 2013 小生境测试集： 与不进行重定位的搜索器相比，RTR 将平均峰值比率从 0.736 提高到了 0.777。它在组合函数（5–20 维）上的表现具有竞争力，接近已发表的最佳结果，但在具有许多紧密排列最优解的低维问题（如 Shubert 函数）上，其表现落后于专门的小生境方法。
移动峰值基准测试（Moving Peaks Benchmark）： 正如预期，RTR 在离线误差（offline error，奖励追踪单个最高峰值的指标）方面并不突出，因为该方法将精力均匀分布在所有持有的峰值上。然而，研究表明重定位是至关重要的，与不进行重定位的搜索器相比，它显著降低了离线误差。
消融与控制实验：
- 触发 vs. 随机： 以与 RTR 相同的频率进行随机重定位会导致性能大幅下降（平均峰值比率为 0.217），证实了触发机制才是增益的来源。
- 收敛 vs. 冗余： 仅在收敛或停滞时进行重启（不含冗余触发）的效果并不比从不重定位更好。
- 感知半径： 全局排除（全感知）触及了理论极限，且在处理具有紧密排列最优解的问题时表现较差。为了避免错误的冗余判定，必须使用有限的感知（或固定的微小半径）。
- 延迟信息： 当队友信息延迟高达一个完整周期时，该规则依然保持稳健。

意义与主张
本文声称，RTR 为静态和动态多峰优化提供了一种有效且轻量级的方案，用于协调局部搜索器，且无需聚类、中央控制或针对最优解数量的问题特定参数调优。其主要贡献在于证明了：一种简单的去中心化规则——即仅在感知到附近存在更优队友时进行重定位——可以显著提升相对于独立搜索器和标准基准算法的性能。

作者也谦虚地承认了局限性：RTR 并非为优先考虑单个最佳峰值的离线误差指标而设计，并且在最优解极其接近的情况下表现挣扎，在这种场景下，显式的盆地检测方法（如 HillVallEA）仍然更具优势。研究结论认为，RTR 的益处在于特定的触发机制以及使用较小的有效排除半径，这使得团队能够动态且局部地调整其探索与开发（exploration-exploitation）之间的平衡。

类似论文