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

В обзорной статье трека мы договорились, что SBSE — это переформулировка инженерной задачи как задачи поиска. Здесь мы разбираем самый важный и самый недооценённый этап: саму переформулировку. Алгоритм поиска (отжиг, генетика, PSO) — сменная деталь, её меняют за час; представление и фитнес-функция определяют, решаема задача вообще или нет.

Марк Харман и Брайан Джонс в статье, с которой началась дисциплина (Search-based software engineering, IST 2001), говорят прямо: чтобы применить SBSE, нужны всего две вещи — представление решения и функция качества, всё остальное берётся с полки. Практика добавила третий пункт, который в 2001-м считался частью первого: оператор соседства/вариации. Без него представление — формат хранения, а не пространство для ходьбы.

Три вопроса до первой строчки кода

1. Что такое одно решение? Как выглядит объект, который я в итоге отдам пользователю, и как я его закодирую.
2. Что значит «рядом»? Какая минимальная правка превращает одно решение в другое.
3. Что значит «лучше»? Число, которое я минимизирую или максимизирую, и — критично — которое различает два плохих решения между собой.

Третий пункт ломается чаще всего: фитнес вида «тест прошёл / не прошёл» даёт ландшафт из одной иглы в бесконечной пустыне, после чего делается вывод «поиск не работает». Работает — ему не сказали, куда идти.

Обратите внимание: обе стрелки к алгоритму проходят через представление — смена кодировки автоматически меняет и операторы, и смысл фитнеса.

Пространство поиска

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

Формально: найти $s^\ast \in S$ такое, что $f(s^\ast ) \le f(s)$ для всех $s \in S$. На практике мы почти никогда не находим $s^\ast $ и не можем доказать, что нашли, — мы находим достаточно хорошее решение за приемлемое время. Масштабы стоит прочувствовать на цифрах:

Даже самая скромная строка недоступна перебору: при миллиарде оценок в секунду $10^{18}$ вариантов займут 30 лет. Отсюда весь смысл дисциплины — мы не перебираем, мы направленно блуждаем. При этом рост $|S|$ сам по себе задачу не утяжеляет: максимум монотонной функции на $2^{1000}$ точек берётся за 1000 шагов. Тяжесть создаёт форма ландшафта, а не его размер.

Представление решения

Представление (encoding, genotype) — это отображение $g : G \to P$ из пространства генотипов, по которому ходит алгоритм, в пространство фенотипов — реальных артефактов, которые оценивает фитнес.

Свойства хорошего представления

Полнота (completeness). Оптимум должен быть выразим. Кодируете тест как «до 5 вызовов методов», а нужен сценарий из шести — оптимума в $S$ просто нет, и никакой алгоритм его не найдёт.

Замкнутость (closure). Любой генотип должен декодироваться во что-то оцениваемое: дерево в GP обязано вычисляться при любых входах — отсюда «защищённое деление» (div(a, 0) = 1) вместо исключения.

Локальность (locality). Маленькое изменение генотипа должно давать маленькое изменение фенотипа и, как следствие, фитнеса. Франц Ротлауф посвятил этому целую книгу (Representations for Genetic and Evolutionary Algorithms), и вывод там жёсткий: представление с низкой локальностью превращает направленный поиск в случайный.

Классическая иллюстрация — «обрыв Хэмминга» в обычном двоичном коде:

Числа 7 (0111) и 8 (1000) — соседи на числовой оси, но в пространстве генотипов между ними расстояние Хэмминга 4: одиночная мутация никогда не переведёт одно в другое, и поиск, подошедший к 7 снизу, застревает. Код Грея ($g(n) = n \oplus (n \gg 1)$) убирает обрывы — соседние значения отличаются ровно одним битом.

Минимальная избыточность (redundancy). Если 1000 генотипов кодируют один фенотип, бюджет уходит на блуждание по плато эквивалентных решений. Кодируя разбиение 200 классов вектором меток, вы получаете $k!$ вариантов одного разбиения — просто переименования модулей; каноникализация меток сжимает пространство в $k!$ раз. (Иногда избыточность полезна: нейтральные мутации помогают уходить с плато.)

