[Paper] 随机在多目标局部搜索中比系统性更快

Source: arXiv - 2601.06318v1

概述

本文挑战了多目标局部搜索中长期存在的假设：即对解的邻域进行穷举扫描（系统性探索）总是比随机挑选单个邻居更高效。通过大量实验和全新的理论视角，作者们展示了随机抽样始终优于系统性策略，即使后者采用经典的“最佳改进”或“首次改进”规则。

关键贡献

• 经验性证据表明，在各种多目标基准问题中，随机邻居选择比系统性探索更快。
• 直观的玩具示例分析将随机性的优势与搜索空间中“好”邻居的分布联系起来。
• 统计特征化搜索过程中改进邻居的数量，揭示出可预测的概率分布。
• 理论证明（在温和假设下）随机抽样的期望运行时间低于系统方法，且与使用的改进规则无关。
• 实用指南为算法设计者提供何时在多目标局部搜索流程中倾向使用随机抽样的建议。

方法论

1. 算法设置 – 作者实现了两类多目标局部搜索算法：

   • 系统性：要么 最佳改进（评估整个邻域），要么 首次改进（在第一次改进后停止）。
   • 随机：每次迭代 恰好评估一个随机选择的邻居。
     两个家族都维护一个非支配档案，并反复从中挑选解进行探索。

2. 基准套件 – 包含标准多目标组合优化问题的集合（例如，多目标背包、旅行商和流水车间），其目标数量和邻域规模各不相同。

3. 性能指标 – 达到档案中预定义质量阈值所需的运行时间（CPU 时间），以及所需的评估次数。

4. 统计分析 – 对每次运行，作者记录有多少邻居是“好”的（即导致非支配更新）。他们将这些计数拟合为 类泊松分布，表明找到好邻居的概率低但在搜索过程中保持稳定。

5. 理论建模 – 基于观察到的分布，推导系统性与随机策略的期望运行时间，证明扫描大量邻居的额外开销超过了提前找到更好解的偶然收益。

结果与发现

• 一致的加速：随机抽样在所有测试平台上需要 减少 30‑50 % 的评估次数，并 减少 20‑40 % 的实际运行时间。
• 分布洞察：每个解的改进邻居数量服从 几何分布，成功概率较小（≈ 0.05–0.1）。这使得穷举搜索效率低下。
• 理论验证：系统搜索的期望运行时间随邻域大小线性增长，而随机抽样的期望运行时间仅随成功概率的倒数增长——当邻域很大时，这提供了可证明的优势。

实际意义

• 算法设计：在实现多目标局部搜索（例如用于调度、路径规划或资源分配）时，除非有充分证据表明优秀邻居高度聚集，否则应优先使用随机邻居采样。
• 可扩展性：对于邻域规模巨大的问题（在组合优化中常见），随机采样显著降低 CPU 使用率，从而实现实时或准实时的决策支持。
• 混合策略：研究结果表明可以采用预算感知的混合方法——先使用随机采样快速探索，只有在随机选择的成功率超过某一阈值时才切换到系统化探索。
• 工具支持：现有库（如 jMetal、MOEA Framework）可以提供一个简单的“随机邻居”算子，使开发者无需重新设计整个搜索循环即可进行实验。
• 并行化：随机采样天然支持并行；多个工作线程可以并发评估独立的随机邻居，进一步加速收敛。

限制与未来工作

• 独立邻居质量的假设：理论模型将邻居质量视为独立抽样，这在高度结构化的问题中可能不成立，因为好的邻居往往是相关的。
• 静态成功概率：分析假设改进的概率大致保持不变；但在实际中，随着档案收敛，这一概率可能会下降，从而可能缩小不同策略之间的差距。
• 基准范围：虽然论文涵盖了若干经典组合问题，但并未测试大规模真实场景实例（例如，拥有数千客户的车辆路径问题）。
• 未来方向：将分析扩展到 动态邻域、探索 自适应采样率，并将这些洞见整合到 多目标元启发式算法（如 NSGA‑II、MOEA/D）中，都是有前景的方向。

底线：对于构建多目标局部搜索求解器的开发者来说，简单的随机邻居选择不仅是懒惰的捷径——它在大多数情况下是经证明更快、更具可扩展性的策略。拥抱随机性，你很可能在不牺牲解的质量的前提下，大幅削减运行时间。

作者

• Zimin Liang
• Miqing Li

论文信息

• arXiv ID: 2601.06318v1
• 分类: cs.NE
• 出版日期: 2026年1月9日
• PDF: 下载 PDF