PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Niki van Stein, Thomas Bäck

arXiv:2405.20132v4cs.NEcs.AI

TL;DR

The paper asks whether LLMs can automate the generation and optimization of effective metaheuristics beyond expert-defined design spaces and prior small or combinatorial settings. It introduces LLaMEA, an evolutionary framework that generates, evaluates, and refines algorithm code using benchmark feedback. LLaMEA generates high-performing algorithms that rival and sometimes surpass established optimization techniques, while the study identifies computational and experimental boundaries for the approach.

  • Problem

    Prior LLM algorithm-generation work often targets small or combinatorial problems or lacks benchmarking against state-of-the-art algorithms, while modular methods remain bounded by expert-selected design spaces.

  • Method

    LLaMEA combines LLM-generated algorithm code with an evolutionary loop that uses automated IOHexperimenter evaluations, performance scores, runtime errors, and textual feedback to guide refinement or redesign.

  • Results

    LLaMEA generates algorithms that rival and sometimes surpass existing state-of-the-art techniques, with GPT-4 LLaMEA showing better convergence and a better final algorithm than EoH.

  • Takeaways & Limitations

    The findings demonstrate the feasibility of using LLMs to automatically generate and optimize metaheuristic algorithms within a computationally feasible framework.

  • Takeaways & Limitations

    The experiments were limited to five repetitions because commercial LLM calls were costly in computational effort and funds.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses limitations of expert-designed and modular metaheuristics by introducing LLaMEA, which uses LLMs in an evolutionary loop to generate and optimize algorithms with automated benchmarking feedback.

  • Metaphor-inspired algorithms are numerous, but systematic empirical benchmarking against state-of-the-art methods is typically not performed.
  • Modular frameworks can search millions of algorithm combinations, but experts must define their modules and infrastructure, limiting the explored design space.
  • LLaMEA uses LLMs within an evolutionary loop to iteratively evolve and optimize metaheuristic program code.
  • LLaMEA combines in-context learning, task prompts, error handling, and selection strategies to generate metaheuristics for continuous optimization.
  • IOHexperimenter evaluates generated algorithms on BBOB and supplies performance feedback, enabling automated comparison with established algorithms.
  • Prior LLM algorithm-generation approaches commonly target small or combinatorial problems, whereas this work combines in-context learning with evolutionary generation for continuous optimization.

III. LLAMEA

LLaMEA follows a one-parent, one-child evolutionary structure: it initializes an LLM-generated algorithm, evaluates it, repeatedly generates offspring through refinement or redesign, and retains according to a selection strategy.

  • LLaMEA iteratively repeats initialization, evaluation, and refinement or mutation using an IOHexperimenter-based optimization loop.
  • Initialization: The algorithm begins with a task prompt, generates an initial program, evaluates its quality, and stores it as the best-so-far candidate.
  • Optimization loop: Each iteration constructs a feedback prompt and asks the LLM to generate an offspring algorithm by mutation.
  • Selection: The (1+1) strategy accepts improvements, while the (1,1) strategy always accepts the newly generated algorithm.
  • Evaluation: Runtime errors are recorded, and erroneous candidates receive quality zero before the best-so-far algorithm is updated.
  • Evaluation: The generic framework leaves the quality function unspecified until a task-specific measure is defined.

A. Starting Prompt

The starting prompt defines black-box optimization as the task, specifies the required Python interface and evaluation budget, and includes an example-code format for generating a heuristic.

  • A simple random-search implementation is included as example code, with the response requested in a named algorithm and code format.
  • The prompt asks the LLM to design novel metaheuristic algorithms for black-box optimization problems.
  • The task covers a wide range of tasks evaluated on a large suite of noiseless functions.
  • Generated algorithms must be written in Python and contain a __call__(self, f) function.
  • The objective function may be called only within the specified budget of function evaluations.

B. Algorithm Synthesis (Initialization)

