SBSE: поисковая инженерия ПО — что это и зачем

Почти всё, чем занимается инженер-программист, — это выбор из огромного числа вариантов. Какие 40 тестов из 12 000 прогнать в pre-merge? Какие фичи взять в релиз при бюджете в 300 человеко-дней? Как разложить 900 классов легаси-монолита по модулям, чтобы связность внутри была высокой, а зацепление между модулями низким? Какой набор входных данных заставит выполниться вот эта ветка, до которой не доходит ни один тест?

Обычно такие вопросы решают «экспертным мнением»: сели, поспорили, выбрали. Это работает, пока вариантов десятки. Когда их $2^{900}$, экспертное мнение — это осознанный отказ искать хорошее решение.

Search-Based Software Engineering (SBSE) — это дисциплина, которая говорит: переформулируй инженерную задачу как задачу оптимизации и отдай её поисковому алгоритму. Не «найди идеал доказуемо», а «найди решение существенно лучше того, что придумает человек за то же время».

Определение и происхождение термина

Термин ввели Марк Харман и Брайан Джонс в статье «Search-based software engineering» (Information and Software Technology, 2001). Их тезис прост и радикален:

Инженерия ПО насыщена задачами, где пространство решений огромно, точный алгоритм неизвестен или неприменим, но при этом качество готового решения легко измерить. Именно такие задачи идеально ложатся на метаэвристический поиск.

Ключевое слово — измерить. Мы можем не знать, как построить хороший набор тестов, но у готового набора легко посчитаем покрытие. Не знаем, как правильно нарезать монолит, но у готовой нарезки посчитаем modularization quality. Эта асимметрия — «сделать трудно, оценить легко» — и есть топливо SBSE. Обзорная работа, с которой стоит начинать серьёзное чтение: Harman, Mansouri, Zhang. «Search-Based Software Engineering: Trends, Techniques and Applications», ACM Computing Surveys, 2012.

Три ингредиента — весь рецепт

Чтобы применить SBSE к задаче, нужно ровно три вещи. Не четыре, не две.

1. Представление решения (representation). Как закодировать один вариант ответа в структуру данных: битовая строка, перестановка, вектор чисел, дерево выражения, последовательность вызовов API.
2. Фитнес-функция (fitness function). Числовая оценка «насколько этот вариант хорош». Должна быть вычислимой быстро и — критично — градуированной: чуть лучшее решение должно получать чуть лучший балл.
3. Операторы поиска (search operators). Как из имеющегося решения получить соседнее: мутация одного бита, перестановка двух элементов, скрещивание двух родителей.

Всё остальное — генетические алгоритмы, отжиг, роевой интеллект — это разные способы гулять по пространству, которое вы задали этими тремя вещами. Поэтому 80 % успеха проекта на SBSE определяется качеством представления и фитнеса, а не выбором алгоритма. Об этом — следующая статья трека.

Обратите внимание на последний блок. Поиск оптимизирует ровно то, что вы написали в фитнес-функции, и ни на йоту больше. Это источник почти всех разочарований в SBSE — вернёмся к нему в разделе про ошибки.

Почему поиск, а не точный алгоритм

Резонный вопрос: если задача — оптимизация, почему не решить её точно, целочисленным или динамическим программированием? Иногда именно так и надо: рюкзак на 50 предметов с линейными ограничениями — берите OR-Tools или солвер MILP и получайте доказуемый оптимум. SBSE начинается там, где точные методы ломаются:

Метаэвристики не требуют ни выпуклости, ни дифференцируемости, ни даже явной формулы — им нужно уметь только сравнить два решения. Взамен они не дают гарантий оптимальности, только «лучшее из увиденного».

Средняя панель — важная. Случайный поиск (random search) — не соломенное чучело, а обязательный baseline: множество опубликованных «умных» SBSE-подходов при честной проверке оказывались не лучше случайного поиска на том же бюджете. Если ваш генетический алгоритм не бьёт random search статистически значимо — проблема в фитнесе или представлении, а не в алгоритме.

Ландшафт фитнеса: главная интуиция трека

