The Pareto Frontier, Evolved by Genetic Algorithm

After reading this you will know what a Pareto frontier is, how NSGA-II breeds a population toward it, and how to read the moving scatter of bridge designs without fooling yourself about what the numbers mean.

What a Pareto frontier is

Most design problems pull in two directions at once. A bridge that weighs less bends more under load. A bridge that barely bends needs thick members and so weighs more. There is no single winner. Instead there is a set of designs where you cannot make the weight smaller without making the deflection larger, and cannot make the deflection smaller without adding weight. That set is the Pareto frontier.

Here is the hook. Suppose you have four candidate bridges with these weight (kg) and worst deck deflection (mm) numbers: A at (120, 8.0), B at (150, 5.0), C at (200, 4.5), and D at (160, 9.0). Design D is beaten by B on both counts: B is lighter (150 < 160) and stiffer (5.0 < 9.0), so D is dominated and drops out. A, B and C each win on at least one objective, so all three sit on the frontier. The simulator does this sorting for a population of hundreds and redraws the frontier every generation.

Formally, design p dominates design q when it is no worse on every objective and strictly better on at least one:

p \prec q \iff \forall i: f_i(p) \le f_i(q) \; \text{ and } \; \exists j: f_j(p) \lt f_j(q)

Here f_i is objective i (weight or deflection, both to be minimised), p \prec q reads "p dominates q", and the frontier is every design that no other design dominates.

When to use this idea, and when not

Reach for a Pareto frontier whenever you face two or three goals that trade off and you refuse to collapse them into one number too early. Cost against reliability. Speed against accuracy. Weight against stiffness. The frontier hands you the full menu of sensible compromises and lets a human pick afterward.

Do not use it when the objectives do not actually conflict. If cheaper always means better here, there is one best design and no trade-off to trace. Also be careful past three objectives: a four-dimensional frontier is nearly impossible to see, and most designs become non-dominated by accident, which starves selection of information.

The frontier tells you the efficient trade-offs. It does not tell you which one to build. A bridge at (120, 8.0) and one at (200, 4.5) are both Pareto-optimal; choosing between them needs a design brief, not more math.

How NSGA-II climbs toward the frontier

NSGA-II is the standard multi-objective genetic algorithm. It keeps a population of designs and improves them with two ranking rules stacked on top of each other.

The first rule is fast non-dominated sorting. Split the population into layers. Rank 1 is every design that nothing dominates: the current frontier. Remove them, and rank 2 is the frontier of what remains. Repeat until every design has a rank. Lower rank is better.

The second rule is crowding distance, a tie-breaker inside a rank. For each objective, sort the rank and measure the gap between each design's neighbours. The crowding distance of design i summed over objectives is

d_i = \sum_{m} \frac{f_m^{(i+1)} - f_m^{(i-1)}}{f_m^{\max} - f_m^{\min}}

where f_m^{(i+1)} and f_m^{(i-1)} are the objective values of the two neighbours of design i along objective m, and the denominator is that objective's range across the rank. Designs in sparse regions get a large d_i and are preferred, which spreads the population evenly along the frontier instead of letting it clump.

