ПОВЕДЕНЧЕСКАЯ ТАКСОНОМИЯ ФУНКЦИЙ ПО РЕЗУЛЬТАТАМ ПРОГОНА DE: ОТ ЛОКАЛЬНОГО ДЕСКРИПТОРА (ARGMIN) К ГЛОБАЛЬНОМУ (ПРОФИЛЬ СХОДИМОСТИ)

1. Постановка

Можно ли классифицировать функции оптимизации по «отпечатку» поведения алгоритма? Подход: прогнать алгоритм по сетке гиперпараметров и взять координаты лучшей ячейки в качестве дескриптора функции; разделение на ячейки порождает классификацию. Проверяем для DE/rand/1/bin [1].

2. Метод

2.1. Алгоритм DE. DE/rand/1/bin [1] оптимизирует f:[0,1]^D→R, поддерживая набор из mточек {x_i}_i^m=1⊂[0,1]^D. На каждом шаге для каждой точки xi строится пробная точка u_i в три этапа.

Шаг 1: сдвиг по разности.

 (1)

где r₁,r₂,r₃ выбираются равномерно из {1,…,m}\{i}, F∈[0,1] — параметр сдвига.

Шаг 2: биномиальное смешение координат.

 (2)

cr∈[0,1] — доля координат, заимствуемых у v_i; d_rand — случайная координата (гарантирует, что хотя бы одна меняется).

Шаг 3: принятие с улучшением. x_i←u_i, если f(u_i)<f(x_i), иначе x_i сохраняется. Размер набора m=64, бюджет T_max=10⁵.

2.2. Эксперимент. 67 функций SFU [2] (60 на R₂, 7 на R⁴), приведённых к [0,1] по эмпирическим f_min,f_max. Из 72 функций SFU исключены 5 без [0,1]-нормировки на стандартной области (Rosenbrock ND, Schwefel 1.2, Ackley ND, Zakharov ND, Dixon-Price ND): их f-масштаб несравним с остальными. Поднятие до D — усреднением по непересекающимся плиткам:

 (3)

Скан: F∈{0,1;0,2;…;1,0} (10 значений), cr∈{0;0,1;…;1,0} (11 значений) — 10×11 сетка; 200 сидов в ячейке, D∈{16,32,64}. Порог сходимости f_x<0,01.

2.3. Два дескриптора. Локальный (argmin): координаты ячейки с наименьшим средним f_x (при равенстве выбирается ячейка с наименьшим F, затем с наименьшим cr — 4 функции из 67 имеют ничьи),

 (4)

где f_x^(s)(F,cr) — результат прогона DE с сидом s в ячейке (F, cr). Бинаризация F^⋆, cr^⋆ по 0,5 на каждой оси даёт 4 класса; класс функции — модальный по D.

Глобальный (профиль сходимости): вектор долей сходимости в каждой из 10×11=110 ячеек сетки (F, cr), усреднённых по D:

 (5)

i=1,…,10; j=0,…,10. Каждый компонент — эмпирическая частота сходимости функции f_n в ячейке гиперпараметров (F_i, cr_j) по 200 сидам и 3 размерностям. Полный дескриптор c_n∈R¹¹⁰ — «карта сходимости» f_n.

2.4. Метрики качества таксономии. Стабильность по размерности:

 (6)

где C(n,D) — класс функции n при размерности D. Порог осмысленности Стаб>70%.

Adjusted Rand Index (для двух разбиений A, B множества Ω, |Ω|=N, с матрицей сопряжённости n_ij=|A_i∩B_j|, a_i=∑_j​n_ij, b_j=∑_i​n_ij):

 (7)

ARI [4]∈[-1,1],=1 при идентичных разбиениях, =0 при случайном; пороги: >0,6 — сильное согласие, ∈[0,3, 0,6] — умеренное, <0,3 — слабое.

