PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap

Xingyu Wu, Sheng-hao Wu, Jibin Wu, Liang Feng, Kay Chen Tan

arXiv:2401.10034v3cs.NEcs.AIcs.CL

TL;DR

This paper reviews how LLMs and EAs can address limitations in each other while pursuing complex optimization and AI tasks. It organizes the literature into LLM-enhanced EA, EA-enhanced LLM, and integrated applications, and identifies progress alongside challenges in complex and large-scale optimization.

  • Problem

    EAs offer global search but may require many steps because they lack task-related knowledge, while LLMs still struggle with complex and large-scale optimization problems.

  • Method

    The paper provides a comprehensive review and roadmap organized around LLM-enhanced EA, EA-enhanced LLM, and integrated LLM–EA applications.

  • Results

    The reviewed studies demonstrate LLM-assisted optimization for small-sized single-objective and multi-objective problems and collaborative advances in NAS, code generation, software engineering, and generation tasks.

  • Takeaways & Limitations

    LLMs can contribute domain knowledge, text understanding, and generation to EA search, while EAs can optimize LLM prompts and architectures under black-box settings.

  • Takeaways & Limitations

    Current evaluations and applications remain constrained by LLM context abilities, especially for high-dimensional, constrained, precise, large-scale, and complex tasks.

Abstract

from arXiv · show

Large language models (LLMs) have not only revolutionized natural language processing but also extended their prowess to various domains, marking a significant stride towards artificial general intelligence. The interplay between LLMs and evolutionary algorithms (EAs), despite differing in objectives and methodologies, share a common pursuit of applicability in complex problems. Meanwhile, EA can provide an optimization framework for LLM's further enhancement under black-box settings, empowering LLM with flexible global search capacities. On the other hand, the abundant domain knowledge inherent in LLMs could enable EA to conduct more intelligent searches. Furthermore, the text processing and generative capabilities of LLMs would aid in deploying EAs across a wide range of tasks. Based on these complementary advantages, this paper provides a thorough review and a forward-looking roadmap, categorizing the reciprocal inspiration into two main avenues: LLM-enhanced EA and EA-enhanced LLM. Some integrated synergy methods are further introduced to exemplify the complementarity between LLMs and EAs in diverse scenarios, including code generation, software engineering, neural architecture search, and various generation tasks. As the first comprehensive review focused on the EA research in the era of LLMs, this paper provides a foundational stepping stone for understanding the collaborative potential of LLMs and EAs. The identified challenges and future directions offer guidance for researchers and practitioners to unlock the full potential of this innovative collaboration in propelling advancements in optimization and artificial intelligence. We have created a GitHub repository to index the relevant papers: https://github.com/wuxingyu-ai/LLM4EC.

I. INTRODUCTION

LLMs and EAs pursue broad applicability through complementary strengths: LLMs provide knowledge and generation, while EAs provide black-box global search. The survey organizes their interaction around LLM-enhanced EA and EA-enhanced LLM.

  • Complementary strengths: LLMs and EAs share a focus on applicability across diverse scenarios rather than only maximizing performance on specific domain problems.LLMs learn unified task handling from extensive data, while EAs depend less on problem-specific characteristics than traditional optimization methods.
  • Complementary strengths: EAs can address LLM limitations arising from black-box operation, one-shot search, and dependence on prompts and training data.The paper identifies prompt optimization and neural architecture search as black-box settings where EAs can provide iterative global exploration.
  • Research directions: The paper presents an integrated framework for research combining LLMs and EAs.The supplied figure caption identifies the framework as general and integrated.
  • Complementary strengths: LLMs can guide EA search with domain knowledge, potentially helping evolutionary methods converge faster when task-related knowledge is scarce.The passage specifically describes LLM guidance as valuable during the early search stage.
  • Research directions: The survey frames reciprocal collaboration through LLM-enhanced evolutionary optimization and EA-enhanced LLM optimization.LLMs can act as evolution operators or generate code for EA improvement, while EAs can optimize prompts and LLM architectures.

3) Applications Driven by Integrated Synergy of LLM and EA:

