Метод дифференциальной эволюции: векторная мутация в глобальной оптимизации

Оптимизация в непрерывных недифференцируемых пространствах

Инженерам часто приходится решать задачи глобальной оптимизации, где целевая функция представляет собой «черный ящик» — мы можем вычислить ее значение при заданных параметрах (например, запустив тяжелую аэродинамическую симуляцию), но мы совершенно не знаем ее градиентов (производных). Более того, ландшафт этой функции может быть изрезан оврагами, содержать сотни ложных локальных минимумов и иметь разрывы. Как мы уже выяснили, классические методы Ньютона или градиентного спуска в таких условиях бесполезны: они застревают в первой же яме.

Для таких задач были созданы стохастические генетические алгоритмы (ГА). Классические ГА работают путем кодирования параметров в виде бинарных строк (хромосом) из нулей и единиц. Однако при оптимизации непрерывных вещественных параметров (например, длина волны лазера, концентрация реагента в молях, напряжение в вольтах) бинарное кодирование порождает массу проблем, связанных с потерей точности и эффектом Хэмминга. В 1995 году Кеннет Прайс и Райнер Сторн разработали революционный алгоритм — Дифференциальную эволюцию (Differential Evolution, DE). Этот алгоритм изначально создавался для работы напрямую с векторами чисел с плавающей запятой, устраняя необходимость в громоздких бинарных преобразованиях.

Векторная разность как направляющая сила мутации

Дифференциальная эволюция относится к классу популяционных методов. Программа создает случайное облако (популяцию) из N возможных решений, разбросанных по всему многомерному пространству поиска. Вектор каждого решения хранит конкретные вещественные числа (координаты). Настоящая магия DE кроется в ее операторе мутации, который в корне отличается от слепого случайного шума в классических ГА.

Для того чтобы создать нового «мутанта» из текущей особи (целевого вектора), алгоритм случайным образом выбирает из популяции еще три других, абсолютно независимых вектора: A, B и C. Затем он вычисляет векторную разность между B и C. Эта математическая разность масштабируется (умножается на постоянный коэффициент мутации F) и прибавляется к вектору A. Полученный вектор становится основой для нового потомка. В чем гениальность этого подхода? Векторная разность автоматически адаптирует алгоритм к топологии ландшафта! В начале работы, когда популяция разбросана далеко друг от друга, разности огромны, и алгоритм делает гигантские разведывательные шаги, перепрыгивая через любые локальные минимумы. Когда алгоритм нащупывает глобальную долину, популяция стягивается в плотный клубок, разности между векторами становятся микроскопическими, и алгоритм переходит в режим ювелирной, сверхточной настройки параметров, не требуя ручного изменения радиуса мутации (в отличие от методов имитации отжига).

Скрещивание, селекция и индустриальное применение

После создания вектора-мутанта происходит процесс дискретного скрещивания (кроссовера). Некоторые координаты мутанта смешиваются с координатами исходного целевого вектора с заданной вероятностью (CR). Наконец, вступает в действие жесткий дарвиновский отбор: программа оценивает значение целевой функции для нового ребенка. Если ребенок оказался лучше (функция меньше), он безжалостно убивает своего родителя и занимает его место в популяции. Если ребенок хуже, он исчезает, а родитель живет дальше.

Всего три простых математических операции — сложение векторов, масштабирование разности и условная замена. Алгоритм дифференциальной эволюции умещается в 20 строк программного кода, требует настройки всего двух интуитивных параметров (F и CR) и феноменально легко распараллеливается на многоядерных процессорах. Благодаря своей беспрецедентной способности находить глобальный минимум сложных невыпуклых функций, метод DE стал основным алгоритмом для настройки гиперпараметров нейронных сетей, автоматического синтеза фрактальных Wi-Fi антенн сложной формы и проектирования молекул новых лекарственных препаратов в хемоинформатике.