Роевой интеллект: муравьиные алгоритмы и PSO

В генетических алгоритмах популяция улучшается через отбор и рекомбинацию: хорошие решения скрещиваются, плохие вымирают. Роевой интеллект (swarm intelligence) устроен принципиально иначе — никто не умирает и никто не скрещивается. Агенты живут весь прогон, каждый двигается по своим локальным правилам, а координация возникает из общей информации: следа в среде или знания о том, где сейчас лучший.

Это не косметическое различие. В ГА информация о хороших решениях передаётся через генотип потомка; в рое — через среду или соседей, а само решение агент строит заново на каждой итерации. Отсюда другие сильные стороны, другие патологии и другие ручки настройки.

В этой статье разбираем два алгоритма, которые действительно работают и действительно используются: ACO (Ant Colony Optimization) для комбинаторных задач, где решение конструируется по шагам, и PSO (Particle Swarm Optimization) для непрерывных, где решение — точка в $\mathbb{R}^d$. И отдельно — почему к остальному «зоопарку» роевых алгоритмов стоит относиться скептически.

Три принципа, из которых состоит любой рой

1. Локальность правил. Отдельный агент не видит всей задачи. У муравья нет карты графа, у частицы нет градиента. Есть только то, что доступно «здесь и сейчас»: концентрация феромона на исходящих рёбрах, координаты лучшего соседа.
2. Стигмергия или социальное влияние. Агенты не общаются напрямую. В ACO координация идёт через среду (термин стигмергия, Грассе, 1959 — про постройку термитника): муравей меняет феромон, феромон меняет поведение следующего муравья. В PSO координация идёт через разделяемый рекорд соседства.
3. Положительная обратная связь плюс забывание. Хорошее решение усиливается (автокатализ), но без противовеса система схлопнется в первое попавшееся. Противовес — испарение феромона в ACO и инерция/стохастика в PSO. Баланс усиления и забывания и есть весь дизайн роевого алгоритма.

Дальше — по порядку, начиная с муравьёв.

Часть I. ACO: решение живёт в среде

Двойной мост

Биологическая основа ACO — не выдумка, а воспроизводимый эксперимент. Дёнёбур и коллеги (Deneubourg et al., 1990) соединили гнездо аргентинских муравьёв с кормушкой двумя мостиками разной длины. Муравьи не умеют мерить длину. Тем не менее через несколько десятков минут колония почти целиком переходила на короткий мост.

Механизм чисто механический: муравьи, случайно выбравшие короткий путь, возвращаются раньше, значит успевают положить феромон на этот путь больше раз за единицу времени. Концентрация растёт → вероятность выбора растёт → ещё больше муравьёв → ещё больше феромона. Длинный путь тем временем испаряется.

Ключевой вывод для инженера: решение хранится не в агенте, а в разделяемой структуре данных. Муравей — это одноразовый сэмплер из распределения, заданного феромоном. Поэтому ACO иногда точнее называть не «популяционным алгоритмом», а методом построения и обновления вероятностной модели решения — родственником оценки распределения (EDA) и, если хотите, дальним предком того, как языковая модель сэмплирует токен за токеном из выученного распределения.

Формальная модель

ACO применим, когда решение можно сконструировать пошагово из компонентов. Формально задаётся конструктивный граф: множество компонентов $C = {c_1, \dots, c_k}$, частичное решение $s^p$ — последовательность компонентов, и множество допустимых продолжений $N(s^p) \subseteq C$.

Каждому компоненту (или переходу) сопоставлены две величины:

• $\tau_{ij}$ — феромон: выученная колонией «полезность» выбора $j$ в контексте $i$. Изменяется во времени.
• $\eta_{ij}$ — эвристика: априорная, статически или динамически вычислимая привлекательность. Для TSP это $1/d_{ij}$; для приоритизации тестов — сколько новых дефектов ловит тест.

Муравей на каждом шаге выбирает следующий компонент вероятностно:

$$ p_{ij} = \frac{\tau_{ij}^{\alpha},\eta_{ij}^{\beta}}{\sum_{l \in N(s^p)} \tau_{il}^{\alpha},\eta_{il}^{\beta}} $$