The paper surveys how LLMs and EAs are combined across optimization and application domains, organizing methods by their complementary roles and identifying challenges for future work. It highlights LLM-assisted black-box optimization alongside applications such as code generation, software engineering, NAS, and text generation.

  • Integrated applications: The reviewed collaboration spans NAS, code generation, software engineering, text generation, and other generative task domains.The paper presents these areas as application scenarios influenced by combined LLM and EA advances.
  • Survey scope: The survey reviews cross-disciplinary LLM–EA research, classifies it into three categories, and analyzes existing methods, applications, strengths, weaknesses, and challenges.The authors describe the review as the first comprehensive and up-to-date survey focused specifically on EA research in the LLM era.
  • LLM-assisted black-box optimization: LLMs can serve as black-box search operators that generate successive solutions for single-objective and multi-objective optimization.The paper reports validated optimization ability primarily on small-sized problems and describes iterative improvement through prompts containing prior solutions and values.
  • LLM-assisted black-box optimization: LLM-driven evolutionary methods can use language models for crossover, mutation, parent selection, or offspring generation within EA frameworks.LMEA uses LLMs for crossover and mutation and constructs generation-specific prompts for selecting parents; another method uses a fine-tuned LLM to generate 10% of offspring.

2) Multi-objective optimization:

LLMs have been integrated into multiobjective evolutionary optimization as search operators, evaluators, and offspring generators. Early evidence suggests efficiency benefits, but complex real-world problems remain challenging.

  • LLMs generate offspring for multiobjective subproblems through prompt engineering and in-context learning.
  • LLMs can evaluate solution quality and diversity in quality-diversity search instead of relying on manually designed evaluations.
  • A fine-tuned LLM generates 10% of offspring to accelerate population convergence.
  • LLM-guided evolution outperforms random optimization in efficiency and can achieve efficiency comparable to manually designed genetic operators.
  • High-dimensional, constrained, and precision-demanding problems can exceed LLM context abilities, while current evaluations consider limited factors.
  • LLM-based algorithm generation and hybrid optimization methods extend LLM assistance beyond direct evolutionary operators.

2) Iterative Generaiton:

Iterative generation uses evolutionary optimization to refine algorithms and code, with LLMs manipulating or generating algorithmic representations. The approach has expanded across domains but faces practical efficiency and problem-complexity constraints.

  • Iterative Generaiton: Evolutionary algorithms iteratively refine algorithms by using LLMs as operators that directly manipulate code text.
  • Iterative Generaiton: Self-Referential EA Distillation generates search-distribution updates from population members, fitnesses, and search-distribution statistics.
  • Iterative Generaiton: LLM algorithm-generation research leverages algorithm comprehension, representation, and generation to enhance evolutionary algorithms at the algorithmic level.
  • Iterative Generaiton: Practical challenges include intricate problem descriptions, large numerical inputs, and time-intensive interactions.
  • Iterative Generaiton: OptiChat diagnoses infeasible optimization models by identifying constraints that cannot be satisfied simultaneously.
  • Iterative Generaiton: LLMs can provide explanations and visualizations for genetic-programming results in nonlinear dimensionality reduction.
  • Iterative Generaiton: The reviewed EA-enhanced LLM direction focuses on prompt engineering and neural architecture search.

A. EA-based Prompt Engineering

EA-based prompt engineering optimizes textual and continuous prompts for black-box or closed-source LLMs. The surveyed methods include evolutionary prompt search, multiobjective instruction optimization, and gradient-free soft-prompt tuning.

  • A. EA-based Prompt Engineering: Black-box prompt engineering adjusts prompts without access to model parameters or gradients, supporting optimization of closed-source LLMs.
  • A. EA-based Prompt Engineering: Evolutionary prompt engineering includes discrete textual optimization and continuous numerical-vector optimization.
  • 1) Textual Prompt Optimization:: Earlier methods applied greedy search or genetic algorithms to prompt engineering in pretrained language models.
  • 1) Textual Prompt Optimization:: EvoPrompt uses LLM-simulated crossover and mutation while an EA retains the best candidate prompts.
  • 1) Textual Prompt Optimization:: PromptBreeder automatically evolves task prompts and mutation prompts from problem descriptions using diverse mutation operators.
  • 1) Textual Prompt Optimization:: InstOptima applies NSGA-II to optimize instruction performance, length, and perplexity as multiple objectives.
  • 2) Gradient-Free Soft Prompt Optimization:: BBT optimizes continuous prompt vectors with limited samples without gradient-based model-performance optimization.
  • 2) Gradient-Free Soft Prompt Optimization:: BBTv2 adds prompt vectors across hidden layers, while Clip-Tuning uses dropout-sampled subnetworks for finer evaluation feedback.

