LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics

📄 arXiv: 2405.20132v4 📥 PDF

作者: Niki van Stein, Thomas Bäck

分类: cs.NE, cs.AI

发布日期: 2024-05-30 (更新: 2025-01-30)

备注: Accepted at IEEE TEVC

💡 一句话要点

LLaMEA：基于大语言模型进化算法的元启发式算法自动生成框架

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

关键词: 大语言模型 进化算法 元启发式算法 自动算法生成 黑盒优化

📋 核心要点

  1. 现有元启发式算法设计依赖专家知识，且人工设计耗时费力，难以适应复杂优化问题。
  2. LLaMEA利用GPT模型，通过进化算法迭代生成、变异和选择算法，实现元启发式算法的自动设计与优化。
  3. 实验表明，LLaMEA生成的算法在BBOB测试中，超越了CMA-ES和DE等先进算法，验证了框架的有效性。

📝 摘要（中文）

本文提出了一种新颖的大语言模型进化算法（LLaMEA）框架，该框架利用GPT模型自动生成和优化算法。给定一组标准和一个任务定义（搜索空间），LLaMEA基于性能指标和运行时评估的反馈，迭代地生成、变异和选择算法。该框架提供了一种独特的算法优化方法，无需大量的先验专业知识。我们展示了如何使用该框架自动生成新的黑盒元启发式优化算法。LLaMEA生成的多个算法在五维黑盒优化基准（BBOB）上优于最先进的优化算法（协方差矩阵自适应进化策略和差分进化）。这些算法在测试函数的10维和20维实例上也表现出有竞争力的性能，尽管它们在自动生成过程中没有见过这些实例。结果证明了该框架的可行性，并确定了通过LLM自动生成和优化算法的未来方向。

🔬 方法详解

问题定义：论文旨在解决元启发式算法设计过程中对专家知识的依赖以及手动设计算法的低效问题。现有方法需要大量人工干预，难以快速适应新的优化问题，并且设计的算法可能并非最优。

核心思路：论文的核心思路是利用大语言模型（LLM）的强大代码生成能力，结合进化算法的迭代优化机制，自动生成和优化元启发式算法。通过定义合适的评价指标和反馈机制，引导LLM生成更有效的算法。

技术框架：LLaMEA框架包含以下主要模块：1) 算法生成：使用LLM（如GPT模型）根据给定的任务定义和约束条件生成候选算法。2) 算法评估：在目标问题上运行生成的算法，并根据预定义的性能指标（如优化结果、运行时间）评估算法的性能。3) 算法选择：使用进化算法的选择算子（如锦标赛选择）选择表现较好的算法。4) 算法变异：对选定的算法进行变异操作，例如修改算法的代码片段，以生成新的候选算法。重复以上步骤，直到满足停止条件。

关键创新：该方法最重要的创新点在于将大语言模型的代码生成能力与进化算法的优化能力相结合，实现元启发式算法的自动设计。与传统的手动设计方法相比，该方法可以更快地探索更广阔的算法空间，并发现更有效的算法。

关键设计：关键设计包括：1) 任务定义：明确定义优化问题的搜索空间、目标函数和约束条件。2) 性能指标：选择合适的性能指标来评估算法的优化效果，例如目标函数值、收敛速度等。3) 变异算子：设计有效的变异算子，以保证算法的多样性和探索能力。4) LLM提示工程：设计合适的提示词，引导LLM生成符合要求的算法代码。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LLaMEA生成的算法在五维BBOB测试函数上显著优于CMA-ES和DE等先进算法。此外，这些算法在未经训练的10维和20维实例上也表现出竞争力的性能，表明该框架具有良好的泛化能力。这些结果验证了LLaMEA框架在自动生成元启发式算法方面的有效性。

🎯 应用场景

该研究成果可应用于各种优化问题，例如机器学习模型参数优化、组合优化、工程设计等。通过自动生成针对特定问题的优化算法，可以降低算法设计的门槛，提高优化效率，并加速相关领域的创新。未来，该方法有望应用于更复杂的优化问题，并与其他AI技术相结合，实现更智能的自动化优化。

📄 摘要（原文）

Large Language Models (LLMs) such as GPT-4 have demonstrated their ability to understand natural language and generate complex code snippets. This paper introduces a novel Large Language Model Evolutionary Algorithm (LLaMEA) framework, leveraging GPT models for the automated generation and refinement of algorithms. Given a set of criteria and a task definition (the search space), LLaMEA iteratively generates, mutates and selects algorithms based on performance metrics and feedback from runtime evaluations. This framework offers a unique approach to generating optimized algorithms without requiring extensive prior expertise. We show how this framework can be used to generate novel black-box metaheuristic optimization algorithms automatically. LLaMEA generates multiple algorithms that outperform state-of-the-art optimization algorithms (Covariance Matrix Adaptation Evolution Strategy and Differential Evolution) on the five dimensional black box optimization benchmark (BBOB). The algorithms also show competitive performance on the 10- and 20-dimensional instances of the test functions, although they have not seen such instances during the automated generation process. The results demonstrate the feasibility of the framework and identify future directions for automated generation and optimization of algorithms via LLMs.