Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model

📄 arXiv: 2401.02051v3 📥 PDF

作者: Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, Qingfu Zhang

分类: cs.NE, cs.AI

发布日期: 2024-01-04 (更新: 2024-06-01)

💡 一句话要点

提出进化启发式算法以实现高效自动算法设计

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

关键词: 启发式算法 自动化设计 进化计算 大型语言模型 组合优化 在线装箱问题 算法性能

📋 核心要点

  1. 现有的启发式算法设计方法劳动强度大，且依赖于设计者的经验和知识，效率低下。
  2. 本文提出的进化启发式算法（EoH）通过结合大型语言模型和进化计算，实现了启发式算法的自动化设计。
  3. 实验结果显示，EoH在多个组合优化问题上表现优异，尤其在在线装箱问题中，性能显著超过传统手工设计的算法。

📝 摘要（中文）

启发式算法广泛应用于复杂搜索和优化问题的解决。然而，手动设计启发式算法通常劳动强度大且需要丰富的经验和知识。本文提出了一种新颖的进化启发式算法（EoH），结合了大型语言模型（LLMs）和进化计算（EC）方法，实现自动启发式设计（AHD）。EoH将启发式思想以自然语言表示，称为“思维”，并通过LLMs转化为可执行代码。在进化搜索框架中，思维和代码的共同进化使得生成高性能启发式算法变得高效有效。实验表明，EoH在多个组合优化基准问题上超越了常用的手工设计启发式算法及其他最近的AHD方法，尤其是在在线装箱问题中，EoH以较低的计算预算显著优于人类手工设计的基线算法。

🔬 方法详解

问题定义：本文旨在解决启发式算法设计中的高劳动强度和效率低下的问题。现有方法往往依赖于设计者的经验，导致设计过程繁琐且不够灵活。

核心思路：论文提出的EoH方法通过将启发式思想用自然语言表达，并利用大型语言模型将其转化为代码，从而实现启发式算法的自动化设计。这种方法能够快速生成高性能的启发式算法。

技术框架：EoH的整体架构包括两个主要模块：首先是将启发式思想转化为自然语言的“思维”表示；其次是通过进化计算框架对这些思维和相应代码进行进化搜索，以生成高效的启发式算法。

关键创新：EoH的最大创新在于将大型语言模型与进化计算结合，形成了一种新的自动启发式设计方法。这一方法与传统的手工设计方法本质上不同，能够在更短的时间内生成更优的算法。

关键设计：在EoH中，关键参数包括LLMs的查询次数和进化计算的选择策略。损失函数设计用于评估生成算法的性能，而网络结构则基于LLMs的架构进行优化，以确保生成代码的可执行性和效率。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，EoH在多个组合优化基准问题上表现优异，尤其是在在线装箱问题中，其生成的启发式算法在计算预算较低的情况下，性能显著超越传统手工设计的基线算法，展示了EoH的高效性和有效性。

🎯 应用场景

该研究的潜在应用领域包括组合优化、资源分配、调度问题等多个复杂决策场景。通过自动化启发式算法设计，EoH能够为实际问题提供高效解决方案，降低人工设计成本，提升算法性能，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.