3) Prompt Generation for Data Augmentation:

The review covers EA-based prompt generation, security applications, and evolutionary search for LLM architectures. Across these areas, EAs automate exploration, while LLMs contribute generation, knowledge, or evaluation capabilities.

  • 3) Prompt Generation for Data Augmentation:: Evol-Instruct uses manually written seed instructions and an LLM instruction evolver to iteratively generate enhanced instruction data.
  • 4) Prompt Generation for LLM Security:: AutoDAN models jailbreak generation as an optimization problem, using an initialized population, a text-suitable adaptive function, and hierarchical genetic search.
  • 4) Prompt Generation for LLM Security:: EA-based prompt engineering supports discrete and continuous prompt optimization, data augmentation, and LLM security applications.The review identifies initial-population selection, search-space expansion, and method stability as continuing challenges.
  • B. EA-based LLM Architecture Search: EA-based LLM architecture search automates otherwise laborious design through mutation, crossover, and selection, balancing exploration with exploitation.Reviewed applications include new backbones, hidden-unit dimensions, and architecture hyperparameters.
  • B. EA-based LLM Architecture Search: AutoBERT-Zero searches for a universal LLM backbone from scratch using primitive mathematical operations, convolution blocks, and an Operation-Priority evolution strategy.
  • B. EA-based LLM Architecture Search: EA-based NAS has been applied to LLM architecture hyperparameters, including hidden-state dimensions, attention heads, and feedforward-network dimensions.AutoTinyBERT simplifies its search by using identical layer depths and dimensions.
  • B. EA-based LLM Architecture Search: The “Set of Sets” concept uses multiobjective multi-task EAs to obtain smaller specialized models satisfying multiple task and resource constraints.The resulting models can achieve better performance or higher compression rates than the original large model in reported applications.
  • B. EA-based LLM Architecture Search: The review identifies high time consumption and limited generalization ability as unresolved challenges for EA-assisted LLM architecture search.

C. EA Empowering LLM for Other Enhanced Capabilities

The review describes EA assistance for improving LLMs beyond prompt optimization and NAS. Examples include resource-adaptive inference and evolutionary optimization of model-related parameters.

  • EA search can assist LLM improvement beyond neural architecture search by optimizing additional model capabilities.
  • LengthDrop trains Transformers to tolerate layer-wise sequence-length reduction, after which an EA optimizes settings under computational resource constraints.
  • EA search optimizes rescaling factors and initial positions so different dimensions and positions receive different interpolation or extrapolation degrees.This preserves original positional information better than uniformly rescaling all dimensions, according to the reviewed study.

A. Code Generation

Integrated LLM–EA methods combine LLM code understanding and generation with EA search to expand and improve code-generation workflows. The review describes evolutionary mutation, reward design, contextual prompting, and broader applications.

  • A. Code Generation: LLMs learn programming concepts from source code, while EAs search program spaces; their combination addresses limitations of learned distributions and traditional mutation operators.
  • A. Code Generation: ELM combines MAP-Elites with LLM-based intelligent mutation, using hand-written program seeds to generate functionally rich programs as design examples.The LLM-based mutation operator is intended to improve genetic-programming search efficiency.
  • A. Code Generation: LLM–EA collaboration has been applied to data cleaning, reinforcement-learning reward design, AI accelerator design, scientific discovery, adversarial attacks, and network criticality evaluation.
  • A. Code Generation: EUREKA tracks reward-component values during reinforcement-learning training and converts their changes into reward-feedback text.
  • A. Code Generation: GPT4AIGChip uses a demo-augmented prompt generator to select two relevant demonstrations and add them as contextual information for code generation.