Selection favours low rank first, then high crowding distance. Winners are bred with simulated binary crossover (blend two parents' genes) and polynomial mutation (nudge a gene by a small random amount). Parents and children are pooled, sorted again, and the best half survives. That elitist pooling is why past frontiers fade behind the population: each generation's best is never simply thrown away.

The bridge behind every dot

Every dot is a real 2D truss, not a lookup table. The genome carries five top-chord heights and 25 member cross-section thicknesses. To evaluate it, the simulator runs the direct stiffness method: assemble each member's contribution into a global stiffness matrix K, apply the deck loads as a force vector F, and solve for node displacements u.

K u = F

Each member of length L, area A and modulus E contributes an axial stiffness EA/L, rotated into global coordinates. Solving u = K^{-1} F gives every node's movement. The two objectives fall straight out: weight is the total material, \sum_k \rho A_k L_k, and the second objective is the worst vertical deflection anywhere along the deck. Thicker members raise A_k, so weight goes up while deflection goes down. That is the physical source of the trade-off.

Reproducing the demo run

Click the demo button (it uses the field defaults) and watch generation 0. A fresh random population scatters wide, roughly from (90, 30) to (320, 4) in (weight kg, deflection mm). Follow the knee design and the numbers below are the shape you should see.

Generation 0: the orange front is jagged and far out. The knee sits near (210, 12): middling weight, middling deflection.
Generation 10: the population has swept down and left. The knee is near (165, 7.5). Notice deflection fell 38% while weight fell 21%.
Generation 30: the front is smooth and the knee sits near (150, 6.0). Improvement per generation has slowed to under 2%.
Generation 60: the front barely moves. The knee holds near (145, 5.7). The algorithm has converged.

Click the two ends of the front to confirm the physics. The far-left dot is a spindly truss with thin members that bends a lot. The far-right dot is a heavy truss with thick members that barely moves. The knee is the balanced middle.

Grey dots are individual designs across several generations; the orange line traces the current non-dominated front. The knee sits near (145, 5.7), where bending toward either objective costs a lot in the other.

Reading the objective-space scatter

Down and to the left is better, because both objectives are minimised. Three things are worth watching each generation.

First, the front's shape. A bowed-in (convex) front means every compromise is efficient. A disconnected front, which the ZDT3 benchmark produces on purpose, means whole stretches of the trade-off are simply unreachable. Kursawe produces a non-convex front, where a straight line between two good designs would pass below the achievable region.

Second, the knee. That is the point of sharpest curvature, where you get the most deflection reduction per kilogram before diminishing returns kick in. From the demo, moving left of the knee from (145, 5.7) to (130, 11) saves 15 kg but nearly doubles deflection: a bad trade. Moving right to (220, 5.5) adds 75 kg to cut deflection by only 0.2 mm: also a bad trade. The knee is where the front stops being cheap.

Third, the spread. Crowding distance should keep dots evenly spaced along the front. A gap means the algorithm has not filled that region yet.

Common mistakes

The frequent errors are less about the algorithm and more about interpretation.

Collapsing too early: Averaging weight and deflection into one score before you evolve throws away the whole frontier. You get one answer and never see the alternatives.
Trusting a rough front: At generation 5 the front is still jagged and far from converged. Reading a knee off it will mislead you. Wait until the front stops moving, near generation 60 in the demo.
Comparing across scales: Weight in kilograms and deflection in millimetres have different magnitudes. Crowding distance normalises by each objective's range, but your eye does not. Judge trades by percent change, as in the worked example.
Believing the mesh is a real bridge: This is a 2D truss with idealised pin joints and a single load case. A real bridge has 3D geometry, dynamic loads, buckling and safety factors. Treat the front as a teaching object, not an engineering deliverable.

If the front looks stuck with big gaps, the population may be too small to hold designs in every region. A larger population fills the front more evenly, at the cost of more finite-element solves per generation.

Related simulations on this site

If watching a rule-based population evolve interests you, several other simulators here run agents or equations forward in time and let you read the emergent pattern.

The SIR Epidemic Simulator and the Predator–Prey Simulator both integrate small systems of differential equations and show how they burn out or cycle. For emergent order from simple local rules, try the Schelling's Segregation Model, the Forest Fire Model, and Sugarscape. For flow and congestion, see the Traffic Jam Simulator and the City Traffic Grid. Opinion dynamics on a network appear in Opinion Spread.

Frequently asked questions

What does non-dominated mean in plain terms?

A design is non-dominated when no other design in the population beats it on both objectives at once. In the four-bridge example, D at (160, 9.0) is dominated by B at (150, 5.0) because B is both lighter and stiffer. A, B and C are non-dominated.

Why does the front stop improving?

Once the population reaches the true frontier, no mutation or crossover can push a design below it, because the physics forbids it. In the demo the knee moves from (210, 12) at generation 0 to about (145, 5.7) by generation 60, then holds steady. That flattening is convergence, not a bug.

What is the knee and why care about it?

The knee is the point of sharpest curvature on the front, where the exchange rate between the two objectives is most balanced. Moving away from it costs a lot in one objective for little gain in the other, so it is often the default engineering compromise.

Why include ZDT1, ZDT3 and Kursawe?

Those are benchmark problems with mathematically known true fronts: convex, disconnected and non-convex respectively. Running them lets you check that NSGA-II actually lands on the known answer, which builds trust before you point it at the bridge.

Is crossover or mutation doing the real work?

Both. Simulated binary crossover recombines good partial designs, which drives most of the early sweep from generation 0 to 10. Polynomial mutation supplies small variation that fills gaps and fine-tunes near the front in later generations. Remove either and the front converges slower or fills unevenly.

Try it yourself in the tool