Представьте пространство всех решений как рельеф: координаты — закодированное решение, высота — значение фитнеса. Поиск — путешествие по рельефу в тумане: высоту видно только там, где стоите и куда можете шагнуть.

• Гладкий ландшафт. Любой жадный метод дойдёт до оптимума. Здесь SBSE избыточен — берите hill climbing и не усложняйте.
• Многоэкстремальный. Жадный метод застрянет в первой яме. Нужны механизмы выхода: случайные рестарты, имитация отжига, популяция решений. Это типичный случай для реальных задач.
• Плато и «игла». Фитнес постоянен почти везде и резко проваливается в одной точке. Направления нет, поиск вырождается в случайный. Классический пример: фитнес «тест упал / не упал» — бинарный, значит плоский.

Третий случай — не приговор задаче, а приговор вашей фитнес-функции. Классический приём: заменить бинарный предикат на расстояние до его выполнения. Для if (x == 42) возвращаем не 0/1, а |x - 42| — плато превращается в склон.

def branch_distance(op: str, lhs: float, rhs: float) -> float:
    """Расстояние ветви: 0.0 означает, что условие выполнено.

    Идея из работ Korel (1990) и Tracey (1998): вместо бинарного «истина/ложь»
    возвращаем, НАСКОЛЬКО далеко мы от истины. Это превращает плато в градиент.
    """
    K = 1.0  # положительная константа, чтобы «почти истина» не равнялась истине
    if op == "==":
        return 0.0 if lhs == rhs else abs(lhs - rhs) + K
    if op == "!=":
        return 0.0 if lhs != rhs else K
    if op == "<":
        return 0.0 if lhs < rhs else (lhs - rhs) + K
    raise ValueError(f"неизвестный оператор: {op}")


def normalize(d: float) -> float:
    """Нормировка в [0, 1) — чтобы складывать расстояния разных ветвей.
    Стандартная схема из EvoSuite: d / (d + 1)."""
    return d / (d + 1.0)

Эта пара функций — сердце автоматической генерации тестов. Детально разберём в статье про генерацию тестов, а формальную теорию ландшафтов — в статье про пространство поиска и фитнес.

Карта области: какие задачи решает SBSE

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

Когда SBSE окупается

Не всякая задача стоит поискового движка. Полезная эвристика — две оси: насколько велико пространство и насколько хорош сигнал фитнеса.

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

Полный рабочий пример: Next Release Problem

Разберём задачу целиком, от постановки до статистики. Next Release Problem (Bagnall, Rayward-Smith, Whittley, Information and Software Technology, 2001): есть набор фич, каждая имеет стоимость в человеко-днях и ценность для клиентов; часть фич зависит от других. Нужно выбрать подмножество, максимизирующее ценность при бюджете.

Представление: битовая строка длины $n$, бит $i$ = «фича $i$ включена в релиз». Фитнес: сумма ценностей, со штрафом за превышение бюджета и за нарушенные зависимости. Оператор: инверсия случайного бита (мутация) — минимальный шаг по пространству.

import random
from dataclasses import dataclass


@dataclass(frozen=True)
class Feature:
    name: str
    cost: int              # человеко-дни
    value: int             # бизнес-ценность
    depends_on: tuple[int, ...] = ()   # индексы фич, без которых эта бессмысленна


def make_problem(n: int, seed: int = 7) -> tuple[list[Feature], int]:
    """Синтетический бэклог: n фич, бюджет ~30 % от суммарной стоимости."""
    rnd = random.Random(seed)
    features: list[Feature] = []
    for i in range(n):
        deps = tuple(rnd.sample(range(i), k=min(i, rnd.choice([0, 0, 1, 2])))) if i else ()
        features.append(Feature(f"F{i:03d}", rnd.randint(1, 40), rnd.randint(1, 100), deps))
    return features, int(sum(f.cost for f in features) * 0.30)


