Мультистарт (MLSL)

Класс	Воспроизводимость	Стартовая точка	Свёртка по полосе
глобальный	полная	используется	по выбранному локальному методу

Ниже приведено окно настройки метода:

Назначение

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

Алгоритм

Мультистарт с фильтром бассейнов (Multi-Level Single Linkage). Точки-кандидаты берутся из квазислучайной последовательности Соболя, покрывающей диапазоны равномернее случайной выборки; последовательность детерминирована, поэтому прогон воспроизводим.

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

$$r_k = \pi^{-1/2} \left( \Gamma \left( 1 + \frac{n}{2} \right) \frac{\sigma \ln k}{k} \right)^{1/n}$$

где k — число просмотренных точек, σ — параметр правила. Смысл правила: «есть более перспективный сосед — этот бассейн, скорее всего, уже исследован». Радиус r_k убывает с ростом k, поэтому по ходу прогона фильтр слабеет и допускает спуски в более тесно расположенные бассейны.

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

Параметры

Параметр	Поле в интерфейсе	По умолчанию	Диапазон	На что влияет
Бюджет расчётов	Бюджет расчетов (0 = авто)	0 = авто	—	общий предел; число стартов ≈ бюджет / бюджет одного спуска
Локальный метод	Локальный метод	Доверительная область	Доверительная область / Симплекс	Симплекс — при агрегации «худшая точка» или негладкой задаче; иначе Доверительная область
Бюджет одного спуска	Бюджет одного спуска	50	25–100	компромисс «глубина ↔ охват»: больше — каждый бассейн дожимается тщательнее, но стартов меньше; меньше — шире охват при недожатых минимумах
Начальный шаг (доля диапазона)	Начальный шаг (доля диапазона)	0,150	0,05–0,25	передаётся локальному методу
Точность по параметрам (доля диапазона)	Точность	0,0010	0,0001–0,01	критерий останова каждого спуска; достигший её спуск возвращает остаток своего бюджета в общий. Прогон в целом это не останавливает — см. ниже
Останов без улучшения	Останов без улучшения (0 = выкл)	0 = выкл	0–100000	единственный критерий сходимости самого прогона: остановиться, если лучшая F не улучшалась столько расчётов подряд

Отсутствие собственной сходимости

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

Остановка прогона локальным спуском

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

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

Отдельный статус сохранён намеренно: если такой отказ когда-нибудь случится, прогон скажет об этом прямо. До его появления он сообщал «Расчёт сошёлся (достигнута точность)» — то есть критерий, которого у метода нет вообще.

Границы локальных спусков в мониторе

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

Как читать нумерацию:

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

Поколений у метода нет, поэтому флажок «Популяция» на его прогоне неактивен, а полос этапов не будет: этап у прогона один.

Рекомендации

• Заданная пользователем стартовая точка участвует как первый старт.
• Если прогон всё же остановится со статусом «остановлен вложенным методом», а результат не улучшится — задача, скорее всего, уже в оптимуме либо погрешность расчёта сравнима с разницей между кандидатами. Увеличьте точность решателя или возьмите метод без локальных спусков (ISRES, CRS2).
• Если бюджет большой, а улучшения прекращаются рано, задайте порог стагнации — иначе остаток бюджета уйдёт на спуски в уже исследованные бассейны.
• При 10 параметрах и бюджете спуска 50 в авто-бюджете (max(50, 20·n) = 200) помещается ~4 старта — для многопараметрических задач увеличивайте общий бюджет явно.
• Плохо работает с дискретными осями (переменные «с шагом» / «список») — для них предпочтите глобальный метод (DIRECT-L, CRS2, конвейер).