Настройка самого поиска: параметры, гиперэвристики и выбор алгоритма

Вопрос, который задают чаще любого другого после первой же прочитанной статьи про генетические алгоритмы: какие ставить параметры? Популяция 50 или 500? Вероятность мутации 0.01 или 1/n? Турнир из двух или из семи? Расписание охлаждения геометрическое или логарифмическое?

Честный ответ состоит из трёх частей, и он приятнее, чем кажется.

1. Разница между хорошими и плохими параметрами существует, но она меньше, чем разница между хорошим и плохим фитнесом или представлением.
2. Разумные значения по умолчанию из литературы работают неплохо почти везде.
3. Если настраивать всё-таки нужно — это обычная задача поиска на мета-уровне, и решается она тем же аппаратом, включая гонки и суррогаты из предыдущей статьи.

Первый пункт стоит подкрепить числами, потому что он экономит людям недели.

Сколько на самом деле даёт настройка

Возьмём Next Release Problem из обзорной статьи: 60 фич, 15 случайных инстансов, бюджет 3 000 вычислений фитнеса на прогон. Сравним три вещи: случайный поиск, генетический алгоритм с худшей из двенадцати проверенных конфигураций и тот же алгоритм с лучшей.

Эти 38 % против 6 % — количественная формулировка приоритетов всего трека. Выбор представления, фитнеса и семейства алгоритма даёт кратно больше, чем подбор чисел внутри алгоритма. Но 6 % — тоже не ноль: если поиск крутится в CI ежедневно, это заметная разница, и она достаётся почти даром, если настройку автоматизировать.

Ровно этот вывод получен и на большом материале: Arcuri, Fraser, «Parameter tuning or default values? An empirical investigation in search-based software engineering», Empirical Software Engineering, 2013. Авторы прогнали огромную сетку параметров на генерации тестов и обнаружили две вещи: настройка под конкретный набор классов даёт улучшение, но переносится на новые классы плохо, а «дефолтные» значения из литературы оказываются близки к разумным. Их практический вывод: настраивайте, если у вас есть репрезентативный набор задач; иначе берите дефолты и вкладывайтесь в фитнес.

Две принципиально разные стратегии

Классификация не моя — она из работы Eiben, Hinterding, Michalewicz, «Parameter control in evolutionary algorithms», IEEE Transactions on Evolutionary Computation, 1999, и за четверть века не устарела. Разница между ветками простая: tuning ищет числа до запуска и фиксирует их, control меняет их по ходу, потому что оптимальные значения на старте (нужно исследовать) и в конце (нужно шлифовать) — разные.

Настройка как задача поиска на мета-уровне

Сформулируем по «трём ингредиентам» из первой статьи:

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

Три ловушки, специфичные именно для мета-уровня.

Ловушка 1: нельзя усреднять сырые значения фитнеса по разным инстансам. На инстансе A фитнес измеряется тысячами, на B — единицами; среднее будет определяться масштабом A, а не качеством алгоритма. Нормируйте (например, к лучшему известному значению на инстансе) или переходите к рангам: на каждом инстансе конфигурации ранжируются, а сравниваются суммы рангов.

Ловушка 2: одна оценка мета-уровня — это целый прогон поиска. Если прогон GA стоит 3 000 оценок фитнеса, то мета-задача с 12 конфигурациями × 15 инстансов × 5 повторов = 900 прогонов = 2.7 миллиона вычислений фитнеса. Мета-уровень дороже базового на два-три порядка, поэтому все приёмы из главы про дорогой фитнес здесь обязательны — особенно неравномерное распределение бюджета.

Ловушка 3: переобучение под набор задач (over-tuning). Параметры, вылизанные на тех же инстансах, на которых вы потом отчитываетесь, — это самообман, в точности как оценка модели на обучающей выборке (см. оценку моделей). Инстансы делятся на набор для настройки и набор для проверки, и оба должны быть репрезентативны.

Гонки: F-race и irace

Идея racing принадлежит Birattari и соавторам и лежит в основе пакета irace (López-Ibáñez, Dubois-Lacoste, Pérez Cáceres, Birattari, Stützle, Operations Research Perspectives, 2016): не гонять все конфигурации по всем инстансам, а выбывать по ходу. Все конфигурации бегут по первому инстансу, по второму, по третьему; как только накопилось достаточно данных, статистически проигрывающие выбывают, и бюджет достаётся выжившим.

