Generalizable Heuristic Generation Through Large Language Models with Meta-Optimization

📄 arXiv: 2505.20881v1 📥 PDF

作者: Yiding Shi, Jianan Zhou, Wen Song, Jieyi Bi, Yaoxin Wu, Jie Zhang

分类: cs.LG, cs.AI

发布日期: 2025-05-27

💡 一句话要点

提出MoH框架，利用LLM元优化启发式算法，提升组合优化问题泛化性。

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

关键词: 元学习 大型语言模型 启发式算法 组合优化 多任务学习

📋 核心要点

  1. 现有方法依赖手动预定义的进化计算优化器和单任务训练，限制了启发式算法的多样性和泛化能力。
  2. MoH框架通过元学习，利用LLM迭代优化元优化器，自主构建多样化优化器，演化启发式算法。
  3. 实验表明，MoH构建的元优化器在各种下游任务中实现了SOTA性能，尤其在跨规模设置中。

📝 摘要（中文）

本文提出了一种名为启发式元优化（MoH）的新框架，旨在解决利用大型语言模型（LLM）设计启发式算法时，对预定义进化计算（EC）优化器和单任务训练方案的依赖问题，这些依赖限制了启发式算法的多样性探索和泛化能力。MoH在优化器层面运行，通过元学习原则发现有效的优化器。具体而言，MoH利用LLM迭代优化元优化器，该元优化器通过（自）调用自主构建多样化的优化器，从而消除了对预定义EC优化器的依赖。这些构建的优化器随后演化下游任务的启发式算法，从而实现更广泛的启发式探索。此外，MoH采用多任务训练方案来提升其泛化能力。在经典组合优化问题上的实验表明，MoH构建了一个有效且可解释的元优化器，在各种下游任务中实现了最先进的性能，尤其是在跨规模设置中。

🔬 方法详解

问题定义：现有基于LLM的启发式算法设计方法依赖于手动预定义的进化计算（EC）优化器和单任务训练方案。这种依赖限制了对多样化启发式算法的探索，并且阻碍了启发式算法在不同问题规模和类型上的泛化能力。因此，如何设计一种能够自动探索和优化启发式算法，并具备良好泛化能力的框架，是本文要解决的核心问题。

核心思路：本文的核心思路是采用元学习的思想，训练一个元优化器，该元优化器能够自主地生成和优化用于特定组合优化问题的启发式算法。通过让LLM扮演元优化器的角色，并利用其强大的生成和推理能力，可以摆脱对预定义EC优化器的依赖，从而探索更广泛的启发式算法空间。同时，采用多任务训练策略，可以提高元优化器在不同问题上的泛化能力。

技术框架：MoH框架主要包含以下几个阶段：1) 元优化器构建：利用LLM构建一个元优化器，该优化器能够生成和优化用于特定组合优化问题的优化器。2) 优化器生成：元优化器通过自调用或外部调用，生成一系列用于演化启发式算法的优化器。3) 启发式算法演化：生成的优化器用于演化针对下游任务的启发式算法。4) 多任务训练：采用多任务训练策略，在多个组合优化问题上训练元优化器，提高其泛化能力。

关键创新：MoH的关键创新在于提出了一个基于LLM的元优化框架，该框架能够自主地生成和优化启发式算法，而无需依赖预定义的EC优化器。这种方法不仅能够探索更广泛的启发式算法空间，而且能够提高启发式算法在不同问题上的泛化能力。此外，MoH还采用了多任务训练策略，进一步提升了元优化器的泛化性能。

关键设计：MoH的关键设计包括：1) LLM的选择：选择具有强大生成和推理能力的LLM作为元优化器。2) 元优化器的训练目标：设计合适的训练目标，例如最大化下游任务的性能。3) 多任务训练策略：选择合适的组合优化问题作为训练任务，并设计合适的训练策略。4) 优化器生成方式：设计元优化器生成优化器的方式，例如通过自调用或外部调用。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，MoH在各种经典组合优化问题上取得了最先进的性能，尤其是在跨规模设置中。例如，在旅行商问题（TSP）上，MoH在不同规模的TSP实例上均优于现有的启发式算法。此外，MoH生成的元优化器具有良好的可解释性，可以帮助研究人员理解启发式算法的内在机制。

🎯 应用场景

MoH框架具有广泛的应用前景，可应用于车辆路径规划、调度优化、资源分配等各种组合优化问题。通过自动生成和优化启发式算法，MoH可以显著降低人工设计启发式算法的成本，并提高求解效率和质量。未来，MoH有望成为解决复杂组合优化问题的重要工具，推动相关领域的发展。

📄 摘要（原文）

Heuristic design with large language models (LLMs) has emerged as a promising approach for tackling combinatorial optimization problems (COPs). However, existing approaches often rely on manually predefined evolutionary computation (EC) optimizers and single-task training schemes, which may constrain the exploration of diverse heuristic algorithms and hinder the generalization of the resulting heuristics. To address these issues, we propose Meta-Optimization of Heuristics (MoH), a novel framework that operates at the optimizer level, discovering effective optimizers through the principle of meta-learning. Specifically, MoH leverages LLMs to iteratively refine a meta-optimizer that autonomously constructs diverse optimizers through (self-)invocation, thereby eliminating the reliance on a predefined EC optimizer. These constructed optimizers subsequently evolve heuristics for downstream tasks, enabling broader heuristic exploration. Moreover, MoH employs a multi-task training scheme to promote its generalization capability. Experiments on classic COPs demonstrate that MoH constructs an effective and interpretable meta-optimizer, achieving state-of-the-art performance across various downstream tasks, particularly in cross-size settings.