Компактность. Чем короче генотип, тем меньше $|S|$ и плотнее покрытие — но чрезмерное сжатие режет полноту. Это первый настоящий trade-off статьи.

Trade-off: выразительность против локальности

Расположите кандидатов на две оси — «насколько мощно можно выразить решение» и «насколько гладок получающийся ландшафт». Битовая строка NRP и вектор в коде Грея живут в удобном верхнем углу: узко, но гладко. Последовательности вызовов API и деревья GP выразительны, но рваны — за выразительность всегда платят гладкостью, и плата берётся бюджетом оценок. Сочетания «мощно и гладко» не существует; выбирают минимальное представление, в котором оптимум ещё выразим.

Соседство и ландшафт

Формально ландшафт — тройка $(S, N, f)$, где $N : S \to 2^S$ задаёт соседей. Одно пространство с одним фитнесом, но разными операторами соседства даёт разные ландшафты: в одном оптимум берётся за 50 шагов, в другом поиск безнадёжно застревает.

Три врага поиска, видимые на картинке:

• Локальный оптимум — лучше всех соседей, но хуже глобального; вся следующая статья трека про то, как из него выбираться.
• Плато — фитнес постоянен, сигнала нет, поиск деградирует до случайного блуждания. Опаснее локального оптимума: из ямы можно выпрыгнуть, а на плато не видно, в какую сторону прыгать.
• Обманчивость (deceptiveness) — градиент систематически уводит от оптимума; широкий бассейн плохого решения съедает почти все старты.

Как измерить ландшафт, не решая задачу

Две дешёвые метрики, которые стоит посчитать до долгого эксперимента.

Автокорреляция случайного блуждания (Вайнбергер, 1990): пройдите случайным блужданием по соседям, запишите ряд $f_1, \dots, f_m$ и посчитайте автокорреляцию с лагом 1:

$$\rho(1) = \frac{\sum_{i=1}^{m-1}(f_i - \bar f)(f_{i+1} - \bar f)}{\sum_{i=1}^{m}(f_i - \bar f)^2}$$

$\rho(1)$ близко к 1 — ландшафт гладкий, локальный поиск будет эффективен. Близко к 0 — соседство не несёт информации, надо менять оператор или кодировку.

Fitness-distance correlation (Джонс и Форрест, 1995). Если оптимум известен (модельная задача, бенчмарк), посчитайте корреляцию фитнеса с расстоянием до оптимума: сильная положительная для минимизации — хороший знак, отрицательная означает обманчивый ландшафт.

import random, statistics

def walk_autocorrelation(problem, steps=2000, seed=0):
    """Гладкость ландшафта: автокорреляция фитнеса вдоль случайного блуждания. O(steps) оценок."""
    rnd = random.Random(seed)
    cur = problem.random_solution(rnd)
    series = [problem.fitness(cur)]
    for _ in range(steps):
        cur = rnd.choice(list(problem.neighbours(cur)))     # шаг к случайному соседу
        series.append(problem.fitness(cur))
    m = statistics.fmean(series)
    num = sum((series[i] - m) * (series[i + 1] - m) for i in range(len(series) - 1))
    den = sum((v - m) ** 2 for v in series)
    return num / den if den else 0.0

Стоимость — $O(\text{steps})$ оценок фитнеса: на порядки дешевле полного эксперимента.

Фитнес-функция

Фитнес — не «метрика качества для отчёта», а компас, и требования к нему другие.

Свойство 1: фитнес обязан различать плохие решения

Главное правило SBSE. Функция «тест дошёл до целевой строки: 0/1» бесполезна — она даёт информацию только в момент, когда задача уже решена. Канонический пример: нужно достичь return "target".

def classify(x, y):
    if x > 100:            # узел 1
        if y == x - 50:    # узел 2 — цель за этой веткой
            return "target"
    return "other"