def fitness(solution: list[int], features: list[Feature], budget: int) -> float:
    """Больше — лучше. Ограничения выражены штрафом, а не запретом.

    Почему штраф, а не отбрасывание невалидных решений: путь к хорошему решению
    часто проходит ЧЕРЕЗ слегка невалидные. Жёсткий запрет режет связность
    пространства поиска и превращает ландшафт в набор изолированных островов.
    """
    total_value = total_cost = violations = 0
    for i, taken in enumerate(solution):
        if not taken:
            continue
        f = features[i]
        total_value += f.value
        total_cost += f.cost
        violations += sum(1 for d in f.depends_on if not solution[d])

    over = max(0, total_cost - budget)
    # Штрафы подобраны так, чтобы нарушение НИКОГДА не окупалось ценностью,
    # но при этом сохранялся градиент: «превысил на 1 день» лучше, чем «на 100».
    return total_value - 10.0 * over - 50.0 * violations


def random_search(features, budget, evaluations: int, seed: int):
    """Baseline. Каждый раз бросаем монетку заново, память не используем."""
    rnd = random.Random(seed)
    n = len(features)
    best, best_fit = None, float("-inf")
    for _ in range(evaluations):
        cand = [rnd.randint(0, 1) for _ in range(n)]
        fit = fitness(cand, features, budget)
        if fit > best_fit:
            best, best_fit = cand, fit
    return best, best_fit


def hill_climb(features, budget, evaluations: int, seed: int):
    """Простейший направленный поиск: мутируем один бит, принимаем улучшения.

    Со случайными рестартами при застревании — иначе застрянем в первом локальном
    максимуме, см. панель «Многоэкстремальный» на картинке выше.
    """
    rnd = random.Random(seed)
    n = len(features)
    current = [rnd.randint(0, 1) for _ in range(n)]
    current_fit = fitness(current, features, budget)
    best, best_fit = current[:], current_fit
    used = 1
    stagnation = 0

    while used < evaluations:
        cand = current[:]
        idx = rnd.randrange(n)
        cand[idx] ^= 1                      # оператор соседства
        cand_fit = fitness(cand, features, budget)
        used += 1

        if cand_fit >= current_fit:         # >= пропускает нейтральные шаги по плато
            current, current_fit = cand, cand_fit
            stagnation = 0 if cand_fit > best_fit else stagnation + 1
        else:
            stagnation += 1

        if current_fit > best_fit:
            best, best_fit = current[:], current_fit

        if stagnation > 4 * n:              # застряли — рестарт из случайной точки
            current = [rnd.randint(0, 1) for _ in range(n)]
            current_fit = fitness(current, features, budget)
            used += 1
            stagnation = 0

    return best, best_fit


if __name__ == "__main__":
    features, budget = make_problem(n=120)
    N_EVAL = 20_000                     # одинаковый бюджет для обоих алгоритмов!
    rs = [random_search(features, budget, N_EVAL, seed=s)[1] for s in range(30)]
    hc = [hill_climb(features, budget, N_EVAL, seed=s)[1] for s in range(30)]
    print(f"бюджет релиза: {budget} чел.-дней, фич: {len(features)}")
    print(f"random search : медиана {sorted(rs)[15]:.0f}, максимум {max(rs):.0f}")
    print(f"hill climbing : медиана {sorted(hc)[15]:.0f}, максимум {max(hc):.0f}")

Реальный вывод этого кода: random search: медиана 852, hill climbing: медиана 2453 — почти втрое лучше при одинаковом числе вычислений фитнеса. Это и есть суть SBSE: не «больше считать», а «считать в правильном направлении».

Разбор сложности

Считать сложность метаэвристик в терминах $O(n)$ от размера входа бессмысленно — алгоритм не завершается «когда решил», он завершается «когда кончился бюджет». Правильная единица измерения — число вычислений фитнес-функции ($N_{eval}$), потому что в реальных задачах именно фитнес доминирует по времени (запуск тест-сюита — секунды, инверсия бита — наносекунды).

Отсюда два практических вывода. Первый: оптимизируйте фитнес-функцию, а не алгоритм — ускорение фитнеса в 10 раз даёт в 10 раз больше итераций поиска, что обычно выгоднее замены hill climbing на модный алгоритм (приёмы: инкрементальный пересчёт дельтой при инверсии бита, кэш, суррогатные модели, параллельная оценка популяции). Второй: сравнивать алгоритмы всегда при равном $N_{eval}$, а не при равном wall-clock, иначе вы сравниваете качество реализации, а не качество идеи.

