Введение

Семья методов стохастической оптимизации

Алгоритмы оценки распределения (EDA), иногда называемые генетическими алгоритмами построения вероятностных моделей (PMBGAs), — это методы стохастической оптимизации, которые направляют поиск оптимального решения, строя и используя явные вероятностные модели перспективных кандидатов. Оптимизация рассматривается как последовательность инкрементных обновлений вероятностной модели, начиная с модели, кодирующей неинформативное априорное распределение допустимых решений, и заканчивая моделью, которая генерирует только глобальные оптимумы. EDA относятся к классу эволюционных алгоритмов. Основное отличие EDA от большинства традиционных эволюционных алгоритмов заключается в том, что эволюционные алгоритмы генерируют новые решения-кандидаты, используя неявное распределение, определяемое одним или несколькими операторами вариации, в то время как EDA используют явное распределение вероятностей, закодированное байесовской сетью, многомерным нормальным распределением или другим классом моделей. Подобно другим эволюционным алгоритмам, EDA могут использоваться для решения задач оптимизации, определенных в различных представлениях – от векторов до S-выражений в стиле LISP, а качество решений-кандидатов часто оценивается с использованием одной или нескольких целевых функций. Общая процедура EDA выглядит следующим образом:

t := 0
инициализировать модель M(0) для представления равномерного распределения по допустимым решениям
пока (критерии останова не выполнены) выполнять:
P := сгенерировать N > 0 решений-кандидатов путем выборки из M(t)
F := оценить все решения-кандидаты в P
M(t + 1) := обновить модель (P, F, M(t))
t := t + 1

Использование явных вероятностных моделей в оптимизации позволило EDA эффективно решать задачи оптимизации, которые были особенно сложными для большинства традиционных эволюционных алгоритмов и традиционных методов оптимизации, например, задачи с высоким уровнем эпистаза. Тем не менее, преимущество EDA также заключается в том, что эти алгоритмы предоставляют специалисту по оптимизации ряд вероятностных моделей, которые содержат много информации о решаемой задаче. Эту информацию, в свою очередь, можно использовать для разработки специфичных для задачи операторов окрестности для локального поиска, для смещения будущих запусков EDA для аналогичной задачи или для создания эффективной вычислительной модели задачи. Например, если популяция представлена битовыми строками длиной 4, EDA может представить популяцию перспективных решений, используя один вектор из четырех вероятностей (p1, p2, p3, p4), где каждый компонент p определяет вероятность того, что данная позиция будет равна 1. Используя этот вектор вероятностей, можно создать любое количество решений-кандидатов.

Оценка алгоритмов распределения (EDA)

В этом разделе описываются модели, созданные некоторыми известными EDA различной сложности. Всегда подразумевается наличие популяции в каждом поколении, оператора отбора, оператора построения модели и оператора выборки.

Одновариантные факторизации

Самые простые ЭДО предполагают, что переменные принятия решений независимы, то есть, следовательно, унивариантные ЭДО опираются только на унивариантную статистику, а многомерные распределения должны быть факторизованы как произведение унивариантных распределений вероятностей.

Такая факторизация используется во многих различных ЭДО, далее мы опишем некоторые из них.

Инкрементальное обучение населения (PBIL)

PBIL представляет популяцию неявно своей моделью, из которой он генерирует новые решения и обновляет эту модель. В каждом поколении решения генерируются и отбираются. Затем отобранные решения используются для обновления модели следующим образом: где – параметр, определяющий скорость обучения; небольшое значение указывает на то, что предыдущая модель должна быть лишь незначительно модифицирована новыми сгенерированными решениями. PBIL можно описать как

Комплексный генетический алгоритм (cGA)

CGA также опирается на неявные популяции, определяемые унивариантными распределениями. В каждом поколении отбираются два индивида, после чего популяция сортируется по убыванию пригодности, где является лучшим, а является худшим решением. CGA оценивает унивариантные вероятности следующим образом:

где – константа, определяющая скорость обучения, обычно устанавливаемая равной. CGA может быть определена как

Бивариантные факторизации

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

Взаимная информация, максимизирующая кластерирование входных данных (MIMIC)

MIMIC факторизует совместное распределение вероятностей в виде цепной модели, представляющей последовательные зависимости между переменными. Он находит перестановку переменных принятия решений, , такую, что минимизирует расхождение Кульбака — Лейблера по отношению к истинному распределению вероятностей, то есть MIMIC моделирует распределение. Новые решения отбираются от самой левой переменной к самой правой, первая генерируется независимо, а остальные – в соответствии с условными вероятностями. Поскольку оцененное распределение необходимо пересчитывать при каждой генерации, MIMIC использует конкретные популяции следующим образом:

Многомерная факторизация

Следующим этапом развития ЭДА стало использование многомерных факторизаций. В этом случае совместное распределение вероятностей обычно раскладывается на несколько компонентов ограниченного размера. Обучение ПГМ, кодирующих многомерные распределения, является вычислительно сложной задачей, поэтому ЭДА обычно оценивают многомерную статистику на основе двумерной статистики. Такое упрощение позволяет строить ПГМ за полиномиальное время, однако оно также ограничивает общность таких ЭДА.

Байесовский алгоритм оптимизации (BOA)

BOA использует байесовские сети для моделирования и выборки перспективных решений. Байесовские сети – это направленные ациклические графы, с узлами, представляющими переменные, и ребрами, представляющими условные вероятности между парами переменных. Значение переменной может быть обусловлено максимум других переменных, определенных в BOA. BOA строит PGM, кодирующую факторизованное совместное распределение, в котором параметры сети, то есть условные вероятности, оцениваются на основе отобранной популяции с использованием метода максимального правдоподобия. Структура байесовской сети, с другой стороны, должна строиться итеративно (обучение связям). Она начинается с сети без ребер и на каждом шаге добавляет ребро, которое наилучшим образом улучшает некоторую метрику оценки (например, байесовский информационный критерий (BIC) или байесовскую метрику Дирихле с эквивалентностью правдоподобия (BDe)). Метрика оценки оценивает структуру сети в соответствии с ее точностью в моделировании отобранной популяции. Из построенной сети BOA выбирает новые перспективные решения следующим образом: (1) вычисляется предковый порядок для каждой переменной, при котором каждому узлу предшествуют его родители; (2) каждая переменная выбирается условно относительно своих родителей. При таком сценарии каждый шаг BOA может быть определен как