Здесь $\alpha$ — вес опыта колонии, $\beta$ — вес «жадности». Крайние случаи полезно держать в голове:

• $\alpha = 0$ — феромон игнорируется, получается стохастический жадный алгоритм с рестартами;
• $\beta = 0$ — эвристика игнорируется, поиск ведётся вслепую и сходится медленно;
• $\alpha$ велико — быстрая сходимость и стагнация: все муравьи ходят одним маршрутом.

После того как все $m$ муравьёв построили решения, феромон обновляется:

$$ \tau_{ij} \leftarrow (1-\rho),\tau_{ij} + \sum_{k \in \text{депонирующие}} \Delta\tau_{ij}^{k}, \qquad \Delta\tau^{k}_ {ij} = \begin{cases} Q \cdot f(s^k), & (i,j) \in s^k \ 0, & \text{иначе}\end{cases} $$

Множитель $(1-\rho)$ — испарение, единственный механизм забывания. Без него алгоритм монотонно накапливает предпочтения и через сотню итераций перестаёт исследовать что-либо новое.

Обратите внимание на порядок в диаграмме: испарение применяется ко всей матрице, депонирование — только к рёбрам избранных решений. Перепутать порядок или испарять только «использованные» рёбра — классическая ошибка реализации, ломающая нормировку.

Три варианта, которые надо знать

MMAS — то, что стоит реализовывать по умолчанию. Ограничение снизу $\tau_{\min} > 0$ математически гарантирует, что ни один переход никогда не становится невозможным: алгоритм не может окончательно «отрезать» часть пространства поиска. Ограничение сверху не даёт одному раннему удачному решению задавить всё остальное. Плюс рестарт феромона (сброс к $\tau_{\max}$) при детекте стагнации.

Задача: приоритизация регрессионных тестов

Возьмём настоящую SBSE-задачу, а не TSP. Регрессионный прогон идёт 6 часов, CI падает по таймауту, а падение обычно случается из-за одного-двух дефектов. Хочется переупорядочить тесты так, чтобы дефекты обнаруживались как можно раньше — тогда фидбэк разработчику приходит через 10 минут, а не через 6 часов.

Метрика — APFD (Average Percentage of Faults Detected, Rothermel et al., IEEE TSE 2001):

$$ \mathrm{APFD} = 1 - \frac{TF_1 + TF_2 + \dots + TF_m}{n,m} + \frac{1}{2n} $$

где $n$ — число тестов, $m$ — число дефектов, $TF_i$ — позиция первого теста, обнаруживающего дефект $i$. APFD близка к 1, когда все дефекты вылавливаются в начале прогона.

Задача — перестановочная, то есть ровно та, для которой ACO придуман: решение конструируется позиция за позицией. Пространство поиска — $n!$, что для 500 тестов исключает перебор навсегда.

Важный дизайнерский выбор: на чём держать феромон. Для маршрутных задач естественно $\tau_{ij}$ = «после компонента $i$ идёт $j$». Для приоритизации важно не соседство, а абсолютная позиция: тест, который надо ставить первым, надо ставить первым всегда. Поэтому используем $\tau[\text{pos}][t]$ — «насколько хорошо тест $t$ стоит на позиции pos».

"""ACO (в варианте MAX-MIN) для приоритизации регрессионных тестов."""
from __future__ import annotations
import random
from typing import Sequence


def apfd(order: Sequence[int], covers: list[set[int]], n_faults: int) -> float:
    """APFD для заданного порядка тестов.

    covers[t] — множество дефектов, которые ловит тест t.
    Сложность: O(n + суммарный размер covers) — линейно по матрице покрытия.
    """
    n = len(order)
    first: list[int | None] = [None] * n_faults
    left = n_faults
    for pos, t in enumerate(order, start=1):
        for f in covers[t]:
            if first[f] is None:
                first[f] = pos
                left -= 1
        if left == 0:                      # все дефекты пойманы, хвост не влияет
            break
    # непойманный дефект штрафуем позицией n+1 (иначе метрика неопределена)
    total = sum(p if p is not None else n + 1 for p in first)
    return 1.0 - total / (n * n_faults) + 1.0 / (2 * n)


