沙丘社区
论文

RAISE：带鲁棒对手实例搜索的LLM自动启发式设计

RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

Fei Liu; Alessio Figalli; Patrick Owen; Nicola Serra
模型推理推理搜索与路径规划

摘要

具有大型语言模型 (LLM) 的自动启发式设计 (AHD) 在发现高质量启发式方法方面取得了显着进展。然而，现有的基于 LLM 的 AHD 方法优化了固定训练实例集的启发式方法，并且在现实世界的分布变化下部署时可能会发生灾难性的失败。我们提出了鲁棒对手实例搜索（RAISE），这是一个框架，它将训练分布的原则邻域内的受约束的最坏情况实例搜索集成到基于 LLM 的进化搜索循环中。 RAISE 将鲁棒 AHD 视为受约束的对抗性实例搜索问题：外循环通过 LLM 算子演化启发式算法，而无 LLM 的内循环使用带有边界投影的基础分布参数化，有效识别训练实例集周围 epsilon 球内的硬实例。跨五个分布系列的在线装箱 (OBP)、在线作业车间调度 (OJSP) 和在线车辆路由 (OVRP) 的综合实验表明，现有的基于 LLM 的 AHD 方法在分布转移下性能下降高达 19 倍，而 RAISE 在所有测试的分布和问题规模上始终保持强劲的性能

RAISE：带鲁棒对手实例搜索的LLM自动启发式设计：论文配图
图 1：RAISE 框架概述：用于启发式设计的 LLM 驱动的外部进化循环，与无 LLM 的内部对抗性实例搜索相结合，可发现围绕标称训练分布的 ε\varepsilon-ball 不确定性集内的最坏情况实例。