Методы оптимизации

Методы

Метод	Класс	Группа в списке	Воспроизводим	Стартовая точка	Этап конвейера	Страница
Глобальный → локальный	связка	с дожимом	да	используется	—	pipeline
Доверительная область (BOBYQA)	локальный	локальные	да	используется	локальный	bobyqa
Симплекс (SBPLX)	локальный	локальные	да	используется	локальный	sbplx
Поиск с ограничениями (COBYLA)	локальный	локальные	да	используется	локальный	cobyla
Систематический глобальный (DIRECT-L)	глобальный	глобальные	да	игнорируется	глобальный	directl
Управляемый случайный поиск (CRS2)	глобальный	глобальные	при фиксированном зерне	используется	глобальный	crs2
Мультистарт (MLSL)	глобальный	с дожимом	да	используется	глобальный	mlsl
Адаптивная эволюция (ISRES)	глобальный	глобальные	при seed ≠ 0	используется	глобальный	isres
Эволюционная стратегия (ESCH)	глобальный	глобальные	при seed ≠ 0	используется	глобальный	esch
Адаптивный глобальный (MaxLIPO)	глобальный	глобальные	да	используется	глобальный	maxlipo
Ковариационная адаптация (CMA-ES)	глобальный	глобальные	при seed ≠ 0	используется	глобальный	cmaes

Колонка «Стартовая точка» говорит, участвует ли текущая геометрия в прогоне. «Используется» не значит «нужна»: у популяционных методов (CRS2, ISRES, ESCH, CMA-ES) она становится первой особью популяции, поэтому итог прогона не бывает хуже текущей конструкции, но и без хорошего старта они работают. Единственный метод, который её действительно игнорирует, — Систематический глобальный (DIRECT-L): он делит всю область и стартовой точки не имеет.

Колонка «Этап конвейера» говорит, каким этапом метод можно выбрать в связке Глобальный → локальный (поля Глобальный этап / Локальный этап); сам конвейер этапом быть не может. Подробно — см. Какие методы доступны как этапы. Воспроизводимость конвейера полная независимо от выбора этапов: этап работает с зерном по умолчанию, а поле Seed страницы метода на этап не влияет.

Список методов в диалоге разбит на три группы с заголовками и разделителями: Локальные (спуск от текущей геометрии), Глобальные (поиск по всему диапазону) и С дожимом — методы, которые сами доводят найденную точку локальным спуском. Порядок групп фиксирован, заголовок и разделитель выбрать нельзя. Мультистарт (MLSL) по природе поиска остаётся глобальным методом, но в списке стоит в группе «С дожимом», потому что запускает локальный спуск в каждом найденном бассейне.

Совместимость метода с задачей (подвал диалога)

В подвале диалога, над кнопками OK / Отмена, показано информационное сообщение о том, насколько выбранный метод подходит к текущим целям и переменным. Первая строка — сводка задачи, например Переменные: 5 (дискретных: 2), Цели: 3 (ограничений: 1, экстремумов: 1). Уточнения в скобках печатаются только тогда, когда есть что уточнять: у задачи без дискретных осей, без ограничений и без экстремальных целей строка короче. Ниже — список замечаний с префиксом уровня:

Уровень	Что означает
Несовместимо	метод не умеет то, что требует задача (например, жёсткие ограничения) — расчёт пойдёт, но требование будет обойдено
Предупреждение	метод применим, но условия для него неблагоприятны (локальный метод без стартовой точки)
Примечание	метод отработает, но неэффективно (дискретные оси, размерность вне рекомендуемого диапазона, бюджет меньше одной популяции, выключенный порог стагнации у метода без собственной сходимости)

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

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

Сообщение носит рекомендательный характер и никогда не блокирует кнопку OK. Оно пересчитывается на лету при смене метода, агрегации, пресета и этапов связки, а также при изменении бюджета и размера популяции. Тот же набор замечаний повторяется в журнале решателя при старте расчёта (предстартовый отчёт), поэтому подвал — это ранний показ того, что раньше было видно только после запуска.

Как выбрать метод

