Evolutionary Algorithms & Multi-Objective Search

An evolutionary algorithm maintains a population of candidate solutions, evaluates them, preferentially selects candidates, creates variants by mutation and recombination, and replaces some or all of the population. The biological metaphor is optional; the engineering content is a stochastic population search with explicit representation and selection pressure.

flowchart TD
  P["population"] --> E["evaluate objectives and constraints"]
  E --> S["select parents"]
  S --> V["recombine and mutate"]
  V --> R["replacement and elitism"]
  R --> P

Representation defines the neighborhood #

A candidate may be a bit string, real vector, permutation, tree, graph or program. Mutation determines which nearby candidates are reachable in one step; crossover determines how partial structures are combined. A poor encoding creates invalid offspring or makes small semantic changes require large genotype changes.

Match operators to invariants. Permutation crossover should preserve each item exactly once. Constrained geometry may be better represented by parameters that generate valid shapes than by repairing arbitrary coordinates after mutation.

Selection and variation #

Let scalar fitness be $F(x)$. Tournament selection samples several candidates and selects the best; rank selection uses order rather than raw magnitude; fitness-proportionate selection makes scale and outliers influential. Strong selection accelerates convergence but removes diversity. Mutation restores local exploration; recombination can combine compatible building blocks but can also destroy them.

Elitism preserves the best candidates across generations. Without it, stochastic replacement can lose progress. With too much elitism, the population can collapse around a local basin.

A minimal generational procedure is:

1. initialize a diverse population within constraints;
2. evaluate every candidate with a reproducible objective;
3. preserve a bounded elite;
4. select parents;
5. create offspring with domain-valid variation;
6. evaluate and form the next population;
7. stop by evaluation budget and convergence diagnostics, not one unchanged generation.

Constraints are part of the search #

Penalty functions mix feasibility with objective quality and can be hard to scale. Alternatives include feasibility-first ordering, repair operators, decoders that generate only feasible candidates, and specialized variation that preserves constraints. Report which method was used: two runs with the same “genetic algorithm” but different constraint handling solve different optimization problems.

Multi-objective search #

For several conflicting objectives, scalarizing with fixed weights returns one preference-dependent solution and can miss non-convex parts of the Pareto frontier. Population methods can approximate many non-dominated trade-offs in one run.

NSGA-II uses:

• non-dominated sorting to assign Pareto fronts;
• elitist replacement over the combined parent and offspring population;
• crowding distance to prefer sparsely represented regions within a front.

Its original complexity is $O(MN^2)$ for $M$ objectives and population size $N$. Crowding distance preserves spread only in the represented objective space; it does not ensure uniform coverage of a curved frontier or solve the many-objective loss of selection pressure.

After obtaining a frontier, decision analysis is still required. The algorithm removes dominated alternatives; it does not decide the trade-off among non-dominated ones.

When evolutionary search is appropriate #

Good candidates include expensive black-box simulations, mixed discrete/continuous designs, discontinuous objectives, multiple local basins and multi-objective exploration. Prefer gradient, convex, dynamic-programming or problem-specific methods when their assumptions hold: they exploit structure and usually use evaluations far more efficiently.

Experimental discipline #

Evolutionary results are random variables. A defensible study records representation, operators, population, evaluation budget, random seeds, constraint handling and stopping rule; compares against simple baselines and domain methods; runs multiple independent trials; reports distributions rather than the best run; and reevaluates finalists with higher-fidelity or independent models.

For noisy objectives, repeated evaluation, common random numbers or explicit uncertainty models may be necessary. Otherwise selection can reward noise. For costly simulations, surrogate models can reduce evaluations, but surrogate uncertainty and out-of-domain proposals become part of the algorithm.

An evolutionary algorithm is a search budget allocation mechanism. Its success depends less on biological vocabulary than on representation, variation, constraints, evaluation fidelity and honest comparison.