GDnD Wiki

GDnD Wiki

This site is for Ulster University students and staff. Enter the class access password to continue.

Genetic Algorithms

12 min read

Summary

A genetic algorithm (GA) is an optimisation technique that evolves a population of candidate solutions through repeated cycles of selection, crossover, and mutation — inspired by biological natural selection. Rather than searching a solution space exhaustively or following a gradient, a GA explores it stochastically, guided by a fitness function that scores how well each candidate solves the problem. Over generations, fitter solutions reproduce more and their traits spread through the population. (Brabazon, O’Neill and McGarraghy, Natural Computing Algorithms, see source-natural-computing-algorithms)

(Shiffman, The Nature of Code, Chs. 9–11, see source-nature-of-code)

JavaScript to Unity/C# bridge

In The Nature of Code, the genetic algorithm examples are shown in JavaScript, often with immediate text or canvas feedback. In Unity, the GA structure stays the same, but the presentation changes:

  • the population usually lives in a manager component
  • each chromosome becomes a C# class or struct
  • per-generation feedback often appears in the Inspector, Debug.Log, UI text, or visible agents in a scene

The key thing to preserve is the loop of evaluate → select → crossover → mutate, not the original language or exact sketch structure.

The three requirements

Evolution — biological or computational — requires all three of the following. If any is absent, the algorithm degenerates:

RequirementMeaningIf absent
HeredityParent traits pass to offspringEach generation is independent; learning cannot accumulate
VariationThe population contains diverse individualsAll children are identical to parents; no exploration
SelectionFitness determines who reproducesUniform reproduction; no optimisation pressure

The algorithm

1. Initialisation

Create a population of N individuals with randomly generated DNA (genotype). Population size is a global parameter — larger populations explore more of the solution space but cost more computation per generation.

2. Evaluate fitness

Score every individual using the fitness function. This is the most important design decision. The function must:

  • Return a numerical value
  • Accurately reflect the goal
  • Be automatable (or interactively provided by a human)
// Example: phrase-matching fitness
float Fitness(string target, char[] genes)
{
    int correct = 0;
    for (int i = 0; i < genes.Length; i++)
        if (genes[i] == target[i]) correct++;
    return (float)correct / target.Length;
}

Scaling the fitness function changes selection pressure:

  • Linear: fitness = correct / total — moderate pressure
  • Quadratic: fitness = (correct / total)² — higher scorers dominate faster
  • Exponential: fitness = 2^correct — extreme pressure; risks premature convergence

3. Selection

The goal: individuals with higher fitness should be more likely to reproduce, but not guaranteed. Pure elitism (top N only) reduces variation too quickly.

Probabilistic / “wheel of fortune” selection: Normalise all fitness scores to sum to 1. Draw a random number and walk down the list subtracting scores until crossing it — the individual where the crossing occurs is selected. Higher fitness = more space on the wheel.

// Relay-race selection
DNA PickParent(DNA[] population, float[] fitness)
{
    float r = Random.value;
    int i = 0;
    while (r > 0)
    {
        r -= fitness[i];
        i++;
    }
    return population[i - 1];
}

Accept-reject: Pick a random individual. Accept it with probability proportional to its fitness; otherwise try again. Simpler to implement; slightly less efficient.

4. Crossover

Combine two parents’ DNA to create a child:

char[] Crossover(char[] parentA, char[] parentB)
{
    char[] child = new char[parentA.Length];
    int midpoint = Random.Range(0, parentA.Length);
    for (int i = 0; i < child.Length; i++)
        child[i] = i < midpoint ? parentA[i] : parentB[i];
    return child;
}

Coin-flip variant: Each gene independently chosen from either parent (50/50). Maximum genetic variation.

5. Mutation

Randomly alter individual genes at a low rate after crossover:

void Mutate(char[] genes, float rate)
{
    for (int i = 0; i < genes.Length; i++)
        if (Random.value < rate)
            genes[i] = (char)Random.Range(32, 127);
}

Mutation rate trade-offs:

  • 0% — Evolution stalls if the complete solution is not in the initial population.
  • ~1–2% — Typical range balancing exploration and exploitation.
  • >10% — Overwhelms selection pressure; devolves to near-random search.

6. Repeat

The new generation becomes the current population. Repeat from step 2 until the fitness target is reached or generation limit exceeded.

Beginner Unity code example

For a simple Unity teaching version, see:

  • DNA.cs — minimal genotype container for a text-matching GA
  • TextPopulationManager.cs — population loop running evaluate/select/crossover/mutate each generation