Как поиск взаимодействует с системой: пример генерации тестов

В задачах тестирования фитнес-функция — это не формула, а запуск программы. Инструментированная сборка сообщает поисковику, какие ветви были достигнуты и насколько близко подошли к недостигнутым.

Такая архитектура — точное описание того, как устроен EvoSuite (Fraser & Arcuri, ESEC/FSE 2011) для Java и Pynguin для Python. Обратите внимание на последний шаг: сырой результат поиска — набор вызовов без ассертов; ассерты добавляются отдельной фазой, обычно через мутационное тестирование (оставляем те ассерты, которые убивают мутантов).

Немного истории: откуда это выросло

Полезный ресурс с сотнями работ по годам и темам — SBSE Repository CREST, UCL. Основная конференция области — SSBSE.

Как это выглядит в продакшене

Sapienz в Meta/Facebook. Самый известный кейс промышленного SBSE. Многокритериальный поиск (NSGA-II) генерирует последовательности UI-событий для Android-приложения, оптимизируя одновременно покрытие, число найденных падений и длину сценария — короткие сценарии воспроизведения нужны, чтобы разработчик мог понять баг. Работал в CI на каждом диффе, репортил падения прямо в код-ревью. См. Mao, Harman, Jia. Sapienz, ISSTA 2016 и Alshahwan et al. Deploying SBSE with Sapienz at Facebook, SSBSE 2018. Урок из внедрения важнее самого алгоритма: успех определился не качеством поиска, а «actionability» результата — первые версии находили падения, которые никто не чинил, потому что воспроизведение занимало 300 шагов. Минимизация длины сценария в целях оптимизации превратила прототип в рабочий инструмент.

Фаззинг. AFL++ и OSS-Fuzz в Google — по сути SBSE, только сообщество называет это иначе: представление — байтовый буфер, операторы — мутации байтов, фитнес — новизна покрытия (отбор входов, открывших новое ребро CFG).

Автотюнинг. Подбор флагов JIT/GC, параметров индексов СУБД, размеров пулов — классические SBSE-задачи под именем «auto-tuning» или «configuration optimization».

Генерация тестов в IDE. EvoSuite, Pynguin, Randoop живут в pre-commit и как плагины; типичный режим — «догенерировать тесты до целевого покрытия для конкретного класса», а не «покрыть проект целиком».

Оценка результатов: без статистики результата нет

Метаэвристики стохастичны: два запуска дают разные ответы, один запуск ничего не доказывает. Стандарт зафиксирован в работе Arcuri & Briand. «A Hitchhiker’s Guide to Statistical Tests for Assessing Randomized Algorithms in Software Engineering» (STVR, 2014):

1. Минимум 30 независимых запусков с разными seed.
2. Сравнение распределений непараметрическим тестом — Mann–Whitney U (данные не нормальны, среднее врёт).
3. Обязательный размер эффекта — статистика Варга–Делани $\hat{A}_ {12}$: вероятность того, что случайный запуск A даст результат лучше случайного запуска B. $0.5$ — разницы нет, $0.71$ и выше — большой эффект. p-value без размера эффекта бесполезен: на 10 000 запусков значимой станет любая ерунда.
4. Baseline — random search при равном бюджете вычислений.

from itertools import product
from statistics import median


def a12(xs: list[float], ys: list[float]) -> float:
    """Статистика Варга–Делани A12 для «больше — лучше»: P(x > y) + 0.5 * P(x == y).

    0.5 — алгоритмы неразличимы; 0.56 / 0.64 / 0.71 — малый / средний / большой эффект.
    Сложность O(|xs| * |ys|); для сотен запусков это доли секунды.
    """
    wins = sum((x > y) + 0.5 * (x == y) for x, y in product(xs, ys))
    return wins / (len(xs) * len(ys))


def report(a: list[float], b: list[float]) -> str:
    e = a12(a, b)
    size = ("нет разницы" if abs(e - 0.5) < 0.06 else "малый" if abs(e - 0.5) < 0.14
            else "средний" if abs(e - 0.5) < 0.21 else "большой")
    return f"медианы {median(a):.1f} vs {median(b):.1f} | A12={e:.3f} ({size} эффект)"

