PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Language Models as Evolutionary Optimizers

Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, Yew-Soon Ong

arXiv:2310.19046v3cs.NE

TL;DR

The paper asks whether LLMs can reduce the domain expertise and human effort needed to design evolutionary operators for combinatorial optimization. It proposes LMEA, which uses an LLM for parent selection, crossover, and mutation within an EA, and finds competitive TSP performance up to 20 nodes. The authors identify scalability to relatively large problems as an open limitation.

  • Problem

    Evolutionary algorithms often require problem-specific operators designed with substantial domain expertise and human effort.

  • Method

    LMEA uses an LLM in each generation to select parents and perform crossover and mutation, evaluates offspring, retains top solutions, and self-adapts temperature.

  • Results

    LMEA performs competitively with traditional heuristics on TSP instances with up to 20 nodes, while LLM-driven operators outperform OPRO across eight test sets.

  • Takeaways & Limitations

    The results demonstrate the capacity of LLM-driven evolutionary search to solve non-trivial NP-hard combinatorial problems with minimal domain expertise.

  • Takeaways & Limitations

    LMEA currently has limitations in handling relatively large problems.

Abstract

from arXiv · show

Evolutionary algorithms (EAs) have achieved remarkable success in tackling complex combinatorial optimization problems. However, EAs often demand carefully-designed operators with the aid of domain expertise to achieve satisfactory performance. In this work, we present the first study on large language models (LLMs) as evolutionary combinatorial optimizers. The main advantage is that it requires minimal domain knowledge and human efforts, as well as no additional training of the model. This approach is referred to as LLM-driven EA (LMEA). Specifically, in each generation of the evolutionary search, LMEA instructs the LLM to select parent solutions from current population, and perform crossover and mutation to generate offspring solutions. Then, LMEA evaluates these new solutions and include them into the population for the next generation. LMEA is equipped with a self-adaptation mechanism that controls the temperature of the LLM. This enables it to balance between exploration and exploitation and prevents the search from getting stuck in local optima. We investigate the power of LMEA on the classical traveling salesman problems (TSPs) widely used in combinatorial optimization research. Notably, the results show that LMEA performs competitively to traditional heuristics in finding high-quality solutions on TSP instances with up to 20 nodes. Additionally, we also study the effectiveness of LLM-driven crossover/mutation and the self-adaptation mechanism in evolutionary search. In summary, our results reveal the great potentials of LLMs as evolutionary optimizers for solving combinatorial problems. We hope our research shall inspire future explorations on LLM-driven EAs for complex optimization challenges.

I. INTRODUCTION

The paper addresses the domain expertise and human effort required to design effective evolutionary operators by proposing LMEA, which uses an LLM to drive evolutionary search. On TSPs up to 20 nodes, LMEA performs competitively with traditional heuristics while requiring minimal domain knowledge.

  • Motivation: Evolutionary algorithms often require carefully handcrafted operators tailored to problem structure, making their design dependent on domain expertise and human effort.This burden can increase when algorithms are applied to new problems.
  • Motivation: Meta-optimization automates some EA design choices but still faces challenges in selecting training sets, defining design spaces, and solving the meta-optimization problem.
  • Approach: LMEA instructs an LLM each generation to select parents and perform crossover and mutation, then evaluates offspring and adds them to the population.A self-adaptation mechanism controls LLM temperature to balance exploration and exploitation.
  • Approach: LMEA describes problems and desired solution properties in natural language, enabling adaptation across optimization problems with minimal domain knowledge and human effort.The method uses zero-shot LLM operation, requiring no additional model training.
  • Results: LMEA performs competitively with traditional heuristics on TSP instances with up to 20 nodes and consistently finds optimal solutions on 10-node and 15-node instances.The study also evaluates LLM-driven genetic operators and the self-adaptation mechanism.
  • Contribution: The paper presents, to the authors’ knowledge, the first use of LLMs in evolutionary combinatorial optimization and emphasizes a departure from prior EA design paradigms.The stated goal is not to outperform sophisticated specialized TSP solvers.

II. RELATED WORKS