class MMASPrioritizer:
    def __init__(self, covers: list[set[int]], n_faults: int, *,
                 n_ants: int = 20, alpha: float = 1.0, beta: float = 3.0,
                 rho: float = 0.10, seed: int | None = None) -> None:
        self.covers, self.n_faults = covers, n_faults
        self.n = len(covers)
        self.n_ants, self.alpha, self.beta, self.rho = n_ants, alpha, beta, rho
        self.rng = random.Random(seed)
        # τ_max/τ_min пересчитываются по текущему рекорду (правило MMAS)
        self.tau_max = 1.0 / self.rho
        self.tau_min = self.tau_max / (2.0 * self.n)
        # матрица позиция × тест
        self.tau = [[self.tau_max] * self.n for _ in range(self.n)]

    def _construct(self) -> list[int]:
        """Один муравей строит перестановку. O(n²·k), k — средний размер covers."""
        unused = list(range(self.n))
        uncovered = set(range(self.n_faults))
        order: list[int] = []
        for pos in range(self.n):
            weights = []
            for t in unused:
                # ДИНАМИЧЕСКАЯ эвристика: сколько ЕЩЁ НЕ пойманных дефектов даст тест.
                # +1 — чтобы вес не обнулялся у тестов, не дающих нового покрытия.
                eta = 1.0 + len(self.covers[t] & uncovered)
                weights.append((self.tau[pos][t] ** self.alpha) * (eta ** self.beta))
            t = self.rng.choices(unused, weights=weights, k=1)[0]
            order.append(t)
            unused.remove(t)
            uncovered -= self.covers[t]
        return order

    def _deposit(self, order: Sequence[int], quality: float) -> None:
        for pos, t in enumerate(order):
            self.tau[pos][t] = min(self.tau[pos][t] + quality, self.tau_max)

    def run(self, iterations: int = 200, elite_every: int = 5):
        best_order, best_f = None, -1.0
        stagnation = 0
        for it in range(iterations):
            iter_order, iter_f = None, -1.0
            for _ in range(self.n_ants):
                order = self._construct()
                f = apfd(order, self.covers, self.n_faults)
                if f > iter_f:
                    iter_order, iter_f = order, f
            if iter_f > best_f:
                best_order, best_f = iter_order, iter_f
                stagnation = 0
                # границы MMAS привязаны к качеству рекорда
                self.tau_max = best_f / self.rho
                self.tau_min = self.tau_max / (2.0 * self.n)
            else:
                stagnation += 1

            # 1) испарение — по ВСЕЙ матрице
            for pos in range(self.n):
                row = self.tau[pos]
                for t in range(self.n):
                    row[t] = max(row[t] * (1.0 - self.rho), self.tau_min)
            # 2) депонирует ровно один муравей: периодически — global-best,
            #    в остальные итерации — iteration-best (баланс интенсификации)
            src, q = ((best_order, best_f) if it % elite_every == 0
                      else (iter_order, iter_f))
            self._deposit(src, q)

            # 3) рестарт феромона при затяжной стагнации
            if stagnation >= 40:
                self.tau = [[self.tau_max] * self.n for _ in range(self.n)]
                stagnation = 0
        return best_order, best_f


if __name__ == "__main__":
    rng = random.Random(7)
    N_TESTS, N_FAULTS = 60, 25
    # синтетическая матрица покрытия: несколько «дешёвых» тестов ловят много
    covers = [set(rng.sample(range(N_FAULTS), rng.choice([1, 1, 2, 2, 3, 6])))
              for _ in range(N_TESTS)]

    baseline = apfd(list(range(N_TESTS)), covers, N_FAULTS)
    aco = MMASPrioritizer(covers, N_FAULTS, seed=7)
    order, score = aco.run(iterations=120)
    print(f"исходный порядок APFD = {baseline:.4f}")
    print(f"ACO (MMAS)     APFD = {score:.4f}")

