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

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

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

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

Общая процедура EDA описана ниже:

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

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

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

• 1 Оценка алгоритмов распределения (EDA)
• 2 Одномерные факторизации
  • 2.1 Алгоритм одномерного маржинального распределения (UMDA)
  • 2.2 Популяционное инкрементное обучение (PBIL)
  • 2.3 Компактное генетическое алгоритм (cGA)
• 3 Двумерные факторизации
  • 3.1 Максимизация взаимной информации входной кластеризации (MIMIC)
  • 3.2 Алгоритм двумерного предельного распределения (BMDA)
• 4 Многомерные факторизации
  • 4.1 Расширенный компактный генетический алгоритм (eCGA)
  • 4.2 Байесовский алгоритм оптимизации (BOA)
  • 4.3 Генетический алгоритм дерева связей (LTGA)
• 5 Прочие
• 6 Связанные
• 7 Ссылки

В этом разделе описаны модели, построенные некоторыми хорошо известными EDA разного уровня сложности. Всегда предполагается совокупность $P\; (t)\; \{\backslash \; displaystyle\; P\; (t)\}$в поколении $t\; \{\backslash \; displaystyle\; t\}$, оператор выбора $S\; \{\backslash \; displaystyle\; S\}$, оператор построения модели $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$и оператор выборки $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$.

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

$D\; Одномерные:\; =\; p\; (X\; 1,\; \dots ,\; XN)\; =\; \prod \; i\; =\; 1\; N\; p\; (X\; i).\; \{\backslash \; displaystyle\; D\; \_\; \{\backslash \; text\; \{Univariate\}\}:\; =\; p\; (X\_\; \{1\},\; \backslash \; dots,\; X\_\; \{N\})\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; p\; (X\_\; \{i\}).\}$

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

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

UMDA - это простой EDA, в котором используется оператор $\alpha \; UMDA\; \{\backslash \; displaystyle\; \backslash \; alpha\; \_\; \{UMDA\}\}$для оценки предельных вероятностей от выбранной совокупности $S\; (P\; (t))\; \{\backslash \; displaystyle\; S\; (P\; (t))\}$. Предполагая, что $S\; (P\; (t))\; \{\backslash \; displaystyle\; S\; (P\; (t))\}$содержит $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$элементов, $\alpha \; UMDA\; \{\backslash \; displaystyle\; \backslash \; alpha\; \_\; \{UMDA\}\}$производит вероятности:

$pt\; +\; 1\; (X\; i)\; =\; 1\; \lambda \; \sum \; x\; \in \; S\; (P\; (t))\; xi,\; \forall \; i\; \in \; 1,\; 2,\dots ,\; N.\; \{\backslash \; displaystyle\; p\_\; \{t\; +\; 1\}\; (X\_\; \{i\})\; =\; \{\backslash \; dfrac\; \{1\}\; \{\backslash \; lambda\}\}\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; S\; (P\; (t))\}\; x\_\; \{i\},\; ~\; \backslash \; forall\; i\; \backslash \; in\; 1,2,\; \backslash \; dots,\; N.\}$

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

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

Постепенное обучение на основе совокупности (PBIL)

PBIL неявно представляет совокупность своей моделью, из которой он выбирает новые решения и обновляет модель. В каждом поколении отбираются $\mu \; \{\backslash \; displaystyle\; \backslash \; mu\}$индивидов и выбираются $\lambda \; \le \; \mu \; \{\backslash \; displaystyle\; \backslash \; lambda\; \backslash \; leq\; \backslash \; mu\}$. Затем такие люди используются для обновления модели следующим образом:

$pt\; +\; 1\; (X\; i)\; =\; (1\; -\; \gamma )\; pt\; (X\; i)\; +\; (\gamma \; /\; \lambda )\; \sum \; x\; \in \; S\; (P\; (t))\; xi,\; \forall \; я\; \in \; 1,\; 2,\dots ,\; N,\; \{\backslash \; displaystyle\; p\_\; \{t\; +\; 1\}\; (X\_\; \{i\})\; =\; (1-\; \backslash \; gamma)\; p\_\; \{t\}\; (X\_\; \{i\})\; +\; (\backslash \; gamma\; /\; \backslash \; lambda)\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; S\; (P\; (t))\}\; x\_\; \{i\},\; ~\; \backslash \; forall\; i\; \backslash \; in\; 1,2,\; \backslash \; dots,\; N,\}$