This section reviews combinatorial optimization, evolutionary operators, LLMs and prompts, and the paper’s algorithmic framing. It highlights why problem-specific EA operators and prompt design matter.

  • Combinatorial Optimization: Combinatorial optimization seeks the best solution from a finite set, while many such problems are NP-hard and exact methods generally have exponential time complexity.
  • EAs for Combinatorial Optimization: EA practitioners often tailor crossover, mutation, repair, and regrouping operators to solution representations, constraints, and population-diversity needs.Examples include k-opt mutation and edge assembly crossover for permutation-based TSP and VRP representations.
  • LLMs and Prompts: LLMs are large neural networks trained on extensive text data for next-token prediction and have shown strong performance across reasoning and decision-making tasks.
  • LLMs and Prompts: A prompt is an instruction that guides an LLM toward generating a desired output.
  • LMEA: LMEA is presented as an EA whose input includes an optimization problem, maximum generations, and population size, and whose output is the best found solution.The algorithm listing also includes temperature self-adaptation.
  • LLMs and Prompts: Prompt format can significantly influence LLM output quality, motivating careful attention to context, detail, clarity, demonstrations, and reasoning instructions.

C. Intersection between EAs and LLMs

Research combining LLMs and evolutionary algorithms remains early-stage. Existing work has used LLMs with EAs for generating neural architectures, programs, and meta-heuristics, while EAs have also been used to evolve prompts.

  • Intersection between EAs and LLMs: Recent studies combine LLMs with evolutionary algorithms to generate neural network structures, functional programs, and meta-heuristics.
  • Intersection between EAs and LLMs: Evolutionary principles have also been applied to evolve prompts intended to improve LLM performance.

III. LMEA FOR COMBINATORIAL OPTIMIZATION

LMEA follows an evolutionary framework in which an LLM helps generate offspring through prompt-guided genetic operations. The section then develops prompt construction and temperature self-adaptation, with an overview in Figure 1.

  • III. LMEA FOR COMBINATORIAL OPTIMIZATION: The section presents LMEA’s framework, prompt construction, and self-adaptation mechanism for the LLM’s temperature.
  • III. LMEA FOR COMBINATORIAL OPTIMIZATION: Figure 1 provides an overview of the LMEA approach.

A. Algorithm Framework

LMEA uses an LLM as evolutionary operators in a zero-shot EA framework, guiding parent selection, crossover, and mutation through natural-language prompts. The prompts specify the problem, solution properties, examples, and task instructions while leaving operator details to the LLM.

  • A. Algorithm Framework: LMEA initializes a population, repeatedly generates offspring with LLM-guided selection and genetic variation, and retains the top solutions.Each generation combines the current population with N offspring before selecting the best N solutions for the next generation.
  • A. Algorithm Framework: The LLM performs parent selection, crossover, and mutation in a zero-shot manner through in-context learning and carefully constructed prompts.
  • A. Algorithm Framework: Each prompt contains a problem description and solution properties, in-context examples with fitness values, and explicit task instructions.
  • A. Algorithm Framework: For TSPs, the prompt supplies point coordinates and requires a shortest trace that visits every point exactly once.
  • A. Algorithm Framework: Unlike programmed operators, LMEA gives high-level natural-language instructions and constrains the output format for easy interpretation.Selection outputs and generated solutions use explicit tags such as <selection> and <res>.

C. Self-Adaptation of the LLM’s Temperature

LMEA treats the LLM temperature as a search-exploration parameter and increases it after consecutive generations without improvement. This rule is intended to strengthen exploration when progress stalls.

  • C. Self-Adaptation of the LLM’s Temperature: Higher LLM temperature increases output randomness and exploratory ability, whereas lower temperature makes outputs more deterministic.
  • C. Self-Adaptation of the LLM’s Temperature: If LMEA fails to improve the current best solution for K consecutive generations, it increases temperature by α.The implementation uses K = 20 and α = 0.1, with a default temperature of 1.0.

IV. EXPERIMENTS