Ситуация	Рекомендация
Есть готовая конструкция, нужно уточнить	Доверительная область; при агрегации «худшая точка» — Симплекс
Широкие диапазоны параметров, оптимум неизвестен	Глобальный → локальный, пресет «Авто»
Много параметров (n > 8)	Глобальный → локальный (этап 1 — CRS2 при n ≤ 16, ISRES выше)
Максимизация КПД при жёсткой маске КСВН	Поиск с ограничениями (цели-ограничения)
Малый бюджет расчётов, глобальный поиск без настройки	Адаптивный глобальный (MaxLIPO)
Изрезанный ландшафт средней размерности (n≈10–40)	Ковариационная адаптация (CMA-ES)
Нужна полная воспроизводимость прогона	Любой метод; CRS2 — с фиксированным зерном; ISRES, ESCH и CMA-ES — при зерне ≠ 0
Глобальный поиск при жёстких ограничениях	Адаптивная эволюция (ISRES)
Преемственность со старыми проектами	Отдельного действия не требуется: сохранённый метод «Генетический алгоритм» считается через Адаптивную эволюцию (ISRES), файл проекта не переписывается

Общие параметры (группа Общие, видна при любом методе)

Параметр	По умолчанию	Влияние
Допуск цели	0,001	останов при F ≤ допуска: цели «практически выполнены». 0 — работать до точного выполнения либо исчерпания бюджета. Действует только для набора из одних порогов (Меньше / Больше / Равно): если в наборе есть цель «Минимизировать» или «Максимизировать», порога у F больше нет и это поле на останов не влияет — см. «Критерии останова» ниже
Агрегация по полосе	Сглаженный максимум (по умолчанию)	как штрафы по частотным точкам полосы сворачиваются в одно число; определяет и допустимый выбор метода — см. Цели и целевая функция
Свёртка целей	Сумма	как вклады разных целей объединяются в одно значение F: Сумма (взвешенное среднее) или Минимакс (наихудшая цель) — см. Цели и целевая функция

Бюджет расчётов задаётся на странице каждого метода (поле Бюджет расчетов (0 = авто); 0 = авто: max(50, 20·n)) — это жёсткий предел числа расчётов модели и главный регулятор «время ↔ качество». Стартовая точка — текущая геометрия; используется локальными методами, Мультистартом и конвейером.

Стартовый рапорт совместимости (preflight)

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

Каждый совет имеет уровень:

Уровень	Смысл
Несовместимо	метод не поддерживает нужную возможность; результат будет получен в обход (например, ограничения свёрнуты в штраф)
Предупреждение	возможна пониженная надёжность; стоит рассмотреть другой метод
Примечание	пояснение или совет по эффективности

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

Проверяемые условия:

1. Заданы ограничения, а метод их не поддерживает — цели-ограничения свёрнуты в целевую функцию как взвешенные штрафы (Несовместимо).
2. Выбран локальный метод, но пригодной стартовой точки нет — надёжнее может оказаться глобальный метод (Предупреждение).
3. В задаче есть дискретные оси (переменные «с шагом» / «список»), а метод плохо с ними работает — сходимость по таким осям может быть медленной (Примечание).
4. Переменных меньше рекомендованного для метода диапазона (Примечание).
5. Переменных больше рекомендованного для метода диапазона (Примечание).
6. Есть цели «минимизировать» / «максимизировать» при бюджете расчётов менее 50 — метод может не сойтись, стоит увеличить бюджет (Примечание).
7. Бюджет расчётов меньше одной популяции метода — популяционный метод не успевает завершить и одно поколение; увеличьте бюджет либо уменьшите размер популяции (Примечание).
8. У метода нет собственного критерия сходимости, а порог остановки без улучшения выключен — прогон израсходует весь бюджет даже после того, как перестанет улучшаться; порог задаётся полем Останов без улучшения (0 = выкл) на странице метода (Примечание). Это состояние «из коробки» у методов DIRECT-L, ESCH, MaxLIPO и MLSL — см. «Какой критерий есть у какого метода».

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

Критерии останова (в порядке приоритета)

1. Исчерпан бюджет расчётов.