Вероятность попасть случайно: $x > 100$ даёт примерно 1 $/2$, а y == x - 50 — около $2^{-32}$; случайный поиск не найдёт вход никогда. Решение придумал Богдан Корел ещё в 1990-м (Automated Software Test Data Generation, IEEE TSE), а Вегенер с соавторами довёл до промышленного вида (IST 2001). Фитнес складывается из двух частей:

• approach level — сколько вложенных управляющих зависимостей до цели осталось невыполненными;
• branch distance — насколько «чуть-чуть» не выполнился предикат в той точке, где исполнение свернуло не туда.

Таблица branch distance (по Трейси) для предиката, который оказался ложным; $K > 0$ — константа-штраф, обычно 1:

Ветви разной глубины нельзя складывать напрямую: branch distance неограничен, и одна «почти выполненная» глубокая ветка перевесит целый approach level. Поэтому дистанцию нормируют в $[0, 1)$:

$$\alpha(d) = \frac{d}{d + 1}, \qquad \text{fitness} = \text{approach level} + \alpha(d)$$

Андреа Аркури показал, что конкретный вид нормализации заметно влияет на результат (It does matter how you normalise the branch distance in search based software testing, ICST 2010): наивное $d / d_{\max}$ по наблюдаемому максимуму ломает сравнимость между поколениями.

Проверим экспериментально

import random

K = 1.0
norm = lambda d: d / (d + 1.0)                            # нормировка в [0, 1), монотонна
d_eq = lambda a, b: 0.0 if a == b else abs(a - b) + K     # для ложного предиката a == b
d_gt = lambda a, b: 0.0 if a > b else (b - a) + K         # для ложного предиката a > b

def fitness_guided(ind):
    """Approach level + нормированное branch distance. Минимизируем, 0 = цель достигнута."""
    x, y = ind
    if x <= 100:                       # свернули на узле 1: approach level 1
        return 1 + norm(d_gt(x, 100))
    return norm(d_eq(y, x - 50))       # approach level 0

def fitness_flat(ind):                 # наивный «булев» фитнес
    return 0.0 if classify(*ind) == "target" else 1.0

DELTAS = (1, -1, 10, -10, 100, -100, 1000, -1000, 10000, -10000)

def hill_climb(fit, budget=100_000, seed=0):
    """Восходящий поиск с рестартами. Возвращает число итераций до цели или None."""
    rnd = random.Random(seed)
    start = lambda: [rnd.randint(-10**6, 10**6), rnd.randint(-10**6, 10**6)]
    cur = start(); fcur = fit(cur)
    for step in range(budget):
        if fcur == 0.0:
            return step
        best, fbest = None, fcur
        for j in (0, 1):                                # соседи: сдвиг одной переменной
            for delta in DELTAS:
                cand = list(cur); cand[j] += delta
                f = fit(cand)
                if f < fbest:
                    best, fbest = cand, f
        if best is None:                                # локальный оптимум — рестарт
            cur = start(); fcur = fit(cur)
        else:
            cur, fcur = best, fbest
    return None

Результат на пяти случайных стартах (число итераций до достижения цели):

направляющий фитнес: [104, 100, 28, 84, 96]
плоский фитнес:      [None, 8969, None, None, None]

Алгоритм, пространство поиска и целевая ветка одинаковые; разница только в фитнесе: 100 шагов против «практически никогда». Это и есть случай, когда говорят «поиск не работает» — не работает компас, а не ноги.

Свойство 2: фитнес должен быть дёшев

Метаэвристике нужны $10^4$–$10^7$ оценок; если одна оценка — это mvn test на 40 секунд, в сутки выйдет 2000. Стандартные приёмы:

• Суррогатная модель: дешёвый предиктор фитнеса, настоящая функция — только для перспективных кандидатов (см. трек машинного обучения).
• Кэш по каноническому виду генотипа: повторные оценки — десятки процентов бюджета.
• Раннее прекращение и иерархия точности: обрываем оценку кандидата, который уже хуже лучшего; грубая оценка — для отсева, точная — для финалистов.

