通过两阶段结构演化拓展大模型搜索空间,提升启发式算法自动设计效率。
Breaking Validity-Induced Boundaries to Expand Algorithm Search Space: A Two-Stage AST-Based Operator for LLM-Driven Automated Heuristic Evolution
- 先对代码的抽象语法树进行变异交叉,生成多样但无效的结构变体
- 再用大模型修复无效代码,提升优化性能与收敛速度
- 适合需要高效探索新算法结构的研究者
基于大语言模型(LLM)的自动化启发式设计(AHD)在发现高效启发式算法方面展现出巨大潜力。现有主流方法依赖于仅基于预训练知识的语义演化算子,采用端到端生成方式,严格要求生成代码在操作过程中始终有效,常依赖“思维-代码”表示。本文认为这种设计从根本上限制了算法搜索空间的探索能力。为此,我们提出一种两阶段、基于结构的演化算子。第一阶段直接对启发式代码的抽象语法树(AST)执行交叉与变异,有意生成多样化但通常无效的结构变体;第二阶段利用大模型将这些无效代码修复为可执行的高质量代码。根据底层框架,可将原始无效变体或修复后的代码纳入种群,以保留潜在的结构模式。实验表明,该算子显著提升了当前先进方法EoH-S的搜索能力。在旅行商问题(TSP)和在线装箱问题(OBP)上的结果均显示,本方法有效提升了优化性能与收敛速度。
原文摘要 · Abstract (English)
Large Language Model (LLM) based automated heuristic design (AHD) has shown great potential in discovering efficient heuristics. Most existing LLM-AHD frameworks use semantic evolutionary operators that rely entirely on the LLM's pre-trained knowledge. These one-stage methods strictly require the generated code to be valid during the operation and often rely on a ``thought-code'' representation. We argue that this end-to-end generation fundamentally limits the exploration ability within the algorithm search space. In this paper, we propose a two-stage, structure-based evolutionary operator for LLM-AHD. In the first stage, our approach directly performs crossover and mutation on the Abstract Syntax Trees (ASTs) of the heuristic code, intentionally generating diverse but often invalid structural variants. In the second stage, the LLM is employed to repair these invalid heuristics into executable, high-quality code. Depending on the underlying framework, either the raw invalid variants or the repaired heuristics are integrated into the population to preserve potential structural patterns. We demonstrate that the proposed operator can significantly enhance the search ability of state-of-the-art LLM-AHD algorithms, such as EoH-S. Experimental results on the Traveling Salesman Problem (TSP) and the Online Bin Packing Problem (OBP) show that our method effectively improves both optimization performance and convergence speed.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。