Антагонистический режим: два подагента и явное управление областью поиска

Компромисс между исследованием и использованием проходит через весь трек, и почти везде он управляется косвенно. Вероятность мутации, размер турнира, температура отжига, миграция между островами — всё это ручки, поворот которых сдвигает баланс, но нигде баланс не является предметом отдельного решения. Никто не говорит алгоритму «сейчас расширяемся»; говорят «мутация 0,3», а дальше как выйдет.

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

Постановка, как и в предыдущей статье, взята из диссертационного исследования М. Ф. Зимнурова (специальность 2.3.1). Работа непубличная, цитат здесь нет — только изложение своими словами. Числа автора помечены как его; всё остальное измерено в тех же 100 прогонах, что и в предыдущей главе.

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

Постановка: область, два агента и арбитр

Пусть $\Omega_k \subseteq \mathcal{X}$ — рабочая область поиска на шаге $k$: не всё пространство, а то его подмножество, в котором популяции разрешено находиться. Над областью работают два подагента. Один расширяет, другой сужает:

$$\Omega_{k+1}=\begin{cases}\mathcal{E}(\Omega_k,\xi_k), & \text{если активирован } A^{+},\[2pt] \mathcal{S}(\Omega_k,\zeta_k), & \text{если активирован } A^{-}.\end{cases}$$

Кто из них активируется, решает не расписание и не случай, а арбитр — уровень, который в исходной постановке называется root. Правило выбора записано явно:

$$\pi_k=\arg\max_{\pi\in{A^{+},A^{-}}}\bigl[,\Delta J_k^{(\pi)}-\eta\cdot\Delta C_k^{(\pi)},\bigr]$$

где $\Delta J^{(\pi)}$ — ожидаемый прирост качества от хода агента $\pi$, $\Delta C^{(\pi)}$ — приращение вычислительной стоимости, а $\eta$ — цена этой стоимости. Каждый подагент присылает арбитру пару чисел: сколько он обещает выиграть и во сколько это обойдётся. Арбитр вычитает одно из другого и выбирает.

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

Чем это отличается от адаптивного выбора операторов

Различие тонкое и существенное, потому что схемы выглядят похоже: в обеих есть кандидаты, есть оценка их полезности, есть выбор.

Ключевое — вторая строка. Бандит перераспределяет вероятности между ходами, но множество достижимых точек при этом не меняется: любой геном по-прежнему может быть построен. Здесь меняется именно множество. Сузив область, вы делаете часть решений недостижимыми, и если ответ был там — он потерян до следующего расширения. Это сильный ход, и потому ему нужен явный арбитр, а не статистика по наградам.

Чего в постановке нет

Две вещи стоит назвать сразу, чтобы не выдать нашу конструкцию за авторскую.

Операторы $\mathcal{E}$ и $\mathcal{S}$ в источнике не определены. Они названы и им приписан смысл, но формул для них нет. Всё, что ниже про устройство расширения и сужения, — наша конструкция, и отрицательный результат по ней относится к ней, а не к постановке.

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

Что взято за область в задаче синтеза спецификаций

Область должна быть множеством решений, а не набором настроек. Иначе конструкция схлопнется в ту же настройку параметров, которая в предыдущей главе себя не оправдала.

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

Оценка хода устроена так же, как её описывает автор: каждый подагент получает короткий зонд — прогон поиска в своей предлагаемой области при равном бюджете, — и возвращает две величины. $\Delta J$ — прирост чёткости относительно текущего лучшего. $\Delta C$ — доля обращений к фитнесу, которым потребовался настоящий вызов компилятора; область, порождающая много новых документов, стоит дороже при том же числе обращений, и правило арбитража обязано это видеть. Коэффициент штрафа $\eta$ = 0,1.

Накладные расходы этой руки те же, что у настройки параметров в предыдущей главе: обоим средним уровням отдана одна и та же доля бюджета $\rho$ = 0,25. Сравнение поэтому прямое — два разных способа потратить одинаковые накладные расходы.

Результат

Тот же парный замер: 20 зёрен, восемь задач, 193 600 обращений к фитнесу на прогон каждой руки.

Знаковый тест против одноуровневого поиска по паре «задача × зерно»: по чёткости +21 / −42, $p$ = 0,0111. Значимо хуже базовой линии — как и полный каскад, и по той же причине: накладные расходы среднего уровня, которые нижнему уровню не вернулись.

По трём задачам, которые одноуровневый поиск не решал точной целью, режим тоже ничего не изменил: 0/60 решённых наблюдений против 2/60 у базовой линии. Разброс по зёрнам он снизил слабее, чем простая лестница перезапусков: 1,625 против 1,125 у руки без среднего уровня вовсе.

Всё это ожидаемо после предыдущей главы. Интересное начинается в трассе решений арбитра.

Что на самом деле решал арбитр