Свойство 3: фитнес должен быть детерминирован (или вы обязаны это учесть)

Если фитнес шумит (замеры производительности, flaky-тесты), поиск «поднимается» по шуму и запоминает удачные замеры, а не удачные решения. Лечится усреднением по $n$ прогонам (цена — бюджет $\times n$) или статистически корректным сравнением. Про методологию замеров — обязательный текст Аркури и Бриана (A Hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering, STVR 2014).

Ограничения: три способа не выйти за рамки

Реальные задачи почти всегда с ограничениями: бюджет релиза, зависимости требований, компилируемость патча. Стратегий три, и выбор между ними — второй крупный trade-off статьи.

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

Собираем всё вместе: Next Release Problem

Классическая задача SBSE (Bagnall et al., IST 2001): выбрать подмножество требований максимальной ценности при ограничении по бюджету и с учётом зависимостей («A нельзя взять без B»). NP-трудная — обобщение рюкзака.

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

import random
from dataclasses import dataclass

@dataclass(frozen=True)
class NRP:
    """Представление: битовая строка длины n (взяли требование или нет).
    Соседство: инверсия одного бита + починка. Фитнес: минус суммарная ценность (минимизируем)."""
    value: tuple      # ценность каждого требования
    cost: tuple       # стоимость каждого требования
    deps: dict        # i -> требования, без которых i невозможен
    budget: int

    def random_solution(self, rnd: random.Random):
        return self.repair([rnd.random() < 0.3 for _ in self.value])   # 0.3 — плотность старта

    def repair(self, x):
        """Декодер-починщик: замыкаем по зависимостям, затем выбрасываем самое невыгодное,
        пока не влезем в бюджет."""
        x, changed = list(x), True
        while changed:                                  # транзитивное замыкание зависимостей
            changed = False
            for i, need in self.deps.items():
                for j in need:
                    if x[i] and not x[j]:
                        x[j], changed = True, True
        while sum(c for c, s in zip(self.cost, x) if s) > self.budget:
            chosen = [i for i, s in enumerate(x) if s]
            worst = min(chosen, key=lambda i: self.value[i] / self.cost[i])  # ценность/стоимость
            x[worst] = False
            for i, need in self.deps.items():           # снимаем осиротевшие зависимости
                if x[i] and worst in need:
                    x[i] = False
        return x

    def fitness(self, x) -> float:
        return -sum(v for v, s in zip(self.value, x) if s)

    def neighbours(self, x):
        for i in range(len(x)):
            y = list(x); y[i] = not y[i]
            yield self.repair(y)

Замер на сгенерированном экземпляре из 60 требований (бюджет — 30% суммарной стоимости):

random search (2000 оценок фитнеса):  ценность 1675
hill climbing  (480 оценок фитнеса):  ценность 1753
бюджет 424, стоимость решения 422

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

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

Отсюда практический вывод: починка внутри генерации соседей — самая дорогая часть системы. Оптимизация номер один — инкрементальный фитнес: при инверсии бита $i$ дельта ценности считается за $O(1)$, а не за $O(n)$. Для больших $n$ это разница между часом и сутками.

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

1. Булев фитнес. «0 или 1» — не фитнес. Спрашивайте: чем плохое решение A лучше ещё более плохого B? Нет ответа — фитнес недоделан.
2. Несогласованные масштабы. Складывать «строки кода» (сотни) с «покрытием» (доли единицы) без нормировки — значит выкинуть второй критерий; либо нормируйте, либо переходите к многокритериальной постановке.
3. Оптимизация прокси вместо цели. Фитнес «максимум покрытия строк» даёт наборы тестов, которые всё выполняют и ничего не проверяют: закон Гудхарта работает и здесь.
4. Оператор, ломающий представление. Побитовая мутация на перестановке даёт не перестановку — нужны свои операторы (swap, inversion, PMX-кроссовер).
5. Игнорирование избыточности — $k!$ эквивалентных раскрасок означают $k!$-кратную потерю бюджета.
6. Дорогой фитнес без кэша. Первое, что меряют в профайлере, — доля повторных оценок.
7. Один прогон вместо тридцати. Поиск рандомизирован: вывод «A лучше B» по одному запуску некорректен, нужны повторы, медианы и непараметрические тесты.
8. Забытая теорема о бесплатных обедах (Wolpert & Macready, 1997): усреднённо по всем функциям все алгоритмы одинаковы. Выигрыш всегда берётся из знания о конкретной задаче — и живёт это знание именно в представлении и фитнесе.

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