2. Все цели выполнены — только если в наборе нет целей «Минимизировать» / «Максимизировать».

   Предмет сравнения — наихудшая выборка полосы M_g каждой пороговой цели: цель выполнена, когда M_g ≤ «Допуска достижения цели», и прогон закрывается, только когда это верно у всех пороговых целей сразу. Сравнение целевой функции с допуском (F ≤ допуска) отменено: F — свёртка агрегатов, а агрегат узкого нарушения лежит много ниже собственной наихудшей выборки, поэтому малое F ничего не говорит о выполнении целей.

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

   Проверку делает менеджер оптимизации, поэтому она одинакова у всех методов: движку порог достижения цели не передаётся вовсе — движок видит только F.

   Оговорка для метода «Адаптация ковариации (CMA-ES)». У него проверка выполняется раз в поколение, а не после каждого расчёта, поэтому прогон может перескочить момент выполнения цели на λ−1 расчётов, где λ = 4 + ⌊3·ln n⌋ — размер поколения при n переменных (при заданной вручную популяции — на «популяция − 1»). Это единицы расчётов и на результат не влияет; чтобы прогон дошёл хотя бы до первой проверки, бюджет должен покрывать не менее трёх поколений.

3. Достигнута точность по параметрам (локальные методы, а также CRS2 и ISRES — поле Tolerance на их страницах). У Мультистарта (MLSL) такое же поле есть, но оно останавливает отдельный локальный спуск, а не прогон.

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

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

5. Остановка пользователем — лучшая найденная точка сохраняется.

6. Отказ вложенного метода — только у Мультистарта (MLSL). Устройство метода таково, что отказ очередного локального спуска завершил бы весь прогон, и для этого случая есть отдельный статус. На практике он не наблюдается: локальные спуски заканчиваются штатно (по своей точности либо по своему бюджету), и прогон MLSL расходует бюджет целиком. См. Мультистарт.

Оговорка про наборы с экстремальными целями

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

Практическое следствие: если в наборе есть экстремальная цель, а выбранный метод — «Систематический глобальный (DIRECT-L)», «Эволюционная стратегия (ESCH)», «Адаптивный глобальный (MaxLIPO)» или «Мультистарт (MLSL)», то без порога стагнации прогон израсходует весь бюджет, даже когда улучшения давно нет. Диалог метода и журнал предупреждают об этом отдельной подсказкой; порог задаётся полем Останов без улучшения (0 = выкл) на странице метода. Единственное исключение — Мультистарт: его прогон может закончиться раньше из-за отказа локального спуска (пункт 6 выше).

Какой критерий есть у какого метода

Порог «все цели выполнены» (F ≤ допуска) поддерживают ВСЕ методы — при наборе из одних порогов. Различаются они собственной сходимостью:

Метод	Бюджет	Цель (F ≤ допуска)	Собственная сходимость	Порог стагнации
Доверительная область (BOBYQA)	да	да	да — точность по параметрам	да
Симплекс (SBPLX)	да	да	да — точность по параметрам	да
Поиск с ограничениями (COBYLA)	да	да (в допустимой точке)	да — точность по параметрам	нет
Систематический глобальный (DIRECT-L)	да	да	нет (формально критерий есть, но требует дробления всей области — недостижимо на реальных бюджетах)	да
Управляемый случайный поиск (CRS2)	да	да	да — точность по параметрам	да
Мультистарт (MLSL)	да	да	нет (точность по параметрам ограничивает каждый локальный спуск, а не серию: сошедшийся спуск лишь запускает следующий)	да
Глобальный → локальный (конвейер)	да	да	да — когда все локальные спуски сошлись	у глобального этапа задаётся конвейером автоматически
Адаптивный глобальный (MaxLIPO)	да	да	нет	да
Ковариационная адаптация (CMA-ES)	да	да (проверяется раз в поколение)	да — собственные критерии CMA-ES, затем рестарты	нет
Адаптивная эволюция (ISRES)	да	да (в допустимой точке)	да — точность по параметрам	нет
Эволюционная стратегия (ESCH)	да	да	нет	да

Поле «Останов без улучшения» есть не у всех методов: его заводят там, где собственной сходимости нет (DIRECT-L, ESCH, MaxLIPO, MLSL) либо где полезна страховка от «топтания» локального спуска (BOBYQA, SBPLX) и стагнации популяции (CRS2). У COBYLA и ISRES поля нет намеренно: оба останавливаются по своей точности по параметрам (поле Точность), а CMA-ES располагает собственным набором критериев сходимости и рестартами.

Отмена пользователем работает у всех методов и всегда сохраняет лучшую найденную точку.

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

Отказы расчёта

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