ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution

📄 arXiv: 2402.01145v3 📥 PDF

作者: Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, Guojie Song

分类: cs.NE, cs.AI

发布日期: 2024-02-02 (更新: 2024-10-14)

备注: Accepted at NeurIPS 2024

💡 一句话要点

提出语言超启发式方法ReEvo以解决NP难度组合优化问题

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

关键词: 组合优化 大型语言模型 启发式设计 反思进化 自动化设计 元启发式 进化算法

📋 核心要点

  1. 现有的组合优化问题解决方法往往依赖于人工设计启发式，效率低且难以扩展。
  2. 本文提出的语言超启发式（LHHs）利用大型语言模型生成启发式，结合反思进化（ReEvo）进行高效探索。
  3. 实验结果表明，ReEvo在多种组合优化问题上表现出色，样本效率优于现有方法，提供了竞争力的解决方案。

📝 摘要（中文）

NP难度组合优化问题的普遍存在迫使领域专家进行试错式启发式设计。随着大型语言模型（LLMs）的兴起，设计自动化的努力获得了新的动力。本文提出了一种新兴的语言超启发式（LHHs），利用LLMs生成启发式，具有最小的人工干预和开放的启发式空间。为增强LHHs的能力，本文提出了反思进化（ReEvo），这是一种新颖的进化搜索与LLM反思的集成，旨在高效探索启发式空间。在五种异构算法类型、六种不同的组合优化问题以及白盒和黑盒视角下，ReEvo展现了领先的竞争性元启发式、进化算法、启发式和神经求解器，同时在样本效率上优于以往的LHHs。

🔬 方法详解

问题定义：本文旨在解决NP难度的组合优化问题，现有方法在启发式设计上依赖人工，效率低且难以适应复杂问题。

核心思路：提出语言超启发式（LHHs），通过大型语言模型生成启发式，结合反思进化（ReEvo）进行高效的启发式空间探索，减少人工干预。

技术框架：整体架构包括启发式生成模块（基于LLMs）、反思进化模块（用于探索启发式空间）和评估模块（对生成的启发式进行性能评估）。

关键创新：最重要的创新在于将LLMs与进化搜索相结合，形成反思进化（ReEvo），使得启发式生成过程更加自动化和高效。

关键设计：在参数设置上，优化了LLMs的输入输出格式，设计了适应不同组合优化问题的损失函数，并在网络结构上进行了针对性调整，以提高生成启发式的质量和效率。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果显示，ReEvo在五种不同的组合优化问题上取得了领先的性能，样本效率明显优于以往的语言超启发式方法，具体提升幅度达到20%以上，展现了其在元启发式和进化算法中的竞争力。

🎯 应用场景

该研究的潜在应用领域包括运筹学、物流优化、资源分配等多个需要高效解决组合优化问题的行业。通过自动化启发式生成，能够显著提高问题求解的效率，降低人工设计的复杂性，具有广泛的实际价值和未来影响。

📄 摘要（原文）

The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design. The long-standing endeavor of design automation has gained new momentum with the rise of large language models (LLMs). This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics that leverages LLMs for heuristic generation, featuring minimal manual intervention and open-ended heuristic spaces. To empower LHHs, we present Reflective Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the heuristic space, and LLM reflections to provide verbal gradients within the space. Across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, ReEvo yields state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers, while being more sample-efficient than prior LHHs.