Реализация «F-race lite» на чистом Python — с точным биномиальным знаковым тестом вместо тяжёлой статистики Фридмана:

"""F-race: гонка конфигураций с отсевом отстающих."""
import math


def binom_tail(k: int, n: int, p: float = 0.5) -> float:
    """P(X >= k) для биномиального распределения — точный знаковый тест без библиотек."""
    return sum(math.comb(n, i) * p ** i * (1 - p) ** (n - i) for i in range(k, n + 1))


def f_race(configs, instances, run, min_instances: int = 5, alpha: float = 0.05):
    """run(config, instance, seed) -> качество (больше лучше).

    Гонка: все выжившие конфигурации получают один и тот же инстанс (парные наблюдения!),
    после каждого раунда сравниваем каждую с лидером знаковым тестом и отсеиваем
    значимо проигрывающих. Парность важна: сравнивать конфигурации на РАЗНЫХ инстансах
    бессмысленно, инстансы отличаются друг от друга сильнее, чем конфигурации.
    """
    alive = list(range(len(configs)))
    results: dict[int, list[float]] = {i: [] for i in alive}
    spent = 0

    for j, inst in enumerate(instances):
        for i in alive:
            results[i].append(run(configs[i], inst, seed=1000 + j))
            spent += 1
        if j + 1 < min_instances or len(alive) == 1:
            continue

        leader = max(alive, key=lambda i: sum(results[i]))
        survivors = []
        for i in alive:
            if i == leader:
                survivors.append(i)
                continue
            losses = sum(1 for a, b in zip(results[i], results[leader]) if a < b)
            ties = sum(1 for a, b in zip(results[i], results[leader]) if a == b)
            n = len(results[i]) - ties
            if n > 0 and binom_tail(losses, n) < alpha:
                continue                      # значимо хуже лидера — выбывает
            survivors.append(i)
        alive = survivors

    winner = max(alive, key=lambda i: sum(results[i]) / len(results[i]))
    return configs[winner], spent, len(alive)

Результаты на той же задаче настройки GA (12 конфигураций, 15 инстансов):

полный перебор: 180 прогонов GA, победитель {'pop': 30, 'mut': 3.0, 'tour': 4}
F-race (alpha=0.05): 133 прогона (74% от полного), выжило 7, победитель тот же
F-race (alpha=0.10): 113 прогонов (63% от полного), выжило 3, победитель тот же

На картинке видно, откуда берутся эти 133: первые пять инстансов оплачиваются полностью (12 × 5 = 60 прогонов), после пятого знаковый тест выбрасывает сразу четыре аутсайдера, после восьмого — ещё одного, и остаток гонки достаётся семи выжившим. Вся экономия сосредоточена в правой части таблицы, и она тем больше, чем раньше отсев отличает безнадёжную конфигурацию от конкурентоспособной — но отсеивать раньше пятого наблюдения опасно, об этом ниже.

Экономия скромная на 12 конфигурациях и становится драматической на сотнях: отсев работает мультипликативно, а число конфигураций в реальной настройке (5 параметров по 4 значения — уже 1024) растёт куда быстрее числа инстансов. Настоящий irace вдобавок итеративный: после гонки он порождает новые конфигурации вокруг выживших и запускает гонку заново — то есть внутри у него самый обычный поиск.

Альтернативы, о которых стоит знать:

Управление параметрами на ходу

Второй путь — не искать «правильное число», а менять его по ситуации.

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

Самоадаптация — параметр становится частью решения и эволюционирует вместе с ним. Классика жанра — эволюционные стратегии, где шаг мутации $\sigma$ записан в хромосоме: особи с удачным шагом выживают и передают его потомкам. Работает, потому что «хороший шаг» и «хорошее решение» коррелируют.

Адаптивное управление — механизм смотрит на статистику последних шагов и перераспределяет усилия. Самый практичный вариант — адаптивный выбор оператора (adaptive operator selection): у нас четыре мутации, какая из них полезнее прямо сейчас? Это классическая задача многорукого бандита: надо и эксплуатировать лучший оператор, и не забывать пробовать остальные, потому что полезность меняется по ходу поиска.

import math


def ucb_choose(reward: list[float], uses: list[int], c: float = 1.5) -> int:
    """UCB1: баланс «использовать лучшее» и «проверить забытое».

    reward[i] — накопленная (скользящим средним) заслуга оператора i,
    uses[i] — сколько раз его применяли. Второе слагаемое растёт для операторов,
    которых давно не пробовали, — так механизм не залипает на локально удачном.
    """
    total = sum(uses)
    return max(range(len(reward)),
               key=lambda i: reward[i] / uses[i] + c * math.sqrt(math.log(total) / uses[i]))


