Genetic Algorithms: Evolving a Solution You Don't Know How to Compute

Some problems you can solve directly. Others you can only recognise a good answer to. Given a route through 50 cities you can measure its length instantly, but computing the shortest one means confronting 50! possibilities. Given a walking gait you can measure how far the robot got, but deriving the optimal joint sequence from first principles is hopeless.

For that second class — evaluating is cheap, deriving is impossible — you can borrow the only algorithm known to have designed a working eye: evolution. Generate random candidates, keep the ones that score better, copy them with small errors, repeat. No gradient, no model of the problem, no idea in advance what a good solution looks like.

I built a browser simulation to see whether that really works: a population of dots, each executing a fixed sequence of random moves, evolving over generations until they find a goal. Code: gitlab.com/rustam.niraula90/genetic-algorithm.

These are my notes from building it and from what surprised me afterwards.

---

Concept 1: The genome — encode the solution, not the solver

The first decision in any genetic algorithm is what a candidate solution is as data. I didn’t appreciate how much rides on this until later: get it wrong and nothing else can work.

Here a candidate is an entire pre-committed movement plan — 500 direction codes, generated at random:

export default class Brain {
  constructor() {
    this.step = 0;
    this.size = window.$BRAIN_SIZE;      // 500
    this.directions = [];
    this.mutationRate = (window.$MUTATION_PERCENTAGE / 100);
    this.randomize();
  }

  randomize() {
    for (var i = 0; i < this.size; i++) {
      this.directions[i] = getRndInteger(0, 5);   // 0=stay, 1=left, 2=up, 3=right, 4=down
    }
  }
}

Three properties make this workable, and I’ve since treated them as the general criteria:

Fixed length. Every genome is 500 integers, so any two are structurally interchangeable and mutation can’t produce something malformed.

Every value is legal. A direction code is 0–4 and all five mean something (0 is “stand still”). There’s no such thing as an invalid genome, so mutation never needs repair logic — a large simplification worth designing for deliberately.

No intelligence inside. The dot has no goal-seeking behaviour at all. It cannot see the target. It just replays its list:

move() {
    if (this.brain.directions.length > this.brain.step) {
      this.currentMove = this.brain.directions[this.brain.step];
      this.brain.step++;
    } else {
      this.dead = true;      // out of moves
    }
    switch (this.currentMove) {
      case 1: this.positionX -= window.$ONE_STEP; break;   // left
      case 2: this.positionY -= window.$ONE_STEP; break;   // up
      case 3: this.positionX += window.$ONE_STEP; break;   // right
      case 4: this.positionY += window.$ONE_STEP; break;   // down
      default: break;                                       // stay
    }
}

That last property is what made the result convincing to me. Any competence that emerges came from selection, not from logic I wrote.

Concept 2: Fitness — the only thing you’re allowed to tell it

The fitness function is your entire communication channel with the algorithm. It isn’t a hint or a heuristic; it’s the definition of “better,” and evolution optimises exactly what you write, including the parts you didn’t mean.

calculateFitness() {
    if (this.reachedGoal) {
      this.fitness = 1 + 1.0 / (this.brain.step * this.brain.step);
    } else {
      var distanceToGoal = this.calculateDistance(this.positionX, this.positionY, 100, 30);
      this.fitness = 1.0 / distanceToGoal;
    }
}

Two regimes, and the structure matters more than the formulas:

Not there yet: 1/distance. Closer is better, and inverting distance turns “minimise” into “maximise” while compressing the scale — halving your distance doubles your score, so improvements near the goal count for far more than the same absolute gain far away.

Arrived: 1 + 1/steps². The 1 + guarantees any dot that reaches the goal outscores every dot that didn’t, no matter how close the near-miss got. That hard tier boundary encodes a priority: first solve it, then optimise it. Inside the winners’ tier, 1/steps² rewards doing it faster, and squaring makes that pressure sharp.

This shape — a discontinuous jump between “task achieved” and “not achieved,” with a smooth gradient inside each tier — is the most reusable thing I took from the project. The smooth part gives the population a slope to climb when nobody has succeeded yet; the jump makes sure partial credit never outranks real success.

The gradient part is not optional. If fitness were simply “1 if you reached the goal, else 0,” the first generation would be all zeroes, selection would have nothing to prefer, and the search would never start. Distance gives evolution something to work with before anyone has won. Designing that intermediate signal is usually the hard part of applying a GA to a real problem, and it’s where I’d expect to spend my time on the next one.

Concept 3: The generational loop

Evolution is four phases repeated. Run every candidate until it can’t continue; score them; build a new population from the survivors; perturb it.

if (!population.allDotsDead() && !population.complete) {
    population.update();               // 1. simulate this generation
} else {
    population.calculateFitness();     // 2. score everyone
    population.naturalSelection();     // 3. breed the next generation
    population.mutateBabies();         // 4. introduce variation
    population.show();
    population.complete = false;
}

A generation ends when every dot is either dead (out of bounds or out of moves) or has arrived:

update() {
    if (!this.dead && !this.reachedGoal) {
      this.move();
      if (this.positionX <= 1 || this.positionY <= 1 ||
          this.positionX >= 198 || this.positionY >= 398) {
        this.dead = true;
      } else if ((this.positionX > 90 && this.positionX < 105) &&
                 (this.positionY > 20 && this.positionY < 35)) {
        this.reachedGoal = true;
      }
    }
}

