[Paper] 多目标组合优化中随机局部搜索的可变搜索步长

Source: arXiv - 2602.05675v1

Overview

本文介绍了 Variable Stepsize Randomized Local Search (VS‑RLS)，这是一种轻量级但功能强大的算法，用于解决 multi‑objective combinatorial optimization problems (MOCOPs)。通过在搜索过程中动态调整 neighbourhood size，VS‑RLS 在广泛 exploration 与细粒度 exploitation 之间架起了桥梁，提供的性能可与乃至超越 state‑of‑the‑art multi‑objective evolutionary algorithms (MOEAs) 在各种 benchmark problems 上的表现相媲美。

关键贡献

• 动态步长机制： 一个简单的规则，随着时间推移缩小邻域半径，使算法能够先进行全局搜索，随后逐步聚焦于局部细化。
• 算法简洁性： VS‑RLS 只需要一个随机解存档和一个邻域算子；不需要复杂的种群管理或帕累托排序结构。
• 广泛的实证验证： 在多个经典 MOCOP（如多目标背包、旅行商、集合覆盖）基准上，表现出相较于固定步长局部搜索的持续改进，并且与竞争性的 MOEA 相媲美。
• 通用性： 步长调度与问题无关，可最小化代码改动地嵌入现有的随机局部搜索框架中。

方法论

1. 初始化 – 随机抽样一个解并将其存入档案，档案记录迄今为止发现的所有非支配解。
2. 可变步长调度 – 定义一个递减函数 s(t)（例如指数衰减或线性递减），将当前迭代 t 映射到邻域半径。早期迭代使用较大的 s(t)（宽邻域），后期迭代使用较小的 s(t)（紧邻域）。
3. 随机局部移动 – 在每次迭代中：
   • 从档案中均匀挑选一个解。
   • 通过受当前步长 s(t) 限制的特定问题变异生成邻居。
   • 在所有目标上评估该邻居。
   • 若该邻居相对于档案是非支配的，则将其加入（并可选择性地剔除被支配的档案成员）。
4. 终止条件 – 在预设的评估预算用完或步长降至最小阈值时停止。

核心思想类似于模拟退火中的“冷却”，但 VS‑RLS 控制的是移动在解空间中能够到达的距离，而不是控制接受概率的温度。

Source: …

结果与发现

• 收敛速度： VS‑RLS 在大约只有最佳 MOEA 所需评估次数一半的情况下即可达到高质量的帕累托前沿。
• 鲁棒性： 在 30 次独立运行中的性能方差显著低于 MOEA，表明行为更为稳定。
• 可扩展性： 算法的运行时间随决策变量数量线性增长，适用于规模更大的组合实例，而在这些情况下 MOEA 的计算成本会显著提升。

实际意义

• 快速原型开发： 开发者只需几行代码即可将 VS‑RLS 嵌入现有的优化流水线，避免维护大规模种群或复杂选择机制的开销。
• 资源受限环境： 由于 VS‑RLS 只需要一个适度大小的存档和一个简单的邻域算子，它非常适合在边缘设备、嵌入式系统或 CPU/内存预算紧张的云函数上运行。
• 混合优化： VS‑RLS 可以充当 预处理器，快速生成高质量的初始 Pareto 存档供后续的多目标进化算法（MOEA）使用，从而可能降低整体优化时间。
• 行业应用场景： 调度（如作业车间、车辆路径规划）、投资组合选择和网络设计等问题通常涉及离散决策和多目标；VS‑RLS 提供了一种低维护成本、仍能交付竞争性折衷解的替代方案。

限制与未来工作

• 邻域设计依赖性： VS‑RLS 的有效性依赖于拥有明确定义、针对特定问题的邻域算子；如果选择的移动不佳，变量步长的优势可能会被削弱。
• 步长调度调优： 虽然作者提供了通用的衰减函数，但在高度不规则的搜索空间中，最佳调度仍可能需要经验性的调优。
• 理论保证： 论文提供了实证证据，但缺乏对任意多目标组合优化问题（MOCOP）的形式收敛证明或运行时间复杂度界限。
• 未来方向： 将 VS‑RLS 扩展至处理动态目标，融合自适应调度学习（例如基于强化学习的步长控制），以及探索大规模问题的并行档案更新。

作者

• Xuepeng Ren
• Maocai Wang
• Guangming Dai
• Zimin Liang
• Qianrong Liu
• Shengxiang Yang
• Miqing Li

论文信息

• arXiv ID: 2602.05675v1
• 分类: cs.NE
• 发表时间: February 5, 2026
• PDF: 下载 PDF