3) Security in Code Generation:

The review extends integrated LLM–EA methods to generated-code security, software optimization, testing, and project planning. These applications use LLM generation or understanding within evolutionary search processes.

  • 3) Security in Code Generation:: DeceptPrompt uses a genetic algorithm to optimize natural-language prefixes and suffixes that induce functionally correct code containing specified vulnerabilities.
  • LLM–EA methods have been applied in software engineering to software optimization, software testing, and software project planning.
  • 1) Software Optimization:: LLM-assisted Genetic Improvement generates code mutations for objectives such as time efficiency and memory consumption, then evolves candidate code until termination.
  • 1) Software Optimization:: Treating LLM suggestions as additional mutation operators enriches Genetic Improvement’s search space and can support functional bug fixes or non-functional improvements.
  • C. Neural Architecture Search (NAS): In NAS applications, EAs provide search frameworks while LLMs contribute representation, generation, and prior-knowledge capabilities.

1) With Representation Capability of Fine-tuned LLM:

LLMs and EAs are combined in neural architecture search by using language models to represent, generate, predict, or modify architectures within evolutionary search processes. These approaches extend beyond LLM architecture search to broader NAS tasks.

  • Representation and search: GPT-NAS encodes neural architectures for a pretrained and fine-tuned GPT model, then uses crossover and mutation to optimize architectures.The fine-tuning data introduces neural-architecture prior knowledge into the evolutionary search.
  • Representation and search: LLMatic searches neural-network code rather than direct structural representations, combining network and prompt archives with quality-diversity algorithms.The archives store trained networks, prompts, and temperature parameters used to generate networks.
  • Evolutionary operators: CodeGen performs evolutionary crossover and mutation by modifying selected networks or partially matching multiple networks according to operation-specific prompts.PALM is described as a similar crossover-and-mutation approach.
  • Prediction and selection: ReStruct uses LLM-based performance prediction and selection suggestions within a genetic algorithm to optimize meta-structure populations.Its explanation module uses chain-of-thought prompting to obtain semantically explainable meta-structures.
  • Broader applications: Synergistic LLM-EA methods have influenced NAS, code generation, software engineering, and text generation, while combining generative and search capabilities.The reviewed NAS methods are presented as more versatile than approaches limited to searching LLM architectures.

1) Text Generation:

LLM-EA collaboration applies language-model generation and evolutionary search across text, image, molecular, and social-science tasks. The reviewed studies report progress by combining LLM prior knowledge or generation with evolutionary optimization.

  • Text Generation: News-summary generation uses LLMs to extract event patterns and genetic algorithms to evolve and select informative event-pattern pools.The event-pattern representation captures key information, relationships, and characteristics of events.
  • Image Generation: StableYolo jointly optimizes Stable Diffusion prompts and model hyperparameters with evolutionary search using YOLO recognition confidence as a fitness function.The optimization repeatedly searches for prompts and settings that maximize image quality.
  • Molecular Generation: GPT-3.5 fragmented molecules at rotatable bonds with a 70% success rate and produced chemically reasonable recombinations more often than random recombination.The molecules were represented as SMILES strings.
  • Social Science: LLMs and EAs were also applied to model evolutionary dynamics in social populations involving conflicts of interest, personality traits, and behavioral strategies.LLMs made trait expressions more complex and higher-order before mapping them to behaviors in an agent-based model.
  • Overall progress: Across these generative domains, researchers combine LLM generative ability with EA search ability to produce improved results using prior knowledge and text understanding.The paper characterizes this collaboration as advancing generative modeling and related fields.

V. ROADMAP AND FUTURE DIRECTIONS

