ACO: Ant Colony Optimisation — from stigmergy to the Travelling Salesman

1. Stigmergy and collective intelligence

У 1959 році ентомолог П'єр-Поль Грасс ввів термін стигмергія — координація через середовище. Мурахи не передають команди напряму: кожна лишає феромоновий слід, і наступна мурашка реагує на накопичені сліди всієї колонії. Так виникає «розподілена пам'ять» без центрального сервера.

Класичний дослід: між харчуванням і гніздом ставлять перешкоду з двома обходами — коротким і довгим. Спочатку мурахи розходяться рівномірно. Але ті, хто зайшов коротким шляхом, повертаються швидше й кладуть більше феромону. Решта починає надавати перевагу короткому маршруту — позитивний зворотній зв'язок підсилює фаворита до тих пір, поки практично весь трафік іде по оптимальному шляху.

2. Formalisation: graph and the Travelling Salesman problem

Найкласичніша задача для ACO — Задача Комівояжера (TSP): знайти найкоротший гамільтонів цикл у повному графі з n міст. Кількість можливих маршрутів — (n−1)!/2: для 20 міст це ~6×10¹⁶. Перебір неможливий.

Модель графа:

• Вузли i = 0…n−1 — міста зі координатами (xᵢ, yᵢ).
• Ребра (i, j) мають дві числові характеристики: евкліду відстань d[i][j] та феромон τ[i][j].
• Видимість ребра: η[i][j] = 1 / d[i][j] — чим коротше ребро, тим привабливіше.

Один цикл алгоритму складається з трьох фаз: побудова рішень мурахами → оцінка якості (довжина маршруту) → оновлення феромонів.

3. Pheromone trail: updating τ

Після того як усі m мурах побудували свої маршрути, феромони оновлюються двома кроками:

Step 1 — evaporation

Евапорація запобігає нескінченному накопиченню феромону та дозволяє алгоритму «забувати» старі погані рішення. Типово ρ = 0.1.

Step 2 — deposition

Мурашки, що знайшли короткий маршрут (малий Lₖ), відкладають більше феромону на свої ребра — ці ребра стають привабливішими для наступного покоління.

4. Probabilistic edge selection

Коли мурашка знаходиться у місті i і обирає наступне місто j, вона використовує правило пропорційного вибору (Ant System, Dorigo 1992):

Типові значення: α = 1, β = 5. При α = 0 — чиста жадібність за відстанню; при β = 0 — довільний пошук, керований лише феромоном.

Щоб обрати місто за ймовірністним вектором, використовують метод рулетки: генерують U(0,1), зсуваються по накопиченій сумі до першого j, де сума ≥ U.

5. Evaporation and saturation

Без евапорації феромони накопичуються нескінченно: перший знайдений маршрут залучає всіх мурах, алгоритм застряє у локальному оптимумі. Евапорація з параметром ρ вирішує це:

• Після кожної ітерації всі ребра «випаровуються» на (1−ρ).
• Ребра, яких мурахи не відвідували, поступово повертаються до τ_min.
• Нові кращі маршрути можуть перехопити лідерство.

Баланс між exploration (дослідженням) та exploitation (використанням): мале ρ → довга пам'ять, більша ρ → швидке адаптування, але нестабільність.

6. Min-Max ACO

Класичний Ant System має тенденцію до стагнації: через кілька сотень ітерацій усі мурахи йдуть одним маршрутом, дослідження зупиняється. MAX-MIN Ant System (Stützle & Hoos, 2000) вирішує проблему явними обмеженнями:

Додаткове правило: лише найкраща мурашка (за ітерацію чи глобально) відкладає феромон. Це зменшує шум від поганих рішень.

Min-Max advantage

• Pheromones never reach "zero" or "infinite" values.
• The algorithm maintains exploration into late stages.
• In practice gives results 15–35% better than classic AS on large TSP.

7. JavaScript implementation

Реалізація ACO для TSP: n міст, m мурах, iterations ітерацій. Масиви tau (феромони) та eta (видимість) зберігаються як плоскі Float64Array.

