Еволюційні алгоритми — від біології до коду

1. Ландшафт еволюційних обчислень

Усі ЕА підтримують популяцію кандидатних розв'язків і ітеративно покращують її за допомогою операторів, натхнених природою. Основні родини:

Загальний цикл, спільний для всіх ЕА:

2. Генетичні алгоритми — подання та оператори

Подання

Хромосома кодує кандидатний розв'язок. Поширені кодування включають:

• Бінарний рядок: кожен ген — це 0 або 1. Класика для відбору підмножин або дискретних параметрів.
• Дійснозначний вектор: кожен ген — число з рухомою комою. Поширений для ваг нейронних мереж.
• Перестановка: гени є перестановкою цілих чисел 1…n. Використовується для маршрутизації, планування, задачі комівояжера.

Кросовер

Кросовер поєднує гени двох батьків. Для перестановочних подань стандартний кросовер порушує обмеження впорядкування; потрібні спеціалізовані оператори:

• Порядковий кросовер (OX): копіює підсегмент від батька A; заповнює решту позицій у порядку, в якому вони з'являються в батьку B.
• Частково відображений кросовер (PMX): обмінює сегмент між батьками й усуває конфлікти за допомогою позиційного відображення.

Мутація

Мутація вносить різноманітність для виходу з локальних оптимумів. Для перестановок:

• Мутація обміну: обрати дві випадкові позиції й обміняти їхні гени.
• 2-opt інверсія: обернути випадковий підсегмент. Особливо ефективна для задачі комівояжера.
• Мутація вставки: видалити ген з однієї позиції і вставити його в інше місце.

3. Тиск добору та масштабування пристосованості

Турнірний добір: обрати k особин випадково й залишити найкращу. k = 2 поширений — простий у реалізації, з керованим тиском (більше k = більший тиск).

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

Ранговий добір: сортувати за пристосованістю; призначати ймовірність добору за ранговою позицією, а не за сирою пристосованістю. Стійкіший за рулетку; з керованим лінійним або експоненційним ранговим масштабуванням.

4. Еволюційні стратегії та самоадаптація

Еволюційні стратегії (ES) працюють безпосередньо в ℝⁿ з гаусовою мутацією. Кожна особина несе як вектор параметрів x, так і вектор розміру кроку σ, який еволюціонує разом з ним:

Поширене позначення (μ + λ)-ES підтримує μ батьків і породжує λ нащадків; усі μ + λ особин змагаються за наступне покоління. (μ, λ)-ES відкидає всіх батьків, нав'язуючи агресивніше дослідження.

Правило успіху 1/5 Рехенберга є простішою альтернативою: якщо понад 20% мутацій покращують пристосованість, збільшити σ у 1.22 раза; нижче 20% — зменшити на той самий множник. Коли самоадаптація недоступна, це правило автоматично підтримує хороший розмір кроку.

5. CMA-ES — адаптація матриці коваріації

CMA-ES (еволюційна стратегія з адаптацією матриці коваріації, Hansen та Ostermeier, 2001) — поточний золотий стандарт для безпохідної неперервної оптимізації до кількох сотень вимірів. Вона навчає повну матрицю коваріації розподілу пошуку:

Математичні деталі складні, але загальна інтуїція елегантна: C локально вловлює форму ландшафту пристосованості. Після багатьох ітерацій власні вектори C вирівнюються з «легкими напрямками» ландшафту, дозволяючи CMA-ES робити значно ефективніші кроки, ніж фіксований сферичний розподіл.

CMA-ES має складність O(n²) на покоління й рекомендується для n ≤ 200–300. Для вищих розмірностей сепарабельний CMA-ES (лише діагональна C) поширює його на тисячі змінних.

6. JavaScript: GA для задачі комівояжера

// Задача комівояжера: знайти найкоротший маршрут через N міст
// Хромосома: перестановка індексів міст [0 .. N-1]

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

// Порядковий кросовер (OX)
function oxCrossover(p1, p2) {
  const n  = p1.length;
  const i1 = Math.floor(Math.random() * n);
  const i2 = Math.floor(Math.random() * n);
  const [lo, hi] = [Math.min(i1, i2), Math.max(i1, i2)];
  const segment = new Set(p1.slice(lo, hi));
  const child = p1.slice(lo, hi);
  for (const gene of p2) if (!segment.has(gene)) child.push(gene);
  return [...child.slice(n - lo), ...child.slice(0, n - lo)];
}

