Каскад GA0 → GA1 → GA2: разделение уровней поиска

В главе про настройку поиска мета-уровень появился как инструмент: настроить параметры гонками, поменять оператор бандитом. Здесь тот же мета-уровень рассматривается как архитектурное решение, у которого есть цена и проверяемая польза.

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

Проблема: три функции в одном цикле

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

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

Это не эстетическая претензия. Смешение уровней даёт две конкретные потери.

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

Потеря воспроизводимости. Число поколений подобрано «на глаз» под ноутбук разработчика. На сервере CI прогон успевает больше, на нагруженной машине — меньше. Результат зависит от быстродействия среды, и сравнение двух версий алгоритма перестаёт что-либо значить.

Что делает каждый уровень

GA2 — поиск. Хромосома $A=(a_1,\ldots,a_n)$ задаёт исполнителя каждой задачи. По ней детерминированно строится расписание и вычисляется свёртка $J_p$. Это единственное место, где происходит поиск: турнирная селекция, элита, кроссовер, мутация — всё то, что разбиралось в главе про генетические алгоритмы.

GA1 — выбор конфигурации. Три заранее заданные конфигурации: compact $(32; 0{,}06; 0{,}80)$, balanced $(48; 0{,}10; 0{,}82)$, exploratory $(64; 0{,}18; 0{,}85)$. Каждая получает короткий пилот, побеждает та, у которой $\theta^*=\arg\min_{\theta\in\Theta}J_p(X_{pilot}(\theta))$; при равенстве — меньшая популяция. Обратите внимание: отдельной мета-целевой функции нет. Конфигурация оценивается тем же $J_p$, которым меряется план, и это сознательно — новая функция качества на верхнем уровне означала бы новый источник расхождений.

GA0 — управление бюджетом. Проверяет показатель готовности $c$ после каждого поколения финального GA2 и останавливает расчёт при $N^*=\min{N\leq N_{max}\mid c(N)\geq c_{min}}$.

Итог разделения автор формулирует так:

GA0 не изменяет функцию качества, GA1 не получает бесплатной калибровки, а GA2 остается единым механизмом поиска для парного сравнения.

Бюджет как явная величина

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

Число оценок увеличивается ровно на размер новой популяции. Это делает бюджет сопоставимым между разными конфигурациями и менее зависимым от быстродействия вычислительной среды.

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

Стоимость пилота включается в общий $N_{max}$ и не скрывается при сравнении.

В исполняемом примере это видно арифметически. При $N_{max} = 1200$ каждый из трёх пилотов получает 128 оценок — не меньше 128 и около 8 % общего бюджета. Итого 384 оценки уходят на выбор конфигурации, и на финальный поиск остаётся 816 против 1200 у одноуровневого режима. Каскад обязан отыграть эту разницу качеством конфигурации, иначе он проигрывает.

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

Готовность — не то же самое, что качество

Показатель готовности GA0 устроен так:

$$ c=0{,}25(1-\Delta)+0{,}35S+0{,}30I+0{,}10Q, $$

где $S$ — устойчивость лучшего значения в окне из пяти поколений, $I$ — улучшение относительно начального плана, $Q$ — отделимость лучшего решения от медианного, $\Delta$ — штраф нарушений. Все компоненты лежат в $[0;1]$.

Обратите внимание, чего в этой формуле нет: самого $J_p$. Готовность отвечает на вопрос «поиск ещё движется или уже стоит?», а не на вопрос «план хороший?». Смешивать их нельзя:

Порог $c_{min}$ определяет только право ранней остановки; он не гарантирует оптимальность и не заменяет $J_p$.

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

Связь с самоадаптивными метаэвристиками

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

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

То есть отличие от привычной гиперэвристики — не в GA1, а в GA0. Селектор операторов, адаптивное управление параметрами и racing из главы 13 решают, как искать. Ни один из них не решает, когда прекратить, — обычно это внешний параметр «число поколений». В контуре поддержки решений, который обязан ответить до конца планёрки, момент остановки перестаёт быть внешним параметром и становится уровнем схемы.

Оговорка, которую автор ставит рядом с описанием каскада, стоит того, чтобы её процитировать:

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

Что показал стенд

Учебная реализация каскада лежит в examples/sbse/: пять режимов, 30 экземпляров на размерность, одинаковый бюджет 1200 оценок, парные экземпляры. Фактический вывод node examples/sbse/bench.mjs на размерности M (100 задач, 10 исполнителей):

| Режим         | Медиана J_p | Q1–Q3         | Оценок (медиана) | Допустимых | Ранних остановок |
| ------------- | ----------: | ------------: | ---------------: | ---------: | ---------------: |
| greedy        | 0.0664      | 0.0631–0.1034 | 1                | 80 %       | 0/30             |
| random_repair | 0.1221      | 0.1096–0.1450 | 1200             | 0 %        | 0/30             |
| ga_single     | 0.0664      | 0.0631–0.1012 | 1200             | 70 %       | 0/30             |
| ga1_ga2       | 0.0636      | 0.0609–0.0956 | 1184             | 50 %       | 0/30             |
| ga0_ga1_ga2   | 0.0657      | 0.0622–0.0963 | 512              | 67 %       | 29/30            |