Algorithm synthesis extracts and evaluates LLM-generated Python algorithms on BBOB, then feeds scores, errors, and prior candidates back into prompts for refinement or redesign.

  • LLM responses are parsed to extract algorithm names and Python code, with exception handling for deviations from the requested format.
  • Generated code is dynamically loaded and instantiated; syntax errors are recorded, skipped during evaluation, and assigned quality zero.
  • BBOB evaluates each generated algorithm on 24 noiseless functions spanning five function groups.
  • Each run uses a fixed function-evaluation budget, and IOHexperimenter enforces termination after the full budget is used.
  • The feedback prompt supplies prior algorithm names and scores plus the selected algorithm, its mean and standard-deviation AOCC scores, and an instruction to refine or redesign.
  • The LLM may make a small refinement or complete redesign, with redesign functioning analogously to a restart or large mutation in evolutionary optimization.

Restarts and Mutation Rate:

LLaMEA supports two selection strategies and experiments with richer feedback, history representations, and multiple LLM configurations. Detailed per-function feedback did not improve performance, while retaining full code history is avoided because its cost grows with the run.

  • Selection strategies: LLaMEA supports elitist (1 + 1) selection, which refines the best-so-far algorithm, and (1, 1) selection, which refines the last generated algorithm.Each iteration provides the LLM with the full code of the selected algorithm.
  • Detailed feedback: Providing per-function-group AOCC means and standard deviations gives the LLM more detailed performance feedback than an overall score.The feedback covers five BBOB function groups.
  • Detailed feedback: Adding per-function-group performance details never increased performance in the experiments.The corresponding results were therefore moved to the supplemental material.
  • Run history: The framework omits the complete run history because supplying all previous algorithm codes becomes increasingly expensive as the list grows.A larger archive of previous attempts could theoretically support multi-shot in-context learning.
  • Run history: Instead of all previous codes, LLaMEA provides a condensed list of generated algorithm names and their scores.This list is intended to help the LLM identify successful algorithm types and reduce repeated generations.
  • Experimental comparisons: The experiments compare three ChatGPT-family LLMs and two selection strategies, then compare the best combination with EoH and random search.The tested models are gpt-3.5-turbo-0125, gpt-4-turbo-2024-04-09, and gpt-4o-2024-05-13.

B. Benchmark Problems

The evaluation uses the BBOB continuous-optimization suite and normalized AOCC to measure anytime performance across functions, instances, and repeated runs. LLaMEA is compared with EoH and random search; GPT-4 with (1 + 1) selection shows the strongest reported convergence, while execution failures account for 18.7% of runs.

  • Benchmark setup: BBOB evaluation uses 24 noiseless functions, three instances per function, and three independent runs per instance.Each run uses an evaluation budget of B = 10 000 function evaluations.
  • Performance metric: Normalized AOCC measures anytime performance over the complete evaluation budget rather than only the final objective value.It is computed from best-so-far log-scaled precision values using bounds lb = 10^-8 and ub = 10^2.
  • Performance metric: The final quality feedback is the mean AOCC over 24 BBOB functions, their instances, and k = 5 independent algorithm runs.This score is returned to the LLM and used as the best-so-far value when improved.
  • Evaluation handling: Runtime and compile errors also inform LLM feedback, while fatal errors receive the minimum mean AOCC score of zero.This makes infeasible algorithm executions unsuccessful candidates in the evaluation loop.
  • Results comparison: LLaMEA-(1 + 1) GPT-4 converges better than EoH and random search, while EoH is more stable across runs because it uses a larger population.Different selection strategies produce different outcomes depending on the LLM; GPT-4 performs best overall in the reported comparison.

A. Novelty and diversity

LLaMEA-generated algorithms combine existing algorithmic components through refinement, redesign, and mutations that range from parameter tuning to changes in high-level logic.

  • Generated algorithms commonly combine existing techniques, including evolution, adaptive or dynamic strategies, harmony, firework, gradient, local search, and elitism.
  • GPT-4-LLaMEA generally makes the largest parent-offspring code changes, indicating greater exploration across runs.
  • GPT-3.5 produces smaller average code differences, while its (1+1) strategy shows unusually large differences at the beginning of runs.
  • Mutations can alter hyperparameters, high-level logic such as crossover or mutation operators, and explanatory comments.
  • The LLM alternates between refining algorithms through name and code changes and redesigning them around different strategies.
  • Jaro similarity tracks name changes between parent and offspring, with some GPT-3.5 steps making small mutations and occasional complete restarts.

