Genetic Algorithms and Evolution Strategies

Evolutionary computation  optimizes by maintaining a population of candidate solutions, scoring them, and producing the next population from the better ones through variation. Selection concentrates the population on good regions; variation supplies the novelty on which selection can act. Remove either and the process stops working.

It matters to swarm intelligence for a specific reason. Hand-designing local rules that produce a wanted global behaviour is hard, because emergence maps rules to outcomes in ways no designer can invert. Evolution does not need to invert it. It only needs to recognize the outcome.

Two traditions

Genetic algorithms, developed by John Holland in the 1960s and 1970s, emphasize recombination of discrete representations and were originally motivated as a model of adaptation rather than as an optimizer.

Evolution strategies, developed independently by Ingo Rechenberg and Hans-Paul Schwefel in Berlin at roughly the same time, work on real-valued vectors, emphasize mutation over recombination, and — decisively — evolve their own mutation parameters.

The two converged. What remains distinct is emphasis: genetic algorithms lean on crossover, evolution strategies on adaptive mutation.

Genetic algorithms

Representation

The encoding is the design decision that constrains everything else. Binary strings are classical and make crossover trivially definable. Real-valued vectors are natural for continuous parameters. Permutations suit ordering problems and require crossover operators that preserve validity. Trees encode programs, which is genetic programming .

A good encoding makes small genotype changes produce small phenotype changes. When it does not — when flipping one bit reorganizes the solution entirely — selection has nothing to work with.

Selection

Fitness-proportionate (roulette-wheel) selection samples parents in proportion to fitness. It is the textbook method and it is poorly behaved: one dominant individual takes over the population, and adding a constant to every fitness value changes the selection pressure, which means the algorithm depends on the arbitrary origin of the objective.

Tournament selection picks $k$ individuals at random and takes the best. Selection pressure is set by $k$ alone, and the method is invariant to any monotone rescaling of fitness. It is what you should use.

Rank selection sorts and samples by rank, similarly scale-invariant. Elitism — copying the best individuals unchanged into the next generation — guarantees monotone improvement of the best-so-far, and costs diversity.

Operators

Crossover recombines parents: single-point, multi-point, or uniform for strings; blend and simulated-binary for real vectors; order-preserving variants for permutations. Its theoretical justification is that it assembles good partial solutions discovered separately.

Mutation perturbs an individual: bit-flip, Gaussian, or polynomial. Its function is to maintain reachability. Without mutation, once an allele is lost from the population it can never return, and crossover alone can only recombine what already exists.

Evolution strategies

Self-adaptation

Evolution strategies evolve the mutation distribution alongside the solution. An individual is a pair $\langle \mathbf{x}, \boldsymbol{\sigma} \rangle$: solution parameters and the step sizes used to mutate them.

Reproduction mutates the step sizes first, then uses them:

with learning rates $\tau', \tau$. The logic is indirect but sound: an individual whose step size happened to suit the local landscape produces fit offspring, and those offspring inherit that step size. The algorithm’s own exploration–exploitation balance is therefore selected for, not set by hand.

Selection notation

$(\mu, \lambda)$-ES generates $\lambda$ offspring from $\mu$ parents and selects the $\mu$ best offspring, discarding the parents entirely. $(\mu + \lambda)$-ES selects the $\mu$ best from parents and offspring combined.

The comma strategy pairs better with self-adaptation, precisely because it forgets: a parent that survives forever carries a step size tuned to a landscape region the population has left. The plus strategy is more elitist and never loses the best solution. The tradeoff is exactly the one between memory and adaptability that recurs across this field.

CMA-ES

CMA-ES  — covariance matrix adaptation — is the mature form. It maintains a full covariance matrix for the mutation distribution and adapts it from the path the population has taken through the space, learning the local metric of the objective. On non-separable, ill-conditioned continuous problems it is close to the state of the art among derivative-free methods, and it is what a serious practitioner reaches for before anything else in this family.

Advanced methods

