Genetic Algorithm — Solve the TSP

A TSP tour is a permutation of city indices. Number of possible tours for N cities = (N-1)! / 2. For N=20 that's ~60 billion — way too many to check exhaustively.

// Generate random cities
const N_CITIES = 24;
const cities = Array.from({ length: N_CITIES }, () => ({
  x: 30 + Math.random() * 740,
  y: 30 + Math.random() * 440,
}));

// A tour = array of city indices in visit order
// e.g. [0, 5, 3, 11, ...] — visit city 0, then 5, then 3, etc.
// Always return to city 0 (the start) to complete the loop

function tourDistance(tour) {
  let dist = 0;
  for (let i = 0; i < tour.length; i++) {
    const a = cities[tour[i]];
    const b = cities[tour[(i + 1) % tour.length]];
    dist += Math.hypot(b.x - a.x, b.y - a.y);
  }
  return dist;
}

We minimise distance. For selection we need a fitness that is higher is better — invert the distance:

function fitness(tour) {
  return 1 / tourDistance(tour);
}
// Shorter tour → smaller distance → larger fitness → more likely to reproduce

const POP_SIZE = 200;

function randomTour() {
  const tour = Array.from({ length: N_CITIES }, (_, i) => i);
  // Fisher-Yates shuffle
  for (let i = tour.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [tour[i], tour[j]] = [tour[j], tour[i]];
  }
  return tour;
}

let population = Array.from({ length: POP_SIZE }, randomTour);
let best = [...population[0]]; // track all-time best

Pick k random individuals from the population and return the fittest one. Higher k = more selection pressure (converges faster but may lose diversity):

function tournament(pop, k = 5) {
  let best = null;
  let bestFit = -Infinity;
  for (let i = 0; i < k; i++) {
    const candidate = pop[Math.floor(Math.random() * pop.length)];
    const f = fitness(candidate);
    if (f > bestFit) { bestFit = f; best = candidate; }
  }
  return best;
}

Regular single-point crossover doesn't work for permutations — it creates duplicate cities. OX preserves relative order:

function orderedCrossover(parent1, parent2) {
  const n = parent1.length;
  // Pick a random segment from parent1
  const start = Math.floor(Math.random() * n);
  const end   = start + Math.floor(Math.random() * (n - start));

  const child = new Array(n).fill(-1);
  const segSet = new Set();

  // Copy segment from parent1
  for (let i = start; i <= end; i++) {
    child[i] = parent1[i];
    segSet.add(parent1[i]);
  }

  // Fill remaining positions from parent2 in order
  let pos = (end + 1) % n;
  for (let i = 0; i < n; i++) {
    const city = parent2[(end + 1 + i) % n];
    if (!segSet.has(city)) {
      child[pos] = city;
      pos = (pos + 1) % n;
    }
  }
  return child;
}

Mutation prevents premature convergence by randomly exploring nearby tours. Swap mutation picks two random cities and exchanges them:

const MUTATION_RATE = 0.02;

function mutate(tour) {
  const child = [...tour];
  for (let i = 0; i < child.length; i++) {
    if (Math.random() < MUTATION_RATE) {
      const j = Math.floor(Math.random() * child.length);
      [child[i], child[j]] = [child[j], child[i]];
    }
  }
  return child;
}

// 2-opt local search (optional, very effective for TSP)
function twoOpt(tour) {
  let improved = true;
  while (improved) {
    improved = false;
    for (let i = 1; i < tour.length - 1; i++) {
      for (let j = i + 1; j < tour.length; j++) {
        // Reverse segment [i..j] and check if shorter
        const d1 = Math.hypot(cities[tour[i-1]].x - cities[tour[i]].x,
                              cities[tour[i-1]].y - cities[tour[i]].y)
                 + Math.hypot(cities[tour[j]].x   - cities[tour[j%tour.length+1===tour.length?0:j+1]].x,
                              cities[tour[j]].y   - cities[tour[j%tour.length+1===tour.length?0:j+1]].y);
        // (simplified — see full demo for complete 2-opt)
      }
    }
  }
  return tour;
}

const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');
let generation = 0;

function nextGeneration() {
  const newPop = [];
  // Elitism: keep top 2 individuals
  const sorted = [...population].sort((a, b) => fitness(b) - fitness(a));
  newPop.push([...sorted[0]], [...sorted[1]]);

  while (newPop.length < POP_SIZE) {
    const p1 = tournament(population);
    const p2 = tournament(population);
    const child = mutate(orderedCrossover(p1, p2));
    newPop.push(child);
  }
  population = newPop;

  // Update best
  const fittest = population.reduce((a, b) => fitness(a) > fitness(b) ? a : b);
  if (tourDistance(fittest) < tourDistance(best)) best = [...fittest];

  generation++;
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Draw best tour
  ctx.strokeStyle = '#22c55e';
  ctx.lineWidth = 2;
  ctx.beginPath();
  for (let i = 0; i <= best.length; i++) {
    const c = cities[best[i % best.length]];
    i === 0 ? ctx.moveTo(c.x, c.y) : ctx.lineTo(c.x, c.y);
  }
  ctx.stroke();

  // Draw cities
  ctx.fillStyle = '#f8fafc';
  for (const city of cities) {
    ctx.beginPath();
    ctx.arc(city.x, city.y, 5, 0, Math.PI*2);
    ctx.fill();
  }

  ctx.fillStyle = '#94a3b8';
  ctx.font = '14px monospace';
  ctx.fillText(`Gen: ${generation}  Best: ${tourDistance(best).toFixed(1)}px`, 10, 20);
}

let running = true;
(function loop() {
  if (!running) return;
  nextGeneration();
  draw();
  requestAnimationFrame(loop);
})();