The experiments evaluate LMEA on generated EUC-2D TSP instances across two instance types and four problem sizes, comparing performance with traditional heuristics and testing operator and adaptation effectiveness. Test sets contain five instances, with optimality gaps and optimal-solution successes reported.

  • IV. EXPERIMENTS: The experiments ask whether LMEA competes with hand-designed heuristics and whether LLM-driven operators and self-adaptation improve optimization performance.
  • IV. EXPERIMENTS: The study uses EUC-2D TSPs whose nodes lie on a two-dimensional plane and have symmetric pairwise distances.
  • IV. EXPERIMENTS: Two generators create rue instances with uniformly random node placement and clu instances with nodes placed around central nodes.
  • IV. EXPERIMENTS: Table I reports average optimality gaps, generation counts, and numbers of optimal-solution successes for LMEA and OPRO across the eight test sets.N/A indicates that no optimal solution was found for any instance in a test set.
  • IV. EXPERIMENTS: Concorde, an exact TSP solver, supplies optimal solutions for all 40 generated instances.

B. Baseline Algorithms

The study uses traditional TSP heuristics as baseline algorithms, including nearest neighbor and insertion-based methods. These heuristics construct tours by locally choosing the next node or insertion decision.

  • B. Baseline Algorithms: The baselines comprise nearest neighbor and farthest, nearest, and random insertion variants.
  • B. Baseline Algorithms: The nearest-neighbor heuristic starts from a random node and repeatedly appends the nearest node to the current tour endpoint.
  • B. Baseline Algorithms: Insertion heuristics choose a node position that minimizes the insertion cost c(k) = d_i,k + d_k,j − d_i,j.Farthest, nearest, and random insertion differ in how the node to insert is selected.

C. Experimental Setup

The experiments compare LMEA with OPRO and heuristics on TSP test sets using optimality gaps and convergence behavior. LMEA performs strongly on smaller instances, but its optimality gap rises rapidly as problem size increases.

  • N = 16 and G = 250 were used for both LMEA and OPRO.
  • The evaluation reports average optimality gaps across rue/clu test sets and also records generations needed to find optimal solutions.The optimality gap is (len(s*) − opt)/opt.
  • 19 out of 20 rue/clu-10/15 instances received optimal solutions from LMEA within at most 4000 fitness evaluations.The evaluation count follows G × N = 250 × 16 = 4000.
  • On 20-node instances, LMEA was slightly worse than the heuristics except NN, while its optimality gap increased rapidly at n = 25.The paper identifies improving scalability as a crucial direction for future research.
  • Across all eight test sets, LMEA outperformed OPRO, with a larger performance gap as node number increased.Convergence curves indicate that LMEA generally found better solutions more quickly than OPRO.

E. Effectiveness of Self-Adaptation

The self-adaptation mechanism is evaluated by comparing LMEA with LMEA*, a variant without self-adaptation, on rue-20. LMEA achieves better optimality gaps and finds better solutions more quickly.

  • LMEA achieved significantly better optimality gaps than LMEA* on the rue-20 test set.
  • LMEA found better solutions more quickly than LMEA* even when its random initial solutions were worse.
  • The comparison demonstrates the effectiveness of self-adaptation in LMEA.

V. DISCUSSIONS AND CONCLUSION

The paper identifies several directions for extending LMEA, including scalability, cost, learning from unsuccessful solutions, prompt engineering, and application to other problems.

  • Future directions: LMEA currently has limitations in handling relatively large problems, motivating local-part improvements to increase scalability.The paper suggests focusing on improving local parts of solutions rather than the whole solution.
  • Future directions: Learning lessons from incorrect answers is proposed as a way to improve LMEA’s optimization performance.The paper connects this direction to prior evidence that instructing LLMs to learn from unsuccessful solutions can improve performance.
  • Future directions: Running LMEA on a small-scale problem takes around half a day and is highly expensive because of frequent ChatGPT API interactions.Future work could use smaller fine-tuned models locally to reduce runtime and cost.
  • Future directions: State-of-the-art prompt-engineering techniques, including chain of thoughts and self-consistency, may enhance LMEA’s performance.These techniques are identified as potential extensions rather than evaluated results in this passage.
  • Future directions: Applying LMEA to different combinatorial optimization problems remains an open direction for evaluating its broader performance.The paper explicitly calls for investigation on other problem types.
Loading 2310.19046v3…