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

Оценка алгоритма распределения. Для каждой итерации i выполняется случайная выборка для популяции P в распределении PDu . Затем параметры распределения PDe оцениваются с использованием выбранных точек PS . Иллюстрированный пример оптимизирует непрерывную целевую функцию f(X) с уникальным оптимальным O . Выборка (соответствующая нормальному распределению N ) концентрируется вокруг оптимального значения по мере продвижения по алгоритму размотки.

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

EDA относятся к классу эволюционных алгоритмов . Основное различие между EDA и большинством традиционных эволюционных алгоритмов заключается в том, что эволюционные алгоритмы генерируют новые возможные решения, используя неявное распределение, определяемое одним или несколькими операторами вариации, тогда как EDA используют явное распределение вероятностей, закодированное байесовской сетью , многомерным нормальным распределением или другим способом. класс модели. Как и другие эволюционные алгоритмы, EDA могут использоваться для решения задач оптимизации, определенных для ряда представлений, от векторов до S-выражений в стиле LISP , а качество возможных решений часто оценивается с использованием одной или нескольких целевых функций.

Общая процедура EDA изложена в следующем:

t := 0
initialize model M(0) to represent uniform distribution over admissible solutions
while (termination criteria not met) do
    P := generate N>0 candidate solutions by sampling M(t)
    F := evaluate all candidate solutions in P
    M(t + 1) := adjust_model(P, F, M(t))
    t := t + 1

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

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

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

В этом разделе описаны модели, построенные некоторыми известными EDA различного уровня сложности. Всегда предполагается, что популяция $P(t)$ в поколении $t$, оператор выбора $S$, оператор по построению моделей $\alpha$ и оператор выборки $\beta$.

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

Самые простые EDA предполагают, что переменные решения независимы, т.е. $p(X_{1},X_{2})=p(X_{1})\cdot p(X_{2})$. Следовательно, одномерные EDA полагаются только на одномерную статистику, а многомерные распределения должны быть факторизованы как произведение $N$ одномерные распределения вероятностей,

$D_{\text{Univariate}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}).$

Такие факторизации используются во многих различных EDA, ниже мы опишем некоторые из них.

Алгоритм одномерного предельного распределения (UMDA)

УМДА — это простой EDA, использующий оператор $\alpha _{UMDA}$ для оценки предельных вероятностей из выбранной совокупности $S(P(t))$. Предполагая $S(P(t))$ содержать $\lambda$ элементы, $\alpha _{UMDA}$ производит вероятности:

$p_{t+1}(X_{i})={\dfrac {1}{\lambda }}\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N.$

Каждый шаг UMDA можно описать следующим образом.

$D(t+1)=\alpha _{\text{UMDA}}\circ S\circ \beta _{\lambda }(D(t)).$

Популяционное дополнительное обучение (PBIL)

ПБИЛ, неявно представляет совокупность по своей модели, из которой она выбирает новые решения и обновляет модель. В каждом поколении $\mu$ отдельные лица отбираются и $\lambda \leq \mu$ выбраны. Такие люди затем используются для обновления модели следующим образом:

$p_{t+1}(X_{i})=(1-\gamma )p_{t}(X_{i})+(\gamma /\lambda )\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N,$

где $\gamma \in (0,1]$ — параметр, определяющий скорость обучения , небольшое значение определяет, что предыдущая модель $p_{t}(X_{i})$ должны быть лишь слегка изменены новыми выбранными решениями. PBIL можно описать как

$D(t+1)=\alpha _{\text{PIBIL}}\circ S\circ \beta _{\mu }(D(t))$

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

ЦГА, также полагается на неявные совокупности, определяемые одномерными распределениями. В каждом поколении $t$, два человека $x,y$ отбираются, $P(t)=\beta _{2}(D(t))$. Население $P(t)$ затем сортируется в порядке убывания пригодности, $S_{{\text{Sort}}(f)}(P(t))$, с $u$ быть лучшим и $v$ это худшее решение. CGA оценивает одномерные вероятности следующим образом:

$p_{t+1}(X_{i})=p_{t}(X_{i})+\gamma (u_{i}-v_{i}),\quad \forall i\in 1,2,\dots ,N,$

где, $\gamma \in (0,1]$ — константа, определяющая скорость обучения , обычно равная $\gamma =1/N$. CGA можно определить как

$D(t+1)=\alpha _{\text{CGA}}\circ S_{{\text{Sort}}(f)}\circ \beta _{2}(D(t))$

Двумерные факторизации