This is intentionally simpler than a full agent-based scene. It gives students a clear C# baseline before moving to rockets, creatures, or neuroevolution.

Scene setup for the Unity example

Use the text-matching GA as a console-style Unity lab:

  1. Create an empty GameObject named TextGA.
  2. Add TextPopulationManager to it.
  3. Set target to a short phrase, such as HELLO.
  4. Set populationSize to 100.
  5. Set mutationRate to 0.01.
  6. Press Play and watch the Console.
  7. Increase the target length only after the short phrase converges.

This example does not need sprites. The visible output is the best text found each generation, printed through Debug.Log.

Code walkthrough

DNA owns one candidate solution. It stores a char[] called Genes, exposes the current Text, and stores Fitness after evaluation. Randomise() creates a starting candidate from the allowed alphabet.

Evaluate() compares the genes against the target phrase and scores the fraction of matching characters. This is the fitness function. For this beginner example, the goal is deliberately simple so students can see evolution happen.

Crossover() creates a child by taking genes from one parent before a random midpoint and genes from the other parent after that midpoint. Mutate() then gives each gene a small chance to change to a new random character.

TextPopulationManager owns the population loop. Start() creates the first random population. Each Update() calls EvolveOneGeneration(), which evaluates fitness, selects parents, creates children, mutates them, replaces the population and logs the current best text.

PickParent() uses accept-reject selection. A candidate is chosen randomly, then accepted with probability based on fitness. Higher fitness candidates are more likely to reproduce, but lower fitness candidates can still occasionally contribute variation.

What to change first

ChangeExpected effect
targetlonger targets take more generations
populationSizelarger populations explore more candidates but cost more
mutationRatelow values may stall, high values can disrupt progress
alphabet in DNAchanges which phrases can be evolved
logging frequencymakes long runs easier to read

Debugging checklist

  • If the output never improves, check that Evaluate() is called before PickParent().
  • If the target can never be reached, check that every target character exists in Alphabet.
  • If evolution looks random, reduce mutationRate.
  • If progress is very slow, shorten the target phrase or increase populationSize.
  • If the Console floods too quickly, log every tenth or hundredth generation instead of every frame.

Practice

Run three experiments:

  1. Target HELLO, population 100, mutation 0.01.
  2. Same target and population, mutation 0.
  3. Same target and population, mutation 0.15.

For each run, describe whether the population converges, stalls or behaves randomly. Then explain which run best balances selection and variation.

Self-test

  1. What is the genotype in the text example?
  2. What is the phenotype?
  3. What does the fitness function measure?
  4. Why can a mutation rate of 0 cause the search to stall?
  5. Why can a high mutation rate damage progress?

Answers

  1. The genotype is the char[] Genes array.
  2. The phenotype is the text produced from those genes and evaluated against the target.
  3. It measures the fraction of characters that match the target phrase.
  4. With no mutation, the algorithm cannot introduce missing characters that are absent from the selected parent lines.
  5. A high mutation rate can overwrite useful inherited genes so quickly that selection cannot preserve improvements.

Genotype vs. phenotype

The genotype is the raw genetic data — an array of characters, floats, or vectors. The phenotype is how that data is expressed and evaluated. The same genotype can produce different phenotypes depending on how it is interpreted. Separating these two concerns keeps the GA core reusable across different problems.

Elitism

Without elitism, crossover and mutation can accidentally destroy the best chromosomes discovered so far — they represent a small fraction of the population, so selection may simply not choose them.

Elitism: copy the top N% of the population (typically 2–5%) directly to the next generation without modification. The rest of the population is generated normally through selection, crossover, and mutation.

// Elitist selection — copy top agents unchanged
int eliteCount = Mathf.RoundToInt(population.Length * 0.05f);
for (int i = 0; i < eliteCount; i++)
    newPopulation[i] = population[sortedByFitness[i]].Copy();
// fill remainder with crossover + mutation

Trade-off: Too few elite → slower convergence. Too many → premature convergence to a local optimum (diversity lost). The sweet spot depends on problem size and selection pressure.

(Prof Charles, CRE341 Wks 8–9)

Global parameters

ParameterEffectTypical value
Population sizeLarger = more diversity, more computation100–500
Mutation rateHigher = more exploration, less exploitation0.5%–2%
Fitness scalingLinear vs. quadratic vs. exponentialProblem-dependent
Crossover methodMidpoint vs. coin-flipCoin-flip for more variation

Classic problem encodings

The choice of encoding determines which crossover and mutation operators are valid. (Prof Charles, CRE341 Wks 8–9)