// Мутація 2-opt інверсією
function mutate(tour, rate) {
  if (Math.random() > rate) return tour;
  const i = Math.floor(Math.random() * tour.length);
  const j = Math.floor(Math.random() * tour.length);
  const [lo, hi] = [Math.min(i, j), Math.max(i, j)];
  return [
    ...tour.slice(0, lo),
    ...tour.slice(lo, hi + 1).reverse(),
    ...tour.slice(hi + 1),
  ];
}

function runGA(cities, { popSize = 100, generations = 500, mutRate = 0.1, eliteN = 5 } = {}) {
  const n = cities.length;

  // Ініціалізація випадковими перестановками
  let pop = Array.from({ length: popSize }, () =>
    [...Array(n).keys()].sort(() => Math.random() - 0.5));

  for (let gen = 0; gen < generations; gen++) {
    // Оцінка (менша відстань = вища пристосованість)
    pop.sort((a, b) => tourDistance(cities, a) - tourDistance(cities, b));

    // Елітизм: зберегти найкращі eliteN без змін
    const nextPop = pop.slice(0, eliteN);

    while (nextPop.length < popSize) {
      // Турнірний добір (k=3)
      const tournament = () => {
        let best = pop[Math.floor(Math.random() * pop.length)];
        for (let k = 1; k < 3; k++) {
          const c = pop[Math.floor(Math.random() * pop.length)];
          if (tourDistance(cities, c) < tourDistance(cities, best)) best = c;
        }
        return best;
      };
      const child = mutate(oxCrossover(tournament(), tournament()), mutRate);
      nextPop.push(child);
    }
    pop = nextPop;
  }
  return pop[0];   // найкращий маршрут
}

// Приклад: 10 випадкових міст
const cities = Array.from({ length: 10 }, () =>
  ({ x: Math.random() * 100, y: Math.random() * 100 }));
const best = runGA(cities);
console.log('Найкращий маршрут:', best);
console.log('Відстань:', tourDistance(cities, best).toFixed(2));

7. Типові підводні камені та налаштування

Передчасна збіжність

Популяція втрачає різноманітність і застрягає в локальному оптимумі ще до знаходження глобального. Засоби: зменшити тиск добору (менший розмір турніру); збільшити темп мутації; використати географічне ніширування (острівна модель з міграцією); перезапуск. Різноманітність популяції можна дешево відстежувати, обчислюючи середню попарну відстань Геммінга.

Роздування (генетичне програмування)

У граматичних або деревоподібних поданнях програми ростуть без обмежень («роздування»), тоді як пристосованість стагнує. Тиск ощадливості (штраф за довші програми) або жорсткі обмеження розміру запобігають цьому.

Вибір гіперпараметрів

• Розмір популяції: зазвичай 50–200 для GA; 4 + ⌊3 ln n⌋ для CMA-ES.
• Темп мутації: ~1/n для бінарного GA (переворот одного біта на хромосому); 0.1–0.3 для перестановочного GA.
• Темп кросоверу: 0.6–0.9 для бінарного; 1.0 для перестановочного (завжди схрещувати).
• Бюджет: виконувати до стагнації (немає покращення протягом 50 поколінь), потім перезапустити.

8. Застосування

Пошук нейронної архітектури (NAS)

Еволюційні методи (NEAT, регуляризована еволюція) одночасно відкривають топології та ваги нейронних мереж — кодуючи структуру графа мережі як хромосому. AmoebaNet від Google знайшла передові класифікатори зображень за допомогою еволюційного пошуку.

Розробка ліків

Молекулярні структури подаються як рядки SMILES або молекулярні графи. ЕА досліджують хімічний простір, мутуючи функціональні групи та схрещуючи молекулярні каркаси, керуючись прогнозованою спорідненістю зв'язування із сурогатної моделі (часто графової нейронної мережі).

Планування та логістика

Планування виробничих цехів, маршрутизація транспорту, планування супутникових спостережень і складання екіпажів авіакомпаній — усе це складні комбінаторні задачі, де GA зі специфічними для предметної області операторами конкурують із (або переважають) спеціалізованими точними розв'язувачами.