Хотя одномерные модели можно эффективно вычислять, во многих случаях они недостаточно репрезентативны, чтобы обеспечить лучшую производительность, чем ГА. Чтобы преодолеть такой недостаток, в сообществе EDA было предложено использование двумерной факторизации, с помощью которой можно было моделировать зависимости между парами переменных. Двумерную факторизацию можно определить следующим образом, где $\pi _{i}$ содержит возможную переменную, зависящую от $X_{i}$, то есть $|\pi _{i}|=1$.

$D_{\text{Bivariate}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}).$

Двумерные и многомерные распределения обычно представляют в виде вероятностных графических моделей (графиков), в которых ребра обозначают статистические зависимости (или условные вероятности), а вершины обозначают переменные. Чтобы изучить структуру PGM на основе обучения связям данных, используется обучение.

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

МИМИЧЕСКИЙ факторизует совместное распределение вероятностей в цепной модели, представляющей последовательные зависимости между переменными. Он находит перестановку переменных решения, $r:i\mapsto j$, такой, что $x_{r(1)}x_{r(2)},\dots ,x_{r(N)}$ минимизирует расхождение Кульбака-Лейблера по отношению к истинному распределению вероятностей, т.е. $\pi _{r(i+1)}=\{X_{r(i)}\}$. MIMIC моделирует распространение

$p_{t+1}(X_{1},\dots ,X_{N})=p_{t}(X_{r(N)})\prod _{i=1}^{N-1}p_{t}(X_{r(i)}|X_{r(i+1)}).$

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

$P(t+1)=\beta _{\mu }\circ \alpha _{\text{MIMIC}}\circ S(P(t)).$

Алгоритм двумерного предельного распределения (BMDA)

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

Полученная модель представляет собой лес с несколькими деревьями, укорененными в узлах. $\Upsilon _{t}$. Учитывая $I_{t}$ некорневых переменных, BMDA оценивает факторизованное распределение, в котором корневые переменные могут быть выбраны независимо, тогда как все остальные должны быть обусловлены родительской переменной $\pi _{i}$.

$p_{t+1}(X_{1},\dots ,X_{N})=\prod _{X_{i}\in \Upsilon _{t}}p_{t}(X_{i})\cdot \prod _{X_{i}\in I_{t}}p_{t}(X_{i}|\pi _{i}).$

Каждый шаг BMDA определяется следующим образом

$P(t+1)=\beta _{\mu }\circ \alpha _{\text{BMDA}}\circ S(P(t)).$

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

Следующим этапом развития EDA стало использование многомерных факторизаций. В этом случае совместное распределение вероятностей обычно разлагается на несколько компонентов ограниченного размера. $|\pi _{i}|\leq K,~\forall i\in 1,2,\dots ,N$.

$p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i})$

Изучение PGM, кодирующих многомерные распределения, является вычислительно дорогостоящей задачей, поэтому EDA обычно оценивают многомерную статистику на основе двумерной статистики. Такая релаксация позволяет строить PGM за полиномиальное время. $N$; однако это также ограничивает универсальность таких EDA.

Расширенный компактный генетический алгоритм (eCGA)

ЭКГА был одним из первых EDA, применивших многомерную факторизацию, в которой можно моделировать зависимости высокого порядка между переменными решения. Его подход факторизует совместное распределение вероятностей в продукте многомерных маргинальных распределений. Предполагать $T_{\text{eCGA}}=\{\tau _{1},\dots ,\tau _{\Psi }\}$ представляет собой набор подмножеств, в котором каждое $\tau \in T_{\text{eCGA}}$ представляет собой набор связей, содержащий $|\tau |\leq K$ переменные. Факторизованное совместное распределение вероятностей представлено следующим образом:

$p(X_{1},\dots ,X_{N})=\prod _{\tau \in T_{\text{eCGA}}}p(\tau ).$

ECGA популяризировала термин «обучение по связям» как обозначение процедур, определяющих наборы связей. Его процедура обучения связям опирается на две меры: (1) сложность модели (MC) и (2) сложность сжатой совокупности (CPC). MC количественно определяет размер представления модели с точки зрения количества битов, необходимых для хранения всех предельных вероятностей.

$MC=\log _{2}(\lambda +1)\sum _{\tau \in T_{\text{eCGA}}}(2^{|\tau |-1}),$

CPC, с другой стороны, количественно оценивает сжатие данных с точки зрения энтропии предельного распределения по всем разделам, где $\lambda$ выбранный размер популяции, $|\tau |$ количество переменных решения в наборе связей $\tau$ и $H(\tau )$ - совместная энтропия переменных в $\tau$

