arXiv:2509.02297cs.AI2025-09

LLM能自动生成3D装箱问题的启发式算法,但受限于脆弱性和预训练偏见。

Re-evaluating LLM-based Heuristic Search: A Case Study on the 3D Packing Problem

  • 用约束骨架和迭代自修正提升LLM生成代码的稳定性
  • LLM主要优化评分函数,对搜索空间探索有限
  • 结果与人工设计算法相当,适合集成到现有求解框架

启发式设计传统上依赖人工。尽管大语言模型(LLMs)可生成搜索启发式代码,但其应用多限于调整人类构建框架中的简单函数,其在更广泛创新中的潜力尚不明确。为探究此问题,我们让一个LLM独立构建求解约束3D装箱问题的完整求解器。直接代码生成很快显现出脆弱性,因此引入两项支持:约束骨架(预先编写的约束检查代码)和迭代自修正(额外的纠错循环以修复漏洞并生成可行初始种群)。值得注意的是,在贪婪过程中庞大的搜索空间中,LLM几乎全部精力集中在优化评分函数上。这表明,先前研究中对评分函数的侧重可能并非原则性策略,而是当前LLM能力的自然局限。最终生成的启发式算法与人工设计的贪心算法相当;当其评分函数被整合进人工构建的元启发式算法时,性能媲美成熟求解器,但在约束收紧时表现下降。研究揭示了当前LLM在自动化启发式设计中的两大障碍:复杂推理任务中缓解其脆弱性所需工程投入,以及预训练偏差的影响,会过早缩小新颖解的搜索范围。

原文摘要 · Abstract (English)

The art of heuristic design has traditionally been a human pursuit. While Large Language Models (LLMs) can generate code for search heuristics, their application has largely been confined to adjusting simple functions within human-crafted frameworks, leaving their capacity for broader innovation an open question. To investigate this, we tasked an LLM with building a complete solver for the constrained 3D Packing Problem. Direct code generation quickly proved fragile, prompting us to introduce two supports: constraint scaffolding--prewritten constraint-checking code--and iterative self-correction--additional refinement cycles to repair bugs and produce a viable initial population. Notably, even within a vast search space in a greedy process, the LLM concentrated its efforts almost exclusively on refining the scoring function. This suggests that the emphasis on scoring functions in prior work may reflect not a principled strategy, but rather a natural limitation of LLM capabilities. The resulting heuristic was comparable to a human-designed greedy algorithm, and when its scoring function was integrated into a human-crafted metaheuristic, its performance rivaled established solvers, though its effectiveness waned as constraints tightened. Our findings highlight two major barriers to automated heuristic design with current LLMs: the engineering required to mitigate their fragility in complex reasoning tasks, and the influence of pretrained biases, which can prematurely narrow the search for novel solutions.

启发式搜索大模型应用3D装箱代码生成

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。