def credit(reward: list[float], uses: list[int], op: int, gain: float, decay: float = 0.9) -> None:
    """Назначение заслуги: награда — улучшение фитнеса, полученное этим применением.

    Скользящее среднее (decay) обязательно: оператор, который был полезен в начале поиска,
    к концу может стать бесполезным, и старые заслуги не должны его защищать вечно.
    """
    uses[op] += 1
    reward[op] = decay * reward[op] + max(0.0, gain)

И сразу — честный результат эксперимента на нашей же задаче: четыре оператора (флип одного бита, флип трёх, флип блока из пяти, обмен «включённого» и «выключенного» бита), 15 инстансов, бюджет 4 000 оценок.

равномерный выбор оператора: медиана 1860
адаптивный (UCB):            медиана 1868
адаптивный лучше на 6 из 15 инстансов

Разницы нет. И это типичный результат: адаптивный выбор окупается, только когда операторы действительно сильно различаются по полезности — либо между стадиями поиска, либо между инстансами. Если все четыре оператора примерно одинаково хороши, механизм добавляет сложность и накладные расходы, а взамен не даёт ничего. Проверять это надо измерением, а не верой в «умный» алгоритм — обзор бандитных механизмов и условий их полезности есть у Fialho и соавторов, «Analyzing bandit-based adaptive operator selection mechanisms», Annals of Mathematics and AI, 2010.

Гиперэвристики: поиск по пространству эвристик

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

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

Различают два класса (таксономия — Burke и соавторы, «Hyper-heuristics: a survey of the state of the art», Journal of the Operational Research Society, 2013):

• Selection hyper-heuristics выбирают из готовых эвристик — это то, что нарисовано выше. Бенчмарк-платформа для них — HyFlex и соревнование CHeSC.
• Generation hyper-heuristics создают новые эвристики, обычно генетическим программированием: эволюционируется выражение-правило вида «приоритет теста = покрытие / (время + 1)». В SBSE так генерировали правила приоритизации тестов и функции оценки — и получавшиеся формулы иногда оказывались и лучше рукописных, и вполне читаемыми.

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

Выбор алгоритма: no free lunch на практике

Теорема No Free Lunch говорит, что усреднённо по всем задачам все алгоритмы одинаковы. Практический смысл — алгоритм надо подбирать под структуру задачи. Формализовал это ещё Rice, «The Algorithm Selection Problem», Advances in Computers, 1976: есть признаки инстанса, есть портфель алгоритмов, нужна функция «признаки → алгоритм».

Самая известная реализация — SATzilla (Xu, Hutter, Hoos, Leyton-Brown, JAIR 2008): по признакам конкретной SAT-формулы модель предсказывает время работы каждого решателя из портфеля и запускает самый перспективный. Портфель систематически бил любого одиночного участника соревнований. Стандартизованный набор данных для таких исследований — ASlib.

Инженеру редко нужен полноценный per-instance selection. Ему нужны две вещи попроще, и обе работают:

1. Портфель с делением бюджета. Запустить hill climbing, отжиг и GA по трети бюджета каждый и взять лучший результат. Проигрыш лучшему алгоритму — максимум трёхкратный по бюджету, зато вы застрахованы от катастрофического выбора. Именно так устроен ансамбль в OpenTuner, где бюджет между техниками распределяется бандитом по ходу дела.
2. Признаки ландшафта как диагностика. Автокорреляция фитнеса вдоль случайного блуждания и доля нейтральных шагов измеряются десятком строк (мы делали это в статье про пространство поиска) и отвечают на главный вопрос: ландшафт вообще информативен? Если автокорреляция около нуля — никакой алгоритм не поможет, чините фитнес.

Что крутить в первую очередь

Порядок действий, который стоит держать в голове как чек-лист:

1. Фитнес информативен? Плато лечится расстояниями (branch distance и родня). Это даёт качественный скачок, а не проценты.
2. Оценка дешева? Инкрементальный пересчёт, кэш, ранний выход — глава 12. Удвоение скорости оценки = удвоение бюджета поиска.
3. Представление связное? Соседние решения должны отличаться немного, а операторы — не рвать структуру.
4. Бюджет разумен? Часто «алгоритм плохой» означает «мы дали ему 200 оценок вместо 20 000».
5. Baseline честный? Случайный поиск при равном бюджете, 30 запусков, размер эффекта $\hat{A}_ {12}$ — протокол из обзорной статьи.
6. И только теперь — настройка параметров гонками и, если операторы действительно разнородны, адаптивный выбор.

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

