Генетичний алгоритм — розв'язуємо задачу комівояжера

Маршрут у задачі комівояжера — це перестановка індексів міст. Кількість можливих маршрутів для N міст = (N-1)! / 2. Для N=20 це ~60 мільярдів — надто багато, щоб перевірити повним перебором.

// Генеруємо випадкові міста
const N_CITIES = 24;
const cities = Array.from({ length: N_CITIES }, () => ({
  x: 30 + Math.random() * 740,
  y: 30 + Math.random() * 440,
}));

// Маршрут = масив індексів міст у порядку відвідування
// напр. [0, 5, 3, 11, ...] — відвідати місто 0, потім 5, потім 3 і т. д.
// Завжди повертаємося до міста 0 (старт), щоб замкнути цикл

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;
}

Ми мінімізуємо відстань. Для відбору нам потрібна пристосованість, де більше — краще, тож інвертуємо відстань:

function fitness(tour) {
  return 1 / tourDistance(tour);
}
// Коротший маршрут → менша відстань → вища пристосованість → більша ймовірність розмноження

const POP_SIZE = 200;

function randomTour() {
  const tour = Array.from({ length: N_CITIES }, (_, i) => i);
  // Перемішування Фішера-Єйтса
  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]]; // відстежуємо найкращий за весь час

Обираємо k випадкових особин із популяції та повертаємо найпристосованішу з них. Більше k = сильніший тиск відбору (швидше сходиться, але може втратити різноманіття):

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;
}

Звичайний одноточковий кросовер не працює для перестановок — він створює дублікати міст. OX зберігає відносний порядок:

function orderedCrossover(parent1, parent2) {
  const n = parent1.length;
  // Обираємо випадковий сегмент із 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();

  // Копіюємо сегмент із parent1
  for (let i = start; i <= end; i++) {
    child[i] = parent1[i];
    segSet.add(parent1[i]);
  }

  // Заповнюємо решту позицій з parent2 по порядку
  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;
}

Мутація запобігає передчасній збіжності, випадково досліджуючи сусідні маршрути. Мутація обміном обирає два випадкові міста й міняє їх місцями:

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 (необов'язково, дуже ефективний для задачі комівояжера)
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++) {
        // Обертаємо сегмент [i..j] і перевіряємо, чи став коротшим
        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);
        // (спрощено — повний 2-opt дивіться в демо)
      }
    }
  }
  return tour;
}

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

function nextGeneration() {
  const newPop = [];
  // Елітизм: зберігаємо 2 найкращі особини
  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;

  // Оновлюємо найкращий
  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);

  // Малюємо найкращий маршрут
  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();

  // Малюємо міста
  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);
})();