LLM-Driven Configuration of Genetic Algorithms for Constraint-Rich Optimization Problems
TL;DR
A framework that combines large language models (LLMs) for problem understanding with a structured Biased Random-Key Genetic Algorithm (BRKGA) configurator for algorithm realization is presented, allowing users to describe optimization problems in natural language and receive executable GPU-accelerated GA implementations.
Abstract
Configuring genetic algorithms (GAs) for new optimization problems typically requires substantial expertise in representation design, decoder construction, and constraint handling. We present a framework that combines large language models (LLMs) for problem understanding with a structured Biased Random-Key Genetic Algorithm (BRKGA) configurator for algorithm realization, allowing users to describe optimization problems in natural language and receive executable GPU-accelerated GA implementations. We compare two workflows: LLM-Only, where the LLM generates a complete standalone GA from the problem description; and LLM+Config, where the LLM is restricted to problem parsing and decoder synthesis against a fixed brkga3 interface that provides the evolutionary architecture, Adaptive Large Neighborhood Search (ALNS) warm-start, GPU-parallel segmented sort, and bottleneck-focused local search. We evaluate on three problem families (the Traveling Salesperson Problem (TSP), the Traveling Salesperson Problem with Job-times (TSPJ), and the Vehicle Routing Problem with Resource Pick-up and Delivery (VRP-RPD)) on instances up to 999 nodes. LLM+Config outperforms or matches LLM-Only on every instance where both workflows produced a result, and additionally solves four TSP instances on which LLM-Only failed (Wilcoxon signed-rank with Holm correction across the three problem families, all adjusted p ≤ 0.012); on TSPJ it matches CPLEX optimal on 3 of 10 benchmarks and establishes first reported results for 6 large instances (n = 202–1,000); on VRP-RPD it wins all 13 instances against LLM-Only with 51–329 % advantage on large instances. GPU-parallel BRKGA evolution runs 25–35× faster per generation than a single-threaded CPU baseline. We characterise LLM stochasticity through two complementary studies: 15 sessions across 3 problems with one model (80% success rate), and 100 sessions across 10 LLMs from 3 providers on TSPJ/eil101 (Friedman and Wilcoxon-Holm tests on within-tier and within-provider blocks), finding that capability tier dominates over provider at the large tier and that small-tier non-Anthropic models contribute zero usable sessions.