где $\gamma \; \in \; (0,\; 1\; ]\; \{\backslash \; displaystyle\; \backslash \; gamma\; \backslash \; in\; (0,1]\}$- параметр, определяющий скорость обучения, небольшое значение определяет, что предыдущая модель $pt\; (X\; i)\; \{\backslash \; displaystyle\; p\_\; \{t\}\; (X\_\; \{i\})\}$должен быть лишь немного изменен с помощью новых решений, выбранных в качестве образца. PBIL можно описать как

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

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

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

$pt\; +\; 1\; (X\; i)\; =\; pt\; (X\; i)\; +\; \gamma \; (ui\; -\; vi),\; \forall \; i\; \in \; 1,\; 2,\dots ,\; N,\; \{\backslash \; displaystyle\; p\_\; \{t\; +\; 1\; \}\; (X\_\; \{i\})\; =\; p\_\; \{t\}\; (X\_\; \{i\})\; +\; \backslash \; gamma\; (u\_\; \{i\}\; -v\_\; \{i\}),\; \backslash \; quad\; \backslash \; forall\; i\; \backslash \; in\; 1,2,\; \backslash \; dots,\; N,\}$

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

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

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

$D\; двумерное:\; =\; p\; (X\; 1,\dots ,\; X\; N)\; =\; \prod \; i\; =\; 1\; N\; p\; (X\; i\; |\; \pi \; i).\; \{\backslash \; displaystyle\; D\; \_\; \{\backslash \; text\; \{Bivariate\}\}:\; =\; p\; (X\_\; \{1\},\; \backslash \; dots,\; X\_\; \{N\})\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; p\; (X\_\; \{i\}\; |\; \backslash \; pi\; \_\; \{i\}).\}$

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

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

MIMIC факторизует совместное распределение вероятностей в цепочечной модели, представляющей последовательные зависимости между переменными. Он находит перестановку переменных решения, $r:\; i\; \mapsto \; j\; \{\backslash \; displaystyle\; r:\; i\; \backslash \; mapsto\; j\}$, такую, что $xr\; (1)\; xr\; (2),\dots ,\; xr\; (N)\; \{\backslash \; displaystyle\; x\_\; \{r\; (1)\}\; x\_\; \{r\; (2)\},\; \backslash \; dots,\; x\_\; \{r\; (N)\}\}$минимизирует расхождение Кульбака-Лейблера по отношению к истинному распределению вероятностей, т.е. $\pi \; r\; (i\; +\; 1)\; =\; \{X\; r\; (i)\}\; \{\backslash \; displaystyle\; \backslash \; pi\; \_\; \{r\; (i\; +\; 1)\}\; =\; \backslash \; \{X\_\; \{r\; (i)\}\; \backslash \}\}$. MIMIC моделирует распределение

$pt\; +\; 1\; (X\; 1,\dots ,\; XN)\; =\; pt\; (X\; r\; (N))\; \prod \; i\; =\; 1\; N\; -\; 1\; pt\; (X\; r\; (i)\; |\; X\; r\; (i\; +\; 1)).\; \{\backslash \; displaystyle\; p\_\; \{t\; +\; 1\}\; (X\_\; \{1\},\; \backslash \; dots,\; X\_\; \{N\})\; =\; p\_\; \{t\}\; (X\_\; \{r\; (N)\})\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{N-1\; \}\; p\_\; \{t\}\; (X\_\; \{r\; (i)\}\; |\; X\_\; \{r\; (i\; +\; 1)\}).\}$

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

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

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

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

