用连续空间优化替代传统离散搜索,提升自动算法设计效率。
Latent Heuristic Search: Continuous Optimization for Automated Algorithm Design

- 将程序映射到连续潜空间,通过梯度搜索优化
- 在多个组合优化问题上达到顶尖基线性能
- 适合需要高效生成新算法的研究者使用
将大语言模型(LLM)融入进化框架,开创了自动化启发式发现的新范式。然而,现有方法通常在程序语法的离散空间中搜索,依赖随机采样穿越高度非凸的优化景观。本文提出一种连续启发式发现框架,将优化转移到学习得到的潜在流形上。采用编码器将离散程序映射为连续嵌入,并训练可微分代理模型预测性能,实现基于梯度的搜索。为正则化优化轨迹,使用可逆归一化流将嵌入映射到结构化高斯先验,在其上执行梯度上升。最终优化的潜向量通过学习的映射器转化为软提示,用于条件化冻结的LLM以生成新型可执行启发式。我们在旅行商问题(TSP)、容量受限车辆路径问题(CVRP)、背包问题(KSP)和在线装箱问题(OBP)上评估该方法。实验结果表明,连续潜空间优化在性能上可媲美最先进的离散进化基线,同时为自动化算法设计提供互补的方法论选择。实现代码见: https://github.com/cheikh025/LHS。
原文摘要 · Abstract (English)
The integration of Large Language Models (LLMs) into evolutionary frameworks has established a new paradigm for automated heuristic discovery. Despite their promise, these methods typically search in the discrete space of program syntax, relying on stochastic sampling to navigate a highly non-convex optimization landscape. This work proposes a continuous heuristic discovery framework that shifts optimization to a learned latent manifold. We employ an encoder to map discrete programs into continuous embeddings and train a differentiable surrogate model to predict performance, enabling gradient-based search. To regularize the optimization trajectory, an invertible normalizing flow maps these embeddings to a structured Gaussian prior, where we perform gradient ascent. The resulting optimized latent vectors are projected through a learned mapper into soft prompts, which condition a frozen LLM to synthesize novel executable heuristics. We evaluate the proposed method on the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), the Knapsack Problem (KSP), and Online Bin Packing (OBP). Empirical results demonstrate that continuous latent-space optimization achieves performance competitive with state-of-the-art discrete evolutionary baselines while offering a complementary methodological alternative for automated algorithm design. The implementation code is available at \url{https://github.com/cheikh025/LHS}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。