Multi-objective evolutionary algorithms approximate the whole Pareto front  in a single run — a natural fit, since a population is a set of solutions. NSGA-II  sorts by dominance rank and breaks ties by crowding distance, preserving spread. Indicator-based methods optimize a scalar quality measure of the whole front, typically hypervolume.

Coevolution evolves interacting populations. In cooperative coevolution a problem is decomposed and subpopulations evolve components that are evaluated together. In competitive coevolution, populations evolve against each other — solutions against test cases, controllers against adversarial environments. Competitive coevolution can produce open-ended arms races, and it can also produce cycling, where populations chase each other around a loop and nothing improves. Detecting the difference requires an external yardstick.

Memetic algorithms apply local search to individuals, evolving refined solutions rather than raw ones. The hybrid nearly always outperforms the pure evolutionary algorithm on problems where a local search exists.

Evolutionary computation in swarm systems

Tuning parameters. The weights and radii of a flocking controller, the $\alpha$, $\beta$, $\rho$ of ant colony optimization, the response thresholds of a task-allocation rule. This is straightforward and effective, and it is the usual first application.

Evolving behaviour. More ambitiously, evolve the local rules themselves — as neural network weights (neuroevolution ) or as programs (genetic programming) — with fitness measured on the collective outcome. This is the technique’s real contribution to swarm research, because it circumvents the design problem: you specify what the swarm should achieve, not how each agent should behave.

The difficulty is credit assignment. When a swarm succeeds, which agent’s rule deserves the credit? Evolving a shared rule for identical agents sidesteps this, at the cost of foreclosing specialization.

Distributed evolution. Island models evolve subpopulations in parallel with occasional migration, which preserves diversity better than a single panmictic population and maps naturally onto parallel hardware. Embodied evolution runs the evolutionary process on the robots, with agents exchanging genomes on encounter — evolution as a swarm behaviour rather than as an offline design step.

Practice

Population size trades diversity against evaluation budget. Too small and the population converges before it has explored; too large and it never converges within budget. Monitor diversity directly — mean pairwise genotype distance, or fitness variance — and treat its collapse as the true termination condition, whatever your iteration limit says.

Diversity maintenance through fitness sharing (penalizing crowded regions), crowding (replacing similar individuals), or niching keeps a population exploring multiple optima. It is the standard remedy for premature convergence, which is this family’s characteristic failure just as it is PSO’s.

Constraints are handled by penalty functions, repair operators, feasibility-preserving operators, or by treating violation as an objective. The same menu as everywhere else.

Termination on generation count is convenient and arbitrary. Terminating on stagnation of the best-so-far, or on diversity collapse, is more informative.

Theory

Schema theory, Holland’s original analysis, argues that short, low-order, above-average-fitness building blocks proliferate exponentially under selection and crossover. It is illuminating and it is not a convergence proof; the building-block hypothesis has resisted general demonstration.

Runtime analysis takes the modern approach: bound the expected number of evaluations to optimum for specific algorithms on specific problem classes. Where the results exist they are rigorous, and they are confined to problems far simpler than the ones evolutionary algorithms are used on.

No free lunch deserves a mention and a caveat. Averaged over all objective functions, every search algorithm performs identically. This is true and nearly always misapplied: the functions we actually care about are a vanishing, highly structured subset, and an algorithm that exploits their structure genuinely beats one that does not.

In Arboria’s work

Evolutionary search was our original parameter tuner. It has been superseded by Bayesian optimization  — tree-structured Parzen estimators and CMA-ES under successive-halving pruning — because when a single objective evaluation is a full multi-agent simulation across many seeds, the sample efficiency of a surrogate model dominates the parallelism of a population. The evolutionary path remains available for parity against older runs. See Maneuver.Map.

The broader lesson stands, though, and it is why this page exists. In a system whose behaviour is emergent, you cannot design backward from the outcome. Evolution — and, increasingly, reinforcement learning — is how you get rules you could not have written.