Управляемый случайный поиск (CRS2)

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

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

Назначение

Стохастический глобальный поиск с популяцией точек: начальная популяция — текущая конструкция плюс случайные точки — постепенно «стягивается» к перспективным областям через симплекс-преобразования. Основной глобальный метод при n > 8 и при сильно изрезанной целевой функции, где систематическое деление пространства дорого.

Алгоритм

Управляемый случайный поиск с популяцией (Controlled Random Search). Начальная популяция из N точек — текущая конструкция плюс случайные точки в диапазонах. Далее на каждой итерации из популяции выбираются случайные n+1 точек, одна из которых — текущая лучшая, и строится проба отражением

$$x_t = 2 \bar{x} - x_{n+1}, \qquad \bar{x} = \frac{1}{n} \sum_{i=1}^{n} x_i$$

где x_t — проба, x_{n+1} — последняя из выбранных точек, а x̄ — центр остальных. Если проба попала в диапазоны и оказалась лучше худшей точки популяции, она эту худшую заменяет, иначе отбрасывается. С некоторой вероятностью вместо отражения строится «локальная мутация» — проба в окрестности лучшей точки; это и добавляет к глобальной разведке дожим.

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

Параметры

Параметр	Поле в интерфейсе	По умолчанию	Диапазон	На что влияет
Бюджет расчётов	Бюджет расчетов (0 = авто)	0 = авто	≥ размера популяции	предел числа расчётов; первые «размер популяции» расчётов — заполнение популяции (первый из них — текущая конструкция)
Размер популяции	Размер популяции (0 = авто)	0 = авто: 10·(n+1)	≥ n+2	больше — шире разведка и устойчивость к локальным минимумам, но дороже старт; при дорогих расчётах допустимо снижать до 5·(n+1)
Зерно ГСЧ	Зерно ГСЧ	1	0 — случайное	фиксированное значение делает прогон воспроизводимым; 0 — каждый запуск даёт новую траекторию (полезно для серии независимых попыток)
Останов без улучшения	Останов без улучшения (0 = выкл)	0 = выкл	0–100000	остановиться при стагнации популяции
Точность по параметрам (доля диапазона)	Точность	0,0010	0–1	останов, когда очередная улучшающая точка отличается от прежней лучшей меньше чем на этот допуск по каждой оси. Это собственный критерий сходимости CRS2; 0 — выключить и работать до бюджета. Значение по умолчанию совпадает с тем, что метод использовал до вывода поля в интерфейс, поэтому старые проекты считаются как прежде

Что видно в мониторе

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

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

• Найденную точку дожимайте локальным методом (конвейер делает это автоматически и выбирает CRS2 первым этапом при 9 ≤ n ≤ 16; выше — ISRES).
• Серия коротких запусков с зерном 0 иногда информативнее одного длинного: разброс результатов показывает мультимодальность задачи.
• Хорошо работает с дискретными осями (переменные «с шагом» / «список»).