The roadmap identifies future work in methods, theory, and applications, emphasizing practical limitations in complex optimization, robust prompt engineering, multimodal search, and domain-knowledge integration. It also calls for better interpretation, evaluation, and search strategies.

  • LLM-assisted EA for Complex & Large-scale Optimization: LLM optimization remains practical mainly for small-scale numerical problems, while high-dimensional, constrained, high-precision, and poorly evaluated settings remain challenging.The paper also notes limited interpretability and uncertainty about whether optimization ability reflects reasoning or randomness.
  • LLM-assisted EA for Complex & Large-scale Optimization: Future studies should improve LLM behavior interpretation, optimization evaluation, information use, and methods for solving complex problems.Suggested analyses include internal attention mechanisms and the relationship between temperature settings and exploration.
  • LLM for Evolutionary Optimization: Multimodal LLMs could support cross-domain EAs by enabling cross-modal crossover and mutation through prompts or examples linking different modalities.The proposed applications include image captioning and text-to-image generation.
  • LLM for Evolutionary Optimization: LLM domain knowledge could provide initial solutions, improve problem formulation, and guide algorithm design for multi-objective, discrete, and dynamic problems.The paper frames this knowledge transfer as a route toward better optimization efficiency or optimality.
  • Robust and Stable Prompt Engineering: Prompt-evolution methods face initialization sensitivity, exponentially growing search spaces, overfitting or local optima, instability, and dependence on LLM capabilities.Proposed directions include multi-source initialization, adaptive evolution, human feedback, internal-representation analysis, and stable prompt optimization.

D. Theoretical Study for Specific LLM+EA Methods

The paper calls for theoretical analysis of specific LLM-EA methods alongside broader studies of their interaction, code-generation limits, and applications. Key targets include convergence, complexity, problem modeling, and strategies for complex tasks.

  • Theoretical Study for Specific LLM+EA Methods: Small-scale empirical studies support LLM-EA effectiveness, but the incentives behind their interaction remain unclear and require larger empirical and theoretical investigations.The paper specifically calls for analyzing complementary advantages and existing issues.
  • Theoretical Study for Specific LLM+EA Methods: Theoretical work can analyze convergence and complexity by studying optimality, local optima, parameter effects, and time and space costs.These analyses concern algorithms that combine LLMs and EAs.
  • Theoretical Study for Specific LLM+EA Methods: Optimization-theoretic modeling should characterize objectives, constraints, feasible solution spaces, and search strategies for specific LLM-EA problems.The paper identifies search-strategy design as central to improving combined-method performance.
  • Generalized Code Generation for Complex Task: LLM-EA code-generation research supports downstream software engineering and evolutionary-algorithm design but may lack sufficient training-data diversity and scale.The paper notes that generated data may not cover all possible use cases.
  • Generalized Code Generation for Complex Task: Complex algorithmic logic can require multiple code snippets, yet LLMs struggle to generate large code collections under input-output length limits.The paper suggests modular decomposition or interactive user-guided task decomposition as mitigations.

F. Generalized or Universal NAS

The paper frames LLM–EA collaboration as useful for NAS and broader higher-level tasks, while identifying efficiency, evaluation, and generalization challenges that future work should address.

  • F. Generalized or Universal NAS: LLM prior knowledge about network architectures and code generation can help EAs discover neural architectures more efficiently.The paper presents NAS as a vital application scenario for their collaboration.
  • F. Generalized or Universal NAS: NAS methods combining LLMs and EAs still face high time consumption and integration-specific challenges.The paper distinguishes challenges common to EA-based NAS from issues introduced by LLM integration.
  • F. Generalized or Universal NAS: Future NAS research should fairly evaluate different LLMs, improve fine-tuning, reuse historical search knowledge, and define search spaces for LLMs.These directions target application scope, generalization, solution quality, and search efficiency.
  • G. Applications and Innovations in Higher-level Tasks: At higher task levels, LLMs can analyze related projects to provide EA search spaces and support knowledge transfer across projects.The paper gives repository-level software engineering as an example of techniques functioning as submodules in broader tasks.
  • VI. CONCLUSION: The review organizes the field into LLM-enhanced EA, EA-enhanced LLM, and integrated applications across NAS, code generation, software engineering, and text generation.It also notes that existing LLMs do not directly handle complex, large-scale optimization but can generate algorithms and evaluate optimization results.
Loading 2401.10034v3…