Сложность. Построение одного решения — $O(n^2 k)$, где $k$ — средний размер множества покрытия (внешний цикл по $n$ позициям, внутренний по оставшимся кандидатам). За прогон: $O(I \cdot m \cdot n^2 k)$ по времени, где $I$ — итерации, $m$ — муравьи. Память — $O(n^2)$ на феромонную матрицу. Для $n = 5000$ тестов матрица «позиция × тест» — это 25 млн ячеек, то есть 200 МБ во float64: на этом масштабе позиционный феромон заменяют на разреженный (только top-$K$ кандидатов на позицию) или переходят на группировку тестов.

Честное предупреждение. Для приоритизации тестов простая жадная эвристика «дополнительное покрытие» (additional greedy) работает удивительно хорошо, и работа Li, Harman, Hierons, IEEE TSE 2007 показала, что метаэвристики обыгрывают её далеко не всегда. Если вы внедряете ACO — обязательно сравнивайте с жадным baseline. Публикации типа Singh, Kaur, Suri, ACM SIGSOFT SEN 2010 про ACO для приоритизации существуют, но воспроизводимость в этой подобласти исторически слабая.

Настройка ACO: что реально крутить

Главный ресурс — число вычислений фитнеса, а не число итераций. Сравнивать конфигурации надо при равном бюджете оценок; 50 муравьёв × 100 итераций и 10 муравьёв × 500 итераций — это одинаковая цена, и почти всегда вторая конфигурация лучше.

Где ACO действительно в проде

• Маршрутизация и логистика. VRP/TSP-решатели: эталонная реализация Штютцле ACOTSP — рабочий C-код, а не псевдокод из статьи.
• Сетевая маршрутизация. AntNet (Di Caro & Dorigo, JAIR 1998) — адаптивная маршрутизация пакетов, где феромон естественно отражает меняющуюся нагрузку. Это тот редкий случай, когда динамичность среды — аргумент в пользу ACO: феромон сам «переучивается» при изменении топологии, тогда как решение, найденное ГА, устаревает целиком.
• Планирование. Расстановка задач по машинам/агентам, составление расписаний CI-джоб.
• В SBSE. Генерация тестовых путей по CFG (путь = конструкция из рёбер — идеальная посадка на модель ACO), приоритизация и селекция тестов, поиск последовательностей вызовов API.

Часть II. PSO: рой в непрерывном пространстве

Интуиция