Hitting a wall is fatal, which means the constraint is expressed through mortality rather than through the fitness function — an obstacle doesn’t reduce your score, it truncates your run, freezing your position at the wall and therefore your distance. I like this more than I expected to: constraints implemented as early termination avoid the penalty-weight tuning that constraint terms in a fitness function usually drag in.

Concept 4: Mutation is the only source of novelty

Copying survivors preserves what works. Mutation invents anything new:

mutate() {
    for (var i = 0; i < this.directions.length; i++) {
      var rand = Math.random();
      if (rand < this.mutationRate) {
        this.directions[i] = getRndInteger(0, 5);
      }
    }
}

Each gene independently has a mutationRate chance of being redrawn. The rate is the central tuning knob, and both extremes fail in opposite ways:

• Too low → offspring are near-copies, the population converges on a local optimum and stops improving.
• Too high → good genomes get scrambled faster than selection can consolidate them, and the search degenerates into random guessing.

I exposed it as a live input in the UI, along with population size, genome length and step length, which turned out to be the best decision in the project — you can watch convergence stall at 2% and watch it thrash at 80%. My default is 30%, which is high next to the conventional 1–5%, and the reason is directly tied to the selection design in the next section.

Concept 5: Elitism — don’t lose the best thing you found

Because reproduction is random, the best solution in a generation can fail to be reproduced accurately and the population gets worse. Elitism fixes that: copy the champion into the next generation unmutated.

newDots[0] = this.dotList[this.bestDotIndex].getBaby();
newDots[0].isBest = true;
this.bestDot = this.dotList[this.bestDotIndex];

mutateBabies() {
    this.dotList.forEach((dot) => {
      if (!dot.isBest) {
        dot.brain.mutate();     // the elite is deliberately skipped
      }
    });
}

This guarantees monotonic improvement: best-ever fitness can never decrease. Cheap insurance, and nearly every practical GA includes some form of it. The elite is also rendered in a distinct colour, so you can watch the current champion’s path against the cloud of its mutated descendants — the clearest visual in the whole simulation, and the thing that made the mechanism obvious to me.

Design note: what my selection strategy is, and what it costs

Here’s the part I find most interesting in hindsight. Parents are chosen like this:

selectParent() {
    return this.dotList[this.bestDotIndex];
}

Every child descends from the single best dot. Meanwhile the code computes a total fitness across the population:

calculateFitnessSum() {
    this.fitnessSum = 0;
    for (var i = 0; i < this.dotList.length; i++) {
      this.fitnessSum += this.dotList[i].fitness;
    }
}

A fitness sum has one classical purpose: fitness-proportionate selection, better known as roulette wheel. Pick a random number in [0, fitnessSum), walk the population accumulating fitness, take whoever you land on. A dot with twice the fitness is twice as likely to be a parent, but a mediocre dot still gets a chance. I built the odometer while working out how selection should behave, and shipped the simpler strategy — pure elitist selection — because it was enough to solve the maze.

What I have, then, is closer to parallel hill climbing: one parent, cloned a thousand times, each copy randomly perturbed, keep the best, repeat. It works, and having both designs side by side in my head is what finally explained what proportionate selection contributes:

Diversity as insurance against local optima. With one parent, the whole population sits in one neighbourhood of the search space. If that neighbourhood is a dead end — a path hugging a wall that can’t be extended without dying — the only escape is a lucky mutation from that single lineage. With proportionate selection the second- and fifth- and fiftieth-best dots also reproduce, so the population explores several regions at once, and one of them may route around the obstacle that trapped the leader.

Ancestral variety, which is what crossover needs. Full GAs also combine parents: first half of one genome, second half of another. That only helps if the parents are meaningfully different. Descend everyone from one ancestor and crossover has nothing to mix — which is why there’s no crossover in this version. The two choices are linked, and I only saw that after the fact.

It also explains my 30% mutation rate. With a population collapsed to one lineage, mutation is the only source of diversity, so it has to carry a load that selection would normally share. That gave me the sharpest lesson of the project: a genetic algorithm’s power comes from maintaining a diverse population, not from mutation volume. Adding roulette-wheel selection and single-point crossover — both small changes, and the sum is already computed — should let the mutation rate drop by an order of magnitude while searching better, because variation would come from having many good ideas instead of from repeatedly perturbing one. That’s the next iteration.

When to reach for this

Evolutionary search fits when:

• You can evaluate a candidate but not derive the best one.
• There’s no usable gradient — the space is discrete, or the objective isn’t differentiable.
• Very good is acceptable; provably optimal isn’t required.

And it’s the wrong tool when a gradient exists (use it — it’s vastly faster), when evaluation is expensive (thousands of candidates × many generations gets brutal), or when the problem has structure a purpose-built algorithm exploits.

What made this worth building wasn’t the maze getting solved. It was watching a thousand dots spray outward in generation one and, by generation forty, trace a coherent path to a goal none of them could see — carrying nothing but a list of 500 random numbers, filtered by the only feedback they ever got.