Иерархическая кластеризация UPGMA (Unweighted Pair Group Method with Arithmetic Mean): начиная с N кластеров-синглетонов {C₁,…,C_N} и попарных расстояний d(C_i,C_j), на каждом шаге сливаются два ближайших кластера C_i,C_j в C_ij=C_i∪C_j; расстояния пересчитываются по правилу взвешенного среднего:

 (8)

Применяем к евклидовым расстояниям между стандартизованными векторами cили F^⋆,cr^⋆. k-средних — стандартный, со случайной инициализацией центров (20 запусков, выбирается лучший по сумме квадратов отклонений).

MMD² _{с RBF-ядром} k(x,y)=exp(-∥x-y∥²/(2h²)):

 (9)​

Аппроксимация случайными признаками Фурье [3]: φ(x)=√2/D_rffcos(Wx+b), W_ij∼N(0,1/h²), bj∼U[0,2π], D_rff=1000, seed=42. Тогда MMD²(P,Q)≈∥φ_P-φ_Q∥². h² — медианная эвристика на 5000 точках.

ELA-признаки. ELA [5] — набор числовых характеристик ландшафта оптимизации, считающихся по случайной равномерной выборке {(x_i,f(x_i))}i^N=1 размером N=min(50D, 5000) (в нашем эксперименте N=800, 1600, 3200 для D=16,32,64 соответственно) без запуска оптимизатора. В этой работе используются 15 признаков; ключевые с формулами:

— Монотонность — коэффициент ранговой корреляции Спирмана между порядком обхода выборки методом «иди к ближайшему ещё не посещённому соседу» (1-NN-обход) и значениями f в этой последовательности. Если функция монотонно убывает к минимуму, то на пути к минимуму f также монотонно падает ⇒ высокая монотонность.

 (10)

где t_i=1,…,N — порядок обхода, π — 1-NN перестановка выборки. Коэффициент Спирмана ρ_Spearman(X,Y) для двух выборок {(x_i,y_i)}i^N=1 — Пирсонова корреляция между рангами x_i и y_i (а не самими значениями). При отсутствии повторов:

 (11)

ρ=+1 — Y монотонно растёт по X; ρ=-1 — монотонно убывает; ρ=0 — нет монотонной зависимости. В отличие от Пирсоновой корреляции (которая ловит только линейную зависимость), Спирмана инвариантен к любым монотонным преобразованиям и не требует fбыть линейной.

— Асимметрия f — γ₁({f(x_i)})=μ₃/σ³, стандартный коэффициент асимметрии распределения значений. Сильно отрицательная — большинство выборок близки к минимуму; положительная — большинство близки к максимуму.

— Convex R² — коэффициент детерминации квадратичной регрессии:

 (12)

где (A, b, c) — параметры МНК (метода наименьших квадратов). Близок к 1 для функций квадратичной формы.

— FDC (Fitness-Distance Correlation) — Пирсонова корреляция между значениями f(x_i) и расстояниями до известного глобального минимума x^⋆:

 (13)

FDC→1 — доминирующий бассейн; FDC→0 — много сравнимых бассейнов.

— NBC (Nearest Better Clustering): для каждой выборки x_i находим её 10 ближайших соседей и проверяем, является ли x_i минимальной по f среди них. Признак NBC #лок. мин. — число таких «локальных минимумов»:

 (14)

Отнош. NBC — отношение медианных расстояний до 1-го и до 2-го ближайшего соседа: характеризует «густоту» структуры минимумов.

Остальные 9 признаков (показатель Гёльдера α, доля плато, информационное содержание, отношение бассейнов, рассеяние топ-5, рассеяние топ-25, смещение лучшей массы, n_attractors, доля длинных NBC) — аналогичные структурные характеристики ландшафта; полные формулы — в [5].

3. Локальный дескриптор: проверки проваливаются

