Black-box optimisation
A black-box objective accepts a candidate and returns a score. The goal here is to make that score smaller, within a limited number of evaluations.
Think of a traffic-signal plan. You choose the timings, run a simulator and read the total delay. You can compare plans without knowing a useful derivative of that delay.
Derivatives might exist, or even be approximated. But they may be expensive, noisy or uninformative. The methods below search using objective values alone.
Every query spends part of the budget. One iteration can contain many queries.
The maps show two-dimensional test functions. Blue-tinted regions have lower objective values; diamond markers indicate known optima. These landmarks are shown to you, not supplied to the algorithms. The population and Bayesian experiments start paused and use fixed seeds so you can replay them.
Local minima and gradient descent
The outcome of local descent depends on the starting point and the shape of the objective.
These thirteen starting points follow a numerical gradient down the same curve. Watch the trajectories and their loss together. Play runs the descent; Step advances one update. Click the landscape to add a starting point and replay.
Hollow circles mark the starts; blue points are still descending. Green marks convergence to the lowest minimum in this interval, vermilion another local minimum. A number beside a minimum counts the points that settled there.
The update and its limits
The demo estimates the derivative with a central difference and uses a fixed step size of 0.025. Playback slows the early iterations so their motion is visible; the numerical update is unchanged. A step that is too large can increase the objective or oscillate. A zero derivative alone does not prove a minimum. Here we stop when the estimated derivative is small, or at the iteration limit.
Particle swarm optimisation
Each particle remembers its best position and follows the best point found by the group. Momentum keeps it moving. A swarm can search several basins, but it can also gather around the wrong one.
Experiment Set the social coefficient to zero. With zero initial velocities and personal records at the initial positions, this swarm cannot start moving.
The mathematics Update rule, implementation & limits
The random vectors are sampled independently in [0, 1] for each particle and coordinate. The demo clips velocities and positions at the search bounds. Personal and global records only change when a better score is found.
Trails show particle movement. The convergence curve records the best objective value found, which need not be the global minimum.
Genetic algorithms
Select promising candidates, blend their coordinates, then add random mutations. The best candidate survives into the next generation. New points are offspring, not the same individuals moving through space.
Experiment Increase mutation to spread the offspring. Then lower it and watch how quickly the population loses diversity.
The mathematics Update rule, implementation & limits
This is a real-valued genetic algorithm with tournament selection, BLX-α crossover, Gaussian mutation and elitism. The equation shows crossover before clipping to the search bounds. Each coordinate then has a 50% chance of Gaussian mutation; its standard deviation is a fraction of the search-box width. Other genetic algorithms use different representations and operators.
A larger tournament favours fitter parents more strongly. It can speed up improvement while making premature concentration more likely.
Differential evolution
Take the difference between two candidates and add a scaled version to a third. Mix that donor with a target candidate. Keep the trial only if it improves the target.
Experiment Lower crossover to change fewer coordinates. Raise the difference weight to propose larger moves.
The mathematics Update rule, implementation & limits
The DE/rand/1/bin rule uses three distinct population members, excluding the target. A forced donor coordinate prevents a trial from being an unchanged copy of the target. Bounds are enforced by clipping.
The difference vectors shrink as candidates gather. That gives a useful adaptive scale, but a collapsed population can still stall.
Simulated annealing
One point takes random steps. Improvements are accepted; worse proposals may be accepted while the temperature is high. Cooling gradually makes the search more selective.
Experiment Raise the initial temperature and look for accepted uphill moves. Slow the cooling to keep that behaviour for longer.
The mathematics Update rule, implementation & limits
Here the proposal is symmetric and the objective is minimised, so Δf is the proposed score minus the current score. Temperature has the same scale as the objective. The current point can get worse while the best point on record cannot.
This finite geometric cooling schedule is a practical choice, not a guarantee of finding the global minimum.
Covariance matrix adaptation
Sample a cloud, keep its better points, then update the centre, scale and covariance. The ellipse shows how the search changes direction and stretches along a valley.
Experiment Start on Rosenbrock. Watch the sampling ellipse tilt as the search follows the curved valley.
The mathematics Update rule, implementation & limits
Positive recombination weights sum to one. Evolution paths and rank-one/rank-μ updates adapt the covariance and global step size. The ellipses represent one and two sampling standard deviations, not confidence intervals for the location of the optimum.
CMA-ES adapts a search distribution. It does not calculate the objective's Hessian, and a single run can settle in a local basin.
Bayesian optimisation
Fit a probabilistic model to the observations. Use expected improvement to choose the next point, balancing predicted value and uncertainty. Here the model is a Gaussian process on a one-dimensional function.
Experiment Take one sample at a time. Change the length scale and notice how far an observation influences the model.
The mathematics Update rule, implementation & limits
The demo uses an RBF kernel with fixed hyperparameters and searches a finite grid for the largest expected improvement. The shaded band is the model mean ± two posterior standard deviations. It reflects the chosen model, not a guaranteed error bound.
The dashed objective is visible to you for explanation. The optimiser only receives its sampled values. This small example does not establish performance in hundreds of dimensions.
Comparing optimisation methods
Compare objective values at a matched evaluation budget, using several independent random seeds.
| Your constraint | A starting point | What to check |
|---|---|---|
| Every query is expensive | Bayesian optimisation | Can the surrogate model represent the problem? How many dimensions? |
| Continuous, badly scaled variables | CMA-ES | Population cost, constraints and restarts. |
| Continuous, little known structure | Differential evolution | Evaluation budget and loss of population diversity. |
| A useful way to recombine solutions | Genetic algorithm | Whether crossover preserves useful structure. |
| A simple population baseline | Particle swarm | Premature concentration and parameter sensitivity. |
| A useful local proposal, little memory | Simulated annealing | Objective scaling and the cooling schedule. |
Always include a simple baseline: random search, a domain heuristic or local search with restarts. Keep the evaluation budget and stopping rule comparable. These examples teach mechanisms; they do not rank the methods.
The No Free Lunch theorem
The classic theorem concerns a uniform average over all objective functions on a finite domain, with non-revisiting search. Under those assumptions, methods have the same average performance. Real problems are not a uniform sample of all functions. Their structure is precisely what an algorithm can exploit.
Wolpert & Macready, No Free Lunch Theorems for Optimization (1997) ↗
For the covariance method: Hansen's CMA-ES tutorial and reference implementations ↗.
Application: traffic-signal optimisation
The project grew out of the Delta 2026 traffic-signal challenge. The accompanying experiment compares equal green times, demand-based allocation and an optimised signal plan on a synthetic road network.
Open the traffic lab ↗A synthetic grid of 36 junctions, an analytical delay model and a particle swarm. Change demand, compare signal plans and measure the improvement.
This is a teaching model, not the official competition simulator. Its results do not establish the optimum of a real city or reproduce a competition score.
Inspect the model ↗