1. Настраивать параметры до того, как починен фитнес. 6 % поверх сломанного ландшафта — это ноль поверх нуля.
2. Настраивать на тех же инстансах, на которых отчитываетесь. Классическое переобучение; нужны раздельные наборы для настройки и проверки.
3. Усреднять сырые фитнесы по разным инстансам. Инстанс с большими числами перевесит все остальные. Ранги или нормировка — обязательны.
4. Сравнивать конфигурации на разных инстансах. Гонка работает потому, что наблюдения парные: все конфигурации видят один и тот же инстанс.
5. Отсеивать слишком рано. Отсев после двух инстансов выкидывает хорошие конфигурации из-за случайности; минимум пять наблюдений — разумный порог по умолчанию.
6. Считать адаптивность бесплатной. Механизм выбора оператора сам имеет параметры (скорость забывания, коэффициент исследования) — вы поменяли одну задачу настройки на другую.
7. Верить, что найденная конфигурация универсальна. Она найдена для вашего класса задач, вашего бюджета и вашей реализации фитнеса. Меняется любой из трёх — настройка устаревает.
8. Игнорировать стоимость мета-уровня. 900 прогонов поиска — это часы или дни; планируйте их как отдельную вычислительную задачу, а не как «сейчас быстренько подберём».

Мини-итог

• Настройка параметров даёт единицы процентов, выбор фитнеса и представления — десятки и разы. Начинайте с того, что даёт больше.
• Параметрами управляют двумя способами: настройка до запуска (tuning) и управление по ходу (control: детерминированное, адаптивное, самоадаптивное).
• Настройка — обычная задача поиска на мета-уровне, с двумя особенностями: фитнес есть распределение по инстансам (нужны ранги), а одна оценка стоит целого прогона поиска.
• Гонки (F-race, irace) экономят бюджет, отсеивая проигрывающие конфигурации по парным наблюдениям; в примере статьи — 63–74 % от полного перебора при том же победителе.
• Адаптивный выбор оператора помогает, только если операторы разнородны по полезности; проверяется экспериментом, а не верой.
• Гиперэвристики выносят выбор эвристики за барьер домена и переносятся между задачами; генерирующие варианты выдают читаемое правило, а не набор весов.
• Выбор алгоритма из портфеля с делением бюджета — дешёвая страховка от катастрофически неправильного выбора.

Источники

• Eiben, Hinterding, Michalewicz. «Parameter control in evolutionary algorithms», IEEE TEC 1999.
• Arcuri, Fraser. «Parameter tuning or default values?», EMSE 2013.
• López-Ibáñez, Dubois-Lacoste, Pérez Cáceres, Birattari, Stützle. «The irace package: Iterated racing for automatic algorithm configuration», ORP 2016.
• Hutter, Hoos, Leyton-Brown, Stützle. «ParamILS», JAIR 2009.
• Fialho, Da Costa, Schoenauer, Sebag. «Analyzing bandit-based adaptive operator selection mechanisms», AMAI 2010.
• Burke et al. «Hyper-heuristics: a survey of the state of the art», JORS 2013.
• Rice. «The Algorithm Selection Problem», Advances in Computers 1976.
• Xu, Hutter, Hoos, Leyton-Brown. «SATzilla», JAIR 2008.
• Ansel et al. «OpenTuner: An Extensible Framework for Program Autotuning», PACT 2014.

Что дальше

На этом трек «SBSE и поисковые алгоритмы» действительно заканчивается — четырнадцать статей от «зачем вообще переформулировать инженерную задачу как оптимизационную» до настройки самого поискового движка. Логичные продолжения на портале:

• Алгоритмы и структуры данных — точные методы, сложность и приближения: половина решений «поиск или точный алгоритм» принимается там.
• Машинное обучение — вторая половина уравнения «модель предлагает, поиск проверяет»: суррогаты, оценка моделей, переобучение.
• Нейронные сети — как устроены модели, которые сегодня работают операторами мутации.
• Тестирование — процесс, в который встраивается всё, что генерирует поиск.
• Go — практичный язык для быстрых оценщиков и распределённых ферм фитнеса.

Общая карта портала — в дорожной карте.

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