Результирующая модель представляет собой лес с несколькими деревьями с корнями в узлах ${\rm Y}\; t\; \{\backslash \; displaystyle\; \backslash \; Upsilon\; \_\; \{t\}\}$. Учитывая $I\; t\; \{\backslash \; displaystyle\; I\_\; \{t\}\}$некорневые переменные, BMDA оценивает факторизованное распределение, в котором корневые переменные могут быть выбраны независимо, тогда как все остальные должны быть обусловлены родительская переменная $\pi \; i\; \{\backslash \; displaystyle\; \backslash \; pi\; \_\; \{i\}\}$.

$pt\; +\; 1\; (X\; 1,\dots ,\; XN)\; =\; \prod \; X\; i\; \in \; {\rm Y}\; tpt\; (X\; i)\; \cdot \; \prod \; X\; i\; \in \; I\; tpt\; (\; X\; i\; |\; \pi \; i).\; \{\backslash \; displaystyle\; p\_\; \{t\; +\; 1\}\; (X\_\; \{1\},\; \backslash \; dots,\; X\_\; \{N\})\; =\; \backslash \; prod\; \_\; \{X\_\; \{i\}\; \backslash \; in\; \backslash \; Upsilon\; \_\; \{t\}\}\; p\_\; \{t\}\; (X\_\; \{i\})\; \backslash \; cdot\; \backslash \; prod\; \_\; \{X\_\; \{i\}\; \backslash \; in\; I\_\; \{t\}\}\; p\_\; \{t\}\; (X\_\; \{i\}\; |\; \backslash \; pi\; \_\; \{i\}).\}$

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

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

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

$p\; (X\; 1,\dots ,\; XN)\; знак\; равно\; \prod \; я\; знак\; равно\; 1\; N\; п\; (Икс\; я\; |\; \pi \; я)\; \{\backslash \; Displaystyle\; р\; (X\_\; \{1\},\; \backslash \; точки,\; X\_\; \{N\})\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; p\; (X\_\; \{i\}\; |\; \backslash \; pi\; \_\; \{i\})\}$

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

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

ECGA был одним из первых EDA, который использовал многомерные факторизации, в которых можно моделировать зависимости высокого порядка между переменными решения. Его подход факторизует совместное распределение вероятностей в произведении многомерных маржинальных распределений. Допустим, $T\; eCGA\; =\; \{\tau \; 1,\dots ,\; \tau \; \Psi \}\; \{\backslash \; displaystyle\; T\; \_\; \{\backslash \; text\; \{eCGA\}\}\; =\; \backslash \; \{\backslash \; tau\; \_\; \{1\},\; \backslash \; dots,\; \backslash \; tau\; \_\; \{\backslash \; Psi\}\; \backslash \}\}$- это набор подмножеств, в котором каждый $\tau \; \in \; T\; eCGA\; \{\backslash \; displaystyle\; \backslash \; tau\; \backslash \; in\; T\; \_\; \{\backslash \; text\; \{eCGA\}\}\}$представляет собой набор связей, содержащий $|\; \tau \; |\; \le \; K\; \{\backslash \; displaystyle\; |\; \backslash \; tau\; |\; \backslash \; leq\; K\}$переменные. Факторизованное совместное распределение вероятностей представляется следующим образом:

$p\; (X\; 1,\dots ,\; X\; N)\; =\; \prod \; \tau \; \in \; T\; eCGA\; p\; (\tau ).\; \{\backslash \; displaystyle\; p\; (X\_\; \{1\},\; \backslash \; dots,\; X\_\; \{N\})\; =\; \backslash \; prod\; \_\; \{\backslash \; tau\; \backslash \; in\; T\; \_\; \{\backslash \; text\; \{eCGA\}\}\}\; p\; (\backslash \; tau).\}$

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

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

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

$CPC\; =\; \lambda \; \sum \; \tau \; \in \; T\; eCGA\; H\; (\tau ).\; \{\backslash \; displaystyle\; CPC\; =\; \backslash \; lambda\; \backslash \; sum\; \_\; \{\backslash \; tau\; \backslash \; in\; T\; \_\; \{\backslash \; text\; \{eCGA\}\}\}\; H\; (\backslash \; tau).\}$

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

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

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

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

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

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

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

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

