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

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

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

2. Метод

2.1. Алгоритм DE. DE/rand/1/bin [1] оптимизирует , поддерживая набор из точек . На каждом шаге для каждой точки строится пробная точка в три этапа.

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

где выбираются равномерно из , — параметр сдвига.

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

— доля координат, заимствуемых у ; — случайная координата (гарантирует, что хотя бы одна меняется).

Шаг 3: принятие с улучшением. , если , иначе сохраняется. Размер набора , бюджет .

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

Скан: (10 значений), (11 значений) — сетка; 200 сидов в ячейке, . Порог сходимости .

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

где — результат прогона DE с сидом в ячейке . Бинаризация по на каждой оси даёт 4 класса; класс функции — модальный по .

Глобальный (профиль сходимости): вектор долей сходимости в каждой из ячеек сетки , усреднённых по :

. Каждый компонент — эмпирическая частота сходимости функции в ячейке гиперпараметров по 200 сидам и 3 размерностям. Полный дескриптор — «карта сходимости» .

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

где — класс функции при размерности . Порог осмысленности .

Adjusted Rand Index (для двух разбиений множества , , с матрицей сопряжённости , , ):

[4] , при идентичных разбиениях, при случайном; пороги: — сильное согласие, — умеренное, — слабое.

Иерархическая кластеризация UPGMA (Unweighted Pair Group Method with Arithmetic Mean): начиная с кластеров-синглетонов и попарных расстояний , на каждом шаге сливаются два ближайших кластера в ; расстояния пересчитываются по правилу взвешенного среднего:

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

MMD с RBF-ядром :

Аппроксимация случайными признаками Фурье [3]: , , , , seed . Тогда . — медианная эвристика на 5000 точках.

ELA-признаки. ELA [5] — набор числовых характеристик ландшафта оптимизации, считающихся по случайной равномерной выборке размером (в нашем эксперименте для соответственно) без запуска оптимизатора. В этой работе используются 15 признаков; ключевые с формулами:

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

где — порядок обхода, — 1-NN перестановка выборки. Коэффициент Спирмана для двух выборок — Пирсонова корреляция между рангами и (а не самими значениями). При отсутствии повторов:

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

— Асимметрия — , стандартный коэффициент асимметрии распределения значений. Сильно отрицательная — большинство выборок близки к минимуму; положительная — большинство близки к максимуму.

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

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

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

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

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

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

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

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

3.1. Координатно-ориентированный: перебор 16 пороговых пар. Распределения выраженно бимодальны: имеет пики при (93 пары) и (39 пар) — два режима DE (смешение по одной координате и по всем). Бинаризация даёт классы , .

Перебор 16 пар порогов плюс из квантилей: ни одна не даёт . Самая «стабильная» вырождается в и бессодержательна. Дело не в порогах, а в самих координатах.

3.2. Не координатно-ориентированный: -средних K=2. -средних K=2 на стандартизованных по одной точке на функцию даёт центры и , размеры . — лучше координатно-ориентированной бинаризации, но всё ниже порога. Найденная граница близка к одно-осной (ARI этой бинаризации с разбиением -средних ), что соответствует выбору режима DE (смешение по одной координате vs по всем). — локальная граница и глобальная говорят о разных структурных сигналах.

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

Таблица 1.

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

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

Колонки и заполнены только для основной бинаризации — альтернативы уже дисквалифицированы по стабильности.

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

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

UPGMA на при даёт двухклассовую таксономию (таблица 2). Стаб — единственный подход, прошедший порог осмысленности.

Таблица 2.

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

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

Колонка — среднее значение компонент (см. (5)) по всем 110 ячейкам и функциям класса.

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

8 функций без сходимости ( модально по ): 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-кластеризация при не работает (); при даёт . Одиночные ELA-признаки, бинаризованные по медиане, — сильнее (таблица 3).

Таблица 3.

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

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

Лучший — монотонность ().

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

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

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

Таблица 4.

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

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

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

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

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

Выводы.

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