function acoTSP(cities, { m = 20, alpha = 1, beta = 5,
                              rho = 0.1, Q = 100, iterations = 200 } = {}) {
  const n = cities.length;
  const idx = (i, j) => i * n + j;

  // Distances and visibility
  const dist = new Float64Array(n * n);
  const eta  = new Float64Array(n * n);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const dx = cities[i].x - cities[j].x;
      const dy = cities[i].y - cities[j].y;
      dist[idx(i,j)] = Math.sqrt(dx*dx + dy*dy);
      eta[idx(i,j)]  = 1 / dist[idx(i,j)];
    }
  }

  // Pheromone initialisation
  const tau0 = 1 / n;
  const tau  = new Float64Array(n * n).fill(tau0);

  let bestTour = null, bestLen = Infinity;

  for (let iter = 0; iter < iterations; iter++) {
    const allTours = [];

    // Each ant builds a route
    for (let k = 0; k < m; k++) {
      const visited = new Uint8Array(n);
      const tour = [Math.floor(Math.random() * n)];
      visited[tour[0]] = 1;

      while (tour.length < n) {
        const cur = tour[tour.length - 1];
        const probs = [];
        let   sum   = 0;

        for (let j = 0; j < n; j++) {
          if (visited[j]) { probs.push(0); continue; }
          const v = Math.pow(tau[idx(cur,j)], alpha)
                  * Math.pow(eta[idx(cur,j)], beta);
          probs.push(v); sum += v;
        }

        // Roulette wheel
        let r = Math.random() * sum, acc = 0, next = -1;
        for (let j = 0; j < n; j++) {
          if (visited[j]) continue;
          acc += probs[j];
          if (acc >= r) { next = j; break; }
        }
        if (next === -1) next = probs.findIndex((v,j)=>!visited[j]);
        tour.push(next); visited[next] = 1;
      }

      // Route length
      let len = 0;
      for (let i = 0; i < n; i++)
        len += dist[idx(tour[i], tour[(i+1) % n])];
      allTours.push({ tour, len });
      if (len < bestLen) { bestLen = len; bestTour = [...tour]; }
    }

    // Evaporation
    for (let i = 0; i < tau.length; i++) tau[i] *= (1 - rho);

    // Pheromone deposition
    for (const { tour, len } of allTours) {
      const deposit = Q / len;
      for (let i = 0; i < n; i++) {
        const a = tour[i], b = tour[(i+1) % n];
        tau[idx(a,b)] += deposit;
        tau[idx(b,a)] += deposit; // symmetric graph
      }
    }
  }

  return { tour: bestTour, length: bestLen };
}

Для 50 міст на 200 ітерацій з m = 25 мурахами функція знаходить маршрут протягом <100 мс. При збільшенні n > 200 доцільно обмежити список кандидатів (nearest neighbor list) розміром 20–30.

8. ACO applications

АКО особливо корисний там, де динамічне середовище: якщо граф змінюється (ребра з'являються або зникають), мурашиний алгоритм може адаптуватися в реальному часі — феромони «пам'ятають» актуальний стан.

9. Extensions and variants

• Ant Colony System (ACS) — Dorigo & Gambardella (1997): детерміноване правило вибору з ймовірністю q₀ («exploitation») або ймовірнісне (p=1−q₀, «exploration»). На практиці ACS на 10–20 % краще за AS.
• Elitist ACO: лише найкраща глобальна мурашка отримує додаткове підсилення феромону. Швидша конвергенція, але більший ризик передчасного застрягання.
• Parallel ACO: кілька незалежних колоній іноді обмінюються найкращими рішеннями («immigration»). Ефективно для багатоядерний CPU / WASM Workers.
• 3D / Continuous ACO: замість дискретних ребер — неперервний простір параметрів. Замість матриці τ — гаусівська суміш навколо хороших точок (ACOR).
• Мурашки у симуляції: зворотний підхід — не оптимізувати, а візуалізувати феромонну мережу як анімацію. Мурахи залишають яскраві сліди, що поступово згасають.