LTGA отличается от большинства EDA в том смысле, что не моделирует явно распределение вероятностей, а только модель связи, называемую деревом связей. Связь $T\; \{\backslash \; displaystyle\; T\}$- это набор наборов связей, не связанный с распределением вероятностей, поэтому нет возможности пробовать новые решения непосредственно из $T\; \{\backslash \; displaystyle\; T\}$. Модель связи представляет собой дерево связей, созданное в виде семейства наборов (FOS).

$T\; LT\; =\; \{\{x\; 1\},\; \{x\; 2\},\; \{x\; 3\},\; \{x\; 4\},\; \{x\; 1,\; x\; 2\},\; \{x\; 3,\; x\; 4\}\}.\; \{\backslash \; displaystyle\; T\; \_\; \{\backslash \; text\; \{LT\}\}\; =\; \backslash \; \{\backslash \; \{x\_\; \{1\}\; \backslash \},\; \backslash \; \{x\_\; \{2\}\; \backslash \},\; \backslash \; \{x\_\; \{3\}\; \backslash \},\; \backslash \; \{x\_\; \{4\}\; \backslash \},\; \backslash \; \{x\_\; \{1\},\; x\_\; \{2\}\; \backslash \},\; \backslash \; \{x\_\; \{3\},\; x\_\; \{4\}\; \backslash \}\; \backslash \}.\}$

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

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

Алгоритм Оптимальное смешивание генофонда Вход: семейство подмножеств $T\; LT\; \{\backslash \; displaystyle\; T\; \_\; \{\backslash \; text\; \{LT\}\}\; \}$и совокупность $P\; (t)\; \{\backslash \; displaystyle\; P\; (t)\}$Вывод: совокупность $P\; (t\; +\; 1)\; \{\backslash \; displaystyle\; P\; (t\; +1)\}$. для каждого $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$in$P\; (t)\; \{\backslash \; displaystyle\; P\; (t)\}$doдля каждого $\tau \; \{\backslash \; displaystyle\; \backslash \; tau\}$in$T\; LT\; \{\backslash \; displaystyle\; T\; \_\; \{\backslash \; text\; \{LT\}\}\}$doвыберите случайный $xj\; \in \; P\; (t):\; xi\; \ne \; xj\; \{\backslash \; displaystyle\; x\_\; \{j\}\; \backslash \; in\; P\; (t):\; x\_\; \{i\}\; \backslash \; neq\; x\_\; \{j\}\}$$fxi\; \{\backslash \; displaystyle\; f\_\; \{x\_\; \{i\}\}\}$: = $f\; (xi)\; \{\backslash \; displaystyle\; f\; (x\_\; \{i\})\}$$xi\; [\tau ]\; \{\backslash \; displaystyle\; x\_\; \{i\}\; [\backslash \; tau]\}$: = $xj\; [\tau ]\; \{\backslash \; дис\; стиль\; игры\; x\_\; \{j\}\; [\backslash \; tau]\}$if$f\; (xi)\; \le \; fxi\; \{\backslash \; displaystyle\; f\; (x\_\; \{i\})\; \backslash \; leq\; f\_\; \{x\_\; \{i\}\}\}$, затем$xi\; [\tau ]:\; =\; xj\; [\tau ]\; \{\backslash \; displaystyle\; x\_\; \{i\}\; [\backslash \; tau]:\; =\; x\_\; \{j\}\; [\backslash \; tau]\}$возврат$P\; (t)\; \{\backslash \; displaystyle\; P\; (\; t)\}$

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

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

$P\; (T\; +\; 1)\; знак\; равно\; R\; LTGA\; (P\; (t))\; \circ \; \alpha \; LTGA\; (P\; (t))\; \{\backslash \; displaystyle\; P\; (t\; +\; 1)\; =\; R\; \_\; \{\backslash \; text\; \{LTGA\}\}\; (P\; (t))\; \backslash \; circ\; \backslash \; alpha\; \_\; \{\backslash \; text\; \{LTGA\}\}\; (P\; (t))\}$

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

• CMA-ES
• Cross- энтропийный метод