用对抗样本搜索提升大模型设计启发式算法的鲁棒性
RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search
- 将大模型进化搜索与约束对抗实例生成结合，动态发现难例
- 在五类分布下测试，现有方法性能下降最高达19倍，RAISE保持稳定
- 适合需要高鲁棒性的在线优化任务，如调度、打包、路径规划
基于大语言模型（LLM）的自动化启发式设计（AHD）在发现高质量启发式策略方面取得显著进展。然而，现有方法仅针对固定训练实例集优化，在真实世界分布偏移下可能彻底失效。本文提出鲁棒对抗实例搜索框架（RAISE），将约束最坏情况实例搜索融入基于LLM的进化搜索循环中。RAISE将鲁棒AHD建模为约束对抗实例搜索问题：外层通过LLM操作符进化启发式，内层无需LLM，利用基分布参数化与边界投影，在训练分布邻域的epsilon球内高效识别困难实例。在在线装箱（OBP）、在线作业车间调度（OJSP）和在线车辆路径（OVRP）任务上，跨五类分布家族的综合实验表明，现有方法在分布偏移下性能最高下降19倍，而RAISE始终在所有测试分布和问题规模下保持强性能。
原文摘要 · Abstract (English)
Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics for a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。