Новый GPU-оптимизатор Chisao находит все моды мультимодальных функций: до 39x быстрее аналогов
Научная группа опубликовала на arXiv препринт, описывающий Chisao — новый оптимизатор для GPU, предназначенный для поиска всех мод мультимодальных чёрных ящиков. В отличие от традиционных методов, таких как basin-hopping, CMA-ES или мультистартовый градиентный спуск, Chisao работает со всей популяцией точек одновременно, используя полный параллелизм современных видеоускорителей.
Ключевая особенность алгоритма — асимметричный цикл сходимости-антисходимости. Точки, достигшие истинного пика, замораживаются и сохраняются, в то время как остальные продолжают исследование с помощью импульсной антисходимости и стохастически сглаженных градиентов. Это предотвращает преждевременное застревание в локальных оптимумах.
Для поддержания разнообразия популяции применяются две стратегии адаптивного ресемплинга: Repulse Monkey и Golden Rooster. Они запускают новые точки в области, которые ещё не были полностью исследованы, что особенно важно при увеличении размерности пространства.
Тестирование проводилось на полном наборе из 42 функций оптимизационного бенчмарка Университета Саймона Фрейзера для размерностей от 2 до 64. На самых сложных мультимодальных функциях при размерности 8 и выше CPU-методы переставали находить все моды, тогда как Chisao добился 100% восстановления мод на всех функциях.
Скоростные результаты впечатляют: на функции Michalewicz (d=64) ускорение составило до 34 раз по сравнению с basin-hopping, а на унимодальной функции Rotated Hyper-Ellipsoid (d=64) — до 39 раз. Важно, что все тесты проводились в безградиентном режиме (конечные разности), так что реальный выигрыш от GPU может быть ещё выше при наличии аналитических градиентов.
Алгоритм оказался устойчив к шуму: при уровне шума до ?=1.0 точность обнаружения мод осталась 100%. Это делает его применимым для задач с зашумлёнными целевыми функциями, например, в байесовском выводе или симуляциях.
Разработчики выложили реализацию в открытом доступе: пакет на Python доступен на PyPI под открытой лицензией. Это позволяет исследователям и инженерам сразу протестировать Chisao на своих задачах оптимизации.