3.1. Координатно-ориентированный: перебор 16 пороговых пар. Распределения (F^⋆, cr^⋆) выраженно бимодальны: cr^⋆ имеет пики при cr∈[0, 0,1] (93 пары) и cr∈[0,9, 1] (39 пар) — два режима DE (смешение по одной координате и по всем). Бинаризация 0,5, 0,5 даёт классы 45/10/6/6, Стаб=30%.

Перебор 16 пар порогов (F_t,cr_t)∈{0,2,0,3,0,4,0,5,0,6}×{0,3,0,5,0,7} плюс 0,30, 0,20 из квантилей: ни одна не даёт Стаб>43%. Самая «стабильная» 0,6, 0,7 вырождается в 53/6/5/3 и бессодержательна. Дело не в порогах, а в самих координатах.

3.2. Не координатно-ориентированный: k-средних K=2. k-средних K=2 на стандартизованных (F^⋆, cr^⋆) по одной точке на функцию даёт центры (F^⋆≈0,25, cr^⋆≈0,15) и (F^⋆≈0,50, cr^⋆≈0,69), размеры 43/24. Стаб=49% — лучше координатно-ориентированной бинаризации, но всё ниже порога. Найденная граница близка к одно-осной cr^⋆<0,50 (ARI этой бинаризации с разбиением k-средних=0,72), что соответствует выбору режима DE (смешение по одной координате vs по всем). ARI(k-средних, профиль K=2)=0,13 — локальная граница и глобальная говорят о разных структурных сигналах.

3.3. Сводка локальных дескрипторов. Сводка показана в таблице 1 — ни один локальный дескриптор не проходит порог осмысленности.

Таблица 1.

Сводка локальных дескрипторов

Дескриптор	Стаб, %	ARIMMD	ARIELA
Координатная (0,5; 0,5)	30	−0,06	0,10
16 порогов: max	43	—	—
k-средних K=2	49	—	—
Порог осмысленности	> 70	> 0,3	> 0,3

 

Колонки ARI_MMD и ARI_ELA заполнены только для основной бинаризации (0,5, 0,5) — альтернативы уже дисквалифицированы по стабильности.

Причина — у DE нет узкого оптимума в (F, cr). Контраст ⟨f_x⟩^⋆/f ‾_x^grid=0,41 (только 2,4× выигрыш от выбора лучшей ячейки), доля ячеек с f_x<0,01 при случайном выборе=30%. Argmin внутри плато выбирается с большой долей случайности — никакая локальная классификация не извлечёт стабильный сигнал.

4. Глобальный дескриптор: профиль работает

UPGMA на c∈R¹¹⁰ при K=2 даёт двухклассовую таксономию (таблица 2). Стаб=73% — единственный подход, прошедший порог осмысленности.

Таблица 2.

Двухклассовая таксономия по профилю сходимости

Класс	n	⟨c⟩	Представители
DE-Устойчивые	33	0,90	Sphere, Trid, Powell, Rosenbrock, Bohachevsky, Levy, Griewank, …
DE-Чувствительные	34	0,26	Ackley, Rastrigin, Schwefel, Easom, Langermann, megacity, Shubert-семейство, …

 

Колонка ⟨c⟩ — среднее значение компонент c_n^(i,j) (см. (5)) по всем 110 ячейкам и функциям класса.

Граница соответствует одно-бассейновости / многобассейновости функции (по составу классов и по связи с ELA-признаками, §5). DE-Устойчивые (⟨c⟩=0,90): DE сходится почти в любой ячейке; DE-Чувствительные (⟨c⟩=0,26): только в малой части. Расширение до K=3 (UPGMA на тех же c-векторах) дробит DE-Чувствительные на «решаемые многомодальные» и «трудные», но стабильность падает до 39% — ниже порога осмысленности 70%, поэтому в основном результате не используется.