| Режим         | Δ медианы J_p | Â₁₂   | Эффект    | p       | p (Холм) | Вывод                |
| ------------- | ------------: | ----: | --------- | ------: | -------: | -------------------- |
| greedy        | +0.0000       | 0.479 | ничтожный | 0.7844  | 1.0000   | различия не показано |
| random_repair | +0.0484       | 0.114 | большой   | <0.0001 | <0.0001  | различие есть        |
| ga1_ga2       | -0.0024       | 0.611 | малый     | 0.1412  | 0.4237   | различия не показано |
| ga0_ga1_ga2   | +0.0000       | 0.533 | ничтожный | 0.6627  | 1.0000   | различия не показано |

Три вывода, и ни один из них не звучит как реклама схемы.

Надстройка над GA2 не показала преимущества по качеству. После поправки Холма $p$ равно единице. Разделение уровней окупается интерпретируемостью, а не процентами $J_p$, — и на этом бюджете не окупается вовсе. В диссертации есть ровно такой же результат по независимой калибровке: «метауровень не считается полезным только по факту его наличия».

Устойчивый эффект — экономия бюджета. ga0_ga1_ga2 тратит 512 оценок вместо 1200 при неотличимой медиане $J_p$. Это тот показатель, который переносится между машинами, в отличие от секунд.

Жадный алгоритм не отличим от эволюционного поиска на M. Бюджета в 1200 оценок при 100 задачах не хватает, чтобы улучшить конструктивный план. Вывод относится к этому бюджету и этой размерности, а не к генетическим алгоритмам вообще — и это стандартная ошибка чтения таких таблиц.

Границы утверждений

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

Числа из examples/sbse/ — тем более учебные: одна размерность задачи, один класс сценариев, ни точного решателя, ни сравнения с NSGA-II, ни отложенной калибровки.

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

1. Дать метауровню бесплатный бюджет. Пилоты считаются отдельно от «основного» прогона — и каскад выигрывает у одноуровневого режима на ровном месте.
2. Завести отдельную функцию качества на верхнем уровне. Тогда непонятно, чей оптимум вы получили: планировщика или его настройщика.
3. Мерить бюджет в поколениях. Конфигурация с популяцией 64 получает вдвое больше оценок, чем с популяцией 32, при «одинаковом» числе поколений.
4. Мерить бюджет в секундах. Результат становится характеристикой машины.
5. Считать порог остановки критерием качества. $c \geq c_{min}$ — право остановиться, а не утверждение о плане.
6. Проверять готовность с первого поколения. Окно устойчивости из пяти поколений существует именно потому, что на второй итерации «стабильно» означает «ещё не начало двигаться».
7. Настраивать порог на тех же данных, на которых отчитываетесь. Ровно то переобучение мета-уровня, о котором предупреждает глава 13.
8. Считать, что уровней должно быть три. Три — потому что в этой задаче три вопроса: какой план, какими параметрами искать, когда остановиться. Появится четвёртый вопрос — появится уровень; не появится — не надо.

Мини-итог

• Смешение поиска, настройки и остановки в одном цикле не ломает алгоритм, но лишает возможности понять, что именно пошло не так.
• Каскад разделяет ответственность: GA2 ищет план, GA1 выбирает конфигурацию по короткому пилоту, GA0 решает, когда прекратить.
• Бюджет измеряется в оценках целевой функции и включает стоимость пилота. Настройка не бесплатна.
• Показатель готовности отвечает на вопрос «поиск ещё движется?», а не «план хороший?»; порог даёт право остановиться и ничего не гарантирует.
• В учебном стенде разделение уровней не улучшило $J_p$ статистически значимо, но дало устойчивую экономию бюджета — 512 оценок вместо 1200 при неотличимом качестве.
• Полезность каждого уровня проверяется экспериментом, а не тем, что уровень существует.

Источники

• Зимнуров М. Ф. Иерархическая многокритериальная оптимизация плана назначения в СППР: модель, каскад GA0→GA1→GA2 и воспроизводимый эксперимент в курсе системного анализа // Образование и наука: современный вектор развития: материалы V Национальной научно-практической конференции. — Керчь, 2026. — С. 48–54.
• Зимнуров М. Ф., Астраханцева И. А. Построение API для систем отслеживания задач // Современные наукоемкие технологии. Региональное приложение. — 2024. — № 4 (80). — С. 97–103. — DOI 10.6060/snt.20248004.00013.
• Зимнуров М. Ф. Разработка интерфейса по метрике загруженности сотрудников // Известия высших учебных заведений. Серия: Экономика, финансы и управление производством. — 2024. — № 4 (62). — С. 82–87. — DOI 10.6060/ivecofin.2024624.705.
• Зимнуров М. Ф., Астраханцева И. А., Грименицкий П. Н. Системный анализ и оптимизация количественных показателей эффективности в технологических проектах на основе гибких методологий // Современные наукоемкие технологии. Региональное приложение. — 2023. — № 3 (75). — С. 61–68. — DOI 10.6060/snt.20237503.0008.
• Eiben A. E., Hinterding R., Michalewicz Z. «Parameter control in evolutionary algorithms», IEEE TEC 1999 — классификация tuning/control, на которую опирается уровень GA1.
• Karafotias G., Hoogendoorn M., Eiben A. E. «Parameter control in evolutionary algorithms: trends and challenges», IEEE TEC 2015.
• Burke E. K. et al. «Hyper-heuristics: a survey of the state of the art», JORS 2013 — барьер домена и место GA1 в этой таксономии.

Что дальше

Каскад — это ответ на вопрос «как устроить поиск». Но все выводы этой главы держатся на другом: на том, что 300 прогонов можно повторить и получить те же числа, что критерий выбран до эксперимента, а не после, и что «различия не показано» пишется так же спокойно, как «различие есть».

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