VI. ANALYSIS OF BEST ALGORITHMS

The study evaluates generated algorithms across BBOB dimensions and compares them with CMA-ES, optimized CMA-ES, and Differential Evolution. In 5d, several generated algorithms outperform baselines under different evaluation budgets, while ERADS shows especially promising behavior on selected functions.

  • 3 657 of 4 500 generated algorithms achieved an AOCC score larger than zero on the 5d BBOB suite.The validation evaluates performance in 5, 10, and 20 dimensions using five instances and five independent runs per instance.
  • Figure 7 compares six best generated algorithms with CMA-ES, CMA-best, and Differential Evolution using EAF curves averaged over 24 BBOB functions in 5d.The EAF fraction is plotted against the number of function evaluations.
  • ERADS outperforms CMA-ES in 5d by AOCC, while ERADS and AdaptiveDifferentialEvolutionHarmonySearch outperform CMA-best after the total budget.
  • EnhancedFireworkAlgorithmWithLocalSearch and QuantumDifferentialParticleOptizerWithElitism outperform CMA-best during the first 1000 evaluations.
  • ERADS shows especially promising search behavior on BBOB functions f17 and f18.Figure 8 reports median best-so-far function values over 10 000 evaluations for ERADS and three baselines across all 24 functions.

A. The ”ERADS QuantumFluxUltraRefined” Algorithm

ERADS QuantumFluxUltraRefined is an LLM-generated differential-evolution-like algorithm that adds memory-guided mutation and adaptive parameter control. Its generated 5d hyperparameters were not further improved by supplemental optimization.

  • Algorithm design: ERADS resembles Differential Evolution but adds a memory factor to mutation and adaptive F and CR control.Its mutation combines three random individuals, the best individual, and a memory vector before binomial crossover.
  • Relation to prior methods: The proposed ERADS algorithm is most similar to JADE, with key differences reported as novel by the authors.The differences center on a memory vector and parameter adaptation.
  • Mutation mechanism: ERADS uses the mutation rule v_i = x_r1 + F_g · (x_best − x_r1) + F_g · (x_r2 − x_r3) + F_g · m_f · m.F_g changes by generation, while the memory contribution is 0.3·F_g·m because m_f remains 0.3.
  • Parameter adaptation: The algorithm increases F_g linearly from 0.55 to 0.85 over the run while keeping the mutation factor below the typically recommended maximum range.The update is F_g = 0.55 + 0.3 · t/B.
  • Hyperparameter assessment: The LLM-generated 5d hyperparameter settings could not be improved further in the supplemental optimization experiments.This finding concerns ERADS and the tested BBOB 5d setting.

B. Performance Analysis in Higher Dimensions

The generated algorithms were evaluated against CMA-best, CMA-ES, and Differential Evolution in higher-dimensional BBOB settings. The authors explicitly limit the intended scope because generation targeted BBOB in 5d.

  • Evaluation: The higher-dimensional evaluation compares LLaMEA algorithms with CMA-best, CMA-ES, and Differential Evolution using BBOB results.CMA-ES and DE use recommended hyperparameter settings, and the comparison includes dimensions 10 and 20.
  • Scope boundary: The generated algorithm was designed for BBOB in 5d and was not expected to scale to high-dimensional problems.For this reason, the evaluation does not extend beyond d = 20.

VII. CONCLUSIONS AND OUTLOOK