Для p-value берите scipy.stats.mannwhitneyu. Правило хорошего тона: публикуйте медианы и boxplot, а не средние; фиксируйте seed; указывайте бюджет $N_{eval}$.

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

1. Бинарный фитнес. «1 если тест упал, иначе 0» — ландшафт сплошное плато, поиск вырождается в случайный. Всегда ищите непрерывную аппроксимацию цели.
2. Оптимизация метрики вместо цели (закон Гудхарта). Просите максимум покрытия — получите тесты без единого ассерта. Просите минимум числа тестов — получите один гигантский тест. Лечение: многокритериальная постановка (см. статью про Парето и NSGA-II) и обязательная человеческая валидация результата.
3. Жёсткие ограничения вместо штрафов. Отбрасывание невалидных решений рвёт пространство на изолированные острова. Обычно лучше штрафовать (как в примере NRP) или чинить решение оператором repair.
4. Сравнение без baseline и без статистики. «Наш GA дал 84 % покрытия» — бессмысленное утверждение без ответа на вопрос «а random search сколько дал?».
5. Тюнинг под тестовый набор. Параметры алгоритма подобраны на тех же задачах, на которых меряется качество, — это переобучение. Нужны отдельные наборы для настройки и для оценки.
6. Дорогой фитнес без кэша. Оценка кандидата 3 секунды × 20 000 оценок = 16 часов. Инкрементальный пересчёт, кэш по хешу решения и параллельная оценка популяции обязательны.
7. Вера в универсальный алгоритм. Теорема No Free Lunch (Wolpert & Macready, IEEE TEC, 1997) утверждает: усреднённо по всем возможным задачам все алгоритмы поиска одинаковы. Практический смысл — алгоритм хорош ровно в той мере, в какой его допущения совпадают со структурой вашей задачи. Поэтому «лучшего алгоритма SBSE» не существует, и поэтому в треке мы разбираем целое семейство.
8. Недетерминированный фитнес. Если оценка зависит от времени, сети или порядка потоков, поиск гоняется за шумом и «оптимизирует» удачные случайности. Изолируйте, мокайте, усредняйте по повторам.

Место SBSE рядом с машинным обучением

Частый вопрос: зачем поиск, если есть нейросети и LLM? Ответ — это ортогональные инструменты, и сегодня они всё чаще работают вместе.

• ML предсказывает, поиск конструирует. Модель говорит «этот дифф вероятно содержит баг»; поиск строит конкретный входной вектор, который этот баг проявляет.
• LLM генерирует, поиск проверяет и отбирает. Языковая модель предлагает патчи-кандидаты, а поисковый цикл прогоняет тесты и отбирает те, что реально чинят баг, — тот же generate-and-validate, что и в классическом автоматическом исправлении программ, только с умным генератором.
• Поиск настраивает ML. Подбор гиперпараметров и архитектур (neural architecture search) — это ровно метаэвристический поиск; связь с треками машинного обучения и нейросетей здесь прямая.

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

Инструменты, с которых начинать

Свободная и очень хорошая книга по самим алгоритмам: Sean Luke. «Essentials of Metaheuristics» — читается за выходные и покрывает половину этого трека.

Мини-итог

• SBSE — это переформулировка инженерных задач как задач оптимизации и решение их метаэвристиками.
• Работает там, где решение построить трудно, а оценить — легко и дёшево.
• Нужны ровно три вещи: представление, фитнес-функция, операторы поиска. Качество первых двух важнее выбора алгоритма.
• Главный враг — плоский ландшафт фитнеса. Лечится заменой бинарных предикатов на расстояния.
• Мерять эффективность нужно в вычислениях фитнеса, а результаты — статистикой по 30+ запускам с размером эффекта $\hat{A}_ {12}$ и baseline в виде random search.
• Промышленные примеры работают: Sapienz в Meta, EvoSuite в CI, фаззинг в OSS-Fuzz. Универсального алгоритма при этом нет — No Free Lunch; есть соответствие алгоритма структуре конкретной задачи.

Что дальше

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

Пространство поиска, представление решения и фитнес-функция