EvoSuite (evosuite.org) генерирует JUnit-тесты для Java. Представление — набор последовательностей вызовов конструкторов и методов с аргументами; фитнес эволюционировал от «одна ветка = один запуск» через whole-suite (Fraser & Arcuri, TSE 2013), где фитнес — сумма нормированных дистанций по всем ветвям сразу, до DynaMOSA (Panichella et al., TSE 2018), где каждая ветка — отдельная цель, а порядок целей выводится из графа зависимостей динамически.

Sapienz в Meta (Mao, Harman, Jia, ISSTA 2016) ищет последовательности UI-событий, роняющие Android-приложение. Представление — последовательность событий переменной длины; фитнес трёхкритериальный: максимум покрытия, максимум числа падений и минимум длины последовательности, потому что баг-репорт из 300 тапов бесполезен. Работает в CI на каждом диффе.

Автоматическая починка программ (статья 08): представление — последовательность правок AST, фитнес — доля прошедших тестов, взвешенная по «негативным» (воспроизводящим баг) и «позитивным» (регрессионным); SapFix в Meta (блог, 2018) довёл это до продакшена в связке с Sapienz.

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

Мини-итог

• Пространство поиска задаётся кодировкой; его размер астрономичен, но сам по себе не страшен.
• Форму ландшафта определяет пара «представление + оператор соседства»; плохая локальность (обрыв Хэмминга, избыточность) убивает поиск надёжнее плохого алгоритма.
• Фитнес обязан различать плохие решения между собой: approach level + нормированное branch distance для тестирования, непрерывная целевая функция плюс работа с ограничениями для комбинаторных задач.
• Ограничения обрабатывают штрафом, починкой или декодером; выбор бьёт и по локальности, и по цене шага.
• Дешевизна и детерминированность фитнеса задают доступное число итераций; прежде чем менять алгоритм, измерьте ландшафт — это дешевле и обычно информативнее.

Источники

• M. Harman, B. F. Jones. Search-based software engineering. Information and Software Technology, 2001. DOI
• M. Harman, S. A. Mansouri, Y. Zhang. Search-Based Software Engineering: Trends, Techniques and Applications. ACM Computing Surveys, 2012. DOI
• P. McMinn. Search-based software test data generation: a survey. STVR, 2004. DOI
• B. Korel. Automated Software Test Data Generation. IEEE TSE, 1990. DOI
• J. Wegener, A. Baresel, H. Sthamer. Evolutionary test environment for automatic structural testing. IST, 2001. DOI
• A. Arcuri. It does matter how you normalise the branch distance in search based software testing. ICST, 2010. DOI
• F. Rothlauf. Representations for Genetic and Evolutionary Algorithms. Springer, 2006. DOI
• D. Wolpert, W. Macready. No free lunch theorems for optimization. IEEE TEC, 1997. DOI
• A. Arcuri, L. Briand. A Hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. STVR, 2014. DOI — как корректно сравнивать рандомизированные алгоритмы.
• A. Bagnall, V. Rayward-Smith, I. Whittley. The next release problem. IST, 2001. DOI; документация EvoSuite: evosuite.org

Что дальше

Мы построили пространство и компас. Теперь нужен способ по нему ходить — начнём с самых простых и самых полезных на практике методов, которые двигаются только между соседями.

Локальный поиск: hill climbing, имитация отжига, tabu search