$CPC=\lambda \sum _{\tau \in T_{\text{eCGA}}}H(\tau ).$

Обучение связям в ECGA работает следующим образом: (1) вставьте каждую переменную в кластер, (2) вычислите CCC = MC + CPC текущих наборов связей, (3) проверьте увеличение CCC, обеспечиваемое объединением пар кластеров, (4) эффективно объединяет те кластеры с наибольшим улучшением CCC. Эта процедура повторяется до тех пор, пока улучшения CCC становятся невозможными, и создается модель связи. $T_{\text{eCGA}}$. ECGA работает с конкретными совокупностями, поэтому, используя факторизованное распределение, смоделированное ECGA, его можно описать как

$P(t+1)=\beta _{\mu }\circ \alpha _{\text{eCGA}}\circ S(P(t))$

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

БОА использует байесовские сети для моделирования и выборки перспективных решений. Байесовские сети представляют собой ориентированные ациклические графы, узлы которых представляют переменные, а ребра представляют условные вероятности между парами переменных. Значение переменной $x_{i}$ может быть обусловлено максимум $K$ другие переменные, определенные в $\pi _{i}$. BOA строит PGM, кодируя факторизованное совместное распределение, в котором параметры сети, то есть условные вероятности, оцениваются на основе выбранной совокупности с использованием средства оценки максимального правдоподобия.

$p(X_{1},X_{2},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}).$

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

$P(t+1)=\beta _{\mu }\circ \alpha _{\text{BOA}}\circ S(P(t))$

Генетический алгоритм дерева связей (LTGA)

ЛТГА отличается от большинства EDA в том смысле, что он не моделирует явно распределение вероятностей, а только модель связей, называемую деревом связей. Связь $T$ представляет собой набор наборов связей, не связанных с распределением вероятностей, поэтому нет возможности выбирать новые решения непосредственно из $T$. Модель связей представляет собой дерево связей, хранящееся в виде семейства наборов (FOS).

$T_{\text{LT}}=\{\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\},\{x_{1},x_{2}\},\{x_{3},x_{4}\}\}.$

Процедура обучения дерева связей представляет собой алгоритм иерархической кластеризации , который работает следующим образом. На каждом шаге два ближайших кластера $i$ и $j$ объединяются, эта процедура повторяется до тех пор, пока не останется только один кластер, каждое поддерево сохраняется как подмножество $\tau \in T_{\text{LT}}$.

LTGA использует $T_{\text{LT}}$ руководить процедурой «оптимального смешивания», которая напоминает оператор рекомбинации, но допускает только улучшающие ходы. Мы обозначаем его как $R_{\text{LTGA}}$, где обозначение $x[\tau ]\gets y[\tau ]$ указывает на передачу генетического материала, индексируемого $\tau$ от $y$ к $x$.

Algorithm Gene-pool optimal mixing
   Input: A family of subsets $T_{\text{LT}}$ and a population $P(t)$
   Output: A population $P(t+1)$.
   for each $x_{i}$ in $P(t)$ do
       for each $\tau$ in $T_{\text{LT}}$ do
           choose a random $x_{j}\in P(t):x_{i}\neq x_{j}$
           $f_{x_{i}}$ := $f(x_{i})$
           $x_{i}[\tau ]$:= $x_{j}[\tau ]$
           if $f(x_{i})\leq f_{x_{i}}$ then
               $x_{i}[\tau ]:=x_{j}[\tau ]$
   return $P(t)$

• « ←» означает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого изменяется на значение элемента .
• « return » завершает алгоритм и выводит следующее значение.

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

$P(t+1)=R_{\text{LTGA}}(P(t))\circ \alpha _{\text{LTGA}}(P(t))$

Другой

• Коллективы вероятностей (ПК)
• Восхождение на холм с обучением (HCwL)
• Оценка многомерного нормального алгоритма (EMNA)
• Оценка алгоритма байесовских сетей (EBNA)
• Стохастическое восхождение в гору с обучением по векторам нормального распределения (SHCLVND)
• PBIL с реальным кодом
• Алгоритм эгоистичного гена (SG)
• Компактная дифференциальная эволюция (cDE) и его варианты
• Оптимизация компактного роя частиц (cPSO)
• Компактная оптимизация бактериального сбора пищи (cBFO)
• Вероятностная поэтапная эволюция программы (PIPE)
• Алгоритм оценки гауссовских сетей (EGNA)
• Многомерный нормальный алгоритм оценки с пороговой сходимостью
• Генетический алгоритм матрицы структуры зависимостей (DSMGA)

Связанный

• СМА-ES
• Метод перекрестной энтропии