Решений за весь замер — 379. Из них расширение выбрано 78 раз, сужение — 301: доля расширений 20,6 %. Перекос сильный, и объясняется он не свойствами задачи, а свойством правила арбитража на нашем ландшафте.

Медиана $\Delta J$ у расширяющего агента — 0,0000, у сужающего — 0,0000. Оба нуля. На плато с иглами короткий зонд почти никогда не улучшает текущий результат, поэтому первое слагаемое правила чаще всего одинаково у обоих кандидатов и равно нулю.

Что остаётся, когда $\Delta J$ одинаков? Остаётся $-\eta\Delta C$, то есть выбор дешёвого. Медианы стоимости: 0,8148 у расширения против 0,7661 у сужения. Сужение систематически дешевле — меньшая область порождает меньше разных геномов, больше попаданий в кэш. Значит, при отсутствии сигнала о качестве правило вырождается в «всегда сужать».

Насколько часто так выходит, считается точно. Ничьих по качеству — таких решений, где $\Delta J$ у обоих подагентов совпал до последнего знака, — 182 из 379, то есть 48,0 %. На ничьей исход не может принять ничто, кроме слагаемого стоимости: первое слагаемое сократилось, выбирать больше нечем.

Вторая, менее точная оценка того же — сколько решений изменилось бы при $\eta = 0$: 175 из 379, то есть 46,2 %. Менее точная она потому, что при $\eta = 0$ ничьи приходится разрешать произвольно, и результат зависит от того, в чью пользу. Смотреть надо на первую величину; вторая приведена, потому что её считают чаще, и полезно видеть, что она даёт близкий ответ.

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

Итог виден и в конечных областях. Медиана предельного числа правил на момент остановки — 7,0 при стартовом значении 8; медиана размера турнира — 4,0 при стартовых 2. Область стабильно ужимается, давление отбора стабильно растёт. Механизм, который должен был чередовать расширение и сужение, свёлся к одностороннему сжатию — и это ровно та динамика, которой боишься, вводя необратимые ходы.

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

Динамика области хорошо видна, если нарисовать её как автомат. Задумывалось так, что оба перехода живые и система ходит между режимами:

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

Диагностика, которую стоит встроить сразу

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

def degeneracy_report(decisions: list[dict], eta: float) -> dict:
    """Насколько решения арбитра определяются качеством, а не ценой.

    decisions — записи вида {"dj_plus", "dj_minus", "dc_plus", "dc_minus", "winner"}:
    по одной на каждое решение, с оценками ОБОИХ кандидатов, включая проигравшего.
    Без проигравшей стороны вопрос «а был ли выбор» не имеет ответа.
    """
    ties = sum(1 for d in decisions if d["dj_plus"] == d["dj_minus"])
    # Кого выбрал бы арбитр без штрафа за стоимость.
    flips = sum(
        1
        for d in decisions
        if ("A+" if d["dj_plus"] >= d["dj_minus"] else "A-") != d["winner"]
    )
    return {
        "решений": len(decisions),
        # Доля решений, где качество кандидатов неразличимо: если она велика,
        # критерий превратился в минимизацию стоимости, и итоговые метрики
        # этого не покажут — покажет только эта строка.
        "ничьих по качеству": ties / len(decisions),
        "изменилось бы при eta=0": flips / len(decisions),
        "eta": eta,
    }

На наших данных ничьих по качеству вышло 48,0 %, изменилось бы при eta=0 — 46,2 %. Порога, выше которого «плохо», в литературе нет, и придумывать его здесь не будем; но величина, при которой почти каждое второе решение принимает не то слагаемое, которое вы считали главным, — повод пересмотреть критерий, а не продолжать замер.

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

Метафора, которую автор убрал

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

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

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

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

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

Что с этим делать

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

Дать $\Delta J$ шкалу, на которой есть градации. Чёткость на плато почти всегда одна и та же, но у той же задачи есть градуированная цель — средняя относительная ошибка вместо точного совпадения. Она даёт склон там, где точная цель даёт ступеньку (глава про исполняемую спецификацию её меряет). Арбитру достаточно наблюдать градуированную величину, даже если приёмка остаётся точной.

Сделать $\eta$ величиной, а не константой. Сейчас штраф фиксирован, и его вес относительно $\Delta J$ никем не проверяется. Разумная форма — нормировать оба слагаемых на их наблюдаемый разброс, чтобы слагаемое без разброса не могло решать исход.

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

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

Границы вывода

Отрицательный результат стоит ровно столько, сколько стоит его область применимости.

• Наш результат относится к нашим $\mathcal{E}$ и $\mathcal{S}$: в источнике они не определены. Другая конструкция расширения и сужения может вести себя иначе.
• Он относится к ландшафту «плато с иглами». Диагноз — «первое слагаемое правила не различает кандидатов» — прямо указывает, что на непрерывном информативном фитнесе будет иначе.
• Он относится к режиму общего бюджета, где средний уровень платит за себя. При отдельном бюджете арбитра выводы предыдущей главы про накладные расходы не действуют, и остаётся только вопрос про вырождение правила.
• Восемь задач одного класса, 20 зёрен. Этого хватает, чтобы увидеть перекос в 20,6 % расширений, и не хватает, чтобы утверждать что-либо о задачах другого вида.

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