Binary encoding — Knapsack Problem

Encode the chromosome as a bit string: 1 = include item, 0 = exclude.

ObjectValueWeight
A7031
B2010
C3920
D3719
E74

Fitness: total value of included items if total weight ≤ capacity; otherwise 0 (or penalised).

Standard single-point or two-point crossover works because swapping bit substrings produces valid candidates (any subset is encodable).

Permutation encoding — Travelling Salesman Problem

A salesman must visit all cities exactly once, minimising total distance. The chromosome is a permutation of city indices.

Problem with standard crossover: swapping arbitrary substrings creates duplicates (city visited twice). Use specialised operators:

Partially Matched Crossover (PMX):

  1. Choose two crossover points; note the mapping of swapped elements
  2. Copy the segment directly; replace duplicates in the remainder using the mapping
Parent A: 1-5-6-2-3-4
Parent B: 1-2-3-4-6-5
Segment (positions 2-4):  [6-2-3] ↔ [3-4-6]
Child:    1-5-3-4-6-2     (no city repeated)

Exchange Mutation (EM): Choose two random genes and swap them.

Before: 1-5-3-4-6-2
After:  2-5-3-4-6-1   (positions 0 and 5 swapped)

Fitness: (worst route distance) - (this route distance) — higher is better.

Sequence encoding — Genetic Lunar Lander

A lander is controlled by a sequence of (action, duration) pairs: thrust / rotate-left / rotate-right / do-nothing.

The genome encodes the sequence; each gene is an action + duration.

  • Crossover: two-point crossover on whole genes (not individual bits)
  • Mutation: randomly change an action or alter its duration
  • Fitness: how close to a successful landing (minimise distance to pad, minimise crash velocity)

Design principle: encode solutions so that crossover of two valid individuals always produces a valid individual. The encoding choice constrains which operators are correct.

Neuroevolution

Neuroevolution applies genetic algorithms to neural network weights. Instead of training a single network with backpropagation and labelled data, a population of networks is evaluated by letting them interact with an environment, then evolved using their environmental performance as fitness.

This makes it suited to problems where:

  • There is no labelled training data
  • The desired behaviour is difficult to specify explicitly
  • Performance can only be measured through interaction (game scores, survival time)

Pattern: neuroevolution agent loop

// Each frame, for each agent:
1. Read sensor inputs (normalised environmental values)
2. Feed inputs to neural network → get output action
3. Execute action in simulation
4. Accumulate fitness score
5. When dead/time limit: record fitness

// After generation:
1. Sort by fitness
2. Probabilistic selection of two parents
3. crossover() → child network
4. mutate(childNetwork, rate)
5. Replace population with children

Continuous ecosystem model

Rather than discrete generations, a persistent ecosystem keeps agents alive until health reaches zero, then reproduces them on the fly:

  • Agents consume resources to regain health
  • Each frame, health decreases slightly
  • When an agent dies, two fit parents are selected from the surviving population and a child is spawned
  • Population stays roughly constant, evolution is continuous

This feels more like a living world than a batch optimisation.

Sensor-based perception for evolved agents

To limit what an agent “knows”, attach virtual sensors — rays or radii that return normalised distance-to-target values:

float SenseFood(Vector2 foodPosition)
{
    float distance = Vector2.Distance(transform.position, foodPosition);
    return Mathf.Clamp01(1f - distance / sensorRadius);
    // 1.0 = food is here; 0.0 = food is at edge of range or beyond
}

The sensor values become the network inputs. The network learns, through evolution, which combination of sensor readings warrants which action — without the programmer specifying the rule.

In practice (game AI applications)

Use caseFitness function
Racing lineLap time, distance covered
Flappy Bird cloneFrames survived
Enemy difficulty calibrationPlayer win rate deviation from target
Procedural level generationPlayer completion rate + completion time
Weapon stat balancingWin rate symmetry across options
Creature behaviourFood consumed per lifetime

Genetic algorithms are best when:

  • A fitness function can be computed automatically
  • The solution space is too large for exhaustive search
  • Local minima are a risk (GAs escape them through mutation)

They are not the best choice when:

  • A closed-form solution exists (e.g., pathfinding — use A*)
  • Training time must be short
  • The fitness function is expensive to evaluate and the population is large

For the Unity/C# Nature of Code strand, GA is best treated as a later batch after motion, particles, and grid systems are already in place. That way students can evolve behaviour in an environment they already understand rather than learning evolution and rendering problems at the same time. See overview-unity-nature-of-code-examples.

Graph View

Backlinks