LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm

📄 arXiv: 2509.09707v1 📥 PDF

作者: Camilo Chacón Sartori, Martín Isla Pino, Pedro Pinacho-Davidson, Christian Blum

分类: cs.NE, cs.AI, cs.CL

发布日期: 2025-09-05

备注: Submitted to a journal for review

💡 一句话要点

提出基于LLM的实例驱动启发式偏置BRKGA算法，解决NP难的最长运行子序列问题。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 元启发式算法 组合优化 启发式偏置 遗传算法

📋 核心要点

  1. 现有方法在利用LLM优化组合问题时，常忽略问题实例的结构特性，导致优化效果受限。
  2. 提出一种人-LLM协作框架，LLM分析实例特征，生成启发式偏置，引导BRKGA算法搜索。
  3. 实验表明，该方法在复杂实例上显著优于标准BRKGA，验证了LLM驱动的启发式偏置的有效性。

📝 摘要（中文）

本文提出了一种新颖的框架，将大型语言模型（LLM）集成到元启发式算法中，以解决复杂的组合优化问题。该方法利用LLM与偏置随机密钥遗传算法（BRKGA）相结合，解决NP难的最长运行子序列问题。通过引入人-LLM协作过程，共同设计和实现一组计算高效的度量，扩展了实例驱动的启发式偏置范式。LLM分析这些特定于实例的度量，生成定制的启发式偏置，引导BRKGA搜索有希望的区域。实验评估表明，最佳混合模型BRKGA+Llama-4-Maverick在最复杂的实例上，相比标准BRKGA基线，取得了显著的统计改进。研究结果证实，利用LLM生成先验的、实例驱动的启发式偏置，是增强复杂优化领域元启发式算法的一种有价值的方法。

🔬 方法详解

问题定义：论文旨在解决NP难的最长运行子序列（Longest Run Subsequence）问题。现有方法在利用LLM时，通常侧重于生成代码或优化特定启发式算法，而忽略了不同问题实例的结构差异，导致算法在面对复杂实例时性能下降。

核心思路：论文的核心思路是利用LLM分析特定问题实例的特征，生成实例驱动的启发式偏置。该偏置能够引导BRKGA算法优先搜索更有希望的区域，从而提高算法的效率和性能。这种方法的核心在于将LLM的推理能力与元启发式算法的搜索能力相结合。

技术框架：整体框架包含以下几个主要阶段：1) 人-LLM协作设计实例特征度量；2) LLM分析实例特征，生成启发式偏置；3) 将启发式偏置融入BRKGA算法中，引导搜索过程；4) 评估算法性能。其中，人-LLM协作过程旨在设计出能够有效捕捉实例特征的度量，LLM则负责根据这些度量生成合适的启发式偏置。

关键创新：论文的关键创新在于提出了基于LLM的实例驱动启发式偏置方法。与现有方法相比，该方法能够根据不同问题实例的特点，动态调整搜索策略，从而更好地适应复杂优化问题。此外，人-LLM协作过程也为启发式算法的设计提供了一种新的思路。

关键设计：论文的关键设计包括：1) 设计了一系列计算高效的实例特征度量，用于描述最长运行子序列问题的不同方面；2) 利用LLM（Llama-4-Maverick）分析这些度量，生成启发式偏置；3) 将启发式偏置融入BRKGA算法的密钥向量初始化和交叉算子中，从而影响算法的搜索方向。具体的参数设置和损失函数等细节未在摘要中详细描述，属于未知信息。

🖼️ 关键图片

img_0

📊 实验亮点

实验结果表明，基于Llama-4-Maverick的BRKGA+Llama-4-Maverick算法在最复杂的实例上，相比标准BRKGA基线，取得了显著的统计改进。这表明利用LLM生成实例驱动的启发式偏置能够有效提高元启发式算法的性能。具体的性能提升幅度未在摘要中给出，属于未知信息。

🎯 应用场景

该研究成果可应用于各种组合优化问题，例如调度问题、资源分配问题和路径规划问题等。通过利用LLM分析问题实例的特征，可以为这些问题设计出更加高效的元启发式算法。此外，人-LLM协作模式也为算法设计提供了一种新的思路，有望加速算法开发过程。

📄 摘要（原文）

Integrating Large Language Models (LLMs) within metaheuristics opens a novel path for solving complex combinatorial optimization problems. While most existing approaches leverage LLMs for code generation to create or refine specific heuristics, they often overlook the structural properties of individual problem instances. In this work, we introduce a novel framework that integrates LLMs with a Biased Random-Key Genetic Algorithm (BRKGA) to solve the NP-hard Longest Run Subsequence problem. Our approach extends the instance-driven heuristic bias paradigm by introducing a human-LLM collaborative process to co-design and implement a set of computationally efficient metrics. The LLM analyzes these instance-specific metrics to generate a tailored heuristic bias, which steers the BRKGA toward promising areas of the search space. We conduct a comprehensive experimental evaluation, including rigorous statistical tests, convergence and behavioral analyses, and targeted ablation studies, comparing our method against a standard BRKGA baseline across 1,050 generated instances of varying complexity. Results show that our top-performing hybrid, BRKGA+Llama-4-Maverick, achieves statistically significant improvements over the baseline, particularly on the most complex instances. Our findings confirm that leveraging an LLM to produce an a priori, instance-driven heuristic bias is a valuable approach for enhancing metaheuristics in complex optimization domains.