Как воспроизвести

node --test test/cascade.test.mjs      # включая тесты на E, S и на правило (2.26)
node src/run.mjs paired --seeds 20 --workers 16 --budget 24200
node src/report.mjs

Два теста относятся именно к этому режиму и стоят упоминания, потому что закрывают два способа обмануть себя. Первый проверяет, что $\mathcal{E}$ и $\mathcal{S}$ двигают область в противоположные стороны и не выходят за границы при многократном применении. Второй — что записанный в трассу выбор арбитра действительно совпадает с $\arg\max$ по формуле, а не с чем-то похожим: в трассу пишутся обе оценки, и тест пересчитывает решение из них.

Полная трасса решений арбитра лежит в сыром файле прогона: по каждому решению записаны $\Delta J$ и $\Delta C$ обоих подагентов, победитель и получившаяся область. Доля решений, изменившихся бы при $\eta = 0$, считается из этих же записей, а не из отдельного прогона.

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

1. Считать выбор области тем же, что выбор оператора. Оператор перераспределяет вероятности, область меняет множество достижимых решений. Второе необратимо в пределах шага и потому требует более осторожного правила.
2. Вводить критерий «выигрыш минус стоимость», не проверив разброс выигрыша. Если первое слагаемое чаще всего одинаково, критерий превращается в минимизацию стоимости, и вы этого не заметите по итоговым метрикам — только по трассе решений.
3. Не логировать оценки обоих кандидатов. Победитель без проигравшего не даёт понять, почему решение было таким. Половина выводов этой статьи получена именно из чисел проигравшей стороны.
4. Разрешать одностороннее сжатие без нижней границы. Область, ужимающаяся монотонно, рано или поздно отрежет ответ, и поиск после этого будет выглядеть сошедшимся.
5. Достраивать недостающие части постановки молча. Если в источнике оператор назван, но не определён, ваша реализация — ваша ответственность, и отрицательный результат относится к ней.
6. Добирать руки эксперимента после того, как основной вывод получен. Это подбор конфигурации до красивой картинки, даже если каждый отдельный прогон честен.
7. Заполнять отсутствующее сравнение догадками. Если у источника нет чисел по механизму, так и надо написать.

Мини-итог

• Антагонистический режим ставит компромисс исследование/использование как явное решение арбитра по паре «прирост качества, приращение стоимости» — этим он отличается от всех косвенных ручек трека.
• Он меняет множество достижимых решений, а не распределение над операторами; это делает его сильнее адаптивного выбора операторов и опаснее его.
• На нашей задаче при равном бюджете он значимо хуже одноуровневого поиска, ровно как и каскад с настройкой параметров, и по той же причине — накладные расходы среднего уровня.
• Правило арбитража выродилось: приросты качества у обоих подагентов почти всегда одинаковы и равны нулю, поэтому исход решает штраф за стоимость, а он систематически на стороне сужения.
• На 48,0 % решений качество кандидатов было неразличимо, и выбирать могла только цена — величина, которая ставит диагноз лучше любой итоговой метрики.
• Механизм отказа локален и указывает, что чинить: шкалу $\Delta J$, нормировку слагаемых и запрет на необратимое сжатие. Мы это не проверяли и помечаем как гипотезы.

Источники

• Зимнуров М. Ф. «Оптимизация итеративных методов управления разработкой программного обеспечения с использованием генетических алгоритмов», диссертация на соискание учёной степени кандидата технических наук, специальность 2.3.1, 2025. Источник постановки антагонистического двухагентного режима под root-управлением. Работа непубличная; в защищаемой версии режим отнесён к дальнейшим направлениям.
• Fialho, Da Costa, Schoenauer, Sebag. «Analyzing bandit-based adaptive operator selection mechanisms», Annals of Mathematics and AI, 2010 — ближайший родственник схемы и точка, от которой она отличается.
• Eiben, Hinterding, Michalewicz. «Parameter control in evolutionary algorithms», IEEE TEC 1999 — куда режим попадает в классификации управления.
• Črepinšek, Liu, Mernik. «Exploration and exploitation in evolutionary algorithms: a survey», ACM Computing Surveys, 2013 — обзор того самого компромисса, который здесь пытались сделать управляемым.
• Auer, Cesa-Bianchi, Fischer. «Finite-time analysis of the multiarmed bandit problem», Machine Learning, 2002 — UCB1; альтернатива явному арбитру.

Смежные статьи трека: иерархический каскад, настройка поиска, исполняемая спецификация как фитнес, генетические алгоритмы.

Что дальше

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

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

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

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