Мультистарт

Материал из MachineLearning.

Версия от 05:36, 17 июля 2026; Aleksandr Iakovlev (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM GPT-5.6 Sol xhigh и проверено участником Aleksandr Iakovlev 09:36, 17 июля 2026 (MSD)

Содержание

1 Определение и мотивация
2 Формальная схема
3 Вероятность попадания в область притяжения
4 Стратегии генерации стартов
5 Критерии остановки
6 Повторные минимумы и кластеризация
7 Адаптивный и многоуровневый мультистарт
8 Псевдокод
9 Численный пример
10 Параллельная реализация
11 Преимущества и ограничения
12 Отличие от близких подходов
13 См. также
14 Литература

Мультистарт (англ. multistart, multi-start; простейший случай — random restart, случайный перезапуск) — метаалгоритмическая схема поиска решения, в которой локальный алгоритм многократно запускают из различных начальных точек, а затем выбирают лучшее из полученных решений. В непрерывной невыпуклой оптимизации мультистарт превращает быстрый локальный метод в вероятностную эвристику глобального поиска. Он не делает локальный метод глобальным и, при конечном числе запусков, обычно не даёт сертификата глобальности.

Термин охватывает и независимые перезапуски без памяти, и схемы с отбором стартов, кластеризацией или адаптацией. Свойства последних нельзя приписывать простому random restart.^[1]

Определение и мотивация

Пусть требуется решить задачу

$f_* = \min_{x\in D} f(x), \qquad D\subseteq {\mathbb R}^d,$

где допустимая область $D$ может содержать ограничения, а функция $f$ имеет несколько локальных минимумов. Локальный решатель $L$ по начальной точке $x$ возвращает найденную точку $L(x)$ либо сообщение о неудаче. Результат зависит от старта: разные точки могут попадать в разные области притяжения.

Мультистарт распределяет бюджет между несколькими областями и полезен, когда локальная оптимизация сравнительно дешева, но чувствительна к инициализации. Классические развитые варианты объединяют выборку, локальный поиск и кластеризацию.^[1]

Формальная схема

Базовый алгоритм состоит из трёх стадий: генерация стартов — локальная оптимизация — выбор решения. Пусть $x_1,\ldots,x_m$ сгенерированы по распределению $q$ на $D$ . Для каждого старта вычисляют

$y_i=L(x_i), \qquad v_i=f(y_i).$

Неудачные и недопустимые результаты исключают. Выходом служит

$i_*\in\arg\min_{i:\,y_i\in D} v_i,\qquad \widehat x=y_{i_*}.$

Для поиска нескольких минимумов возвращают классы различных решений. Локальный решатель может быть градиентным или безградиентным, например методом Нелдера—Мида. Для сравнимости запусков фиксируют критерии допустимости и точности; при шуме нужны повторные оценки или статистическое сравнение.

Вероятность попадания в область притяжения

Для фиксированного локального алгоритма областью притяжения минимума $x^{(j)}$ назовём

$B_j=\{x\in D: L(x)=x^{(j)}\}.$

Границы областей зависят не только от $f$ , но и от реализации решателя, ограничений и допусков. Если старты независимы и одинаково распределены по $q$ , а вероятность попасть в область глобального минимума равна

$p=\Pr_q\{x\in B_*\}=\int_{B_*}q(x)\,dx,$

то вероятность хотя бы одного успешного попадания после $m$ запусков составляет

$P_m=1-(1-p)^m.$

Чтобы получить вероятность успеха не меньше $1-\delta$ , достаточно

$m\geq\left\lceil\frac{\ln\delta}{\ln(1-p)}\right\rceil.$

При малом $p$ используется приближение $m\approx \ln(1/\delta)/p$ . Например, при известной нижней оценке $p\geq0{,}01$ для доверия 0,95 требуется не менее 299 независимых стартов.

На практике $p$ обычно неизвестно. Частое повторное нахождение одного минимума оценивает распространённость уже найденной области, но не доказывает отсутствие более узкой и лучшей области. Формула применима только при независимых стартах и корректном распределении $q$ ; для латинского гиперкуба и детерминированных квазислучайных последовательностей биномиальная формула без дополнительного обоснования неприменима.

Стратегии генерации стартов

Независимые случайные точки

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

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

Квазислучайные последовательности

Последовательности низкого расхождения, например последовательность Соболя, стремятся равномернее заполнять гиперкуб. Их применяют и в QMC-вариантах MLSL.^[1] Это улучшает покрытие, но не гарантирует попадания в узкую область. Для статистических оценок используют независимо рандомизированные варианты.

Латинский гиперкуб

В латинском гиперкубе диапазон каждой координаты делят на $m$ равновероятных слоёв, используя по одному значению из каждого; сочетания слоёв переставляют.^[1] Это стратифицирует одномерные проекции, но не все многомерные сочетания. Отбрасывание недопустимых точек нарушает стратификацию.

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

Критерии остановки

Остановка может задаваться одним или несколькими условиями:

исчерпан лимит локальных запусков, вычислений $f$ , времени или памяти;
достигнуто заранее известное целевое значение $f_{\rm target}$ с требуемой допустимостью;
в последних $r$ запусках или пакетах лучшее значение не улучшилось более чем на $\varepsilon_f$ ;
при обоснованной нижней оценке $p_0$ выполнено $1-(1-p_0)^m\geq1-\delta$ ;
в кластерной схеме несколько пакетов не дают новых классов минимумов, а её собственный теоретический или статистический критерий выполнен.

Стагнация и повторы — не сертификаты глобальности. Классические методы предлагали модельно-зависимые доверительные и байесовские правила,^[1] справедливые только при их предположениях. Лучшее решение можно затем «довести» строгими локальными допусками.

Повторные минимумы и кластеризация

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

$\|y_i-y_j\|\leq\varepsilon_x(1+\max(\|y_i\|,\|y_j\|)),$

$|f(y_i)-f(y_j)|\leq\varepsilon_f(1+\max(|f(y_i)|,|f(y_j)|)).$

Учитывают масштабы координат и известные симметрии. Большие допуски сливают разные минимумы, малые создают дубли. Поскольку близость может быть нетранзитивна, явно задают правило кластеризации, например связные компоненты графа близости.

Удаление дублей после локальной оптимизации экономит память и упрощает отчёт, но не возвращает уже потраченные вычисления. Кластерные методы группируют перспективные стартовые точки до локального поиска и запускают решатель только из представителей предполагаемых областей. Именно это, а не базовый random restart, снижает число повторных локальных запусков. Ранние стохастические кластерные схемы систематизированы в классических работах Rinnooy Kan и Timmer.^[1]

Адаптивный и многоуровневый мультистарт

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

$q_t(x)=(1-\lambda_t)q_0(x)+\lambda_t\widetilde q_t(x),$

где $q_0$ покрывает всю допустимую область, а $\widetilde q_t$ концентрируется по накопленным данным. Конкретные гарантии зависят от правил адаптации; само слово «адаптивный» их не обеспечивает.

Метод многоуровневых одиночных связей (multi-level single linkage, MLSL) на уровне $k$ добавляет пакет случайных точек к накопленной выборке, рассматривает лучшую её долю и применяет локальный поиск только к точкам, рядом с которыми нет точки с меньшим значением $f$ или уже найденного минимума. Критический радиус связи уменьшается при росте общего числа $n$ точек в масштабе

$r_n=C\left(\frac{\log n}{n}\right)^{1/d},$

где константа зависит от объёма области и параметров алгоритма. Большой радиус на ранних уровнях подавляет очевидные повторы; уменьшение радиуса позднее позволяет исследовать более мелкие области. При условиях исходной теории — компактной области, равномерной независимой выборке, регулярности функции и локального алгоритма, конечном числе изолированных минимумов — MLSL обладает вероятностными результатами полноты и избегает бесконечного числа повторных локальных поисков. Это асимптотическое утверждение при предположениях, а не гарантия обнаружения глобального минимума за заранее заданное конечное время.^[1]

Развитый кластерный алгоритм GLOBAL также сочетает выборку, отбор лучших точек, кластеризацию и локальный поиск для ограниченных задач с «чёрным ящиком».^[1] Его устройство и экспериментальные свойства не следует считать свойствами простого независимого перезапуска.

Псевдокод

вход: f, допустимая область D, локальный решатель L,
      генератор стартов G, бюджет m, допуски eps_x и eps_f
S := пустое множество классов решений
для i = 1,...,m:
    x := следующая точка G в D
    (y, status) := L(f, D, x)
    если status неуспешен или y недопустима: продолжить
    если y близка к классу C из S:
        обновить представителя C, если f(y) меньше
    иначе:
        добавить новый класс с представителем y
    если выполнен критерий остановки: прервать цикл
если S пусто: сообщить о неудаче
иначе: вернуть представитель с наименьшим f и таблицу S

В базовом random restart шаг объединения классов необязателен и выполняется только для отчёта. В кластерном или адаптивном варианте генератор $G$ и решение о запуске $L$ заменяются правилами соответствующего метода.

Численный пример

Рассмотрим функцию на отрезке $[-2,2]$ :

$f(x)=x^4-2x^2+0{,}3x.$

У неё два локальных минимума: глобальный $x\approx-1{,}03558$ , $f(x)\approx-1{,}30543$ , и неглобальный $x\approx0{,}96015$ , $f(x)\approx-0{,}70585$ . Между ними находится локальный максимум $x\approx0{,}07543$ . Для идеализированного локального поиска по градиентному потоку этот максимум разделяет области притяжения.

Старт $x_0$	Результат локального поиска	Значение $f$
$-1{,}5$	$-1{,}03558$	$-1{,}30543$
$-0{,}5$	$-1{,}03558$	$-1{,}30543$
$0$	$-1{,}03558$	$-1{,}30543$
$0{,}2$	$0{,}96015$	$-0{,}70585$
$0{,}8$	$0{,}96015$	$-0{,}70585$
$1{,}5$	$0{,}96015$	$-0{,}70585$

Один запуск из $0{,}8$ возвращает лишь неглобальный минимум, тогда как мультистарт выбирает левый. При равномерном старте доля области глобального минимума в этой одномерной модели равна приблизительно $p=(0{,}07543+2)/4\approx0{,}519$ . Для шести независимых стартов вероятность хотя бы одного попадания составляет около $1-(1-p)^6\approx0{,}988$ . Этот расчёт использует известную здесь границу областей; в реальной задаче она обычно неизвестна.

Параллельная реализация

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

Нужны непересекающиеся потоки случайных чисел, единые допуски, контроль вложенной многопоточности и безопасное обновление лучшего результата. Адаптивные методы обмениваются найденными минимумами, поэтому хуже воспроизводятся. Простой мультистарт почти не требует связи и масштабируется лучше.^[1]

Преимущества и ограничения

Преимущества:

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

Ограничения:

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

Мультистарт особенно уместен как базовый метод и как контрольная линия для более сложной эвристики. Если требуется доказанная точность глобального решения, нужны методы, строящие глобальные оценки или сертификаты; увеличение числа перезапусков само по себе такого сертификата не создаёт.^[1]

Отличие от близких подходов

Подход	Что повторяется	Как используется несколько результатов
Простой мультистарт	Независимый локальный поиск из разных точек	Обычно выбирается лучший минимум; память между запусками не обязательна
Перезапуски при обучении нейронной сети	Обучение из разных начальных весов	Это применение мультистарта, если решения сравниваются по одной заранее заданной процедуре; смена темпа обучения или восстановление после сбоя сами по себе мультистартом не являются
Ансамбль алгоритмов	Обучение нескольких моделей или алгоритмов	Предсказания нескольких моделей сохраняются и объединяются, а не обязательно выбирается единственный лучший параметрический минимум
Basin hopping	Возмущение текущего состояния и локальная минимизация на каждом шаге	Новая локальная точка принимается или отклоняется, часто по критерию Метрополиса; возникает связанная траектория по минимумам, а не набор независимых стартов^[1]

Независимый внешний мультистарт можно применять и к basin hopping, но тогда это композиция двух уровней, а не тождество методов. Аналогично несколько обученных нейросетей образуют ансамбль только тогда, когда их выходы совместно используются при предсказании.

См. также

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D1%81%D1%82%D0%B0%D1%80%D1%82»

Категории: Оптимизация | Численные методы