LLaMEA uses LLMs to generate and evolve metaheuristic algorithms, producing candidates that rival established techniques. The paper highlights practical promise while identifying prompt, execution, and scalability challenges.

  • Conclusions: LLaMEA automatically generates and optimizes metaheuristic algorithms with LLMs.The framework automates evolution of algorithm design within a computationally feasible framework.
  • Conclusions: LLaMEA-generated algorithms perform comparably to traditional state-of-the-art metaheuristics.The conclusion presents this as evidence of potential for LLMs in algorithmic design.
  • Interpretation: LLMs fine-tune parameters and introduce new mutation and crossover logic in generated optimization algorithms.The paper connects this behavior with the LLM’s access to a large code base of existing metaheuristics.
  • Implications: The authors argue that automated design may become preferable for application-specific heuristics because manual nature-inspired heuristics are laborious and often insufficiently novel.The passage also notes that such heuristics often cannot compete with random search.
  • Limitations: Prompt quality, generated-code reliability, and LLM computational cost constrain LLaMEA’s robustness and scalability.The authors identify these challenges especially for extensive or multi-objective optimization problems.
  • Outlook: Future work proposes broader evolutionary strategies, including population-based (µ +, λ)-EAs and applications to Bayesian or surrogate-assisted algorithms.The proposed extensions aim to increase candidate diversity and demonstrate versatility across algorithm classes.

APPENDIX A BBOB FUNCTION GROUPS

The appendix documents the BBOB benchmark, supplementary performance analyses, and examples of LLM-generated code mutations. It also compares default and optimized ERADS hyperparameters across dimensions.

  • BBOB benchmark: BBOB contains 24 noiseless functions grouped into five function categories, with rotated and translated instances used in experiments.The benchmark is used extensively for black-box optimization evaluation.
  • Supplementary evaluation: The supplementary experiments report additional BBOB results for different LLM and strategy combinations, including feedback based on function-group AOCC scores.The additional feedback did not produce better optimization performance and is therefore shown only in the supplement.
  • Performance figures: Figures 10–13 visualize empirical attainment or median best-so-far values for selected algorithms and baselines across 5d, 10d, and 20d.The EAF aggregates attainment behavior over the 24 BBOB functions, while the convergence plots use 2 000·d evaluations.
  • Code evolution: The mutation examples show that LLaMEA can tune hyperparameters, add mutation logic, and alter crossover operators.Early evolution shows larger changes, while later evolution can make small hyperparameter adjustments.
  • Hyperparameter comparison: SMAC3 hyperparameter optimization outperformed ERADS’s default settings only in 20d; 5d and 10d performance was not significantly different.The supplemental comparison uses EAF curves and a 5,000-evaluation optimization budget.

I. BBOB FUNCTION GROUPS

The evaluation uses the 24-function BBOB suite across five function groups and compares LLM-discovered algorithms with established baselines across 5d, 10d, and 20d. Additional analyses examine mutation patterns and whether external hyper-parameter optimization improves the best discovered algorithm.

  • Benchmark design: BBOB comprises 24 noiseless functions grouped into five categories, with rotated and translated instances used for benchmarking.The experiments evaluate algorithms across varied function landscapes and instances.
  • Benchmark design: EAF plots compare the best algorithm per configuration with CMA-ES, CMA-best, and DE across all 24 functions in 5d, 10d, and 20d.The EAF measures the percentage of runs reaching a target value by a given runtime.
  • Benchmark results: Median best-so-far values are tracked over 2 000 · d evaluations for each BBOB function against CMA-ES, DE, and BIPOP-CMA-ES in 5d.Corresponding plots report the 10d and 20d evaluations separately.
  • Evolutionary mutations: LLM mutations range from early hyper-parameter tuning and new mutation strategies to late fine-tuning and changes to the crossover operator.The examples illustrate both substantial early changes and smaller late-stage modifications.
  • Hyper-parameter analysis: SMAC3 optimization of ERADS QuantumFluxUltraRefined improved performance over LLM-generated defaults only in 20d, while 5d and 10d performance was not significantly different.The comparison used a 5 000-evaluation SMAC3 budget and evaluated the resulting settings on the BBOB functions.
Loading 2405.20132v4…