Кеннеди и Эберхарт (ICNN'95) начинали с симуляции стаи птиц и обнаружили, что если убрать из модели почти всё, останется работающий оптимизатор из двух строк. Каждая частица — это точка $x_i \in \mathbb{R}^d$ с вектором скорости $v_i$. Частица помнит свой лучший результат $p_i$ и знает лучший результат соседей $g_i$. Скорость обновляется как сумма трёх тяг:

$$ v_i \leftarrow \underbrace{w,v_i}_ {\text{инерция}} + \underbrace{c_1 r_1 \odot (p_i - x_i)}_ {\text{когнитивная}} + \underbrace{c_2 r_2 \odot (g_i - x_i)}_ {\text{социальная}}, \qquad x_i \leftarrow x_i + v_i $$

где $r_1, r_2 \sim U(0,1)^d$ генерируются заново на каждой итерации покомпонентно (это важно: общий скаляр вместо вектора резко ухудшает поиск), а $\odot$ — поэлементное умножение.

Физическая аналогия точная: частица — это тело с импульсом, привязанное двумя пружинами со случайной жёсткостью к двум точкам притяжения. Инерция позволяет проскакивать мимо аттрактора и исследовать за ним — именно из-за этого PSO не сваливается в ближайший локальный минимум мгновенно.

Инерция и коэффициент сжатия

В исходной версии 1995 года $w$ не было, и скорости взрывались экспоненциально. Два исторических исправления:

1. Inertia weight (Shi & Eberhart, 1998): линейно уменьшать $w$ от 0.9 к 0.4 по ходу прогона — сначала исследуем, потом уточняем. Простой и до сих пор рабочий приём.
2. Constriction factor (Clerc & Kennedy, IEEE TEC 2002): математически выведенный множитель $\chi$, гарантирующий сходимость без клампинга скорости. При $\varphi = c_1 + c_2 = 4.1$:

$$ \chi = \frac{2}{\left|2 - \varphi - \sqrt{\varphi^2 - 4\varphi}\right|} \approx 0.7298 $$

что эквивалентно $w = 0.7298$, $c_1 = c_2 = 1.49445$. Это и есть дефолтные константы, которые вы видите во всех библиотеках — они не подобраны на глаз, а следуют из анализа устойчивости динамической системы. Не подбирайте их случайно, пока не поняли, зачем.

Топология соседства решает больше, чем константы

$g_i$ — это лучший среди соседей частицы $i$, а кто такие соседи, задаёт топология:

Практическое правило: на унимодальной гладкой задаче — gbest, на мультимодальной — кольцо или von Neumann. Смена топологии обычно даёт больший эффект, чем шлифовка $c_1, c_2$. Вариант, где частица усредняет влияние всех соседей, а не только лучшего — Fully Informed Particle Swarm (Mendes, Kennedy, Neves, IEEE TEC 2004) — на многих бенчмарках устойчиво сильнее классики.

Режимы жизни роя

Стагнация в PSO имеет точный механизм: когда $x_i = p_i = g$, все три слагаемых обнуляются (кроме инерции, которая затухает), и частица замирает мёртвой. В отличие от ГА, у PSO нет мутации, которая вытащила бы её. Поэтому в продакшн-реализации всегда должен быть детектор схлопывания и перезапуск.

Задача: калибровка модели оценки трудозатрат

Классическое SBSE-применение PSO — подбор параметров модели, где нет градиента и нет выпуклости. Возьмём COCOMO-подобную модель: трудозатраты $E = a \cdot \mathrm{KLOC}^{b}$, коэффициенты $a, b$ калибруем по историческим проектам компании.

"""PSO с инерцией + клампингом скорости; калибровка модели трудозатрат."""
from __future__ import annotations
import numpy as np


def pso(fitness, bounds, *, n_particles: int = 30, iters: int = 300,
        w_start: float = 0.9, w_end: float = 0.4,
        c1: float = 1.49445, c2: float = 1.49445, seed: int = 0):
    """Минимизация fitness на прямоугольнике bounds = [(lo, hi), ...].

    Время:  O(iters · n_particles · (d + cost(fitness)))
    Память: O(n_particles · d)
    """
    rng = np.random.default_rng(seed)
    lo, hi = np.asarray(bounds, dtype=float).T
    d = lo.size

    x = rng.uniform(lo, hi, size=(n_particles, d))
    vmax = 0.2 * (hi - lo)                    # клампинг: шаг не больше 20% диапазона
    v = rng.uniform(-vmax, vmax, size=(n_particles, d))

    p = x.copy()
    fp = np.array([fitness(row) for row in x])
    best = int(fp.argmin())
    g, fg = p[best].copy(), float(fp[best])

    history = []
    for it in range(iters):
        w = w_start + (w_end - w_start) * it / max(iters - 1, 1)
        r1 = rng.random((n_particles, d))     # ПОКОМПОНЕНТНО, не по одному скаляру
        r2 = rng.random((n_particles, d))
        v = w * v + c1 * r1 * (p - x) + c2 * r2 * (g - x)
        np.clip(v, -vmax, vmax, out=v)
        x = x + v

        # границы: прижать позицию и погасить скорость,
        # иначе частица «залипает» в стенку, толкаясь в неё каждую итерацию
        under, over = x < lo, x > hi
        x = np.where(under, lo, np.where(over, hi, x))
        v[under | over] = 0.0

        f = np.array([fitness(row) for row in x])
        improved = f < fp
        p[improved], fp[improved] = x[improved], f[improved]
        best = int(fp.argmin())
        if fp[best] < fg:
            g, fg = p[best].copy(), float(fp[best])

        # диагностика схлопывания роя
        spread = float(np.mean(np.std(x, axis=0) / (hi - lo)))
        history.append((it, fg, spread))
        if spread < 1e-4 and it < iters - 1:
            # мягкий рестарт: сохраняем лидера, худшую половину раскидываем заново
            worst = np.argsort(fp)[n_particles // 2:]
            x[worst] = rng.uniform(lo, hi, size=(worst.size, d))
            v[worst] = rng.uniform(-vmax, vmax, size=(worst.size, d))
    return g, fg, history


# ---- целевая функция: MMRE модели E = a · KLOC^b -------------------------
KLOC = np.array([2.1, 3.6, 7.9, 11.4, 18.0, 26.5, 40.2, 61.0, 95.5, 140.0])
EFFORT = np.array([5.0, 8.4, 21.0, 33.5, 62.0, 95.0, 168.0, 280.0, 520.0, 830.0])


def mmre(theta: np.ndarray) -> float:
    """Mean Magnitude of Relative Error — классическая (и спорная) метрика."""
    a, b = theta
    pred = a * KLOC ** b
    return float(np.mean(np.abs(pred - EFFORT) / EFFORT))


if __name__ == "__main__":
    (a, b), err, hist = pso(mmre, [(0.5, 20.0), (0.5, 2.0)], seed=42)
    print(f"E = {a:.3f} · KLOC^{b:.3f}    MMRE = {err:.4f}")

Одна оговорка по существу: MMRE — плохая метрика качества оценки. Она систематически поощряет занижение прогноза, потому что относительная ошибка ограничена снизу единицей при недооценке и не ограничена сверху при переоценке. Шеппард и Макдоннелл (Evaluating prediction systems in software project estimation, IST 2012) предлагают вместо неё Standardised Accuracy — сравнение с случайным угадыванием. Это иллюстрация универсального правила из статьи про фитнес-функции: оптимизатор безжалостно эксплуатирует дефект метрики, и виноват будет не PSO.

Binary PSO: когда решение — подмножество

Для выбора подмножества тестов/фич позиции должны быть битами. Каноническое решение (Kennedy & Eberhart, 1997): скорость остаётся вещественной и трактуется как логит вероятности единицы.

def bpso_step(x, v, p, g, w, c1, c2, rng, vmax=4.0):
    """Один шаг бинарного PSO. x ∈ {0,1}^(n×d), v ∈ R^(n×d)."""
    r1, r2 = rng.random(x.shape), rng.random(x.shape)
    v = w * v + c1 * r1 * (p - x) + c2 * r2 * (g - x)
    np.clip(v, -vmax, vmax, out=v)          # без клампинга сигмоида насыщается
    s = 1.0 / (1.0 + np.exp(-v))            # S-образная transfer function
    x = (rng.random(x.shape) < s).astype(float)
    return x, v

Здесь спрятана известная патология: при $v \to 0$ вероятность стремится к $0.5$, то есть сошедшаяся частица превращается в генератор случайных битов — ровно наоборот тому, что должно происходить при сходимости. Лечится V-образными функциями переноса вида $|\tanh(v)|$, где бит переключается с вероятностью, растущей по модулю скорости (Mirjalili & Lewis, Swarm and Evolutionary Computation 2013). Если пишете BPSO сами — берите V-образную версию.

Типичные ошибки в PSO

1. Забыть клампинг скорости и не взять constriction. Классический симптом: частицы за 20 итераций улетают на $10^{12}$ и NaN-ят фитнес.
2. Общий скаляр вместо $r_1, r_2 \in U(0,1)^d$. Тогда частица движется строго в плоскости, натянутой на $x, p, g$ — размерность поиска фактически схлопывается.
3. Отражение от границы без гашения скорости. Частица начинает «долбиться» в стенку и тратит бюджет впустую.
4. Разные масштабы переменных. PSO не инвариантен к масштабированию осей: если один параметр в диапазоне $[0, 1]$, а другой $[0, 10^6]$, единая $vmax$ бессмысленна. Всегда нормализуйте пространство поиска в единичный куб и разворачивайте обратно внутри фитнеса.
5. Применять PSO к комбинаторике «в лоб», округляя вещественные координаты до перестановки. Округление уничтожает locality: соседние точки в $\mathbb{R}^d$ дают радикально разные перестановки. Для перестановок берите ACO или ГА с перестановочными операторами.
6. Сравнивать по одному прогону. Роевые алгоритмы стохастичны; один сид не значит ничего.

Часть III. Как выбирать: рой, эволюция или локальный поиск

Практический чек-лист выбора:

• Решение конструируется по шагам (маршрут, порядок, путь по CFG) → ACO. Феромон естественно ложится на «переход» или «позицию».
• Решение — вектор вещественных чисел и функция гладкая-ish → PSO или CMA-ES. Кстати, для $d \le 20$ и дорогого фитнеса байесовская оптимизация чаще выигрывает у обоих.
• Решение — битовая маска → ГА или binary PSO; здесь ГА обычно предпочтительнее, потому что кроссовер бит-масок содержателен.
• Ландшафт почти унимодален (типично для покрытия одной ветви в генерации тестов) → не тратьте деньги на популяцию, берите локальный поиск с рестартами.
• Целей несколько и они конфликтуют → сначала читайте про Парето и NSGA-II, а рой прикручивайте потом (MOPSO — надстройка над PSO с архивом недоминируемых решений и лидером, выбираемым из архива).

Сравнение по механизмам

Осторожно: метафоры

За тридцать лет опубликованы сотни «новых» роевых алгоритмов: волки, летучие мыши, светлячки, гармонический поиск, стая китов, чёрные дыры. Подавляющее большинство — переименованные варианты PSO или эволюционных стратегий с новой историей во введении. Кеннет Сёренсен так и озаглавил разбор: Metaheuristics — the metaphor exposed (ITOR, 2015). Показательный случай — Harmony Search: формальный разбор показал его прямую эквивалентность $(\mu+1)$-эволюционной стратегии, известной с 1970-х (Weyland, 2010).

Как отличить содержательный алгоритм от метафоры:

1. Есть ли формальное описание без единого слова про животных? Если убрать метафору и алгоритм не описывается уравнениями — это подозрительно.
2. Есть ли новый механизм, отсутствующий у PSO/ES/ГА? У ACO такой механизм есть — конструктивная вероятностная модель с испарением. У «алгоритма стаи китов» — нет.
3. Сравнивают ли с сильным baseline (CMA-ES, MMAS, хороший ГА) при равном бюджете оценок, а не с ванильным PSO 1995 года?
4. Приведён ли статистический анализ по многим сидам?

По последнему пункту стандарт в SBSE задан работой Arcuri & Briand, «A practical guide for using statistical tests to assess randomized algorithms in software engineering» (ICSE 2011): минимум 30 независимых прогонов, непараметрический тест (Манна–Уитни/Уилкоксон) и размер эффекта Варга–Дилейни $\hat{A}_ {12}$ вместо голого p-value. И держите в голове No Free Lunch: «универсально лучшего» роя не существует, преимущество всегда покупается предположениями о структуре конкретной задачи. Подробнее — в обзорной статье трека.

Инженерия: как это выглядит в проде

• Библиотеки. Для PSO — pyswarms (векторизован, есть топологии) и scikit-opt (PSO, ACO, отжиг, ГА в одном пакете, простой API). Для ACO на серьёзных объёмах — писать самому или брать ACOTSP. В JVM-стеке SBSE-инструменты (тот же EvoSuite) исторически строятся на ГА, а не на рое — учитывайте это при интеграции.
• Бюджет и остановка. Останавливайтесь по вычислениям фитнеса или по стенным часам, а не по итерациям. В CI жёсткий дедлайн: «дай лучшее, что успел за 8 минут». Реализуйте anytime-поведение — рекорд доступен в любой момент.
• Параллелизм. ACO параллелится тривиально: муравьи независимы внутри итерации, синхронизация нужна только при обновлении $\tau$. PSO параллелится по оценке фитнеса; асинхронные варианты (частица обновляется, не дожидаясь всей итерации) дают лучшую утилизацию, но меняют динамику — проверяйте качество, а не только скорость.
• Кэширование фитнеса. Если оценка = прогон тестов, кэшируйте по хешу решения. В ACO повторы решений в поздних итерациях массовые — кэш экономит десятки процентов.
• Суррогатные модели. Когда одна оценка стоит минуты (сборка, статический анализ, прогон интеграционных тестов), обучайте дешёвый регрессор-суррогат и отправляйте на реальную оценку только топ-кандидатов.
• Воспроизводимость. Фиксируйте сид и логируйте его в артефактах CI. «У меня локально нашлось лучше» без сида — не баг-репорт.
• Наблюдаемость. Логируйте не только рекорд, но и разброс (диаметр роя, энтропия феромонной матрицы). Кривая рекорда, вышедшая на плато, ничего не говорит; кривая разброса, упавшая в ноль, говорит «алгоритм умер, перезапускай».

Сводка типичных ошибок

Мини-итог

• Рой — это локальные правила + разделяемая память + положительная обратная связь с забыванием. Всё остальное детали.
• ACO строит решение по шагам, храня знание в феромонной матрице. Его ниша — комбинаторные конструктивные задачи и динамические среды. Дефолт для реализации — MAX–MIN Ant System, потому что его границы $[\tau_{\min}, \tau_{\max}]$ структурно предотвращают стагнацию.
• PSO двигает точки в $\mathbb{R}^d$ под действием трёх тяг. Дефолт — constriction-константы $w=0.7298$, $c_1=c_2=1.49445$, а главная ручка настройки — топология соседства, а не коэффициенты.
• Обе семьи имеют одну и ту же смертельную болезнь — преждевременную сходимость, и одинаковое лекарство — измерять разброс и перезапускаться.
• К «новым» роевым алгоритмам относитесь как к сомнительной библиотеке без тестов: требуйте формального описания без метафор, сильного baseline и статистики.
• И самое частое разочарование: перед внедрением роя сравните его с жадной эвристикой и hill climbing с рестартами. Часто они выигрывают, и это отличная новость — их проще сопровождать.

Источники

• M. Dorigo, V. Maniezzo, A. Colorni. The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. SMC-B, 1996.
• T. Stützle, H. Hoos. MAX–MIN Ant System, Future Generation Computer Systems, 2000.
• M. Dorigo, T. Stützle. Ant Colony Optimization, MIT Press, 2004 — базовая книга, включая формальные результаты сходимости.
• J.-L. Deneubourg et al. The self-organizing exploratory pattern of the Argentine ant, J. Insect Behavior, 1990.
• J. Kennedy, R. Eberhart. Particle Swarm Optimization, ICNN'95.
• Y. Shi, R. Eberhart. A Modified Particle Swarm Optimizer, IEEE CEC, 1998.
• M. Clerc, J. Kennedy. The Particle Swarm — Explosion, Stability, and Convergence in a Multidimensional Complex Space, IEEE TEC, 2002.
• S. Mirjalili, A. Lewis. S-shaped versus V-shaped transfer functions for binary PSO, Swarm and Evolutionary Computation, 2013.
• G. Rothermel et al. Prioritizing Test Cases For Regression Testing, IEEE TSE, 2001 — определение APFD.
• Z. Li, M. Harman, R. Hierons. Search Algorithms for Regression Test Case Prioritization, IEEE TSE, 2007.
• M. Harman, A. Mansouri, Y. Zhang. Search-Based Software Engineering: Trends, Techniques and Applications, ACM Computing Surveys, 2012.
• A. Arcuri, L. Briand. A Practical Guide for Using Statistical Tests to Assess Randomized Algorithms in Software Engineering, ICSE 2011.
• K. Sörensen. Metaheuristics — the metaphor exposed, International Transactions in Operational Research, 2015.
• M. Shepperd, S. MacDonell. Evaluating prediction systems in software project estimation, Information and Software Technology, 2012.
• Документация pyswarms и scikit-opt.

Что дальше

Мы прошли весь основной арсенал поисковых алгоритмов — от hill climbing до роя. Пора применить его к задаче, которая принесла SBSE наибольшую практическую пользу: автоматическому созданию тестов, где фитнесом становится покрытие, а «противником» — сам код.

Автоматическая генерация тестов: EvoSuite, фаззинг, мутационное тестирование