Source-linked AI summary
Algorithm Evolution Using Large Language Model
Fei Liu, Xialiang Tong, Mingxuan Yuan, Qingfu Zhang
TL;DR
Designing optimization algorithms often requires substantial expert effort, while existing automated approaches may rely on frameworks, training, or solution-level LLM search. AEL evolves algorithms with an LLM, and on TSP it outperforms greedy and directly LLM-generated heuristics while scaling better than a trained domain model.
Problem
Designing effective optimization algorithms typically requires extensive manual effort and domain knowledge, while prior automated methods can require frameworks or training and operator-level LLM optimizers decline on large-scale problems.
Source: §I · p. 1Method
AEL uses an evolutionary framework in which an LLM creates and modifies algorithms treated as individuals, without domain-model training.
Source: §I · p. 2, §VI · p. 9Results
Across TSP problem sizes, AEL outperformed simple greedy and directly LLM-generated algorithms and scaled better than a domain neural model; against Greedy, average gap fell from 17.0% to 6.2% on TSP20 and from 25.2% to 12.8% on TSP1000.
Source: §I · p. 2, 3) Evaluation of Optimized Algorithm · p. 7, §VI · p. 9Takeaways & Limitations
For the demonstrated TSP constructive-method setting, AEL reduces the need for expert knowledge and domain-model training while producing algorithms that scale across problem sizes.
Source: §VI · p. 9
Abstract
from arXiv · showhide
Optimization can be found in many real-life applications. Designing an effective algorithm for a specific optimization problem typically requires a tedious amount of effort from human experts with domain knowledge and algorithm design skills. In this paper, we propose a novel approach called Algorithm Evolution using Large Language Model (AEL). It utilizes a large language model (LLM) to automatically generate optimization algorithms via an evolutionary framework. AEL does algorithm-level evolution without model training. Human effort and requirements for domain knowledge can be significantly reduced. We take constructive methods for the salesman traveling problem as a test example, we show that the constructive algorithm obtained by AEL outperforms simple hand-crafted and LLM-generated heuristics. Compared with other domain deep learning model-based algorithms, these methods exhibit excellent scalability across different problem sizes. AEL is also very different from previous attempts that utilize LLMs as search operators in algorithms.
I. INTRODUCTION
AEL uses an LLM in an evolutionary framework to create algorithms rather than training a domain model; on TSP, it outperforms greedy and directly LLM-generated heuristics.
A. Automatic Algorithm Design (AAD)
- Optimization algorithms often require extensive manual crafting and domain knowledge, while prior automated-design advances can still depend on an underlying framework or manually crafted components.The latter approaches can make the design process time-consuming.Source: §I · p. 1, A. Automatic Algorithm Design (AAD) · p. 2
I. INTRODUCTION
- Learning-based design, AutoML, hyperheuristics, and neural solvers have advanced automatic algorithm design, but often require an algorithm framework or time-consuming domain-model crafting and training.The introduction also lists reinforcement, supervised, transfer, and meta-learning among approaches used to enhance optimization and generate algorithms.Source: §I · p. 1
- AEL outperforms the human-designed greedy heuristic across problem sizes, generalizes better than a trained domain model, and surpasses directly LLM-generated algorithms on TSP.Figure 1 compares gap to baseline by problem size; results are averaged over 64 randomly generated instances.Source: Figure 1 · p. 1, §I · p. 2
- Prior LLM optimization work generates solutions at the operator level, and its performance declines on large-scale problems as solution representations and search spaces grow.The paper distinguishes AEL's algorithm-level evolution from those approaches.Source: §I · pp. 1–2
- AEL treats each algorithm as an individual and uses an evolutionary framework with LLMs to create or modify search strategies, without domain-model training or substantial expert knowledge.The paper demonstrates this approach by designing a constructive heuristic for TSP.Source: §I · p. 2
A. Automatic Algorithm Design (AAD)
- Automatic algorithm design includes approaches that configure, select, or compose algorithms, yet some still rely on a backbone framework or manually crafted components.The paper identifies these dependencies as potentially time-consuming.Source: A. Automatic Algorithm Design (AAD) · p. 2
B. Machine Learning for Optimization
Prior optimization approaches use machine learning, trained models, or LLMs as solution-level operators, while AEL applies LLMs within an evolutionary framework to evolve algorithms for a target problem. Its framework iteratively selects, crosses over, mutates, evaluates, and manages a population of algorithms.
B. Machine Learning for Optimization
- AEL uses machine learning approaches including reinforcement, supervised, transfer, and meta-learning, while end-to-end neural solvers often require substantial domain-model design and training effort.Other directions include surrogate models and genetic programming.Source: B. Machine Learning for Optimization · p. 2
C. Large Language Model (LLM)
- LLMs have shown broad capabilities, including zero-shot performance, but their practical use for designing optimization algorithms remains at an early stage.Source: C. Large Language Model (LLM) · p. 2
D. LLMs for Algorithm Design
- Prior LLM optimization work uses models as operators or optimizers, with poor large-scale generalization attributed to long solution representations and large search spaces.A lightweight operator proposed for continuous optimization is not suitable for combinatorial optimization.Source: D. LLMs for Algorithm Design · pp. 2–3
A. AEL Framework
- AEL evolves algorithms for a target problem rather than seeking better solutions for particular instances, and does so without training new models or using baseline algorithms.Existing automatic design methods may require expensive searches or specific model training.Source: A. AEL Framework · p. 3
- AEL initializes and evaluates a population of algorithms, then iteratively selects individuals and uses LLM crossover and mutation to generate or modify algorithms.New individuals are added and the worst are removed to restore the population size.Source: A. AEL Framework · pp. 3–4
B. Individual Representation
AEL represents each candidate as an algorithm with a natural-language description, formatted code, and a fitness value, then evaluates it across target-problem instances.
B. Individual Representation
- Each AEL individual is a problem-tailored algorithm represented by a natural-language description, a code block, and a fitness value.Source: B. Individual Representation · p. 4
- The code format specifies a standardized class or function, typed inputs, outputs, and hints for viable, innovative responses with limited explanatory text.Source: B. Individual Representation · p. 4
- AEL evaluates individuals by running their algorithms on a set of evaluation instances, unlike traditional evolutionary computing's single-instance objective evaluation.Source: B. Individual Representation · p. 4
C. Initilization
Initialization creates an initial population of algorithms, and the experiments use LLM-generated algorithms to avoid expert knowledge. Prompts specify the task, expected response, and initialization hints.
C. Initilization
- The initial population can use manually crafted algorithms or LLM-generated algorithms; the experiments use LLMs for all initial algorithms to eliminate expert knowledge.Source: C. Initilization · p. 4
- The initialization prompt describes the optimization task and specifies the expected algorithm description and code format.Source: C. Initilization · p. 4
- Initialization-specific hints encourage diverse, novel algorithms and may prompt creativity; the procedure runs N times to generate N initial algorithms.Source: C. Initilization · p. 4
D. Selection
Selection draws individuals from the population, while crossover uses selected parent algorithms to generate new algorithms. Crossover prompts encourage offspring that draw on, yet differ from, their parents.
D. Selection
- Selection randomly chooses l algorithms from the population, and the number selected can scale with the LLM prompt's flexible input capacity, up to its token-size limit.Source: D. Selection · pp. 4–5
E. Crossover
- At iteration j, crossover takes l selected individuals as input and produces a new set of s individuals using an LLM prompt combining the target problem and selected algorithms.Source: E. Crossover · p. 5
- Crossover prompts provide parent algorithm descriptions and code, and ask for offspring motivated by—but distinct from—the parent algorithms.Source: E. Crossover · p. 5
F. Mutation
Mutation uses an LLM to revise an input algorithm, while population management removes low-fitness individuals. In the TSP demonstration, AEL evolves a strategy for choosing the next node in a constructive route.
F. Mutation
- Mutation prompts the LLM with the target problem and one parent algorithm, asking it to revise that algorithm.The prompt combines natural language and code; mutation-specific hints emphasize that the new algorithm should be a revision of its input.Source: F. Mutation · p. 5
G. Population Management
- Population management removes the worst-fitness individuals to reduce the population from (s + 1)N to N.Source: G. Population Management · p. 5
IV. DEMONSTRATION ON TSP
- For TSP, AEL uses a constructive framework that builds a route step by step by selecting the next node.AEL's task is to create a novel, competitive next-node selection algorithm.Source: §IV · p. 5
A. AEL Implementation
AEL is a general algorithm-design framework that needs problem-specific individual representations and prompts. For TSP, each individual combines an algorithm description, executable code, and a fitness value.
A. AEL Implementation
- AEL is a general framework that requires problem-specific individual representations and prompts for initialization, crossover, and mutation.Source: A. AEL Implementation · p. 5
1) Individual Representation:
- Each TSP individual contains a natural-language algorithm description, a Python next-node function, and a fitness value based on its average gap to Gurobi across 64 size-50 instances.The function takes the current node, destination node, unvisited nodes, and distance matrix as inputs and returns the next node.Source: 1) Individual Representation · p. 5, Figure 3 · p. 5
2) Prompt Engineering for Initialization, Crossover, and Mutation:
- Prompts share a task description and expected-output format, while crossover and mutation include parent algorithms and ask for inspired or modified strategies.Initialization instead requests a completely new algorithm; additional hints encourage innovation and discourage extra explanation.Source: 2) Prompt Engineering for… · p. 6
1) Experimental Settings:
The experiments evaluate AEL on TSP using a constructive next-node selection task and compare it with existing algorithm-design approaches. The setup evaluates algorithms against Gurobi and uses prompts tailored to the evolutionary stages.
1) Experimental Settings:
- Each algorithm is evaluated on 64 randomly generated TSP50 instances, with fitness measured as the average gap to Gurobi's optimal solution.Source: 1) Experimental Settings · p. 6
- The reported settings list population size N=10, number of population Ng=10, two parent individuals l=2, and one offspring individual s=1, without identifying them specifically as crossover counts.Source: 1) Experimental Settings · p. 6
- The comparison covers AEL, a human-designed greedy algorithm, and a trained domain model within the same step-by-step constructive framework.The authors note that AEL could also be applied within other advanced frameworks.Source: 1) Experimental Settings · p. 6
- The TSP prompts address task description, parent algorithms, prompt-specific hints, expected output, and other hints.The prompt examples specify a function that selects the next node from the current node, destination, unvisited nodes, and distance matrix.Source: Figure 4 · p. 6, 1) Experimental Settings · p. 6
2) Experimental Results:
On TSP50, GPT-4 AEL's objective values converge as evolution proceeds, and its best algorithm beats the greedy heuristic by the end. That algorithm uses a multi-factor scoring rule with a threshold fallback.
2) Experimental Results:
- From 20% to around 12% optimal gap, GPT-4 AEL nearly converges in 10 generations and beats the greedy algorithm by evolution's end.The best first-population algorithm was close to the greedy algorithm.Source: 2) Experimental Results · p. 7
- The best evolved algorithm scores unvisited nodes using distance, mean distance, and standard deviation, with a threshold fallback that chooses the closest node when the minimum score exceeds the threshold.The scoring system gives higher weight to close node clusters by incorporating standard deviation.Source: 2) Experimental Results · p. 7
- The evolved algorithm is more complex than the greedy heuristic, with a threshold and four hyperparameters developed through 100 LLM interactions.The authors note that designing this strategy would require substantial trial and error even for an expert.Source: 2) Experimental Results · p. 7
3) Evaluation of Optimized Algorithm:
On TSP instances from 20 to 1000 locations, AEL’s constructive algorithms outperform the greedy heuristic and directly prompted LLM algorithms, and generalize better than a domain model across problem sizes. The comparison uses a basic constructive heuristic framework.
3) Evaluation of Optimized Algorithm:
- Average gaps fall from 17.0% to 6.2% on TSP20 and from 25.2% to 12.8% on TSP1000, with AEL outperforming greedy across all problem sizes.The reported comparisons describe the average gap as reduced by half.Source: 3) Evaluation of Optimized Algorithm · p. 7
- AEL generalizes better than the domain model trained on TSP50, whose average gap rises from less than 1% to over 50% on large problems.The domain model does better than AEL near its training size, but its performance deteriorates on large-scale problems.Source: 3) Evaluation of Optimized Algorithm · p. 7
- The best directly prompted LLM algorithm is competitive with greedy but inferior to AEL; GPT-4’s best gap is worse than GPT-3.5-turbo’s.The authors suggest GPT-4’s greater innovativeness and randomness may make some directly generated algorithms considerably worse.Source: 3) Evaluation of Optimized Algorithm · pp. 7, 9
- The comparison uses a basic constructive heuristic framework, although more complex algorithms can generate near-optimal TSP solutions.The authors note that advanced frameworks could be integrated in future work.Source: 3) Evaluation of Optimized Algorithm · p. 9
- For TSP100, TSP500, and TSP1000, AEL routes show fewer intersections and shorter total distances than greedy, and GPT-4-based AEL outperforms GPT-3.5-turbo-based AEL.The visual compares routes; its nodes are locations, blue lines are routes, and red nodes mark the start and end.Source: Figure 7 · p. 8, 3) Evaluation of Optimized Algorithm · p. 9
C. Created Algorithms or Spliced Algorithms
The authors report that most AEL-created algorithms cannot be found on the web or in publications, while identifying prompt design as the main workload and outlining extensions to the framework. Their TSP conclusion reports strong comparisons across sizes, within the constructive-method setting.
C. Created Algorithms or Spliced Algorithms
- Most algorithms created in AEL cannot be found on the web or in publications, and the authors say AEL stimulates novel algorithms by combining evolutionary computing with LLMs.They acknowledge it remains debatable whether LLMs create knowledge or recombine existing information.Source: C. Created Algorithms or Spliced… · p. 9
D. Less/No Expert Knowledge
- AEL requires minimal expert knowledge; its primary workload is designing natural-language prompts for each component of the target problem.The authors describe this prompt format as accessible to algorithm designers from diverse backgrounds.Source: D. Less/No Expert Knowledge · p. 9
V. FUTURE WORKS
- Future work proposes adding external tools and optimization information, decomposing complex problems, hierarchical algorithm-and-code evolution, refinement, and multi-objective optimization.The authors state that more information may support more powerful algorithms and that multi-objective AEL could find tradeoff algorithms.Source: §V · p. 9
VI. CONCLUSION
- On TSP sizes 20–1000, AEL outperforms hand-crafted greedy and directly prompted LLM algorithms, and scales better across sizes than a trained domain neural model.These results are demonstrated for the constructive method for TSP; the authors suggest advanced frameworks could yield more powerful algorithms.Source: §VI · p. 9