Новый алгоритм ZIG-EDA: эффективная разреженная оптимизация без ручных операторов

Исследователи из международной группы опубликовали на arXiv препринт, в котором предложили новый метод для разреженной оптимизации — ZIG-EDA. Алгоритм основан на многомерных нуль-инфляционных гауссовых (ZIG) распределениях и предназначен для решения задач, где оптимальное решение содержит много нулевых коэффициентов.

Традиционные эволюционные алгоритмы, такие как генетические или эволюционные стратегии, используют ручные операторы мутации и скрещивания. Для задач с неизвестной структурой это может вносить смещение. Алгоритмы оценки распределения (EDA) обходят эту проблему, подбирая вероятностное распределение по лучшим особям и генерируя из него новую популяцию. Однако до сих пор EDA не были адаптированы для разреженных пространств параметров.

ZIG-EDA закрывает этот пробел. Нуль-инфляционное распределение моделирует как разреженность (какие параметры равны нулю), так и значения активных параметров, а также корреляции между ними. Это позволяет оптимизировать разреженность и активные значения совместно, без иерархий или пороговых значений.

Авторы доказали, что латентные параметры модели идентифицируемы по наблюдаемым выборкам, и разработали практические амортизированные оценщики на основе обращения матриц. Эти оценщики точно восстанавливают латентные корреляционные структуры.

В тесте на бенчмарке Lunar Lander ZIG-EDA показал более быструю сходимость и достиг более высоких итоговых наград по сравнению с плотным гауссовым EDA, ручным разреженным эволюционным алгоритмом и наивным разреженным EDA. При этом найденные контроллеры использовали лишь малую долю активных параметров.

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