8 функций без сходимости (f_x^⋆≥0,01 модально по D): Drop-Wave, Easom, Eggholder, Langermann, megacity, Shekel, shifted_weierstrass, shubert_coupled — все в DE-Чувствительные. Структурно делятся на пять типов: плато с одиночной иглой (Easom, megacity), разнесённые узкие минимумы (Langermann, Shekel), фрактальная шероховатость (shifted_weierstrass), регулярная решётка минимумов (shubert_coupled), широкие бассейны с рябью или угловым минимумом (Drop-Wave, Eggholder).

5. ELA-предсказание K=2

Многопризнаковая ELA-кластеризация при K=2 не работает (ARI=-0,001); при K∈{4,5} даёт ARI∈0,31, 0,33. Одиночные ELA-признаки, бинаризованные по медиане, — сильнее (таблица 3).

Таблица 3.

ELA-предикторы, бинаризованные по медиане

ELA-признак	Лучший ARI	Размеры
монотонность	0,573	34/33
асимметрия f	0,484	34/33
отнош. NBC	0,443	40/27
#лок. мин. (NBC)	0,365	34/33
convex R2 / FDC	0,365	40/27

 

Лучший — монотонность (ARI=0,57).

Если монотонность функции выше медианы — кандидат в DE-Устойчивые; если ниже — DE-Чувствительные. Точность ∼80%. Тот факт, что несколько разных структурных признаков (монотонность, асимметрия f, FDC, NBC, convex R²) предсказывают одну и ту же границу, — свидетельство её реального структурного смысла, а не случайного разбиения. При этом многопризнаковый ансамбль (UPGMA на 15-мерном векторе) даёт ARI всего 0,33 при K=4 — заметно хуже лучшего одиночного признака — монотонности (0,57). Объяснение: 9 информативных ELA-признаков сильно коррелированы между собой (все измеряют, грубо говоря, степень одно-бассейновости функции), и евклидово расстояние в 15-мерном пространстве размывает сигнал лучшего канала шумом остальных.

6. Обсуждение и выводы

Сравнение двух подходов к таксономии для DE приведено в таблице 4.

Таблица 4.

Сравнение двух подходов к таксономии для DE

Характеристика	Локальный (argmin)	Глобальный (профиль)
Размерность дескриптора	2	110
Стаб по D	30–49%	73%
ARIMMD (RFF-MMD UPGMA)	−0,06	—
ARIELA, многопризнаковая UPGMA	0,10	0,33
ARIELA, лучший одиночный признак (бинаризация по медиане)	0,22 (Hölder α)	0,57 (монотонность)

 

Все значения ARI — максимум по соответствующему диапазону параметров (число кластеров K для UPGMA-методов; квантиль бинаризации для одиночного признака).

Локальный не работает: у DE нет узкого оптимума в (F, cr) — есть широкое плато (контраст 2,4×). Argmin внутри плато случаен, таксономия наследует шум. Глобальный работает: информация о функции — в форме карты P(conv) по всей сетке, а не в положении лучшей ячейки.

Гипотеза для практики: чем выше контраст argmin/grid (т.е. чем уже оптимум алгоритма по гиперпараметрам), тем больше шансов у локального дескриптора. В нашем эксперименте контраст 2,4× оказался недостаточным; конкретный порог, выше которого локальный подход начинает работать, — предмет проверки на других алгоритмах.

Выводы.

1. Argmin-таксономия для DE проваливает три проверки (Стаб 30%, ARI_MMD=-0,06, ARI_ELA=0,10). 16 порогов и k-средних K=2 (49%) тоже не достигают 70%.
2. Профиль сходимости даёт устойчивую K=2 таксономию: DE-Устойчивые (33) / DE-Чувствительные (34), Стаб=73%.
3. Один ELA-признак — монотонность — предсказывает её с ARI=0,57.
4. Для DE/rand/1/bin (с его широким плато оптимальных параметров) дескриптор должен быть глобальным (профиль), а не локальным (argmin). Обобщение на алгоритмы с другой чувствительностью к гиперпараметрам — предмет будущих проверок.