← Home
Evolutionary computation
Rough reading notes on ten papers: five that the field is built on, and five that put a language model in the mutation slot. These are my own summaries, so check the papers before trusting any detail.
-
Problem
- Black-box minimization of a function of n real variables. The only information is the function value at points I choose, and cost is counted in function evaluations.
- Aimed at landscapes where quasi-Newton or conjugate gradient methods break: non-convex, rugged, noisy, with local optima. The hard cases it targets are ill-conditioned and non-separable functions, where variables are badly scaled and interact.
How it works
- Each generation samples the population from a multivariate normal with three parts: a mean, one overall step size, and a covariance matrix that sets the shape.
- The new mean is a weighted average of the best-ranked samples, with better ranks getting more weight. Only the ranking of function values is used, never the values.
- The covariance gets two updates added together. The rank-mu update uses all the selected steps of the current generation. The rank-one update uses an evolution path, a fading sum of the mean's recent moves, so the sign and correlation of consecutive steps are not thrown away.
- Step size is adapted separately with a second evolution path. If the path is shorter than it would be under random selection, steps are cancelling out and the step size shrinks. If it is longer, steps agree and it grows. The stated reason for the separate rule: the largest safe learning rate for the covariance is too slow to change the overall scale.
Results
- It is a tutorial, not a results paper. What it gives is claims with derivations. Main one: learning the covariance is like learning the inverse Hessian in a quasi-Newton method, and can cut evaluations by orders of magnitude on ill-conditioned or non-separable problems.
- Stated invariances: to any order-preserving transformation of the function values, to rotation of the search space, and (if the starting distribution is transformed to match) to any invertible linear transformation.
- The population can be small. The default is about 4 + 3 ln n, and the text says the learning rates keep the covariance from degenerating even at a population of 9.
Limits and open questions
- Step size control stops the population collapsing early, but the tutorial says outright that it does not stop the search ending in a local optimum. The advice is a bigger population or restarts with a growing population, at the price of slower convergence.
- The best exponent for the covariance learning rate in high dimension is called an open question in the text.
- It assumes a real-valued vector. I do not see how the covariance idea carries over to search spaces made of programs or text.
Why I care
- This is the case where the proposal distribution is fully written down: mean, step size, covariance, and an explicit rule for changing each. A language model used as the mutation step is also a distribution over candidates, but nobody can write its parameters down and usually nothing updates it between generations except the prompt.
- One design test I want to borrow: under random selection the distribution parameters should not drift. I would like to know what the analogue of that check is for an LLM proposer.
-
Problem
- Multi-objective optimization: one run should return a spread of trade-off solutions along the Pareto front, not a single optimum.
- Earlier non-dominated sorting GAs had three complaints against them: sorting cost of O(MN³) for M objectives and population N, no elitism, and a sharing parameter that had to be set by hand.
How it works
- Fast non-dominated sort. For each solution, count how many others dominate it and list the ones it dominates. Solutions with count zero are front 1. Remove them, decrement the counts, repeat. Cost is O(MN²).
- Crowding distance replaces the sharing parameter. Within a front, sort by each objective and add up the normalized gap between each solution's two neighbours. Selection then prefers lower front rank, and inside the same front the solution in the less crowded region.
- Main loop: make N offspring by binary tournament, crossover and mutation. Pool them with the N parents, sort the 2N, fill the next population front by front, and cut the last front that does not fit by crowding distance. Elitism falls out of the pooling.
- Constraints are handled by changing the definition of dominance. A feasible solution beats an infeasible one, two infeasible ones are compared on total constraint violation, two feasible ones on the usual rule. No penalty parameter.
Results
- Nine two-objective test problems (SCH, FON, POL, KUR, ZDT1 to ZDT4, ZDT6), 25,000 function evaluations each, against PAES and SPEA.
- Spread: NSGA-II was best on all nine. Convergence: best on seven. PAES got closer to the true front on ZDT3 and ZDT6.
- Constrained version against the Ray-Tai-Seow method on four problems (CONSTR, SRN, TNK, WATER). Better convergence and spread reported. WATER is the five-objective, seven-constraint one.
Limits and open questions
- They built a rotated problem where the variables are coupled. NSGA-II gets closer to the front than the other two, but the paper admits this kind of linkage is hard for all of them and needs more systematic study.
- NSGA-II parameters were not tuned. On ZDT4 the real-coded version gets stuck on local fronts with the default settings, and the authors suspect ZDT6 needs different settings too.
- Open question for me: every unconstrained test has two objectives and the largest problem has five. What happens to dominance ranking when there are many more?
Why I care
- The survival step here does not care how candidates were made. If I score LLM-proposed candidates on more than one thing, this sort plus crowding rule could sit behind the proposer unchanged. It also keeps diversity without a tuned parameter, which is one less knob to confuse with proposer effects.
-
Problem
- Should evolution change a network's topology as well as its weights? The evidence at the time said maybe not: a fixed-topology method (ESP) had solved the hardest pole balancing benchmark 5 times faster than Cellular Encoding, which evolves structure.
- The paper names what makes evolving structure hard: crossover between networks of different shape has no obvious alignment, and a new structure usually lowers fitness before its weights are tuned, so it dies before it can pay off.
How it works
- A genome is a list of connection genes. Each has an in node, out node, weight, an enable bit and an innovation number.
- The innovation number comes from a global counter that goes up whenever a structural mutation creates a new gene, and it is inherited unchanged. To cross two genomes, line up genes with the same number. No graph matching needed.
- Speciation: a compatibility distance built from how many genes fail to match plus weight differences. A genome joins the first species whose representative is within a threshold. Fitness is shared inside a species, so no single species can take over.
- Everyone starts with no hidden nodes, inputs wired straight to outputs. Add-node and add-connection mutations grow structure, and it only survives if it helps.
Results
- XOR sanity check: solved in 32 generations on average (4,755 networks evaluated), with 2.35 hidden nodes on average.
- Double pole balancing with velocity inputs: 3,600 evaluations against 3,800 for ESP, which is not a significant difference. NEAT's solutions used 0 to 4 hidden nodes where the fixed-topology methods used 10.
- Double pole balancing without velocities, the hard version: 33,184 evaluations against 169,466 for ESP and 840,000 for Cellular Encoding, averaged over 20 runs. ESP needed about four restarts per solution and NEAT needed none.
- Ablations on the easier pole task, where full NEAT takes 3,600 evaluations and never fails. No growth: fails 80% of runs. No speciation: fails 25% and is about 7 times slower. Random starting topologies: about 7 times slower. No crossover: 5,557 evaluations.
Limits and open questions
- The evidence is XOR plus pole balancing. On the easier pole task NEAT only ties ESP. The advantage shows up on the harder one.
- Historical markings are never ablated, because speciation and crossover both depend on them. So that piece is argued, not measured.
- Whether growing from minimal structure scales to large networks is not something this paper answers.
Why I care
- Speciation is the part I keep coming back to. A new idea usually scores worse at first, so any search loop needs a way to give it time. In the no-speciation ablation the population converged on whatever topology was best at the start within about 10 generations. I would expect an LLM-driven loop that only keeps top scorers to do the same thing to a program that was just restructured.
-
Problem
- Most search algorithms return one best solution. Sometimes the useful answer is the best solution at every combination of some features I care about. The paper calls this illumination, as opposed to optimization.
- It also points at a known failure of ordinary evolutionary runs: within one run the population piles onto one peak, and variety only shows up across separate runs.
How it works
- I choose a performance measure and N feature dimensions, plus a function that maps any solution to its feature values. Each dimension is cut into bins, giving a grid.
- Start by generating G random genomes, evaluating them, and dropping each in its cell. Keep the best one per cell.
- Loop: pick an occupied cell at random, copy its genome with a random change, evaluate, find the cell the child lands in. It is stored if that cell is empty or the child beats the occupant.
- The search happens in genome space. There is no way to ask for a cell directly, since nobody knows ahead of time which genome lands where, and some cells may be impossible to fill. The experiments use a version that starts with coarse cells and subdivides them.
Results
- Neural networks on a retina task, features are connection cost and modularity. Against a plain EA, novelty search with local competition, and random sampling, 20 runs each: MAP-Elites is higher on all four measures (best single solution, reliability, precision, coverage) at p < 1e-7.
- It beats the plain EA even on best single solution. The authors' reading is that the task is deceptive and the EA has no pressure for diversity. Tracing lineages shows elites descending through long paths across the map, so other cells act as stepping stones.
- Simulated soft robots, features are share of bone material and share of voxels filled: better reliability and coverage than an EA and an EA with a diversity term, p < 0.002.
- A real soft robot arm with a one-dimensional feature (64 cells) and 640 evaluations per run: better than random sampling and grid search in the harder parts of the range, but no statistics are given for this one.
Limits and open questions
- The authors say plainly that the data are preliminary and ask readers not to conclude anything firm yet. A comparison with one earlier method is only anecdotal in this draft.
- The feature space is fixed up front. New kinds of cells cannot appear during a run, so by the authors' own account it cannot be open-ended.
- The catch for a user: someone has to choose the feature dimensions and the grid resolution, and the map is only as useful as that choice.
Why I care
- The map is the obvious memory for an LLM-proposer loop: parents drawn from different cells give the model different starting points. Two of the later papers in this list use it or a variant. One detail I noted: parents are picked uniformly from occupied cells, and the authors report that biasing the pick did not beat the default in early tests. LLM loops often bias toward top scorers, so that is worth checking and not assuming.
-
Problem
- Treat reinforcement learning as black-box optimization over policy parameters, as an alternative to Q-learning and policy gradients. No backpropagation and no value function.
- The question is whether something this simple is competitive on standard benchmarks and whether it scales across many machines.
How it works
- The population is an isotropic Gaussian around the current parameters with a fixed noise scale. Each worker adds noise to the parameters, runs an episode, and reports the return. The update moves the parameters along the return-weighted sum of the noise vectors.
- Variance reduction: always evaluate a noise vector and its negative as a pair, and replace raw returns with their ranks. Weight decay keeps parameters from growing large next to the noise. They tried adapting the noise scale and saw no benefit.
- The scaling trick is shared random seeds. Workers only send scalar returns, since every worker can rebuild every other worker's noise.
- The policy network had to be reparameterized to make this work. On Atari, without virtual batch normalization, perturbed policies often took the same action in every state. On some MuJoCo tasks they discretized actions to get enough exploration.
Results
- MuJoCo: matches TRPO's final performance at 5 million timesteps. Cost in data is under 10x on the hard tasks (Hopper, Walker2d), and on the simple ones ES needed up to 3x less data than TRPO. On the humanoid it found odd gaits, such as walking sideways or backwards, that TRPO never produced.
- Atari: 51 games, 1 billion frames each, about an hour per game on 720 CPUs. Better than the published A3C scores on 23 games and worse on 28, at roughly equal compute, since A3C used 320 million frames but also does backpropagation.
- Scaling: 3D humanoid takes about 11 hours on one 18-core machine and 10 minutes on 1,440 cores.
Limits and open questions
- My earlier question was the sample cost. The answer is in the paper: 3x to 10x more data than A3C on Atari. The wall-clock win is paid for in environment steps.
- The update is a finite difference estimate in random directions, and theory says the number of steps should grow linearly with dimension. The authors argue that what matters is the intrinsic dimension of the problem, and report slightly better results with larger networks. That is an argument plus one observation, not a settled answer.
- The authors say ES was brittle without the reparameterization tricks. So the method is simple, but not tuning-free.
Why I care
- This is the far end from an LLM proposer: mutation is plain Gaussian noise with no knowledge of the problem, and the loop works by buying a huge number of cheap evaluations. An LLM proposer makes few, expensive, structured proposals. Because the noise distribution here is known exactly, the loop can be analyzed on paper. With a language model in that slot, the behaviour has to be measured.
-
Problem
- In genetic programming, a random change to code is almost never useful, which is why GP normally works in languages designed to survive mutation. The idea here is a mutation operator that changes code the way a programmer would.
- The second aim is data: produce many working programs in a domain the model was never trained on, from a single hand-written example.
How it works
- The operator is a diff model: a language model trained on code diffs to predict the diff from the file and the commit message. A mutation is a sampled diff for the current program, under one of three fixed commit messages picked with fixed probabilities.
- The search around it is MAP-Elites over Python programs that build Sodarace walkers. The map is 12 × 12 × 12 over walker height, width and mass, so 1,728 niches. Each step picks an occupied niche, mutates its program with the diff model, simulates the walker, and keeps it if it opens a niche or beats the occupant.
- The diff model is fine-tuned once on the diffs that MAP-Elites accepted in earlier runs, so the operator adapts to the domain.
- Two further stages: train a language model on the generated programs, then use RL (PPO) to make it output a walker conditioned on the terrain.
Results
- 4-Parity bug-fixing test of a single mutation: the chance that a GP mutation fixes the code drops off exponentially with the number of bugs, and with five bugs it never succeeded in 100,000 tries. The 300M-parameter diff model fixed all five.
- Sodarace: four seed programs, three runs each, 1,024,000 evaluations per run (2,000 iterations of 512 diffs). Runs fill most of the map from a single seed. The Square seed spreads more slowly than the others.
- The fine-tuned diff model produces a higher share of diffs that apply and run, and a higher quality diversity score.
- The generated programs were filtered into datasets of 280K and 95K examples. After the RL stage the model produces different walkers for different terrains, each working on its own terrain.
Limits and open questions
- The seed matters. The Radial seed scored well but its walkers seemed to exploit chaotic dynamics specific to flat ground, and those runs were left out of the later stages.
- Only one round of fine-tuning is shown, and early tests of further rounds gave diminishing returns. The RL stage is described as brittle, with some runs diverging.
- Left open by the authors: whether the final model can go beyond the terrains it was trained on. Left open for me: how good the proposer has to be before the loop stops making progress.
Why I care
- This is the template for LLM-proposer search: the model is the mutation step, an evaluator and an archive do the rest. The 4-Parity test is a measurement of the operator on its own, one step, outside any loop. In the same test, prompted API models did better than the diff model, so the choice of proposer is not a detail. What the paper does not do is connect that one-step measurement to how each operator behaves inside the full search, which is the link I am interested in.
-
Problem
- Language models state wrong things with confidence, which blocks using them for discovery. The fix here is to never trust the model: every output is a program, and an evaluator scores it.
- Applied to problems where a candidate can be checked fast and exactly, such as cap sets in extremal combinatorics and online bin packing.
How it works
- I write an evaluate function and a program skeleton. Only one function inside the skeleton is evolved, for example the priority function that decides what to add next. For cap sets the starting point is a trivial one.
- The search is over programs that build a solution, not over solutions. Their argument is that structured solutions have short descriptions as code, and the code is easier for a person to read than the raw object.
- Prompt: two programs sampled from the database, sorted by score, and the model is asked to write the next version. Programs live on separate islands. Every 4 hours the worse half of the islands is wiped and reseeded from the best programs of the survivors.
- The model is Codey, a code model from the PaLM 2 family. They chose fast inference over sample quality and used on the order of a million samples per run, typically with 15 samplers and 150 CPU evaluators.
Results
- Cap set problem: a cap set of size 512 in 8 dimensions, larger than any known before.
- Lower bound on cap set capacity moved from 2.2180 to 2.2202, through an admissible set construction.
- Online bin packing, excess bins over the lower bound: 5.30% on OR1 against 5.81% for best fit and 6.42% for first fit. On Weibull instances with 100,000 items, 0.03% against 3.79% and 4.00%.
Limits and open questions
- Run-to-run variance is large. Only 4 of 140 runs found the 512 cap set.
- The paper states what a problem needs: an efficient evaluator, a score richer than pass or fail, and a skeleton with an isolated part to evolve. Theorem proving is outside the scope for the second reason.
- It only works where a candidate can be scored cheaply and automatically, and it spends about a million model calls per run. Most problems I care about do not come with that.
Why I care
- With an exact evaluator, a made-up program just gets a bad score and drops out, so proposer mistakes cost samples and nothing else. That makes exact-evaluator problems a clean place to study the proposer itself. The 4 in 140 figure is the other lesson: with the proposer held fixed, the outcome of the loop is still a wide distribution, so any statement about how a proposer behaves in a loop has to be about many runs.
-
Problem
- Designing heuristics by hand takes expertise and time. FunSearch showed an LLM loop can do it, but the authors point out it needs around a million LLM queries, which most people cannot afford.
- The bet: evolve the idea behind a heuristic in plain language together with its code, and the search gets much cheaper.
How it works
- An individual has three parts: a few sentences describing the heuristic (the thought), a Python function in a fixed format, and a fitness measured on a set of problem instances.
- Five prompt strategies act as the variation operators. E1: write something as different as possible from the parents. E2: find the idea the parents share and build a new heuristic on it. M1: modify one heuristic. M2: change its parameters. M3: remove redundant parts. The model always writes the description first, then the code.
- Each generation, every strategy is called N times, giving up to 5N new heuristics, and the best N overall survive. Parents are picked by rank. The first population is also written by the model.
- Settings: 20 generations, population 20 for bin packing and 10 for the other two, GPT-3.5-turbo. For TSP and flow shop scheduling it does not write a whole solver, only the rule that reshapes the landscape inside guided local search.
Results
- Online bin packing with about 2,000 LLM queries. On six sets of Weibull instances, against the heuristic FunSearch published, EoH wins four, ties one and loses one. Example win: 2.13% against 6.75% on 1k items at capacity 500. The loss: 0.61% against 0.33% on 10k items at capacity 100.
- TSP: best of the compared methods on six TSPLib instances, hitting the best known tour on three (pr124, kroA150, u159). Flow shop: best on all the Taillard sets among the methods compared.
- Ablations: code-only and thought-only variants both do worse than evolving the pair, and dropping the modification prompts also hurts. My earlier question was whether the thought does real work. This is at least a partial yes.
- Model choice matters: GPT-3.5 and Gemini Pro do better than CodeLlama and Deepseek. All four, with 2,000 queries in the loop, beat 10,000 random GPT-3.5 queries with no loop.
Limits and open questions
- The FunSearch comparison uses FunSearch's published heuristic. It is not a rerun of FunSearch at the same query budget, so the efficiency claim compares outcomes, not controlled runs.
- The ablations are on bin packing only, with three repeats where a count is given. That is thin for a claim about thoughts in general.
- Fitness comes from small instance sets, and the paper itself notes its code-only variant overfit the training distribution. The authors also list understanding the search space of heuristics as open.
Why I care
- The five prompts are five different mutation operators taken from one model. So how a proposer behaves depends on the prompt as much as on the weights. The model comparison says a similar thing from the other side: swap the proposer and the result moves, but a weak proposer inside the loop still beats far more samples from a stronger one outside it.
-
Problem
- Reward design for RL. The true task metric is usually sparse and hard to learn from, so someone writes a shaped reward by trial and error. Here that someone is an LLM writing reward code.
- The claim to test is that this works with no task-specific prompt and no reward template, including on hard dexterous manipulation.
How it works
- The prompt holds the task description and the raw environment source code with the reward removed. The model returns a Python reward function.
- Each iteration samples 16 rewards independently. Sampling that many makes it very likely at least one runs without error. Each is used to train a policy (PPO, in Isaac Gym), and the policy is scored on the true task metric.
- The best reward goes back into the prompt with a reward reflection: the values of each reward component and of the task metric at checkpoints through training. The next 16 are edits of that one reward.
- 5 iterations per run, 5 independent runs per environment, GPT-4. Only the single best candidate carries over, so there is no population.
Results
- 29 tasks across 10 robots. Eureka rewards beat the human-written ones on 83% of tasks, with an average normalized improvement of 52%. At or above human level on all 9 Isaac tasks and 15 of the 20 two-handed dexterity tasks.
- The loop earns its keep: sampling 32 first-try rewards with no iteration does worse than two iterations of 16. Removing the per-component feedback and giving only the task score lowers the average normalized score by 28.6% on the Isaac tasks.
- The rewards are mostly weakly correlated with the human ones, and a few are negatively correlated and still better. With GPT-3.5 it gets worse but still matches or beats human rewards on most Isaac tasks.
- Pen spinning on a simulated Shadow Hand needed a curriculum: train on reorienting the pen, then fine-tune on the spinning sequence. Without the two-stage setup it could not finish one cycle.
Limits and open questions
- Cost. By my count that is 5 runs × 5 iterations × 16 candidates per task, and every candidate needs its own RL training run. This only works with fast simulation.
- Everything is in simulation, and the PPO hyperparameters are the ones already tuned for the human rewards.
- It needs a task metric to score against. Where there is none they substitute written human feedback, shown on one humanoid task with a 20-person preference study.
Why I care
- This is about the smallest LLM search loop there is: best so far, feedback, 16 fresh samples. The 32-sample ablation is a direct comparison of sampling zero-shot against proposing inside a loop at equal budget, and the loop wins. So zero-shot quality is not the whole story of a proposer. Whether it at least predicts the in-loop behaviour is the question I work on.
-
Problem
- Automating algorithm discovery for problems where a candidate can be scored by running code. It is the successor to FunSearch, which evolved one short Python function and needed millions of samples.
- The goal is the same loop at larger scale: whole files, any language, slow evaluations, far fewer samples.
How it works
- I mark the regions of a codebase to evolve with EVOLVE-BLOCK comments and supply an evaluate function that returns a dictionary of scores. Everything outside the blocks is fixed skeleton.
- Loop: sample a parent and some inspiration programs from the database, build a prompt, get a diff back in a search and replace format, apply it, evaluate, store the result with its scores.
- Two models share the work. Gemini 2.0 Flash produces most of the candidates because it is fast. Gemini 2.0 Pro gives fewer, better suggestions.
- The database is described as inspired by a mix of MAP-Elites and island populations. Extras: cheap tests before expensive ones, optional LLM-written feedback, several metrics at once, and prompts that are themselves evolved.
Results
- Matrix multiplication: better than the best known algorithm for 14 sizes. The headline is 4×4 complex matrices in 48 scalar multiplications, against 49 from applying Strassen recursively, a first in 56 years.
- Over 50 open math problems: matched the best known construction on about 75% and beat it on about 20%. Examples: kissing number in 11 dimensions from 592 to 593, and 26 circles in a unit square with sum of radii from 2.634 to 2.635.
- Infrastructure: a scheduling heuristic that recovers 0.7% of fleet compute on average, a kernel tiling heuristic giving a 23% average kernel speedup and 1% off Gemini training time, and a 32% speedup on a FlashAttention kernel.
- Ablations on two tasks (tensor decomposition and kissing numbers): no evolution, no context in the prompt, no evolved prompts, evolving only one function, and a small model only. Each one does worse than the full system.
Limits and open questions
- It needs an automated evaluator. The authors call this the main limitation, and it rules out anything needing manual experiments.
- The ablations are shown as curves over three seeds on two tasks. So my earlier question, model or loop, gets the answer that both matter, without a number for how much each.
- Several of the math gains are in the third decimal place, and details on those problems are deferred to a later paper.
Why I care
- The no-evolution ablation feeds the same starting program to the model again and again, which is zero-shot sampling at scale, and it loses to the loop. The small-model-only run also loses. So the result depends on both the proposer and the loop, and the paper does not separate the two beyond that. Circle packing with an exact score is one of its test problems, which is the kind of setting I use to ask how much of a proposer's in-loop behaviour shows up zero-shot.