Исполняемая спецификация как фитнес-функция: поиск, у которого судья — компилятор
Аналитик приносит восемь строк. Сумма корзины — скидка: 5000 → 0, 8000 → 0, 12000 → 1200, 50000 → 5000. И ещё четыре с отметкой «постоянный клиент»: 1000 → 50, 5000 → 250, 12000 → 1800, 50000 → 7500. Правила он словами не формулирует: «ну, там процент какой-то, у нас всегда так считали». Задача — написать спецификацию, которая эти восемь строк объясняет.
Это ровно постановка SBSE. Пространство — все спецификации, которые вообще можно написать. Оценка — исполнить и сравнить. Сделать трудно, проверить легко. Асимметрия на месте, значит, можно искать.
Особенность этой задачи в том, чего в ней нет. Нет ни эксперта, ни модели-судьи, ни метрики-прокси вроде покрытия строк. Кандидата оценивает компилятор языка спецификаций: разобрал или нет, проверил типы или нет, исполнил примеры или получил расхождение. Фитнес — это код возврата. И именно потому, что фитнес здесь идеален по всем учебным критериям — детерминирован, дёшев, полностью машинный, — на нём особенно отчётливо видно, что хорошая фитнес-функция не спасает от главной беды поиска: он оптимизирует ровно то, что вы измерили, и ни на йоту больше.
Всё, что ниже, — разбор одного прогона: 115 запусков, 1 865 472 оценок фитнеса, 8 задач, 5 зёрен на каждую конфигурацию. Числа в тексте — только измеренные; ни одно не приведено по памяти.
Статья предполагает, что вы знакомы с устройством пространства поиска и требованиями к фитнесу (Пространство поиска и фитнес-функция), с механикой ГА — селекцией, кроссовером, мутацией (Генетические алгоритмы) — и с доминированием по Парето, недоминируемой сортировкой и constrained-domination (Многокритериальная оптимизация). Ничего из этого здесь не пересказывается. Про язык исполняемых спецификаций, который выступает оракулом, достаточно знать, что у него есть блоки
правило,свойствоипример— см. трек FTS.
Почему фитнес — главная трудность, и почему здесь её нет
Вводная статья трека формулирует правило: SBSE работает там, где «сделать трудно, оценить легко». Обратная сторона правила названа там же — правый нижний угол диаграммы, задачи вроде «сделай архитектуру красивее», где пространство огромно, а честного числового критерия нет. Между этими полюсами лежит вся практика, и почти всегда оценка — компромисс: покрытие вместо качества тестов, modularization quality вместо качества нарезки, «прошли тесты» вместо корректности.
Спецификация как объект поиска даёт редкий случай, когда компромисса нет. Оценщик не приближает цель — он и есть цель:
| Что обычно приходится измерять прокси | Здесь измеряется напрямую |
|---|---|
| «код синтаксически корректен» — линтером с эвристиками | грамматика языка, распознаватель |
| «типы сходятся» — статическим анализом с ложными срабатываниями | validate, вывод типов |
| «поведение верно» — выборкой тестов | блок пример, исполняется движком |
| «обобщение верно» — надеждой | блок свойство, инвариант, исполняется на каждом входе |
| «рассуждение не порочно» — ревью | детектор структурных дефектов вывода |
| «посылка допустима» — доверием к автору | манифест проверенных законов |
Шесть уровней проверки, ни одного человеческого суждения, полностью
детерминированный результат. Прогон одного и того же кандидата дважды даёт один
и тот же вердикт с точностью до бита. Требование Свойство 3 из первой статьи
трека выполнено не усилием, а по построению.
И этого недостаточно. Дальше — почему.
Что синтезируется: спецификация как дерево
Особь — не строка. Строка порождала бы синтаксический мусор, и весь бюджет уходил бы на его отбраковку. Особь — типизированное дерево, каждый узел которого соответствует одному правилу грамматики целевого языка:
геном
└── rules: [правило]
├── name
├── when: [условие] (1..3)
│ ├── field — имя поля объекта
│ ├── operator — не меньше | больше | равен | ...
│ └── value: операнд
└── action
├── kind — add («то добавить») | set («то результат равен»)
└── value: операнд
операнд ::= значение | поле F | результат | N процентов от поля F
Печать дерева в текст — детерминированный принтер, обратный распознавателю грамматики. Отсюда главное свойство представления: любая мутация и любое скрещивание дают документ, который грамматика принимает. Это не рассуждение, а измерение: за весь основной прогон, 1 865 472 оценок, синтаксических отказов было 0 — 0,00 % популяции.
Заметьте, что именно этим доказано, а что нет. Грамматика гарантирует синтаксис и больше ничего. Мутация «поменять поле в условии, не трогая операнд» свободно порождает документ, где процент считается от логического признака, — он безупречно разбирается и падает на типизации. Такие особи в прогоне составили 4,36 %. Граница между «форма» и «смысл» здесь проходит буквально по коду возврата, и её видно в цифрах.
Операторы
Девять мутаций, каждая — локальное изменение одного узла: сдвиг константы (самая частая), замена операнда, замена оператора, замена поля в условии, замена действия, добавление и удаление правила, добавление и удаление условия, перестановка двух правил.
Перестановка — не декорация. Список правил упорядочен и семантичен: добавить
копит, результат равен перезаписывает. Поэтому и скрещивание одноточечное, с
обменом хвостами: оно сохраняет смысл префиксов обоих родителей, тогда как
равномерное разрушает порядок. Равномерное оставлено вторым вариантом и
применяется в четверти случаев.
Пороги берутся не из воздуха. Пул констант для каждого числового поля собирается
из значений, встречающихся во входах обучающих примеров, — тот же приём, каким
деревья решений выбирают точки разбиения. Без него искать порог 10000 на
непрерывной прямой безнадёжно. Забегая вперёд: именно этот пул станет источником
самого поучительного результата всей работы.
Семь величин, ни одна из которых не оценивается человеком
компилируется 0/1 ограничение
проходит validate (типы) 0/1 ограничение
только verified/derived морфизмы 0/1 ограничение
доля пройденных блоков «пример» [0,1] цель
доля выполненных блоков «свойство» [0,1] цель
находок детектора структурных ошибок N цель (штраф)
число правил N цель (штраф за раздувание)
Разделение на цели и ограничения — не техническая деталь. Три первые величины булевы, и это не шкала: особь, которая не компилируется, не «хуже на 0,3», её просто нет. Поэтому они входят в NSGA-II не координатами фронта, а правилом доминирования по Дебу — ровно так, как это описано в статье про многокритериальность, где «патч обязан компилироваться» приведён как канонический пример ограничения.
Четыре цели дают вектор, который алгоритм минимизирует. Ни одна из них не сворачивается в скаляр весами, и это принципиально. Спецификация из восьми правил, объясняющая все примеры, и спецификация из двух, объясняющая девять из десяти, — разные ответы на разные вопросы. Выбирать между ними должен человек, глядя на фронт. Коэффициент, подобранный до прогона, спрятал бы этот выбор внутрь и выдал бы его за вычисление.
Честный результат про фронт
Так — в теории. На практике фронт в этой задаче вырождается, и об этом стоит сказать раньше, чем о победах.
Цели дискретны и грубы: доля примеров при восьми примерах принимает девять значений, число находок детектора — обычно ноль, число правил — от одного до восьми. Ничьих поэтому чудовищно много, и десятки особей садятся ровно в одну точку пространства целей. Считать размер фронта по особям бессмысленно: он равен размеру популяции почти всегда. Считать нужно различные векторы, и вот их за весь прогон набиралось от 2 до 8 штук на задачу.
Хуже того: как только цель «непройденные примеры» обнуляется, а находок детектора нет, единственная оставшаяся координата — число правил, и фронт схлопывается в две-три точки. Многокритериальность работает во время поиска, поддерживая разнообразие компромиссов, и почти перестаёт работать в конце.
Практический вывод: правило выбора ответа с фронта всё равно приходится объявлять явно. Здесь оно такое: максимум пройденных обучающих примеров, при равенстве — минимум правил, затем минимум находок детектора. Это по-прежнему лучше весов — правило написано в одном месте, читается за секунду и не влияет на ход поиска, — но иллюзий про «фронт сам всё покажет» лучше не иметь.
Прогон, который ничего не доказал
Первый полный прогон (популяция 150, 60 поколений) дал аккуратную картинку: алгоритм сходился, кривые выглядели прилично, 3 задачи из 8 не решались ни в одном прогоне. Напрашивалось объяснение «сложные задачи, нужен бюджет побольше».
Для 2 из них объяснение было неверным. Лестница процентов в пространстве поиска обрывалась на 100 %, а эталон кредитного лимита содержал «300 процентов от поля доход», эталон счёта абонента — «200 процентов» и «500 процентов». Ответа в пространстве просто не было. Алгоритм честно сходился к лучшему из того, что там лежало, и кривая сходимости выглядела ровно так же, как у задачи, которая трудна по существу.
Это стоит сформулировать как правило:
«Алгоритм не нашёл» и «искать было негде» дают неотличимые кривые сходимости. Прежде чем объяснять неудачу поиска свойствами ландшафта, бюджетом или параметрами, проверьте, что ответ достижим: возьмите известное решение, закодируйте его вручную и убедитесь, что фитнес выдаёт на нём нулевой вектор целей. Проверка стоит одного теста.
Теперь — оговорка, без которой этот раздел был бы рекламой. Лестницу процентов я расширил одновременно с увеличением бюджета (популяция 200, 120 поколений), поэтому разделить два эффекта по имеющимся данным нельзя. Что видно: кредитный лимит перешёл с 1/5 на 4/5 решённых прогонов, счёт абонента остался на 0/5 — то есть достижимость была необходима и не оказалась достаточна. Ставить чистый эксперимент «только пул, при том же бюджете» я не стал, и это дырка в измерении, а не результат.
Сырые числа первой версии сохранены отдельным файлом и не выброшены: это единственный измеренный пример ошибки «искать было негде», а такие примеры полезнее исправленных.
Переобучение под фитнес: центральный результат
Постановка эксперимента простая. Из эталонной спецификации порождается сетка пар «вход → выход» — всего 639 пар на 8 задач. 8 пар отдаются алгоритму как обучающие. Остальные откладываются и не участвуют ни в целях, ни в ограничениях, ни в критерии остановки — это измерительный прибор, а не часть отбора. (Отдельный тест механически проверяет, что вектор целей не меняется от того, передана отложенная выборка или нет.)
Витрина первая: порог, которого не было в данных
Задача — та самая скидка из вступления. Эталон написан человеком и взят из репозитория языка без единой правки:
правило «Большая покупка»
если сумма не меньше 10000
то добавить 10 процентов от поля сумма
правило «Постоянный клиент»
если «постоянный клиент» равен да
то добавить 5 процентов от поля сумма
Что нашёл поиск (зерно 1, все обучающие примеры пройдены):
правило П1
если «постоянный клиент» не равен нет
то добавить 5 процентов от поля сумма
правило П2
если сумма больше 8000
то добавить 10 процентов от поля сумма
Правила переставлены (порядок здесь ничего не меняет — оба добавить),
«равен да» записано как «не равен нет» — но структура найдена точно: два
правила, те же поля, те же проценты. Для восьми примеров это идеальный ответ.
Расходится одно число: порог 10000 против 8000. И вот значения суммы в обучающей выборке: 1000, 5000, 8000, 12000, 50000. Между 8000 и 12000 данных нет вообще. Любой порог из этого промежутка объясняет все восемь примеров одинаково хорошо. Алгоритм выбрал крайний слева — не по злому умыслу, а потому что в его пространстве это было первое значение, которое сработало.
На отложенных парах спецификация проваливается ровно 2 из 16 раз, и оба раза на одном входе: сумма 9000 — единственная точка, где два порога расходятся. Разрыв составляет 12,5 п.п.
Это не ошибка алгоритма. Это недоопределённость постановки, которую поиск
обнаружил и предъявил. Человек, писавший 10000, знал что-то, чего в данных
нет: круглые числа в маркетинговых правилах. Алгоритм такого знания не имеет и
имитировать его не должен.
Витрина вторая: запоминание вместо объяснения
Задача — итоговый балл курса. Что нашёл поиск на тех же 8 примерах:
правило П1
если посещаемость равен 50
и «баллы за работы» не меньше 56
то результат равен 56
правило П2
если посещаемость больше 80
и посещаемость не меньше поле посещаемость
то результат равен 42
правило П3
если посещаемость равен 95
и «баллы за работы» не больше 100
то результат равен 10
Здесь нет ни одной попытки что-либо обобщить. Есть три условия, вырезающие по одной обучающей точке, и три константы, равные ответам в этих точках. Условие «посещаемость не меньше поле посещаемость» — тавтология, добавленная мутацией и не отсеянная, потому что ни одна из семи величин фитнеса за тавтологии не штрафует.
Обучающие примеры: 100,0 %. Отложенные: 34,5 %. Разрыв — 65,5 п.п., худший в наборе.
Разница между двумя витринами — это разница между спецификацией и таблицей подстановки. Обе проходят приёмку. Первая — почти правильная, вторая — бесполезная, и отличить их по фитнесу невозможно, потому что фитнес у них одинаковый и равен максимуму.
Величина разрыва
Медиана по семи задачам, где мерялись все три конфигурации, по 5 зёрнам каждая:
| Конфигурация | обучающие | отложенные | разрыв (медиана) | разрыв (среднее по задачам) |
|---|---|---|---|---|
| только примеры | 87,5 % | 45,3 % | 24,4 п.п. | 30,4 п.п. |
| примеры + свойства | 87,5 % | 55,6 % | 30,4 п.п. | 31,9 п.п. |
| градуированная цель | 87,5 % | 55,6 % | 16,1 п.п. | 22,1 п.п. |
По задачам разброс огромный — от 12,5 п.п. на скидке до 65,5 п.п. на курсе, и это при одинаковом бюджете и одинаковом числе обучающих пар. Хуже всего дела там, где выход зависит от численного поля напрямую, а лучше всего — там, где ответ дискретен.
Разброс между зёрнами тоже стоит смотреть, а не усреднять. На платежах отложенная доля по пяти зёрнам легла в 64,3–71,4 % — то есть один и тот же алгоритм на одной и той же задаче даёт то почти правильную спецификацию, то почти бесполезную, и разница целиком в случайном зерне.
Это в точности тот же феномен, что описан в автоматическом ремонте программ: тест-сьют — обучающая выборка, реальные входы — отложенная, инструмент оптимизирует train-loss. Новое здесь только то, что оракул безупречен. Патч, переобученный под тесты, можно списать на слабость тестов. Спецификация, переобученная под примеры, списать не на что: примеры исполнены точно, типы проверены, детектор молчал. Разрыв возник не из-за плохого измерения, а из-за того, что измерять было нечего.
Сколько примеров нужно, чтобы разрыв закрылся
Единственный рычаг, который в этой задаче работает надёжно, — количество данных. 275 прогонов, четыре размера обучающей выборки:
| Обучающих пар | обучающие | отложенные | разрыв |
|---|---|---|---|
| 4 | 100,0 % | 26,5 % | 68,8 п.п. |
| 8 | 87,5 % | 45,6 % | 35,6 п.п. |
| 16 | 75,0 % | 65,0 % | 18,4 п.п. |
| 32 | 59,4 % | 45,0 % | 11,2 п.п. |
Кривая знакомая до боли всякому, кто видел learning curve. Разрыв падает примерно вшестеро. Обучающая доля при этом падает — с 100,0 % до 59,4 %, — и это правильный признак: при четырёх примерах алгоритм подгоняет их все и не понимает ничего; при тридцати двух он уже не может подогнать всё и вынужден искать что-то похожее на правило.
Практическое следствие для того, кто собирается синтезировать спецификации по примерам: отчёт «алгоритм объяснил 100 % ваших примеров» на выборке из четырёх штук означает ровно то, что примеров было четыре. Отложенная выборка здесь не научная строгость, а единственный способ отличить находку от запоминания.
Помогают ли свойства? Проверяемая гипотеза и её измерение
Язык различает пример и свойство. Пример — точка: этот вход даёт этот выход.
Свойство — инвариант: результат неотрицателен, результат не превышает 20 %
от суммы, счёт не ниже абонентской платы. Гипотеза очевидна: инвариант
запрещает целые области пространства, значит, должен сузить множество
спецификаций, которые проходят приёмку, но врут за пределами обучающих точек.
Гипотеза оказалась верной, и эффект оказался маленьким.
По медиане на восьми обучающих парах свойства разрыв даже ухудшили (24,4 п.п. против 30,4 п.п.) — но это артефакт того, что при восьми парах медиана считается по трём-четырём различным значениям. Развёртка по размеру выборки показывает картину чище:
| Обучающих пар | разрыв, только примеры | разрыв, + свойства | эффект |
|---|---|---|---|
| 4 | 68,8 п.п. | 67,6 п.п. | -1,2 п.п. |
| 8 | 35,6 п.п. | 31,3 п.п. | -4,3 п.п. |
| 16 | 18,4 п.п. | 17,3 п.п. | -1,1 п.п. |
| 32 | 11,2 п.п. | 9,4 п.п. | -1,9 п.п. |
Свойства сокращают разрыв на всех 4 размерах — 4 из 4 точек со знаком «минус», без единого исключения, — но величина эффекта 1,1–4,3 п.п., тогда как учетверение выборки даёт десятки. Честный вывод: инвариант — правильный по направлению, но слабый по силе инструмент, и заменить им данные нельзя.
Почему так — видно, если посмотреть, что именно инвариант запрещает. «Скидка неотрицательна» и «скидка не больше 20 % от суммы» отсекают спецификации, которые вылетают за коридор. Обе витрины выше в коридор укладываются: и порог 8000, и таблица подстановки дают неотрицательные значения в пределах 20 %. Инвариант отсекает грубую ложь, а переобучение — ложь тонкая, живущая внутри допустимого коридора, в промежутках между обучающими точками.
Ровно об этой границе честно предупреждает документация самого языка: проверка идёт по узлам сетки, и нарушение, живущее строго между узлами и не достающее до края, будет пропущено. Уменьшение шага расширяет сетку и полноты не даёт. Инвариант сужает пространство обмана. Он его не закрывает.
Ступенька против склона: цель определяет ландшафт
Блок пример в языке проверяет точное совпадение: ожидается результат равен 3000
либо выполнено, либо нет. Это правильная приёмка и никуда не годный ландшафт.
Пока сумма всех сработавших правил не сойдётся до последнего рубля, награда
равна нулю; поиску не за что зацепиться; пространство — плато с редкими иглами.
Третья рука эксперимента подменяет цель: вместо доли точных совпадений — средняя относительная ошибка, срезанная единицей. Приёмка не меняется, меняется только то, что подаётся в NSGA-II. Результат:
| Задача | точное совпадение, отложенные | градуированная ошибка, отложенные |
|---|---|---|
| счёт абонента | 0,0 % | 100,0 % |
| стоимость доставки | 40,6 % | 55,6 % |
| страховая премия | 45,3 % | 3,1 % |
| кредитный лимит | 75,6 % | 55,6 % |
На счёте абонента градуированная цель превращает полный провал в полное решение. На страховой премии — ровно наоборот, ломает то, что работало: средняя ошибка вознаграждает «примерно правильные» коэффициенты, и поиск застревает в широком пологом минимуме, из которого до точного ответа не дотягивается. В среднем по задачам градуированная цель разрыв сокращает (22,1 п.п. против 30,4 п.п.), но цена — поломка тех задач, где точное совпадение работало.
Мораль не «берите градуированный фитнес». Мораль в том, что приёмка и цель поиска — разные функции, и подменять одну другой можно только осознанно. Статья про дорогой фитнес формулирует смежное правило с другой стороны: раннее прекращение прогона на первом падении допустимо для бинарного решения и запрещено для градуированного, потому что уничтожает градиент. Здесь то же различие видно с точки зрения не стоимости, а результата.
Манифест как стена: вторая семья задач
В задачах-утилитах седьмая составляющая фитнеса — «только verified/derived морфизмы» — вырождена: утилита законов не объявляет, ограничение выполнено всегда. Чтобы измерить его, нужна вторая постановка: дан стартовый тип и целевой, найти цепочку доменных законов, которую верификационный гейт сертифицирует.
Словарь генов — 43 записей, из которых 21 допустимы, а остальные — правдоподобные подделки: несуществующие законы, записи со статусом «предложено, не проверено» и подмены домена под проверенным именем. Поиск не знает, что есть что.
Результат: 30/30 прогонов дошли до сертификации, медиана — 1 поколений поколение. Задача лёгкая. Интересна не она, а гистограмма отказов:
| Код | Доля популяции |
|---|---|
| несходящаяся цепочка вывода (тип) | 99,79 % |
| заключение не совпадает с целью | 0,09 % |
| закон не подтверждён библиотекой | 0,08 % |
| сертифицировано | 0,04 % |
Ограничение «только проверенные законы» срабатывает на 0,08 % кандидатов — не потому что подделки редки (их в словаре половина), а потому что почти все они не доживают: цепочка с подставным доменом не складывается по типам и умирает раньше, на проверке вывода. Стена стоит на два уровня раньше, чем ожидалось, и она почти непроницаема.
Отсюда следствие, важное для проектирования фитнеса: ограничение, до которого популяция не доживает, ничего не ограничивает. Я прогнал обе конфигурации — допустимость закона как ограничение и как отдельная цель — и разницы не получил: 99,79 % особей отсеиваются раньше, чем эта величина успевает на что-то повлиять.
И одна деталь, которая мне нравится больше всех остальных чисел. Во всех
30/30 прогонах поиск нашёл цепочку
короче человеческого эталона: вместо двух шагов — один, через
derived-запись библиотеки, законно выведенную композицией из тех же двух.
Формально это лучшее решение по цели «длина цепочки». Содержательно — то же
самое рассуждение, записанное короче. Редкий случай, когда «поиск обыграл
человека» означает именно то, что звучит.
Параллельность: что масштабируется, а что нет
Прогоны независимы, поэтому напрашивается пул: 32 прогонов в очередь, N рабочих потоков.
| Потоков | Настенное время | Сумма времени прогонов | Ускорение | Эффективность |
|---|---|---|---|---|
| 1 | 80,3 с | 80,2 с | 1,00 × | 100 % |
| 2 | 41,9 с | 83,5 с | 1,92 × | 96 % |
| 4 | 22,9 с | 91,3 с | 3,50 × | 87 % |
| 8 | 17,5 с | 131,3 с | 4,59 × | 57 % |
| 16 | 16,9 с | 250,6 с | 4,76 × | 30 % |
Читать эту таблицу нужно по третьему столбцу, а не по четвёртому. Сумма собственного времени прогонов растёт с 80,2 с до 250,6 с — втрое. Это не накладные расходы на синхронизацию (её здесь нет вовсе), это конкуренция за физическое ядро: процессор — AMD Ryzen 7 9700X 8-Core Processor, то есть 16 потоков логических на восьми физических, а машина к тому же не пустая — средняя загрузка в момент замера 9,7. Отсюда потолок 4,76 × и эффективность 30 %.
Скучный, но полезный вывод: на SMT-ядрах вычислительная нагрузка не удваивается, и отчитываться про «16 ядер» без проверки топологии — способ опубликовать неверное число. Полезная часть кривой заканчивается на четырёх потоках, где эффективность ещё 87 %.
Островная модель: где параллельность даёт не только скорость
Пул прогонов ускоряет и ничего не меняет в качестве. Островная модель меняет: 8 популяций, 10 эпох по 15 поколений, между эпохами — кольцевая миграция лучших особей.
| Конфигурация | Островов решило задачу (медиана) | Всего решивших островов | Оценок (медиана) |
|---|---|---|---|
| без миграции | 1,5 | 60 | 42625 |
| с миграцией | 7,5 | 117 | 43643 |
Разница почти двукратная по числу решивших островов при практически одинаковом числе оценок фитнеса и одинаковом настенном времени (1,8 с против 1,9 с). Миграция здесь — не оптимизация скорости, а механизм передачи находки: остров, наткнувшийся на удачную структуру правил, раздаёт её соседям, и те доводят константы.
Когда поиск уместен, а когда нет
Две базовые линии, без которых числа выше ничего не значат.
Случайный поиск при равном бюджете (24200 оценок, никакого отбора, лучшая особь по тому же правилу выбора). Генетика выигрывает по обучающим примерам на 6/8 задачах. По отложенным — только на 4/8.
Это надо перечитать. Отбор, скрещивание и фронт уверенно помогают подогнать обучающую выборку и в половине случаев не помогают обобщить. На кредитном лимите случайный поиск дал отложенную долю 77,8 % против 75,6 % у генетики — то есть проиграл на обучении и выиграл на отложенных, ровно потому, что подогнал слабее. Более сильный оптимизатор переобучается сильнее; это не парадокс, а определение.
Перебор. Для задач с одним правилом пространство мало, и полный обход занимает секунды. Для двух правил:
| Задача | Размер пространства (2 правила) | Обойдено целиком | Решение найдено на шаге |
|---|---|---|---|
| контроль доступа | 1,55·10^4 | да, 1,5 с | 1021 |
| скидка | 1,65·10^7 | нет | — |
| счёт абонента | 4,54·10^8 | нет | — |
Задача про контроль доступа — единственная с логическим выходом, и пространство действий в ней сжимается до двух точек. Полный перебор находит решение за 1,5 с. Генетический алгоритм решает её тоже — за 9 поколений, с 5/5 прогонов, — и не даёт ничего сверх перебора: отложенная доля у обоих 80,0 %. Тут ГА — лишняя конструкция, которую надо было заменить четырьмя вложенными циклами.
Дальше пространство растёт как $|A|^k$ по числу правил, и на двух правилах уже не влезает в бюджет ни в одной из остальных задач. Граница между «перебирайте» и «ищите» в этом семействе проходит между одним и двумя правилами, и находится она арифметикой, а не экспериментом.
Сводя всё вместе:
| Признак задачи | Что брать |
|---|---|
| выход дискретен, полей мало, правил 1–2 | перебор; ГА не окупается |
| приёмка бинарная и точная, ландшафт — плато с иглами | сначала чинить цель, потом алгоритм |
| примеров меньше десятка | не искать вовсе: подгонка гарантирована |
| есть инварианты в дополнение к примерам | искать, но не ждать от инвариантов чуда |
| нужен размен «покрытие / размер» | фронт, но с явным правилом выбора ответа |
| ответ может лежать вне словаря операндов | проверить достижимость эталона до прогона |
Типичные ошибки
- Отчитываться о качестве по той же выборке, на которой шёл поиск. Разрыв в 68,8 п.п. при четырёх примерах — не экзотика, а норма.
- Считать безупречный оракул защитой от переобучения. Компилятор детерминирован, типы проверены, детектор молчит — и спецификация всё равно таблица подстановки. Качество оракула и полнота постановки — разные вещи.
- Объяснять неудачу поиска ландшафтом, не проверив достижимость ответа. Кривые совпадают; проверка стоит одного теста.
- Мерить размер фронта по особям. При дискретных целях он равен размеру популяции почти всегда и ничего не сообщает. Считайте различные векторы.
- Вводить ограничение, до которого популяция не доживает. Оно не ограничивает; проверяйте гистограмму кодов отказа, а не намерения.
- Подменять приёмку целью поиска молча. Градуированная ошибка спасает одни задачи и ломает другие; это осознанное решение, а не улучшение.
- Публиковать ускорение, не проверив топологию процессора и загрузку машины. Шестнадцать потоков на восьми ядрах дают 4,76 ×, а не шестнадцать.
- Усреднять по зёрнам, не показывая разброс. Одна и та же задача даёт отложенную долю в диапазоне 64,3–71,4 %.
- Ждать, что фронт сам выберет ответ. Правило выбора всё равно объявляется; лучше явно и в одном месте.
Мини-итог
| Вопрос | Ответ из измерений |
|---|---|
| Даёт ли исполняемая спецификация детерминированный фитнес? | Да, полностью: 0,00 % синтаксических отказов, все вердикты воспроизводимы |
| Спасает ли это от переобучения? | Нет. Медианный разрыв 24,4 п.п., худший — 65,5 п.п. |
| Помогают ли инварианты? | Да, стабильно и слабо: 1,1–4,3 п.п. на всех размерах выборки |
| Что помогает сильно? | Данные: с 4 до 32 примеров разрыв падает с 68,8 п.п. до 11,2 п.п. |
| Бьёт ли ГА случайный поиск? | По обучающим — 6/8. По отложенным — 4/8 |
| Нужен ли ГА всегда? | Нет: где перебор влезает в 1,5 с, он даёт то же самое |
Три вещи, которые стоит унести:
- Идеальный оракул не делает постановку полной. Компилятор отвечает на вопрос «согласуется ли это с тем, что вы написали». На вопрос «то ли вы написали» он не отвечает и отвечать не может.
- Поиск — прибор для поиска дыр в вашей постановке. Порог 8000 вместо 10000 и тавтологическое условие в правиле — не сбои алгоритма, а точные указания на то, чего в задаче не было сказано.
- Отложенная выборка обязательна и должна быть отложена по-настоящему. Если она влияет на остановку, на выбор ответа с фронта или на настройку параметров — это уже обучающая выборка, и разрыв вы просто перестанете видеть.
Источники
- Deb K., Pratap A., Agarwal S., Meyarivan T. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 2002 — DOI. Недоминируемая сортировка, дистанция скученности и constrained-domination, использованные здесь без изменений.
- Harman M., Jones B. F. Search-Based Software Engineering. Information and Software Technology, 43(14), 2001 — DOI.
- Qi Z., Long F., Achour S., Rinard M. An Analysis of Patch Plausibility and Correctness for Generate-and-Validate Patch Generation Systems. ISSTA 2015 — DOI. Каноническое измерение переобучения под тест-сьют; постановка этой главы — его вариант с идеальным оракулом.
- Smith T., Husbands P., O’Shea M. Fitness Landscapes and Evolvability. Evolutionary Computation, 10(1), 2002 — DOI.
- Gong D., Tian T., Sun X. Fitness Landscape Analysis in Search-Based Software Engineering — обзорная рамка для раздела про ступеньку и склон.
- Arcuri A., Fraser G. Parameter Tuning or Default Values? An Empirical Investigation in Search-Based Software Engineering. Empirical Software Engineering, 18(3), 2013 — DOI. Про то, почему настройка параметров переносится плохо, а вложения в фитнес — хорошо.
Смежные статьи трека: механика ГА — https://courses.digitable.life/post/sbse/03-genetic-algorithms/; Парето, NSGA-II и constrained-domination — https://courses.digitable.life/post/sbse/05-multi-objective/; переобучение под тесты в автоматическом ремонте — https://courses.digitable.life/post/sbse/08-automated-program-repair/; reward hacking и закон Гудхарта в современной практике — https://courses.digitable.life/post/sbse/09-sbse-in-practice/; стоимость оценки и финальная перепроверка победителей — https://courses.digitable.life/post/sbse/12-expensive-fitness/; разделение наборов для настройки и проверки — https://courses.digitable.life/post/sbse/13-tuning-the-search/. Про сам язык исполняемых спецификаций: правила, свойства и порядок — https://courses.digitable.life/post/fts/05-utilities-rules-properties/; примеры как предметные тесты — https://courses.digitable.life/post/fts/06-examples-as-tests/; честная граница автоматической проверки корпуса спек — https://courses.digitable.life/post/fts/22-spec-driven/.
Что дальше
Эта статья замыкает круг, начатый в первой: там было сказано, что фитнес обязан быть детерминированным, дешёвым и различающим. Здесь мы взяли фитнес, который выполняет все три требования идеально, и получили разрыв обучающих и отложенных примеров в 65,5 п.п. на худшей задаче. Требования к фитнесу необходимы и недостаточны — вот, пожалуй, главное, что стоит унести из трека целиком.
Логичные продолжения на портале:
- FTS — исполняемые спецификации — сам язык, который здесь работал оракулом: правила, свойства, примеры, сертификаты и граница того, что проверка ловит.
- Машинное обучение — оценка моделей и переобучение, откуда взяты и разделение выборок, и learning curve.
- Алгоритмы и структуры данных — когда вместо метаэвристики берут точный метод или приближение с гарантией.
- Логика — допущения и области значений: тот самый разбор, из которого выросли проверки структурных дефектов вывода.
Общая карта портала — в дорожной карте.
И последнее, практическое. Если вы собираетесь синтезировать что-нибудь поиском по машинно-проверяемому критерию — спецификации, конфигурации, патчи, схемы, — сделайте три вещи прежде всего остального: отложите половину данных и не трогайте её; закодируйте руками известный правильный ответ и убедитесь, что представление способен его выразить; запустите случайный поиск с тем же бюджетом. Всё остальное из этой главы имеет смысл только после этих трёх шагов.
Следующие две главы берут тот же стенд и ту же задачу синтеза спецификаций и надстраивают над поиском метауровень: сначала уровень настройки параметров, потом уровень управления рабочей областью.
Иерархический каскад: три уровня поиска, делящих один бюджет
