用动态协同进化让启发式算法自适应搜索阶段,提升复杂优化性能。
DyACE: Dynamic Algorithm Co-evolution for Online Automated Heuristic Design with Large Language Model
- 构建基于滚动时域控制的动态协同演化框架,实时调整启发式逻辑。
- 在三个组合优化任务中超越现有静态方法,高维空间表现更优。
- 依赖真实搜索轨迹感知,避免盲目调整,适合复杂动态优化场景。
当前自动启发式设计普遍假设单一固定算法可应对组合搜索的动态变化,但对扰动启发式而言,逃逸局部最优的最优算法高度依赖搜索阶段。为此,我们将启发式设计重构为非平稳双层控制问题,提出 DyACE(动态算法协同演化)。与传统开环求解器不同,DyACE 采用滚动时域控制架构,持续协同演化启发式逻辑与解群体。核心是前瞻滚动搜索,通过查询搜索空间几何结构提取搜索轨迹特征,提供感知反馈,使大语言模型(LLM)成为具备实际依据的元控制器,根据实时搜索状态生成阶段特定干预策略。我们在三个典型组合优化基准上验证了 DyACE,结果表明其显著优于当前最先进的静态基线,在高维搜索空间中展现出更强可扩展性。消融实验进一步证实,若缺乏基于真实环境的感知,动态适应反而可能劣于静态算法,说明 DyACE 的有效性源于所生成逻辑与优化景观真实梯度之间的因果对齐。
原文摘要 · Abstract (English)
The prevailing paradigm in Automated Heuristic Design (AHD) typically relies on the assumption that a single, fixed algorithm can effectively navigate the shifting dynamics of a combinatorial search. This static approach often proves inadequate for Perturbative Heuristics, where the optimal algorithm for escaping local optima depends heavily on the specific search phase. To address this limitation, we reformulate heuristic design as a Non-stationary Bi-level Control problem and introduce DyACE (Dynamic Algorithm Co-evolution). Distinct from standard open-loop solvers, DyACE use a Receding Horizon Control architecture to continuously co-evolve the heuristic logic alongside the solution population. A core element of this framework is the Look-Ahead Rollout Search, which queries the landscape geometry to extract Search Trajectory Features. This sensory feedback allows the Large Language Model (LLM) to function as a grounded meta-controller, prescribing phase-specific interventions tailored to the real-time search status. We validate DyACE on three representative combinatorial optimization benchmarks. The results demonstrate that our method significantly outperforms state-of-the-art static baselines, exhibiting superior scalability in high-dimensional search spaces. Furthermore, ablation studies confirm that dynamic adaptation fails without grounded perception, often performing worse than static algorithms. This indicates that DyACE's effectiveness stems from the causal alignment between the synthesized logic and the verified gradients of the optimization landscape.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。